COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/unionfind.h @ 2550:f26368148b9c

Last change on this file since 2550:f26368148b9c was 2550:f26368148b9c, checked in by Balazs Dezso, 11 years ago

Changing degree of tournament tree
Bug fix in union find
Small efficiency improvment in bipartite matchings

File size: 47.6 KB
Line 
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2007
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 *
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
12 *
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
15 * purpose.
16 *
17 */
18
19#ifndef LEMON_UNION_FIND_H
20#define LEMON_UNION_FIND_H
21
22//!\ingroup auxdat
23//!\file
24//!\brief Union-Find data structures.
25//!
26
27#include <vector>
28#include <list>
29#include <utility>
30#include <algorithm>
31
32#include <lemon/bits/invalid.h>
33
34namespace lemon {
35
36  /// \ingroup auxdat
37  ///
38  /// \brief A \e Union-Find data structure implementation
39  ///
40  /// The class implements the \e Union-Find data structure.
41  /// The union operation uses rank heuristic, while
42  /// the find operation uses path compression.
43  /// This is a very simple but efficient implementation, providing
44  /// only four methods: join (union), find, insert and size.
45  /// For more features see the \ref UnionFindEnum class.
46  ///
47  /// It is primarily used in Kruskal algorithm for finding minimal
48  /// cost spanning tree in a graph.
49  /// \sa kruskal()
50  ///
51  /// \pre You need to add all the elements by the \ref insert()
52  /// method. 
53  template <typename _ItemIntMap>
54  class UnionFind {
55  public:
56
57    typedef _ItemIntMap ItemIntMap;
58    typedef typename ItemIntMap::Key Item;
59
60  private:
61    // If the items vector stores negative value for an item then
62    // that item is root item and it has -items[it] component size.
63    // Else the items[it] contains the index of the parent.
64    std::vector<int> items;
65    ItemIntMap& index;
66
67    bool rep(int idx) const {
68      return items[idx] < 0;
69    }
70
71    int repIndex(int idx) const {
72      int k = idx;
73      while (!rep(k)) {
74        k = items[k] ;
75      }
76      while (idx != k) {
77        int next = items[idx];
78        const_cast<int&>(items[idx]) = k;
79        idx = next;
80      }
81      return k;
82    }
83
84  public:
85
86    /// \brief Constructor
87    ///
88    /// Constructor of the UnionFind class. You should give an item to
89    /// integer map which will be used from the data structure. If you
90    /// modify directly this map that may cause segmentation fault,
91    /// invalid data structure, or infinite loop when you use again
92    /// the union-find.
93    UnionFind(ItemIntMap& m) : index(m) {}
94
95    /// \brief Returns the index of the element's component.
96    ///
97    /// The method returns the index of the element's component.
98    /// This is an integer between zero and the number of inserted elements.
99    ///
100    int find(const Item& a) {
101      return repIndex(index[a]);
102    }
103
104    /// \brief Clears the union-find data structure
105    ///
106    /// Erase each item from the data structure.
107    void clear() {
108      items.clear();
109    }
110
111    /// \brief Inserts a new element into the structure.
112    ///
113    /// This method inserts a new element into the data structure.
114    ///
115    /// The method returns the index of the new component.
116    int insert(const Item& a) {
117      int n = items.size();
118      items.push_back(-1);
119      index.set(a,n);
120      return n;
121    }
122
123    /// \brief Joining the components of element \e a and element \e b.
124    ///
125    /// This is the \e union operation of the Union-Find structure.
126    /// Joins the component of element \e a and component of
127    /// element \e b. If \e a and \e b are in the same component then
128    /// it returns false otherwise it returns true.
129    bool join(const Item& a, const Item& b) {
130      int ka = repIndex(index[a]);
131      int kb = repIndex(index[b]);
132
133      if ( ka == kb )
134        return false;
135
136      if (items[ka] < items[kb]) {
137        items[ka] += items[kb];
138        items[kb] = ka;
139      } else {
140        items[kb] += items[ka];
141        items[ka] = kb;
142      }
143      return true;
144    }
145
146    /// \brief Returns the size of the component of element \e a.
147    ///
148    /// Returns the size of the component of element \e a.
149    int size(const Item& a) {
150      int k = repIndex(index[a]);
151      return - items[k];
152    }
153
154  };
155
156  /// \ingroup auxdat
157  ///
158  /// \brief A \e Union-Find data structure implementation which
159  /// is able to enumerate the components.
160  ///
161  /// The class implements a \e Union-Find data structure
162  /// which is able to enumerate the components and the items in
163  /// a component. If you don't need this feature then perhaps it's
164  /// better to use the \ref UnionFind class which is more efficient.
165  ///
166  /// The union operation uses rank heuristic, while
167  /// the find operation uses path compression.
168  ///
169  /// \pre You need to add all the elements by the \ref insert()
170  /// method.
171  ///
172  template <typename _ItemIntMap>
173  class UnionFindEnum {
174  public:
175   
176    typedef _ItemIntMap ItemIntMap;
177    typedef typename ItemIntMap::Key Item;
178
179  private:
180   
181    ItemIntMap& index;
182
183    // If the parent stores negative value for an item then that item
184    // is root item and it has ~(items[it].parent) component id.  Else
185    // the items[it].parent contains the index of the parent.
186    //
187    // The \c next and \c prev provides the double-linked
188    // cyclic list of one component's items.
189    struct ItemT {
190      int parent;
191      Item item;
192
193      int next, prev;
194    };
195
196    std::vector<ItemT> items;
197    int firstFreeItem;
198
199    struct ClassT {
200      int size;
201      int firstItem;
202      int next, prev;
203    };
204   
205    std::vector<ClassT> classes;
206    int firstClass, firstFreeClass;
207
208    int newClass() {
209      if (firstFreeClass == -1) {
210        int cdx = classes.size();
211        classes.push_back(ClassT());
212        return cdx;
213      } else {
214        int cdx = firstFreeClass;
215        firstFreeClass = classes[firstFreeClass].next;
216        return cdx;
217      }
218    }
219
220    int newItem() {
221      if (firstFreeItem == -1) {
222        int idx = items.size();
223        items.push_back(ItemT());
224        return idx;
225      } else {
226        int idx = firstFreeItem;
227        firstFreeItem = items[firstFreeItem].next;
228        return idx;
229      }
230    }
231
232
233    bool rep(int idx) const {
234      return items[idx].parent < 0;
235    }
236
237    int repIndex(int idx) const {
238      int k = idx;
239      while (!rep(k)) {
240        k = items[k].parent;
241      }
242      while (idx != k) {
243        int next = items[idx].parent;
244        const_cast<int&>(items[idx].parent) = k;
245        idx = next;
246      }
247      return k;
248    }
249
250    int classIndex(int idx) const {
251      return ~(items[repIndex(idx)].parent);
252    }
253
254    void singletonItem(int idx) {
255      items[idx].next = idx;
256      items[idx].prev = idx;
257    }
258
259    void laceItem(int idx, int rdx) {
260      items[idx].prev = rdx;
261      items[idx].next = items[rdx].next;
262      items[items[rdx].next].prev = idx;
263      items[rdx].next = idx;
264    }
265
266    void unlaceItem(int idx) {
267      items[items[idx].prev].next = items[idx].next;
268      items[items[idx].next].prev = items[idx].prev;
269     
270      items[idx].next = firstFreeItem;
271      firstFreeItem = idx;
272    }
273
274    void spliceItems(int ak, int bk) {
275      items[items[ak].prev].next = bk;
276      items[items[bk].prev].next = ak;
277      int tmp = items[ak].prev;
278      items[ak].prev = items[bk].prev;
279      items[bk].prev = tmp;
280       
281    }
282
283    void laceClass(int cls) {
284      if (firstClass != -1) {
285        classes[firstClass].prev = cls;
286      }
287      classes[cls].next = firstClass;
288      classes[cls].prev = -1;
289      firstClass = cls;
290    }
291
292    void unlaceClass(int cls) {
293      if (classes[cls].prev != -1) {
294        classes[classes[cls].prev].next = classes[cls].next;
295      } else {
296        firstClass = classes[cls].next;
297      }
298      if (classes[cls].next != -1) {
299        classes[classes[cls].next].prev = classes[cls].prev;
300      }
301     
302      classes[cls].next = firstFreeClass;
303      firstFreeClass = cls;
304    }
305
306  public:
307
308    UnionFindEnum(ItemIntMap& _index)
309      : index(_index), items(), firstFreeItem(-1),
310        firstClass(-1), firstFreeClass(-1) {}
311   
312    /// \brief Inserts the given element into a new component.
313    ///
314    /// This method creates a new component consisting only of the
315    /// given element.
316    ///
317    int insert(const Item& item) {
318      int idx = newItem();
319
320      index.set(item, idx);
321
322      singletonItem(idx);
323      items[idx].item = item;
324
325      int cdx = newClass();
326
327      items[idx].parent = ~cdx;
328
329      laceClass(cdx);
330      classes[cdx].size = 1;
331      classes[cdx].firstItem = idx;
332
333      firstClass = cdx;
334     
335      return cdx;
336    }
337
338    /// \brief Inserts the given element into the component of the others.
339    ///
340    /// This methods inserts the element \e a into the component of the
341    /// element \e comp.
342    void insert(const Item& item, int cls) {
343      int rdx = classes[cls].firstItem;
344      int idx = newItem();
345
346      index.set(item, idx);
347
348      laceItem(idx, rdx);
349
350      items[idx].item = item;
351      items[idx].parent = rdx;
352
353      ++classes[~(items[rdx].parent)].size;
354    }
355
356    /// \brief Clears the union-find data structure
357    ///
358    /// Erase each item from the data structure.
359    void clear() {
360      items.clear();
361      firstClass = -1;
362      firstFreeItem = -1;
363    }
364
365    /// \brief Finds the component of the given element.
366    ///
367    /// The method returns the component id of the given element.
368    int find(const Item &item) const {
369      return ~(items[repIndex(index[item])].parent);
370    }
371
372    /// \brief Joining the component of element \e a and element \e b.
373    ///
374    /// This is the \e union operation of the Union-Find structure.
375    /// Joins the component of element \e a and component of
376    /// element \e b. If \e a and \e b are in the same component then
377    /// returns -1 else returns the remaining class.
378    int join(const Item& a, const Item& b) {
379
380      int ak = repIndex(index[a]);
381      int bk = repIndex(index[b]);
382
383      if (ak == bk) {
384        return -1;
385      }
386
387      int acx = ~(items[ak].parent);
388      int bcx = ~(items[bk].parent);
389
390      int rcx;
391
392      if (classes[acx].size > classes[bcx].size) {
393        classes[acx].size += classes[bcx].size;
394        items[bk].parent = ak;
395        unlaceClass(bcx);
396        rcx = acx;
397      } else {
398        classes[bcx].size += classes[acx].size;
399        items[ak].parent = bk;
400        unlaceClass(acx);
401        rcx = bcx;
402      }
403      spliceItems(ak, bk);
404
405      return rcx;
406    }
407
408    /// \brief Returns the size of the class.
409    ///
410    /// Returns the size of the class.
411    int size(int cls) const {
412      return classes[cls].size;
413    }
414
415    /// \brief Splits up the component.
416    ///
417    /// Splitting the component into singleton components (component
418    /// of size one).
419    void split(int cls) {
420      int fdx = classes[cls].firstItem;
421      int idx = items[fdx].next;
422      while (idx != fdx) {
423        int next = items[idx].next;
424
425        singletonItem(idx);
426
427        int cdx = newClass();       
428        items[idx].parent = ~cdx;
429
430        laceClass(cdx);
431        classes[cdx].size = 1;
432        classes[cdx].firstItem = idx;
433       
434        idx = next;
435      }
436
437      items[idx].prev = idx;
438      items[idx].next = idx;
439
440      classes[~(items[idx].parent)].size = 1;
441     
442    }
443
444    /// \brief Removes the given element from the structure.
445    ///
446    /// Removes the element from its component and if the component becomes
447    /// empty then removes that component from the component list.
448    ///
449    /// \warning It is an error to remove an element which is not in
450    /// the structure.
451    /// \warning This running time of this operation is proportional to the
452    /// number of the items in this class.
453    void erase(const Item& item) {
454      int idx = index[item];
455      int fdx = items[idx].next;
456
457      int cdx = classIndex(idx);
458      if (idx == fdx) {
459        unlaceClass(cdx);
460        items[idx].next = firstFreeItem;
461        firstFreeItem = idx;
462        return;
463      } else {
464        classes[cdx].firstItem = fdx;
465        --classes[cdx].size;
466        items[fdx].parent = ~cdx;
467
468        unlaceItem(idx);
469        idx = items[fdx].next;
470        while (idx != fdx) {
471          items[idx].parent = fdx;
472          idx = items[idx].next;
473        }
474         
475      }
476
477    }
478
479    /// \brief Gives back a representant item of the component.
480    ///
481    /// Gives back a representant item of the component.
482    Item item(int cls) const {
483      return items[classes[cls].firstItem].item;
484    }
485
486    /// \brief Removes the component of the given element from the structure.
487    ///
488    /// Removes the component of the given element from the structure.
489    ///
490    /// \warning It is an error to give an element which is not in the
491    /// structure.
492    void eraseClass(int cls) {
493      int fdx = classes[cls].firstItem;
494      unlaceClass(cls);
495      items[items[fdx].prev].next = firstFreeItem;
496      firstFreeItem = fdx;
497    }
498
499    /// \brief Lemon style iterator for the representant items.
500    ///
501    /// ClassIt is a lemon style iterator for the components. It iterates
502    /// on the ids of the classes.
503    class ClassIt {
504    public:
505      /// \brief Constructor of the iterator
506      ///
507      /// Constructor of the iterator
508      ClassIt(const UnionFindEnum& ufe) : unionFind(&ufe) {
509        cdx = unionFind->firstClass;
510      }
511
512      /// \brief Constructor to get invalid iterator
513      ///
514      /// Constructor to get invalid iterator
515      ClassIt(Invalid) : unionFind(0), cdx(-1) {}
516     
517      /// \brief Increment operator
518      ///
519      /// It steps to the next representant item.
520      ClassIt& operator++() {
521        cdx = unionFind->classes[cdx].next;
522        return *this;
523      }
524     
525      /// \brief Conversion operator
526      ///
527      /// It converts the iterator to the current representant item.
528      operator int() const {
529        return cdx;
530      }
531
532      /// \brief Equality operator
533      ///
534      /// Equality operator
535      bool operator==(const ClassIt& i) {
536        return i.cdx == cdx;
537      }
538
539      /// \brief Inequality operator
540      ///
541      /// Inequality operator
542      bool operator!=(const ClassIt& i) {
543        return i.cdx != cdx;
544      }
545     
546    private:
547      const UnionFindEnum* unionFind;
548      int cdx;
549    };
550
551    /// \brief Lemon style iterator for the items of a component.
552    ///
553    /// ClassIt is a lemon style iterator for the components. It iterates
554    /// on the items of a class. By example if you want to iterate on
555    /// each items of each classes then you may write the next code.
556    ///\code
557    /// for (ClassIt cit(ufe); cit != INVALID; ++cit) {
558    ///   std::cout << "Class: ";
559    ///   for (ItemIt iit(ufe, cit); iit != INVALID; ++iit) {
560    ///     std::cout << toString(iit) << ' ' << std::endl;
561    ///   }
562    ///   std::cout << std::endl;
563    /// }
564    ///\endcode
565    class ItemIt {
566    public:
567      /// \brief Constructor of the iterator
568      ///
569      /// Constructor of the iterator. The iterator iterates
570      /// on the class of the \c item.
571      ItemIt(const UnionFindEnum& ufe, int cls) : unionFind(&ufe) {
572        fdx = idx = unionFind->classes[cls].firstItem;
573      }
574
575      /// \brief Constructor to get invalid iterator
576      ///
577      /// Constructor to get invalid iterator
578      ItemIt(Invalid) : unionFind(0), idx(-1) {}
579     
580      /// \brief Increment operator
581      ///
582      /// It steps to the next item in the class.
583      ItemIt& operator++() {
584        idx = unionFind->items[idx].next;
585        if (idx == fdx) idx = -1;
586        return *this;
587      }
588     
589      /// \brief Conversion operator
590      ///
591      /// It converts the iterator to the current item.
592      operator const Item&() const {
593        return unionFind->items[idx].item;
594      }
595
596      /// \brief Equality operator
597      ///
598      /// Equality operator
599      bool operator==(const ItemIt& i) {
600        return i.idx == idx;
601      }
602
603      /// \brief Inequality operator
604      ///
605      /// Inequality operator
606      bool operator!=(const ItemIt& i) {
607        return i.idx != idx;
608      }
609     
610    private:
611      const UnionFindEnum* unionFind;
612      int idx, fdx;
613    };
614
615  };
616
617  /// \ingroup auxdat
618  ///
619  /// \brief A \e Extend-Find data structure implementation which
620  /// is able to enumerate the components.
621  ///
622  /// The class implements an \e Extend-Find data structure which is
623  /// able to enumerate the components and the items in a
624  /// component. The data structure is a simplification of the
625  /// Union-Find structure, and it does not allow to merge two components.
626  ///
627  /// \pre You need to add all the elements by the \ref insert()
628  /// method.
629  template <typename _ItemIntMap>
630  class ExtendFindEnum {
631  public:
632   
633    typedef _ItemIntMap ItemIntMap;
634    typedef typename ItemIntMap::Key Item;
635
636  private:
637   
638    ItemIntMap& index;
639
640    struct ItemT {
641      int cls;
642      Item item;
643      int next, prev;
644    };
645
646    std::vector<ItemT> items;
647    int firstFreeItem;
648
649    struct ClassT {
650      int firstItem;
651      int next, prev;
652    };
653
654    std::vector<ClassT> classes;
655
656    int firstClass, firstFreeClass;
657
658    int newClass() {
659      if (firstFreeClass != -1) {
660        int cdx = firstFreeClass;
661        firstFreeClass = classes[cdx].next;
662        return cdx;
663      } else {
664        classes.push_back(ClassT());
665        return classes.size() - 1;
666      }
667    }
668
669    int newItem() {
670      if (firstFreeItem != -1) {
671        int idx = firstFreeItem;
672        firstFreeItem = items[idx].next;
673        return idx;
674      } else {
675        items.push_back(ItemT());
676        return items.size() - 1;
677      }
678    }
679
680  public:
681
682    /// \brief Constructor
683    ExtendFindEnum(ItemIntMap& _index)
684      : index(_index), items(), firstFreeItem(-1),
685        classes(), firstClass(-1), firstFreeClass(-1) {}
686   
687    /// \brief Inserts the given element into a new component.
688    ///
689    /// This method creates a new component consisting only of the
690    /// given element.
691    int insert(const Item& item) {
692      int cdx = newClass();
693      classes[cdx].prev = -1;
694      classes[cdx].next = firstClass;
695      if (firstClass != -1) {
696        classes[firstClass].prev = cdx;
697      }
698      firstClass = cdx;
699     
700      int idx = newItem();
701      items[idx].item = item;
702      items[idx].cls = cdx;
703      items[idx].prev = idx;
704      items[idx].next = idx;
705
706      classes[cdx].firstItem = idx;
707
708      index.set(item, idx);
709     
710      return cdx;
711    }
712
713    /// \brief Inserts the given element into the given component.
714    ///
715    /// This methods inserts the element \e item a into the \e cls class.
716    void insert(const Item& item, int cls) {
717      int idx = newItem();
718      int rdx = classes[cls].firstItem;
719      items[idx].item = item;
720      items[idx].cls = cls;
721
722      items[idx].prev = rdx;
723      items[idx].next = items[rdx].next;
724      items[items[rdx].next].prev = idx;
725      items[rdx].next = idx;
726
727      index.set(item, idx);
728    }
729
730    /// \brief Clears the union-find data structure
731    ///
732    /// Erase each item from the data structure.
733    void clear() {
734      items.clear();
735      classes.clear;
736      firstClass = firstFreeClass = firstFreeItem = -1;
737    }
738
739    /// \brief Gives back the class of the \e item.
740    ///
741    /// Gives back the class of the \e item.
742    int find(const Item &item) const {
743      return items[index[item]].cls;
744    }
745
746    /// \brief Gives back a representant item of the component.
747    ///
748    /// Gives back a representant item of the component.
749    Item item(int cls) const {
750      return items[classes[cls].firstItem].item;
751    }
752   
753    /// \brief Removes the given element from the structure.
754    ///
755    /// Removes the element from its component and if the component becomes
756    /// empty then removes that component from the component list.
757    ///
758    /// \warning It is an error to remove an element which is not in
759    /// the structure.
760    void erase(const Item &item) {
761      int idx = index[item];
762      int cdx = items[idx].cls;
763     
764      if (idx == items[idx].next) {
765        if (classes[cdx].prev != -1) {
766          classes[classes[cdx].prev].next = classes[cdx].next;
767        } else {
768          firstClass = classes[cdx].next;
769        }
770        if (classes[cdx].next != -1) {
771          classes[classes[cdx].next].prev = classes[cdx].prev;
772        }
773        classes[cdx].next = firstFreeClass;
774        firstFreeClass = cdx;
775      } else {
776        classes[cdx].firstItem = items[idx].next;
777        items[items[idx].next].prev = items[idx].prev;
778        items[items[idx].prev].next = items[idx].next;
779      }
780      items[idx].next = firstFreeItem;
781      firstFreeItem = idx;
782       
783    }   
784
785   
786    /// \brief Removes the component of the given element from the structure.
787    ///
788    /// Removes the component of the given element from the structure.
789    ///
790    /// \warning It is an error to give an element which is not in the
791    /// structure.
792    void eraseClass(int cdx) {
793      int idx = classes[cdx].firstItem;
794      items[items[idx].prev].next = firstFreeItem;
795      firstFreeItem = idx;
796
797      if (classes[cdx].prev != -1) {
798        classes[classes[cdx].prev].next = classes[cdx].next;
799      } else {
800        firstClass = classes[cdx].next;
801      }
802      if (classes[cdx].next != -1) {
803        classes[classes[cdx].next].prev = classes[cdx].prev;
804      }
805      classes[cdx].next = firstFreeClass;
806      firstFreeClass = cdx;
807    }
808
809    /// \brief Lemon style iterator for the classes.
810    ///
811    /// ClassIt is a lemon style iterator for the components. It iterates
812    /// on the ids of classes.
813    class ClassIt {
814    public:
815      /// \brief Constructor of the iterator
816      ///
817      /// Constructor of the iterator
818      ClassIt(const ExtendFindEnum& ufe) : extendFind(&ufe) {
819        cdx = extendFind->firstClass;
820      }
821
822      /// \brief Constructor to get invalid iterator
823      ///
824      /// Constructor to get invalid iterator
825      ClassIt(Invalid) : extendFind(0), cdx(-1) {}
826     
827      /// \brief Increment operator
828      ///
829      /// It steps to the next representant item.
830      ClassIt& operator++() {
831        cdx = extendFind->classes[cdx].next;
832        return *this;
833      }
834     
835      /// \brief Conversion operator
836      ///
837      /// It converts the iterator to the current class id.
838      operator int() const {
839        return cdx;
840      }
841
842      /// \brief Equality operator
843      ///
844      /// Equality operator
845      bool operator==(const ClassIt& i) {
846        return i.cdx == cdx;
847      }
848
849      /// \brief Inequality operator
850      ///
851      /// Inequality operator
852      bool operator!=(const ClassIt& i) {
853        return i.cdx != cdx;
854      }
855     
856    private:
857      const ExtendFindEnum* extendFind;
858      int cdx;
859    };
860
861    /// \brief Lemon style iterator for the items of a component.
862    ///
863    /// ClassIt is a lemon style iterator for the components. It iterates
864    /// on the items of a class. By example if you want to iterate on
865    /// each items of each classes then you may write the next code.
866    ///\code
867    /// for (ClassIt cit(ufe); cit != INVALID; ++cit) {
868    ///   std::cout << "Class: ";
869    ///   for (ItemIt iit(ufe, cit); iit != INVALID; ++iit) {
870    ///     std::cout << toString(iit) << ' ' << std::endl;
871    ///   }
872    ///   std::cout << std::endl;
873    /// }
874    ///\endcode
875    class ItemIt {
876    public:
877      /// \brief Constructor of the iterator
878      ///
879      /// Constructor of the iterator. The iterator iterates
880      /// on the class of the \c item.
881      ItemIt(const ExtendFindEnum& ufe, int cls) : extendFind(&ufe) {
882        fdx = idx = extendFind->classes[cls].firstItem;
883      }
884
885      /// \brief Constructor to get invalid iterator
886      ///
887      /// Constructor to get invalid iterator
888      ItemIt(Invalid) : extendFind(0), idx(-1) {}
889     
890      /// \brief Increment operator
891      ///
892      /// It steps to the next item in the class.
893      ItemIt& operator++() {
894        idx = extendFind->items[idx].next;
895        if (fdx == idx) idx = -1;
896        return *this;
897      }
898     
899      /// \brief Conversion operator
900      ///
901      /// It converts the iterator to the current item.
902      operator const Item&() const {
903        return extendFind->items[idx].item;
904      }
905
906      /// \brief Equality operator
907      ///
908      /// Equality operator
909      bool operator==(const ItemIt& i) {
910        return i.idx == idx;
911      }
912
913      /// \brief Inequality operator
914      ///
915      /// Inequality operator
916      bool operator!=(const ItemIt& i) {
917        return i.idx != idx;
918      }
919     
920    private:
921      const ExtendFindEnum* extendFind;
922      int idx, fdx;
923    };
924
925  };
926
927  /// \ingroup auxdat
928  ///
929  /// \brief A \e Union-Find data structure implementation which
930  /// is able to store a priority for each item and retrieve the minimum of
931  /// each class.
932  ///
933  /// A \e Union-Find data structure implementation which is able to
934  /// store a priority for each item and retrieve the minimum of each
935  /// class. In addition, it supports the joining and splitting the
936  /// components. If you don't need this feature then you makes
937  /// better to use the \ref UnionFind class which is more efficient.
938  ///
939  /// The union-find data strcuture based on a (2, 16)-tree with a
940  /// tournament minimum selection on the internal nodes. The insert
941  /// operation takes O(1), the find, set, decrease and increase takes
942  /// O(log(n)), where n is the number of nodes in the current
943  /// component.  The complexity of join and split is O(log(n)*k),
944  /// where n is the sum of the number of the nodes and k is the
945  /// number of joined components or the number of the components
946  /// after the split.
947  ///
948  /// \pre You need to add all the elements by the \ref insert()
949  /// method.
950  ///
951  template <typename _Value, typename _ItemIntMap,
952            typename _Comp = std::less<_Value> >
953  class HeapUnionFind {
954  public:
955   
956    typedef _Value Value;
957    typedef typename _ItemIntMap::Key Item;
958
959    typedef _ItemIntMap ItemIntMap;
960
961    typedef _Comp Comp;
962
963  private:
964
965    static const int cmax = 16;
966
967    ItemIntMap& index;
968
969    struct ClassNode {
970      int parent;
971      int depth;
972
973      int left, right;
974      int next, prev;
975    };
976
977    int first_class;
978    int first_free_class;
979    std::vector<ClassNode> classes;
980
981    int newClass() {
982      if (first_free_class < 0) {
983        int id = classes.size();
984        classes.push_back(ClassNode());
985        return id;
986      } else {
987        int id = first_free_class;
988        first_free_class = classes[id].next;
989        return id;
990      }
991    }
992
993    void deleteClass(int id) {
994      classes[id].next = first_free_class;
995      first_free_class = id;
996    }
997
998    struct ItemNode {
999      int parent;
1000      Item item;
1001      Value prio;
1002      int next, prev;
1003      int left, right;
1004      int size;
1005    };
1006
1007    int first_free_node;
1008    std::vector<ItemNode> nodes;
1009
1010    int newNode() {
1011      if (first_free_node < 0) {
1012        int id = nodes.size();
1013        nodes.push_back(ItemNode());
1014        return id;
1015      } else {
1016        int id = first_free_node;
1017        first_free_node = nodes[id].next;
1018        return id;
1019      }
1020    }
1021
1022    void deleteNode(int id) {
1023      nodes[id].next = first_free_node;
1024      first_free_node = id;
1025    }
1026
1027    Comp comp;
1028
1029    int findClass(int id) const {
1030      int kd = id;
1031      while (kd >= 0) {
1032        kd = nodes[kd].parent;
1033      }
1034      return ~kd;
1035    }
1036
1037    int leftNode(int id) const {
1038      int kd = ~(classes[id].parent);
1039      for (int i = 0; i < classes[id].depth; ++i) {
1040        kd = nodes[kd].left;
1041      }
1042      return kd;
1043    }
1044
1045    int nextNode(int id) const {
1046      int depth = 0;
1047      while (id >= 0 && nodes[id].next == -1) {
1048        id = nodes[id].parent;
1049        ++depth;
1050      }
1051      if (id < 0) {
1052        return -1;
1053      }
1054      id = nodes[id].next;
1055      while (depth--) {
1056        id = nodes[id].left;     
1057      }
1058      return id;
1059    }
1060
1061
1062    void setPrio(int id) {
1063      int jd = nodes[id].left;
1064      nodes[id].prio = nodes[jd].prio;
1065      nodes[id].item = nodes[jd].item;
1066      jd = nodes[jd].next;
1067      while (jd != -1) {
1068        if (comp(nodes[jd].prio, nodes[id].prio)) {
1069          nodes[id].prio = nodes[jd].prio;
1070          nodes[id].item = nodes[jd].item;
1071        }
1072        jd = nodes[jd].next;
1073      }
1074    }
1075
1076    void push(int id, int jd) {
1077      nodes[id].size = 1;
1078      nodes[id].left = nodes[id].right = jd;
1079      nodes[jd].next = nodes[jd].prev = -1;
1080      nodes[jd].parent = id;
1081    }
1082
1083    void pushAfter(int id, int jd) {
1084      int kd = nodes[id].parent;
1085      if (nodes[id].next != -1) {
1086        nodes[nodes[id].next].prev = jd;
1087        if (kd >= 0) {
1088          nodes[kd].size += 1;
1089        }
1090      } else {
1091        if (kd >= 0) {
1092          nodes[kd].right = jd;
1093          nodes[kd].size += 1;
1094        }
1095      }
1096      nodes[jd].next = nodes[id].next;
1097      nodes[jd].prev = id;
1098      nodes[id].next = jd;
1099      nodes[jd].parent = kd;
1100    }
1101
1102    void pushRight(int id, int jd) {
1103      nodes[id].size += 1;
1104      nodes[jd].prev = nodes[id].right;
1105      nodes[jd].next = -1;
1106      nodes[nodes[id].right].next = jd;
1107      nodes[id].right = jd;
1108      nodes[jd].parent = id;
1109    }
1110
1111    void popRight(int id) {
1112      nodes[id].size -= 1;
1113      int jd = nodes[id].right;
1114      nodes[nodes[jd].prev].next = -1;
1115      nodes[id].right = nodes[jd].prev;
1116    }
1117
1118    void splice(int id, int jd) {
1119      nodes[id].size += nodes[jd].size;
1120      nodes[nodes[id].right].next = nodes[jd].left;
1121      nodes[nodes[jd].left].prev = nodes[id].right;
1122      int kd = nodes[jd].left;
1123      while (kd != -1) {
1124        nodes[kd].parent = id;
1125        kd = nodes[kd].next;
1126      }
1127      nodes[id].right = nodes[jd].right;
1128    }
1129
1130    void split(int id, int jd) {
1131      int kd = nodes[id].parent;
1132      nodes[kd].right = nodes[id].prev;
1133      nodes[nodes[id].prev].next = -1;
1134     
1135      nodes[jd].left = id;
1136      nodes[id].prev = -1;
1137      int num = 0;
1138      while (id != -1) {
1139        nodes[id].parent = jd;
1140        nodes[jd].right = id;
1141        id = nodes[id].next;
1142        ++num;
1143      }     
1144      nodes[kd].size -= num;
1145      nodes[jd].size = num;
1146    }
1147
1148    void pushLeft(int id, int jd) {
1149      nodes[id].size += 1;
1150      nodes[jd].next = nodes[id].left;
1151      nodes[jd].prev = -1;
1152      nodes[nodes[id].left].prev = jd;
1153      nodes[id].left = jd;
1154      nodes[jd].parent = id;
1155    }
1156
1157    void popLeft(int id) {
1158      nodes[id].size -= 1;
1159      int jd = nodes[id].left;
1160      nodes[nodes[jd].next].prev = -1;
1161      nodes[id].left = nodes[jd].next;
1162    }
1163
1164    void repairLeft(int id) {
1165      int jd = ~(classes[id].parent);
1166      while (nodes[jd].left != -1) {
1167        int kd = nodes[jd].left;
1168        if (nodes[jd].size == 1) {
1169          if (nodes[jd].parent < 0) {
1170            classes[id].parent = ~kd;
1171            classes[id].depth -= 1;
1172            nodes[kd].parent = ~id;
1173            deleteNode(jd);
1174            jd = kd;
1175          } else {
1176            int pd = nodes[jd].parent;
1177            if (nodes[nodes[jd].next].size < cmax) {
1178              pushLeft(nodes[jd].next, nodes[jd].left);
1179              if (less(nodes[jd].left, nodes[jd].next)) {
1180                nodes[nodes[jd].next].prio = nodes[nodes[jd].left].prio;
1181                nodes[nodes[jd].next].item = nodes[nodes[jd].left].item;
1182              }
1183              popLeft(pd);
1184              deleteNode(jd);
1185              jd = pd;
1186            } else {
1187              int ld = nodes[nodes[jd].next].left;
1188              popLeft(nodes[jd].next);
1189              pushRight(jd, ld);
1190              if (less(ld, nodes[jd].left)) {
1191                nodes[jd].item = nodes[ld].item;
1192                nodes[jd].prio = nodes[jd].prio;
1193              }
1194              if (nodes[nodes[jd].next].item == nodes[ld].item) {
1195                setPrio(nodes[jd].next);
1196              }
1197              jd = nodes[jd].left;
1198            }
1199          }
1200        } else {
1201          jd = nodes[jd].left;
1202        }
1203      }
1204    }   
1205
1206    void repairRight(int id) {
1207      int jd = ~(classes[id].parent);
1208      while (nodes[jd].right != -1) {
1209        int kd = nodes[jd].right;
1210        if (nodes[jd].size == 1) {
1211          if (nodes[jd].parent < 0) {
1212            classes[id].parent = ~kd;
1213            classes[id].depth -= 1;
1214            nodes[kd].parent = ~id;
1215            deleteNode(jd);
1216            jd = kd;
1217          } else {
1218            int pd = nodes[jd].parent;
1219            if (nodes[nodes[jd].prev].size < cmax) {
1220              pushRight(nodes[jd].prev, nodes[jd].right);
1221              if (less(nodes[jd].right, nodes[jd].prev)) {
1222                nodes[nodes[jd].prev].prio = nodes[nodes[jd].right].prio;
1223                nodes[nodes[jd].prev].item = nodes[nodes[jd].right].item;
1224              }
1225              popRight(pd);
1226              deleteNode(jd);
1227              jd = pd;
1228            } else {
1229              int ld = nodes[nodes[jd].prev].right;
1230              popRight(nodes[jd].prev);
1231              pushLeft(jd, ld);
1232              if (less(ld, nodes[jd].right)) {
1233                nodes[jd].item = nodes[ld].item;
1234                nodes[jd].prio = nodes[jd].prio;
1235              }
1236              if (nodes[nodes[jd].prev].item == nodes[ld].item) {
1237                setPrio(nodes[jd].prev);
1238              }
1239              jd = nodes[jd].right;
1240            }
1241          }
1242        } else {
1243          jd = nodes[jd].right;
1244        }
1245      }
1246    }
1247
1248
1249    bool less(int id, int jd) const {
1250      return comp(nodes[id].prio, nodes[jd].prio);
1251    }
1252
1253    bool equal(int id, int jd) const {
1254      return !less(id, jd) && !less(jd, id);
1255    }
1256
1257
1258  public:
1259
1260    /// \brief Returns true when the given class is alive.
1261    ///
1262    /// Returns true when the given class is alive, ie. the class is
1263    /// not nested into other class.
1264    bool alive(int cls) const {
1265      return classes[cls].parent < 0;
1266    }
1267
1268    /// \brief Returns true when the given class is trivial.
1269    ///
1270    /// Returns true when the given class is trivial, ie. the class
1271    /// contains just one item directly.
1272    bool trivial(int cls) const {
1273      return classes[cls].left == -1;
1274    }
1275
1276    /// \brief Constructs the union-find.
1277    ///
1278    /// Constructs the union-find. 
1279    /// \brief _index The index map of the union-find. The data
1280    /// structure uses internally for store references.
1281    HeapUnionFind(ItemIntMap& _index)
1282      : index(_index), first_class(-1),
1283        first_free_class(-1), first_free_node(-1) {}
1284
1285    /// \brief Insert a new node into a new component.
1286    ///
1287    /// Insert a new node into a new component.
1288    /// \param item The item of the new node.
1289    /// \param prio The priority of the new node.
1290    /// \return The class id of the one-item-heap.
1291    int insert(const Item& item, const Value& prio) {
1292      int id = newNode();
1293      nodes[id].item = item;
1294      nodes[id].prio = prio;
1295      nodes[id].size = 0;
1296
1297      nodes[id].prev = -1;
1298      nodes[id].next = -1;
1299
1300      nodes[id].left = -1;
1301      nodes[id].right = -1;
1302
1303      nodes[id].item = item;
1304      index[item] = id;
1305     
1306      int class_id = newClass();
1307      classes[class_id].parent = ~id;
1308      classes[class_id].depth = 0;
1309
1310      classes[class_id].left = -1;
1311      classes[class_id].right = -1;
1312     
1313      if (first_class != -1) {
1314        classes[first_class].prev = class_id;
1315      }
1316      classes[class_id].next = first_class;
1317      classes[class_id].prev = -1;
1318      first_class = class_id;
1319
1320      nodes[id].parent = ~class_id;
1321     
1322      return class_id;
1323    }
1324
1325    /// \brief The class of the item.
1326    ///
1327    /// \return The alive class id of the item, which is not nested into
1328    /// other classes.
1329    ///
1330    /// The time complexity is O(log(n)).
1331    int find(const Item& item) const {
1332      return findClass(index[item]);
1333    }
1334   
1335    /// \brief Joins the classes.
1336    ///
1337    /// The current function joins the given classes. The parameter is
1338    /// an STL range which should be contains valid class ids. The
1339    /// time complexity is O(log(n)*k) where n is the overall number
1340    /// of the joined nodes and k is the number of classes.
1341    /// \return The class of the joined classes.
1342    /// \pre The range should contain at least two class ids.
1343    template <typename Iterator>
1344    int join(Iterator begin, Iterator end) {
1345      std::vector<int> cs;
1346      for (Iterator it = begin; it != end; ++it) {
1347        cs.push_back(*it);
1348      }
1349
1350      int class_id = newClass();
1351      { // creation union-find
1352
1353        if (first_class != -1) {
1354          classes[first_class].prev = class_id;
1355        }
1356        classes[class_id].next = first_class;
1357        classes[class_id].prev = -1;
1358        first_class = class_id;
1359
1360        classes[class_id].depth = classes[cs[0]].depth;
1361        classes[class_id].parent = classes[cs[0]].parent;
1362        nodes[~(classes[class_id].parent)].parent = ~class_id;
1363
1364        int l = cs[0];
1365
1366        classes[class_id].left = l;
1367        classes[class_id].right = l;
1368
1369        if (classes[l].next != -1) {
1370          classes[classes[l].next].prev = classes[l].prev;
1371        }
1372        classes[classes[l].prev].next = classes[l].next;
1373       
1374        classes[l].prev = -1;
1375        classes[l].next = -1;
1376
1377        classes[l].depth = leftNode(l);
1378        classes[l].parent = class_id;
1379       
1380      }
1381
1382      { // merging of heap
1383        int l = class_id;
1384        for (int ci = 1; ci < int(cs.size()); ++ci) {
1385          int r = cs[ci];
1386          int rln = leftNode(r);
1387          if (classes[l].depth > classes[r].depth) {
1388            int id = ~(classes[l].parent);
1389            for (int i = classes[r].depth + 1; i < classes[l].depth; ++i) {
1390              id = nodes[id].right;
1391            }
1392            while (id >= 0 && nodes[id].size == cmax) {
1393              int new_id = newNode();
1394              int right_id = nodes[id].right;
1395
1396              popRight(id);
1397              if (nodes[id].item == nodes[right_id].item) {
1398                setPrio(id);
1399              }
1400              push(new_id, right_id);
1401              pushRight(new_id, ~(classes[r].parent));
1402              setPrio(new_id);
1403
1404              id = nodes[id].parent;
1405              classes[r].parent = ~new_id;
1406            }
1407            if (id < 0) {
1408              int new_parent = newNode();
1409              nodes[new_parent].next = -1;
1410              nodes[new_parent].prev = -1;
1411              nodes[new_parent].parent = ~l;
1412
1413              push(new_parent, ~(classes[l].parent));
1414              pushRight(new_parent, ~(classes[r].parent));
1415              setPrio(new_parent);
1416
1417              classes[l].parent = ~new_parent;
1418              classes[l].depth += 1;
1419            } else {
1420              pushRight(id, ~(classes[r].parent));
1421              while (id >= 0 && less(~(classes[r].parent), id)) {
1422                nodes[id].prio = nodes[~(classes[r].parent)].prio;
1423                nodes[id].item = nodes[~(classes[r].parent)].item;
1424                id = nodes[id].parent;
1425              }
1426            }
1427          } else if (classes[r].depth > classes[l].depth) {
1428            int id = ~(classes[r].parent);
1429            for (int i = classes[l].depth + 1; i < classes[r].depth; ++i) {
1430              id = nodes[id].left;
1431            }
1432            while (id >= 0 && nodes[id].size == cmax) {
1433              int new_id = newNode();
1434              int left_id = nodes[id].left;
1435
1436              popLeft(id);
1437              if (nodes[id].prio == nodes[left_id].prio) {
1438                setPrio(id);
1439              }
1440              push(new_id, left_id);
1441              pushLeft(new_id, ~(classes[l].parent));
1442              setPrio(new_id);
1443
1444              id = nodes[id].parent;
1445              classes[l].parent = ~new_id;
1446
1447            }
1448            if (id < 0) {
1449              int new_parent = newNode();
1450              nodes[new_parent].next = -1;
1451              nodes[new_parent].prev = -1;
1452              nodes[new_parent].parent = ~l;
1453
1454              push(new_parent, ~(classes[r].parent));
1455              pushLeft(new_parent, ~(classes[l].parent));
1456              setPrio(new_parent);
1457             
1458              classes[r].parent = ~new_parent;
1459              classes[r].depth += 1;
1460            } else {
1461              pushLeft(id, ~(classes[l].parent));
1462              while (id >= 0 && less(~(classes[l].parent), id)) {
1463                nodes[id].prio = nodes[~(classes[l].parent)].prio;
1464                nodes[id].item = nodes[~(classes[l].parent)].item;
1465                id = nodes[id].parent;
1466              }
1467            }
1468            nodes[~(classes[r].parent)].parent = ~l;
1469            classes[l].parent = classes[r].parent;
1470            classes[l].depth = classes[r].depth;
1471          } else {
1472            if (classes[l].depth != 0 &&
1473                nodes[~(classes[l].parent)].size +
1474                nodes[~(classes[r].parent)].size <= cmax) {
1475              splice(~(classes[l].parent), ~(classes[r].parent));
1476              deleteNode(~(classes[r].parent));
1477              if (less(~(classes[r].parent), ~(classes[l].parent))) {
1478                nodes[~(classes[l].parent)].prio =
1479                  nodes[~(classes[r].parent)].prio;
1480                nodes[~(classes[l].parent)].item =
1481                  nodes[~(classes[r].parent)].item;
1482              }
1483            } else {
1484              int new_parent = newNode();
1485              nodes[new_parent].next = nodes[new_parent].prev = -1;
1486              push(new_parent, ~(classes[l].parent));
1487              pushRight(new_parent, ~(classes[r].parent));
1488              setPrio(new_parent);
1489           
1490              classes[l].parent = ~new_parent;
1491              classes[l].depth += 1;
1492              nodes[new_parent].parent = ~l;
1493            }
1494          }
1495          if (classes[r].next != -1) {
1496            classes[classes[r].next].prev = classes[r].prev;
1497          }
1498          classes[classes[r].prev].next = classes[r].next;
1499
1500          classes[r].prev = classes[l].right;
1501          classes[classes[l].right].next = r;
1502          classes[l].right = r;
1503          classes[r].parent = l;
1504
1505          classes[r].next = -1;
1506          classes[r].depth = rln;
1507        }
1508      }
1509      return class_id;
1510    }
1511
1512    /// \brief Split the class to subclasses.
1513    ///
1514    /// The current function splits the given class. The join, which
1515    /// made the current class, stored a reference to the
1516    /// subclasses. The \c splitClass() member restores the classes
1517    /// and creates the heaps. The parameter is an STL output iterator
1518    /// which will be filled with the subclass ids. The time
1519    /// complexity is O(log(n)*k) where n is the overall number of
1520    /// nodes in the splitted classes and k is the number of the
1521    /// classes.
1522    template <typename Iterator>
1523    void split(int cls, Iterator out) {
1524      std::vector<int> cs;
1525      { // splitting union-find
1526        int id = cls;
1527        int l = classes[id].left;
1528
1529        classes[l].parent = classes[id].parent;
1530        classes[l].depth = classes[id].depth;
1531
1532        nodes[~(classes[l].parent)].parent = ~l;
1533
1534        *out++ = l;
1535
1536        while (l != -1) {
1537          cs.push_back(l);
1538          l = classes[l].next;
1539        }
1540
1541        classes[classes[id].right].next = first_class;
1542        classes[first_class].prev = classes[id].right;
1543        first_class = classes[id].left;
1544       
1545        if (classes[id].next != -1) {
1546          classes[classes[id].next].prev = classes[id].prev;
1547        }
1548        classes[classes[id].prev].next = classes[id].next;
1549       
1550        deleteClass(id);
1551      }
1552
1553      {
1554        for (int i = 1; i < int(cs.size()); ++i) {
1555          int l = classes[cs[i]].depth;
1556          while (nodes[nodes[l].parent].left == l) {
1557            l = nodes[l].parent;
1558          }
1559          int r = l;   
1560          while (nodes[l].parent >= 0) {
1561            l = nodes[l].parent;
1562            int new_node = newNode();
1563
1564            nodes[new_node].prev = -1;
1565            nodes[new_node].next = -1;
1566
1567            split(r, new_node);
1568            pushAfter(l, new_node);
1569            setPrio(l);
1570            setPrio(new_node);
1571            r = new_node;
1572          }
1573          classes[cs[i]].parent = ~r;
1574          classes[cs[i]].depth = classes[~(nodes[l].parent)].depth;
1575          nodes[r].parent = ~cs[i];
1576
1577          nodes[l].next = -1;
1578          nodes[r].prev = -1;
1579
1580          repairRight(~(nodes[l].parent));
1581          repairLeft(cs[i]);
1582         
1583          *out++ = cs[i];
1584        }
1585      }
1586    }
1587
1588    /// \brief Gives back the priority of the current item.
1589    ///
1590    /// \return Gives back the priority of the current item.
1591    const Value& operator[](const Item& item) const {
1592      return nodes[index[item]].prio;
1593    }
1594
1595    /// \brief Sets the priority of the current item.
1596    ///
1597    /// Sets the priority of the current item.
1598    void set(const Item& item, const Value& prio) {
1599      if (comp(prio, nodes[index[item]].prio)) {
1600        decrease(item, prio);
1601      } else if (!comp(prio, nodes[index[item]].prio)) {
1602        increase(item, prio);
1603      }
1604    }
1605     
1606    /// \brief Increase the priority of the current item.
1607    ///
1608    /// Increase the priority of the current item.
1609    void increase(const Item& item, const Value& prio) {
1610      int id = index[item];
1611      int kd = nodes[id].parent;
1612      nodes[id].prio = prio;
1613      while (kd >= 0 && nodes[kd].item == item) {
1614        setPrio(kd);
1615        kd = nodes[kd].parent;
1616      }
1617    }
1618
1619    /// \brief Increase the priority of the current item.
1620    ///
1621    /// Increase the priority of the current item.
1622    void decrease(const Item& item, const Value& prio) {
1623      int id = index[item];
1624      int kd = nodes[id].parent;
1625      nodes[id].prio = prio;
1626      while (kd >= 0 && less(id, kd)) {
1627        nodes[kd].prio = prio;
1628        nodes[kd].item = item;
1629        kd = nodes[kd].parent;
1630      }
1631    }
1632   
1633    /// \brief Gives back the minimum priority of the class.
1634    ///
1635    /// \return Gives back the minimum priority of the class.
1636    const Value& classPrio(int cls) const {
1637      return nodes[~(classes[cls].parent)].prio;
1638    }
1639
1640    /// \brief Gives back the minimum priority item of the class.
1641    ///
1642    /// \return Gives back the minimum priority item of the class.
1643    const Item& classTop(int cls) const {
1644      return nodes[~(classes[cls].parent)].item;
1645    }
1646
1647    /// \brief Gives back a representant item of the class.
1648    ///
1649    /// The representant is indpendent from the priorities of the
1650    /// items.
1651    /// \return Gives back a representant item of the class.
1652    const Item& classRep(int id) const {
1653      int parent = classes[id].parent;
1654      return nodes[parent >= 0 ? classes[id].depth : leftNode(id)].item;
1655    }
1656
1657    /// \brief Lemon style iterator for the items of a class.
1658    ///
1659    /// ClassIt is a lemon style iterator for the components. It iterates
1660    /// on the items of a class. By example if you want to iterate on
1661    /// each items of each classes then you may write the next code.
1662    ///\code
1663    /// for (ClassIt cit(huf); cit != INVALID; ++cit) {
1664    ///   std::cout << "Class: ";
1665    ///   for (ItemIt iit(huf, cit); iit != INVALID; ++iit) {
1666    ///     std::cout << toString(iit) << ' ' << std::endl;
1667    ///   }
1668    ///   std::cout << std::endl;
1669    /// }
1670    ///\endcode
1671    class ItemIt {
1672    private:
1673
1674      const HeapUnionFind* _huf;
1675      int _id, _lid;
1676     
1677    public:
1678
1679      /// \brief Default constructor
1680      ///
1681      /// Default constructor
1682      ItemIt() {}
1683
1684      ItemIt(const HeapUnionFind& huf, int cls) : _huf(&huf) {
1685        int id = cls;
1686        int parent = _huf->classes[id].parent;
1687        if (parent >= 0) {
1688          _id = _huf->classes[id].depth;
1689          if (_huf->classes[id].next != -1) {
1690            _lid = _huf->classes[_huf->classes[id].next].depth;
1691          } else {
1692            _lid = -1;
1693          }
1694        } else {
1695          _id = _huf->leftNode(id);
1696          _lid = -1;
1697        }
1698      }
1699     
1700      /// \brief Increment operator
1701      ///
1702      /// It steps to the next item in the class.
1703      ItemIt& operator++() {
1704        _id = _huf->nextNode(_id);
1705        return *this;
1706      }
1707
1708      /// \brief Conversion operator
1709      ///
1710      /// It converts the iterator to the current item.
1711      operator const Item&() const {
1712        return _huf->nodes[_id].item;
1713      }
1714     
1715      /// \brief Equality operator
1716      ///
1717      /// Equality operator
1718      bool operator==(const ItemIt& i) {
1719        return i._id == _id;
1720      }
1721
1722      /// \brief Inequality operator
1723      ///
1724      /// Inequality operator
1725      bool operator!=(const ItemIt& i) {
1726        return i._id != _id;
1727      }
1728
1729      /// \brief Equality operator
1730      ///
1731      /// Equality operator
1732      bool operator==(Invalid) {
1733        return _id == _lid;
1734      }
1735
1736      /// \brief Inequality operator
1737      ///
1738      /// Inequality operator
1739      bool operator!=(Invalid) {
1740        return _id != _lid;
1741      }
1742     
1743    };
1744
1745    /// \brief Class iterator
1746    ///
1747    /// The iterator stores
1748    class ClassIt {
1749    private:
1750
1751      const HeapUnionFind* _huf;
1752      int _id;
1753
1754    public:
1755
1756      ClassIt(const HeapUnionFind& huf)
1757        : _huf(&huf), _id(huf.first_class) {}
1758
1759      ClassIt(const HeapUnionFind& huf, int cls)
1760        : _huf(&huf), _id(huf.classes[cls].left) {}
1761
1762      ClassIt(Invalid) : _huf(0), _id(-1) {}
1763     
1764      const ClassIt& operator++() {
1765        _id = _huf->classes[_id].next;
1766        return *this;
1767      }
1768
1769      /// \brief Equality operator
1770      ///
1771      /// Equality operator
1772      bool operator==(const ClassIt& i) {
1773        return i._id == _id;
1774      }
1775
1776      /// \brief Inequality operator
1777      ///
1778      /// Inequality operator
1779      bool operator!=(const ClassIt& i) {
1780        return i._id != _id;
1781      }     
1782     
1783      operator int() const {
1784        return _id;
1785      }
1786           
1787    };
1788
1789  };
1790
1791  //! @}
1792
1793} //namespace lemon
1794
1795#endif //LEMON_UNION_FIND_H
Note: See TracBrowser for help on using the repository browser.