# HG changeset patch
# User beckerjc
# Date 1083258044 0
# Node ID ce29ae5b2e1b7bd9bd92a4f37005efc41db2af40
# Parent  dce64ce044d6894fcc0193600bd0cbea920e0029
UnionFind moved to include. Test compiles and runs cleanly.

* test/makefile:
  minor cleanups

diff -r dce64ce044d6 -r ce29ae5b2e1b src/include/unionfind.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/include/unionfind.h	Thu Apr 29 17:00:44 2004 +0000
@@ -0,0 +1,700 @@
+// -*- c++ -*- //
+#ifndef HUGO_UNION_FIND_H
+#define HUGO_UNION_FIND_H
+
+//!ingroup auxdat
+//!\file
+//!\brief Union-Find data structures.
+
+
+#include <vector>
+#include <list>
+#include <utility>
+#include <algorithm>
+
+#include <invalid.h>
+
+namespace hugo {
+
+  //! \addtogroup auxdat
+  //! @{
+
+  /**
+   * \brief A \e Union-Find data structure implementation
+   *
+   * The class implements the \e Union-Find data structure. 
+   * The union operation uses rank heuristic, while
+   * the find operation uses path compresson.
+   * This is a very simple but efficient implementation, providing 
+   * only four methods: join (union), find, insert and size.
+   * For more features see the \ref UnionFindEnum class.
+   *
+   * \pre The elements are automatically added only if the map 
+   * given to the constructor was filled with -1's. Otherwise you
+   * need to add all the elements by the \ref insert() method.
+   */
+
+  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) {}
+
+    /**
+     * \brief Returns the index of the element's component.
+     *
+     * The method returns the index of the element's component.
+     * This is an integer between zero and the number of inserted elements.
+     */
+
+    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;
+    }
+
+    /**
+     * \brief Insert a new element into the structure.
+     *
+     * This method inserts a new element into the data structure. 
+     *
+     * It is not required to use this method:
+     * if the map given to the constructor was filled 
+     * with -1's then it is called automatically
+     * on the first \ref find or \ref join.
+     *
+     * The method returns the index of the new component.
+     */
+
+    int insert(T a)
+    {
+      int n = data.size();
+      data.push_back(std::make_pair(n, 1));
+      map.set(a,n);
+      return n;
+    }
+
+    /**
+     * \brief Joining the components of element \e a and element \e b.
+     *
+     * This is the \e union operation of the Union-Find structure. 
+     * Joins the component of elemenent \e a and component of
+     * element \e b. If \e a and \e b are in the same component then
+     * it returns false otherwise it returns true.
+     */
+
+    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;
+    }
+
+    /**
+     * \brief Returns the size of the component of element \e a.
+     *
+     * Returns the size of the component of element \e a.
+     */
+
+    int size(T a)
+    {
+      int ca = find(a);
+      return data[ca].second;
+    }
+
+  };
+
+
+
+
+  /*******************************************************/
+
+
+#ifdef DEVELOPMENT_DOCS
+
+  /**
+   * \brief The auxiliary class for the \ref UnionFindEnum class.
+   *
+   * In the \ref UnionFindEnum class all components are represented as
+   * a std::list. 
+   * Items of these lists are UnionFindEnumItem structures.
+   *
+   * The class has four fields:
+   *  - T me - the actual element 
+   *  - IIter parent - the parent of the element in the union-find structure
+   *  - int size - the size of the component of the element. 
+   *            Only valid if the element
+   *            is the leader of the component.
+   *  - CIter my_class - pointer into the list of components 
+   *            pointing to the component of the element.
+   *            Only valid if the element is the leader of the component.
+   */
+
+#endif
+
+  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) {}
+  };
+
+
+  /**
+   * \brief A \e Union-Find data structure implementation which
+   * is able to enumerate the components.
+   *
+   * The class implements an \e Union-Find data structure
+   * which is able to enumerate the components and the items in
+   * a component. If you don't need this feature then perhaps it's
+   * better to use the \ref UnionFind class which is more efficient.
+   *
+   * The union operation uses rank heuristic, while
+   * the find operation uses path compresson.
+   *
+   * \pre You
+   * need to add all the elements by the \ref insert() method.
+   */
+
+
+  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 _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) {}
+
+
+    /**
+     * \brief Insert the given element into a new component.
+     *
+     * This method creates a new component consisting only of the
+     * given element.
+     */
+
+    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);
+
+    }
+
+    /**
+     * \brief Insert the given element into the component of the others.
+     *
+     * This methods insert the element \e a into the component of the
+     * element \e comp. 
+     */
+
+    void insert(const T &a, const T &comp) {
+      
+      IIter clit = _find(m[comp]);
+      ItemList &c = *clit->my_class;
+      c.push_back(ItemType(a,0));
+      IIter ai = c.end();
+      --ai;
+      ai->parent = clit;
+      m.set(a, ai);
+      ++clit->size;
+    }
+
+
+    /**
+     * \brief Find the leader of the component of the given element.
+     *
+     * The method returns the leader of the component of the given element.
+     */
+
+    T find(const T &a) const {
+      return _find(m[a])->me;
+    }
+
+
+    /**
+     * \brief Joining the component of element \e a and element \e b.
+     *
+     * This is the \e union operation of the Union-Find structure. 
+     * Joins the component of elemenent \e a and component of
+     * element \e b. If \e a and \e b are in the same component then
+     * returns false else returns true.
+     */
+
+    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;
+    }
+
+
+    /**
+     * \brief Returns the size of the component of element \e a.
+     *
+     * Returns the size of the component of element \e a.
+     */
+
+    int size(const T &a) const {
+      return _find(m[a])->size;
+    }
+
+
+    /**
+     * \brief Split up the component of the element. 
+     *
+     * Splitting the component of the element into sigleton
+     * components (component of size one).
+     */
+
+    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;
+    }
+
+
+    /**
+     * \brief Set the given element to the leader element of its component.
+     *
+     * Set the given element to the leader element of its component.
+     */
+
+    void makeRep(const T &a) {
+
+      IIter ia = m[a];
+      IIter la = _find(ia);
+      if (la == ia) return;
+
+      ia->my_class = la->my_class;
+      la->my_class = 0;
+
+      ia->size = la->size;
+
+      CIter l = ia->my_class;
+      l->splice(l->begin(),*l,ia);
+
+      ia->parent = ia;
+      la->parent = ia;
+    }
+
+    /**
+     * \brief Move the given element to an other component.
+     *
+     * This method moves the element \e a from its component
+     * to the component of \e comp.
+     * If \e a and \e comp are in the same component then
+     * it returns false otherwise it returns true.
+     */
+
+    bool move(const T &a, const T &comp) {
+
+      IIter ai = m[a];
+      IIter lai = _find(ai);
+      IIter clit = _find(m[comp]);
+
+      if (lai == clit)
+	return false;
+
+      ItemList &c = *clit->my_class;
+
+      bool is_leader = (lai == ai);
+      bool singleton = false;
+
+      if (is_leader) {
+	++lai;
+      }
+
+      c.splice(c.end(), *lai->my_class, ai);
+
+      if (is_leader) {
+	if (ai->size == 1) {
+	  classes.erase(ai->my_class);
+	  singleton = true;
+	}
+	else {
+	  lai->size = ai->size; 
+	  lai->my_class = ai->my_class;	
+	}
+      }
+      if (!singleton) {
+	for (IIter i = lai; i != lai->my_class->end(); ++i)
+	  i->parent = lai;
+	--lai->size;
+      }
+
+      ai->parent = clit;
+      ai->my_class = 0;
+      ++clit->size;
+
+      return true;
+    }
+
+
+    /**
+     * \brief Remove the given element from the structure.
+     *
+     * Remove the given element from the structure.
+     *
+     * Removes the element from its component and if the component becomes
+     * empty then removes that component from the component list.
+     */
+    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; 
+	la->my_class = ma->my_class;	
+      }
+
+      for (IIter i = la; i != la->my_class->end(); ++i) {
+	i->parent = la;
+      }
+
+      la->size--;
+      la->my_class->erase(ma);
+      m.set(a,0);
+    }
+
+    /**
+     * \brief Removes the component of the given element from the structure.
+     *
+     * Removes the component of the given element from the structure.
+     */
+
+    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;
+      }
+    };
+
+    /**
+     * \brief Sets the iterator to point to the first component.
+     * 
+     * Sets the iterator to point to the first component.
+     *
+     * With the \ref first, \ref valid and \ref next methods you can
+     * iterate through the components. For example:
+     * \code
+     * UnionFindEnum<Graph::Node, Graph::NodeMap>::MapType map(G);
+     * UnionFindEnum<Graph::Node, Graph::NodeMap> U(map);
+     * UnionFindEnum<Graph::Node, Graph::NodeMap>::ClassIt iter;
+     *  for (U.first(iter); U.valid(iter); U.next(iter)) {
+     *    // iter is convertible to Graph::Node
+     *    cout << iter << endl;
+     *  }
+     * \endcode
+     */
+
+    ClassIt& first(ClassIt& it) const {
+      it.first(classes);
+      return it;
+    }
+
+    /**
+     * \brief Returns whether the iterator is valid.
+     *
+     * Returns whether the iterator is valid.
+     *
+     * With the \ref first, \ref valid and \ref next methods you can
+     * iterate through the components. See the example here: \ref first.
+     */
+
+    bool valid(ClassIt const &it) const {
+      return it.valid(); 
+    }
+
+    /**
+     * \brief Steps the iterator to the next component. 
+     *
+     * Steps the iterator to the next component.
+     *
+     * With the \ref first, \ref valid and \ref next methods you can
+     * iterate through the components. See the example here: \ref first.
+     */
+
+    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;
+      }
+    };
+
+
+
+    /**
+     * \brief Sets the iterator to point to the first element of the component.
+     * 
+     * \anchor first2 
+     * Sets the iterator to point to the first element of the component.
+     *
+     * With the \ref first2 "first", \ref valid2 "valid" 
+     * and \ref next2 "next" methods you can
+     * iterate through the elements of a component. For example
+     * (iterating through the component of the node \e node):
+     * \code
+     * Graph::Node node = ...;
+     * UnionFindEnum<Graph::Node, Graph::NodeMap>::MapType map(G);
+     * UnionFindEnum<Graph::Node, Graph::NodeMap> U(map);
+     * UnionFindEnum<Graph::Node, Graph::NodeMap>::ItemIt iiter;
+     *   for (U.first(iiter, node); U.valid(iiter); U.next(iiter)) {
+     *     // iiter is convertible to Graph::Node
+     *     cout << iiter << endl;
+     *   }
+     * \endcode
+     */
+    
+    ItemIt& first(ItemIt& it, const T& a) const {
+      it.first( * _find(m[a])->my_class );
+      return it;
+    }
+
+    /**
+     * \brief Returns whether the iterator is valid.
+     *
+     * \anchor valid2
+     * Returns whether the iterator is valid.
+     *
+     * With the \ref first2 "first", \ref valid2 "valid" 
+     * and \ref next2 "next" methods you can
+     * iterate through the elements of a component.
+     * See the example here: \ref first2 "first".
+     */
+
+    bool valid(ItemIt const &it) const {
+      return it.valid(); 
+    }
+
+    /**
+     * \brief Steps the iterator to the next component. 
+     *
+     * \anchor next2
+     * Steps the iterator to the next component.
+     *
+     * With the \ref first2 "first", \ref valid2 "valid" 
+     * and \ref next2 "next" methods you can
+     * iterate through the elements of a component.
+     * See the example here: \ref first2 "first".
+     */
+
+    ItemIt& next(ItemIt& it) const {
+      it.next();
+      return it;
+    }
+    
+  };
+
+
+  //! @}
+
+} //namespace hugo
+
+#endif //HUGO_UNION_FIND_H
diff -r dce64ce044d6 -r ce29ae5b2e1b src/test/makefile
--- a/src/test/makefile	Thu Apr 29 16:59:00 2004 +0000
+++ b/src/test/makefile	Thu Apr 29 17:00:44 2004 +0000
@@ -1,18 +1,21 @@
-#CXX3 := $(shell type -p g++-3.4 || shell type -p g++-3.3 || type -p g++-3.2 || type -p g++-3.0 || type -p g++-3 || echo g++)
-CXX3 := $(shell type -p g++-3.3 || type -p g++-3.2 || type -p g++-3.0 || type -p g++-3 || echo g++)
-CXX2 = g++-2.95
-CXX=$(CXX3)
+INCLUDEDIRS ?= -I../include
+CXXFLAGS += -Wall -O3 -ansi -pedantic $(INCLUDEDIRS) 
+#LEDAROOT ?= /ledasrc/LEDA-4.1
+
+BINARIES = dijkstra_heap_test unionfind_test
+
+ifdef GCCVER
+CXX := g++-$(GCCVER)
+else
+CXX := $(shell type -p g++-3.3 || type -p g++-3.2 || type -p g++-3.0 || type -p g++-3 || echo g++)
+endif
+
 CC=$(CXX)
