Changeset 2205:c20b0eb92a33 in lemon-0.x

Timestamp:

09/06/06 13:17:12 (17 years ago)

Author:

Balazs Dezso

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2930

Message:

UnionFind?
Changing the representation of the union-find
it has the same running time but it takes just 2/3 space
! does not auto insert items /performance/

UnionFindEnum?
Changing the interface - more convenient to UnionFind?
Does not based on the stl data structures /it could be disadvantage/

=> does not use singular iterator assignment /not stl conform, but always work/

Just new iterator interface

MaxMatching? + UnionFindTest?
Using new iterator interface instead of the old

Files:

• lemon/kruskal.h (modified) (3 diffs)
• lemon/max_matching.h (modified) (3 diffs)
• lemon/unionfind.h (modified) (2 diffs)
• test/unionfind_test.cc (modified) (3 diffs)

lemon/kruskal.h

@@ -25 +25 @@
 #include <lemon/bits/utility.h>
 #include <lemon/bits/traits.h>
+#include <lemon/time_measure.h>
+#include <iostream>
 
 ///\ingroup spantree
@@ -118 +120 @@
     typedef typename GR::Node Node;
 
-    NodeIntMap comp(g, -1);
-    UnionFind<Node,NodeIntMap> uf(comp); 
+    Timer timer;
+    NodeIntMap comp(g);
+    UnionFind<Node,NodeIntMap> uf(comp);
+    for (typename GR::NodeIt it(g); it != INVALID; ++it) {
+      uf.insert(it);
+    }
       
     EdgeCost tot_cost = 0;
@@ -133 +139 @@
       }
     }
+    std::cout << timer << std::endl;
     return tot_cost;
   }

lemon/max_matching.h

@@ -66 +66 @@
     typedef typename Graph::IncEdgeIt IncEdgeIt;
 
-    typedef UnionFindEnum<Node, Graph::template NodeMap> UFE;
+    typedef typename Graph::template NodeMap<int> UFECrossRef;
+    typedef UnionFindEnum<Node, UFECrossRef> UFE;
 
   public:
@@ -122 +123 @@
       //representative elements of UFE blossom) and for the nodes in C 
       
-      typename UFE::MapType blossom_base(g);
+      UFECrossRef blossom_base(g);
       UFE blossom(blossom_base);
-      typename UFE::MapType tree_base(g);
+
+      UFECrossRef tree_base(g);
       UFE tree(tree_base);
+
       //If these UFE's would be members of the class then also
       //blossom_base and tree_base should be a member.
@@ -550 +553 @@
     }
     Node y=blossom.find(x);
