COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/unionfind.h @ 2533:aea952a1af99

Last change on this file since 2533:aea952a1af99 was 2506:216c6bd5c18c, checked in by Balazs Dezso, 16 years ago

Change to new union-find interface

File size: 23.7 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      firstClass = cdx;
696     
697      int idx = newItem();
698      items[idx].item = item;
699      items[idx].cls = cdx;
700      items[idx].prev = idx;
701      items[idx].next = idx;
702
703      classes[cdx].firstItem = idx;
704
705      index.set(item, idx);
706     
707      return cdx;
708    }
709
710    /// \brief Inserts the given element into the given component.
711    ///
712    /// This methods inserts the element \e item a into the \e cls class.
713    void insert(const Item& item, int cls) {
714      int idx = newItem();
715      int rdx = classes[cls].firstItem;
716      items[idx].item = item;
717      items[idx].cls = cls;
718
719      items[idx].prev = rdx;
720      items[idx].next = items[rdx].next;
721      items[items[rdx].next].prev = idx;
722      items[rdx].next = idx;
723
724      index.set(item, idx);
725    }
726
727    /// \brief Clears the union-find data structure
728    ///
729    /// Erase each item from the data structure.
730    void clear() {
731      items.clear();
732      classes.clear;
733      firstClass = firstFreeClass = firstFreeItem = -1;
734    }
735
736    /// \brief Gives back the class of the \e item.
737    ///
738    /// Gives back the class of the \e item.
739    int find(const Item &item) const {
740      return items[index[item]].cls;
741    }
742
743    /// \brief Gives back a representant item of the component.
744    ///
745    /// Gives back a representant item of the component.
746    Item item(int cls) const {
747      return items[classes[cls].firstItem].item;
748    }
749   
750    /// \brief Removes the given element from the structure.
751    ///
752    /// Removes the element from its component and if the component becomes
753    /// empty then removes that component from the component list.
754    ///
755    /// \warning It is an error to remove an element which is not in
756    /// the structure.
757    void erase(const Item &item) {
758      int idx = index[item];
759      int cdx = items[idx].cls;
760     
761      if (idx == items[idx].next) {
762        if (classes[cdx].prev != -1) {
763          classes[classes[cdx].prev].next = classes[cdx].next;
764        } else {
765          firstClass = classes[cdx].next;
766        }
767        if (classes[cdx].next != -1) {
768          classes[classes[cdx].next].prev = classes[cdx].prev;
769        }
770        classes[cdx].next = firstFreeClass;
771        firstFreeClass = cdx;
772      } else {
773        classes[cdx].firstItem = items[idx].next;
774        items[items[idx].next].prev = items[idx].prev;
775        items[items[idx].prev].next = items[idx].next;
776      }
777      items[idx].next = firstFreeItem;
778      firstFreeItem = idx;
779       
780    }   
781
782   
783    /// \brief Removes the component of the given element from the structure.
784    ///
785    /// Removes the component of the given element from the structure.
786    ///
787    /// \warning It is an error to give an element which is not in the
788    /// structure.
789    void eraseClass(int cdx) {
790      int idx = classes[cdx].firstItem;
791      items[items[idx].prev].next = firstFreeItem;
792      firstFreeItem = idx;
793
794      if (classes[cdx].prev != -1) {
795        classes[classes[cdx].prev].next = classes[cdx].next;
796      } else {
797        firstClass = classes[cdx].next;
798      }
799      if (classes[cdx].next != -1) {
800        classes[classes[cdx].next].prev = classes[cdx].prev;
801      }
802      classes[cdx].next = firstFreeClass;
803      firstFreeClass = cdx;
804    }
805
806    /// \brief Lemon style iterator for the classes.
807    ///
808    /// ClassIt is a lemon style iterator for the components. It iterates
809    /// on the ids of classes.
810    class ClassIt {
811    public:
812      /// \brief Constructor of the iterator
813      ///
814      /// Constructor of the iterator
815      ClassIt(const ExtendFindEnum& ufe) : extendFind(&ufe) {
816        cdx = extendFind->firstClass;
817      }
818
819      /// \brief Constructor to get invalid iterator
820      ///
821      /// Constructor to get invalid iterator
822      ClassIt(Invalid) : extendFind(0), cdx(-1) {}
823     
824      /// \brief Increment operator
825      ///
826      /// It steps to the next representant item.
827      ClassIt& operator++() {
828        cdx = extendFind->classes[cdx].next;
829        return *this;
830      }
831     
832      /// \brief Conversion operator
833      ///
834      /// It converts the iterator to the current class id.
835      operator int() const {
836        return cdx;
837      }
838
839      /// \brief Equality operator
840      ///
841      /// Equality operator
842      bool operator==(const ClassIt& i) {
843        return i.cdx == cdx;
844      }
845
846      /// \brief Inequality operator
847      ///
848      /// Inequality operator
849      bool operator!=(const ClassIt& i) {
850        return i.cdx != cdx;
851      }
852     
853    private:
854      const ExtendFindEnum* extendFind;
855      int cdx;
856    };
857
858    /// \brief Lemon style iterator for the items of a component.
859    ///
860    /// ClassIt is a lemon style iterator for the components. It iterates
861    /// on the items of a class. By example if you want to iterate on
862    /// each items of each classes then you may write the next code.
863    ///\code
864    /// for (ClassIt cit(ufe); cit != INVALID; ++cit) {
865    ///   std::cout << "Class: ";
866    ///   for (ItemIt iit(ufe, cit); iit != INVALID; ++iit) {
867    ///     std::cout << toString(iit) << ' ' << std::endl;
868    ///   }
869    ///   std::cout << std::endl;
870    /// }
871    ///\endcode
872    class ItemIt {
873    public:
874      /// \brief Constructor of the iterator
875      ///
876      /// Constructor of the iterator. The iterator iterates
877      /// on the class of the \c item.
878      ItemIt(const ExtendFindEnum& ufe, int cls) : extendFind(&ufe) {
879        fdx = idx = extendFind->classes[cls].firstItem;
880      }
881
882      /// \brief Constructor to get invalid iterator
883      ///
884      /// Constructor to get invalid iterator
885      ItemIt(Invalid) : extendFind(0), idx(-1) {}
886     
887      /// \brief Increment operator
888      ///
889      /// It steps to the next item in the class.
890      ItemIt& operator++() {
891        idx = extendFind->items[idx].next;
892        if (fdx == idx) idx = -1;
893        return *this;
894      }
895     
896      /// \brief Conversion operator
897      ///
898      /// It converts the iterator to the current item.
899      operator const Item&() const {
900        return extendFind->items[idx].item;
901      }
902
903      /// \brief Equality operator
904      ///
905      /// Equality operator
906      bool operator==(const ItemIt& i) {
907        return i.idx == idx;
908      }
909
910      /// \brief Inequality operator
911      ///
912      /// Inequality operator
913      bool operator!=(const ItemIt& i) {
914        return i.idx != idx;
915      }
916     
917    private:
918      const ExtendFindEnum* extendFind;
919      int idx, fdx;
920    };
921
922  };
923
924  //! @}
925
926} //namespace lemon
927
928#endif //LEMON_UNION_FIND_H
Note: See TracBrowser for help on using the repository browser.