src/hugo/unionfind.h
author marci
Wed, 01 Sep 2004 09:04:07 +0000
changeset 779 83c49c272679
parent 649 ce74706e924d
child 810 e9fbc747ca47
permissions -rw-r--r--
correction
beckerjc@483
     1
// -*- c++ -*- //
beckerjc@483
     2
#ifndef HUGO_UNION_FIND_H
beckerjc@483
     3
#define HUGO_UNION_FIND_H
beckerjc@483
     4
klao@491
     5
//!\ingroup auxdat
beckerjc@483
     6
//!\file
beckerjc@483
     7
//!\brief Union-Find data structures.
alpar@774
     8
//!
alpar@774
     9
//!\bug unionfind_test.cc doesn't work with Intel compiler. It compiles but
alpar@774
    10
//!fails to run (Segmentation fault).
beckerjc@483
    11
beckerjc@483
    12
beckerjc@483
    13
#include <vector>
beckerjc@483
    14
#include <list>
beckerjc@483
    15
#include <utility>
beckerjc@483
    16
#include <algorithm>
beckerjc@483
    17
ladanyi@542
    18
#include <hugo/invalid.h>
beckerjc@483
    19
beckerjc@483
    20
namespace hugo {
beckerjc@483
    21
beckerjc@483
    22
  //! \addtogroup auxdat
beckerjc@483
    23
  //! @{
beckerjc@483
    24
beckerjc@483
    25
  /**
beckerjc@483
    26
   * \brief A \e Union-Find data structure implementation
beckerjc@483
    27
   *
beckerjc@483
    28
   * The class implements the \e Union-Find data structure. 
beckerjc@483
    29
   * The union operation uses rank heuristic, while
athos@649
    30
   * the find operation uses path compression.
beckerjc@483
    31
   * This is a very simple but efficient implementation, providing 
beckerjc@483
    32
   * only four methods: join (union), find, insert and size.
beckerjc@483
    33
   * For more features see the \ref UnionFindEnum class.
beckerjc@483
    34
   *
beckerjc@483
    35
   * \pre The elements are automatically added only if the map 
beckerjc@483
    36
   * given to the constructor was filled with -1's. Otherwise you
beckerjc@483
    37
   * need to add all the elements by the \ref insert() method.
beckerjc@483
    38
   */
beckerjc@483
    39
beckerjc@483
    40
  template <typename T, typename TIntMap>
beckerjc@483
    41
  class UnionFind {
beckerjc@483
    42
    
beckerjc@483
    43
  public:
beckerjc@483
    44
    typedef T ElementType;
beckerjc@483
    45
    typedef std::pair<int,int> PairType;
beckerjc@483
    46
beckerjc@483
    47
  private:
beckerjc@483
    48
    std::vector<PairType> data;
beckerjc@483
    49
    TIntMap& map;
beckerjc@483
    50
beckerjc@483
    51
  public:
beckerjc@483
    52
    UnionFind(TIntMap& m) : map(m) {}
beckerjc@483
    53
beckerjc@483
    54
    /**
beckerjc@483
    55
     * \brief Returns the index of the element's component.
beckerjc@483
    56
     *
beckerjc@483
    57
     * The method returns the index of the element's component.
beckerjc@483
    58
     * This is an integer between zero and the number of inserted elements.
beckerjc@483
    59
     */
beckerjc@483
    60
beckerjc@483
    61
    int find(T a)
beckerjc@483
    62
    {
beckerjc@483
    63
      int comp0 = map[a];
beckerjc@483
    64
      if (comp0 < 0) {
beckerjc@483
    65
	return insert(a);
beckerjc@483
    66
      }
beckerjc@483
    67
      int comp = comp0;
beckerjc@483
    68
      int next;
beckerjc@483
    69
      while ( (next = data[comp].first) != comp) {
beckerjc@483
    70
	comp = next;
beckerjc@483
    71
      }
beckerjc@483
    72
      while ( (next = data[comp0].first) != comp) {
beckerjc@483
    73
	data[comp0].first = comp;
beckerjc@483
    74
	comp0 = next;
beckerjc@483
    75
      }
beckerjc@483
    76
beckerjc@483
    77
      return comp;
beckerjc@483
    78
    }
beckerjc@483
    79
beckerjc@483
    80
    /**
beckerjc@483
    81
     * \brief Insert a new element into the structure.
beckerjc@483
    82
     *
beckerjc@483
    83
     * This method inserts a new element into the data structure. 
beckerjc@483
    84
     *
beckerjc@483
    85
     * It is not required to use this method:
beckerjc@483
    86
     * if the map given to the constructor was filled 
beckerjc@483
    87
     * with -1's then it is called automatically
beckerjc@483
    88
     * on the first \ref find or \ref join.
beckerjc@483
    89
     *
beckerjc@483
    90
     * The method returns the index of the new component.
beckerjc@483
    91
     */
beckerjc@483
    92
beckerjc@483
    93
    int insert(T a)
beckerjc@483
    94
    {
beckerjc@483
    95
      int n = data.size();
beckerjc@483
    96
      data.push_back(std::make_pair(n, 1));
beckerjc@483
    97
      map.set(a,n);
beckerjc@483
    98
      return n;
beckerjc@483
    99
    }
beckerjc@483
   100
beckerjc@483
   101
    /**
beckerjc@483
   102
     * \brief Joining the components of element \e a and element \e b.
beckerjc@483
   103
     *
beckerjc@483
   104
     * This is the \e union operation of the Union-Find structure. 
beckerjc@483
   105
     * Joins the component of elemenent \e a and component of
beckerjc@483
   106
     * element \e b. If \e a and \e b are in the same component then
beckerjc@483
   107
     * it returns false otherwise it returns true.
beckerjc@483
   108
     */
beckerjc@483
   109
beckerjc@483
   110
    bool join(T a, T b)
beckerjc@483
   111
    {
beckerjc@483
   112
      int ca = find(a);
beckerjc@483
   113
      int cb = find(b);
beckerjc@483
   114
beckerjc@483
   115
      if ( ca == cb ) 
beckerjc@483
   116
	return false;
beckerjc@483
   117
beckerjc@483
   118
      if ( data[ca].second > data[cb].second ) {
beckerjc@483
   119
	data[cb].first = ca;
beckerjc@483
   120
	data[ca].second += data[cb].second;
beckerjc@483
   121
      }
beckerjc@483
   122
      else {
beckerjc@483
   123
	data[ca].first = cb;
beckerjc@483
   124
	data[cb].second += data[ca].second;
beckerjc@483
   125
      }
beckerjc@483
   126
      return true;
beckerjc@483
   127
    }
beckerjc@483
   128
beckerjc@483
   129
    /**
beckerjc@483
   130
     * \brief Returns the size of the component of element \e a.
beckerjc@483
   131
     *
beckerjc@483
   132
     * Returns the size of the component of element \e a.
beckerjc@483
   133
     */
beckerjc@483
   134
beckerjc@483
   135
    int size(T a)
beckerjc@483
   136
    {
beckerjc@483
   137
      int ca = find(a);
beckerjc@483
   138
      return data[ca].second;
beckerjc@483
   139
    }
beckerjc@483
   140
beckerjc@483
   141
  };
beckerjc@483
   142
beckerjc@483
   143
beckerjc@483
   144
beckerjc@483
   145
beckerjc@483
   146
  /*******************************************************/
beckerjc@483
   147
beckerjc@483
   148
beckerjc@483
   149
#ifdef DEVELOPMENT_DOCS
beckerjc@483
   150
beckerjc@483
   151
  /**
beckerjc@483
   152
   * \brief The auxiliary class for the \ref UnionFindEnum class.
beckerjc@483
   153
   *
beckerjc@483
   154
   * In the \ref UnionFindEnum class all components are represented as
beckerjc@483
   155
   * a std::list. 
beckerjc@483
   156
   * Items of these lists are UnionFindEnumItem structures.
beckerjc@483
   157
   *
beckerjc@483
   158
   * The class has four fields:
beckerjc@483
   159
   *  - T me - the actual element 
beckerjc@483
   160
   *  - IIter parent - the parent of the element in the union-find structure
beckerjc@483
   161
   *  - int size - the size of the component of the element. 
beckerjc@483
   162
   *            Only valid if the element
beckerjc@483
   163
   *            is the leader of the component.
beckerjc@483
   164
   *  - CIter my_class - pointer into the list of components 
beckerjc@483
   165
   *            pointing to the component of the element.
beckerjc@483
   166
   *            Only valid if the element is the leader of the component.
beckerjc@483
   167
   */
beckerjc@483
   168
beckerjc@483
   169
#endif
beckerjc@483
   170
beckerjc@483
   171
  template <typename T>
beckerjc@483
   172
  struct UnionFindEnumItem {
beckerjc@483
   173
beckerjc@483
   174
    typedef std::list<UnionFindEnumItem> ItemList;
beckerjc@483
   175
    typedef std::list<ItemList> ClassList;
beckerjc@483
   176
    typedef typename ItemList::iterator IIter;
beckerjc@483
   177
    typedef typename ClassList::iterator CIter;
beckerjc@483
   178
beckerjc@483
   179
    T me;
beckerjc@483
   180
    IIter parent;
beckerjc@483
   181
    int size;
beckerjc@483
   182
    CIter my_class;
beckerjc@483
   183
beckerjc@483
   184
    UnionFindEnumItem() {}
beckerjc@483
   185
    UnionFindEnumItem(const T &_me, CIter _my_class): 
beckerjc@483
   186
      me(_me), size(1), my_class(_my_class) {}
beckerjc@483
   187
  };
beckerjc@483
   188
beckerjc@483
   189
beckerjc@483
   190
  /**
beckerjc@483
   191
   * \brief A \e Union-Find data structure implementation which
beckerjc@483
   192
   * is able to enumerate the components.
beckerjc@483
   193
   *
athos@649
   194
   * The class implements a \e Union-Find data structure
beckerjc@483
   195
   * which is able to enumerate the components and the items in
beckerjc@483
   196
   * a component. If you don't need this feature then perhaps it's
beckerjc@483
   197
   * better to use the \ref UnionFind class which is more efficient.
beckerjc@483
   198
   *
beckerjc@483
   199
   * The union operation uses rank heuristic, while
athos@649
   200
   * the find operation uses path compression.
beckerjc@483
   201
   *
beckerjc@483
   202
   * \pre You
beckerjc@483
   203
   * need to add all the elements by the \ref insert() method.
beckerjc@483
   204
   */
beckerjc@483
   205
beckerjc@483
   206
beckerjc@483
   207
  template <typename T, template <typename Item> class Map>
beckerjc@483
   208
  class UnionFindEnum {
beckerjc@483
   209
beckerjc@483
   210
    typedef std::list<UnionFindEnumItem<T> > ItemList;
beckerjc@483
   211
    typedef std::list<ItemList> ClassList;
beckerjc@483
   212
    typedef typename ItemList::iterator IIter;
beckerjc@483
   213
    typedef typename ItemList::const_iterator IcIter;
beckerjc@483
   214
    typedef typename ClassList::iterator CIter;
beckerjc@483
   215
    typedef typename ClassList::const_iterator CcIter;
beckerjc@483
   216
beckerjc@483
   217
  public:
beckerjc@483
   218
    typedef T ElementType;
beckerjc@483
   219
    typedef UnionFindEnumItem<T> ItemType;
beckerjc@483
   220
    typedef Map< IIter > MapType;
beckerjc@483
   221
beckerjc@483
   222
  private:
beckerjc@483
   223
    MapType& m;
beckerjc@483
   224
    ClassList classes;
beckerjc@483
   225
beckerjc@483
   226
    IIter _find(IIter a) const {
beckerjc@483
   227
      IIter comp = a;
beckerjc@483
   228
      IIter next;
beckerjc@483
   229
      while( (next = comp->parent) != comp ) {
beckerjc@483
   230
	comp = next;
beckerjc@483
   231
      }
beckerjc@483
   232
beckerjc@483
   233
      IIter comp1 = a;
beckerjc@483
   234
      while( (next = comp1->parent) != comp ) {
beckerjc@483
   235
	comp1->parent = comp->parent;
beckerjc@483
   236
	comp1 = next;
beckerjc@483
   237
      }
beckerjc@483
   238
      return comp;
beckerjc@483
   239
    }
beckerjc@483
   240
beckerjc@483
   241
  public:
beckerjc@483
   242
    UnionFindEnum(MapType& _m) : m(_m) {}
beckerjc@483
   243
beckerjc@483
   244
beckerjc@483
   245
    /**
beckerjc@483
   246
     * \brief Insert the given element into a new component.
beckerjc@483
   247
     *
beckerjc@483
   248
     * This method creates a new component consisting only of the
beckerjc@483
   249
     * given element.
beckerjc@483
   250
     */
beckerjc@483
   251
beckerjc@483
   252
    void insert(const T &a)
beckerjc@483
   253
    {
beckerjc@483
   254
beckerjc@483
   255
beckerjc@483
   256
      classes.push_back(ItemList());
beckerjc@483
   257
      CIter aclass = classes.end();
beckerjc@483
   258
      --aclass;
beckerjc@483
   259
beckerjc@483
   260
      ItemList &alist = *aclass;
beckerjc@483
   261
      alist.push_back(ItemType(a, aclass));
beckerjc@483
   262
      IIter ai = alist.begin();
beckerjc@483
   263
beckerjc@483
   264
      ai->parent = ai;
beckerjc@483
   265
      m.set(a, ai);
beckerjc@483
   266
beckerjc@483
   267
    }
beckerjc@483
   268
beckerjc@483
   269
    /**
beckerjc@483
   270
     * \brief Insert the given element into the component of the others.
beckerjc@483
   271
     *
beckerjc@483
   272
     * This methods insert the element \e a into the component of the
beckerjc@483
   273
     * element \e comp. 
beckerjc@483
   274
     */
beckerjc@483
   275
beckerjc@483
   276
    void insert(const T &a, const T &comp) {
beckerjc@483
   277
      
beckerjc@483
   278
      IIter clit = _find(m[comp]);
beckerjc@483
   279
      ItemList &c = *clit->my_class;
beckerjc@483
   280
      c.push_back(ItemType(a,0));
beckerjc@483
   281
      IIter ai = c.end();
beckerjc@483
   282
      --ai;
beckerjc@483
   283
      ai->parent = clit;
beckerjc@483
   284
      m.set(a, ai);
beckerjc@483
   285
      ++clit->size;
beckerjc@483
   286
    }
beckerjc@483
   287
beckerjc@483
   288
beckerjc@483
   289
    /**
beckerjc@483
   290
     * \brief Find the leader of the component of the given element.
beckerjc@483
   291
     *
beckerjc@483
   292
     * The method returns the leader of the component of the given element.
beckerjc@483
   293
     */
beckerjc@483
   294
beckerjc@483
   295
    T find(const T &a) const {
beckerjc@483
   296
      return _find(m[a])->me;
beckerjc@483
   297
    }
beckerjc@483
   298
beckerjc@483
   299
beckerjc@483
   300
    /**
beckerjc@483
   301
     * \brief Joining the component of element \e a and element \e b.
beckerjc@483
   302
     *
beckerjc@483
   303
     * This is the \e union operation of the Union-Find structure. 
beckerjc@483
   304
     * Joins the component of elemenent \e a and component of
beckerjc@483
   305
     * element \e b. If \e a and \e b are in the same component then
beckerjc@483
   306
     * returns false else returns true.
beckerjc@483
   307
     */
beckerjc@483
   308
beckerjc@483
   309
    bool join(T a, T b) {
beckerjc@483
   310
beckerjc@483
   311
      IIter ca = _find(m[a]);
beckerjc@483
   312
      IIter cb = _find(m[b]);
beckerjc@483
   313
beckerjc@483
   314
      if ( ca == cb ) {
beckerjc@483
   315
	return false;
beckerjc@483
   316
      }
beckerjc@483
   317
beckerjc@483
   318
      if ( ca->size > cb->size ) {
beckerjc@483
   319
beckerjc@483
   320
	cb->parent = ca->parent;
beckerjc@483
   321
	ca->size += cb->size;
beckerjc@483
   322
	
beckerjc@483
   323
	ItemList &alist = *ca->my_class;
beckerjc@483
   324
	alist.splice(alist.end(),*cb->my_class);
beckerjc@483
   325
beckerjc@483
   326
	classes.erase(cb->my_class);
beckerjc@483
   327
	cb->my_class = 0;
beckerjc@483
   328
      }
beckerjc@483
   329
      else {
beckerjc@483
   330
beckerjc@483
   331
	ca->parent = cb->parent;
beckerjc@483
   332
	cb->size += ca->size;
beckerjc@483
   333
	
beckerjc@483
   334
	ItemList &blist = *cb->my_class;
beckerjc@483
   335
	blist.splice(blist.end(),*ca->my_class);
beckerjc@483
   336
beckerjc@483
   337
	classes.erase(ca->my_class);
beckerjc@483
   338
	ca->my_class = 0;
beckerjc@483
   339
      }
beckerjc@483
   340
beckerjc@483
   341
      return true;
beckerjc@483
   342
    }
beckerjc@483
   343
beckerjc@483
   344
beckerjc@483
   345
    /**
beckerjc@483
   346
     * \brief Returns the size of the component of element \e a.
beckerjc@483
   347
     *
beckerjc@483
   348
     * Returns the size of the component of element \e a.
beckerjc@483
   349
     */
beckerjc@483
   350
beckerjc@483
   351
    int size(const T &a) const {
beckerjc@483
   352
      return _find(m[a])->size;
beckerjc@483
   353
    }
beckerjc@483
   354
beckerjc@483
   355
beckerjc@483
   356
    /**
beckerjc@483
   357
     * \brief Split up the component of the element. 
beckerjc@483
   358
     *
beckerjc@483
   359
     * Splitting the component of the element into sigleton
beckerjc@483
   360
     * components (component of size one).
beckerjc@483
   361
     */
beckerjc@483
   362
beckerjc@483
   363
    void split(const T &a) {
beckerjc@483
   364
beckerjc@483
   365
      IIter ca = _find(m[a]);
beckerjc@483
   366
 
beckerjc@483
   367
      if ( ca->size == 1 )
beckerjc@483
   368
	return;
beckerjc@483
   369
      
beckerjc@483
   370
      CIter aclass = ca->my_class;
beckerjc@483
   371
beckerjc@483
   372
      for(IIter curr = ca; ++curr != aclass->end(); curr=ca) {
beckerjc@483
   373
	classes.push_back(ItemList());
beckerjc@483
   374
	CIter nl = --classes.end();
beckerjc@483
   375
	nl->splice(nl->end(), *aclass, curr);
beckerjc@483
   376
beckerjc@483
   377
	curr->size=1;
beckerjc@483
   378
	curr->parent=curr;
beckerjc@483
   379
	curr->my_class = nl;
beckerjc@483
   380
      }
beckerjc@483
   381
beckerjc@483
   382
      ca->size=1;
beckerjc@483
   383
      return;
beckerjc@483
   384
    }
beckerjc@483
   385
beckerjc@483
   386
beckerjc@483
   387
    /**
beckerjc@483
   388
     * \brief Set the given element to the leader element of its component.
beckerjc@483
   389
     *
beckerjc@483
   390
     * Set the given element to the leader element of its component.
beckerjc@483
   391
     */
beckerjc@483
   392
beckerjc@483
   393
    void makeRep(const T &a) {
beckerjc@483
   394
beckerjc@483
   395
      IIter ia = m[a];
beckerjc@483
   396
      IIter la = _find(ia);
beckerjc@483
   397
      if (la == ia) return;
beckerjc@483
   398
beckerjc@483
   399
      ia->my_class = la->my_class;
beckerjc@483
   400
      la->my_class = 0;
beckerjc@483
   401
beckerjc@483
   402
      ia->size = la->size;
beckerjc@483
   403
beckerjc@483
   404
      CIter l = ia->my_class;
beckerjc@483
   405
      l->splice(l->begin(),*l,ia);
beckerjc@483
   406
beckerjc@483
   407
      ia->parent = ia;
beckerjc@483
   408
      la->parent = ia;
beckerjc@483
   409
    }
beckerjc@483
   410
beckerjc@483
   411
    /**
beckerjc@483
   412
     * \brief Move the given element to an other component.
beckerjc@483
   413
     *
beckerjc@483
   414
     * This method moves the element \e a from its component
beckerjc@483
   415
     * to the component of \e comp.
beckerjc@483
   416
     * If \e a and \e comp are in the same component then
beckerjc@483
   417
     * it returns false otherwise it returns true.
beckerjc@483
   418
     */
beckerjc@483
   419
beckerjc@483
   420
    bool move(const T &a, const T &comp) {
beckerjc@483
   421
beckerjc@483
   422
      IIter ai = m[a];
beckerjc@483
   423
      IIter lai = _find(ai);
beckerjc@483
   424
      IIter clit = _find(m[comp]);
beckerjc@483
   425
beckerjc@483
   426
      if (lai == clit)
beckerjc@483
   427
	return false;
beckerjc@483
   428
beckerjc@483
   429
      ItemList &c = *clit->my_class;
beckerjc@483
   430
beckerjc@483
   431
      bool is_leader = (lai == ai);
beckerjc@483
   432
      bool singleton = false;
beckerjc@483
   433
beckerjc@483
   434
      if (is_leader) {
beckerjc@483
   435
	++lai;
beckerjc@483
   436
      }
beckerjc@483
   437
beckerjc@483
   438
      c.splice(c.end(), *lai->my_class, ai);
beckerjc@483
   439
beckerjc@483
   440
      if (is_leader) {
beckerjc@483
   441
	if (ai->size == 1) {
beckerjc@483
   442
	  classes.erase(ai->my_class);
beckerjc@483
   443
	  singleton = true;
beckerjc@483
   444
	}
beckerjc@483
   445
	else {
beckerjc@483
   446
	  lai->size = ai->size; 
beckerjc@483
   447
	  lai->my_class = ai->my_class;	
beckerjc@483
   448
	}
beckerjc@483
   449
      }
beckerjc@483
   450
      if (!singleton) {
beckerjc@483
   451
	for (IIter i = lai; i != lai->my_class->end(); ++i)
beckerjc@483
   452
	  i->parent = lai;
beckerjc@483
   453
	--lai->size;
beckerjc@483
   454
      }
beckerjc@483
   455
beckerjc@483
   456
      ai->parent = clit;
beckerjc@483
   457
      ai->my_class = 0;
beckerjc@483
   458
      ++clit->size;
beckerjc@483
   459
beckerjc@483
   460
      return true;
beckerjc@483
   461
    }
beckerjc@483
   462
beckerjc@483
   463
beckerjc@483
   464
    /**
beckerjc@483
   465
     * \brief Remove the given element from the structure.
beckerjc@483
   466
     *
beckerjc@483
   467
     * Remove the given element from the structure.
beckerjc@483
   468
     *
beckerjc@483
   469
     * Removes the element from its component and if the component becomes
beckerjc@483
   470
     * empty then removes that component from the component list.
beckerjc@483
   471
     */
beckerjc@483
   472
    void erase(const T &a) {
beckerjc@483
   473
beckerjc@483
   474
      IIter ma = m[a];
beckerjc@483
   475
      if (ma == 0) return;
beckerjc@483
   476
beckerjc@483
   477
      IIter la = _find(ma);
beckerjc@483
   478
      if (la == ma) {
beckerjc@483
   479
	if (ma -> size == 1){
beckerjc@483
   480
	  classes.erase(ma->my_class);
beckerjc@483
   481
	  m.set(a,0);
beckerjc@483
   482
	  return;
beckerjc@483
   483
	}
beckerjc@483
   484
	++la;
beckerjc@483
   485
	la->size = ma->size; 
beckerjc@483
   486
	la->my_class = ma->my_class;	
beckerjc@483
   487
      }
beckerjc@483
   488
beckerjc@483
   489
      for (IIter i = la; i != la->my_class->end(); ++i) {
beckerjc@483
   490
	i->parent = la;
beckerjc@483
   491
      }
beckerjc@483
   492
beckerjc@483
   493
      la->size--;
beckerjc@483
   494
      la->my_class->erase(ma);
beckerjc@483
   495
      m.set(a,0);
beckerjc@483
   496
    }
beckerjc@483
   497
beckerjc@483
   498
    /**
beckerjc@483
   499
     * \brief Removes the component of the given element from the structure.
beckerjc@483
   500
     *
beckerjc@483
   501
     * Removes the component of the given element from the structure.
beckerjc@483
   502
     */
beckerjc@483
   503
beckerjc@483
   504
    void eraseClass(const T &a) {
beckerjc@483
   505
      IIter ma = m[a];
beckerjc@483
   506
      if (ma == 0) return;
beckerjc@483
   507
#     ifdef DEBUG
beckerjc@483
   508
      CIter c = _find(ma)->my_class;
beckerjc@483
   509
      for (IIter i=c->begin(); i!=c->end(); ++i)
beckerjc@483
   510
	m.set(i->me, 0);
beckerjc@483
   511
#     endif
beckerjc@483
   512
      classes.erase(_find(ma)->my_class);
beckerjc@483
   513
    }
beckerjc@483
   514
beckerjc@483
   515
beckerjc@483
   516
    class ClassIt {
beckerjc@483
   517
      friend class UnionFindEnum;
beckerjc@483
   518
beckerjc@483
   519
      CcIter i;
beckerjc@483
   520
    public:
beckerjc@483
   521
      ClassIt(Invalid): i(0) {}
beckerjc@483
   522
      ClassIt() {}
beckerjc@483
   523
      
beckerjc@483
   524
      operator const T& () const { 
beckerjc@483
   525
	ItemList const &ll = *i;
beckerjc@483
   526
	return (ll.begin())->me; }
beckerjc@483
   527
      bool operator == (ClassIt it) const {
beckerjc@483
   528
	return (i == it.i);
beckerjc@483
   529
      }
beckerjc@483
   530
      bool operator != (ClassIt it) const {
beckerjc@483
   531
	return (i != it.i);
beckerjc@483
   532
      }
beckerjc@483
   533
      bool operator < (ClassIt it) const {
beckerjc@483
   534
	return (i < it.i);
beckerjc@483
   535
      }
beckerjc@483
   536
beckerjc@483
   537
      bool valid() const { return i != 0; }
beckerjc@483
   538
    private:
beckerjc@483
   539
      void first(const ClassList &l) { i = l.begin(); validate(l); }
beckerjc@483
   540
      void next(const ClassList &l) {
beckerjc@483
   541
	++i; 
beckerjc@483
   542
	validate(l);
beckerjc@483
   543
      }
beckerjc@483
   544
      void validate(const ClassList &l) {
beckerjc@483
   545
	if ( i == l.end() ) 
beckerjc@483
   546
	  i = 0;
beckerjc@483
   547
      }
beckerjc@483
   548
    };
beckerjc@483
   549
beckerjc@483
   550
    /**
beckerjc@483
   551
     * \brief Sets the iterator to point to the first component.
beckerjc@483
   552
     * 
beckerjc@483
   553
     * Sets the iterator to point to the first component.
beckerjc@483
   554
     *
beckerjc@483
   555
     * With the \ref first, \ref valid and \ref next methods you can
beckerjc@483
   556
     * iterate through the components. For example:
beckerjc@483
   557
     * \code
beckerjc@483
   558
     * UnionFindEnum<Graph::Node, Graph::NodeMap>::MapType map(G);
beckerjc@483
   559
     * UnionFindEnum<Graph::Node, Graph::NodeMap> U(map);
beckerjc@483
   560
     * UnionFindEnum<Graph::Node, Graph::NodeMap>::ClassIt iter;
beckerjc@483
   561
     *  for (U.first(iter); U.valid(iter); U.next(iter)) {
beckerjc@483
   562
     *    // iter is convertible to Graph::Node
beckerjc@483
   563
     *    cout << iter << endl;
beckerjc@483
   564
     *  }
beckerjc@483
   565
     * \endcode
beckerjc@483
   566
     */
beckerjc@483
   567
beckerjc@483
   568
    ClassIt& first(ClassIt& it) const {
beckerjc@483
   569
      it.first(classes);
beckerjc@483
   570
      return it;
beckerjc@483
   571
    }
beckerjc@483
   572
beckerjc@483
   573
    /**
beckerjc@483
   574
     * \brief Returns whether the iterator is valid.
beckerjc@483
   575
     *
beckerjc@483
   576
     * Returns whether the iterator is valid.
beckerjc@483
   577
     *
beckerjc@483
   578
     * With the \ref first, \ref valid and \ref next methods you can
beckerjc@483
   579
     * iterate through the components. See the example here: \ref first.
beckerjc@483
   580
     */
beckerjc@483
   581
beckerjc@483
   582
    bool valid(ClassIt const &it) const {
beckerjc@483
   583
      return it.valid(); 
beckerjc@483
   584
    }
beckerjc@483
   585
beckerjc@483
   586
    /**
beckerjc@483
   587
     * \brief Steps the iterator to the next component. 
beckerjc@483
   588
     *
beckerjc@483
   589
     * Steps the iterator to the next component.
beckerjc@483
   590
     *
beckerjc@483
   591
     * With the \ref first, \ref valid and \ref next methods you can
beckerjc@483
   592
     * iterate through the components. See the example here: \ref first.
beckerjc@483
   593
     */
beckerjc@483
   594
beckerjc@483
   595
    ClassIt& next(ClassIt& it) const {
beckerjc@483
   596
      it.next(classes);
beckerjc@483
   597
      return it;
beckerjc@483
   598
    }
beckerjc@483
   599
beckerjc@483
   600
beckerjc@483
   601
    class ItemIt {
beckerjc@483
   602
      friend class UnionFindEnum;
beckerjc@483
   603
beckerjc@483
   604
      IcIter i;
beckerjc@483
   605
      const ItemList *l;
beckerjc@483
   606
    public:
beckerjc@483
   607
      ItemIt(Invalid): i(0) {}
beckerjc@483
   608
      ItemIt() {}
beckerjc@483
   609
      
beckerjc@483
   610
      operator const T& () const { return i->me; }
beckerjc@483
   611
      bool operator == (ItemIt it) const {
beckerjc@483
   612
	return (i == it.i);
beckerjc@483
   613
      }
beckerjc@483
   614
      bool operator != (ItemIt it) const {
beckerjc@483
   615
	return (i != it.i);
beckerjc@483
   616
      }
beckerjc@483
   617
      bool operator < (ItemIt it) const {
beckerjc@483
   618
	return (i < it.i);
beckerjc@483
   619
      }
beckerjc@483
   620
beckerjc@483
   621
      bool valid() const { return i != 0; }
beckerjc@483
   622
    private:
beckerjc@483
   623
      void first(const ItemList &il) { l=&il; i = l->begin(); validate(); }
beckerjc@483
   624
      void next() {
beckerjc@483
   625
	++i; 
beckerjc@483
   626
	validate();
beckerjc@483
   627
      }
beckerjc@483
   628
      void validate() {
beckerjc@483
   629
	if ( i == l->end() ) 
beckerjc@483
   630
	  i = 0;
beckerjc@483
   631
      }
beckerjc@483
   632
    };
beckerjc@483
   633
beckerjc@483
   634
beckerjc@483
   635
beckerjc@483
   636
    /**
beckerjc@483
   637
     * \brief Sets the iterator to point to the first element of the component.
beckerjc@483
   638
     * 
beckerjc@483
   639
     * \anchor first2 
beckerjc@483
   640
     * Sets the iterator to point to the first element of the component.
beckerjc@483
   641
     *
beckerjc@483
   642
     * With the \ref first2 "first", \ref valid2 "valid" 
beckerjc@483
   643
     * and \ref next2 "next" methods you can
beckerjc@483
   644
     * iterate through the elements of a component. For example
beckerjc@483
   645
     * (iterating through the component of the node \e node):
beckerjc@483
   646
     * \code
beckerjc@483
   647
     * Graph::Node node = ...;
beckerjc@483
   648
     * UnionFindEnum<Graph::Node, Graph::NodeMap>::MapType map(G);
beckerjc@483
   649
     * UnionFindEnum<Graph::Node, Graph::NodeMap> U(map);
beckerjc@483
   650
     * UnionFindEnum<Graph::Node, Graph::NodeMap>::ItemIt iiter;
beckerjc@483
   651
     *   for (U.first(iiter, node); U.valid(iiter); U.next(iiter)) {
beckerjc@483
   652
     *     // iiter is convertible to Graph::Node
beckerjc@483
   653
     *     cout << iiter << endl;
beckerjc@483
   654
     *   }
beckerjc@483
   655
     * \endcode
beckerjc@483
   656
     */
beckerjc@483
   657
    
beckerjc@483
   658
    ItemIt& first(ItemIt& it, const T& a) const {
beckerjc@483
   659
      it.first( * _find(m[a])->my_class );
beckerjc@483
   660
      return it;
beckerjc@483
   661
    }
beckerjc@483
   662
beckerjc@483
   663
    /**
beckerjc@483
   664
     * \brief Returns whether the iterator is valid.
beckerjc@483
   665
     *
beckerjc@483
   666
     * \anchor valid2
beckerjc@483
   667
     * Returns whether the iterator is valid.
beckerjc@483
   668
     *
beckerjc@483
   669
     * With the \ref first2 "first", \ref valid2 "valid" 
beckerjc@483
   670
     * and \ref next2 "next" methods you can
beckerjc@483
   671
     * iterate through the elements of a component.
beckerjc@483
   672
     * See the example here: \ref first2 "first".
beckerjc@483
   673
     */
beckerjc@483
   674
beckerjc@483
   675
    bool valid(ItemIt const &it) const {
beckerjc@483
   676
      return it.valid(); 
beckerjc@483
   677
    }
beckerjc@483
   678
beckerjc@483
   679
    /**
beckerjc@483
   680
     * \brief Steps the iterator to the next component. 
beckerjc@483
   681
     *
beckerjc@483
   682
     * \anchor next2
beckerjc@483
   683
     * Steps the iterator to the next component.
beckerjc@483
   684
     *
beckerjc@483
   685
     * With the \ref first2 "first", \ref valid2 "valid" 
beckerjc@483
   686
     * and \ref next2 "next" methods you can
beckerjc@483
   687
     * iterate through the elements of a component.
beckerjc@483
   688
     * See the example here: \ref first2 "first".
beckerjc@483
   689
     */
beckerjc@483
   690
beckerjc@483
   691
    ItemIt& next(ItemIt& it) const {
beckerjc@483
   692
      it.next();
beckerjc@483
   693
      return it;
beckerjc@483
   694
    }
beckerjc@483
   695
    
beckerjc@483
   696
  };
beckerjc@483
   697
beckerjc@483
   698
beckerjc@483
   699
  //! @}
beckerjc@483
   700
beckerjc@483
   701
} //namespace hugo
beckerjc@483
   702
beckerjc@483
   703
#endif //HUGO_UNION_FIND_H