-    typename UFE::ItemIt it;
-    for (tree.first(it,blossom.find(x)); tree.valid(it); tree.next(it)) {   
-      if ( position[it] == D ) {
-        typename UFE::ItemIt b_it;
-        for (blossom.first(b_it,it); blossom.valid(b_it); blossom.next(b_it)) {  
-          position.set( b_it ,C);
+    for (typename UFE::ItemIt tit(tree, y); tit != INVALID; ++tit) {   
+      if ( position[tit] == D ) {
+        for (typename UFE::ItemIt bit(blossom, tit); bit != INVALID; ++bit) {  
+          position.set( bit ,C);
         }
-        blossom.eraseClass(it);
-      } else position.set( it ,C);
+        blossom.eraseClass(tit);
+      } else position.set( tit ,C);
     }
     tree.eraseClass(y);

lemon/unionfind.h

@@ -37 +37 @@
   //! @{
 
-  /**
-   * \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 compression.
-   * 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.
-   *
-   * It is primarily used in Kruskal algorithm for finding minimal
-   * cost spanning tree in a graph.
-   * \sa kruskal()
-   *
-   * \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.
-   * \bug It is not clear what the constructor parameter is used for.
-   */
-
-  template <typename T, typename TIntMap>
+  /// \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 compression.
+  /// 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.
+  ///
+  /// It is primarily used in Kruskal algorithm for finding minimal
+  /// cost spanning tree in a graph.
+  /// \sa kruskal()
+  ///
+  /// \pre You need to add all the elements by the \ref insert()
+  /// method.  
+  template <typename Item, typename ItemIntMap>
   class UnionFind {
     
   public:
-    typedef T ElementType;
-    typedef std::pair<int,int> PairType;
+    typedef Item ElementType;
 
   private:
-    std::vector<PairType> data;
-    TIntMap& map;
+    // If the items vector stores negative value for an item then
+    // that item is root item and it has -items[it] component size.
+    // Else the items[it] contains the index of the parent.
+    std::vector<int> items;
+    ItemIntMap& index;
+
+    bool rep(int idx) const {
+      return items[idx] < 0;
+    }
+
+    int repIndex(int idx) const {
+      int k = idx;
+      while (!rep(k)) {
+        k = items[k] ;
+      }
+      while (idx != k) {
+        int next = items[idx];
+        const_cast<int&>(items[idx]) = k;
+        idx = next;
+      }
+      return k;
+    }
 
   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 Inserts 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);
+
+    /// \brief Constructor
+    ///
+    /// Constructor of the UnionFind class. You should give an item to
+    /// integer map which will be used from the data structure. If you
+    /// modify directly this map that may cause segmentation fault,
+    /// invalid data structure, or infinite loop when you use again
+    /// the union-find.
+    UnionFind(ItemIntMap& m) : index(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(const Item& a) {
+      return repIndex(index[a]);
+    }
+
+    /// \brief Inserts a new element into the structure.
+    ///
+    /// This method inserts a new element into the data structure. 
+    ///
+    /// The method returns the index of the new component.
+    int insert(const Item& a) {
+      int n = items.size();
+      items.push_back(-1);
+      index.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 element \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 ) 
+    /// \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 element \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(const Item& a, const Item& b) {
+      int ka = repIndex(index[a]);
+      int kb = repIndex(index[b]);
+
+      if ( ka == kb ) 
         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;
+      if (items[ka] < items[kb]) {
+        items[ka] += items[kb];
+        items[kb] = ka;
+      } else {
+        items[kb] += items[ka];
+        items[ka] = kb;
       }
       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;
+    /// \brief Returns the size of the component of element \e a.
+    ///
+    /// Returns the size of the component of element \e a.
+    int size(const Item& a) {
+      int k = repIndex(index[a]);
+      return - items[k];
     }
 
@@ -161 +148 @@
 
 
-
-
-  /*******************************************************/
-
-
-#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 a \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 compression.
+  ///
+  /// \pre You need to add all the elements by the \ref insert()
+  /// method.
+  ///
+  template <typename _Item, typename _ItemIntMap>
+  class UnionFindEnum {
+  public:
+    
+    typedef _Item Item;
+    typedef _ItemIntMap ItemIntMap;
+    
+  private:
+    
+    // If the parent stores negative value for an item then that item
+    // is root item and it has -items[it].parent component size.  Else
+    // the items[it].parent contains the index of the parent.
+    //
+    // The \c nextItem and \c prevItem provides the double-linked
+    // cyclic list of one component's items. The \c prevClass and
+    // \c nextClass gives the double linked list of the representant
+    // items. 
+    struct ItemT {
+      int parent;
+      Item item;
+
+      int nextItem, prevItem;
+      int nextClass, prevClass;
+    };
+
+    std::vector<ItemT> items;
+    ItemIntMap& index;
+
+    int firstClass;
+
+
+    bool rep(int idx) const {
+      return items[idx].parent < 0;
+    }
+
+    int repIndex(int idx) const {
+      int k = idx;
+      while (!rep(k)) {
+        k = items[k].parent;
+      }
+      while (idx != k) {
+        int next = items[idx].parent;
+        const_cast<int&>(items[idx].parent) = k;
+        idx = next;
+      }
+      return k;
+    }
+
+    void unlaceClass(int k) {
+      if (items[k].prevClass != -1) {
+        items[items[k].prevClass].nextClass = items[k].nextClass;
+      } else {
+        firstClass = items[k].nextClass;
+      }
+      if (items[k].nextClass != -1) {
+        items[items[k].nextClass].prevClass = items[k].prevClass;
+      }
+    } 
+
+    void spliceItems(int ak, int bk) {
+      items[items[ak].prevItem].nextItem = bk;
+      items[items[bk].prevItem].nextItem = ak;
+      int tmp = items[ak].prevItem;
+      items[ak].prevItem = items[bk].prevItem;
+      items[bk].prevItem = tmp;
+        
+    }
+
+  public:
+
+    UnionFindEnum(ItemIntMap& _index) 
+      : items(), index(_index), firstClass(-1) {}
+    
+    /// \brief Inserts the given element into a new component.
+    ///
+    /// This method creates a new component consisting only of the
+    /// given element.
+    ///
+    void insert(const Item& item) {
+      ItemT t;
+
+      int idx = items.size();
+      index.set(item, idx);
+
+      t.nextItem = idx;
+      t.prevItem = idx;
+      t.item = item;
+      t.parent = -1;
+      
+      t.nextClass = firstClass;
+      if (firstClass != -1) {
+        items[firstClass].prevClass = idx;
+      }
+      t.prevClass = -1;
+      firstClass = idx;
+
+      items.push_back(t);
+    }
+
+    /// \brief Inserts the given element into the component of the others.
+    ///
+    /// This methods inserts the element \e a into the component of the
+    /// element \e comp. 
+    void insert(const Item& item, const Item& comp) {
+      int k = repIndex(index[comp]);
+      ItemT t;
+
+      int idx = items.size();
+      index.set(item, idx);
+
+      t.prevItem = k;
+      t.nextItem = items[k].nextItem;
+      items[items[k].nextItem].prevItem = idx;
+      items[k].nextItem = idx;
+
+      t.item = item;
+      t.parent = k;
+
+      --items[k].parent;
+
+      items.push_back(t);
+    }
+
+    /// \brief Finds the leader of the component of the given element.
+    ///
+    /// The method returns the leader of the component of the given element.
+    const Item& find(const Item &item) const {
+      return items[repIndex(index[item])].item;
+    }
+
+    /// \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 element \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(const Item& a, const Item& b) {
+
+      int ak = repIndex(index[a]);
+      int bk = repIndex(index[b]);
+
+      if (ak == bk) {
+        return false;
+      }
+
+      if ( items[ak].parent < items[bk].parent ) {
+        unlaceClass(bk);
+        items[ak].parent += items[bk].parent;
+        items[bk].parent = ak;
+      } else {
+        unlaceClass(bk);
+        items[bk].parent += items[ak].parent;
+        items[ak].parent = bk;
+      }
+      spliceItems(ak, bk);
+
+      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 Item &item) const {
+      return - items[repIndex(index[item])].parent;
+    }
+
+    /// \brief Splits up the component of the element. 
+    ///
+    /// Splitting the component of the element into sigleton
+    /// components (component of size one).
+    void split(const Item &item) {
+      int k = repIndex(index[item]);
+      int idx = items[k].nextItem;
+      while (idx != k) {
+        int next = items[idx].nextItem;
+        
+        items[idx].parent = -1;
+        items[idx].prevItem = idx;
+        items[idx].nextItem = idx;
+        
+        items[idx].nextClass = firstClass;
+        items[firstClass].prevClass = idx;
+        firstClass = idx;
+
+        idx = next;
+      }
+
+      items[idx].parent = -1;
+      items[idx].prevItem = idx;
+      items[idx].nextItem = idx;
+      
+      items[firstClass].prevClass = -1;
+    }
+
+    /// \brief Sets the given element to the leader element of its component.
+    ///
+    /// Sets the given element to the leader element of its component.
+    void makeRep(const Item &item) {
+      int nk = index[item];
+      int k = repIndex(nk);
+      if (nk == k) return;
+      
+      if (items[k].prevClass != -1) {
+        items[items[k].prevClass].nextClass = nk;
+      } else {
+        firstClass = nk;
+      }
+      if (items[k].nextClass != -1) {
+        items[items[k].nextClass].prevClass = nk;
+      }
+      
+      int idx = items[k].nextItem;
+      while (idx != k) {
+        items[idx].parent = nk;
+        idx = items[idx].nextItem;
+      }
+      
+      items[nk].parent = items[k].parent;
+      items[k].parent = nk;
+    }
+
+    /// \brief Removes 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.
+    ///
+    /// \warning It is an error to remove an element which is not in
+    /// the structure.
+    void erase(const Item &item) {
+      int idx = index[item];
+      if (rep(idx)) {
+        int k = idx;
+        if (items[k].parent == -1) {
+          unlaceClass(idx);
+          return;
+        } else {
+          int nk = items[k].nextItem;
+          if (items[k].prevClass != -1) {
+            items[items[k].prevClass].nextClass = nk;
+          } else {
+            firstClass = nk;
+          }
+          if (items[k].nextClass != -1) {
+            items[items[k].nextClass].prevClass = nk;
+          }
+      
+          int idx = items[k].nextItem;
+          while (idx != k) {
+            items[idx].parent = nk;
+            idx = items[idx].nextItem;
+          }
+          
+          items[nk].parent = items[k].parent + 1;
+        }
+      } else {
+        
+        int k = repIndex(idx);
+        idx = items[k].nextItem;
+        while (idx != k) {
+          items[idx].parent = k;
+          idx = items[idx].nextItem;
+        }
+
+        ++items[k].parent;
+      }
+
+      idx = index[item];      
+      items[items[idx].prevItem].nextItem = items[idx].nextItem;
+      items[items[idx].nextItem].prevItem = items[idx].prevItem;
+
+    }    
+
+    /// \brief Moves the given element to another 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 Item &item, const Item &comp) {
+      if (repIndex(index[item]) == repIndex(index[comp])) return false;
+      erase(item);
+      insert(item, comp);
+      return true;
+    }
+
+
+    /// \brief Removes the component of the given element from the structure.
+    ///
+    /// Removes the component of the given element from the structure.
+    ///
+    /// \warning It is an error to give an element which is not in the
+    /// structure.
+    void eraseClass(const Item &item) {
+      unlaceClass(repIndex(index[item]));
+    }
+
+    /// \brief Lemon style iterator for the representant items.
+    ///
+    /// ClassIt is a lemon style iterator for the components. It iterates
+    /// on the representant items of the classes.
+    class ClassIt {
+    public:
+      /// \brief Constructor of the iterator
+      ///
+      /// Constructor of the iterator
+      ClassIt(const UnionFindEnum& ufe) : unionFind(&ufe) {
+        idx = unionFind->firstClass;
+      }
+
+      /// \brief Constructor to get invalid iterator
+      ///
+      /// Constructor to get invalid iterator
+      ClassIt(Invalid) : unionFind(0), idx(-1) {}
+      
+      /// \brief Increment operator
+      ///
+      /// It steps to the next representant item.
+      ClassIt& operator++() {
+        idx = unionFind->items[idx].nextClass;
+        return *this;
+      }
+      
+      /// \brief Conversion operator
+      ///
+      /// It converts the iterator to the current representant item.
+      operator const Item&() const {
+        return unionFind->items[idx].item;
+      }
+
+      /// \brief Equality operator
+      ///
+      /// Equality operator
+      bool operator==(const ClassIt& i) { 
+        return i.idx == idx;
+      }
+
+      /// \brief Inequality operator
+      ///
+      /// Inequality operator
+      bool operator!=(const ClassIt& i) { 
+        return i.idx != idx;
+      }
+      
+    private:
+      const UnionFindEnum* unionFind;
+      int idx;
+    };
+
+    /// \brief Lemon style iterator for the items of a component.
+    ///
+    /// ClassIt is a lemon style iterator for the components. It iterates
+    /// on the items of a class. By example if you want to iterate on
+    /// each items of each classes then you may write the next code.
+    ///\code
+    /// for (ClassIt cit(ufe); cit != INVALID; ++cit) {
+    ///   std::cout << "Class: ";
+    ///   for (ItemIt iit(ufe, cit); iit != INVALID; ++iit) {
+    ///     std::cout << toString(iit) << ' ' << std::endl;
+    ///   }
+    ///   std::cout << std::endl;
+    /// }
+    ///\endcode
+    class ItemIt {
+    public:
+      /// \brief Constructor of the iterator
+      ///
+      /// Constructor of the iterator. The iterator iterates
+      /// on the class of the \c item.
+      ItemIt(const UnionFindEnum& ufe, const Item& item) : unionFind(&ufe) {
+        idx = unionFind->repIndex(unionFind->index[item]);
+      }
+
+      /// \brief Constructor to get invalid iterator
+      ///
+      /// Constructor to get invalid iterator
+      ItemIt(Invalid) : unionFind(0), idx(-1) {}
+      
+      /// \brief Increment operator
+      ///
+      /// It steps to the next item in the class.
+      ItemIt& operator++() {
+        idx = unionFind->items[idx].nextItem;
+        if (unionFind->rep(idx)) idx = -1;
+        return *this;
+      }
+      
+      /// \brief Conversion operator
+      ///
+      /// It converts the iterator to the current item.
+      operator const Item&() const {
+        return unionFind->items[idx].item;
+      }
+
+      /// \brief Equality operator
+      ///
+      /// Equality operator
+      bool operator==(const ItemIt& i) { 
+        return i.idx == idx;
+      }
+
+      /// \brief Inequality operator
+      ///
+      /// Inequality operator
+      bool operator!=(const ItemIt& i) { 
+        return i.idx != idx;
+      }
+      
+    private:
+      const UnionFindEnum* unionFind;
+      int idx;
+    };
+
   };
 
 
-  /**
-   * \brief A \e Union-Find data structure implementation which
-   * is able to enumerate the components.
-   *
-   * The class implements a \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 compression.
-   *
-   * \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;
-    }
-
-    const ItemList& classOf(const T &a) const {
-      return *_find(m[a])->my_class;
-    }
-
-  public:
-    UnionFindEnum(MapType& _m) : m(_m) {}
-
-
-    /**
-     * \brief Inserts 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 Inserts the given element into the component of the others.
-     *
-     * This methods inserts 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,CIter()));
-      IIter ai = c.end();
-      --ai;
-      ai->parent = clit;
-      m.set(a, ai);
-      ++clit->size;
-    }
-
-
-    /**
-     * \brief Finds 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 element \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);
-      }
-      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);
-      }
-
-      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 Splits 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 Sets the given element to the leader element of its component.
-     *
-     * Sets 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;
-
-      ia->size = la->size;
-
-      CIter l = ia->my_class;
-      l->splice(l->begin(),*l,ia);
-
-      ia->parent = ia;
-      la->parent = ia;
-    }
-
-    /**
-     * \brief Moves the given element to another 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 &cl = *clit->my_class,
-        &al = *lai->my_class;
-
-      bool is_leader = (lai == ai);
-      bool singleton = false;
-
-      if (is_leader) {
-        ++lai;
-      }
-
-      cl.splice(cl.end(), al, 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 != al.end(); ++i)
-          i->parent = lai;
-        --lai->size;
-      }
-
-      ai->parent = clit;
-      ++clit->size;
-
-      return true;
-    }
-
-
-    /**
-     * \brief Removes 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.
-     *
-     * It is an error to remove an element which is not in the structure.
-     */
-    void erase(const T &a) {
-
-      IIter ma = m[a];
-
-      IIter la = _find(ma);
-      if (la == ma) {
-        if (ma -> size == 1){
-          classes.erase(ma->my_class);
-          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);
-    }
-
-    /**
-     * \brief Removes the component of the given element from the structure.
-     *
-     * Removes the component of the given element from the structure.
-     *
-     * It is an error to give an element which is not in the structure.
-     */
-
-    void eraseClass(const T &a) {
-      IIter ma = m[a];
-      classes.erase(_find(ma)->my_class);
-    }
-
-
-    class ClassIt {
-      friend class UnionFindEnum;
-
-      CcIter i;
-      const ClassList *l;
-
-    public:
-      ClassIt(Invalid): l(0) {}
-      ClassIt() {}
-      ClassIt(UnionFindEnum const &ufe) {
-        l = &ufe.classes;
-        i = l->begin();
-      }
-      
-      operator const T& () const { 
-        ItemList const &ll = *i;
-        return (ll.begin())->me;
-      }
-      bool operator == (ClassIt const &it) const {
-        return (l==it.l && i==it.i) || (!valid() && !it.valid());
-      }
-      bool operator != (ClassIt const &it) const {
-        return !(*this == it);
-      }
-      bool operator < (ClassIt const &it) const {
-        return (i < it.i);
-      }
-
-      bool operator==(Invalid) const {
-        return !valid();
-      }
-      bool operator!=(Invalid) const {
-        return valid();
-      }
-
-      ClassIt& operator++() {
-        ++i;
-        return *this;
-      }
-
-      // obsoleted:
-      bool valid() const { return l!=0 && i!=l->end(); }
-    };
-
-    /**
-     * \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
-     *
-     * \bug obsoleted, use the new LEMON iterator interface instead
-     */
-
-    ClassIt& first(ClassIt& it) const {
-      it = ClassIt(*this);
-      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.
-     *
-     * \bug obsoleted, use the new LEMON iterator interface instead
-     */
-
-    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 {
-      return ++it;
-    }
-
-
-    class ItemIt {
-      friend class UnionFindEnum;
-
-      IcIter i;
-      const ItemList *l;
-    public:
-      ItemIt(Invalid): l(0) {}
-      ItemIt() {}
-      ItemIt(UnionFindEnum const &ufe, const T& a) {
-        l = &ufe.classOf(a);
-        i = l->begin();
-      }
-      
-      operator const T& () const { return i->me; }
-      bool operator == (ItemIt const &it) const {
-        return (l==it.l && i==it.i) || (!valid() && !it.valid());
-      }
-      bool operator != (ItemIt const &it) const {
-        return !(*this == it);
-      }
-      bool operator < (ItemIt const &it) const {
-        return (i < it.i);
-      }
-
-      bool operator==(Invalid) const {
-        return !valid();
-      }
-      bool operator!=(Invalid) const {
-        return valid();
-      }
-
-      ItemIt& operator++() {
-        ++i;
-        return *this;
-      }
-
-      // obsoleted:
-      bool valid() const { return l!=0 && i!=l->end(); }
-    };
-
-
-
-    /**
-     * \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
-     *
-     * \bug obsoleted, use the new LEMON iterator interface instead
-     */
-    
-    ItemIt& first(ItemIt& it, const T& a) const {
-      it = ItemIt(*this, a);
-      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".
-     *
-     * \bug obsoleted, use the new LEMON iterator interface instead
-     */
-
-    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".
-     *
-     * \bug obsoleted, use the new LEMON iterator interface instead
-     */
-
-    ItemIt& next(ItemIt& it) const {
-      return ++it;
-    }
-    
-  };
-
-
   //! @}
 

test/unionfind_test.cc

@@ -26 +26 @@
 using namespace std;
 
-template <typename T>
-class BaseMap : public StdMap<int,T> {};
-
-typedef UnionFindEnum<int, BaseMap> UFE;
+typedef UnionFindEnum<int, StdMap<int, int> > UFE;
 
 void print(UFE const &ufe) {
-  UFE::ClassIt cit;
   cout << "Print the classes of the structure:" << endl;
   int i = 1;
-  for (ufe.first(cit); ufe.valid(cit); ufe.next(cit)) {
+  for (UFE::ClassIt cit(ufe); cit != INVALID; ++cit) {
     cout << "  " << i << " (" << cit << "):" << flush;
-    UFE::ItemIt iit;
-    for (ufe.first(iit, cit); ufe.valid(iit); ufe.next(iit)) {
+    for (UFE::ItemIt iit(ufe, cit); iit != INVALID; ++iit) {
       cout << " " << iit << flush;
     }
@@ -49 +44 @@
 
 int main() {
-  UFE::MapType base;
+  StdMap<int, int> base;
   UFE U(base);
 
@@ -76 +71 @@
   U.insert(9);
   U.insert(10,9);
+
   check(U.join(8,10),"Test failed.");