alpar@906: /* -*- C++ -*-
alpar@906:  *
alpar@1956:  * This file is a part of LEMON, a generic C++ optimization library
alpar@1956:  *
alpar@2553:  * Copyright (C) 2003-2008
alpar@1956:  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@1359:  * (Egervary Research Group on Combinatorial Optimization, EGRES).
alpar@906:  *
alpar@906:  * Permission to use, modify and distribute this software is granted
alpar@906:  * provided that this copyright notice appears in all copies. For
alpar@906:  * precise terms see the accompanying LICENSE file.
alpar@906:  *
alpar@906:  * This software is provided "AS IS" with no warranty of any kind,
alpar@906:  * express or implied, and with no claim as to its suitability for any
alpar@906:  * purpose.
alpar@906:  *
alpar@906:  */
alpar@906: 
alpar@921: #ifndef LEMON_UNION_FIND_H
alpar@921: #define LEMON_UNION_FIND_H
beckerjc@483: 
klao@491: //!\ingroup auxdat
beckerjc@483: //!\file
beckerjc@483: //!\brief Union-Find data structures.
alpar@774: //!
beckerjc@483: 
beckerjc@483: #include <vector>
beckerjc@483: #include <list>
beckerjc@483: #include <utility>
beckerjc@483: #include <algorithm>
ladanyi@2551: #include <functional>
beckerjc@483: 
deba@1993: #include <lemon/bits/invalid.h>
beckerjc@483: 
alpar@921: namespace lemon {
beckerjc@483: 
deba@2308:   /// \ingroup auxdat
deba@2308:   ///
deba@2205:   /// \brief A \e Union-Find data structure implementation
deba@2205:   ///
deba@2205:   /// The class implements the \e Union-Find data structure. 
deba@2205:   /// The union operation uses rank heuristic, while
deba@2205:   /// the find operation uses path compression.
deba@2205:   /// This is a very simple but efficient implementation, providing 
deba@2205:   /// only four methods: join (union), find, insert and size.
deba@2205:   /// For more features see the \ref UnionFindEnum class.
deba@2205:   ///
deba@2205:   /// It is primarily used in Kruskal algorithm for finding minimal
deba@2205:   /// cost spanning tree in a graph.
deba@2205:   /// \sa kruskal()
deba@2205:   ///
deba@2205:   /// \pre You need to add all the elements by the \ref insert()
deba@2205:   /// method.  
deba@2308:   template <typename _ItemIntMap>
beckerjc@483:   class UnionFind {
beckerjc@483:   public:
deba@2308: 
deba@2308:     typedef _ItemIntMap ItemIntMap;
deba@2308:     typedef typename ItemIntMap::Key Item;
beckerjc@483: 
beckerjc@483:   private:
deba@2205:     // If the items vector stores negative value for an item then
deba@2205:     // that item is root item and it has -items[it] component size.
deba@2205:     // Else the items[it] contains the index of the parent.
deba@2205:     std::vector<int> items;
deba@2205:     ItemIntMap& index;
deba@2205: 
deba@2205:     bool rep(int idx) const {
deba@2205:       return items[idx] < 0;
deba@2205:     }
deba@2205: 
deba@2205:     int repIndex(int idx) const {
deba@2205:       int k = idx;
deba@2205:       while (!rep(k)) {
deba@2205:         k = items[k] ;
deba@2205:       }
deba@2205:       while (idx != k) {
deba@2205:         int next = items[idx];
deba@2205:         const_cast<int&>(items[idx]) = k;
deba@2205:         idx = next;
deba@2205:       }
deba@2205:       return k;
deba@2205:     }
beckerjc@483: 
beckerjc@483:   public:
beckerjc@483: 
deba@2205:     /// \brief Constructor
deba@2205:     ///
deba@2205:     /// Constructor of the UnionFind class. You should give an item to
deba@2205:     /// integer map which will be used from the data structure. If you
deba@2205:     /// modify directly this map that may cause segmentation fault,
deba@2205:     /// invalid data structure, or infinite loop when you use again
deba@2205:     /// the union-find.
deba@2205:     UnionFind(ItemIntMap& m) : index(m) {}
beckerjc@483: 
deba@2205:     /// \brief Returns the index of the element's component.
deba@2205:     ///
deba@2205:     /// The method returns the index of the element's component.
deba@2205:     /// This is an integer between zero and the number of inserted elements.
deba@2205:     ///
deba@2205:     int find(const Item& a) {
deba@2205:       return repIndex(index[a]);
beckerjc@483:     }
beckerjc@483: 
deba@2427:     /// \brief Clears the union-find data structure
deba@2427:     ///
deba@2427:     /// Erase each item from the data structure.
deba@2427:     void clear() {
deba@2427:       items.clear();
deba@2427:     }
deba@2427: 
deba@2205:     /// \brief Inserts a new element into the structure.
deba@2205:     ///
deba@2205:     /// This method inserts a new element into the data structure. 
deba@2205:     ///
deba@2205:     /// The method returns the index of the new component.
deba@2205:     int insert(const Item& a) {
deba@2205:       int n = items.size();
deba@2205:       items.push_back(-1);
deba@2205:       index.set(a,n);
beckerjc@483:       return n;
beckerjc@483:     }
beckerjc@483: 
deba@2205:     /// \brief Joining the components of element \e a and element \e b.
deba@2205:     ///
deba@2205:     /// This is the \e union operation of the Union-Find structure. 
deba@2205:     /// Joins the component of element \e a and component of
deba@2205:     /// element \e b. If \e a and \e b are in the same component then
deba@2205:     /// it returns false otherwise it returns true.
deba@2205:     bool join(const Item& a, const Item& b) {
deba@2205:       int ka = repIndex(index[a]);
deba@2205:       int kb = repIndex(index[b]);
beckerjc@483: 
deba@2205:       if ( ka == kb ) 
beckerjc@483: 	return false;
beckerjc@483: 
deba@2205:       if (items[ka] < items[kb]) {
deba@2205: 	items[ka] += items[kb];
deba@2205: 	items[kb] = ka;
deba@2205:       } else {
deba@2205: 	items[kb] += items[ka];
deba@2205: 	items[ka] = kb;
beckerjc@483:       }
beckerjc@483:       return true;
beckerjc@483:     }
beckerjc@483: 
deba@2205:     /// \brief Returns the size of the component of element \e a.
deba@2205:     ///
deba@2205:     /// Returns the size of the component of element \e a.
deba@2205:     int size(const Item& a) {
deba@2205:       int k = repIndex(index[a]);
deba@2205:       return - items[k];
beckerjc@483:     }
beckerjc@483: 
beckerjc@483:   };
beckerjc@483: 
deba@2308:   /// \ingroup auxdat
deba@2308:   ///
deba@2205:   /// \brief A \e Union-Find data structure implementation which
deba@2205:   /// is able to enumerate the components.
deba@2205:   ///
deba@2205:   /// The class implements a \e Union-Find data structure
deba@2205:   /// which is able to enumerate the components and the items in
deba@2205:   /// a component. If you don't need this feature then perhaps it's
deba@2205:   /// better to use the \ref UnionFind class which is more efficient.
deba@2205:   ///
deba@2205:   /// The union operation uses rank heuristic, while
deba@2205:   /// the find operation uses path compression.
deba@2205:   ///
deba@2205:   /// \pre You need to add all the elements by the \ref insert()
deba@2205:   /// method.
deba@2205:   ///
deba@2308:   template <typename _ItemIntMap>
deba@2205:   class UnionFindEnum {
deba@2205:   public:
deba@2205:     
deba@2205:     typedef _ItemIntMap ItemIntMap;
deba@2308:     typedef typename ItemIntMap::Key Item;
deba@2308: 
deba@2205:   private:
deba@2205:     
deba@2505:     ItemIntMap& index;
deba@2505: 
deba@2205:     // If the parent stores negative value for an item then that item
deba@2505:     // is root item and it has ~(items[it].parent) component id.  Else
deba@2205:     // the items[it].parent contains the index of the parent.
deba@2205:     //
deba@2505:     // The \c next and \c prev provides the double-linked
deba@2505:     // cyclic list of one component's items.
deba@2205:     struct ItemT {
deba@2205:       int parent;
deba@2205:       Item item;
beckerjc@483: 
deba@2505:       int next, prev;
deba@2205:     };
beckerjc@483: 
deba@2205:     std::vector<ItemT> items;
deba@2505:     int firstFreeItem;
beckerjc@483: 
deba@2505:     struct ClassT {
deba@2505:       int size;
deba@2505:       int firstItem;
deba@2505:       int next, prev;
deba@2505:     };
deba@2505:     
deba@2505:     std::vector<ClassT> classes;
deba@2505:     int firstClass, firstFreeClass;
deba@2505: 
deba@2505:     int newClass() {
deba@2505:       if (firstFreeClass == -1) {
deba@2505: 	int cdx = classes.size();
deba@2505: 	classes.push_back(ClassT());
deba@2505: 	return cdx;
deba@2505:       } else {
deba@2505: 	int cdx = firstFreeClass;
deba@2505: 	firstFreeClass = classes[firstFreeClass].next;
deba@2505: 	return cdx;
deba@2505:       }
deba@2505:     }
deba@2505: 
deba@2505:     int newItem() {
deba@2505:       if (firstFreeItem == -1) {
deba@2505: 	int idx = items.size();
deba@2505: 	items.push_back(ItemT());
deba@2505: 	return idx;
deba@2505:       } else {
deba@2505: 	int idx = firstFreeItem;
deba@2505: 	firstFreeItem = items[firstFreeItem].next;
deba@2505: 	return idx;
deba@2505:       }
deba@2505:     }
beckerjc@483: 
beckerjc@483: 
deba@2205:     bool rep(int idx) const {
deba@2205:       return items[idx].parent < 0;
beckerjc@483:     }
beckerjc@483: 
deba@2205:     int repIndex(int idx) const {
deba@2205:       int k = idx;
deba@2205:       while (!rep(k)) {
deba@2205:         k = items[k].parent;
deba@2205:       }
deba@2205:       while (idx != k) {
deba@2205:         int next = items[idx].parent;
deba@2205:         const_cast<int&>(items[idx].parent) = k;
deba@2205:         idx = next;
deba@2205:       }
deba@2205:       return k;
deba@2205:     }
deba@2205: 
deba@2505:     int classIndex(int idx) const {
deba@2505:       return ~(items[repIndex(idx)].parent);
deba@2505:     }
deba@2505: 
deba@2505:     void singletonItem(int idx) {
deba@2505:       items[idx].next = idx;
deba@2505:       items[idx].prev = idx;
deba@2505:     }
deba@2505: 
deba@2505:     void laceItem(int idx, int rdx) {
deba@2505:       items[idx].prev = rdx;
deba@2505:       items[idx].next = items[rdx].next;
deba@2505:       items[items[rdx].next].prev = idx;
deba@2505:       items[rdx].next = idx;
deba@2505:     }
deba@2505: 
deba@2505:     void unlaceItem(int idx) {
deba@2505:       items[items[idx].prev].next = items[idx].next;
deba@2505:       items[items[idx].next].prev = items[idx].prev;
deba@2505:       
deba@2505:       items[idx].next = firstFreeItem;
deba@2505:       firstFreeItem = idx;
deba@2505:     }
deba@2505: 
deba@2505:     void spliceItems(int ak, int bk) {
deba@2505:       items[items[ak].prev].next = bk;
deba@2505:       items[items[bk].prev].next = ak;
deba@2505:       int tmp = items[ak].prev;
deba@2505:       items[ak].prev = items[bk].prev;
deba@2505:       items[bk].prev = tmp;
deba@2505:         
deba@2505:     }
deba@2505: 
deba@2505:     void laceClass(int cls) {
deba@2505:       if (firstClass != -1) {
deba@2505:         classes[firstClass].prev = cls;
deba@2205:       }
deba@2505:       classes[cls].next = firstClass;
deba@2505:       classes[cls].prev = -1;
deba@2505:       firstClass = cls;
deba@2205:     } 
deba@2205: 
deba@2505:     void unlaceClass(int cls) {
deba@2505:       if (classes[cls].prev != -1) {
deba@2505:         classes[classes[cls].prev].next = classes[cls].next;
deba@2505:       } else {
deba@2505:         firstClass = classes[cls].next;
deba@2505:       }
deba@2505:       if (classes[cls].next != -1) {
deba@2505:         classes[classes[cls].next].prev = classes[cls].prev;
deba@2505:       }
deba@2505:       
deba@2505:       classes[cls].next = firstFreeClass;
deba@2505:       firstFreeClass = cls;
deba@2505:     } 
klao@2003: 
beckerjc@483:   public:
beckerjc@483: 
deba@2205:     UnionFindEnum(ItemIntMap& _index) 
deba@2505:       : index(_index), items(), firstFreeItem(-1), 
deba@2505: 	firstClass(-1), firstFreeClass(-1) {}
deba@2205:     
deba@2205:     /// \brief Inserts the given element into a new component.
deba@2205:     ///
deba@2205:     /// This method creates a new component consisting only of the
deba@2205:     /// given element.
deba@2205:     ///
deba@2505:     int insert(const Item& item) {
deba@2505:       int idx = newItem();
beckerjc@483: 
deba@2205:       index.set(item, idx);
beckerjc@483: 
deba@2505:       singletonItem(idx);
deba@2505:       items[idx].item = item;
deba@2505: 
deba@2505:       int cdx = newClass();
deba@2505: 
deba@2505:       items[idx].parent = ~cdx;
deba@2505: 
deba@2505:       laceClass(cdx);
deba@2505:       classes[cdx].size = 1;
deba@2505:       classes[cdx].firstItem = idx;
deba@2505: 
deba@2505:       firstClass = cdx;
deba@2205:       
deba@2505:       return cdx;
beckerjc@483:     }
beckerjc@483: 
deba@2205:     /// \brief Inserts the given element into the component of the others.
deba@2205:     ///
deba@2205:     /// This methods inserts the element \e a into the component of the
deba@2205:     /// element \e comp. 
deba@2505:     void insert(const Item& item, int cls) {
deba@2505:       int rdx = classes[cls].firstItem;
deba@2505:       int idx = newItem();
beckerjc@483: 
deba@2205:       index.set(item, idx);
deba@2205: 
deba@2505:       laceItem(idx, rdx);
deba@2205: 
deba@2505:       items[idx].item = item;
deba@2505:       items[idx].parent = rdx;
deba@2205: 
deba@2505:       ++classes[~(items[rdx].parent)].size;
beckerjc@483:     }
beckerjc@483: 
deba@2427:     /// \brief Clears the union-find data structure
deba@2427:     ///
deba@2427:     /// Erase each item from the data structure.
deba@2427:     void clear() {
deba@2427:       items.clear();
deba@2427:       firstClass = -1;
deba@2505:       firstFreeItem = -1;
deba@2427:     }
deba@2427: 
deba@2505:     /// \brief Finds the component of the given element.
deba@2205:     ///
deba@2505:     /// The method returns the component id of the given element.
deba@2505:     int find(const Item &item) const {
deba@2505:       return ~(items[repIndex(index[item])].parent);
beckerjc@483:     }
beckerjc@483: 
deba@2205:     /// \brief Joining the component of element \e a and element \e b.
deba@2205:     ///
deba@2205:     /// This is the \e union operation of the Union-Find structure. 
deba@2205:     /// Joins the component of element \e a and component of
deba@2205:     /// element \e b. If \e a and \e b are in the same component then
deba@2505:     /// returns -1 else returns the remaining class.
deba@2505:     int join(const Item& a, const Item& b) {
beckerjc@483: 
deba@2205:       int ak = repIndex(index[a]);
deba@2205:       int bk = repIndex(index[b]);
beckerjc@483: 
deba@2205:       if (ak == bk) {
deba@2505: 	return -1;
beckerjc@483:       }
beckerjc@483: 
deba@2505:       int acx = ~(items[ak].parent);
deba@2505:       int bcx = ~(items[bk].parent);
deba@2505: 
deba@2505:       int rcx;
deba@2505: 
deba@2505:       if (classes[acx].size > classes[bcx].size) {
deba@2505: 	classes[acx].size += classes[bcx].size;
deba@2205: 	items[bk].parent = ak;
deba@2505:         unlaceClass(bcx);
deba@2505: 	rcx = acx;
deba@2205:       } else {
deba@2505: 	classes[bcx].size += classes[acx].size;
deba@2205: 	items[ak].parent = bk;
deba@2505:         unlaceClass(acx);
deba@2505: 	rcx = bcx;
beckerjc@483:       }
deba@2205:       spliceItems(ak, bk);
beckerjc@483: 
deba@2505:       return rcx;
beckerjc@483:     }
beckerjc@483: 
deba@2505:     /// \brief Returns the size of the class.
deba@2205:     ///
deba@2505:     /// Returns the size of the class.
deba@2505:     int size(int cls) const {
deba@2505:       return classes[cls].size;
beckerjc@483:     }
beckerjc@483: 
deba@2505:     /// \brief Splits up the component. 
deba@2205:     ///
deba@2505:     /// Splitting the component into singleton components (component
deba@2505:     /// of size one).
deba@2505:     void split(int cls) {
deba@2505:       int fdx = classes[cls].firstItem;
deba@2505:       int idx = items[fdx].next;
deba@2505:       while (idx != fdx) {
deba@2505:         int next = items[idx].next;
deba@2505: 
deba@2505: 	singletonItem(idx);
deba@2505: 
deba@2505: 	int cdx = newClass();        
deba@2505:         items[idx].parent = ~cdx;
deba@2505: 
deba@2505: 	laceClass(cdx);
deba@2505: 	classes[cdx].size = 1;
deba@2505: 	classes[cdx].firstItem = idx;
deba@2205:         
deba@2205:         idx = next;
beckerjc@483:       }
beckerjc@483: 
deba@2505:       items[idx].prev = idx;
deba@2505:       items[idx].next = idx;
deba@2505: 
deba@2505:       classes[~(items[idx].parent)].size = 1;
deba@2205:       
beckerjc@483:     }
beckerjc@483: 
deba@2205:     /// \brief Removes the given element from the structure.
deba@2205:     ///
deba@2205:     /// Removes the element from its component and if the component becomes
deba@2205:     /// empty then removes that component from the component list.
deba@2205:     ///
deba@2205:     /// \warning It is an error to remove an element which is not in
deba@2205:     /// the structure.
deba@2505:     /// \warning This running time of this operation is proportional to the
deba@2505:     /// number of the items in this class.
deba@2505:     void erase(const Item& item) {
deba@2205:       int idx = index[item];
deba@2505:       int fdx = items[idx].next;
deba@2505: 
deba@2505:       int cdx = classIndex(idx);
deba@2505:       if (idx == fdx) {
deba@2505: 	unlaceClass(cdx);
deba@2505: 	items[idx].next = firstFreeItem;
deba@2505: 	firstFreeItem = idx;
deba@2505: 	return;
deba@2505:       } else {
deba@2505: 	classes[cdx].firstItem = fdx;
deba@2505: 	--classes[cdx].size;
deba@2505: 	items[fdx].parent = ~cdx;
deba@2505: 
deba@2505: 	unlaceItem(idx);
deba@2505: 	idx = items[fdx].next;
deba@2505: 	while (idx != fdx) {
deba@2505: 	  items[idx].parent = fdx;
deba@2505: 	  idx = items[idx].next;
deba@2505: 	}
deba@2205:           
beckerjc@483:       }
beckerjc@483: 
deba@2506:     }
deba@2506: 
deba@2506:     /// \brief Gives back a representant item of the component.
deba@2506:     ///
deba@2506:     /// Gives back a representant item of the component.
deba@2506:     Item item(int cls) const {
deba@2506:       return items[classes[cls].firstItem].item;
deba@2506:     }
beckerjc@483: 
deba@2205:     /// \brief Removes the component of the given element from the structure.
deba@2205:     ///
deba@2205:     /// Removes the component of the given element from the structure.
deba@2205:     ///
deba@2205:     /// \warning It is an error to give an element which is not in the
deba@2205:     /// structure.
deba@2505:     void eraseClass(int cls) {
deba@2505:       int fdx = classes[cls].firstItem;
deba@2505:       unlaceClass(cls);
deba@2505:       items[items[fdx].prev].next = firstFreeItem;
deba@2505:       firstFreeItem = fdx;
deba@2205:     }
beckerjc@483: 
deba@2205:     /// \brief Lemon style iterator for the representant items.
deba@2205:     ///
deba@2205:     /// ClassIt is a lemon style iterator for the components. It iterates
deba@2505:     /// on the ids of the classes.
deba@2205:     class ClassIt {
deba@2205:     public:
deba@2205:       /// \brief Constructor of the iterator
deba@2205:       ///
deba@2205:       /// Constructor of the iterator
deba@2205:       ClassIt(const UnionFindEnum& ufe) : unionFind(&ufe) {
deba@2505:         cdx = unionFind->firstClass;
beckerjc@483:       }
beckerjc@483: 
deba@2205:       /// \brief Constructor to get invalid iterator
deba@2205:       ///
deba@2205:       /// Constructor to get invalid iterator
deba@2505:       ClassIt(Invalid) : unionFind(0), cdx(-1) {}
deba@2205:       
deba@2205:       /// \brief Increment operator
deba@2205:       ///
deba@2205:       /// It steps to the next representant item.
deba@2205:       ClassIt& operator++() {
deba@2505:         cdx = unionFind->classes[cdx].next;
deba@2205:         return *this;
deba@2205:       }
deba@2205:       
deba@2205:       /// \brief Conversion operator
deba@2205:       ///
deba@2205:       /// It converts the iterator to the current representant item.
deba@2505:       operator int() const {
deba@2505:         return cdx;
beckerjc@483:       }
beckerjc@483: 
deba@2205:       /// \brief Equality operator
deba@2205:       ///
deba@2205:       /// Equality operator
deba@2205:       bool operator==(const ClassIt& i) { 
deba@2505:         return i.cdx == cdx;
deba@2205:       }
beckerjc@483: 
deba@2205:       /// \brief Inequality operator
deba@2205:       ///
deba@2205:       /// Inequality operator
deba@2205:       bool operator!=(const ClassIt& i) { 
deba@2505:         return i.cdx != cdx;
klao@2003:       }
beckerjc@483:       
deba@2205:     private:
deba@2205:       const UnionFindEnum* unionFind;
deba@2505:       int cdx;
deba@2205:     };
deba@2205: 
deba@2205:     /// \brief Lemon style iterator for the items of a component.
deba@2205:     ///
deba@2205:     /// ClassIt is a lemon style iterator for the components. It iterates
deba@2205:     /// on the items of a class. By example if you want to iterate on
deba@2205:     /// each items of each classes then you may write the next code.
deba@2205:     ///\code
deba@2205:     /// for (ClassIt cit(ufe); cit != INVALID; ++cit) {
deba@2205:     ///   std::cout << "Class: ";
deba@2205:     ///   for (ItemIt iit(ufe, cit); iit != INVALID; ++iit) {
deba@2205:     ///     std::cout << toString(iit) << ' ' << std::endl;
deba@2205:     ///   }
deba@2205:     ///   std::cout << std::endl;
deba@2205:     /// }
deba@2205:     ///\endcode
deba@2205:     class ItemIt {
deba@2205:     public:
deba@2205:       /// \brief Constructor of the iterator
deba@2205:       ///
deba@2205:       /// Constructor of the iterator. The iterator iterates
deba@2205:       /// on the class of the \c item.
deba@2505:       ItemIt(const UnionFindEnum& ufe, int cls) : unionFind(&ufe) {
deba@2505:         fdx = idx = unionFind->classes[cls].firstItem;
beckerjc@483:       }
beckerjc@483: 
deba@2205:       /// \brief Constructor to get invalid iterator
deba@2205:       ///
deba@2205:       /// Constructor to get invalid iterator
deba@2205:       ItemIt(Invalid) : unionFind(0), idx(-1) {}
deba@2205:       
deba@2205:       /// \brief Increment operator
deba@2205:       ///
deba@2205:       /// It steps to the next item in the class.
deba@2205:       ItemIt& operator++() {
deba@2505:         idx = unionFind->items[idx].next;
deba@2505:         if (idx == fdx) idx = -1;
deba@2205:         return *this;
klao@2003:       }
deba@2205:       
deba@2205:       /// \brief Conversion operator
deba@2205:       ///
deba@2205:       /// It converts the iterator to the current item.
deba@2205:       operator const Item&() const {
deba@2205:         return unionFind->items[idx].item;
klao@2003:       }
klao@2003: 
deba@2205:       /// \brief Equality operator
deba@2205:       ///
deba@2205:       /// Equality operator
deba@2205:       bool operator==(const ItemIt& i) { 
deba@2205:         return i.idx == idx;
klao@2003:       }
klao@2003: 
deba@2205:       /// \brief Inequality operator
deba@2205:       ///
deba@2205:       /// Inequality operator
deba@2205:       bool operator!=(const ItemIt& i) { 
deba@2205:         return i.idx != idx;
deba@2205:       }
deba@2205:       
deba@2205:     private:
deba@2205:       const UnionFindEnum* unionFind;
deba@2505:       int idx, fdx;
beckerjc@483:     };
beckerjc@483: 
beckerjc@483:   };
beckerjc@483: 
deba@2505:   /// \ingroup auxdat
deba@2505:   ///
deba@2505:   /// \brief A \e Extend-Find data structure implementation which
deba@2505:   /// is able to enumerate the components.
deba@2505:   ///
deba@2505:   /// The class implements an \e Extend-Find data structure which is
deba@2505:   /// able to enumerate the components and the items in a
deba@2505:   /// component. The data structure is a simplification of the
deba@2505:   /// Union-Find structure, and it does not allow to merge two components.
deba@2505:   ///
deba@2505:   /// \pre You need to add all the elements by the \ref insert()
deba@2505:   /// method.
deba@2505:   template <typename _ItemIntMap>
deba@2505:   class ExtendFindEnum {
deba@2505:   public:
deba@2505:     
deba@2505:     typedef _ItemIntMap ItemIntMap;
deba@2505:     typedef typename ItemIntMap::Key Item;
deba@2505: 
deba@2505:   private:
deba@2505:     
deba@2505:     ItemIntMap& index;
deba@2505: 
deba@2505:     struct ItemT {
deba@2505:       int cls;
deba@2505:       Item item;
deba@2505:       int next, prev;
deba@2505:     };
deba@2505: 
deba@2505:     std::vector<ItemT> items;
deba@2505:     int firstFreeItem;
deba@2505: 
deba@2505:     struct ClassT {
deba@2505:       int firstItem;
deba@2505:       int next, prev;
deba@2505:     };
deba@2505: 
deba@2505:     std::vector<ClassT> classes;
deba@2505: 
deba@2505:     int firstClass, firstFreeClass;
deba@2505: 
deba@2505:     int newClass() {
deba@2505:       if (firstFreeClass != -1) {
deba@2505: 	int cdx = firstFreeClass;
deba@2505: 	firstFreeClass = classes[cdx].next;
deba@2505: 	return cdx;
deba@2505:       } else {
deba@2505: 	classes.push_back(ClassT());
deba@2505: 	return classes.size() - 1;
deba@2505:       }
deba@2505:     }
deba@2505: 
deba@2505:     int newItem() {
deba@2505:       if (firstFreeItem != -1) {
deba@2505: 	int idx = firstFreeItem;
deba@2505: 	firstFreeItem = items[idx].next;
deba@2505: 	return idx;
deba@2505:       } else {
deba@2505: 	items.push_back(ItemT());
deba@2505: 	return items.size() - 1;
deba@2505:       }
deba@2505:     }
deba@2505: 
deba@2505:   public:
deba@2505: 
deba@2505:     /// \brief Constructor
deba@2505:     ExtendFindEnum(ItemIntMap& _index) 
deba@2505:       : index(_index), items(), firstFreeItem(-1), 
deba@2505: 	classes(), firstClass(-1), firstFreeClass(-1) {}
deba@2505:     
deba@2505:     /// \brief Inserts the given element into a new component.
deba@2505:     ///
deba@2505:     /// This method creates a new component consisting only of the
deba@2505:     /// given element.
deba@2505:     int insert(const Item& item) {
deba@2505:       int cdx = newClass();
deba@2505:       classes[cdx].prev = -1;
deba@2505:       classes[cdx].next = firstClass;
deba@2542:       if (firstClass != -1) {
deba@2542: 	classes[firstClass].prev = cdx;
deba@2542:       }
deba@2505:       firstClass = cdx;
deba@2505:       
deba@2505:       int idx = newItem();
deba@2505:       items[idx].item = item;
deba@2505:       items[idx].cls = cdx;
deba@2505:       items[idx].prev = idx;
deba@2505:       items[idx].next = idx;
deba@2505: 
deba@2505:       classes[cdx].firstItem = idx;
deba@2505: 
deba@2505:       index.set(item, idx);
deba@2505:       
deba@2505:       return cdx;
deba@2505:     }
deba@2505: 
deba@2505:     /// \brief Inserts the given element into the given component.
deba@2505:     ///
deba@2505:     /// This methods inserts the element \e item a into the \e cls class.
deba@2505:     void insert(const Item& item, int cls) {
deba@2505:       int idx = newItem();
deba@2505:       int rdx = classes[cls].firstItem;
deba@2505:       items[idx].item = item;
deba@2505:       items[idx].cls = cls;
deba@2505: 
deba@2505:       items[idx].prev = rdx;
deba@2505:       items[idx].next = items[rdx].next;
deba@2505:       items[items[rdx].next].prev = idx;
deba@2505:       items[rdx].next = idx;
deba@2505: 
deba@2505:       index.set(item, idx);
deba@2505:     }
deba@2505: 
deba@2505:     /// \brief Clears the union-find data structure
deba@2505:     ///
deba@2505:     /// Erase each item from the data structure.
deba@2505:     void clear() {
deba@2505:       items.clear();
deba@2505:       classes.clear;
deba@2505:       firstClass = firstFreeClass = firstFreeItem = -1;
deba@2505:     }
deba@2505: 
deba@2505:     /// \brief Gives back the class of the \e item.
deba@2505:     ///
deba@2505:     /// Gives back the class of the \e item.
deba@2505:     int find(const Item &item) const {
deba@2505:       return items[index[item]].cls;
deba@2505:     }
deba@2506: 
deba@2506:     /// \brief Gives back a representant item of the component.
deba@2506:     ///
deba@2506:     /// Gives back a representant item of the component.
deba@2506:     Item item(int cls) const {
deba@2506:       return items[classes[cls].firstItem].item;
deba@2506:     }
deba@2505:     
deba@2505:     /// \brief Removes the given element from the structure.
deba@2505:     ///
deba@2505:     /// Removes the element from its component and if the component becomes
deba@2505:     /// empty then removes that component from the component list.
deba@2505:     ///
deba@2505:     /// \warning It is an error to remove an element which is not in
deba@2505:     /// the structure.
deba@2505:     void erase(const Item &item) {
deba@2505:       int idx = index[item];
deba@2505:       int cdx = items[idx].cls;
deba@2505:       
deba@2505:       if (idx == items[idx].next) {
deba@2505: 	if (classes[cdx].prev != -1) {
deba@2505: 	  classes[classes[cdx].prev].next = classes[cdx].next; 
deba@2505: 	} else {
deba@2505: 	  firstClass = classes[cdx].next;
deba@2505: 	}
deba@2505: 	if (classes[cdx].next != -1) {
deba@2505: 	  classes[classes[cdx].next].prev = classes[cdx].prev; 
deba@2505: 	}
deba@2505: 	classes[cdx].next = firstFreeClass;
deba@2505: 	firstFreeClass = cdx;
deba@2505:       } else {
deba@2505: 	classes[cdx].firstItem = items[idx].next;
deba@2505: 	items[items[idx].next].prev = items[idx].prev;
deba@2505: 	items[items[idx].prev].next = items[idx].next;
deba@2505:       }
deba@2505:       items[idx].next = firstFreeItem;
deba@2505:       firstFreeItem = idx;
deba@2505: 	
deba@2505:     }    
deba@2505: 
deba@2505:     
deba@2505:     /// \brief Removes the component of the given element from the structure.
deba@2505:     ///
deba@2505:     /// Removes the component of the given element from the structure.
deba@2505:     ///
deba@2505:     /// \warning It is an error to give an element which is not in the
deba@2505:     /// structure.
deba@2505:     void eraseClass(int cdx) {
deba@2505:       int idx = classes[cdx].firstItem;
deba@2505:       items[items[idx].prev].next = firstFreeItem;
deba@2505:       firstFreeItem = idx;
deba@2505: 
deba@2505:       if (classes[cdx].prev != -1) {
deba@2505: 	classes[classes[cdx].prev].next = classes[cdx].next; 
deba@2505:       } else {
deba@2505: 	firstClass = classes[cdx].next;
deba@2505:       }
deba@2505:       if (classes[cdx].next != -1) {
deba@2505: 	classes[classes[cdx].next].prev = classes[cdx].prev; 
deba@2505:       }
deba@2505:       classes[cdx].next = firstFreeClass;
deba@2505:       firstFreeClass = cdx;
deba@2505:     }
deba@2505: 
deba@2505:     /// \brief Lemon style iterator for the classes.
deba@2505:     ///
deba@2505:     /// ClassIt is a lemon style iterator for the components. It iterates
deba@2505:     /// on the ids of classes.
deba@2505:     class ClassIt {
deba@2505:     public:
deba@2505:       /// \brief Constructor of the iterator
deba@2505:       ///
deba@2505:       /// Constructor of the iterator
deba@2505:       ClassIt(const ExtendFindEnum& ufe) : extendFind(&ufe) {
deba@2505:         cdx = extendFind->firstClass;
deba@2505:       }
deba@2505: 
deba@2505:       /// \brief Constructor to get invalid iterator
deba@2505:       ///
deba@2505:       /// Constructor to get invalid iterator
deba@2505:       ClassIt(Invalid) : extendFind(0), cdx(-1) {}
deba@2505:       
deba@2505:       /// \brief Increment operator
deba@2505:       ///
deba@2505:       /// It steps to the next representant item.
deba@2505:       ClassIt& operator++() {
deba@2505:         cdx = extendFind->classes[cdx].next;
deba@2505:         return *this;
deba@2505:       }
deba@2505:       
deba@2505:       /// \brief Conversion operator
deba@2505:       ///
deba@2505:       /// It converts the iterator to the current class id.
deba@2505:       operator int() const {
deba@2505:         return cdx;
deba@2505:       }
deba@2505: 
deba@2505:       /// \brief Equality operator
deba@2505:       ///
deba@2505:       /// Equality operator
deba@2505:       bool operator==(const ClassIt& i) { 
deba@2505:         return i.cdx == cdx;
deba@2505:       }
deba@2505: 
deba@2505:       /// \brief Inequality operator
deba@2505:       ///
deba@2505:       /// Inequality operator
deba@2505:       bool operator!=(const ClassIt& i) { 
deba@2505:         return i.cdx != cdx;
deba@2505:       }
deba@2505:       
deba@2505:     private:
deba@2505:       const ExtendFindEnum* extendFind;
deba@2505:       int cdx;
deba@2505:     };
deba@2505: 
deba@2505:     /// \brief Lemon style iterator for the items of a component.
deba@2505:     ///
deba@2505:     /// ClassIt is a lemon style iterator for the components. It iterates
deba@2505:     /// on the items of a class. By example if you want to iterate on
deba@2505:     /// each items of each classes then you may write the next code.
deba@2505:     ///\code
deba@2505:     /// for (ClassIt cit(ufe); cit != INVALID; ++cit) {
deba@2505:     ///   std::cout << "Class: ";
deba@2505:     ///   for (ItemIt iit(ufe, cit); iit != INVALID; ++iit) {
deba@2505:     ///     std::cout << toString(iit) << ' ' << std::endl;
deba@2505:     ///   }
deba@2505:     ///   std::cout << std::endl;
deba@2505:     /// }
deba@2505:     ///\endcode
deba@2505:     class ItemIt {
deba@2505:     public:
deba@2505:       /// \brief Constructor of the iterator
deba@2505:       ///
deba@2505:       /// Constructor of the iterator. The iterator iterates
deba@2505:       /// on the class of the \c item.
deba@2505:       ItemIt(const ExtendFindEnum& ufe, int cls) : extendFind(&ufe) {
deba@2505:         fdx = idx = extendFind->classes[cls].firstItem;
deba@2505:       }
deba@2505: 
deba@2505:       /// \brief Constructor to get invalid iterator
deba@2505:       ///
deba@2505:       /// Constructor to get invalid iterator
deba@2505:       ItemIt(Invalid) : extendFind(0), idx(-1) {}
deba@2505:       
deba@2505:       /// \brief Increment operator
deba@2505:       ///
deba@2505:       /// It steps to the next item in the class.
deba@2505:       ItemIt& operator++() {
deba@2505:         idx = extendFind->items[idx].next;
deba@2505: 	if (fdx == idx) idx = -1;
deba@2505:         return *this;
deba@2505:       }
deba@2505:       
deba@2505:       /// \brief Conversion operator
deba@2505:       ///
deba@2505:       /// It converts the iterator to the current item.
deba@2505:       operator const Item&() const {
deba@2505:         return extendFind->items[idx].item;
deba@2505:       }
deba@2505: 
deba@2505:       /// \brief Equality operator
deba@2505:       ///
deba@2505:       /// Equality operator
deba@2505:       bool operator==(const ItemIt& i) { 
deba@2505:         return i.idx == idx;
deba@2505:       }
deba@2505: 
deba@2505:       /// \brief Inequality operator
deba@2505:       ///
deba@2505:       /// Inequality operator
deba@2505:       bool operator!=(const ItemIt& i) { 
deba@2505:         return i.idx != idx;
deba@2505:       }
deba@2505:       
deba@2505:     private:
deba@2505:       const ExtendFindEnum* extendFind;
deba@2505:       int idx, fdx;
deba@2505:     };
deba@2505: 
deba@2505:   };
beckerjc@483: 
deba@2548:   /// \ingroup auxdat
deba@2548:   ///
deba@2548:   /// \brief A \e Union-Find data structure implementation which
deba@2548:   /// is able to store a priority for each item and retrieve the minimum of
deba@2548:   /// each class.
deba@2548:   ///
deba@2548:   /// A \e Union-Find data structure implementation which is able to
deba@2548:   /// store a priority for each item and retrieve the minimum of each
deba@2548:   /// class. In addition, it supports the joining and splitting the
deba@2548:   /// components. If you don't need this feature then you makes
deba@2548:   /// better to use the \ref UnionFind class which is more efficient.
deba@2548:   ///
deba@2548:   /// The union-find data strcuture based on a (2, 16)-tree with a
deba@2548:   /// tournament minimum selection on the internal nodes. The insert
deba@2548:   /// operation takes O(1), the find, set, decrease and increase takes
deba@2548:   /// O(log(n)), where n is the number of nodes in the current
deba@2548:   /// component.  The complexity of join and split is O(log(n)*k),
deba@2548:   /// where n is the sum of the number of the nodes and k is the
deba@2548:   /// number of joined components or the number of the components
deba@2548:   /// after the split.
deba@2548:   ///
deba@2548:   /// \pre You need to add all the elements by the \ref insert()
deba@2548:   /// method.
deba@2548:   ///
deba@2548:   template <typename _Value, typename _ItemIntMap, 
deba@2548:             typename _Comp = std::less<_Value> >
deba@2548:   class HeapUnionFind {
deba@2548:   public:
deba@2548:     
deba@2548:     typedef _Value Value;
deba@2548:     typedef typename _ItemIntMap::Key Item;
deba@2548: 
deba@2548:     typedef _ItemIntMap ItemIntMap;
deba@2548: 
deba@2548:     typedef _Comp Comp;
deba@2548: 
deba@2548:   private:
deba@2548: 
deba@2550:     static const int cmax = 16;
deba@2548: 
deba@2548:     ItemIntMap& index;
deba@2548: 
deba@2548:     struct ClassNode {
deba@2548:       int parent;
deba@2548:       int depth;
deba@2548: 
deba@2548:       int left, right;
deba@2548:       int next, prev;
deba@2548:     };
deba@2548: 
deba@2548:     int first_class;
deba@2548:     int first_free_class;
deba@2548:     std::vector<ClassNode> classes;
deba@2548: 
deba@2548:     int newClass() {
deba@2548:       if (first_free_class < 0) {
deba@2548:         int id = classes.size();
deba@2548:         classes.push_back(ClassNode());
deba@2548:         return id;
deba@2548:       } else {
deba@2548:         int id = first_free_class;
deba@2548:         first_free_class = classes[id].next;
deba@2548:         return id;
deba@2548:       }
deba@2548:     }
deba@2548: 
deba@2548:     void deleteClass(int id) {
deba@2548:       classes[id].next = first_free_class;
deba@2548:       first_free_class = id;
deba@2548:     }
deba@2548: 
deba@2548:     struct ItemNode {
deba@2548:       int parent;
deba@2548:       Item item;
deba@2548:       Value prio;
deba@2548:       int next, prev;
deba@2548:       int left, right;
deba@2548:       int size;
deba@2548:     };
deba@2548: 
deba@2548:     int first_free_node;
deba@2548:     std::vector<ItemNode> nodes;
deba@2548: 
deba@2548:     int newNode() {
deba@2548:       if (first_free_node < 0) {
deba@2548:         int id = nodes.size();
deba@2548:         nodes.push_back(ItemNode());
deba@2548:         return id;
deba@2548:       } else {
deba@2548:         int id = first_free_node;
deba@2548:         first_free_node = nodes[id].next;
deba@2548:         return id;
deba@2548:       }
deba@2548:     }
deba@2548: 
deba@2548:     void deleteNode(int id) {
deba@2548:       nodes[id].next = first_free_node;
deba@2548:       first_free_node = id;
deba@2548:     }
deba@2548: 
deba@2548:     Comp comp;
deba@2548: 
deba@2548:     int findClass(int id) const {
deba@2548:       int kd = id;
deba@2548:       while (kd >= 0) {
deba@2548:         kd = nodes[kd].parent;
deba@2548:       }
deba@2548:       return ~kd;
deba@2548:     }
deba@2548: 
deba@2548:     int leftNode(int id) const {
deba@2548:       int kd = ~(classes[id].parent);
deba@2548:       for (int i = 0; i < classes[id].depth; ++i) {
deba@2548:         kd = nodes[kd].left;
deba@2548:       }
deba@2548:       return kd;
deba@2548:     }
deba@2548: 
deba@2548:     int nextNode(int id) const {
deba@2548:       int depth = 0;
deba@2548:       while (id >= 0 && nodes[id].next == -1) {
deba@2548:         id = nodes[id].parent;
deba@2548:         ++depth;
deba@2548:       }
deba@2548:       if (id < 0) {
deba@2548:         return -1;
deba@2548:       }
deba@2548:       id = nodes[id].next;
deba@2548:       while (depth--) {
deba@2548:         id = nodes[id].left;      
deba@2548:       }
deba@2548:       return id;
deba@2548:     }
deba@2548: 
deba@2548: 
deba@2548:     void setPrio(int id) {
deba@2548:       int jd = nodes[id].left;
deba@2548:       nodes[id].prio = nodes[jd].prio;
deba@2548:       nodes[id].item = nodes[jd].item;
deba@2548:       jd = nodes[jd].next;
deba@2548:       while (jd != -1) {
deba@2548:         if (comp(nodes[jd].prio, nodes[id].prio)) {
deba@2548:           nodes[id].prio = nodes[jd].prio;
deba@2548:           nodes[id].item = nodes[jd].item;
deba@2548:         }
deba@2548:         jd = nodes[jd].next;
deba@2548:       }
deba@2548:     }
deba@2548: 
deba@2548:     void push(int id, int jd) {
deba@2548:       nodes[id].size = 1;
deba@2548:       nodes[id].left = nodes[id].right = jd;
deba@2548:       nodes[jd].next = nodes[jd].prev = -1;
deba@2548:       nodes[jd].parent = id;
deba@2548:     }
deba@2548: 
deba@2548:     void pushAfter(int id, int jd) {
deba@2548:       int kd = nodes[id].parent;
deba@2548:       if (nodes[id].next != -1) {
deba@2548:         nodes[nodes[id].next].prev = jd;
deba@2548:         if (kd >= 0) {
deba@2548:           nodes[kd].size += 1;
deba@2548:         }
deba@2548:       } else {
deba@2548:         if (kd >= 0) {
deba@2548:           nodes[kd].right = jd;
deba@2548:           nodes[kd].size += 1;
deba@2548:         }
deba@2548:       }
deba@2548:       nodes[jd].next = nodes[id].next;
deba@2548:       nodes[jd].prev = id;
deba@2548:       nodes[id].next = jd;
deba@2548:       nodes[jd].parent = kd;
deba@2548:     }
deba@2548: 
deba@2548:     void pushRight(int id, int jd) {
deba@2548:       nodes[id].size += 1;
deba@2548:       nodes[jd].prev = nodes[id].right;
deba@2548:       nodes[jd].next = -1;
deba@2548:       nodes[nodes[id].right].next = jd;
deba@2548:       nodes[id].right = jd;
deba@2548:       nodes[jd].parent = id;
deba@2548:     }
deba@2548: 
deba@2548:     void popRight(int id) {
deba@2548:       nodes[id].size -= 1;
deba@2548:       int jd = nodes[id].right;
deba@2548:       nodes[nodes[jd].prev].next = -1;
deba@2548:       nodes[id].right = nodes[jd].prev;
deba@2548:     }
deba@2548: 
deba@2548:     void splice(int id, int jd) {
deba@2548:       nodes[id].size += nodes[jd].size;
deba@2548:       nodes[nodes[id].right].next = nodes[jd].left;
deba@2548:       nodes[nodes[jd].left].prev = nodes[id].right;
deba@2548:       int kd = nodes[jd].left;
deba@2548:       while (kd != -1) {
deba@2548:         nodes[kd].parent = id;
deba@2548:         kd = nodes[kd].next;
deba@2548:       }
deba@2550:       nodes[id].right = nodes[jd].right;
deba@2548:     }
deba@2548: 
deba@2548:     void split(int id, int jd) {
deba@2548:       int kd = nodes[id].parent;
deba@2548:       nodes[kd].right = nodes[id].prev;
deba@2548:       nodes[nodes[id].prev].next = -1;
deba@2548:       
deba@2548:       nodes[jd].left = id;
deba@2548:       nodes[id].prev = -1;
deba@2548:       int num = 0;
deba@2548:       while (id != -1) {
deba@2548:         nodes[id].parent = jd;
deba@2548:         nodes[jd].right = id;
deba@2548:         id = nodes[id].next;
deba@2548:         ++num;
deba@2548:       }      
deba@2548:       nodes[kd].size -= num;
deba@2548:       nodes[jd].size = num;
deba@2548:     }
deba@2548: 
deba@2548:     void pushLeft(int id, int jd) {
deba@2548:       nodes[id].size += 1;
deba@2548:       nodes[jd].next = nodes[id].left;
deba@2548:       nodes[jd].prev = -1;
deba@2548:       nodes[nodes[id].left].prev = jd;
deba@2548:       nodes[id].left = jd;
deba@2548:       nodes[jd].parent = id;
deba@2548:     }
deba@2548: 
deba@2548:     void popLeft(int id) {
deba@2548:       nodes[id].size -= 1;
deba@2548:       int jd = nodes[id].left;
deba@2548:       nodes[nodes[jd].next].prev = -1;
deba@2548:       nodes[id].left = nodes[jd].next;
deba@2548:     }
deba@2548: 
deba@2548:     void repairLeft(int id) {
deba@2548:       int jd = ~(classes[id].parent);
deba@2548:       while (nodes[jd].left != -1) {
deba@2548: 	int kd = nodes[jd].left;
deba@2548: 	if (nodes[jd].size == 1) {
deba@2548: 	  if (nodes[jd].parent < 0) {
deba@2548: 	    classes[id].parent = ~kd;
deba@2548: 	    classes[id].depth -= 1;
deba@2548: 	    nodes[kd].parent = ~id;
deba@2548: 	    deleteNode(jd);
deba@2548: 	    jd = kd;
deba@2548: 	  } else {
deba@2548: 	    int pd = nodes[jd].parent;
deba@2548: 	    if (nodes[nodes[jd].next].size < cmax) {
deba@2548: 	      pushLeft(nodes[jd].next, nodes[jd].left);
deba@2632:               if (less(jd, nodes[jd].next) ||
deba@2632: 		  nodes[jd].item == nodes[pd].item) {
deba@2631:                 nodes[nodes[jd].next].prio = nodes[jd].prio;
deba@2631:                 nodes[nodes[jd].next].item = nodes[jd].item;
deba@2631: 	      }
deba@2548: 	      popLeft(pd);
deba@2548: 	      deleteNode(jd);
deba@2548: 	      jd = pd;
deba@2548: 	    } else {
deba@2548: 	      int ld = nodes[nodes[jd].next].left;
deba@2548: 	      popLeft(nodes[jd].next);
deba@2548: 	      pushRight(jd, ld);
deba@2631:               if (less(ld, nodes[jd].left) || 
deba@2631:                   nodes[ld].item == nodes[pd].item) {
deba@2548: 		nodes[jd].item = nodes[ld].item;
deba@2631: 		nodes[jd].prio = nodes[ld].prio;
deba@2548: 	      }
deba@2548: 	      if (nodes[nodes[jd].next].item == nodes[ld].item) {
deba@2548: 		setPrio(nodes[jd].next);
deba@2548: 	      }
deba@2548: 	      jd = nodes[jd].left;
deba@2548: 	    }
deba@2548: 	  }
deba@2548: 	} else {
deba@2548: 	  jd = nodes[jd].left;
deba@2548: 	}
deba@2548:       }
deba@2548:     }    
deba@2548: 
deba@2548:     void repairRight(int id) {
deba@2548:       int jd = ~(classes[id].parent);
deba@2548:       while (nodes[jd].right != -1) {
deba@2548: 	int kd = nodes[jd].right;
deba@2548: 	if (nodes[jd].size == 1) {
deba@2548: 	  if (nodes[jd].parent < 0) {
deba@2548: 	    classes[id].parent = ~kd;
deba@2548: 	    classes[id].depth -= 1;
deba@2548: 	    nodes[kd].parent = ~id;
deba@2548: 	    deleteNode(jd);
deba@2548: 	    jd = kd;
deba@2548: 	  } else {
deba@2548: 	    int pd = nodes[jd].parent;
deba@2548: 	    if (nodes[nodes[jd].prev].size < cmax) {
deba@2548: 	      pushRight(nodes[jd].prev, nodes[jd].right);
deba@2632:               if (less(jd, nodes[jd].prev) ||
deba@2632: 		  nodes[jd].item == nodes[pd].item) {
deba@2631:                 nodes[nodes[jd].prev].prio = nodes[jd].prio;
deba@2631:                 nodes[nodes[jd].prev].item = nodes[jd].item;
deba@2631: 	      }
deba@2548: 	      popRight(pd);
deba@2548: 	      deleteNode(jd);
deba@2548: 	      jd = pd;
deba@2548: 	    } else {
deba@2548: 	      int ld = nodes[nodes[jd].prev].right;
deba@2548: 	      popRight(nodes[jd].prev);
deba@2548: 	      pushLeft(jd, ld);
deba@2631:               if (less(ld, nodes[jd].right) ||
deba@2631:                   nodes[ld].item == nodes[pd].item) {
deba@2548: 		nodes[jd].item = nodes[ld].item;
deba@2631: 		nodes[jd].prio = nodes[ld].prio;
deba@2548: 	      }
deba@2548: 	      if (nodes[nodes[jd].prev].item == nodes[ld].item) {
deba@2548: 		setPrio(nodes[jd].prev);
deba@2548: 	      }
deba@2548: 	      jd = nodes[jd].right;
deba@2548: 	    }
deba@2548: 	  }
deba@2548: 	} else {
deba@2548: 	  jd = nodes[jd].right;
deba@2548: 	}
deba@2548:       }
deba@2548:     }
deba@2548: 
deba@2548: 
deba@2548:     bool less(int id, int jd) const {
deba@2548:       return comp(nodes[id].prio, nodes[jd].prio);
deba@2548:     }
deba@2548: 
deba@2548:     bool equal(int id, int jd) const {
deba@2548:       return !less(id, jd) && !less(jd, id);
deba@2548:     }
deba@2548: 
deba@2548: 
deba@2548:   public:
deba@2548: 
deba@2548:     /// \brief Returns true when the given class is alive.
deba@2548:     ///
deba@2548:     /// Returns true when the given class is alive, ie. the class is
deba@2548:     /// not nested into other class.
deba@2548:     bool alive(int cls) const {
deba@2548:       return classes[cls].parent < 0;
deba@2548:     }
deba@2548: 
deba@2548:     /// \brief Returns true when the given class is trivial.
deba@2548:     ///
deba@2548:     /// Returns true when the given class is trivial, ie. the class
deba@2548:     /// contains just one item directly.
deba@2548:     bool trivial(int cls) const {
deba@2548:       return classes[cls].left == -1;
deba@2548:     }
deba@2548: 
deba@2548:     /// \brief Constructs the union-find.
deba@2548:     ///
deba@2548:     /// Constructs the union-find.  
deba@2548:     /// \brief _index The index map of the union-find. The data
deba@2548:     /// structure uses internally for store references.
deba@2548:     HeapUnionFind(ItemIntMap& _index) 
deba@2548:       : index(_index), first_class(-1), 
deba@2548: 	first_free_class(-1), first_free_node(-1) {}
deba@2548: 
deba@2548:     /// \brief Insert a new node into a new component.
deba@2548:     ///
deba@2548:     /// Insert a new node into a new component.
deba@2548:     /// \param item The item of the new node.
deba@2548:     /// \param prio The priority of the new node.
deba@2548:     /// \return The class id of the one-item-heap.
deba@2548:     int insert(const Item& item, const Value& prio) {
deba@2548:       int id = newNode();
deba@2548:       nodes[id].item = item;
deba@2548:       nodes[id].prio = prio;
deba@2548:       nodes[id].size = 0;
deba@2548: 
deba@2548:       nodes[id].prev = -1;
deba@2548:       nodes[id].next = -1;
deba@2548: 
deba@2548:       nodes[id].left = -1;
deba@2548:       nodes[id].right = -1;
deba@2548: 
deba@2548:       nodes[id].item = item;
deba@2548:       index[item] = id;
deba@2548:       
deba@2548:       int class_id = newClass();
deba@2548:       classes[class_id].parent = ~id;
deba@2548:       classes[class_id].depth = 0;
deba@2548: 
deba@2548:       classes[class_id].left = -1;
deba@2548:       classes[class_id].right = -1;
deba@2548:       
deba@2548:       if (first_class != -1) {
deba@2548:         classes[first_class].prev = class_id;
deba@2548:       }
deba@2548:       classes[class_id].next = first_class;
deba@2548:       classes[class_id].prev = -1;
deba@2548:       first_class = class_id;
deba@2548: 
deba@2548:       nodes[id].parent = ~class_id;
deba@2548:       
deba@2548:       return class_id;
deba@2548:     }
deba@2548: 
deba@2548:     /// \brief The class of the item.
deba@2548:     ///
deba@2548:     /// \return The alive class id of the item, which is not nested into
deba@2548:     /// other classes.
deba@2548:     ///
deba@2548:     /// The time complexity is O(log(n)).
deba@2548:     int find(const Item& item) const {
deba@2548:       return findClass(index[item]);
deba@2548:     }
deba@2548:     
deba@2548:     /// \brief Joins the classes.
deba@2548:     ///
deba@2548:     /// The current function joins the given classes. The parameter is
deba@2548:     /// an STL range which should be contains valid class ids. The
deba@2548:     /// time complexity is O(log(n)*k) where n is the overall number
deba@2548:     /// of the joined nodes and k is the number of classes.
deba@2548:     /// \return The class of the joined classes.
deba@2548:     /// \pre The range should contain at least two class ids.
deba@2548:     template <typename Iterator>
deba@2548:     int join(Iterator begin, Iterator end) {
deba@2548:       std::vector<int> cs;
deba@2548:       for (Iterator it = begin; it != end; ++it) {
deba@2548:         cs.push_back(*it);
deba@2548:       }
deba@2548: 
deba@2548:       int class_id = newClass();
deba@2548:       { // creation union-find
deba@2548: 
deba@2548:         if (first_class != -1) {
deba@2548:           classes[first_class].prev = class_id;
deba@2548:         }
deba@2548:         classes[class_id].next = first_class;
deba@2548:         classes[class_id].prev = -1;
deba@2548:         first_class = class_id;
deba@2548: 
deba@2548:         classes[class_id].depth = classes[cs[0]].depth;
deba@2548:         classes[class_id].parent = classes[cs[0]].parent;
deba@2548:         nodes[~(classes[class_id].parent)].parent = ~class_id;
deba@2548: 
deba@2548:         int l = cs[0];
deba@2548: 
deba@2548:         classes[class_id].left = l;
deba@2548:         classes[class_id].right = l;
deba@2548: 
deba@2548:         if (classes[l].next != -1) {
deba@2548:           classes[classes[l].next].prev = classes[l].prev;
deba@2548:         }
deba@2548:         classes[classes[l].prev].next = classes[l].next;
deba@2548:         
deba@2548:         classes[l].prev = -1;
deba@2548:         classes[l].next = -1;
deba@2548: 
deba@2548:         classes[l].depth = leftNode(l);
deba@2548:         classes[l].parent = class_id;
deba@2548:         
deba@2548:       }
deba@2548: 
deba@2548:       { // merging of heap
deba@2548:         int l = class_id;
deba@2548:         for (int ci = 1; ci < int(cs.size()); ++ci) {
deba@2548:           int r = cs[ci];
deba@2548:           int rln = leftNode(r);
deba@2548:           if (classes[l].depth > classes[r].depth) {
deba@2548:             int id = ~(classes[l].parent);
deba@2548:             for (int i = classes[r].depth + 1; i < classes[l].depth; ++i) {
deba@2548:               id = nodes[id].right;
deba@2548:             }
deba@2548:             while (id >= 0 && nodes[id].size == cmax) {
deba@2548:               int new_id = newNode();
deba@2548:               int right_id = nodes[id].right;
deba@2548: 
deba@2548:               popRight(id);
deba@2548:               if (nodes[id].item == nodes[right_id].item) {
deba@2548:                 setPrio(id);
deba@2548:               }
deba@2548:               push(new_id, right_id);
deba@2548:               pushRight(new_id, ~(classes[r].parent));
deba@2631: 
deba@2631:               if (less(~classes[r].parent, right_id)) {
deba@2631:                 nodes[new_id].item = nodes[~classes[r].parent].item;
deba@2631:                 nodes[new_id].prio = nodes[~classes[r].parent].prio;
deba@2631:               } else {
deba@2631:                 nodes[new_id].item = nodes[right_id].item;
deba@2631:                 nodes[new_id].prio = nodes[right_id].prio;
deba@2631:               }
deba@2548: 
deba@2548:               id = nodes[id].parent;
deba@2548:               classes[r].parent = ~new_id;
deba@2548:             }
deba@2548:             if (id < 0) {
deba@2548:               int new_parent = newNode();
deba@2548:               nodes[new_parent].next = -1;
deba@2548:               nodes[new_parent].prev = -1;
deba@2548:               nodes[new_parent].parent = ~l;
deba@2548: 
deba@2548:               push(new_parent, ~(classes[l].parent));
deba@2548:               pushRight(new_parent, ~(classes[r].parent));
deba@2548:               setPrio(new_parent);
deba@2548: 
deba@2548:               classes[l].parent = ~new_parent;
deba@2548:               classes[l].depth += 1;
deba@2548:             } else {
deba@2548:               pushRight(id, ~(classes[r].parent));
deba@2548:               while (id >= 0 && less(~(classes[r].parent), id)) {
deba@2548:                 nodes[id].prio = nodes[~(classes[r].parent)].prio;
deba@2548:                 nodes[id].item = nodes[~(classes[r].parent)].item;
deba@2548:                 id = nodes[id].parent;
deba@2548:               }
deba@2548:             }
deba@2548:           } else if (classes[r].depth > classes[l].depth) {
deba@2548:             int id = ~(classes[r].parent);
deba@2548:             for (int i = classes[l].depth + 1; i < classes[r].depth; ++i) {
deba@2548:               id = nodes[id].left;
deba@2548:             }
deba@2548:             while (id >= 0 && nodes[id].size == cmax) {
deba@2548:               int new_id = newNode();
deba@2548:               int left_id = nodes[id].left;
deba@2548: 
deba@2548:               popLeft(id);
deba@2548:               if (nodes[id].prio == nodes[left_id].prio) {
deba@2548:                 setPrio(id);
deba@2548:               }
deba@2548:               push(new_id, left_id);
deba@2548:               pushLeft(new_id, ~(classes[l].parent));
deba@2631: 
deba@2631:               if (less(~classes[l].parent, left_id)) {
deba@2631:                 nodes[new_id].item = nodes[~classes[l].parent].item;
deba@2631:                 nodes[new_id].prio = nodes[~classes[l].parent].prio;
deba@2631:               } else {
deba@2631:                 nodes[new_id].item = nodes[left_id].item;
deba@2631:                 nodes[new_id].prio = nodes[left_id].prio;
deba@2631:               }
deba@2548: 
deba@2548:               id = nodes[id].parent;
deba@2548:               classes[l].parent = ~new_id;
deba@2548: 
deba@2548:             }
deba@2548:             if (id < 0) {
deba@2548:               int new_parent = newNode();
deba@2548:               nodes[new_parent].next = -1;
deba@2548:               nodes[new_parent].prev = -1;
deba@2548:               nodes[new_parent].parent = ~l;
deba@2548: 
deba@2548:               push(new_parent, ~(classes[r].parent));
deba@2548:               pushLeft(new_parent, ~(classes[l].parent));
deba@2548:               setPrio(new_parent);
deba@2548:               
deba@2548:               classes[r].parent = ~new_parent;
deba@2548:               classes[r].depth += 1;
deba@2548:             } else {
deba@2548:               pushLeft(id, ~(classes[l].parent));
deba@2548:               while (id >= 0 && less(~(classes[l].parent), id)) {
deba@2548:                 nodes[id].prio = nodes[~(classes[l].parent)].prio;
deba@2548:                 nodes[id].item = nodes[~(classes[l].parent)].item;
deba@2548:                 id = nodes[id].parent;
deba@2548:               }
deba@2548:             }
deba@2548:             nodes[~(classes[r].parent)].parent = ~l;
deba@2548:             classes[l].parent = classes[r].parent;
deba@2548:             classes[l].depth = classes[r].depth;
deba@2548:           } else {
deba@2548:             if (classes[l].depth != 0 && 
deba@2548:                 nodes[~(classes[l].parent)].size + 
deba@2548:                 nodes[~(classes[r].parent)].size <= cmax) {
deba@2548:               splice(~(classes[l].parent), ~(classes[r].parent));
deba@2548:               deleteNode(~(classes[r].parent));
deba@2548:               if (less(~(classes[r].parent), ~(classes[l].parent))) {
deba@2548:                 nodes[~(classes[l].parent)].prio = 
deba@2548:                   nodes[~(classes[r].parent)].prio;
deba@2548:                 nodes[~(classes[l].parent)].item = 
deba@2548:                   nodes[~(classes[r].parent)].item;
deba@2548:               }
deba@2548:             } else {
deba@2548:               int new_parent = newNode();
deba@2548:               nodes[new_parent].next = nodes[new_parent].prev = -1;
deba@2548:               push(new_parent, ~(classes[l].parent));
deba@2548:               pushRight(new_parent, ~(classes[r].parent));
deba@2548:               setPrio(new_parent);
deba@2548:             
deba@2548:               classes[l].parent = ~new_parent;
deba@2548:               classes[l].depth += 1;
deba@2548:               nodes[new_parent].parent = ~l;
deba@2548:             }
deba@2548:           }
deba@2548:           if (classes[r].next != -1) {
deba@2548:             classes[classes[r].next].prev = classes[r].prev;
deba@2548:           }
deba@2548:           classes[classes[r].prev].next = classes[r].next;
deba@2548: 
deba@2548:           classes[r].prev = classes[l].right;
deba@2548:           classes[classes[l].right].next = r;
deba@2548:           classes[l].right = r;
deba@2548:           classes[r].parent = l;
deba@2548: 
deba@2548:           classes[r].next = -1;
deba@2548:           classes[r].depth = rln;
deba@2548:         }
deba@2548:       }
deba@2548:       return class_id;
deba@2548:     }
deba@2548: 
deba@2548:     /// \brief Split the class to subclasses.
deba@2548:     ///
deba@2548:     /// The current function splits the given class. The join, which
deba@2548:     /// made the current class, stored a reference to the
deba@2548:     /// subclasses. The \c splitClass() member restores the classes
deba@2548:     /// and creates the heaps. The parameter is an STL output iterator
deba@2548:     /// which will be filled with the subclass ids. The time
deba@2548:     /// complexity is O(log(n)*k) where n is the overall number of
deba@2548:     /// nodes in the splitted classes and k is the number of the
deba@2548:     /// classes.
deba@2548:     template <typename Iterator>
deba@2548:     void split(int cls, Iterator out) {
deba@2548:       std::vector<int> cs;
deba@2548:       { // splitting union-find
deba@2548:         int id = cls;
deba@2548:         int l = classes[id].left;
deba@2548: 
deba@2548:         classes[l].parent = classes[id].parent;
deba@2548:         classes[l].depth = classes[id].depth;
deba@2548: 
deba@2548:         nodes[~(classes[l].parent)].parent = ~l;
deba@2548: 
deba@2548:         *out++ = l;
deba@2548: 
deba@2548:         while (l != -1) {
deba@2548:           cs.push_back(l);
deba@2548:           l = classes[l].next;
deba@2548:         }
deba@2548: 
deba@2548:         classes[classes[id].right].next = first_class;
deba@2548:         classes[first_class].prev = classes[id].right;
deba@2548:         first_class = classes[id].left;
deba@2548:         
deba@2548:         if (classes[id].next != -1) {
deba@2548:           classes[classes[id].next].prev = classes[id].prev;
deba@2548:         }
deba@2548:         classes[classes[id].prev].next = classes[id].next;
deba@2548:         
deba@2548:         deleteClass(id);
deba@2548:       }
deba@2548: 
deba@2548:       {
deba@2548:         for (int i = 1; i < int(cs.size()); ++i) {
deba@2548:           int l = classes[cs[i]].depth;
deba@2548:           while (nodes[nodes[l].parent].left == l) {
deba@2548:             l = nodes[l].parent;
deba@2548:           }
deba@2548:           int r = l;    
deba@2548:           while (nodes[l].parent >= 0) {
deba@2548:             l = nodes[l].parent;
deba@2548:             int new_node = newNode();
deba@2548: 
deba@2548:             nodes[new_node].prev = -1;
deba@2548:             nodes[new_node].next = -1;
deba@2548: 
deba@2548:             split(r, new_node);
deba@2548:             pushAfter(l, new_node);
deba@2548:             setPrio(l);
deba@2548:             setPrio(new_node);
deba@2548:             r = new_node;
deba@2548:           }
deba@2548:           classes[cs[i]].parent = ~r;
deba@2548:           classes[cs[i]].depth = classes[~(nodes[l].parent)].depth;
deba@2548:           nodes[r].parent = ~cs[i];
deba@2548: 
deba@2548:           nodes[l].next = -1;
deba@2548:           nodes[r].prev = -1;
deba@2548: 
deba@2548:           repairRight(~(nodes[l].parent));
deba@2548:           repairLeft(cs[i]);
deba@2548:           
deba@2548:           *out++ = cs[i];
deba@2548:         }
deba@2548:       }
deba@2548:     }
deba@2548: 
deba@2548:     /// \brief Gives back the priority of the current item.
deba@2548:     ///
deba@2548:     /// \return Gives back the priority of the current item.
deba@2548:     const Value& operator[](const Item& item) const {
deba@2548:       return nodes[index[item]].prio;
deba@2548:     }
deba@2548: 
deba@2548:     /// \brief Sets the priority of the current item.
deba@2548:     ///
deba@2548:     /// Sets the priority of the current item.
deba@2548:     void set(const Item& item, const Value& prio) {
deba@2548:       if (comp(prio, nodes[index[item]].prio)) {
deba@2548:         decrease(item, prio);
deba@2548:       } else if (!comp(prio, nodes[index[item]].prio)) {
deba@2548:         increase(item, prio);
deba@2548:       }
deba@2548:     }
deba@2548:       
deba@2548:     /// \brief Increase the priority of the current item.
deba@2548:     ///
deba@2548:     /// Increase the priority of the current item.
deba@2548:     void increase(const Item& item, const Value& prio) {
deba@2548:       int id = index[item];
deba@2548:       int kd = nodes[id].parent;
deba@2548:       nodes[id].prio = prio;
deba@2548:       while (kd >= 0 && nodes[kd].item == item) {
deba@2548:         setPrio(kd);
deba@2548:         kd = nodes[kd].parent;
deba@2548:       }
deba@2548:     }
deba@2548: 
deba@2548:     /// \brief Increase the priority of the current item.
deba@2548:     ///
deba@2548:     /// Increase the priority of the current item.
deba@2548:     void decrease(const Item& item, const Value& prio) {
deba@2548:       int id = index[item];
deba@2548:       int kd = nodes[id].parent;
deba@2548:       nodes[id].prio = prio;
deba@2548:       while (kd >= 0 && less(id, kd)) {
deba@2548:         nodes[kd].prio = prio;
deba@2548:         nodes[kd].item = item;
deba@2548:         kd = nodes[kd].parent;
deba@2548:       }
deba@2548:     }
deba@2548:     
deba@2548:     /// \brief Gives back the minimum priority of the class.
deba@2548:     ///
deba@2548:     /// \return Gives back the minimum priority of the class.
deba@2548:     const Value& classPrio(int cls) const {
deba@2548:       return nodes[~(classes[cls].parent)].prio;
deba@2548:     }
deba@2548: 
deba@2548:     /// \brief Gives back the minimum priority item of the class.
deba@2548:     ///
deba@2548:     /// \return Gives back the minimum priority item of the class.
deba@2548:     const Item& classTop(int cls) const {
deba@2548:       return nodes[~(classes[cls].parent)].item;
deba@2548:     }
deba@2548: 
deba@2548:     /// \brief Gives back a representant item of the class.
deba@2548:     /// 
deba@2548:     /// The representant is indpendent from the priorities of the
deba@2548:     /// items. 
deba@2548:     /// \return Gives back a representant item of the class.
deba@2548:     const Item& classRep(int id) const {
deba@2548:       int parent = classes[id].parent;
deba@2548:       return nodes[parent >= 0 ? classes[id].depth : leftNode(id)].item;
deba@2548:     }
deba@2548: 
deba@2548:     /// \brief Lemon style iterator for the items of a class.
deba@2548:     ///
deba@2548:     /// ClassIt is a lemon style iterator for the components. It iterates
deba@2548:     /// on the items of a class. By example if you want to iterate on
deba@2548:     /// each items of each classes then you may write the next code.
deba@2548:     ///\code
deba@2548:     /// for (ClassIt cit(huf); cit != INVALID; ++cit) {
deba@2548:     ///   std::cout << "Class: ";
deba@2548:     ///   for (ItemIt iit(huf, cit); iit != INVALID; ++iit) {
deba@2548:     ///     std::cout << toString(iit) << ' ' << std::endl;
deba@2548:     ///   }
deba@2548:     ///   std::cout << std::endl;
deba@2548:     /// }
deba@2548:     ///\endcode
deba@2548:     class ItemIt {
deba@2548:     private:
deba@2548: 
deba@2548:       const HeapUnionFind* _huf;
deba@2548:       int _id, _lid;
deba@2548:       
deba@2548:     public:
deba@2548: 
deba@2548:       /// \brief Default constructor 
deba@2548:       ///
deba@2548:       /// Default constructor 
deba@2548:       ItemIt() {}
deba@2548: 
deba@2548:       ItemIt(const HeapUnionFind& huf, int cls) : _huf(&huf) {
deba@2548:         int id = cls;
deba@2548:         int parent = _huf->classes[id].parent;
deba@2548:         if (parent >= 0) {
deba@2548:           _id = _huf->classes[id].depth;
deba@2548:           if (_huf->classes[id].next != -1) {
deba@2548:             _lid = _huf->classes[_huf->classes[id].next].depth;
deba@2548:           } else {
deba@2548:             _lid = -1;
deba@2548:           }
deba@2548:         } else {
deba@2548:           _id = _huf->leftNode(id);
deba@2548:           _lid = -1;
deba@2548:         } 
deba@2548:       }
deba@2548:       
deba@2548:       /// \brief Increment operator
deba@2548:       ///
deba@2548:       /// It steps to the next item in the class.
deba@2548:       ItemIt& operator++() {
deba@2548:         _id = _huf->nextNode(_id);
deba@2548:         return *this;
deba@2548:       }
deba@2548: 
deba@2548:       /// \brief Conversion operator
deba@2548:       ///
deba@2548:       /// It converts the iterator to the current item.
deba@2548:       operator const Item&() const {
deba@2548:         return _huf->nodes[_id].item;
deba@2548:       }
deba@2548:       
deba@2548:       /// \brief Equality operator
deba@2548:       ///
deba@2548:       /// Equality operator
deba@2548:       bool operator==(const ItemIt& i) { 
deba@2548:         return i._id == _id;
deba@2548:       }
deba@2548: 
deba@2548:       /// \brief Inequality operator
deba@2548:       ///
deba@2548:       /// Inequality operator
deba@2548:       bool operator!=(const ItemIt& i) { 
deba@2548:         return i._id != _id;
deba@2548:       }
deba@2548: 
deba@2548:       /// \brief Equality operator
deba@2548:       ///
deba@2548:       /// Equality operator
deba@2548:       bool operator==(Invalid) { 
deba@2548:         return _id == _lid;
deba@2548:       }
deba@2548: 
deba@2548:       /// \brief Inequality operator
deba@2548:       ///
deba@2548:       /// Inequality operator
deba@2548:       bool operator!=(Invalid) { 
deba@2548:         return _id != _lid;
deba@2548:       }
deba@2548:       
deba@2548:     };
deba@2548: 
deba@2548:     /// \brief Class iterator
deba@2548:     ///
deba@2548:     /// The iterator stores 
deba@2548:     class ClassIt {
deba@2548:     private:
deba@2548: 
deba@2548:       const HeapUnionFind* _huf;
deba@2548:       int _id;
deba@2548: 
deba@2548:     public:
deba@2548: 
deba@2548:       ClassIt(const HeapUnionFind& huf) 
deba@2548:         : _huf(&huf), _id(huf.first_class) {}
deba@2548: 
deba@2548:       ClassIt(const HeapUnionFind& huf, int cls) 
deba@2548:         : _huf(&huf), _id(huf.classes[cls].left) {}
deba@2548: 
deba@2548:       ClassIt(Invalid) : _huf(0), _id(-1) {}
deba@2548:       
deba@2548:       const ClassIt& operator++() {
deba@2548:         _id = _huf->classes[_id].next;
deba@2548: 	return *this;
deba@2548:       }
deba@2548: 
deba@2548:       /// \brief Equality operator
deba@2548:       ///
deba@2548:       /// Equality operator
deba@2548:       bool operator==(const ClassIt& i) { 
deba@2548:         return i._id == _id;
deba@2548:       }
deba@2548: 
deba@2548:       /// \brief Inequality operator
deba@2548:       ///
deba@2548:       /// Inequality operator
deba@2548:       bool operator!=(const ClassIt& i) { 
deba@2548:         return i._id != _id;
deba@2548:       }      
deba@2548:       
deba@2548:       operator int() const {
deba@2548: 	return _id;
deba@2548:       }
deba@2548:             
deba@2548:     };
deba@2548: 
deba@2548:   };
deba@2548: 
beckerjc@483:   //! @}
beckerjc@483: 
alpar@921: } //namespace lemon
beckerjc@483: 
alpar@921: #endif //LEMON_UNION_FIND_H