-INCLUDEDIRS ?= -I../include -I.. -I../work/{marci,jacint,alpar,klao,akos,athos} 
-CXXFLAGS = -W -Wall -ansi -pedantic -O3 $(INCLUDEDIRS) 
-LEDAROOT ?= /ledasrc/LEDA-4.1
-
-BINARIES = dijkstra_heap_test
 
 all: $(BINARIES)
 
 .depend dep depend:
-	-$(CXX) $(INCLUDEDIRS) -M $(BINARIES:=.cc) > .depend #2>/dev/null
+	$(CXX) $(INCLUDEDIRS) -M $(BINARIES:=.cc) > .depend
 
 makefile: .depend
 sinclude .depend
diff -r dce64ce044d6 -r ce29ae5b2e1b src/test/unionfind_test.cc
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/test/unionfind_test.cc	Thu Apr 29 17:00:44 2004 +0000
@@ -0,0 +1,205 @@
+#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 << "Inserting 8 to the component of 5 ..." << endl;
+  U.insert(8,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) == 3);
+  cout << "size of the class of 6: " << U.size(6) << endl;
+  check(U.size(6) == 1);
+  cout << "size of the class of 2: " << U.size(2) << endl;
+  check(U.size(2) == 3);
+
+  cout << "Inserting 9 ..." << endl;
+  U.insert(9);
+  print(U);
+  cout << "Inserting 10 to the component of 9 ..." << endl;
+  U.insert(10,9);
+  print(U);
+
+  cout << "Joining 8 and 10..." << endl;
+  check(U.join(8,10));
+  print(U);
+
+  cout << "Move 9 to the class of 4 ..." << endl;
+  check(U.move(9,4));
+  print(U);
+
+  cout << "Move 9 to the class of 2 ..." << endl;
+  check(!U.move(9,2));
+  print(U);
+
+  cout << "size of the class of 4: " << U.size(4) << endl;
+  check(U.size(4) == 4);
+  cout << "size of the class of 9: " << U.size(9) << endl;
+  check(U.size(9) == 4);
+  
+  cout << "Move 5 to the class of 6 ..." << endl;
+  check(U.move(5,6));
+  print(U);
+
+  cout << "size of the class of 5: " << U.size(5) << endl;
+  check(U.size(5) == 2);
+  cout << "size of the class of 8: " << U.size(8) << endl;
+  check(U.size(8) == 3);
+
+  cout << "Move 7 to the class of 10 ..." << endl;
+  check(U.move(7,10));
+  print(U);
+
+  cout << "size of the class of 7: " << U.size(7) << endl;
+  check(U.size(7) == 4);
+
+  cout <<"erase 9: " << endl;
+  U.erase(9);
+  print(U);
+
+  cout <<"erase 1: " << endl;
+  U.erase(1);
+  print(U);
+
+  cout << "size of the class of 4: " << U.size(4) << endl;
+  check(U.size(4) == 2);
+  cout << "size of the class of 2: " << U.size(2) << endl;
+  check(U.size(2) == 2);
+
+
+  cout <<"erase 1: " << endl;
+  U.erase(1);
+  print(U);
+
+  cout <<"erase 6: " << endl;
+  U.erase(6);
+  print(U);
+
+  cout << "split the class of 8: " << endl;
+  U.split(8);
+  print(U);
+
+
+  cout << "size of the class of 4: " << U.size(4) << endl;
+  check(U.size(4) == 2);
+  cout << "size of the class of 3: " << U.size(3) << endl;
+  check(U.size(3) == 1);
+  cout << "size of the class of 2: " << U.size(2) << endl;
+  check(U.size(2) == 2);
+
+
+  cout << "Joining 3 - 4 and 2 - 4 ..." << endl;
+  check(U.join(3,4));
+  check(!U.join(2,4));
+  print(U);
+
+
+  cout << "size of the class of 4: " << U.size(4) << endl;
+  check(U.size(4) == 3);
+  cout << "size of the class of 3: " << U.size(3) << endl;
+  check(U.size(3) == 3);
+  cout << "size of the class of 2: " << U.size(2) << endl;
+  check(U.size(2) == 3);
+
+  cout << "makeRep(4)" << endl;
+  U.makeRep(4);
+  print(U);
+  cout << "makeRep(3)" << endl;
+  U.makeRep(3);
+  print(U);
+  cout << "makeRep(2)" << endl;
+  U.makeRep(2);
+  print(U);
+
+  cout << "size of the class of 4: " << U.size(4) << endl;
+  check(U.size(4) == 3);
+  cout << "size of the class of 3: " << U.size(3) << endl;
+  check(U.size(3) == 3);
+  cout << "size of the class of 2: " << U.size(2) << endl;
+  check(U.size(2) == 3);
+
+
+  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;
+}
diff -r dce64ce044d6 -r ce29ae5b2e1b src/work/johanna/Makefile
--- a/src/work/johanna/Makefile	Thu Apr 29 16:59:00 2004 +0000
+++ b/src/work/johanna/Makefile	Thu Apr 29 17:00:44 2004 +0000
@@ -1,4 +1,4 @@
-BINARIES = kruskal_test ma_order_test unionfind_test
+BINARIES = kruskal_test ma_order_test
 INCLUDEDIRS= -I. -I.. -I../../include -I../{marci,jacint,alpar,klao,akos}
 include ../makefile
 
