beckerjc@150: // -*- c++ -*- //
beckerjc@218: #ifndef HUGO_UNION_FIND_H
beckerjc@218: #define HUGO_UNION_FIND_H
beckerjc@150: 
beckerjc@150: #include <vector>
beckerjc@394: #include <list>
beckerjc@150: #include <utility>
beckerjc@394: #include <algorithm>
beckerjc@394: 
beckerjc@394: #include <invalid.h>
beckerjc@150: 
beckerjc@150: namespace hugo {
beckerjc@150: 
beckerjc@150:   template <typename T, typename TIntMap>
beckerjc@150:   class UnionFind {
beckerjc@150:     
beckerjc@150:   public:
beckerjc@150:     typedef T ElementType;
beckerjc@150:     typedef std::pair<int,int> PairType;
beckerjc@150: 
beckerjc@150:   private:
beckerjc@150:     std::vector<PairType> data;
beckerjc@150:     TIntMap& map;
beckerjc@150: 
beckerjc@150:   public:
beckerjc@150:     UnionFind(TIntMap& m) : map(m) {}
beckerjc@150: 
beckerjc@150: 
beckerjc@394:     int find(T a)
beckerjc@150:     {
beckerjc@349:       int comp0 = map[a];
beckerjc@150:       if (comp0 < 0) {
beckerjc@394: 	return insert(a);
beckerjc@150:       }
beckerjc@150:       int comp = comp0;
beckerjc@150:       int next;
beckerjc@150:       while ( (next = data[comp].first) != comp) {
beckerjc@150: 	comp = next;
beckerjc@150:       }
beckerjc@150:       while ( (next = data[comp0].first) != comp) {
beckerjc@150: 	data[comp0].first = comp;
beckerjc@150: 	comp0 = next;
beckerjc@150:       }
beckerjc@150: 
beckerjc@150:       return comp;
beckerjc@150:     }
beckerjc@150: 
beckerjc@394:     int insert(T a)
beckerjc@150:     {
beckerjc@150:       int n = data.size();
beckerjc@394:       data.push_back(std::make_pair(n, 1));
beckerjc@150:       map.set(a,n);
beckerjc@150:       return n;
beckerjc@150:     }
beckerjc@150: 
beckerjc@394:     bool join(T a, T b)
beckerjc@150:     {
beckerjc@394:       int ca = find(a);
beckerjc@394:       int cb = find(b);
beckerjc@150: 
beckerjc@150:       if ( ca == cb ) 
beckerjc@150: 	return false;
beckerjc@150: 
beckerjc@150:       if ( data[ca].second > data[cb].second ) {
beckerjc@150: 	data[cb].first = ca;
beckerjc@150: 	data[ca].second += data[cb].second;
beckerjc@150:       }
beckerjc@150:       else {
beckerjc@150: 	data[ca].first = cb;
beckerjc@150: 	data[cb].second += data[ca].second;
beckerjc@150:       }
beckerjc@150:       return true;
beckerjc@150:     }
beckerjc@150: 
beckerjc@394:     int size(T a)
beckerjc@218:     {
beckerjc@394:       int ca = find(a);
beckerjc@218:       return data[ca].second;
beckerjc@218:     }
beckerjc@218: 
beckerjc@150:   };
beckerjc@150: 
beckerjc@394: 
beckerjc@394: 
beckerjc@394: 
beckerjc@394:   /*******************************************************/
beckerjc@394: 
beckerjc@394: 
beckerjc@394: 
beckerjc@394:   template <typename T>
beckerjc@394:   struct UnionFindEnumItem {
beckerjc@394: 
beckerjc@394:     typedef std::list<UnionFindEnumItem> ItemList;
beckerjc@394:     typedef std::list<ItemList> ClassList;
beckerjc@394:     typedef typename ItemList::iterator IIter;
beckerjc@394:     typedef typename ClassList::iterator CIter;
beckerjc@394: 
beckerjc@394:     T me;
beckerjc@394:     IIter parent;
beckerjc@394:     int size;
beckerjc@394:     CIter my_class;
beckerjc@394: 
beckerjc@394:     UnionFindEnumItem() {}
beckerjc@394:     UnionFindEnumItem(const T &_me, CIter _my_class): 
beckerjc@394:       me(_me), size(1), my_class(_my_class) {}
beckerjc@394:   };
beckerjc@394: 
beckerjc@394:   template <typename T, template <typename Item> class Map>
beckerjc@394:   class UnionFindEnum {
beckerjc@394: 
beckerjc@394:     typedef std::list<UnionFindEnumItem<T> > ItemList;
beckerjc@394:     typedef std::list<ItemList> ClassList;
beckerjc@394:     typedef typename ItemList::iterator IIter;
beckerjc@394:     typedef typename ItemList::const_iterator IcIter;
beckerjc@394:     typedef typename ClassList::iterator CIter;
beckerjc@394:     typedef typename ClassList::const_iterator CcIter;
beckerjc@394: 
beckerjc@394:   public:
beckerjc@394:     typedef T ElementType;
beckerjc@394:     typedef UnionFindEnumItem<T> ItemType;
beckerjc@394:     typedef Map< IIter > MapType;
beckerjc@394: 
beckerjc@394:   private:
beckerjc@394:     MapType& m;
beckerjc@394:     ClassList classes;
beckerjc@394: 
beckerjc@394:     //    IIter where(const T &a) { return m[a]; }
beckerjc@394:     //    IIter parent(IIter a) { return a->parent; }
beckerjc@394:     //    P sibling(P a) { return &m[a->sibling]; }
beckerjc@394: 
beckerjc@394:     IIter _find(IIter a) const {
beckerjc@394:       IIter comp = a;
beckerjc@394:       IIter next;
beckerjc@394:       while( (next = comp->parent) != comp ) {
beckerjc@394: 	comp = next;
beckerjc@394:       }
beckerjc@394: 
beckerjc@394:       IIter comp1 = a;
beckerjc@394:       while( (next = comp1->parent) != comp ) {
beckerjc@394: 	comp1->parent = comp->parent;
beckerjc@394: 	comp1 = next;
beckerjc@394:       }
beckerjc@394:       return comp;
beckerjc@394:     }
beckerjc@394: 
beckerjc@394:   public:
beckerjc@394:     UnionFindEnum(MapType& _m) : m(_m) {}
beckerjc@394: 
beckerjc@394:     void insert(const T &a)
beckerjc@394:     {
beckerjc@394: 
beckerjc@394: 
beckerjc@394:       classes.push_back(ItemList());
beckerjc@394:       CIter aclass = classes.end();
beckerjc@394:       --aclass;
beckerjc@394: 
beckerjc@394:       ItemList &alist = *aclass;
beckerjc@394:       alist.push_back(ItemType(a, aclass));
beckerjc@394:       IIter ai = alist.begin();
beckerjc@394: 
beckerjc@394:       ai->parent = ai;
beckerjc@394:       m.set(a, ai);
beckerjc@394: 
beckerjc@394:     }
beckerjc@394: 
beckerjc@394:     T find(const T &a) const {
beckerjc@394:       return _find(m[a])->me;
beckerjc@394:     }
beckerjc@394: 
beckerjc@394:     bool join(T a, T b) {
beckerjc@394: 
beckerjc@394:       IIter ca = _find(m[a]);
beckerjc@394:       IIter cb = _find(m[b]);
beckerjc@394: 
beckerjc@394:       if ( ca == cb ) {
beckerjc@394: 	return false;
beckerjc@394:       }
beckerjc@394: 
beckerjc@394:       if ( ca->size > cb->size ) {
beckerjc@394: 
beckerjc@394: 	cb->parent = ca->parent;
beckerjc@394: 	ca->size += cb->size;
beckerjc@394: 	
beckerjc@394: 	ItemList &alist = *ca->my_class;
beckerjc@394: 	alist.splice(alist.end(),*cb->my_class);
beckerjc@394: 
beckerjc@394: 	classes.erase(cb->my_class);
beckerjc@394: 	cb->my_class = 0;
beckerjc@394:       }
beckerjc@394:       else {
beckerjc@394: 
beckerjc@394: 	ca->parent = cb->parent;
beckerjc@394: 	cb->size += ca->size;
beckerjc@394: 	
beckerjc@394: 	ItemList &blist = *cb->my_class;
beckerjc@394: 	blist.splice(blist.end(),*ca->my_class);
beckerjc@394: 
beckerjc@394: 	classes.erase(ca->my_class);
beckerjc@394: 	ca->my_class = 0;
beckerjc@394:       }
beckerjc@394: 
beckerjc@394:       return true;
beckerjc@394:     }
beckerjc@394: 
beckerjc@394:     int size(const T &a) const {
beckerjc@394:       return _find(m[a])->size;
beckerjc@394:     }
beckerjc@394: 
beckerjc@394:     
beckerjc@394:     void split(const T &a) {
beckerjc@394: 
beckerjc@394:       IIter ca = _find(m[a]);
beckerjc@394:  
beckerjc@394:       if ( ca->size == 1 )
beckerjc@394: 	return;
beckerjc@394:       
beckerjc@394:       CIter aclass = ca->my_class;
beckerjc@394: 
beckerjc@394:       for(IIter curr = ca; ++curr != aclass->end(); curr=ca) {
beckerjc@394: 	classes.push_back(ItemList());
beckerjc@394: 	CIter nl = --classes.end();
beckerjc@394: 	nl->splice(nl->end(), *aclass, curr);
beckerjc@394: 
beckerjc@394: 	curr->size=1;
beckerjc@394: 	curr->parent=curr;
beckerjc@394: 	curr->my_class = nl;
beckerjc@394:       }
beckerjc@394: 
beckerjc@394:       ca->size=1;
beckerjc@394:       return;
beckerjc@394:     }
beckerjc@394: 
beckerjc@394:     void erase(const T &a) {
beckerjc@394: 
beckerjc@394:       IIter ma = m[a];
beckerjc@394:       if (ma == 0) return;
beckerjc@394: 
beckerjc@394:       IIter la = _find(ma);
beckerjc@394:       if (la == ma) {
beckerjc@394: 	if (ma -> size == 1){
beckerjc@394: 	  classes.erase(ma->my_class);
beckerjc@394: 	  m.set(a,0);
beckerjc@394: 	  return;
beckerjc@394: 	}
beckerjc@394: 	++la;
beckerjc@394: 	la->size = ma->size - 1; 
beckerjc@394: 	la->my_class = ma->my_class;	
beckerjc@394:       }
beckerjc@394: 
beckerjc@394:       for (IIter i = la; i != la->my_class->end(); ++i) {
beckerjc@394: 	i->parent = la;
beckerjc@394:       }
beckerjc@394: 
beckerjc@394:       la->my_class->erase(ma);
beckerjc@394:       m.set(a,0);
beckerjc@394:     }
beckerjc@394: 
beckerjc@394:     void eraseClass(const T &a) {
beckerjc@394:       IIter ma = m[a];
beckerjc@394:       if (ma == 0) return;
beckerjc@394: #     ifdef DEBUG
beckerjc@394:       CIter c = _find(ma)->my_class;
beckerjc@394:       for (IIter i=c->begin(); i!=c->end(); ++i)
beckerjc@394: 	m.set(i->me, 0);
beckerjc@394: #     endif
beckerjc@394:       classes.erase(_find(ma)->my_class);
beckerjc@394:     }
beckerjc@394: 
beckerjc@394: 
beckerjc@394:     class ClassIt {
beckerjc@394:       friend class UnionFindEnum;
beckerjc@394: 
beckerjc@394:       CcIter i;
beckerjc@394:     public:
beckerjc@394:       ClassIt(Invalid): i(0) {}
beckerjc@394:       ClassIt() {}
beckerjc@394:       
beckerjc@394:       operator const T& () const { 
beckerjc@394: 	ItemList const &ll = *i;
beckerjc@394: 	return (ll.begin())->me; }
beckerjc@394:       bool operator == (ClassIt it) const {
beckerjc@394: 	return (i == it.i);
beckerjc@394:       }
beckerjc@394:       bool operator != (ClassIt it) const {
beckerjc@394: 	return (i != it.i);
beckerjc@394:       }
beckerjc@394:       bool operator < (ClassIt it) const {
beckerjc@394: 	return (i < it.i);
beckerjc@394:       }
beckerjc@394: 
beckerjc@394:       bool valid() const { return i != 0; }
beckerjc@394:     private:
beckerjc@394:       void first(const ClassList &l) { i = l.begin(); validate(l); }
beckerjc@394:       void next(const ClassList &l) {
beckerjc@394: 	++i; 
beckerjc@394: 	validate(l);
beckerjc@394:       }
beckerjc@394:       void validate(const ClassList &l) {
beckerjc@394: 	if ( i == l.end() ) 
beckerjc@394: 	  i = 0;
beckerjc@394:       }
beckerjc@394:     };
beckerjc@394: 
beckerjc@394: 
beckerjc@394:     ClassIt& first(ClassIt& it) const {
beckerjc@394:       it.first(classes);
beckerjc@394:       return it;
beckerjc@394:     }
beckerjc@394: 
beckerjc@394:     bool valid(ClassIt const &it) const {
beckerjc@394:       return it.valid(); 
beckerjc@394:     }
beckerjc@394: 
beckerjc@394:     ClassIt& next(ClassIt& it) const {
beckerjc@394:       it.next(classes);
beckerjc@394:       return it;
beckerjc@394:     }
beckerjc@394: 
beckerjc@394: 
beckerjc@394:     class ItemIt {
beckerjc@394:       friend class UnionFindEnum;
beckerjc@394: 
beckerjc@394:       IcIter i;
beckerjc@394:       const ItemList *l;
beckerjc@394:     public:
beckerjc@394:       ItemIt(Invalid): i(0) {}
beckerjc@394:       ItemIt() {}
beckerjc@394:       
beckerjc@394:       operator const T& () const { return i->me; }
beckerjc@394:       bool operator == (ItemIt it) const {
beckerjc@394: 	return (i == it.i);
beckerjc@394:       }
beckerjc@394:       bool operator != (ItemIt it) const {
beckerjc@394: 	return (i != it.i);
beckerjc@394:       }
beckerjc@394:       bool operator < (ItemIt it) const {
beckerjc@394: 	return (i < it.i);
beckerjc@394:       }
beckerjc@394: 
beckerjc@394:       bool valid() const { return i != 0; }
beckerjc@394:     private:
beckerjc@394:       void first(const ItemList &il) { l=&il; i = l->begin(); validate(); }
beckerjc@394:       void next() {
beckerjc@394: 	++i; 
beckerjc@394: 	validate();
beckerjc@394:       }
beckerjc@394:       void validate() {
beckerjc@394: 	if ( i == l->end() ) 
beckerjc@394: 	  i = 0;
beckerjc@394:       }
beckerjc@394:     };
beckerjc@394: 
beckerjc@394: 
beckerjc@394:     ItemIt& first(ItemIt& it, const T& a) const {
beckerjc@394:       it.first( * _find(m[a])->my_class );
beckerjc@394:       return it;
beckerjc@394:     }
beckerjc@394: 
beckerjc@394:     bool valid(ItemIt const &it) const {
beckerjc@394:       return it.valid(); 
beckerjc@394:     }
beckerjc@394: 
beckerjc@394:     ItemIt& next(ItemIt& it) const {
beckerjc@394:       it.next();
beckerjc@394:       return it;
beckerjc@394:     }
beckerjc@394:     
beckerjc@394: 
beckerjc@394: 
beckerjc@394:   };
beckerjc@394: 
beckerjc@150: } //namespace hugo
beckerjc@150: 
beckerjc@218: #endif //HUGO_UNION_FIND_H