lemon-0.x: comparison src/work/johanna/unionfind.h

equal deleted inserted replaced

-:a361efe2190f
+:bcbd2365ccca
 // -*- 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:
 UnionFind(TIntMap& m) : map(m) {}
-int whichComponent(T a)
+int find(T a)
 {
 int comp0 = map[a];
 if (comp0 < 0) {
-	return insertNewElement(a);
+	return insert(a);
 }
 int comp = comp0;
 int next;
 while ( (next = data[comp].first) != comp) {
 	comp = next;
 }
 return comp;
 }
-int insertNewElement(T a)
+int insert(T a)
 {
 int n = data.size();
-data.push_back(make_pair(n, 1));
+data.push_back(std::make_pair(n, 1));
 map.set(a,n);
 return n;
 }
-bool joinComponents(T a, T b)
+bool join(T a, T b)
 {
-int ca = whichComponent(a);
+int ca = find(a);
-int cb = whichComponent(b);
+int cb = find(b);
 if ( ca == cb )
 	return false;
 if ( data[ca].second > data[cb].second ) {
 	data[cb].second += data[ca].second;
 }
 return true;
 }
-int componentSize(T a)
+int size(T a)
 {
-int ca = whichComponent(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

changeset 405	a2d8ec38e8db
parent 349	42c660f58702
child 462	0ab31578af67