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