# HG changeset patch
# User beckerjc
# Date 1082822605 0
# Node ID 3a34c5626e5294addbfd01ee5e5d76a4e30bcf58
# Parent  4535f78639e2a39cec96de1649ea0b1caf18bdbe
New union-find structure with enumerable classes.

diff -r 4535f78639e2 -r 3a34c5626e52 src/work/johanna/Makefile
--- a/src/work/johanna/Makefile	Sat Apr 24 15:19:17 2004 +0000
+++ b/src/work/johanna/Makefile	Sat Apr 24 16:03:25 2004 +0000
@@ -1,4 +1,4 @@
-BINARIES = kruskal_test ma_order_test
+BINARIES = kruskal_test ma_order_test unionfind_test
 INCLUDEDIRS= -I. -I.. -I../../include -I../{marci,jacint,alpar,klao,akos}
 include ../makefile
 
diff -r 4535f78639e2 -r 3a34c5626e52 src/work/johanna/contract_wrapper.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/work/johanna/contract_wrapper.h	Sat Apr 24 16:03:25 2004 +0000
@@ -0,0 +1,36 @@
+// -*- C++ -*- //
+
+#ifndef HUGO_CONTRACT_WRAPPER
+#define HUGO_CONTRACT_WRAPPER
+
+#include <graph_wrapper.h>
+
+namespace hugo {
+
+  template<typename Graph>
+  class ConractWrapper : public GraphWrapper<const Graph> {
+
+  public:
+    typedef typename Parent::NodeMap NodeMap;
+    class Node;
+
+  private:
+    typedef GraphWrapper<Graph> Parent;
+    
+
+    UnionFindEnum<Node, NodeMap> parts; 
+ 
+  public:
+
+    ConractWrapper(const Graph& _graph) : Parent(_graph) { }
+
+
+
+
+
+  };
+
+
+
+}
+#endif
diff -r 4535f78639e2 -r 3a34c5626e52 src/work/johanna/kruskal.h
--- a/src/work/johanna/kruskal.h	Sat Apr 24 15:19:17 2004 +0000
+++ b/src/work/johanna/kruskal.h	Sat Apr 24 16:03:25 2004 +0000
@@ -25,7 +25,7 @@
     EdgeCost tot_cost = 0;
     for (typename InputEdgeOrder::const_iterator p = edges.begin(); 
 	 p!=edges.end(); ++p ) {
-      if ( uf.joinComponents(G.head(edges.first(p)),
+      if ( uf.join(G.head(edges.first(p)),
 			     G.tail(edges.first(p))) ) {
 	out_map.set(edges.first(p), true);
 	tot_cost += edges.second(p);
diff -r 4535f78639e2 -r 3a34c5626e52 src/work/johanna/unionfind.h
--- a/src/work/johanna/unionfind.h	Sat Apr 24 15:19:17 2004 +0000
+++ b/src/work/johanna/unionfind.h	Sat Apr 24 16:03:25 2004 +0000
@@ -3,7 +3,11 @@
 #define HUGO_UNION_FIND_H
 
 #include <vector>
+#include <list>
 #include <utility>
+#include <algorithm>
+
+#include <invalid.h>
 
 namespace hugo {
 
@@ -22,11 +26,11 @@
     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;
@@ -41,18 +45,18 @@
       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 cb = whichComponent(b);
+      int ca = find(a);
+      int cb = find(b);
 
       if ( ca == cb ) 
 	return false;
@@ -68,14 +72,303 @@
       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
diff -r 4535f78639e2 -r 3a34c5626e52 src/work/johanna/unionfind_test.cc
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/work/johanna/unionfind_test.cc	Sat Apr 24 16:03:25 2004 +0000
@@ -0,0 +1,114 @@
+#include <iostream>
+
+#include <maps.h>
+#include <unionfind.h>
+
+using namespace hugo;
+using namespace std;
+
+bool passed = true;
+
+void check(bool rc) {
+  passed = passed && rc;
+  if(!rc) {
+    cout << "Test failed!" << endl;
+  }
+}
+
+template <typename T>
+class BaseMap : public StdMap<int,T> {};
+
+typedef UnionFindEnum<int, BaseMap> UFE;
+
+void print(UFE const &ufe) {
+  UFE::ClassIt cit;
+  cout << "printing the classes of the structure:" << endl;
+  int i = 1;
+  for (ufe.first(cit); ufe.valid(cit); ufe.next(cit)) {
+    cout << "  " << i << " (" << cit << "):" << flush;
+    UFE::ItemIt iit;
+    for (ufe.first(iit, cit); ufe.valid(iit); ufe.next(iit)) {
+      cout << " " << iit << flush;
+    }
+    cout << endl;
+    i++;
+  }
+  cout << "done" << endl;
+}
+
+
+int main() {
+  UFE::MapType base;
+  UFE U(base);
+
+  print(U);
+
+  cout << "Inserting 1..." << endl;
+  U.insert(1);
+  print(U);
+  
+  cout << "Inserting 2..." << endl;
+  U.insert(2);
+  print(U);
+  
+  cout << "Joining 1 and 2..." << endl;
+  check(U.join(1,2));
+  print(U);
+
+  cout << "Inserting 3, 4, 5, 6, 7..." << endl;
+  U.insert(3);
+  U.insert(4);
+  U.insert(5);
+  U.insert(6);
+  U.insert(7);
+  print (U);
+
+  cout << "Joining 1 - 4, 2 - 4 and 3 - 5 ..." << endl;
+  check(U.join(1,4));
+  check(!U.join(2,4));
+  check(U.join(3,5));
+  print(U);
+
+  cout << "size of the class of 4: " << U.size(4) << endl;
+  check(U.size(4) == 3);
+  cout << "size of the class of 5: " << U.size(5) << endl;
+  check(U.size(5) == 2);
+  cout << "size of the class of 6: " << U.size(6) << endl;
+  check(U.size(6) == 1);
+
+  cout <<"erase 1: " << endl;
+  U.erase(1);
+  print(U);
+
+  cout <<"erase 1: " << endl;
+  U.erase(1);
+  print(U);
+
+  cout <<"erase 6: " << endl;
+  U.erase(6);
+  print(U);
+
+  cout << "split the class of 5: " << endl;
+  U.split(5);
+  print(U);
+
+  cout << "Joining 3 - 4 and 2 - 4 ..." << endl;
+  check(U.join(3,4));
+  check(!U.join(2,4));
+  print(U);
+
+  cout << "eraseClass 4 ..." << endl;
+  U.eraseClass(4);
+  print(U);
+
+  cout << "eraseClass 7 ..." << endl;
+  U.eraseClass(7);
+  print(U);
+
+  cout << "done" << endl;
+
+  cout << (passed ? "All tests passed." : "Some of the tests failed!!!")
+       << endl;
+
+  return passed ? 0 : 1;
+}