src/hugo/unionfind.h
author deba
Wed, 08 Sep 2004 12:06:45 +0000
changeset 822 88226d9fe821
parent 774 4297098d9677
child 906 17f31d280385
permissions -rw-r--r--
The MapFactories have been removed from the code because
if we use macros then they increases only the complexity.

The pair iterators of the maps are separeted from the maps.

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