COIN-OR::LEMON - Graph Library

source: lemon/lemon/unionfind.h @ 210:81cfc04531e8

Last change on this file since 210:81cfc04531e8 was 209:765619b7cbb2, checked in by Alpar Juttner <alpar@…>, 16 years ago

Apply unify-sources.sh to the source tree

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