COIN-OR::LEMON - Graph Library

Changeset 2505:1bb471764ab8 in lemon-0.x for lemon/unionfind.h


Ignore:
Timestamp:
10/30/07 21:21:10 (13 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3351
Message:

Redesign interface of MaxMatching? and UnionFindEnum?
New class ExtendFindEnum?

Faster MaxMatching?

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/unionfind.h

    r2427 r2505  
    179179  private:
    180180   
     181    ItemIntMap& index;
     182
    181183    // If the parent stores negative value for an item then that item
    182     // is root item and it has -items[it].parent component size.  Else
     184    // is root item and it has ~(items[it].parent) component id.  Else
    183185    // the items[it].parent contains the index of the parent.
    184186    //
    185     // The \c nextItem and \c prevItem provides the double-linked
    186     // cyclic list of one component's items. The \c prevClass and
    187     // \c nextClass gives the double linked list of the representant
    188     // items.
     187    // The \c next and \c prev provides the double-linked
     188    // cyclic list of one component's items.
    189189    struct ItemT {
    190190      int parent;
    191191      Item item;
    192192
    193       int nextItem, prevItem;
    194       int nextClass, prevClass;
     193      int next, prev;
    195194    };
    196195
    197196    std::vector<ItemT> items;
    198     ItemIntMap& index;
    199 
    200     int firstClass;
     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    }
    201231
    202232
     
    218248    }
    219249
    220     void unlaceClass(int k) {
    221       if (items[k].prevClass != -1) {
    222         items[items[k].prevClass].nextClass = items[k].nextClass;
     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;
    223295      } else {
    224         firstClass = items[k].nextClass;
    225       }
    226       if (items[k].nextClass != -1) {
    227         items[items[k].nextClass].prevClass = items[k].prevClass;
    228       }
     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;
    229304    }
    230305
    231     void spliceItems(int ak, int bk) {
    232       items[items[ak].prevItem].nextItem = bk;
    233       items[items[bk].prevItem].nextItem = ak;
    234       int tmp = items[ak].prevItem;
    235       items[ak].prevItem = items[bk].prevItem;
    236       items[bk].prevItem = tmp;
    237        
    238     }
    239 
    240306  public:
    241307
    242308    UnionFindEnum(ItemIntMap& _index)
    243       : items(), index(_index), firstClass(-1) {}
     309      : index(_index), items(), firstFreeItem(-1),
     310        firstClass(-1), firstFreeClass(-1) {}
    244311   
    245312    /// \brief Inserts the given element into a new component.
     
    248315    /// given element.
    249316    ///
    250     void insert(const Item& item) {
    251       ItemT t;
    252 
    253       int idx = items.size();
     317    int insert(const Item& item) {
     318      int idx = newItem();
     319
    254320      index.set(item, idx);
    255321
    256       t.nextItem = idx;
    257       t.prevItem = idx;
    258       t.item = item;
    259       t.parent = -1;
    260      
    261       t.nextClass = firstClass;
    262       if (firstClass != -1) {
    263         items[firstClass].prevClass = idx;
    264       }
    265       t.prevClass = -1;
    266       firstClass = idx;
    267 
    268       items.push_back(t);
     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;
    269336    }
    270337
     
    273340    /// This methods inserts the element \e a into the component of the
    274341    /// element \e comp.
    275     void insert(const Item& item, const Item& comp) {
    276       int k = repIndex(index[comp]);
    277       ItemT t;
    278 
    279       int idx = items.size();
     342    void insert(const Item& item, int cls) {
     343      int rdx = classes[cls].firstItem;
     344      int idx = newItem();
     345
    280346      index.set(item, idx);
    281347
    282       t.prevItem = k;
    283       t.nextItem = items[k].nextItem;
    284       items[items[k].nextItem].prevItem = idx;
    285       items[k].nextItem = idx;
    286 
    287       t.item = item;
    288       t.parent = k;
    289 
    290       --items[k].parent;
    291 
    292       items.push_back(t);
     348      laceItem(idx, rdx);
     349
     350      items[idx].item = item;
     351      items[idx].parent = rdx;
     352
     353      ++classes[~(items[rdx].parent)].size;
    293354    }
    294355
     
    299360      items.clear();
    300361      firstClass = -1;
    301     }
    302 
    303     /// \brief Finds the leader of the component of the given element.
    304     ///
    305     /// The method returns the leader of the component of the given element.
    306     const Item& find(const Item &item) const {
    307       return items[repIndex(index[item])].item;
     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);
    308370    }
    309371
     
    313375    /// Joins the component of element \e a and component of
    314376    /// element \e b. If \e a and \e b are in the same component then
    315     /// returns false else returns true.
    316     bool join(const Item& a, const Item& b) {
     377    /// returns -1 else returns the remaining class.
     378    int join(const Item& a, const Item& b) {
    317379
    318380      int ak = repIndex(index[a]);
     
    320382
    321383      if (ak == bk) {
    322         return false;
    323       }
    324 
    325       if ( items[ak].parent < items[bk].parent ) {
    326         unlaceClass(bk);
    327         items[ak].parent += items[bk].parent;
     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;
    328394        items[bk].parent = ak;
     395        unlaceClass(bcx);
     396        rcx = acx;
    329397      } else {
    330         unlaceClass(ak);
    331         items[bk].parent += items[ak].parent;
     398        classes[bcx].size += classes[acx].size;
    332399        items[ak].parent = bk;
     400        unlaceClass(acx);
     401        rcx = bcx;
    333402      }
    334403      spliceItems(ak, bk);
    335404
    336       return true;
    337     }
    338 
    339     /// \brief Returns the size of the component of element \e a.
    340     ///
    341     /// Returns the size of the component of element \e a.
    342     int size(const Item &item) const {
    343       return - items[repIndex(index[item])].parent;
    344     }
    345 
    346     /// \brief Splits up the component of the element.
    347     ///
    348     /// Splitting the component of the element into sigleton
    349     /// components (component of size one).
    350     void split(const Item &item) {
    351       int k = repIndex(index[item]);
    352       int idx = items[k].nextItem;
    353       while (idx != k) {
    354         int next = items[idx].nextItem;
     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;
    355433       
    356         items[idx].parent = -1;
    357         items[idx].prevItem = idx;
    358         items[idx].nextItem = idx;
    359        
    360         items[idx].nextClass = firstClass;
    361         items[firstClass].prevClass = idx;
    362         firstClass = idx;
    363 
    364434        idx = next;
    365435      }
    366436
    367       items[idx].parent = -1;
    368       items[idx].prevItem = idx;
    369       items[idx].nextItem = idx;
    370      
    371       items[firstClass].prevClass = -1;
    372     }
    373 
    374     /// \brief Sets the given element to the leader element of its component.
    375     ///
    376     /// Sets the given element to the leader element of its component.
    377     void makeRep(const Item &item) {
    378       int nk = index[item];
    379       int k = repIndex(nk);
    380       if (nk == k) return;
    381      
    382       if (items[k].prevClass != -1) {
    383         items[items[k].prevClass].nextClass = nk;
    384       } else {
    385         firstClass = nk;
    386       }
    387       if (items[k].nextClass != -1) {
    388         items[items[k].nextClass].prevClass = nk;
    389       }
    390      
    391       int idx = items[k].nextItem;
    392       while (idx != k) {
    393         items[idx].parent = nk;
    394         idx = items[idx].nextItem;
    395       }
    396      
    397       items[nk].parent = items[k].parent;
    398       items[k].parent = nk;
     437      items[idx].prev = idx;
     438      items[idx].next = idx;
     439
     440      classes[~(items[idx].parent)].size = 1;
     441     
    399442    }
    400443
     
    406449    /// \warning It is an error to remove an element which is not in
    407450    /// the structure.
    408     void erase(const Item &item) {
     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) {
    409454      int idx = index[item];
    410       if (rep(idx)) {
    411         int k = idx;
    412         if (items[k].parent == -1) {
    413           unlaceClass(idx);
    414           return;
    415         } else {
    416           int nk = items[k].nextItem;
    417           if (items[k].prevClass != -1) {
    418             items[items[k].prevClass].nextClass = nk;
    419           } else {
    420             firstClass = nk;
    421           }
    422           if (items[k].nextClass != -1) {
    423             items[items[k].nextClass].prevClass = nk;
    424           }
    425      
    426           int l = items[k].nextItem;
    427           while (l != k) {
    428             items[l].parent = nk;
    429             l = items[l].nextItem;
    430           }
     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        }
    431474         
    432           items[nk].parent = items[k].parent + 1;
    433         }
    434       } else {
    435        
    436         int k = repIndex(idx);
    437         idx = items[k].nextItem;
    438         while (idx != k) {
    439           items[idx].parent = k;
    440           idx = items[idx].nextItem;
    441         }
    442 
    443         ++items[k].parent;
    444       }
    445 
    446       idx = index[item];     
    447       items[items[idx].prevItem].nextItem = items[idx].nextItem;
    448       items[items[idx].nextItem].prevItem = items[idx].prevItem;
     475      }
    449476
    450477    }   
    451 
    452     /// \brief Moves the given element to another component.
    453     ///
    454     /// This method moves the element \e a from its component
    455     /// to the component of \e comp.
    456     /// If \e a and \e comp are in the same component then
    457     /// it returns false otherwise it returns true.
    458     bool move(const Item &item, const Item &comp) {
    459       if (repIndex(index[item]) == repIndex(index[comp])) return false;
    460       erase(item);
    461       insert(item, comp);
    462       return true;
    463     }
    464 
    465478
    466479    /// \brief Removes the component of the given element from the structure.
     
    470483    /// \warning It is an error to give an element which is not in the
    471484    /// structure.
    472     void eraseClass(const Item &item) {
    473       unlaceClass(repIndex(index[item]));
     485    void eraseClass(int cls) {
     486      int fdx = classes[cls].firstItem;
     487      unlaceClass(cls);
     488      items[items[fdx].prev].next = firstFreeItem;
     489      firstFreeItem = fdx;
    474490    }
    475491
     
    477493    ///
    478494    /// ClassIt is a lemon style iterator for the components. It iterates
    479     /// on the representant items of the classes.
     495    /// on the ids of the classes.
    480496    class ClassIt {
    481497    public:
     
    484500      /// Constructor of the iterator
    485501      ClassIt(const UnionFindEnum& ufe) : unionFind(&ufe) {
    486         idx = unionFind->firstClass;
     502        cdx = unionFind->firstClass;
    487503      }
    488504
     
    490506      ///
    491507      /// Constructor to get invalid iterator
    492       ClassIt(Invalid) : unionFind(0), idx(-1) {}
     508      ClassIt(Invalid) : unionFind(0), cdx(-1) {}
    493509     
    494510      /// \brief Increment operator
     
    496512      /// It steps to the next representant item.
    497513      ClassIt& operator++() {
    498         idx = unionFind->items[idx].nextClass;
     514        cdx = unionFind->classes[cdx].next;
    499515        return *this;
    500516      }
     
    503519      ///
    504520      /// It converts the iterator to the current representant item.
    505       operator const Item&() const {
    506         return unionFind->items[idx].item;
     521      operator int() const {
     522        return cdx;
    507523      }
    508524
     
    511527      /// Equality operator
    512528      bool operator==(const ClassIt& i) {
    513         return i.idx == idx;
     529        return i.cdx == cdx;
    514530      }
    515531
     
    518534      /// Inequality operator
    519535      bool operator!=(const ClassIt& i) {
    520         return i.idx != idx;
     536        return i.cdx != cdx;
    521537      }
    522538     
    523539    private:
    524540      const UnionFindEnum* unionFind;
    525       int idx;
     541      int cdx;
    526542    };
    527543
     
    546562      /// Constructor of the iterator. The iterator iterates
    547563      /// on the class of the \c item.
    548       ItemIt(const UnionFindEnum& ufe, const Item& item) : unionFind(&ufe) {
    549         idx = unionFind->repIndex(unionFind->index[item]);
     564      ItemIt(const UnionFindEnum& ufe, int cls) : unionFind(&ufe) {
     565        fdx = idx = unionFind->classes[cls].firstItem;
    550566      }
    551567
     
    559575      /// It steps to the next item in the class.
    560576      ItemIt& operator++() {
    561         idx = unionFind->items[idx].nextItem;
    562         if (unionFind->rep(idx)) idx = -1;
     577        idx = unionFind->items[idx].next;
     578        if (idx == fdx) idx = -1;
    563579        return *this;
    564580      }
     
    587603    private:
    588604      const UnionFindEnum* unionFind;
    589       int idx;
     605      int idx, fdx;
    590606    };
    591607
    592608  };
    593609
     610  /// \ingroup auxdat
     611  ///
     612  /// \brief A \e Extend-Find data structure implementation which
     613  /// is able to enumerate the components.
     614  ///
     615  /// The class implements an \e Extend-Find data structure which is
     616  /// able to enumerate the components and the items in a
     617  /// component. The data structure is a simplification of the
     618  /// Union-Find structure, and it does not allow to merge two components.
     619  ///
     620  /// \pre You need to add all the elements by the \ref insert()
     621  /// method.
     622  template <typename _ItemIntMap>
     623  class ExtendFindEnum {
     624  public:
     625   
     626    typedef _ItemIntMap ItemIntMap;
     627    typedef typename ItemIntMap::Key Item;
     628
     629  private:
     630   
     631    ItemIntMap& index;
     632
     633    struct ItemT {
     634      int cls;
     635      Item item;
     636      int next, prev;
     637    };
     638
     639    std::vector<ItemT> items;
     640    int firstFreeItem;
     641
     642    struct ClassT {
     643      int firstItem;
     644      int next, prev;
     645    };
     646
     647    std::vector<ClassT> classes;
     648
     649    int firstClass, firstFreeClass;
     650
     651    int newClass() {
     652      if (firstFreeClass != -1) {
     653        int cdx = firstFreeClass;
     654        firstFreeClass = classes[cdx].next;
     655        return cdx;
     656      } else {
     657        classes.push_back(ClassT());
     658        return classes.size() - 1;
     659      }
     660    }
     661
     662    int newItem() {
     663      if (firstFreeItem != -1) {
     664        int idx = firstFreeItem;
     665        firstFreeItem = items[idx].next;
     666        return idx;
     667      } else {
     668        items.push_back(ItemT());
     669        return items.size() - 1;
     670      }
     671    }
     672
     673  public:
     674
     675    /// \brief Constructor
     676    ExtendFindEnum(ItemIntMap& _index)
     677      : index(_index), items(), firstFreeItem(-1),
     678        classes(), firstClass(-1), firstFreeClass(-1) {}
     679   
     680    /// \brief Inserts the given element into a new component.
     681    ///
     682    /// This method creates a new component consisting only of the
     683    /// given element.
     684    int insert(const Item& item) {
     685      int cdx = newClass();
     686      classes[cdx].prev = -1;
     687      classes[cdx].next = firstClass;
     688      firstClass = cdx;
     689     
     690      int idx = newItem();
     691      items[idx].item = item;
     692      items[idx].cls = cdx;
     693      items[idx].prev = idx;
     694      items[idx].next = idx;
     695
     696      classes[cdx].firstItem = idx;
     697
     698      index.set(item, idx);
     699     
     700      return cdx;
     701    }
     702
     703    /// \brief Inserts the given element into the given component.
     704    ///
     705    /// This methods inserts the element \e item a into the \e cls class.
     706    void insert(const Item& item, int cls) {
     707      int idx = newItem();
     708      int rdx = classes[cls].firstItem;
     709      items[idx].item = item;
     710      items[idx].cls = cls;
     711
     712      items[idx].prev = rdx;
     713      items[idx].next = items[rdx].next;
     714      items[items[rdx].next].prev = idx;
     715      items[rdx].next = idx;
     716
     717      index.set(item, idx);
     718    }
     719
     720    /// \brief Clears the union-find data structure
     721    ///
     722    /// Erase each item from the data structure.
     723    void clear() {
     724      items.clear();
     725      classes.clear;
     726      firstClass = firstFreeClass = firstFreeItem = -1;
     727    }
     728
     729    /// \brief Gives back the class of the \e item.
     730    ///
     731    /// Gives back the class of the \e item.
     732    int find(const Item &item) const {
     733      return items[index[item]].cls;
     734    }
     735   
     736    /// \brief Removes the given element from the structure.
     737    ///
     738    /// Removes the element from its component and if the component becomes
     739    /// empty then removes that component from the component list.
     740    ///
     741    /// \warning It is an error to remove an element which is not in
     742    /// the structure.
     743    void erase(const Item &item) {
     744      int idx = index[item];
     745      int cdx = items[idx].cls;
     746     
     747      if (idx == items[idx].next) {
     748        if (classes[cdx].prev != -1) {
     749          classes[classes[cdx].prev].next = classes[cdx].next;
     750        } else {
     751          firstClass = classes[cdx].next;
     752        }
     753        if (classes[cdx].next != -1) {
     754          classes[classes[cdx].next].prev = classes[cdx].prev;
     755        }
     756        classes[cdx].next = firstFreeClass;
     757        firstFreeClass = cdx;
     758      } else {
     759        classes[cdx].firstItem = items[idx].next;
     760        items[items[idx].next].prev = items[idx].prev;
     761        items[items[idx].prev].next = items[idx].next;
     762      }
     763      items[idx].next = firstFreeItem;
     764      firstFreeItem = idx;
     765       
     766    }   
     767
     768   
     769    /// \brief Removes the component of the given element from the structure.
     770    ///
     771    /// Removes the component of the given element from the structure.
     772    ///
     773    /// \warning It is an error to give an element which is not in the
     774    /// structure.
     775    void eraseClass(int cdx) {
     776      int idx = classes[cdx].firstItem;
     777      items[items[idx].prev].next = firstFreeItem;
     778      firstFreeItem = idx;
     779
     780      if (classes[cdx].prev != -1) {
     781        classes[classes[cdx].prev].next = classes[cdx].next;
     782      } else {
     783        firstClass = classes[cdx].next;
     784      }
     785      if (classes[cdx].next != -1) {
     786        classes[classes[cdx].next].prev = classes[cdx].prev;
     787      }
     788      classes[cdx].next = firstFreeClass;
     789      firstFreeClass = cdx;
     790    }
     791
     792    /// \brief Lemon style iterator for the classes.
     793    ///
     794    /// ClassIt is a lemon style iterator for the components. It iterates
     795    /// on the ids of classes.
     796    class ClassIt {
     797    public:
     798      /// \brief Constructor of the iterator
     799      ///
     800      /// Constructor of the iterator
     801      ClassIt(const ExtendFindEnum& ufe) : extendFind(&ufe) {
     802        cdx = extendFind->firstClass;
     803      }
     804
     805      /// \brief Constructor to get invalid iterator
     806      ///
     807      /// Constructor to get invalid iterator
     808      ClassIt(Invalid) : extendFind(0), cdx(-1) {}
     809     
     810      /// \brief Increment operator
     811      ///
     812      /// It steps to the next representant item.
     813      ClassIt& operator++() {
     814        cdx = extendFind->classes[cdx].next;
     815        return *this;
     816      }
     817     
     818      /// \brief Conversion operator
     819      ///
     820      /// It converts the iterator to the current class id.
     821      operator int() const {
     822        return cdx;
     823      }
     824
     825      /// \brief Equality operator
     826      ///
     827      /// Equality operator
     828      bool operator==(const ClassIt& i) {
     829        return i.cdx == cdx;
     830      }
     831
     832      /// \brief Inequality operator
     833      ///
     834      /// Inequality operator
     835      bool operator!=(const ClassIt& i) {
     836        return i.cdx != cdx;
     837      }
     838     
     839    private:
     840      const ExtendFindEnum* extendFind;
     841      int cdx;
     842    };
     843
     844    /// \brief Lemon style iterator for the items of a component.
     845    ///
     846    /// ClassIt is a lemon style iterator for the components. It iterates
     847    /// on the items of a class. By example if you want to iterate on
     848    /// each items of each classes then you may write the next code.
     849    ///\code
     850    /// for (ClassIt cit(ufe); cit != INVALID; ++cit) {
     851    ///   std::cout << "Class: ";
     852    ///   for (ItemIt iit(ufe, cit); iit != INVALID; ++iit) {
     853    ///     std::cout << toString(iit) << ' ' << std::endl;
     854    ///   }
     855    ///   std::cout << std::endl;
     856    /// }
     857    ///\endcode
     858    class ItemIt {
     859    public:
     860      /// \brief Constructor of the iterator
     861      ///
     862      /// Constructor of the iterator. The iterator iterates
     863      /// on the class of the \c item.
     864      ItemIt(const ExtendFindEnum& ufe, int cls) : extendFind(&ufe) {
     865        fdx = idx = extendFind->classes[cls].firstItem;
     866      }
     867
     868      /// \brief Constructor to get invalid iterator
     869      ///
     870      /// Constructor to get invalid iterator
     871      ItemIt(Invalid) : extendFind(0), idx(-1) {}
     872     
     873      /// \brief Increment operator
     874      ///
     875      /// It steps to the next item in the class.
     876      ItemIt& operator++() {
     877        idx = extendFind->items[idx].next;
     878        if (fdx == idx) idx = -1;
     879        return *this;
     880      }
     881     
     882      /// \brief Conversion operator
     883      ///
     884      /// It converts the iterator to the current item.
     885      operator const Item&() const {
     886        return extendFind->items[idx].item;
     887      }
     888
     889      /// \brief Equality operator
     890      ///
     891      /// Equality operator
     892      bool operator==(const ItemIt& i) {
     893        return i.idx == idx;
     894      }
     895
     896      /// \brief Inequality operator
     897      ///
     898      /// Inequality operator
     899      bool operator!=(const ItemIt& i) {
     900        return i.idx != idx;
     901      }
     902     
     903    private:
     904      const ExtendFindEnum* extendFind;
     905      int idx, fdx;
     906    };
     907
     908  };
    594909
    595910  //! @}
Note: See TracChangeset for help on using the changeset viewer.