lemon/unionfind.h
changeset 215 17c644f5f98d
parent 103 b68a7e348e00
child 220 a5d8c039f218
equal deleted inserted replaced
0:a2fb3411c97d 1:fff4cfc1bb80
     1 /* -*- C++ -*-
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     2  *
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library
     3  * This file is a part of LEMON, a generic C++ optimization library.
     4  *
     4  *
     5  * Copyright (C) 2003-2008
     5  * Copyright (C) 2003-2008
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     8  *
    36 
    36 
    37   /// \ingroup auxdat
    37   /// \ingroup auxdat
    38   ///
    38   ///
    39   /// \brief A \e Union-Find data structure implementation
    39   /// \brief A \e Union-Find data structure implementation
    40   ///
    40   ///
    41   /// The class implements the \e Union-Find data structure. 
    41   /// The class implements the \e Union-Find data structure.
    42   /// The union operation uses rank heuristic, while
    42   /// The union operation uses rank heuristic, while
    43   /// the find operation uses path compression.
    43   /// the find operation uses path compression.
    44   /// This is a very simple but efficient implementation, providing 
    44   /// This is a very simple but efficient implementation, providing
    45   /// only four methods: join (union), find, insert and size.
    45   /// only four methods: join (union), find, insert and size.
    46   /// For more features see the \ref UnionFindEnum class.
    46   /// For more features see the \ref UnionFindEnum class.
    47   ///
    47   ///
    48   /// It is primarily used in Kruskal algorithm for finding minimal
    48   /// It is primarily used in Kruskal algorithm for finding minimal
    49   /// cost spanning tree in a graph.
    49   /// cost spanning tree in a graph.
    50   /// \sa kruskal()
    50   /// \sa kruskal()
    51   ///
    51   ///
    52   /// \pre You need to add all the elements by the \ref insert()
    52   /// \pre You need to add all the elements by the \ref insert()
    53   /// method.  
    53   /// method.
    54   template <typename _ItemIntMap>
    54   template <typename _ItemIntMap>
    55   class UnionFind {
    55   class UnionFind {
    56   public:
    56   public:
    57 
    57 
    58     typedef _ItemIntMap ItemIntMap;
    58     typedef _ItemIntMap ItemIntMap;
   109       items.clear();
   109       items.clear();
   110     }
   110     }
   111 
   111 
   112     /// \brief Inserts a new element into the structure.
   112     /// \brief Inserts a new element into the structure.
   113     ///
   113     ///
   114     /// This method inserts a new element into the data structure. 
   114     /// This method inserts a new element into the data structure.
   115     ///
   115     ///
   116     /// The method returns the index of the new component.
   116     /// The method returns the index of the new component.
   117     int insert(const Item& a) {
   117     int insert(const Item& a) {
   118       int n = items.size();
   118       int n = items.size();
   119       items.push_back(-1);
   119       items.push_back(-1);
   121       return n;
   121       return n;
   122     }
   122     }
   123 
   123 
   124     /// \brief Joining the components of element \e a and element \e b.
   124     /// \brief Joining the components of element \e a and element \e b.
   125     ///
   125     ///
   126     /// This is the \e union operation of the Union-Find structure. 
   126     /// This is the \e union operation of the Union-Find structure.
   127     /// Joins the component of element \e a and component of
   127     /// Joins the component of element \e a and component of
   128     /// element \e b. If \e a and \e b are in the same component then
   128     /// element \e b. If \e a and \e b are in the same component then
   129     /// it returns false otherwise it returns true.
   129     /// it returns false otherwise it returns true.
   130     bool join(const Item& a, const Item& b) {
   130     bool join(const Item& a, const Item& b) {
   131       int ka = repIndex(index[a]);
   131       int ka = repIndex(index[a]);
   132       int kb = repIndex(index[b]);
   132       int kb = repIndex(index[b]);
   133 
   133 
   134       if ( ka == kb ) 
   134       if ( ka == kb )
   135 	return false;
   135         return false;
   136 
   136 
   137       if (items[ka] < items[kb]) {
   137       if (items[ka] < items[kb]) {
   138 	items[ka] += items[kb];
   138         items[ka] += items[kb];
   139 	items[kb] = ka;
   139         items[kb] = ka;
   140       } else {
   140       } else {
   141 	items[kb] += items[ka];
   141         items[kb] += items[ka];
   142 	items[ka] = kb;
   142         items[ka] = kb;
   143       }
   143       }
   144       return true;
   144       return true;
   145     }
   145     }
   146 
   146 
   147     /// \brief Returns the size of the component of element \e a.
   147     /// \brief Returns the size of the component of element \e a.
   171   /// method.
   171   /// method.
   172   ///
   172   ///
   173   template <typename _ItemIntMap>
   173   template <typename _ItemIntMap>
   174   class UnionFindEnum {
   174   class UnionFindEnum {
   175   public:
   175   public:
   176     
   176 
   177     typedef _ItemIntMap ItemIntMap;
   177     typedef _ItemIntMap ItemIntMap;
   178     typedef typename ItemIntMap::Key Item;
   178     typedef typename ItemIntMap::Key Item;
   179 
   179 
   180   private:
   180   private:
   181     
   181 
   182     ItemIntMap& index;
   182     ItemIntMap& index;
   183 
   183 
   184     // If the parent stores negative value for an item then that item
   184     // If the parent stores negative value for an item then that item
   185     // is root item and it has ~(items[it].parent) component id.  Else
   185     // is root item and it has ~(items[it].parent) component id.  Else
   186     // the items[it].parent contains the index of the parent.
   186     // the items[it].parent contains the index of the parent.
   200     struct ClassT {
   200     struct ClassT {
   201       int size;
   201       int size;
   202       int firstItem;
   202       int firstItem;
   203       int next, prev;
   203       int next, prev;
   204     };
   204     };
   205     
   205 
   206     std::vector<ClassT> classes;
   206     std::vector<ClassT> classes;
   207     int firstClass, firstFreeClass;
   207     int firstClass, firstFreeClass;
   208 
   208 
   209     int newClass() {
   209     int newClass() {
   210       if (firstFreeClass == -1) {
   210       if (firstFreeClass == -1) {
   211 	int cdx = classes.size();
   211         int cdx = classes.size();
   212 	classes.push_back(ClassT());
   212         classes.push_back(ClassT());
   213 	return cdx;
   213         return cdx;
   214       } else {
   214       } else {
   215 	int cdx = firstFreeClass;
   215         int cdx = firstFreeClass;
   216 	firstFreeClass = classes[firstFreeClass].next;
   216         firstFreeClass = classes[firstFreeClass].next;
   217 	return cdx;
   217         return cdx;
   218       }
   218       }
   219     }
   219     }
   220 
   220 
   221     int newItem() {
   221     int newItem() {
   222       if (firstFreeItem == -1) {
   222       if (firstFreeItem == -1) {
   223 	int idx = items.size();
   223         int idx = items.size();
   224 	items.push_back(ItemT());
   224         items.push_back(ItemT());
   225 	return idx;
   225         return idx;
   226       } else {
   226       } else {
   227 	int idx = firstFreeItem;
   227         int idx = firstFreeItem;
   228 	firstFreeItem = items[firstFreeItem].next;
   228         firstFreeItem = items[firstFreeItem].next;
   229 	return idx;
   229         return idx;
   230       }
   230       }
   231     }
   231     }
   232 
   232 
   233 
   233 
   234     bool rep(int idx) const {
   234     bool rep(int idx) const {
   265     }
   265     }
   266 
   266 
   267     void unlaceItem(int idx) {
   267     void unlaceItem(int idx) {
   268       items[items[idx].prev].next = items[idx].next;
   268       items[items[idx].prev].next = items[idx].next;
   269       items[items[idx].next].prev = items[idx].prev;
   269       items[items[idx].next].prev = items[idx].prev;
   270       
   270 
   271       items[idx].next = firstFreeItem;
   271       items[idx].next = firstFreeItem;
   272       firstFreeItem = idx;
   272       firstFreeItem = idx;
   273     }
   273     }
   274 
   274 
   275     void spliceItems(int ak, int bk) {
   275     void spliceItems(int ak, int bk) {
   276       items[items[ak].prev].next = bk;
   276       items[items[ak].prev].next = bk;
   277       items[items[bk].prev].next = ak;
   277       items[items[bk].prev].next = ak;
   278       int tmp = items[ak].prev;
   278       int tmp = items[ak].prev;
   279       items[ak].prev = items[bk].prev;
   279       items[ak].prev = items[bk].prev;
   280       items[bk].prev = tmp;
   280       items[bk].prev = tmp;
   281         
   281 
   282     }
   282     }
   283 
   283 
   284     void laceClass(int cls) {
   284     void laceClass(int cls) {
   285       if (firstClass != -1) {
   285       if (firstClass != -1) {
   286         classes[firstClass].prev = cls;
   286         classes[firstClass].prev = cls;
   287       }
   287       }
   288       classes[cls].next = firstClass;
   288       classes[cls].next = firstClass;
   289       classes[cls].prev = -1;
   289       classes[cls].prev = -1;
   290       firstClass = cls;
   290       firstClass = cls;
   291     } 
   291     }
   292 
   292 
   293     void unlaceClass(int cls) {
   293     void unlaceClass(int cls) {
   294       if (classes[cls].prev != -1) {
   294       if (classes[cls].prev != -1) {
   295         classes[classes[cls].prev].next = classes[cls].next;
   295         classes[classes[cls].prev].next = classes[cls].next;
   296       } else {
   296       } else {
   297         firstClass = classes[cls].next;
   297         firstClass = classes[cls].next;
   298       }
   298       }
   299       if (classes[cls].next != -1) {
   299       if (classes[cls].next != -1) {
   300         classes[classes[cls].next].prev = classes[cls].prev;
   300         classes[classes[cls].next].prev = classes[cls].prev;
   301       }
   301       }
   302       
   302 
   303       classes[cls].next = firstFreeClass;
   303       classes[cls].next = firstFreeClass;
   304       firstFreeClass = cls;
   304       firstFreeClass = cls;
   305     } 
   305     }
   306 
   306 
   307   public:
   307   public:
   308 
   308 
   309     UnionFindEnum(ItemIntMap& _index) 
   309     UnionFindEnum(ItemIntMap& _index)
   310       : index(_index), items(), firstFreeItem(-1), 
   310       : index(_index), items(), firstFreeItem(-1),
   311 	firstClass(-1), firstFreeClass(-1) {}
   311         firstClass(-1), firstFreeClass(-1) {}
   312     
   312 
   313     /// \brief Inserts the given element into a new component.
   313     /// \brief Inserts the given element into a new component.
   314     ///
   314     ///
   315     /// This method creates a new component consisting only of the
   315     /// This method creates a new component consisting only of the
   316     /// given element.
   316     /// given element.
   317     ///
   317     ///
   330       laceClass(cdx);
   330       laceClass(cdx);
   331       classes[cdx].size = 1;
   331       classes[cdx].size = 1;
   332       classes[cdx].firstItem = idx;
   332       classes[cdx].firstItem = idx;
   333 
   333 
   334       firstClass = cdx;
   334       firstClass = cdx;
   335       
   335 
   336       return cdx;
   336       return cdx;
   337     }
   337     }
   338 
   338 
   339     /// \brief Inserts the given element into the component of the others.
   339     /// \brief Inserts the given element into the component of the others.
   340     ///
   340     ///
   341     /// This methods inserts the element \e a into the component of the
   341     /// This methods inserts the element \e a into the component of the
   342     /// element \e comp. 
   342     /// element \e comp.
   343     void insert(const Item& item, int cls) {
   343     void insert(const Item& item, int cls) {
   344       int rdx = classes[cls].firstItem;
   344       int rdx = classes[cls].firstItem;
   345       int idx = newItem();
   345       int idx = newItem();
   346 
   346 
   347       index.set(item, idx);
   347       index.set(item, idx);
   370       return ~(items[repIndex(index[item])].parent);
   370       return ~(items[repIndex(index[item])].parent);
   371     }
   371     }
   372 
   372 
   373     /// \brief Joining the component of element \e a and element \e b.
   373     /// \brief Joining the component of element \e a and element \e b.
   374     ///
   374     ///
   375     /// This is the \e union operation of the Union-Find structure. 
   375     /// This is the \e union operation of the Union-Find structure.
   376     /// Joins the component of element \e a and component of
   376     /// Joins the component of element \e a and component of
   377     /// element \e b. If \e a and \e b are in the same component then
   377     /// element \e b. If \e a and \e b are in the same component then
   378     /// returns -1 else returns the remaining class.
   378     /// returns -1 else returns the remaining class.
   379     int join(const Item& a, const Item& b) {
   379     int join(const Item& a, const Item& b) {
   380 
   380 
   381       int ak = repIndex(index[a]);
   381       int ak = repIndex(index[a]);
   382       int bk = repIndex(index[b]);
   382       int bk = repIndex(index[b]);
   383 
   383 
   384       if (ak == bk) {
   384       if (ak == bk) {
   385 	return -1;
   385         return -1;
   386       }
   386       }
   387 
   387 
   388       int acx = ~(items[ak].parent);
   388       int acx = ~(items[ak].parent);
   389       int bcx = ~(items[bk].parent);
   389       int bcx = ~(items[bk].parent);
   390 
   390 
   391       int rcx;
   391       int rcx;
   392 
   392 
   393       if (classes[acx].size > classes[bcx].size) {
   393       if (classes[acx].size > classes[bcx].size) {
   394 	classes[acx].size += classes[bcx].size;
   394         classes[acx].size += classes[bcx].size;
   395 	items[bk].parent = ak;
   395         items[bk].parent = ak;
   396         unlaceClass(bcx);
   396         unlaceClass(bcx);
   397 	rcx = acx;
   397         rcx = acx;
   398       } else {
   398       } else {
   399 	classes[bcx].size += classes[acx].size;
   399         classes[bcx].size += classes[acx].size;
   400 	items[ak].parent = bk;
   400         items[ak].parent = bk;
   401         unlaceClass(acx);
   401         unlaceClass(acx);
   402 	rcx = bcx;
   402         rcx = bcx;
   403       }
   403       }
   404       spliceItems(ak, bk);
   404       spliceItems(ak, bk);
   405 
   405 
   406       return rcx;
   406       return rcx;
   407     }
   407     }
   411     /// Returns the size of the class.
   411     /// Returns the size of the class.
   412     int size(int cls) const {
   412     int size(int cls) const {
   413       return classes[cls].size;
   413       return classes[cls].size;
   414     }
   414     }
   415 
   415 
   416     /// \brief Splits up the component. 
   416     /// \brief Splits up the component.
   417     ///
   417     ///
   418     /// Splitting the component into singleton components (component
   418     /// Splitting the component into singleton components (component
   419     /// of size one).
   419     /// of size one).
   420     void split(int cls) {
   420     void split(int cls) {
   421       int fdx = classes[cls].firstItem;
   421       int fdx = classes[cls].firstItem;
   422       int idx = items[fdx].next;
   422       int idx = items[fdx].next;
   423       while (idx != fdx) {
   423       while (idx != fdx) {
   424         int next = items[idx].next;
   424         int next = items[idx].next;
   425 
   425 
   426 	singletonItem(idx);
   426         singletonItem(idx);
   427 
   427 
   428 	int cdx = newClass();        
   428         int cdx = newClass();
   429         items[idx].parent = ~cdx;
   429         items[idx].parent = ~cdx;
   430 
   430 
   431 	laceClass(cdx);
   431         laceClass(cdx);
   432 	classes[cdx].size = 1;
   432         classes[cdx].size = 1;
   433 	classes[cdx].firstItem = idx;
   433         classes[cdx].firstItem = idx;
   434         
   434 
   435         idx = next;
   435         idx = next;
   436       }
   436       }
   437 
   437 
   438       items[idx].prev = idx;
   438       items[idx].prev = idx;
   439       items[idx].next = idx;
   439       items[idx].next = idx;
   440 
   440 
   441       classes[~(items[idx].parent)].size = 1;
   441       classes[~(items[idx].parent)].size = 1;
   442       
   442 
   443     }
   443     }
   444 
   444 
   445     /// \brief Removes the given element from the structure.
   445     /// \brief Removes the given element from the structure.
   446     ///
   446     ///
   447     /// Removes the element from its component and if the component becomes
   447     /// Removes the element from its component and if the component becomes
   455       int idx = index[item];
   455       int idx = index[item];
   456       int fdx = items[idx].next;
   456       int fdx = items[idx].next;
   457 
   457 
   458       int cdx = classIndex(idx);
   458       int cdx = classIndex(idx);
   459       if (idx == fdx) {
   459       if (idx == fdx) {
   460 	unlaceClass(cdx);
   460         unlaceClass(cdx);
   461 	items[idx].next = firstFreeItem;
   461         items[idx].next = firstFreeItem;
   462 	firstFreeItem = idx;
   462         firstFreeItem = idx;
   463 	return;
   463         return;
   464       } else {
   464       } else {
   465 	classes[cdx].firstItem = fdx;
   465         classes[cdx].firstItem = fdx;
   466 	--classes[cdx].size;
   466         --classes[cdx].size;
   467 	items[fdx].parent = ~cdx;
   467         items[fdx].parent = ~cdx;
   468 
   468 
   469 	unlaceItem(idx);
   469         unlaceItem(idx);
   470 	idx = items[fdx].next;
   470         idx = items[fdx].next;
   471 	while (idx != fdx) {
   471         while (idx != fdx) {
   472 	  items[idx].parent = fdx;
   472           items[idx].parent = fdx;
   473 	  idx = items[idx].next;
   473           idx = items[idx].next;
   474 	}
   474         }
   475           
   475 
   476       }
   476       }
   477 
   477 
   478     }
   478     }
   479 
   479 
   480     /// \brief Gives back a representant item of the component.
   480     /// \brief Gives back a representant item of the component.
   512 
   512 
   513       /// \brief Constructor to get invalid iterator
   513       /// \brief Constructor to get invalid iterator
   514       ///
   514       ///
   515       /// Constructor to get invalid iterator
   515       /// Constructor to get invalid iterator
   516       ClassIt(Invalid) : unionFind(0), cdx(-1) {}
   516       ClassIt(Invalid) : unionFind(0), cdx(-1) {}
   517       
   517 
   518       /// \brief Increment operator
   518       /// \brief Increment operator
   519       ///
   519       ///
   520       /// It steps to the next representant item.
   520       /// It steps to the next representant item.
   521       ClassIt& operator++() {
   521       ClassIt& operator++() {
   522         cdx = unionFind->classes[cdx].next;
   522         cdx = unionFind->classes[cdx].next;
   523         return *this;
   523         return *this;
   524       }
   524       }
   525       
   525 
   526       /// \brief Conversion operator
   526       /// \brief Conversion operator
   527       ///
   527       ///
   528       /// It converts the iterator to the current representant item.
   528       /// It converts the iterator to the current representant item.
   529       operator int() const {
   529       operator int() const {
   530         return cdx;
   530         return cdx;
   531       }
   531       }
   532 
   532 
   533       /// \brief Equality operator
   533       /// \brief Equality operator
   534       ///
   534       ///
   535       /// Equality operator
   535       /// Equality operator
   536       bool operator==(const ClassIt& i) { 
   536       bool operator==(const ClassIt& i) {
   537         return i.cdx == cdx;
   537         return i.cdx == cdx;
   538       }
   538       }
   539 
   539 
   540       /// \brief Inequality operator
   540       /// \brief Inequality operator
   541       ///
   541       ///
   542       /// Inequality operator
   542       /// Inequality operator
   543       bool operator!=(const ClassIt& i) { 
   543       bool operator!=(const ClassIt& i) {
   544         return i.cdx != cdx;
   544         return i.cdx != cdx;
   545       }
   545       }
   546       
   546 
   547     private:
   547     private:
   548       const UnionFindEnum* unionFind;
   548       const UnionFindEnum* unionFind;
   549       int cdx;
   549       int cdx;
   550     };
   550     };
   551 
   551 
   575 
   575 
   576       /// \brief Constructor to get invalid iterator
   576       /// \brief Constructor to get invalid iterator
   577       ///
   577       ///
   578       /// Constructor to get invalid iterator
   578       /// Constructor to get invalid iterator
   579       ItemIt(Invalid) : unionFind(0), idx(-1) {}
   579       ItemIt(Invalid) : unionFind(0), idx(-1) {}
   580       
   580 
   581       /// \brief Increment operator
   581       /// \brief Increment operator
   582       ///
   582       ///
   583       /// It steps to the next item in the class.
   583       /// It steps to the next item in the class.
   584       ItemIt& operator++() {
   584       ItemIt& operator++() {
   585         idx = unionFind->items[idx].next;
   585         idx = unionFind->items[idx].next;
   586         if (idx == fdx) idx = -1;
   586         if (idx == fdx) idx = -1;
   587         return *this;
   587         return *this;
   588       }
   588       }
   589       
   589 
   590       /// \brief Conversion operator
   590       /// \brief Conversion operator
   591       ///
   591       ///
   592       /// It converts the iterator to the current item.
   592       /// It converts the iterator to the current item.
   593       operator const Item&() const {
   593       operator const Item&() const {
   594         return unionFind->items[idx].item;
   594         return unionFind->items[idx].item;
   595       }
   595       }
   596 
   596 
   597       /// \brief Equality operator
   597       /// \brief Equality operator
   598       ///
   598       ///
   599       /// Equality operator
   599       /// Equality operator
   600       bool operator==(const ItemIt& i) { 
   600       bool operator==(const ItemIt& i) {
   601         return i.idx == idx;
   601         return i.idx == idx;
   602       }
   602       }
   603 
   603 
   604       /// \brief Inequality operator
   604       /// \brief Inequality operator
   605       ///
   605       ///
   606       /// Inequality operator
   606       /// Inequality operator
   607       bool operator!=(const ItemIt& i) { 
   607       bool operator!=(const ItemIt& i) {
   608         return i.idx != idx;
   608         return i.idx != idx;
   609       }
   609       }
   610       
   610 
   611     private:
   611     private:
   612       const UnionFindEnum* unionFind;
   612       const UnionFindEnum* unionFind;
   613       int idx, fdx;
   613       int idx, fdx;
   614     };
   614     };
   615 
   615 
   628   /// \pre You need to add all the elements by the \ref insert()
   628   /// \pre You need to add all the elements by the \ref insert()
   629   /// method.
   629   /// method.
   630   template <typename _ItemIntMap>
   630   template <typename _ItemIntMap>
   631   class ExtendFindEnum {
   631   class ExtendFindEnum {
   632   public:
   632   public:
   633     
   633 
   634     typedef _ItemIntMap ItemIntMap;
   634     typedef _ItemIntMap ItemIntMap;
   635     typedef typename ItemIntMap::Key Item;
   635     typedef typename ItemIntMap::Key Item;
   636 
   636 
   637   private:
   637   private:
   638     
   638 
   639     ItemIntMap& index;
   639     ItemIntMap& index;
   640 
   640 
   641     struct ItemT {
   641     struct ItemT {
   642       int cls;
   642       int cls;
   643       Item item;
   643       Item item;
   656 
   656 
   657     int firstClass, firstFreeClass;
   657     int firstClass, firstFreeClass;
   658 
   658 
   659     int newClass() {
   659     int newClass() {
   660       if (firstFreeClass != -1) {
   660       if (firstFreeClass != -1) {
   661 	int cdx = firstFreeClass;
   661         int cdx = firstFreeClass;
   662 	firstFreeClass = classes[cdx].next;
   662         firstFreeClass = classes[cdx].next;
   663 	return cdx;
   663         return cdx;
   664       } else {
   664       } else {
   665 	classes.push_back(ClassT());
   665         classes.push_back(ClassT());
   666 	return classes.size() - 1;
   666         return classes.size() - 1;
   667       }
   667       }
   668     }
   668     }
   669 
   669 
   670     int newItem() {
   670     int newItem() {
   671       if (firstFreeItem != -1) {
   671       if (firstFreeItem != -1) {
   672 	int idx = firstFreeItem;
   672         int idx = firstFreeItem;
   673 	firstFreeItem = items[idx].next;
   673         firstFreeItem = items[idx].next;
   674 	return idx;
   674         return idx;
   675       } else {
   675       } else {
   676 	items.push_back(ItemT());
   676         items.push_back(ItemT());
   677 	return items.size() - 1;
   677         return items.size() - 1;
   678       }
   678       }
   679     }
   679     }
   680 
   680 
   681   public:
   681   public:
   682 
   682 
   683     /// \brief Constructor
   683     /// \brief Constructor
   684     ExtendFindEnum(ItemIntMap& _index) 
   684     ExtendFindEnum(ItemIntMap& _index)
   685       : index(_index), items(), firstFreeItem(-1), 
   685       : index(_index), items(), firstFreeItem(-1),
   686 	classes(), firstClass(-1), firstFreeClass(-1) {}
   686         classes(), firstClass(-1), firstFreeClass(-1) {}
   687     
   687 
   688     /// \brief Inserts the given element into a new component.
   688     /// \brief Inserts the given element into a new component.
   689     ///
   689     ///
   690     /// This method creates a new component consisting only of the
   690     /// This method creates a new component consisting only of the
   691     /// given element.
   691     /// given element.
   692     int insert(const Item& item) {
   692     int insert(const Item& item) {
   693       int cdx = newClass();
   693       int cdx = newClass();
   694       classes[cdx].prev = -1;
   694       classes[cdx].prev = -1;
   695       classes[cdx].next = firstClass;
   695       classes[cdx].next = firstClass;
   696       if (firstClass != -1) {
   696       if (firstClass != -1) {
   697 	classes[firstClass].prev = cdx;
   697         classes[firstClass].prev = cdx;
   698       }
   698       }
   699       firstClass = cdx;
   699       firstClass = cdx;
   700       
   700 
   701       int idx = newItem();
   701       int idx = newItem();
   702       items[idx].item = item;
   702       items[idx].item = item;
   703       items[idx].cls = cdx;
   703       items[idx].cls = cdx;
   704       items[idx].prev = idx;
   704       items[idx].prev = idx;
   705       items[idx].next = idx;
   705       items[idx].next = idx;
   706 
   706 
   707       classes[cdx].firstItem = idx;
   707       classes[cdx].firstItem = idx;
   708 
   708 
   709       index.set(item, idx);
   709       index.set(item, idx);
   710       
   710 
   711       return cdx;
   711       return cdx;
   712     }
   712     }
   713 
   713 
   714     /// \brief Inserts the given element into the given component.
   714     /// \brief Inserts the given element into the given component.
   715     ///
   715     ///
   748     ///
   748     ///
   749     /// Gives back a representant item of the component.
   749     /// Gives back a representant item of the component.
   750     Item item(int cls) const {
   750     Item item(int cls) const {
   751       return items[classes[cls].firstItem].item;
   751       return items[classes[cls].firstItem].item;
   752     }
   752     }
   753     
   753 
   754     /// \brief Removes the given element from the structure.
   754     /// \brief Removes the given element from the structure.
   755     ///
   755     ///
   756     /// Removes the element from its component and if the component becomes
   756     /// Removes the element from its component and if the component becomes
   757     /// empty then removes that component from the component list.
   757     /// empty then removes that component from the component list.
   758     ///
   758     ///
   759     /// \warning It is an error to remove an element which is not in
   759     /// \warning It is an error to remove an element which is not in
   760     /// the structure.
   760     /// the structure.
   761     void erase(const Item &item) {
   761     void erase(const Item &item) {
   762       int idx = index[item];
   762       int idx = index[item];
   763       int cdx = items[idx].cls;
   763       int cdx = items[idx].cls;
   764       
   764 
   765       if (idx == items[idx].next) {
   765       if (idx == items[idx].next) {
   766 	if (classes[cdx].prev != -1) {
   766         if (classes[cdx].prev != -1) {
   767 	  classes[classes[cdx].prev].next = classes[cdx].next; 
   767           classes[classes[cdx].prev].next = classes[cdx].next;
   768 	} else {
   768         } else {
   769 	  firstClass = classes[cdx].next;
   769           firstClass = classes[cdx].next;
   770 	}
   770         }
   771 	if (classes[cdx].next != -1) {
   771         if (classes[cdx].next != -1) {
   772 	  classes[classes[cdx].next].prev = classes[cdx].prev; 
   772           classes[classes[cdx].next].prev = classes[cdx].prev;
   773 	}
   773         }
   774 	classes[cdx].next = firstFreeClass;
   774         classes[cdx].next = firstFreeClass;
   775 	firstFreeClass = cdx;
   775         firstFreeClass = cdx;
   776       } else {
   776       } else {
   777 	classes[cdx].firstItem = items[idx].next;
   777         classes[cdx].firstItem = items[idx].next;
   778 	items[items[idx].next].prev = items[idx].prev;
   778         items[items[idx].next].prev = items[idx].prev;
   779 	items[items[idx].prev].next = items[idx].next;
   779         items[items[idx].prev].next = items[idx].next;
   780       }
   780       }
   781       items[idx].next = firstFreeItem;
   781       items[idx].next = firstFreeItem;
   782       firstFreeItem = idx;
   782       firstFreeItem = idx;
   783 	
   783 
   784     }    
   784     }
   785 
   785 
   786     
   786 
   787     /// \brief Removes the component of the given element from the structure.
   787     /// \brief Removes the component of the given element from the structure.
   788     ///
   788     ///
   789     /// Removes the component of the given element from the structure.
   789     /// Removes the component of the given element from the structure.
   790     ///
   790     ///
   791     /// \warning It is an error to give an element which is not in the
   791     /// \warning It is an error to give an element which is not in the
   794       int idx = classes[cdx].firstItem;
   794       int idx = classes[cdx].firstItem;
   795       items[items[idx].prev].next = firstFreeItem;
   795       items[items[idx].prev].next = firstFreeItem;
   796       firstFreeItem = idx;
   796       firstFreeItem = idx;
   797 
   797 
   798       if (classes[cdx].prev != -1) {
   798       if (classes[cdx].prev != -1) {
   799 	classes[classes[cdx].prev].next = classes[cdx].next; 
   799         classes[classes[cdx].prev].next = classes[cdx].next;
   800       } else {
   800       } else {
   801 	firstClass = classes[cdx].next;
   801         firstClass = classes[cdx].next;
   802       }
   802       }
   803       if (classes[cdx].next != -1) {
   803       if (classes[cdx].next != -1) {
   804 	classes[classes[cdx].next].prev = classes[cdx].prev; 
   804         classes[classes[cdx].next].prev = classes[cdx].prev;
   805       }
   805       }
   806       classes[cdx].next = firstFreeClass;
   806       classes[cdx].next = firstFreeClass;
   807       firstFreeClass = cdx;
   807       firstFreeClass = cdx;
   808     }
   808     }
   809 
   809 
   822 
   822 
   823       /// \brief Constructor to get invalid iterator
   823       /// \brief Constructor to get invalid iterator
   824       ///
   824       ///
   825       /// Constructor to get invalid iterator
   825       /// Constructor to get invalid iterator
   826       ClassIt(Invalid) : extendFind(0), cdx(-1) {}
   826       ClassIt(Invalid) : extendFind(0), cdx(-1) {}
   827       
   827 
   828       /// \brief Increment operator
   828       /// \brief Increment operator
   829       ///
   829       ///
   830       /// It steps to the next representant item.
   830       /// It steps to the next representant item.
   831       ClassIt& operator++() {
   831       ClassIt& operator++() {
   832         cdx = extendFind->classes[cdx].next;
   832         cdx = extendFind->classes[cdx].next;
   833         return *this;
   833         return *this;
   834       }
   834       }
   835       
   835 
   836       /// \brief Conversion operator
   836       /// \brief Conversion operator
   837       ///
   837       ///
   838       /// It converts the iterator to the current class id.
   838       /// It converts the iterator to the current class id.
   839       operator int() const {
   839       operator int() const {
   840         return cdx;
   840         return cdx;
   841       }
   841       }
   842 
   842 
   843       /// \brief Equality operator
   843       /// \brief Equality operator
   844       ///
   844       ///
   845       /// Equality operator
   845       /// Equality operator
   846       bool operator==(const ClassIt& i) { 
   846       bool operator==(const ClassIt& i) {
   847         return i.cdx == cdx;
   847         return i.cdx == cdx;
   848       }
   848       }
   849 
   849 
   850       /// \brief Inequality operator
   850       /// \brief Inequality operator
   851       ///
   851       ///
   852       /// Inequality operator
   852       /// Inequality operator
   853       bool operator!=(const ClassIt& i) { 
   853       bool operator!=(const ClassIt& i) {
   854         return i.cdx != cdx;
   854         return i.cdx != cdx;
   855       }
   855       }
   856       
   856 
   857     private:
   857     private:
   858       const ExtendFindEnum* extendFind;
   858       const ExtendFindEnum* extendFind;
   859       int cdx;
   859       int cdx;
   860     };
   860     };
   861 
   861 
   885 
   885 
   886       /// \brief Constructor to get invalid iterator
   886       /// \brief Constructor to get invalid iterator
   887       ///
   887       ///
   888       /// Constructor to get invalid iterator
   888       /// Constructor to get invalid iterator
   889       ItemIt(Invalid) : extendFind(0), idx(-1) {}
   889       ItemIt(Invalid) : extendFind(0), idx(-1) {}
   890       
   890 
   891       /// \brief Increment operator
   891       /// \brief Increment operator
   892       ///
   892       ///
   893       /// It steps to the next item in the class.
   893       /// It steps to the next item in the class.
   894       ItemIt& operator++() {
   894       ItemIt& operator++() {
   895         idx = extendFind->items[idx].next;
   895         idx = extendFind->items[idx].next;
   896 	if (fdx == idx) idx = -1;
   896         if (fdx == idx) idx = -1;
   897         return *this;
   897         return *this;
   898       }
   898       }
   899       
   899 
   900       /// \brief Conversion operator
   900       /// \brief Conversion operator
   901       ///
   901       ///
   902       /// It converts the iterator to the current item.
   902       /// It converts the iterator to the current item.
   903       operator const Item&() const {
   903       operator const Item&() const {
   904         return extendFind->items[idx].item;
   904         return extendFind->items[idx].item;
   905       }
   905       }
   906 
   906 
   907       /// \brief Equality operator
   907       /// \brief Equality operator
   908       ///
   908       ///
   909       /// Equality operator
   909       /// Equality operator
   910       bool operator==(const ItemIt& i) { 
   910       bool operator==(const ItemIt& i) {
   911         return i.idx == idx;
   911         return i.idx == idx;
   912       }
   912       }
   913 
   913 
   914       /// \brief Inequality operator
   914       /// \brief Inequality operator
   915       ///
   915       ///
   916       /// Inequality operator
   916       /// Inequality operator
   917       bool operator!=(const ItemIt& i) { 
   917       bool operator!=(const ItemIt& i) {
   918         return i.idx != idx;
   918         return i.idx != idx;
   919       }
   919       }
   920       
   920 
   921     private:
   921     private:
   922       const ExtendFindEnum* extendFind;
   922       const ExtendFindEnum* extendFind;
   923       int idx, fdx;
   923       int idx, fdx;
   924     };
   924     };
   925 
   925 
   947   /// after the split.
   947   /// after the split.
   948   ///
   948   ///
   949   /// \pre You need to add all the elements by the \ref insert()
   949   /// \pre You need to add all the elements by the \ref insert()
   950   /// method.
   950   /// method.
   951   ///
   951   ///
   952   template <typename _Value, typename _ItemIntMap, 
   952   template <typename _Value, typename _ItemIntMap,
   953             typename _Comp = std::less<_Value> >
   953             typename _Comp = std::less<_Value> >
   954   class HeapUnionFind {
   954   class HeapUnionFind {
   955   public:
   955   public:
   956     
   956 
   957     typedef _Value Value;
   957     typedef _Value Value;
   958     typedef typename _ItemIntMap::Key Item;
   958     typedef typename _ItemIntMap::Key Item;
   959 
   959 
   960     typedef _ItemIntMap ItemIntMap;
   960     typedef _ItemIntMap ItemIntMap;
   961 
   961 
  1052       if (id < 0) {
  1052       if (id < 0) {
  1053         return -1;
  1053         return -1;
  1054       }
  1054       }
  1055       id = nodes[id].next;
  1055       id = nodes[id].next;
  1056       while (depth--) {
  1056       while (depth--) {
  1057         id = nodes[id].left;      
  1057         id = nodes[id].left;
  1058       }
  1058       }
  1059       return id;
  1059       return id;
  1060     }
  1060     }
  1061 
  1061 
  1062 
  1062 
  1130 
  1130 
  1131     void split(int id, int jd) {
  1131     void split(int id, int jd) {
  1132       int kd = nodes[id].parent;
  1132       int kd = nodes[id].parent;
  1133       nodes[kd].right = nodes[id].prev;
  1133       nodes[kd].right = nodes[id].prev;
  1134       nodes[nodes[id].prev].next = -1;
  1134       nodes[nodes[id].prev].next = -1;
  1135       
  1135 
  1136       nodes[jd].left = id;
  1136       nodes[jd].left = id;
  1137       nodes[id].prev = -1;
  1137       nodes[id].prev = -1;
  1138       int num = 0;
  1138       int num = 0;
  1139       while (id != -1) {
  1139       while (id != -1) {
  1140         nodes[id].parent = jd;
  1140         nodes[id].parent = jd;
  1141         nodes[jd].right = id;
  1141         nodes[jd].right = id;
  1142         id = nodes[id].next;
  1142         id = nodes[id].next;
  1143         ++num;
  1143         ++num;
  1144       }      
  1144       }
  1145       nodes[kd].size -= num;
  1145       nodes[kd].size -= num;
  1146       nodes[jd].size = num;
  1146       nodes[jd].size = num;
  1147     }
  1147     }
  1148 
  1148 
  1149     void pushLeft(int id, int jd) {
  1149     void pushLeft(int id, int jd) {
  1163     }
  1163     }
  1164 
  1164 
  1165     void repairLeft(int id) {
  1165     void repairLeft(int id) {
  1166       int jd = ~(classes[id].parent);
  1166       int jd = ~(classes[id].parent);
  1167       while (nodes[jd].left != -1) {
  1167       while (nodes[jd].left != -1) {
  1168 	int kd = nodes[jd].left;
  1168         int kd = nodes[jd].left;
  1169 	if (nodes[jd].size == 1) {
  1169         if (nodes[jd].size == 1) {
  1170 	  if (nodes[jd].parent < 0) {
  1170           if (nodes[jd].parent < 0) {
  1171 	    classes[id].parent = ~kd;
  1171             classes[id].parent = ~kd;
  1172 	    classes[id].depth -= 1;
  1172             classes[id].depth -= 1;
  1173 	    nodes[kd].parent = ~id;
  1173             nodes[kd].parent = ~id;
  1174 	    deleteNode(jd);
  1174             deleteNode(jd);
  1175 	    jd = kd;
  1175             jd = kd;
  1176 	  } else {
  1176           } else {
  1177 	    int pd = nodes[jd].parent;
  1177             int pd = nodes[jd].parent;
  1178 	    if (nodes[nodes[jd].next].size < cmax) {
  1178             if (nodes[nodes[jd].next].size < cmax) {
  1179 	      pushLeft(nodes[jd].next, nodes[jd].left);
  1179               pushLeft(nodes[jd].next, nodes[jd].left);
  1180 	      if (less(nodes[jd].left, nodes[jd].next)) {
  1180               if (less(nodes[jd].left, nodes[jd].next)) {
  1181 		nodes[nodes[jd].next].prio = nodes[nodes[jd].left].prio;
  1181                 nodes[nodes[jd].next].prio = nodes[nodes[jd].left].prio;
  1182 		nodes[nodes[jd].next].item = nodes[nodes[jd].left].item;
  1182                 nodes[nodes[jd].next].item = nodes[nodes[jd].left].item;
  1183 	      } 
  1183               }
  1184 	      popLeft(pd);
  1184               popLeft(pd);
  1185 	      deleteNode(jd);
  1185               deleteNode(jd);
  1186 	      jd = pd;
  1186               jd = pd;
  1187 	    } else {
  1187             } else {
  1188 	      int ld = nodes[nodes[jd].next].left;
  1188               int ld = nodes[nodes[jd].next].left;
  1189 	      popLeft(nodes[jd].next);
  1189               popLeft(nodes[jd].next);
  1190 	      pushRight(jd, ld);
  1190               pushRight(jd, ld);
  1191 	      if (less(ld, nodes[jd].left)) {
  1191               if (less(ld, nodes[jd].left)) {
  1192 		nodes[jd].item = nodes[ld].item;
  1192                 nodes[jd].item = nodes[ld].item;
  1193 		nodes[jd].prio = nodes[jd].prio;
  1193                 nodes[jd].prio = nodes[jd].prio;
  1194 	      }
  1194               }
  1195 	      if (nodes[nodes[jd].next].item == nodes[ld].item) {
  1195               if (nodes[nodes[jd].next].item == nodes[ld].item) {
  1196 		setPrio(nodes[jd].next);
  1196                 setPrio(nodes[jd].next);
  1197 	      }
  1197               }
  1198 	      jd = nodes[jd].left;
  1198               jd = nodes[jd].left;
  1199 	    }
  1199             }
  1200 	  }
  1200           }
  1201 	} else {
  1201         } else {
  1202 	  jd = nodes[jd].left;
  1202           jd = nodes[jd].left;
  1203 	}
  1203         }
  1204       }
  1204       }
  1205     }    
  1205     }
  1206 
  1206 
  1207     void repairRight(int id) {
  1207     void repairRight(int id) {
  1208       int jd = ~(classes[id].parent);
  1208       int jd = ~(classes[id].parent);
  1209       while (nodes[jd].right != -1) {
  1209       while (nodes[jd].right != -1) {
  1210 	int kd = nodes[jd].right;
  1210         int kd = nodes[jd].right;
  1211 	if (nodes[jd].size == 1) {
  1211         if (nodes[jd].size == 1) {
  1212 	  if (nodes[jd].parent < 0) {
  1212           if (nodes[jd].parent < 0) {
  1213 	    classes[id].parent = ~kd;
  1213             classes[id].parent = ~kd;
  1214 	    classes[id].depth -= 1;
  1214             classes[id].depth -= 1;
  1215 	    nodes[kd].parent = ~id;
  1215             nodes[kd].parent = ~id;
  1216 	    deleteNode(jd);
  1216             deleteNode(jd);
  1217 	    jd = kd;
  1217             jd = kd;
  1218 	  } else {
  1218           } else {
  1219 	    int pd = nodes[jd].parent;
  1219             int pd = nodes[jd].parent;
  1220 	    if (nodes[nodes[jd].prev].size < cmax) {
  1220             if (nodes[nodes[jd].prev].size < cmax) {
  1221 	      pushRight(nodes[jd].prev, nodes[jd].right);
  1221               pushRight(nodes[jd].prev, nodes[jd].right);
  1222 	      if (less(nodes[jd].right, nodes[jd].prev)) {
  1222               if (less(nodes[jd].right, nodes[jd].prev)) {
  1223 		nodes[nodes[jd].prev].prio = nodes[nodes[jd].right].prio;
  1223                 nodes[nodes[jd].prev].prio = nodes[nodes[jd].right].prio;
  1224 		nodes[nodes[jd].prev].item = nodes[nodes[jd].right].item;
  1224                 nodes[nodes[jd].prev].item = nodes[nodes[jd].right].item;
  1225 	      } 
  1225               }
  1226 	      popRight(pd);
  1226               popRight(pd);
  1227 	      deleteNode(jd);
  1227               deleteNode(jd);
  1228 	      jd = pd;
  1228               jd = pd;
  1229 	    } else {
  1229             } else {
  1230 	      int ld = nodes[nodes[jd].prev].right;
  1230               int ld = nodes[nodes[jd].prev].right;
  1231 	      popRight(nodes[jd].prev);
  1231               popRight(nodes[jd].prev);
  1232 	      pushLeft(jd, ld);
  1232               pushLeft(jd, ld);
  1233 	      if (less(ld, nodes[jd].right)) {
  1233               if (less(ld, nodes[jd].right)) {
  1234 		nodes[jd].item = nodes[ld].item;
  1234                 nodes[jd].item = nodes[ld].item;
  1235 		nodes[jd].prio = nodes[jd].prio;
  1235                 nodes[jd].prio = nodes[jd].prio;
  1236 	      }
  1236               }
  1237 	      if (nodes[nodes[jd].prev].item == nodes[ld].item) {
  1237               if (nodes[nodes[jd].prev].item == nodes[ld].item) {
  1238 		setPrio(nodes[jd].prev);
  1238                 setPrio(nodes[jd].prev);
  1239 	      }
  1239               }
  1240 	      jd = nodes[jd].right;
  1240               jd = nodes[jd].right;
  1241 	    }
  1241             }
  1242 	  }
  1242           }
  1243 	} else {
  1243         } else {
  1244 	  jd = nodes[jd].right;
  1244           jd = nodes[jd].right;
  1245 	}
  1245         }
  1246       }
  1246       }
  1247     }
  1247     }
  1248 
  1248 
  1249 
  1249 
  1250     bool less(int id, int jd) const {
  1250     bool less(int id, int jd) const {
  1274       return classes[cls].left == -1;
  1274       return classes[cls].left == -1;
  1275     }
  1275     }
  1276 
  1276 
  1277     /// \brief Constructs the union-find.
  1277     /// \brief Constructs the union-find.
  1278     ///
  1278     ///
  1279     /// Constructs the union-find.  
  1279     /// Constructs the union-find.
  1280     /// \brief _index The index map of the union-find. The data
  1280     /// \brief _index The index map of the union-find. The data
  1281     /// structure uses internally for store references.
  1281     /// structure uses internally for store references.
  1282     HeapUnionFind(ItemIntMap& _index) 
  1282     HeapUnionFind(ItemIntMap& _index)
  1283       : index(_index), first_class(-1), 
  1283       : index(_index), first_class(-1),
  1284 	first_free_class(-1), first_free_node(-1) {}
  1284         first_free_class(-1), first_free_node(-1) {}
  1285 
  1285 
  1286     /// \brief Insert a new node into a new component.
  1286     /// \brief Insert a new node into a new component.
  1287     ///
  1287     ///
  1288     /// Insert a new node into a new component.
  1288     /// Insert a new node into a new component.
  1289     /// \param item The item of the new node.
  1289     /// \param item The item of the new node.
  1301       nodes[id].left = -1;
  1301       nodes[id].left = -1;
  1302       nodes[id].right = -1;
  1302       nodes[id].right = -1;
  1303 
  1303 
  1304       nodes[id].item = item;
  1304       nodes[id].item = item;
  1305       index[item] = id;
  1305       index[item] = id;
  1306       
  1306 
  1307       int class_id = newClass();
  1307       int class_id = newClass();
  1308       classes[class_id].parent = ~id;
  1308       classes[class_id].parent = ~id;
  1309       classes[class_id].depth = 0;
  1309       classes[class_id].depth = 0;
  1310 
  1310 
  1311       classes[class_id].left = -1;
  1311       classes[class_id].left = -1;
  1312       classes[class_id].right = -1;
  1312       classes[class_id].right = -1;
  1313       
  1313 
  1314       if (first_class != -1) {
  1314       if (first_class != -1) {
  1315         classes[first_class].prev = class_id;
  1315         classes[first_class].prev = class_id;
  1316       }
  1316       }
  1317       classes[class_id].next = first_class;
  1317       classes[class_id].next = first_class;
  1318       classes[class_id].prev = -1;
  1318       classes[class_id].prev = -1;
  1319       first_class = class_id;
  1319       first_class = class_id;
  1320 
  1320 
  1321       nodes[id].parent = ~class_id;
  1321       nodes[id].parent = ~class_id;
  1322       
  1322 
  1323       return class_id;
  1323       return class_id;
  1324     }
  1324     }
  1325 
  1325 
  1326     /// \brief The class of the item.
  1326     /// \brief The class of the item.
  1327     ///
  1327     ///
  1330     ///
  1330     ///
  1331     /// The time complexity is O(log(n)).
  1331     /// The time complexity is O(log(n)).
  1332     int find(const Item& item) const {
  1332     int find(const Item& item) const {
  1333       return findClass(index[item]);
  1333       return findClass(index[item]);
  1334     }
  1334     }
  1335     
  1335 
  1336     /// \brief Joins the classes.
  1336     /// \brief Joins the classes.
  1337     ///
  1337     ///
  1338     /// The current function joins the given classes. The parameter is
  1338     /// The current function joins the given classes. The parameter is
  1339     /// an STL range which should be contains valid class ids. The
  1339     /// an STL range which should be contains valid class ids. The
  1340     /// time complexity is O(log(n)*k) where n is the overall number
  1340     /// time complexity is O(log(n)*k) where n is the overall number
  1369 
  1369 
  1370         if (classes[l].next != -1) {
  1370         if (classes[l].next != -1) {
  1371           classes[classes[l].next].prev = classes[l].prev;
  1371           classes[classes[l].next].prev = classes[l].prev;
  1372         }
  1372         }
  1373         classes[classes[l].prev].next = classes[l].next;
  1373         classes[classes[l].prev].next = classes[l].next;
  1374         
  1374 
  1375         classes[l].prev = -1;
  1375         classes[l].prev = -1;
  1376         classes[l].next = -1;
  1376         classes[l].next = -1;
  1377 
  1377 
  1378         classes[l].depth = leftNode(l);
  1378         classes[l].depth = leftNode(l);
  1379         classes[l].parent = class_id;
  1379         classes[l].parent = class_id;
  1380         
  1380 
  1381       }
  1381       }
  1382 
  1382 
  1383       { // merging of heap
  1383       { // merging of heap
  1384         int l = class_id;
  1384         int l = class_id;
  1385         for (int ci = 1; ci < int(cs.size()); ++ci) {
  1385         for (int ci = 1; ci < int(cs.size()); ++ci) {
  1453               nodes[new_parent].parent = ~l;
  1453               nodes[new_parent].parent = ~l;
  1454 
  1454 
  1455               push(new_parent, ~(classes[r].parent));
  1455               push(new_parent, ~(classes[r].parent));
  1456               pushLeft(new_parent, ~(classes[l].parent));
  1456               pushLeft(new_parent, ~(classes[l].parent));
  1457               setPrio(new_parent);
  1457               setPrio(new_parent);
  1458               
  1458 
  1459               classes[r].parent = ~new_parent;
  1459               classes[r].parent = ~new_parent;
  1460               classes[r].depth += 1;
  1460               classes[r].depth += 1;
  1461             } else {
  1461             } else {
  1462               pushLeft(id, ~(classes[l].parent));
  1462               pushLeft(id, ~(classes[l].parent));
  1463               while (id >= 0 && less(~(classes[l].parent), id)) {
  1463               while (id >= 0 && less(~(classes[l].parent), id)) {
  1468             }
  1468             }
  1469             nodes[~(classes[r].parent)].parent = ~l;
  1469             nodes[~(classes[r].parent)].parent = ~l;
  1470             classes[l].parent = classes[r].parent;
  1470             classes[l].parent = classes[r].parent;
  1471             classes[l].depth = classes[r].depth;
  1471             classes[l].depth = classes[r].depth;
  1472           } else {
  1472           } else {
  1473             if (classes[l].depth != 0 && 
  1473             if (classes[l].depth != 0 &&
  1474                 nodes[~(classes[l].parent)].size + 
  1474                 nodes[~(classes[l].parent)].size +
  1475                 nodes[~(classes[r].parent)].size <= cmax) {
  1475                 nodes[~(classes[r].parent)].size <= cmax) {
  1476               splice(~(classes[l].parent), ~(classes[r].parent));
  1476               splice(~(classes[l].parent), ~(classes[r].parent));
  1477               deleteNode(~(classes[r].parent));
  1477               deleteNode(~(classes[r].parent));
  1478               if (less(~(classes[r].parent), ~(classes[l].parent))) {
  1478               if (less(~(classes[r].parent), ~(classes[l].parent))) {
  1479                 nodes[~(classes[l].parent)].prio = 
  1479                 nodes[~(classes[l].parent)].prio =
  1480                   nodes[~(classes[r].parent)].prio;
  1480                   nodes[~(classes[r].parent)].prio;
  1481                 nodes[~(classes[l].parent)].item = 
  1481                 nodes[~(classes[l].parent)].item =
  1482                   nodes[~(classes[r].parent)].item;
  1482                   nodes[~(classes[r].parent)].item;
  1483               }
  1483               }
  1484             } else {
  1484             } else {
  1485               int new_parent = newNode();
  1485               int new_parent = newNode();
  1486               nodes[new_parent].next = nodes[new_parent].prev = -1;
  1486               nodes[new_parent].next = nodes[new_parent].prev = -1;
  1487               push(new_parent, ~(classes[l].parent));
  1487               push(new_parent, ~(classes[l].parent));
  1488               pushRight(new_parent, ~(classes[r].parent));
  1488               pushRight(new_parent, ~(classes[r].parent));
  1489               setPrio(new_parent);
  1489               setPrio(new_parent);
  1490             
  1490 
  1491               classes[l].parent = ~new_parent;
  1491               classes[l].parent = ~new_parent;
  1492               classes[l].depth += 1;
  1492               classes[l].depth += 1;
  1493               nodes[new_parent].parent = ~l;
  1493               nodes[new_parent].parent = ~l;
  1494             }
  1494             }
  1495           }
  1495           }
  1540         }
  1540         }
  1541 
  1541 
  1542         classes[classes[id].right].next = first_class;
  1542         classes[classes[id].right].next = first_class;
  1543         classes[first_class].prev = classes[id].right;
  1543         classes[first_class].prev = classes[id].right;
  1544         first_class = classes[id].left;
  1544         first_class = classes[id].left;
  1545         
  1545 
  1546         if (classes[id].next != -1) {
  1546         if (classes[id].next != -1) {
  1547           classes[classes[id].next].prev = classes[id].prev;
  1547           classes[classes[id].next].prev = classes[id].prev;
  1548         }
  1548         }
  1549         classes[classes[id].prev].next = classes[id].next;
  1549         classes[classes[id].prev].next = classes[id].next;
  1550         
  1550 
  1551         deleteClass(id);
  1551         deleteClass(id);
  1552       }
  1552       }
  1553 
  1553 
  1554       {
  1554       {
  1555         for (int i = 1; i < int(cs.size()); ++i) {
  1555         for (int i = 1; i < int(cs.size()); ++i) {
  1556           int l = classes[cs[i]].depth;
  1556           int l = classes[cs[i]].depth;
  1557           while (nodes[nodes[l].parent].left == l) {
  1557           while (nodes[nodes[l].parent].left == l) {
  1558             l = nodes[l].parent;
  1558             l = nodes[l].parent;
  1559           }
  1559           }
  1560           int r = l;    
  1560           int r = l;
  1561           while (nodes[l].parent >= 0) {
  1561           while (nodes[l].parent >= 0) {
  1562             l = nodes[l].parent;
  1562             l = nodes[l].parent;
  1563             int new_node = newNode();
  1563             int new_node = newNode();
  1564 
  1564 
  1565             nodes[new_node].prev = -1;
  1565             nodes[new_node].prev = -1;
  1578           nodes[l].next = -1;
  1578           nodes[l].next = -1;
  1579           nodes[r].prev = -1;
  1579           nodes[r].prev = -1;
  1580 
  1580 
  1581           repairRight(~(nodes[l].parent));
  1581           repairRight(~(nodes[l].parent));
  1582           repairLeft(cs[i]);
  1582           repairLeft(cs[i]);
  1583           
  1583 
  1584           *out++ = cs[i];
  1584           *out++ = cs[i];
  1585         }
  1585         }
  1586       }
  1586       }
  1587     }
  1587     }
  1588 
  1588 
  1601         decrease(item, prio);
  1601         decrease(item, prio);
  1602       } else if (!comp(prio, nodes[index[item]].prio)) {
  1602       } else if (!comp(prio, nodes[index[item]].prio)) {
  1603         increase(item, prio);
  1603         increase(item, prio);
  1604       }
  1604       }
  1605     }
  1605     }
  1606       
  1606 
  1607     /// \brief Increase the priority of the current item.
  1607     /// \brief Increase the priority of the current item.
  1608     ///
  1608     ///
  1609     /// Increase the priority of the current item.
  1609     /// Increase the priority of the current item.
  1610     void increase(const Item& item, const Value& prio) {
  1610     void increase(const Item& item, const Value& prio) {
  1611       int id = index[item];
  1611       int id = index[item];
  1628         nodes[kd].prio = prio;
  1628         nodes[kd].prio = prio;
  1629         nodes[kd].item = item;
  1629         nodes[kd].item = item;
  1630         kd = nodes[kd].parent;
  1630         kd = nodes[kd].parent;
  1631       }
  1631       }
  1632     }
  1632     }
  1633     
  1633 
  1634     /// \brief Gives back the minimum priority of the class.
  1634     /// \brief Gives back the minimum priority of the class.
  1635     ///
  1635     ///
  1636     /// \return Gives back the minimum priority of the class.
  1636     /// \return Gives back the minimum priority of the class.
  1637     const Value& classPrio(int cls) const {
  1637     const Value& classPrio(int cls) const {
  1638       return nodes[~(classes[cls].parent)].prio;
  1638       return nodes[~(classes[cls].parent)].prio;
  1644     const Item& classTop(int cls) const {
  1644     const Item& classTop(int cls) const {
  1645       return nodes[~(classes[cls].parent)].item;
  1645       return nodes[~(classes[cls].parent)].item;
  1646     }
  1646     }
  1647 
  1647 
  1648     /// \brief Gives back a representant item of the class.
  1648     /// \brief Gives back a representant item of the class.
  1649     /// 
  1649     ///
  1650     /// The representant is indpendent from the priorities of the
  1650     /// The representant is indpendent from the priorities of the
  1651     /// items. 
  1651     /// items.
  1652     /// \return Gives back a representant item of the class.
  1652     /// \return Gives back a representant item of the class.
  1653     const Item& classRep(int id) const {
  1653     const Item& classRep(int id) const {
  1654       int parent = classes[id].parent;
  1654       int parent = classes[id].parent;
  1655       return nodes[parent >= 0 ? classes[id].depth : leftNode(id)].item;
  1655       return nodes[parent >= 0 ? classes[id].depth : leftNode(id)].item;
  1656     }
  1656     }
  1672     class ItemIt {
  1672     class ItemIt {
  1673     private:
  1673     private:
  1674 
  1674 
  1675       const HeapUnionFind* _huf;
  1675       const HeapUnionFind* _huf;
  1676       int _id, _lid;
  1676       int _id, _lid;
  1677       
  1677 
  1678     public:
  1678     public:
  1679 
  1679 
  1680       /// \brief Default constructor 
  1680       /// \brief Default constructor
  1681       ///
  1681       ///
  1682       /// Default constructor 
  1682       /// Default constructor
  1683       ItemIt() {}
  1683       ItemIt() {}
  1684 
  1684 
  1685       ItemIt(const HeapUnionFind& huf, int cls) : _huf(&huf) {
  1685       ItemIt(const HeapUnionFind& huf, int cls) : _huf(&huf) {
  1686         int id = cls;
  1686         int id = cls;
  1687         int parent = _huf->classes[id].parent;
  1687         int parent = _huf->classes[id].parent;
  1693             _lid = -1;
  1693             _lid = -1;
  1694           }
  1694           }
  1695         } else {
  1695         } else {
  1696           _id = _huf->leftNode(id);
  1696           _id = _huf->leftNode(id);
  1697           _lid = -1;
  1697           _lid = -1;
  1698         } 
  1698         }
  1699       }
  1699       }
  1700       
  1700 
  1701       /// \brief Increment operator
  1701       /// \brief Increment operator
  1702       ///
  1702       ///
  1703       /// It steps to the next item in the class.
  1703       /// It steps to the next item in the class.
  1704       ItemIt& operator++() {
  1704       ItemIt& operator++() {
  1705         _id = _huf->nextNode(_id);
  1705         _id = _huf->nextNode(_id);
  1710       ///
  1710       ///
  1711       /// It converts the iterator to the current item.
  1711       /// It converts the iterator to the current item.
  1712       operator const Item&() const {
  1712       operator const Item&() const {
  1713         return _huf->nodes[_id].item;
  1713         return _huf->nodes[_id].item;
  1714       }
  1714       }
  1715       
  1715 
  1716       /// \brief Equality operator
  1716       /// \brief Equality operator
  1717       ///
  1717       ///
  1718       /// Equality operator
  1718       /// Equality operator
  1719       bool operator==(const ItemIt& i) { 
  1719       bool operator==(const ItemIt& i) {
  1720         return i._id == _id;
  1720         return i._id == _id;
  1721       }
  1721       }
  1722 
  1722 
  1723       /// \brief Inequality operator
  1723       /// \brief Inequality operator
  1724       ///
  1724       ///
  1725       /// Inequality operator
  1725       /// Inequality operator
  1726       bool operator!=(const ItemIt& i) { 
  1726       bool operator!=(const ItemIt& i) {
  1727         return i._id != _id;
  1727         return i._id != _id;
  1728       }
  1728       }
  1729 
  1729 
  1730       /// \brief Equality operator
  1730       /// \brief Equality operator
  1731       ///
  1731       ///
  1732       /// Equality operator
  1732       /// Equality operator
  1733       bool operator==(Invalid) { 
  1733       bool operator==(Invalid) {
  1734         return _id == _lid;
  1734         return _id == _lid;
  1735       }
  1735       }
  1736 
  1736 
  1737       /// \brief Inequality operator
  1737       /// \brief Inequality operator
  1738       ///
  1738       ///
  1739       /// Inequality operator
  1739       /// Inequality operator
  1740       bool operator!=(Invalid) { 
  1740       bool operator!=(Invalid) {
  1741         return _id != _lid;
  1741         return _id != _lid;
  1742       }
  1742       }
  1743       
  1743 
  1744     };
  1744     };
  1745 
  1745 
  1746     /// \brief Class iterator
  1746     /// \brief Class iterator
  1747     ///
  1747     ///
  1748     /// The iterator stores 
  1748     /// The iterator stores
  1749     class ClassIt {
  1749     class ClassIt {
  1750     private:
  1750     private:
  1751 
  1751 
  1752       const HeapUnionFind* _huf;
  1752       const HeapUnionFind* _huf;
  1753       int _id;
  1753       int _id;
  1754 
  1754 
  1755     public:
  1755     public:
  1756 
  1756 
  1757       ClassIt(const HeapUnionFind& huf) 
  1757       ClassIt(const HeapUnionFind& huf)
  1758         : _huf(&huf), _id(huf.first_class) {}
  1758         : _huf(&huf), _id(huf.first_class) {}
  1759 
  1759 
  1760       ClassIt(const HeapUnionFind& huf, int cls) 
  1760       ClassIt(const HeapUnionFind& huf, int cls)
  1761         : _huf(&huf), _id(huf.classes[cls].left) {}
  1761         : _huf(&huf), _id(huf.classes[cls].left) {}
  1762 
  1762 
  1763       ClassIt(Invalid) : _huf(0), _id(-1) {}
  1763       ClassIt(Invalid) : _huf(0), _id(-1) {}
  1764       
  1764 
  1765       const ClassIt& operator++() {
  1765       const ClassIt& operator++() {
  1766         _id = _huf->classes[_id].next;
  1766         _id = _huf->classes[_id].next;
  1767 	return *this;
  1767         return *this;
  1768       }
  1768       }
  1769 
  1769 
  1770       /// \brief Equality operator
  1770       /// \brief Equality operator
  1771       ///
  1771       ///
  1772       /// Equality operator
  1772       /// Equality operator
  1773       bool operator==(const ClassIt& i) { 
  1773       bool operator==(const ClassIt& i) {
  1774         return i._id == _id;
  1774         return i._id == _id;
  1775       }
  1775       }
  1776 
  1776 
  1777       /// \brief Inequality operator
  1777       /// \brief Inequality operator
  1778       ///
  1778       ///
  1779       /// Inequality operator
  1779       /// Inequality operator
  1780       bool operator!=(const ClassIt& i) { 
  1780       bool operator!=(const ClassIt& i) {
  1781         return i._id != _id;
  1781         return i._id != _id;
  1782       }      
  1782       }
  1783       
  1783 
  1784       operator int() const {
  1784       operator int() const {
  1785 	return _id;
  1785         return _id;
  1786       }
  1786       }
  1787             
  1787 
  1788     };
  1788     };
  1789 
  1789 
  1790   };
  1790   };
  1791 
  1791 
  1792   //! @}
  1792   //! @}