tpl_union.H

# ifndef TPL_UNION_H
# define TPL_UNION_H

# include <tpl_dynArray.H>
# include <tpl_dynSetTree.H>
 
# define UNION_ATTRS           \
  DynArray<size_t> id;         \
  DynArray<size_t> sz;         \
  size_t           num_blocks;

# define UNION_ROOT_IMPL \
  while (i != id(i))     \
    {                    \
      id(i) = id(id(i)); \
      i = id(i);         \
    }                    \
                         \
  return i;                                     

# define UNION_DEPTH            \
  size_t depth(size_t i)        \
  {                             \
    const int & parent = id(i); \
                                \
    if (parent == i)            \
      return 1;                 \
                                \
    return 1 + depth(parent);   \
  }

# define UNION_CTOR             \
  : num_blocks(n)               \
  {                             \
    id.reserve(n);              \
    sz.reserve(n);              \
                                \
    for (int i = 0; i < n; ++i) \
      {                         \
        id(i) = i;              \
        sz(i) = 1;              \
      }                         \
  }

# define UNION_PUBLIC_ROUTINES                          \
  size_t size() const { return id.size(); }             \
                                                        \
  size_t get_num_blocks() const { return num_blocks; }  \
                                                        \
  bool are_connected(size_t i, size_t j)                \
  {                                                     \
    return root(i) == root(j);                          \
  }                                                     \
                                                        \
  void join(size_t i, size_t j)                         \
  {                                                     \
    i = root(i);                                        \
    j = root(j);                                        \
    if (i == j)                                         \
      return;                                           \
                                                        \
    if (sz(i) < sz(j))                                  \
      {                                                 \
        id(i) = j;                                      \
        sz(j) += sz(i);                                 \
      }                                                 \
    else                                                \
      {                                                 \
        id(j) = i;                                      \
        sz(i) += sz(j);                                 \
      }                                                 \
    --num_blocks;                                       \
  }                                                                     

class Fixed_Relation
{
  UNION_ATTRS

  size_t root(size_t i)
  {
    UNION_ROOT_IMPL
  }

  UNION_DEPTH

public:

  Fixed_Relation(size_t n) UNION_CTOR

  UNION_PUBLIC_ROUTINES
};


class Relation
{
  UNION_ATTRS

  void verify_if_add_new_points(size_t n)
  {
    size_t l = size();
    if (n < l)
      return;
    
    id.reserve(l, n);
    sz.reserve(l, n);
    for (int i = l; i <= n; ++i)
      {
        id(i) = i;
        sz(i) = 1;
      }
    num_blocks += n - l + 1;
  }

  size_t root(size_t i)
  {
    verify_if_add_new_points(i);
    UNION_ROOT_IMPL;
  }

  UNION_DEPTH

public:

  Relation(size_t n = 0) UNION_CTOR

  UNION_PUBLIC_ROUTINES
};


    template <typename T, class Compare = Aleph::less<T>>
class Relation_T : public Relation
{
  struct Pair
  {
    T      item;
    size_t i;

    Pair() {}

    Pair(const T & __item, size_t __i) 
      : item(__item), i(__i) { /* empty */ }
  };

  struct Cmp
  {
    bool operator () (const Pair & p1, const Pair & p2) const
    {
      return Compare() (p1.item, p2.item);
    }
  };

  DynSetAvlTree<Pair, Cmp> items_tree;

  // retorna el id del item; sea porque lo encuentra o porque lo inserta
  size_t test_and_insert_new_item(const T & item)
  {
    size_t N = size();
    Pair p(item, N);
    Pair * ptr = items_tree.search_or_insert(p);
    return ptr->i;
  }

public:

  bool are_connected(const T & p, const T & q)
  {
    size_t i = test_and_insert_new_item(p);
    size_t j = test_and_insert_new_item(q);

    return Relation::are_connected(i, j);
  }

  void join(const T & p, const T & q)
  {
    size_t i = test_and_insert_new_item(p);
    size_t j = test_and_insert_new_item(q);
    Relation::join(i, j);
  }
};

# endif // TPL_UNION_H