diff -r dce64ce044d6 -r ce29ae5b2e1b src/work/johanna/unionfind.h
--- a/src/work/johanna/unionfind.h	Thu Apr 29 16:59:00 2004 +0000
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,700 +0,0 @@
-// -*- c++ -*- //
-#ifndef HUGO_UNION_FIND_H
-#define HUGO_UNION_FIND_H
-
-//!ingroup auxdat
-//!\file
-//!\brief Union-Find data structures.
-
-
-#include <vector>
-#include <list>
-#include <utility>
-#include <algorithm>
-
-#include <invalid.h>
-
-namespace hugo {
-
-  //! \addtogroup auxdat
-  //! @{
-
-  /**
-   * \brief A \e Union-Find data structure implementation
-   *
-   * The class implements the \e Union-Find data structure. 
-   * The union operation uses rank heuristic, while
-   * the find operation uses path compresson.
-   * This is a very simple but efficient implementation, providing 
-   * only four methods: join (union), find, insert and size.
-   * For more features see the \ref UnionFindEnum class.
-   *
-   * \pre The elements are automatically added only if the map 
-   * given to the constructor was filled with -1's. Otherwise you
-   * need to add all the elements by the \ref insert() method.
-   */
-
-  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) {}
-
-    /**
-     * \brief Returns the index of the element's component.
-     *
-     * The method returns the index of the element's component.
-     * This is an integer between zero and the number of inserted elements.
-     */
-
-    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;
-    }
-
-    /**
-     * \brief Insert a new element into the structure.
-     *
-     * This method inserts a new element into the data structure. 
-     *
-     * It is not required to use this method:
-     * if the map given to the constructor was filled 
-     * with -1's then it is called automatically
-     * on the first \ref find or \ref join.
-     *
-     * The method returns the index of the new component.
-     */
-
-    int insert(T a)
-    {
-      int n = data.size();
-      data.push_back(std::make_pair(n, 1));
-      map.set(a,n);
-      return n;
-    }
-
-    /**
-     * \brief Joining the components of element \e a and element \e b.
-     *
-     * This is the \e union operation of the Union-Find structure. 
-     * Joins the component of elemenent \e a and component of
-     * element \e b. If \e a and \e b are in the same component then
-     * it returns false otherwise it returns true.
-     */
-
-    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;
-    }
-
-    /**
-     * \brief Returns the size of the component of element \e a.
-     *
-     * Returns the size of the component of element \e a.
-     */
-
-    int size(T a)
-    {
-      int ca = find(a);
-      return data[ca].second;
-    }
-
-  };
-
-
-
-
-  /*******************************************************/
-
-
-#ifdef DEVELOPMENT_DOCS
-
-  /**
-   * \brief The auxiliary class for the \ref UnionFindEnum class.
-   *
-   * In the \ref UnionFindEnum class all components are represented as
-   * a std::list. 
-   * Items of these lists are UnionFindEnumItem structures.
-   *
-   * The class has four fields:
-   *  - T me - the actual element 
-   *  - IIter parent - the parent of the element in the union-find structure
-   *  - int size - the size of the component of the element. 
-   *            Only valid if the element
-   *            is the leader of the component.
-   *  - CIter my_class - pointer into the list of components 
-   *            pointing to the component of the element.
-   *            Only valid if the element is the leader of the component.
-   */
-
-#endif
-
-  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) {}
-  };
-
-
-  /**
-   * \brief A \e Union-Find data structure implementation which
-   * is able to enumerate the components.
-   *
-   * The class implements an \e Union-Find data structure
-   * which is able to enumerate the components and the items in
-   * a component. If you don't need this feature then perhaps it's
-   * better to use the \ref UnionFind class which is more efficient.
-   *
-   * The union operation uses rank heuristic, while
-   * the find operation uses path compresson.
-   *
-   * \pre You
-   * need to add all the elements by the \ref insert() method.
-   */
-
-
-  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 _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) {}
-
-
-    /**
-     * \brief Insert the given element into a new component.
-     *
-     * This method creates a new component consisting only of the
-     * given element.
-     */
-
-    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);
-
-    }
-
-    /**
-     * \brief Insert the given element into the component of the others.
-     *
-     * This methods insert the element \e a into the component of the
-     * element \e comp. 
-     */
-
-    void insert(const T &a, const T &comp) {
-      
-      IIter clit = _find(m[comp]);
-      ItemList &c = *clit->my_class;
-      c.push_back(ItemType(a,0));
-      IIter ai = c.end();
-      --ai;
-      ai->parent = clit;
-      m.set(a, ai);
-      ++clit->size;
-    }
-
-
-    /**
-     * \brief Find the leader of the component of the given element.
-     *
-     * The method returns the leader of the component of the given element.
-     */
-
-    T find(const T &a) const {
-      return _find(m[a])->me;
-    }
-
-
-    /**
-     * \brief Joining the component of element \e a and element \e b.
-     *
-     * This is the \e union operation of the Union-Find structure. 
-     * Joins the component of elemenent \e a and component of
-     * element \e b. If \e a and \e b are in the same component then
-     * returns false else returns true.
-     */
-
-    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;
-    }
-
-
-    /**
-     * \brief Returns the size of the component of element \e a.
-     *
-     * Returns the size of the component of element \e a.
-     */
-
-    int size(const T &a) const {
-      return _find(m[a])->size;
-    }
-
-
-    /**
-     * \brief Split up the component of the element. 
-     *
-     * Splitting the component of the element into sigleton
-     * components (component of size one).
-     */
-
-    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;
-    }
-
-
-    /**
-     * \brief Set the given element to the leader element of its component.
-     *
-     * Set the given element to the leader element of its component.
-     */
-
-    void makeRep(const T &a) {
-
-      IIter ia = m[a];
-      IIter la = _find(ia);
-      if (la == ia) return;
-
-      ia->my_class = la->my_class;
-      la->my_class = 0;
-
-      ia->size = la->size;
-
-      CIter l = ia->my_class;
-      l->splice(l->begin(),*l,ia);
-
-      ia->parent = ia;
-      la->parent = ia;
-    }
-
-    /**
-     * \brief Move the given element to an other component.
-     *
-     * This method moves the element \e a from its component
-     * to the component of \e comp.
-     * If \e a and \e comp are in the same component then
-     * it returns false otherwise it returns true.
-     */
-
-    bool move(const T &a, const T &comp) {
-
-      IIter ai = m[a];
-      IIter lai = _find(ai);
-      IIter clit = _find(m[comp]);
-
-      if (lai == clit)
-	return false;
-
-      ItemList &c = *clit->my_class;
-
-      bool is_leader = (lai == ai);
-      bool singleton = false;
-
-      if (is_leader) {
-	++lai;
-      }
-
-      c.splice(c.end(), *lai->my_class, ai);
-
-      if (is_leader) {
-	if (ai->size == 1) {
-	  classes.erase(ai->my_class);
-	  singleton = true;
-	}
-	else {
-	  lai->size = ai->size; 
-	  lai->my_class = ai->my_class;	
-	}
-      }
-      if (!singleton) {
-	for (IIter i = lai; i != lai->my_class->end(); ++i)
-	  i->parent = lai;
-	--lai->size;
-      }
-
-      ai->parent = clit;
-      ai->my_class = 0;
-      ++clit->size;
-
-      return true;
-    }
-
-
-    /**
-     * \brief Remove the given element from the structure.
-     *
-     * Remove the given element from the structure.
-     *
-     * Removes the element from its component and if the component becomes
-     * empty then removes that component from the component list.
-     */
-    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; 
-	la->my_class = ma->my_class;	
-      }
-
-      for (IIter i = la; i != la->my_class->end(); ++i) {
-	i->parent = la;
-      }
-
-      la->size--;
-      la->my_class->erase(ma);
-      m.set(a,0);
-    }
-
-    /**
-     * \brief Removes the component of the given element from the structure.
-     *
-     * Removes the component of the given element from the structure.
-     */
-
-    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;
-      }
-    };
-
-    /**
-     * \brief Sets the iterator to point to the first component.
-     * 
-     * Sets the iterator to point to the first component.
-     *
-     * With the \ref first, \ref valid and \ref next methods you can
-     * iterate through the components. For example:
-     * \code
-     * UnionFindEnum<Graph::Node, Graph::NodeMap>::MapType map(G);
-     * UnionFindEnum<Graph::Node, Graph::NodeMap> U(map);
-     * UnionFindEnum<Graph::Node, Graph::NodeMap>::ClassIt iter;
-     *  for (U.first(iter); U.valid(iter); U.next(iter)) {
-     *    // iter is convertible to Graph::Node
-     *    cout << iter << endl;
-     *  }
-     * \endcode
-     */
-
-    ClassIt& first(ClassIt& it) const {
-      it.first(classes);
-      return it;
-    }
-
-    /**
-     * \brief Returns whether the iterator is valid.
-     *
-     * Returns whether the iterator is valid.
-     *
-     * With the \ref first, \ref valid and \ref next methods you can
-     * iterate through the components. See the example here: \ref first.
-     */
-
-    bool valid(ClassIt const &it) const {
-      return it.valid(); 
-    }
-
-    /**
-     * \brief Steps the iterator to the next component. 
-     *
-     * Steps the iterator to the next component.
-     *
-     * With the \ref first, \ref valid and \ref next methods you can
-     * iterate through the components. See the example here: \ref first.
-     */
-
-    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;
-      }
-    };
-
-
-
-    /**
-     * \brief Sets the iterator to point to the first element of the component.
-     * 
-     * \anchor first2 
-     * Sets the iterator to point to the first element of the component.
-     *
-     * With the \ref first2 "first", \ref valid2 "valid" 
-     * and \ref next2 "next" methods you can
-     * iterate through the elements of a component. For example
-     * (iterating through the component of the node \e node):
-     * \code
-     * Graph::Node node = ...;
-     * UnionFindEnum<Graph::Node, Graph::NodeMap>::MapType map(G);
-     * UnionFindEnum<Graph::Node, Graph::NodeMap> U(map);
-     * UnionFindEnum<Graph::Node, Graph::NodeMap>::ItemIt iiter;
-     *   for (U.first(iiter, node); U.valid(iiter); U.next(iiter)) {
-     *     // iiter is convertible to Graph::Node
-     *     cout << iiter << endl;
-     *   }
-     * \endcode
-     */
-    
-    ItemIt& first(ItemIt& it, const T& a) const {
-      it.first( * _find(m[a])->my_class );
-      return it;
-    }
-
-    /**
-     * \brief Returns whether the iterator is valid.
-     *
-     * \anchor valid2
-     * Returns whether the iterator is valid.
-     *
-     * With the \ref first2 "first", \ref valid2 "valid" 
-     * and \ref next2 "next" methods you can
-     * iterate through the elements of a component.
-     * See the example here: \ref first2 "first".
-     */
-
-    bool valid(ItemIt const &it) const {
-      return it.valid(); 
-    }
-
-    /**
-     * \brief Steps the iterator to the next component. 
-     *
-     * \anchor next2
-     * Steps the iterator to the next component.
-     *
-     * With the \ref first2 "first", \ref valid2 "valid" 
-     * and \ref next2 "next" methods you can
-     * iterate through the elements of a component.
-     * See the example here: \ref first2 "first".
-     */
-
-    ItemIt& next(ItemIt& it) const {
-      it.next();
-      return it;
-    }
-    
-  };
-
-
-  //! @}
-
-} //namespace hugo
-
-#endif //HUGO_UNION_FIND_H
diff -r dce64ce044d6 -r ce29ae5b2e1b src/work/johanna/unionfind_test.cc
--- a/src/work/johanna/unionfind_test.cc	Thu Apr 29 16:59:00 2004 +0000
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,205 +0,0 @@
-#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 << "Inserting 8 to the component of 5 ..." << endl;
-  U.insert(8,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) == 3);
-  cout << "size of the class of 6: " << U.size(6) << endl;
-  check(U.size(6) == 1);
-  cout << "size of the class of 2: " << U.size(2) << endl;
-  check(U.size(2) == 3);
-
-  cout << "Inserting 9 ..." << endl;
-  U.insert(9);
-  print(U);
-  cout << "Inserting 10 to the component of 9 ..." << endl;
-  U.insert(10,9);
-  print(U);
-
-  cout << "Joining 8 and 10..." << endl;
-  check(U.join(8,10));
-  print(U);
-
-  cout << "Move 9 to the class of 4 ..." << endl;
-  check(U.move(9,4));
-  print(U);
-
-  cout << "Move 9 to the class of 2 ..." << endl;
-  check(!U.move(9,2));
-  print(U);
-
-  cout << "size of the class of 4: " << U.size(4) << endl;
-  check(U.size(4) == 4);
-  cout << "size of the class of 9: " << U.size(9) << endl;
-  check(U.size(9) == 4);
-  
-  cout << "Move 5 to the class of 6 ..." << endl;
-  check(U.move(5,6));
-  print(U);
-
-  cout << "size of the class of 5: " << U.size(5) << endl;
-  check(U.size(5) == 2);
-  cout << "size of the class of 8: " << U.size(8) << endl;
-  check(U.size(8) == 3);
-
-  cout << "Move 7 to the class of 10 ..." << endl;
-  check(U.move(7,10));
-  print(U);
-
-  cout << "size of the class of 7: " << U.size(7) << endl;
-  check(U.size(7) == 4);
-
-  cout <<"erase 9: " << endl;
-  U.erase(9);
-  print(U);
-
-  cout <<"erase 1: " << endl;
-  U.erase(1);
-  print(U);
-
-  cout << "size of the class of 4: " << U.size(4) << endl;
-  check(U.size(4) == 2);
-  cout << "size of the class of 2: " << U.size(2) << endl;
-  check(U.size(2) == 2);
-
-
-  cout <<"erase 1: " << endl;
-  U.erase(1);
-  print(U);
-
-  cout <<"erase 6: " << endl;
-  U.erase(6);
-  print(U);
-
-  cout << "split the class of 8: " << endl;
-  U.split(8);
-  print(U);
-
-
-  cout << "size of the class of 4: " << U.size(4) << endl;
-  check(U.size(4) == 2);
-  cout << "size of the class of 3: " << U.size(3) << endl;
-  check(U.size(3) == 1);
-  cout << "size of the class of 2: " << U.size(2) << endl;
-  check(U.size(2) == 2);
-
-
-  cout << "Joining 3 - 4 and 2 - 4 ..." << endl;
-  check(U.join(3,4));
-  check(!U.join(2,4));
-  print(U);
-
-
-  cout << "size of the class of 4: " << U.size(4) << endl;
-  check(U.size(4) == 3);
-  cout << "size of the class of 3: " << U.size(3) << endl;
-  check(U.size(3) == 3);
-  cout << "size of the class of 2: " << U.size(2) << endl;
-  check(U.size(2) == 3);
-
-  cout << "makeRep(4)" << endl;
-  U.makeRep(4);
-  print(U);
-  cout << "makeRep(3)" << endl;
-  U.makeRep(3);
-  print(U);
-  cout << "makeRep(2)" << endl;
-  U.makeRep(2);
-  print(U);
-
-  cout << "size of the class of 4: " << U.size(4) << endl;
-  check(U.size(4) == 3);
-  cout << "size of the class of 3: " << U.size(3) << endl;
-  check(U.size(3) == 3);
-  cout << "size of the class of 2: " << U.size(2) << endl;
-  check(U.size(2) == 3);
-
-
-  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;
-}