// -*- c++ -*- //

 #ifndef HUGO_UNION_FIND_H

 #define HUGO_UNION_FIND_H

 #include <vector>

 #include <list>

 #include <utility>

 #include <algorithm>

 #include <invalid.h>

 namespace hugo {

   template <typename T, typename TIntMap>

   class UnionFind {

   public:

     typedef T ElementType;

     typedef std::pair<int,int> PairType;

   private:

     std::vector<PairType> data;

     TIntMap& map;

   public:

     UnionFind(TIntMap& m) : map(m) {}

     int find(T a)

     {

       int comp0 = map[a];

       if (comp0 < 0) {

 	return insert(a);

       }

       int comp = comp0;

       int next;

       while ( (next = data[comp].first) != comp) {

 	comp = next;

       }

       while ( (next = data[comp0].first) != comp) {

 	data[comp0].first = comp;

 	comp0 = next;

       }

       return comp;

     }

     int insert(T a)

     {

       int n = data.size();

       data.push_back(std::make_pair(n, 1));

       map.set(a,n);

       return n;

     }

     bool join(T a, T b)

     {

       int ca = find(a);

       int cb = find(b);

       if ( ca == cb ) 

 	return false;

       if ( data[ca].second > data[cb].second ) {

 	data[cb].first = ca;

 	data[ca].second += data[cb].second;

       }

       else {

 	data[ca].first = cb;

 	data[cb].second += data[ca].second;

       }

       return true;

     }

     int size(T a)

     {

       int ca = find(a);

       return data[ca].second;

     }

   };

   /*******************************************************/

   template <typename T>

   struct UnionFindEnumItem {

     typedef std::list<UnionFindEnumItem> ItemList;

     typedef std::list<ItemList> ClassList;

     typedef typename ItemList::iterator IIter;

     typedef typename ClassList::iterator CIter;

     T me;

     IIter parent;

     int size;

     CIter my_class;

     UnionFindEnumItem() {}

     UnionFindEnumItem(const T &_me, CIter _my_class): 

       me(_me), size(1), my_class(_my_class) {}

   };

   template <typename T, template <typename Item> class Map>

   class UnionFindEnum {

     typedef std::list<UnionFindEnumItem<T> > ItemList;

     typedef std::list<ItemList> ClassList;

     typedef typename ItemList::iterator IIter;

     typedef typename ItemList::const_iterator IcIter;

     typedef typename ClassList::iterator CIter;

     typedef typename ClassList::const_iterator CcIter;

   public:

     typedef T ElementType;

     typedef UnionFindEnumItem<T> ItemType;

     typedef Map< IIter > MapType;

   private:

     MapType& m;

     ClassList classes;

     //    IIter where(const T &a) { return m[a]; }

     //    IIter parent(IIter a) { return a->parent; }

     //    P sibling(P a) { return &m[a->sibling]; }

     IIter _find(IIter a) const {

       IIter comp = a;

       IIter next;

       while( (next = comp->parent) != comp ) {

 	comp = next;

       }

       IIter comp1 = a;

       while( (next = comp1->parent) != comp ) {

 	comp1->parent = comp->parent;

 	comp1 = next;

       }

       return comp;

     }

   public:

     UnionFindEnum(MapType& _m) : m(_m) {}

     void insert(const T &a)

     {

       classes.push_back(ItemList());

       CIter aclass = classes.end();

       --aclass;

       ItemList &alist = *aclass;

       alist.push_back(ItemType(a, aclass));

       IIter ai = alist.begin();

       ai->parent = ai;

       m.set(a, ai);

     }

     T find(const T &a) const {

       return _find(m[a])->me;

     }

     bool join(T a, T b) {

       IIter ca = _find(m[a]);

       IIter cb = _find(m[b]);

       if ( ca == cb ) {

 	return false;

       }

       if ( ca->size > cb->size ) {

 	cb->parent = ca->parent;

 	ca->size += cb->size;

 	ItemList &alist = *ca->my_class;

 	alist.splice(alist.end(),*cb->my_class);

 	classes.erase(cb->my_class);

 	cb->my_class = 0;

       }

       else {

 	ca->parent = cb->parent;

 	cb->size += ca->size;

 	ItemList &blist = *cb->my_class;

 	blist.splice(blist.end(),*ca->my_class);

 	classes.erase(ca->my_class);

 	ca->my_class = 0;

       }

       return true;

     }

     int size(const T &a) const {

       return _find(m[a])->size;

     }

     void split(const T &a) {

       IIter ca = _find(m[a]);

       if ( ca->size == 1 )

 	return;

       CIter aclass = ca->my_class;

       for(IIter curr = ca; ++curr != aclass->end(); curr=ca) {

 	classes.push_back(ItemList());

 	CIter nl = --classes.end();

 	nl->splice(nl->end(), *aclass, curr);

 	curr->size=1;

 	curr->parent=curr;

 	curr->my_class = nl;

       }

       ca->size=1;

       return;

     }

     void erase(const T &a) {

       IIter ma = m[a];

       if (ma == 0) return;

       IIter la = _find(ma);

       if (la == ma) {

 	if (ma -> size == 1){

 	  classes.erase(ma->my_class);

 	  m.set(a,0);

 	  return;

 	}

 	++la;

 	la->size = ma->size - 1; 

 	la->my_class = ma->my_class;	

       }

       for (IIter i = la; i != la->my_class->end(); ++i) {

 	i->parent = la;

       }

       la->my_class->erase(ma);

       m.set(a,0);

     }

     void eraseClass(const T &a) {

       IIter ma = m[a];

       if (ma == 0) return;

 #     ifdef DEBUG

       CIter c = _find(ma)->my_class;

       for (IIter i=c->begin(); i!=c->end(); ++i)

 	m.set(i->me, 0);

 #     endif

       classes.erase(_find(ma)->my_class);

     }

     class ClassIt {

       friend class UnionFindEnum;

       CcIter i;

     public:

       ClassIt(Invalid): i(0) {}

       ClassIt() {}

       operator const T& () const { 

 	ItemList const &ll = *i;

 	return (ll.begin())->me; }

       bool operator == (ClassIt it) const {

 	return (i == it.i);

       }

       bool operator != (ClassIt it) const {

 	return (i != it.i);

       }

       bool operator < (ClassIt it) const {

 	return (i < it.i);

       }

       bool valid() const { return i != 0; }

     private:

       void first(const ClassList &l) { i = l.begin(); validate(l); }

       void next(const ClassList &l) {

 	++i; 

 	validate(l);

       }

       void validate(const ClassList &l) {

 	if ( i == l.end() ) 

 	  i = 0;

       }

     };

     ClassIt& first(ClassIt& it) const {

       it.first(classes);

       return it;

     }

     bool valid(ClassIt const &it) const {

       return it.valid(); 

     }

     ClassIt& next(ClassIt& it) const {

       it.next(classes);

       return it;

     }

     class ItemIt {

       friend class UnionFindEnum;

       IcIter i;

       const ItemList *l;

     public:

       ItemIt(Invalid): i(0) {}

       ItemIt() {}

       operator const T& () const { return i->me; }

       bool operator == (ItemIt it) const {

 	return (i == it.i);

       }

       bool operator != (ItemIt it) const {

 	return (i != it.i);

       }

       bool operator < (ItemIt it) const {

 	return (i < it.i);

       }

       bool valid() const { return i != 0; }

     private:

       void first(const ItemList &il) { l=&il; i = l->begin(); validate(); }

       void next() {

 	++i; 

 	validate();

       }

       void validate() {

 	if ( i == l->end() ) 

 	  i = 0;

       }

     };

     ItemIt& first(ItemIt& it, const T& a) const {

       it.first( * _find(m[a])->my_class );

       return it;

     }

     bool valid(ItemIt const &it) const {

       return it.valid(); 

     }

     ItemIt& next(ItemIt& it) const {

       it.next();

       return it;

     }

   };

 } //namespace hugo

 #endif //HUGO_UNION_FIND_H