1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/lemon/unionfind.h Fri Feb 29 11:01:39 2008 +0000
1.3 @@ -0,0 +1,1796 @@
1.4 +/* -*- C++ -*-
1.5 + *
1.6 + * This file is a part of LEMON, a generic C++ optimization library
1.7 + *
1.8 + * Copyright (C) 2003-2008
1.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.11 + *
1.12 + * Permission to use, modify and distribute this software is granted
1.13 + * provided that this copyright notice appears in all copies. For
1.14 + * precise terms see the accompanying LICENSE file.
1.15 + *
1.16 + * This software is provided "AS IS" with no warranty of any kind,
1.17 + * express or implied, and with no claim as to its suitability for any
1.18 + * purpose.
1.19 + *
1.20 + */
1.21 +
1.22 +#ifndef LEMON_UNION_FIND_H
1.23 +#define LEMON_UNION_FIND_H
1.24 +
1.25 +//!\ingroup auxdat
1.26 +//!\file
1.27 +//!\brief Union-Find data structures.
1.28 +//!
1.29 +
1.30 +#include <vector>
1.31 +#include <list>
1.32 +#include <utility>
1.33 +#include <algorithm>
1.34 +#include <functional>
1.35 +
1.36 +#include <lemon/bits/invalid.h>
1.37 +
1.38 +namespace lemon {
1.39 +
1.40 + /// \ingroup auxdat
1.41 + ///
1.42 + /// \brief A \e Union-Find data structure implementation
1.43 + ///
1.44 + /// The class implements the \e Union-Find data structure.
1.45 + /// The union operation uses rank heuristic, while
1.46 + /// the find operation uses path compression.
1.47 + /// This is a very simple but efficient implementation, providing
1.48 + /// only four methods: join (union), find, insert and size.
1.49 + /// For more features see the \ref UnionFindEnum class.
1.50 + ///
1.51 + /// It is primarily used in Kruskal algorithm for finding minimal
1.52 + /// cost spanning tree in a graph.
1.53 + /// \sa kruskal()
1.54 + ///
1.55 + /// \pre You need to add all the elements by the \ref insert()
1.56 + /// method.
1.57 + template <typename _ItemIntMap>
1.58 + class UnionFind {
1.59 + public:
1.60 +
1.61 + typedef _ItemIntMap ItemIntMap;
1.62 + typedef typename ItemIntMap::Key Item;
1.63 +
1.64 + private:
1.65 + // If the items vector stores negative value for an item then
1.66 + // that item is root item and it has -items[it] component size.
1.67 + // Else the items[it] contains the index of the parent.
1.68 + std::vector<int> items;
1.69 + ItemIntMap& index;
1.70 +
1.71 + bool rep(int idx) const {
1.72 + return items[idx] < 0;
1.73 + }
1.74 +
1.75 + int repIndex(int idx) const {
1.76 + int k = idx;
1.77 + while (!rep(k)) {
1.78 + k = items[k] ;
1.79 + }
1.80 + while (idx != k) {
1.81 + int next = items[idx];
1.82 + const_cast<int&>(items[idx]) = k;
1.83 + idx = next;
1.84 + }
1.85 + return k;
1.86 + }
1.87 +
1.88 + public:
1.89 +
1.90 + /// \brief Constructor
1.91 + ///
1.92 + /// Constructor of the UnionFind class. You should give an item to
1.93 + /// integer map which will be used from the data structure. If you
1.94 + /// modify directly this map that may cause segmentation fault,
1.95 + /// invalid data structure, or infinite loop when you use again
1.96 + /// the union-find.
1.97 + UnionFind(ItemIntMap& m) : index(m) {}
1.98 +
1.99 + /// \brief Returns the index of the element's component.
1.100 + ///
1.101 + /// The method returns the index of the element's component.
1.102 + /// This is an integer between zero and the number of inserted elements.
1.103 + ///
1.104 + int find(const Item& a) {
1.105 + return repIndex(index[a]);
1.106 + }
1.107 +
1.108 + /// \brief Clears the union-find data structure
1.109 + ///
1.110 + /// Erase each item from the data structure.
1.111 + void clear() {
1.112 + items.clear();
1.113 + }
1.114 +
1.115 + /// \brief Inserts a new element into the structure.
1.116 + ///
1.117 + /// This method inserts a new element into the data structure.
1.118 + ///
1.119 + /// The method returns the index of the new component.
1.120 + int insert(const Item& a) {
1.121 + int n = items.size();
1.122 + items.push_back(-1);
1.123 + index.set(a,n);
1.124 + return n;
1.125 + }
1.126 +
1.127 + /// \brief Joining the components of element \e a and element \e b.
1.128 + ///
1.129 + /// This is the \e union operation of the Union-Find structure.
1.130 + /// Joins the component of element \e a and component of
1.131 + /// element \e b. If \e a and \e b are in the same component then
1.132 + /// it returns false otherwise it returns true.
1.133 + bool join(const Item& a, const Item& b) {
1.134 + int ka = repIndex(index[a]);
1.135 + int kb = repIndex(index[b]);
1.136 +
1.137 + if ( ka == kb )
1.138 + return false;
1.139 +
1.140 + if (items[ka] < items[kb]) {
1.141 + items[ka] += items[kb];
1.142 + items[kb] = ka;
1.143 + } else {
1.144 + items[kb] += items[ka];
1.145 + items[ka] = kb;
1.146 + }
1.147 + return true;
1.148 + }
1.149 +
1.150 + /// \brief Returns the size of the component of element \e a.
1.151 + ///
1.152 + /// Returns the size of the component of element \e a.
1.153 + int size(const Item& a) {
1.154 + int k = repIndex(index[a]);
1.155 + return - items[k];
1.156 + }
1.157 +
1.158 + };
1.159 +
1.160 + /// \ingroup auxdat
1.161 + ///
1.162 + /// \brief A \e Union-Find data structure implementation which
1.163 + /// is able to enumerate the components.
1.164 + ///
1.165 + /// The class implements a \e Union-Find data structure
1.166 + /// which is able to enumerate the components and the items in
1.167 + /// a component. If you don't need this feature then perhaps it's
1.168 + /// better to use the \ref UnionFind class which is more efficient.
1.169 + ///
1.170 + /// The union operation uses rank heuristic, while
1.171 + /// the find operation uses path compression.
1.172 + ///
1.173 + /// \pre You need to add all the elements by the \ref insert()
1.174 + /// method.
1.175 + ///
1.176 + template <typename _ItemIntMap>
1.177 + class UnionFindEnum {
1.178 + public:
1.179 +
1.180 + typedef _ItemIntMap ItemIntMap;
1.181 + typedef typename ItemIntMap::Key Item;
1.182 +
1.183 + private:
1.184 +
1.185 + ItemIntMap& index;
1.186 +
1.187 + // If the parent stores negative value for an item then that item
1.188 + // is root item and it has ~(items[it].parent) component id. Else
1.189 + // the items[it].parent contains the index of the parent.
1.190 + //
1.191 + // The \c next and \c prev provides the double-linked
1.192 + // cyclic list of one component's items.
1.193 + struct ItemT {
1.194 + int parent;
1.195 + Item item;
1.196 +
1.197 + int next, prev;
1.198 + };
1.199 +
1.200 + std::vector<ItemT> items;
1.201 + int firstFreeItem;
1.202 +
1.203 + struct ClassT {
1.204 + int size;
1.205 + int firstItem;
1.206 + int next, prev;
1.207 + };
1.208 +
1.209 + std::vector<ClassT> classes;
1.210 + int firstClass, firstFreeClass;
1.211 +
1.212 + int newClass() {
1.213 + if (firstFreeClass == -1) {
1.214 + int cdx = classes.size();
1.215 + classes.push_back(ClassT());
1.216 + return cdx;
1.217 + } else {
1.218 + int cdx = firstFreeClass;
1.219 + firstFreeClass = classes[firstFreeClass].next;
1.220 + return cdx;
1.221 + }
1.222 + }
1.223 +
1.224 + int newItem() {
1.225 + if (firstFreeItem == -1) {
1.226 + int idx = items.size();
1.227 + items.push_back(ItemT());
1.228 + return idx;
1.229 + } else {
1.230 + int idx = firstFreeItem;
1.231 + firstFreeItem = items[firstFreeItem].next;
1.232 + return idx;
1.233 + }
1.234 + }
1.235 +
1.236 +
1.237 + bool rep(int idx) const {
1.238 + return items[idx].parent < 0;
1.239 + }
1.240 +
1.241 + int repIndex(int idx) const {
1.242 + int k = idx;
1.243 + while (!rep(k)) {
1.244 + k = items[k].parent;
1.245 + }
1.246 + while (idx != k) {
1.247 + int next = items[idx].parent;
1.248 + const_cast<int&>(items[idx].parent) = k;
1.249 + idx = next;
1.250 + }
1.251 + return k;
1.252 + }
1.253 +
1.254 + int classIndex(int idx) const {
1.255 + return ~(items[repIndex(idx)].parent);
1.256 + }
1.257 +
1.258 + void singletonItem(int idx) {
1.259 + items[idx].next = idx;
1.260 + items[idx].prev = idx;
1.261 + }
1.262 +
1.263 + void laceItem(int idx, int rdx) {
1.264 + items[idx].prev = rdx;
1.265 + items[idx].next = items[rdx].next;
1.266 + items[items[rdx].next].prev = idx;
1.267 + items[rdx].next = idx;
1.268 + }
1.269 +
1.270 + void unlaceItem(int idx) {
1.271 + items[items[idx].prev].next = items[idx].next;
1.272 + items[items[idx].next].prev = items[idx].prev;
1.273 +
1.274 + items[idx].next = firstFreeItem;
1.275 + firstFreeItem = idx;
1.276 + }
1.277 +
1.278 + void spliceItems(int ak, int bk) {
1.279 + items[items[ak].prev].next = bk;
1.280 + items[items[bk].prev].next = ak;
1.281 + int tmp = items[ak].prev;
1.282 + items[ak].prev = items[bk].prev;
1.283 + items[bk].prev = tmp;
1.284 +
1.285 + }
1.286 +
1.287 + void laceClass(int cls) {
1.288 + if (firstClass != -1) {
1.289 + classes[firstClass].prev = cls;
1.290 + }
1.291 + classes[cls].next = firstClass;
1.292 + classes[cls].prev = -1;
1.293 + firstClass = cls;
1.294 + }
1.295 +
1.296 + void unlaceClass(int cls) {
1.297 + if (classes[cls].prev != -1) {
1.298 + classes[classes[cls].prev].next = classes[cls].next;
1.299 + } else {
1.300 + firstClass = classes[cls].next;
1.301 + }
1.302 + if (classes[cls].next != -1) {
1.303 + classes[classes[cls].next].prev = classes[cls].prev;
1.304 + }
1.305 +
1.306 + classes[cls].next = firstFreeClass;
1.307 + firstFreeClass = cls;
1.308 + }
1.309 +
1.310 + public:
1.311 +
1.312 + UnionFindEnum(ItemIntMap& _index)
1.313 + : index(_index), items(), firstFreeItem(-1),
1.314 + firstClass(-1), firstFreeClass(-1) {}
1.315 +
1.316 + /// \brief Inserts the given element into a new component.
1.317 + ///
1.318 + /// This method creates a new component consisting only of the
1.319 + /// given element.
1.320 + ///
1.321 + int insert(const Item& item) {
1.322 + int idx = newItem();
1.323 +
1.324 + index.set(item, idx);
1.325 +
1.326 + singletonItem(idx);
1.327 + items[idx].item = item;
1.328 +
1.329 + int cdx = newClass();
1.330 +
1.331 + items[idx].parent = ~cdx;
1.332 +
1.333 + laceClass(cdx);
1.334 + classes[cdx].size = 1;
1.335 + classes[cdx].firstItem = idx;
1.336 +
1.337 + firstClass = cdx;
1.338 +
1.339 + return cdx;
1.340 + }
1.341 +
1.342 + /// \brief Inserts the given element into the component of the others.
1.343 + ///
1.344 + /// This methods inserts the element \e a into the component of the
1.345 + /// element \e comp.
1.346 + void insert(const Item& item, int cls) {
1.347 + int rdx = classes[cls].firstItem;
1.348 + int idx = newItem();
1.349 +
1.350 + index.set(item, idx);
1.351 +
1.352 + laceItem(idx, rdx);
1.353 +
1.354 + items[idx].item = item;
1.355 + items[idx].parent = rdx;
1.356 +
1.357 + ++classes[~(items[rdx].parent)].size;
1.358 + }
1.359 +
1.360 + /// \brief Clears the union-find data structure
1.361 + ///
1.362 + /// Erase each item from the data structure.
1.363 + void clear() {
1.364 + items.clear();
1.365 + firstClass = -1;
1.366 + firstFreeItem = -1;
1.367 + }
1.368 +
1.369 + /// \brief Finds the component of the given element.
1.370 + ///
1.371 + /// The method returns the component id of the given element.
1.372 + int find(const Item &item) const {
1.373 + return ~(items[repIndex(index[item])].parent);
1.374 + }
1.375 +
1.376 + /// \brief Joining the component of element \e a and element \e b.
1.377 + ///
1.378 + /// This is the \e union operation of the Union-Find structure.
1.379 + /// Joins the component of element \e a and component of
1.380 + /// element \e b. If \e a and \e b are in the same component then
1.381 + /// returns -1 else returns the remaining class.
1.382 + int join(const Item& a, const Item& b) {
1.383 +
1.384 + int ak = repIndex(index[a]);
1.385 + int bk = repIndex(index[b]);
1.386 +
1.387 + if (ak == bk) {
1.388 + return -1;
1.389 + }
1.390 +
1.391 + int acx = ~(items[ak].parent);
1.392 + int bcx = ~(items[bk].parent);
1.393 +
1.394 + int rcx;
1.395 +
1.396 + if (classes[acx].size > classes[bcx].size) {
1.397 + classes[acx].size += classes[bcx].size;
1.398 + items[bk].parent = ak;
1.399 + unlaceClass(bcx);
1.400 + rcx = acx;
1.401 + } else {
1.402 + classes[bcx].size += classes[acx].size;
1.403 + items[ak].parent = bk;
1.404 + unlaceClass(acx);
1.405 + rcx = bcx;
1.406 + }
1.407 + spliceItems(ak, bk);
1.408 +
1.409 + return rcx;
1.410 + }
1.411 +
1.412 + /// \brief Returns the size of the class.
1.413 + ///
1.414 + /// Returns the size of the class.
1.415 + int size(int cls) const {
1.416 + return classes[cls].size;
1.417 + }
1.418 +
1.419 + /// \brief Splits up the component.
1.420 + ///
1.421 + /// Splitting the component into singleton components (component
1.422 + /// of size one).
1.423 + void split(int cls) {
1.424 + int fdx = classes[cls].firstItem;
1.425 + int idx = items[fdx].next;
1.426 + while (idx != fdx) {
1.427 + int next = items[idx].next;
1.428 +
1.429 + singletonItem(idx);
1.430 +
1.431 + int cdx = newClass();
1.432 + items[idx].parent = ~cdx;
1.433 +
1.434 + laceClass(cdx);
1.435 + classes[cdx].size = 1;
1.436 + classes[cdx].firstItem = idx;
1.437 +
1.438 + idx = next;
1.439 + }
1.440 +
1.441 + items[idx].prev = idx;
1.442 + items[idx].next = idx;
1.443 +
1.444 + classes[~(items[idx].parent)].size = 1;
1.445 +
1.446 + }
1.447 +
1.448 + /// \brief Removes the given element from the structure.
1.449 + ///
1.450 + /// Removes the element from its component and if the component becomes
1.451 + /// empty then removes that component from the component list.
1.452 + ///
1.453 + /// \warning It is an error to remove an element which is not in
1.454 + /// the structure.
1.455 + /// \warning This running time of this operation is proportional to the
1.456 + /// number of the items in this class.
1.457 + void erase(const Item& item) {
1.458 + int idx = index[item];
1.459 + int fdx = items[idx].next;
1.460 +
1.461 + int cdx = classIndex(idx);
1.462 + if (idx == fdx) {
1.463 + unlaceClass(cdx);
1.464 + items[idx].next = firstFreeItem;
1.465 + firstFreeItem = idx;
1.466 + return;
1.467 + } else {
1.468 + classes[cdx].firstItem = fdx;
1.469 + --classes[cdx].size;
1.470 + items[fdx].parent = ~cdx;
1.471 +
1.472 + unlaceItem(idx);
1.473 + idx = items[fdx].next;
1.474 + while (idx != fdx) {
1.475 + items[idx].parent = fdx;
1.476 + idx = items[idx].next;
1.477 + }
1.478 +
1.479 + }
1.480 +
1.481 + }
1.482 +
1.483 + /// \brief Gives back a representant item of the component.
1.484 + ///
1.485 + /// Gives back a representant item of the component.
1.486 + Item item(int cls) const {
1.487 + return items[classes[cls].firstItem].item;
1.488 + }
1.489 +
1.490 + /// \brief Removes the component of the given element from the structure.
1.491 + ///
1.492 + /// Removes the component of the given element from the structure.
1.493 + ///
1.494 + /// \warning It is an error to give an element which is not in the
1.495 + /// structure.
1.496 + void eraseClass(int cls) {
1.497 + int fdx = classes[cls].firstItem;
1.498 + unlaceClass(cls);
1.499 + items[items[fdx].prev].next = firstFreeItem;
1.500 + firstFreeItem = fdx;
1.501 + }
1.502 +
1.503 + /// \brief Lemon style iterator for the representant items.
1.504 + ///
1.505 + /// ClassIt is a lemon style iterator for the components. It iterates
1.506 + /// on the ids of the classes.
1.507 + class ClassIt {
1.508 + public:
1.509 + /// \brief Constructor of the iterator
1.510 + ///
1.511 + /// Constructor of the iterator
1.512 + ClassIt(const UnionFindEnum& ufe) : unionFind(&ufe) {
1.513 + cdx = unionFind->firstClass;
1.514 + }
1.515 +
1.516 + /// \brief Constructor to get invalid iterator
1.517 + ///
1.518 + /// Constructor to get invalid iterator
1.519 + ClassIt(Invalid) : unionFind(0), cdx(-1) {}
1.520 +
1.521 + /// \brief Increment operator
1.522 + ///
1.523 + /// It steps to the next representant item.
1.524 + ClassIt& operator++() {
1.525 + cdx = unionFind->classes[cdx].next;
1.526 + return *this;
1.527 + }
1.528 +
1.529 + /// \brief Conversion operator
1.530 + ///
1.531 + /// It converts the iterator to the current representant item.
1.532 + operator int() const {
1.533 + return cdx;
1.534 + }
1.535 +
1.536 + /// \brief Equality operator
1.537 + ///
1.538 + /// Equality operator
1.539 + bool operator==(const ClassIt& i) {
1.540 + return i.cdx == cdx;
1.541 + }
1.542 +
1.543 + /// \brief Inequality operator
1.544 + ///
1.545 + /// Inequality operator
1.546 + bool operator!=(const ClassIt& i) {
1.547 + return i.cdx != cdx;
1.548 + }
1.549 +
1.550 + private:
1.551 + const UnionFindEnum* unionFind;
1.552 + int cdx;
1.553 + };
1.554 +
1.555 + /// \brief Lemon style iterator for the items of a component.
1.556 + ///
1.557 + /// ClassIt is a lemon style iterator for the components. It iterates
1.558 + /// on the items of a class. By example if you want to iterate on
1.559 + /// each items of each classes then you may write the next code.
1.560 + ///\code
1.561 + /// for (ClassIt cit(ufe); cit != INVALID; ++cit) {
1.562 + /// std::cout << "Class: ";
1.563 + /// for (ItemIt iit(ufe, cit); iit != INVALID; ++iit) {
1.564 + /// std::cout << toString(iit) << ' ' << std::endl;
1.565 + /// }
1.566 + /// std::cout << std::endl;
1.567 + /// }
1.568 + ///\endcode
1.569 + class ItemIt {
1.570 + public:
1.571 + /// \brief Constructor of the iterator
1.572 + ///
1.573 + /// Constructor of the iterator. The iterator iterates
1.574 + /// on the class of the \c item.
1.575 + ItemIt(const UnionFindEnum& ufe, int cls) : unionFind(&ufe) {
1.576 + fdx = idx = unionFind->classes[cls].firstItem;
1.577 + }
1.578 +
1.579 + /// \brief Constructor to get invalid iterator
1.580 + ///
1.581 + /// Constructor to get invalid iterator
1.582 + ItemIt(Invalid) : unionFind(0), idx(-1) {}
1.583 +
1.584 + /// \brief Increment operator
1.585 + ///
1.586 + /// It steps to the next item in the class.
1.587 + ItemIt& operator++() {
1.588 + idx = unionFind->items[idx].next;
1.589 + if (idx == fdx) idx = -1;
1.590 + return *this;
1.591 + }
1.592 +
1.593 + /// \brief Conversion operator
1.594 + ///
1.595 + /// It converts the iterator to the current item.
1.596 + operator const Item&() const {
1.597 + return unionFind->items[idx].item;
1.598 + }
1.599 +
1.600 + /// \brief Equality operator
1.601 + ///
1.602 + /// Equality operator
1.603 + bool operator==(const ItemIt& i) {
1.604 + return i.idx == idx;
1.605 + }
1.606 +
1.607 + /// \brief Inequality operator
1.608 + ///
1.609 + /// Inequality operator
1.610 + bool operator!=(const ItemIt& i) {
1.611 + return i.idx != idx;
1.612 + }
1.613 +
1.614 + private:
1.615 + const UnionFindEnum* unionFind;
1.616 + int idx, fdx;
1.617 + };
1.618 +
1.619 + };
1.620 +
1.621 + /// \ingroup auxdat
1.622 + ///
1.623 + /// \brief A \e Extend-Find data structure implementation which
1.624 + /// is able to enumerate the components.
1.625 + ///
1.626 + /// The class implements an \e Extend-Find data structure which is
1.627 + /// able to enumerate the components and the items in a
1.628 + /// component. The data structure is a simplification of the
1.629 + /// Union-Find structure, and it does not allow to merge two components.
1.630 + ///
1.631 + /// \pre You need to add all the elements by the \ref insert()
1.632 + /// method.
1.633 + template <typename _ItemIntMap>
1.634 + class ExtendFindEnum {
1.635 + public:
1.636 +
1.637 + typedef _ItemIntMap ItemIntMap;
1.638 + typedef typename ItemIntMap::Key Item;
1.639 +
1.640 + private:
1.641 +
1.642 + ItemIntMap& index;
1.643 +
1.644 + struct ItemT {
1.645 + int cls;
1.646 + Item item;
1.647 + int next, prev;
1.648 + };
1.649 +
1.650 + std::vector<ItemT> items;
1.651 + int firstFreeItem;
1.652 +
1.653 + struct ClassT {
1.654 + int firstItem;
1.655 + int next, prev;
1.656 + };
1.657 +
1.658 + std::vector<ClassT> classes;
1.659 +
1.660 + int firstClass, firstFreeClass;
1.661 +
1.662 + int newClass() {
1.663 + if (firstFreeClass != -1) {
1.664 + int cdx = firstFreeClass;
1.665 + firstFreeClass = classes[cdx].next;
1.666 + return cdx;
1.667 + } else {
1.668 + classes.push_back(ClassT());
1.669 + return classes.size() - 1;
1.670 + }
1.671 + }
1.672 +
1.673 + int newItem() {
1.674 + if (firstFreeItem != -1) {
1.675 + int idx = firstFreeItem;
1.676 + firstFreeItem = items[idx].next;
1.677 + return idx;
1.678 + } else {
1.679 + items.push_back(ItemT());
1.680 + return items.size() - 1;
1.681 + }
1.682 + }
1.683 +
1.684 + public:
1.685 +
1.686 + /// \brief Constructor
1.687 + ExtendFindEnum(ItemIntMap& _index)
1.688 + : index(_index), items(), firstFreeItem(-1),
1.689 + classes(), firstClass(-1), firstFreeClass(-1) {}
1.690 +
1.691 + /// \brief Inserts the given element into a new component.
1.692 + ///
1.693 + /// This method creates a new component consisting only of the
1.694 + /// given element.
1.695 + int insert(const Item& item) {
1.696 + int cdx = newClass();
1.697 + classes[cdx].prev = -1;
1.698 + classes[cdx].next = firstClass;
1.699 + if (firstClass != -1) {
1.700 + classes[firstClass].prev = cdx;
1.701 + }
1.702 + firstClass = cdx;
1.703 +
1.704 + int idx = newItem();
1.705 + items[idx].item = item;
1.706 + items[idx].cls = cdx;
1.707 + items[idx].prev = idx;
1.708 + items[idx].next = idx;
1.709 +
1.710 + classes[cdx].firstItem = idx;
1.711 +
1.712 + index.set(item, idx);
1.713 +
1.714 + return cdx;
1.715 + }
1.716 +
1.717 + /// \brief Inserts the given element into the given component.
1.718 + ///
1.719 + /// This methods inserts the element \e item a into the \e cls class.
1.720 + void insert(const Item& item, int cls) {
1.721 + int idx = newItem();
1.722 + int rdx = classes[cls].firstItem;
1.723 + items[idx].item = item;
1.724 + items[idx].cls = cls;
1.725 +
1.726 + items[idx].prev = rdx;
1.727 + items[idx].next = items[rdx].next;
1.728 + items[items[rdx].next].prev = idx;
1.729 + items[rdx].next = idx;
1.730 +
1.731 + index.set(item, idx);
1.732 + }
1.733 +
1.734 + /// \brief Clears the union-find data structure
1.735 + ///
1.736 + /// Erase each item from the data structure.
1.737 + void clear() {
1.738 + items.clear();
1.739 + classes.clear;
1.740 + firstClass = firstFreeClass = firstFreeItem = -1;
1.741 + }
1.742 +
1.743 + /// \brief Gives back the class of the \e item.
1.744 + ///
1.745 + /// Gives back the class of the \e item.
1.746 + int find(const Item &item) const {
1.747 + return items[index[item]].cls;
1.748 + }
1.749 +
1.750 + /// \brief Gives back a representant item of the component.
1.751 + ///
1.752 + /// Gives back a representant item of the component.
1.753 + Item item(int cls) const {
1.754 + return items[classes[cls].firstItem].item;
1.755 + }
1.756 +
1.757 + /// \brief Removes the given element from the structure.
1.758 + ///
1.759 + /// Removes the element from its component and if the component becomes
1.760 + /// empty then removes that component from the component list.
1.761 + ///
1.762 + /// \warning It is an error to remove an element which is not in
1.763 + /// the structure.
1.764 + void erase(const Item &item) {
1.765 + int idx = index[item];
1.766 + int cdx = items[idx].cls;
1.767 +
1.768 + if (idx == items[idx].next) {
1.769 + if (classes[cdx].prev != -1) {
1.770 + classes[classes[cdx].prev].next = classes[cdx].next;
1.771 + } else {
1.772 + firstClass = classes[cdx].next;
1.773 + }
1.774 + if (classes[cdx].next != -1) {
1.775 + classes[classes[cdx].next].prev = classes[cdx].prev;
1.776 + }
1.777 + classes[cdx].next = firstFreeClass;
1.778 + firstFreeClass = cdx;
1.779 + } else {
1.780 + classes[cdx].firstItem = items[idx].next;
1.781 + items[items[idx].next].prev = items[idx].prev;
1.782 + items[items[idx].prev].next = items[idx].next;
1.783 + }
1.784 + items[idx].next = firstFreeItem;
1.785 + firstFreeItem = idx;
1.786 +
1.787 + }
1.788 +
1.789 +
1.790 + /// \brief Removes the component of the given element from the structure.
1.791 + ///
1.792 + /// Removes the component of the given element from the structure.
1.793 + ///
1.794 + /// \warning It is an error to give an element which is not in the
1.795 + /// structure.
1.796 + void eraseClass(int cdx) {
1.797 + int idx = classes[cdx].firstItem;
1.798 + items[items[idx].prev].next = firstFreeItem;
1.799 + firstFreeItem = idx;
1.800 +
1.801 + if (classes[cdx].prev != -1) {
1.802 + classes[classes[cdx].prev].next = classes[cdx].next;
1.803 + } else {
1.804 + firstClass = classes[cdx].next;
1.805 + }
1.806 + if (classes[cdx].next != -1) {
1.807 + classes[classes[cdx].next].prev = classes[cdx].prev;
1.808 + }
1.809 + classes[cdx].next = firstFreeClass;
1.810 + firstFreeClass = cdx;
1.811 + }
1.812 +
1.813 + /// \brief Lemon style iterator for the classes.
1.814 + ///
1.815 + /// ClassIt is a lemon style iterator for the components. It iterates
1.816 + /// on the ids of classes.
1.817 + class ClassIt {
1.818 + public:
1.819 + /// \brief Constructor of the iterator
1.820 + ///
1.821 + /// Constructor of the iterator
1.822 + ClassIt(const ExtendFindEnum& ufe) : extendFind(&ufe) {
1.823 + cdx = extendFind->firstClass;
1.824 + }
1.825 +
1.826 + /// \brief Constructor to get invalid iterator
1.827 + ///
1.828 + /// Constructor to get invalid iterator
1.829 + ClassIt(Invalid) : extendFind(0), cdx(-1) {}
1.830 +
1.831 + /// \brief Increment operator
1.832 + ///
1.833 + /// It steps to the next representant item.
1.834 + ClassIt& operator++() {
1.835 + cdx = extendFind->classes[cdx].next;
1.836 + return *this;
1.837 + }
1.838 +
1.839 + /// \brief Conversion operator
1.840 + ///
1.841 + /// It converts the iterator to the current class id.
1.842 + operator int() const {
1.843 + return cdx;
1.844 + }
1.845 +
1.846 + /// \brief Equality operator
1.847 + ///
1.848 + /// Equality operator
1.849 + bool operator==(const ClassIt& i) {
1.850 + return i.cdx == cdx;
1.851 + }
1.852 +
1.853 + /// \brief Inequality operator
1.854 + ///
1.855 + /// Inequality operator
1.856 + bool operator!=(const ClassIt& i) {
1.857 + return i.cdx != cdx;
1.858 + }
1.859 +
1.860 + private:
1.861 + const ExtendFindEnum* extendFind;
1.862 + int cdx;
1.863 + };
1.864 +
1.865 + /// \brief Lemon style iterator for the items of a component.
1.866 + ///
1.867 + /// ClassIt is a lemon style iterator for the components. It iterates
1.868 + /// on the items of a class. By example if you want to iterate on
1.869 + /// each items of each classes then you may write the next code.
1.870 + ///\code
1.871 + /// for (ClassIt cit(ufe); cit != INVALID; ++cit) {
1.872 + /// std::cout << "Class: ";
1.873 + /// for (ItemIt iit(ufe, cit); iit != INVALID; ++iit) {
1.874 + /// std::cout << toString(iit) << ' ' << std::endl;
1.875 + /// }
1.876 + /// std::cout << std::endl;
1.877 + /// }
1.878 + ///\endcode
1.879 + class ItemIt {
1.880 + public:
1.881 + /// \brief Constructor of the iterator
1.882 + ///
1.883 + /// Constructor of the iterator. The iterator iterates
1.884 + /// on the class of the \c item.
1.885 + ItemIt(const ExtendFindEnum& ufe, int cls) : extendFind(&ufe) {
1.886 + fdx = idx = extendFind->classes[cls].firstItem;
1.887 + }
1.888 +
1.889 + /// \brief Constructor to get invalid iterator
1.890 + ///
1.891 + /// Constructor to get invalid iterator
1.892 + ItemIt(Invalid) : extendFind(0), idx(-1) {}
1.893 +
1.894 + /// \brief Increment operator
1.895 + ///
1.896 + /// It steps to the next item in the class.
1.897 + ItemIt& operator++() {
1.898 + idx = extendFind->items[idx].next;
1.899 + if (fdx == idx) idx = -1;
1.900 + return *this;
1.901 + }
1.902 +
1.903 + /// \brief Conversion operator
1.904 + ///
1.905 + /// It converts the iterator to the current item.
1.906 + operator const Item&() const {
1.907 + return extendFind->items[idx].item;
1.908 + }
1.909 +
1.910 + /// \brief Equality operator
1.911 + ///
1.912 + /// Equality operator
1.913 + bool operator==(const ItemIt& i) {
1.914 + return i.idx == idx;
1.915 + }
1.916 +
1.917 + /// \brief Inequality operator
1.918 + ///
1.919 + /// Inequality operator
1.920 + bool operator!=(const ItemIt& i) {
1.921 + return i.idx != idx;
1.922 + }
1.923 +
1.924 + private:
1.925 + const ExtendFindEnum* extendFind;
1.926 + int idx, fdx;
1.927 + };
1.928 +
1.929 + };
1.930 +
1.931 + /// \ingroup auxdat
1.932 + ///
1.933 + /// \brief A \e Union-Find data structure implementation which
1.934 + /// is able to store a priority for each item and retrieve the minimum of
1.935 + /// each class.
1.936 + ///
1.937 + /// A \e Union-Find data structure implementation which is able to
1.938 + /// store a priority for each item and retrieve the minimum of each
1.939 + /// class. In addition, it supports the joining and splitting the
1.940 + /// components. If you don't need this feature then you makes
1.941 + /// better to use the \ref UnionFind class which is more efficient.
1.942 + ///
1.943 + /// The union-find data strcuture based on a (2, 16)-tree with a
1.944 + /// tournament minimum selection on the internal nodes. The insert
1.945 + /// operation takes O(1), the find, set, decrease and increase takes
1.946 + /// O(log(n)), where n is the number of nodes in the current
1.947 + /// component. The complexity of join and split is O(log(n)*k),
1.948 + /// where n is the sum of the number of the nodes and k is the
1.949 + /// number of joined components or the number of the components
1.950 + /// after the split.
1.951 + ///
1.952 + /// \pre You need to add all the elements by the \ref insert()
1.953 + /// method.
1.954 + ///
1.955 + template <typename _Value, typename _ItemIntMap,
1.956 + typename _Comp = std::less<_Value> >
1.957 + class HeapUnionFind {
1.958 + public:
1.959 +
1.960 + typedef _Value Value;
1.961 + typedef typename _ItemIntMap::Key Item;
1.962 +
1.963 + typedef _ItemIntMap ItemIntMap;
1.964 +
1.965 + typedef _Comp Comp;
1.966 +
1.967 + private:
1.968 +
1.969 + static const int cmax = 16;
1.970 +
1.971 + ItemIntMap& index;
1.972 +
1.973 + struct ClassNode {
1.974 + int parent;
1.975 + int depth;
1.976 +
1.977 + int left, right;
1.978 + int next, prev;
1.979 + };
1.980 +
1.981 + int first_class;
1.982 + int first_free_class;
1.983 + std::vector<ClassNode> classes;
1.984 +
1.985 + int newClass() {
1.986 + if (first_free_class < 0) {
1.987 + int id = classes.size();
1.988 + classes.push_back(ClassNode());
1.989 + return id;
1.990 + } else {
1.991 + int id = first_free_class;
1.992 + first_free_class = classes[id].next;
1.993 + return id;
1.994 + }
1.995 + }
1.996 +
1.997 + void deleteClass(int id) {
1.998 + classes[id].next = first_free_class;
1.999 + first_free_class = id;
1.1000 + }
1.1001 +
1.1002 + struct ItemNode {
1.1003 + int parent;
1.1004 + Item item;
1.1005 + Value prio;
1.1006 + int next, prev;
1.1007 + int left, right;
1.1008 + int size;
1.1009 + };
1.1010 +
1.1011 + int first_free_node;
1.1012 + std::vector<ItemNode> nodes;
1.1013 +
1.1014 + int newNode() {
1.1015 + if (first_free_node < 0) {
1.1016 + int id = nodes.size();
1.1017 + nodes.push_back(ItemNode());
1.1018 + return id;
1.1019 + } else {
1.1020 + int id = first_free_node;
1.1021 + first_free_node = nodes[id].next;
1.1022 + return id;
1.1023 + }
1.1024 + }
1.1025 +
1.1026 + void deleteNode(int id) {
1.1027 + nodes[id].next = first_free_node;
1.1028 + first_free_node = id;
1.1029 + }
1.1030 +
1.1031 + Comp comp;
1.1032 +
1.1033 + int findClass(int id) const {
1.1034 + int kd = id;
1.1035 + while (kd >= 0) {
1.1036 + kd = nodes[kd].parent;
1.1037 + }
1.1038 + return ~kd;
1.1039 + }
1.1040 +
1.1041 + int leftNode(int id) const {
1.1042 + int kd = ~(classes[id].parent);
1.1043 + for (int i = 0; i < classes[id].depth; ++i) {
1.1044 + kd = nodes[kd].left;
1.1045 + }
1.1046 + return kd;
1.1047 + }
1.1048 +
1.1049 + int nextNode(int id) const {
1.1050 + int depth = 0;
1.1051 + while (id >= 0 && nodes[id].next == -1) {
1.1052 + id = nodes[id].parent;
1.1053 + ++depth;
1.1054 + }
1.1055 + if (id < 0) {
1.1056 + return -1;
1.1057 + }
1.1058 + id = nodes[id].next;
1.1059 + while (depth--) {
1.1060 + id = nodes[id].left;
1.1061 + }
1.1062 + return id;
1.1063 + }
1.1064 +
1.1065 +
1.1066 + void setPrio(int id) {
1.1067 + int jd = nodes[id].left;
1.1068 + nodes[id].prio = nodes[jd].prio;
1.1069 + nodes[id].item = nodes[jd].item;
1.1070 + jd = nodes[jd].next;
1.1071 + while (jd != -1) {
1.1072 + if (comp(nodes[jd].prio, nodes[id].prio)) {
1.1073 + nodes[id].prio = nodes[jd].prio;
1.1074 + nodes[id].item = nodes[jd].item;
1.1075 + }
1.1076 + jd = nodes[jd].next;
1.1077 + }
1.1078 + }
1.1079 +
1.1080 + void push(int id, int jd) {
1.1081 + nodes[id].size = 1;
1.1082 + nodes[id].left = nodes[id].right = jd;
1.1083 + nodes[jd].next = nodes[jd].prev = -1;
1.1084 + nodes[jd].parent = id;
1.1085 + }
1.1086 +
1.1087 + void pushAfter(int id, int jd) {
1.1088 + int kd = nodes[id].parent;
1.1089 + if (nodes[id].next != -1) {
1.1090 + nodes[nodes[id].next].prev = jd;
1.1091 + if (kd >= 0) {
1.1092 + nodes[kd].size += 1;
1.1093 + }
1.1094 + } else {
1.1095 + if (kd >= 0) {
1.1096 + nodes[kd].right = jd;
1.1097 + nodes[kd].size += 1;
1.1098 + }
1.1099 + }
1.1100 + nodes[jd].next = nodes[id].next;
1.1101 + nodes[jd].prev = id;
1.1102 + nodes[id].next = jd;
1.1103 + nodes[jd].parent = kd;
1.1104 + }
1.1105 +
1.1106 + void pushRight(int id, int jd) {
1.1107 + nodes[id].size += 1;
1.1108 + nodes[jd].prev = nodes[id].right;
1.1109 + nodes[jd].next = -1;
1.1110 + nodes[nodes[id].right].next = jd;
1.1111 + nodes[id].right = jd;
1.1112 + nodes[jd].parent = id;
1.1113 + }
1.1114 +
1.1115 + void popRight(int id) {
1.1116 + nodes[id].size -= 1;
1.1117 + int jd = nodes[id].right;
1.1118 + nodes[nodes[jd].prev].next = -1;
1.1119 + nodes[id].right = nodes[jd].prev;
1.1120 + }
1.1121 +
1.1122 + void splice(int id, int jd) {
1.1123 + nodes[id].size += nodes[jd].size;
1.1124 + nodes[nodes[id].right].next = nodes[jd].left;
1.1125 + nodes[nodes[jd].left].prev = nodes[id].right;
1.1126 + int kd = nodes[jd].left;
1.1127 + while (kd != -1) {
1.1128 + nodes[kd].parent = id;
1.1129 + kd = nodes[kd].next;
1.1130 + }
1.1131 + nodes[id].right = nodes[jd].right;
1.1132 + }
1.1133 +
1.1134 + void split(int id, int jd) {
1.1135 + int kd = nodes[id].parent;
1.1136 + nodes[kd].right = nodes[id].prev;
1.1137 + nodes[nodes[id].prev].next = -1;
1.1138 +
1.1139 + nodes[jd].left = id;
1.1140 + nodes[id].prev = -1;
1.1141 + int num = 0;
1.1142 + while (id != -1) {
1.1143 + nodes[id].parent = jd;
1.1144 + nodes[jd].right = id;
1.1145 + id = nodes[id].next;
1.1146 + ++num;
1.1147 + }
1.1148 + nodes[kd].size -= num;
1.1149 + nodes[jd].size = num;
1.1150 + }
1.1151 +
1.1152 + void pushLeft(int id, int jd) {
1.1153 + nodes[id].size += 1;
1.1154 + nodes[jd].next = nodes[id].left;
1.1155 + nodes[jd].prev = -1;
1.1156 + nodes[nodes[id].left].prev = jd;
1.1157 + nodes[id].left = jd;
1.1158 + nodes[jd].parent = id;
1.1159 + }
1.1160 +
1.1161 + void popLeft(int id) {
1.1162 + nodes[id].size -= 1;
1.1163 + int jd = nodes[id].left;
1.1164 + nodes[nodes[jd].next].prev = -1;
1.1165 + nodes[id].left = nodes[jd].next;
1.1166 + }
1.1167 +
1.1168 + void repairLeft(int id) {
1.1169 + int jd = ~(classes[id].parent);
1.1170 + while (nodes[jd].left != -1) {
1.1171 + int kd = nodes[jd].left;
1.1172 + if (nodes[jd].size == 1) {
1.1173 + if (nodes[jd].parent < 0) {
1.1174 + classes[id].parent = ~kd;
1.1175 + classes[id].depth -= 1;
1.1176 + nodes[kd].parent = ~id;
1.1177 + deleteNode(jd);
1.1178 + jd = kd;
1.1179 + } else {
1.1180 + int pd = nodes[jd].parent;
1.1181 + if (nodes[nodes[jd].next].size < cmax) {
1.1182 + pushLeft(nodes[jd].next, nodes[jd].left);
1.1183 + if (less(nodes[jd].left, nodes[jd].next)) {
1.1184 + nodes[nodes[jd].next].prio = nodes[nodes[jd].left].prio;
1.1185 + nodes[nodes[jd].next].item = nodes[nodes[jd].left].item;
1.1186 + }
1.1187 + popLeft(pd);
1.1188 + deleteNode(jd);
1.1189 + jd = pd;
1.1190 + } else {
1.1191 + int ld = nodes[nodes[jd].next].left;
1.1192 + popLeft(nodes[jd].next);
1.1193 + pushRight(jd, ld);
1.1194 + if (less(ld, nodes[jd].left)) {
1.1195 + nodes[jd].item = nodes[ld].item;
1.1196 + nodes[jd].prio = nodes[jd].prio;
1.1197 + }
1.1198 + if (nodes[nodes[jd].next].item == nodes[ld].item) {
1.1199 + setPrio(nodes[jd].next);
1.1200 + }
1.1201 + jd = nodes[jd].left;
1.1202 + }
1.1203 + }
1.1204 + } else {
1.1205 + jd = nodes[jd].left;
1.1206 + }
1.1207 + }
1.1208 + }
1.1209 +
1.1210 + void repairRight(int id) {
1.1211 + int jd = ~(classes[id].parent);
1.1212 + while (nodes[jd].right != -1) {
1.1213 + int kd = nodes[jd].right;
1.1214 + if (nodes[jd].size == 1) {
1.1215 + if (nodes[jd].parent < 0) {
1.1216 + classes[id].parent = ~kd;
1.1217 + classes[id].depth -= 1;
1.1218 + nodes[kd].parent = ~id;
1.1219 + deleteNode(jd);
1.1220 + jd = kd;
1.1221 + } else {
1.1222 + int pd = nodes[jd].parent;
1.1223 + if (nodes[nodes[jd].prev].size < cmax) {
1.1224 + pushRight(nodes[jd].prev, nodes[jd].right);
1.1225 + if (less(nodes[jd].right, nodes[jd].prev)) {
1.1226 + nodes[nodes[jd].prev].prio = nodes[nodes[jd].right].prio;
1.1227 + nodes[nodes[jd].prev].item = nodes[nodes[jd].right].item;
1.1228 + }
1.1229 + popRight(pd);
1.1230 + deleteNode(jd);
1.1231 + jd = pd;
1.1232 + } else {
1.1233 + int ld = nodes[nodes[jd].prev].right;
1.1234 + popRight(nodes[jd].prev);
1.1235 + pushLeft(jd, ld);
1.1236 + if (less(ld, nodes[jd].right)) {
1.1237 + nodes[jd].item = nodes[ld].item;
1.1238 + nodes[jd].prio = nodes[jd].prio;
1.1239 + }
1.1240 + if (nodes[nodes[jd].prev].item == nodes[ld].item) {
1.1241 + setPrio(nodes[jd].prev);
1.1242 + }
1.1243 + jd = nodes[jd].right;
1.1244 + }
1.1245 + }
1.1246 + } else {
1.1247 + jd = nodes[jd].right;
1.1248 + }
1.1249 + }
1.1250 + }
1.1251 +
1.1252 +
1.1253 + bool less(int id, int jd) const {
1.1254 + return comp(nodes[id].prio, nodes[jd].prio);
1.1255 + }
1.1256 +
1.1257 + bool equal(int id, int jd) const {
1.1258 + return !less(id, jd) && !less(jd, id);
1.1259 + }
1.1260 +
1.1261 +
1.1262 + public:
1.1263 +
1.1264 + /// \brief Returns true when the given class is alive.
1.1265 + ///
1.1266 + /// Returns true when the given class is alive, ie. the class is
1.1267 + /// not nested into other class.
1.1268 + bool alive(int cls) const {
1.1269 + return classes[cls].parent < 0;
1.1270 + }
1.1271 +
1.1272 + /// \brief Returns true when the given class is trivial.
1.1273 + ///
1.1274 + /// Returns true when the given class is trivial, ie. the class
1.1275 + /// contains just one item directly.
1.1276 + bool trivial(int cls) const {
1.1277 + return classes[cls].left == -1;
1.1278 + }
1.1279 +
1.1280 + /// \brief Constructs the union-find.
1.1281 + ///
1.1282 + /// Constructs the union-find.
1.1283 + /// \brief _index The index map of the union-find. The data
1.1284 + /// structure uses internally for store references.
1.1285 + HeapUnionFind(ItemIntMap& _index)
1.1286 + : index(_index), first_class(-1),
1.1287 + first_free_class(-1), first_free_node(-1) {}
1.1288 +
1.1289 + /// \brief Insert a new node into a new component.
1.1290 + ///
1.1291 + /// Insert a new node into a new component.
1.1292 + /// \param item The item of the new node.
1.1293 + /// \param prio The priority of the new node.
1.1294 + /// \return The class id of the one-item-heap.
1.1295 + int insert(const Item& item, const Value& prio) {
1.1296 + int id = newNode();
1.1297 + nodes[id].item = item;
1.1298 + nodes[id].prio = prio;
1.1299 + nodes[id].size = 0;
1.1300 +
1.1301 + nodes[id].prev = -1;
1.1302 + nodes[id].next = -1;
1.1303 +
1.1304 + nodes[id].left = -1;
1.1305 + nodes[id].right = -1;
1.1306 +
1.1307 + nodes[id].item = item;
1.1308 + index[item] = id;
1.1309 +
1.1310 + int class_id = newClass();
1.1311 + classes[class_id].parent = ~id;
1.1312 + classes[class_id].depth = 0;
1.1313 +
1.1314 + classes[class_id].left = -1;
1.1315 + classes[class_id].right = -1;
1.1316 +
1.1317 + if (first_class != -1) {
1.1318 + classes[first_class].prev = class_id;
1.1319 + }
1.1320 + classes[class_id].next = first_class;
1.1321 + classes[class_id].prev = -1;
1.1322 + first_class = class_id;
1.1323 +
1.1324 + nodes[id].parent = ~class_id;
1.1325 +
1.1326 + return class_id;
1.1327 + }
1.1328 +
1.1329 + /// \brief The class of the item.
1.1330 + ///
1.1331 + /// \return The alive class id of the item, which is not nested into
1.1332 + /// other classes.
1.1333 + ///
1.1334 + /// The time complexity is O(log(n)).
1.1335 + int find(const Item& item) const {
1.1336 + return findClass(index[item]);
1.1337 + }
1.1338 +
1.1339 + /// \brief Joins the classes.
1.1340 + ///
1.1341 + /// The current function joins the given classes. The parameter is
1.1342 + /// an STL range which should be contains valid class ids. The
1.1343 + /// time complexity is O(log(n)*k) where n is the overall number
1.1344 + /// of the joined nodes and k is the number of classes.
1.1345 + /// \return The class of the joined classes.
1.1346 + /// \pre The range should contain at least two class ids.
1.1347 + template <typename Iterator>
1.1348 + int join(Iterator begin, Iterator end) {
1.1349 + std::vector<int> cs;
1.1350 + for (Iterator it = begin; it != end; ++it) {
1.1351 + cs.push_back(*it);
1.1352 + }
1.1353 +
1.1354 + int class_id = newClass();
1.1355 + { // creation union-find
1.1356 +
1.1357 + if (first_class != -1) {
1.1358 + classes[first_class].prev = class_id;
1.1359 + }
1.1360 + classes[class_id].next = first_class;
1.1361 + classes[class_id].prev = -1;
1.1362 + first_class = class_id;
1.1363 +
1.1364 + classes[class_id].depth = classes[cs[0]].depth;
1.1365 + classes[class_id].parent = classes[cs[0]].parent;
1.1366 + nodes[~(classes[class_id].parent)].parent = ~class_id;
1.1367 +
1.1368 + int l = cs[0];
1.1369 +
1.1370 + classes[class_id].left = l;
1.1371 + classes[class_id].right = l;
1.1372 +
1.1373 + if (classes[l].next != -1) {
1.1374 + classes[classes[l].next].prev = classes[l].prev;
1.1375 + }
1.1376 + classes[classes[l].prev].next = classes[l].next;
1.1377 +
1.1378 + classes[l].prev = -1;
1.1379 + classes[l].next = -1;
1.1380 +
1.1381 + classes[l].depth = leftNode(l);
1.1382 + classes[l].parent = class_id;
1.1383 +
1.1384 + }
1.1385 +
1.1386 + { // merging of heap
1.1387 + int l = class_id;
1.1388 + for (int ci = 1; ci < int(cs.size()); ++ci) {
1.1389 + int r = cs[ci];
1.1390 + int rln = leftNode(r);
1.1391 + if (classes[l].depth > classes[r].depth) {
1.1392 + int id = ~(classes[l].parent);
1.1393 + for (int i = classes[r].depth + 1; i < classes[l].depth; ++i) {
1.1394 + id = nodes[id].right;
1.1395 + }
1.1396 + while (id >= 0 && nodes[id].size == cmax) {
1.1397 + int new_id = newNode();
1.1398 + int right_id = nodes[id].right;
1.1399 +
1.1400 + popRight(id);
1.1401 + if (nodes[id].item == nodes[right_id].item) {
1.1402 + setPrio(id);
1.1403 + }
1.1404 + push(new_id, right_id);
1.1405 + pushRight(new_id, ~(classes[r].parent));
1.1406 + setPrio(new_id);
1.1407 +
1.1408 + id = nodes[id].parent;
1.1409 + classes[r].parent = ~new_id;
1.1410 + }
1.1411 + if (id < 0) {
1.1412 + int new_parent = newNode();
1.1413 + nodes[new_parent].next = -1;
1.1414 + nodes[new_parent].prev = -1;
1.1415 + nodes[new_parent].parent = ~l;
1.1416 +
1.1417 + push(new_parent, ~(classes[l].parent));
1.1418 + pushRight(new_parent, ~(classes[r].parent));
1.1419 + setPrio(new_parent);
1.1420 +
1.1421 + classes[l].parent = ~new_parent;
1.1422 + classes[l].depth += 1;
1.1423 + } else {
1.1424 + pushRight(id, ~(classes[r].parent));
1.1425 + while (id >= 0 && less(~(classes[r].parent), id)) {
1.1426 + nodes[id].prio = nodes[~(classes[r].parent)].prio;
1.1427 + nodes[id].item = nodes[~(classes[r].parent)].item;
1.1428 + id = nodes[id].parent;
1.1429 + }
1.1430 + }
1.1431 + } else if (classes[r].depth > classes[l].depth) {
1.1432 + int id = ~(classes[r].parent);
1.1433 + for (int i = classes[l].depth + 1; i < classes[r].depth; ++i) {
1.1434 + id = nodes[id].left;
1.1435 + }
1.1436 + while (id >= 0 && nodes[id].size == cmax) {
1.1437 + int new_id = newNode();
1.1438 + int left_id = nodes[id].left;
1.1439 +
1.1440 + popLeft(id);
1.1441 + if (nodes[id].prio == nodes[left_id].prio) {
1.1442 + setPrio(id);
1.1443 + }
1.1444 + push(new_id, left_id);
1.1445 + pushLeft(new_id, ~(classes[l].parent));
1.1446 + setPrio(new_id);
1.1447 +
1.1448 + id = nodes[id].parent;
1.1449 + classes[l].parent = ~new_id;
1.1450 +
1.1451 + }
1.1452 + if (id < 0) {
1.1453 + int new_parent = newNode();
1.1454 + nodes[new_parent].next = -1;
1.1455 + nodes[new_parent].prev = -1;
1.1456 + nodes[new_parent].parent = ~l;
1.1457 +
1.1458 + push(new_parent, ~(classes[r].parent));
1.1459 + pushLeft(new_parent, ~(classes[l].parent));
1.1460 + setPrio(new_parent);
1.1461 +
1.1462 + classes[r].parent = ~new_parent;
1.1463 + classes[r].depth += 1;
1.1464 + } else {
1.1465 + pushLeft(id, ~(classes[l].parent));
1.1466 + while (id >= 0 && less(~(classes[l].parent), id)) {
1.1467 + nodes[id].prio = nodes[~(classes[l].parent)].prio;
1.1468 + nodes[id].item = nodes[~(classes[l].parent)].item;
1.1469 + id = nodes[id].parent;
1.1470 + }
1.1471 + }
1.1472 + nodes[~(classes[r].parent)].parent = ~l;
1.1473 + classes[l].parent = classes[r].parent;
1.1474 + classes[l].depth = classes[r].depth;
1.1475 + } else {
1.1476 + if (classes[l].depth != 0 &&
1.1477 + nodes[~(classes[l].parent)].size +
1.1478 + nodes[~(classes[r].parent)].size <= cmax) {
1.1479 + splice(~(classes[l].parent), ~(classes[r].parent));
1.1480 + deleteNode(~(classes[r].parent));
1.1481 + if (less(~(classes[r].parent), ~(classes[l].parent))) {
1.1482 + nodes[~(classes[l].parent)].prio =
1.1483 + nodes[~(classes[r].parent)].prio;
1.1484 + nodes[~(classes[l].parent)].item =
1.1485 + nodes[~(classes[r].parent)].item;
1.1486 + }
1.1487 + } else {
1.1488 + int new_parent = newNode();
1.1489 + nodes[new_parent].next = nodes[new_parent].prev = -1;
1.1490 + push(new_parent, ~(classes[l].parent));
1.1491 + pushRight(new_parent, ~(classes[r].parent));
1.1492 + setPrio(new_parent);
1.1493 +
1.1494 + classes[l].parent = ~new_parent;
1.1495 + classes[l].depth += 1;
1.1496 + nodes[new_parent].parent = ~l;
1.1497 + }
1.1498 + }
1.1499 + if (classes[r].next != -1) {
1.1500 + classes[classes[r].next].prev = classes[r].prev;
1.1501 + }
1.1502 + classes[classes[r].prev].next = classes[r].next;
1.1503 +
1.1504 + classes[r].prev = classes[l].right;
1.1505 + classes[classes[l].right].next = r;
1.1506 + classes[l].right = r;
1.1507 + classes[r].parent = l;
1.1508 +
1.1509 + classes[r].next = -1;
1.1510 + classes[r].depth = rln;
1.1511 + }
1.1512 + }
1.1513 + return class_id;
1.1514 + }
1.1515 +
1.1516 + /// \brief Split the class to subclasses.
1.1517 + ///
1.1518 + /// The current function splits the given class. The join, which
1.1519 + /// made the current class, stored a reference to the
1.1520 + /// subclasses. The \c splitClass() member restores the classes
1.1521 + /// and creates the heaps. The parameter is an STL output iterator
1.1522 + /// which will be filled with the subclass ids. The time
1.1523 + /// complexity is O(log(n)*k) where n is the overall number of
1.1524 + /// nodes in the splitted classes and k is the number of the
1.1525 + /// classes.
1.1526 + template <typename Iterator>
1.1527 + void split(int cls, Iterator out) {
1.1528 + std::vector<int> cs;
1.1529 + { // splitting union-find
1.1530 + int id = cls;
1.1531 + int l = classes[id].left;
1.1532 +
1.1533 + classes[l].parent = classes[id].parent;
1.1534 + classes[l].depth = classes[id].depth;
1.1535 +
1.1536 + nodes[~(classes[l].parent)].parent = ~l;
1.1537 +
1.1538 + *out++ = l;
1.1539 +
1.1540 + while (l != -1) {
1.1541 + cs.push_back(l);
1.1542 + l = classes[l].next;
1.1543 + }
1.1544 +
1.1545 + classes[classes[id].right].next = first_class;
1.1546 + classes[first_class].prev = classes[id].right;
1.1547 + first_class = classes[id].left;
1.1548 +
1.1549 + if (classes[id].next != -1) {
1.1550 + classes[classes[id].next].prev = classes[id].prev;
1.1551 + }
1.1552 + classes[classes[id].prev].next = classes[id].next;
1.1553 +
1.1554 + deleteClass(id);
1.1555 + }
1.1556 +
1.1557 + {
1.1558 + for (int i = 1; i < int(cs.size()); ++i) {
1.1559 + int l = classes[cs[i]].depth;
1.1560 + while (nodes[nodes[l].parent].left == l) {
1.1561 + l = nodes[l].parent;
1.1562 + }
1.1563 + int r = l;
1.1564 + while (nodes[l].parent >= 0) {
1.1565 + l = nodes[l].parent;
1.1566 + int new_node = newNode();
1.1567 +
1.1568 + nodes[new_node].prev = -1;
1.1569 + nodes[new_node].next = -1;
1.1570 +
1.1571 + split(r, new_node);
1.1572 + pushAfter(l, new_node);
1.1573 + setPrio(l);
1.1574 + setPrio(new_node);
1.1575 + r = new_node;
1.1576 + }
1.1577 + classes[cs[i]].parent = ~r;
1.1578 + classes[cs[i]].depth = classes[~(nodes[l].parent)].depth;
1.1579 + nodes[r].parent = ~cs[i];
1.1580 +
1.1581 + nodes[l].next = -1;
1.1582 + nodes[r].prev = -1;
1.1583 +
1.1584 + repairRight(~(nodes[l].parent));
1.1585 + repairLeft(cs[i]);
1.1586 +
1.1587 + *out++ = cs[i];
1.1588 + }
1.1589 + }
1.1590 + }
1.1591 +
1.1592 + /// \brief Gives back the priority of the current item.
1.1593 + ///
1.1594 + /// \return Gives back the priority of the current item.
1.1595 + const Value& operator[](const Item& item) const {
1.1596 + return nodes[index[item]].prio;
1.1597 + }
1.1598 +
1.1599 + /// \brief Sets the priority of the current item.
1.1600 + ///
1.1601 + /// Sets the priority of the current item.
1.1602 + void set(const Item& item, const Value& prio) {
1.1603 + if (comp(prio, nodes[index[item]].prio)) {
1.1604 + decrease(item, prio);
1.1605 + } else if (!comp(prio, nodes[index[item]].prio)) {
1.1606 + increase(item, prio);
1.1607 + }
1.1608 + }
1.1609 +
1.1610 + /// \brief Increase the priority of the current item.
1.1611 + ///
1.1612 + /// Increase the priority of the current item.
1.1613 + void increase(const Item& item, const Value& prio) {
1.1614 + int id = index[item];
1.1615 + int kd = nodes[id].parent;
1.1616 + nodes[id].prio = prio;
1.1617 + while (kd >= 0 && nodes[kd].item == item) {
1.1618 + setPrio(kd);
1.1619 + kd = nodes[kd].parent;
1.1620 + }
1.1621 + }
1.1622 +
1.1623 + /// \brief Increase the priority of the current item.
1.1624 + ///
1.1625 + /// Increase the priority of the current item.
1.1626 + void decrease(const Item& item, const Value& prio) {
1.1627 + int id = index[item];
1.1628 + int kd = nodes[id].parent;
1.1629 + nodes[id].prio = prio;
1.1630 + while (kd >= 0 && less(id, kd)) {
1.1631 + nodes[kd].prio = prio;
1.1632 + nodes[kd].item = item;
1.1633 + kd = nodes[kd].parent;
1.1634 + }
1.1635 + }
1.1636 +
1.1637 + /// \brief Gives back the minimum priority of the class.
1.1638 + ///
1.1639 + /// \return Gives back the minimum priority of the class.
1.1640 + const Value& classPrio(int cls) const {
1.1641 + return nodes[~(classes[cls].parent)].prio;
1.1642 + }
1.1643 +
1.1644 + /// \brief Gives back the minimum priority item of the class.
1.1645 + ///
1.1646 + /// \return Gives back the minimum priority item of the class.
1.1647 + const Item& classTop(int cls) const {
1.1648 + return nodes[~(classes[cls].parent)].item;
1.1649 + }
1.1650 +
1.1651 + /// \brief Gives back a representant item of the class.
1.1652 + ///
1.1653 + /// The representant is indpendent from the priorities of the
1.1654 + /// items.
1.1655 + /// \return Gives back a representant item of the class.
1.1656 + const Item& classRep(int id) const {
1.1657 + int parent = classes[id].parent;
1.1658 + return nodes[parent >= 0 ? classes[id].depth : leftNode(id)].item;
1.1659 + }
1.1660 +
1.1661 + /// \brief Lemon style iterator for the items of a class.
1.1662 + ///
1.1663 + /// ClassIt is a lemon style iterator for the components. It iterates
1.1664 + /// on the items of a class. By example if you want to iterate on
1.1665 + /// each items of each classes then you may write the next code.
1.1666 + ///\code
1.1667 + /// for (ClassIt cit(huf); cit != INVALID; ++cit) {
1.1668 + /// std::cout << "Class: ";
1.1669 + /// for (ItemIt iit(huf, cit); iit != INVALID; ++iit) {
1.1670 + /// std::cout << toString(iit) << ' ' << std::endl;
1.1671 + /// }
1.1672 + /// std::cout << std::endl;
1.1673 + /// }
1.1674 + ///\endcode
1.1675 + class ItemIt {
1.1676 + private:
1.1677 +
1.1678 + const HeapUnionFind* _huf;
1.1679 + int _id, _lid;
1.1680 +
1.1681 + public:
1.1682 +
1.1683 + /// \brief Default constructor
1.1684 + ///
1.1685 + /// Default constructor
1.1686 + ItemIt() {}
1.1687 +
1.1688 + ItemIt(const HeapUnionFind& huf, int cls) : _huf(&huf) {
1.1689 + int id = cls;
1.1690 + int parent = _huf->classes[id].parent;
1.1691 + if (parent >= 0) {
1.1692 + _id = _huf->classes[id].depth;
1.1693 + if (_huf->classes[id].next != -1) {
1.1694 + _lid = _huf->classes[_huf->classes[id].next].depth;
1.1695 + } else {
1.1696 + _lid = -1;
1.1697 + }
1.1698 + } else {
1.1699 + _id = _huf->leftNode(id);
1.1700 + _lid = -1;
1.1701 + }
1.1702 + }
1.1703 +
1.1704 + /// \brief Increment operator
1.1705 + ///
1.1706 + /// It steps to the next item in the class.
1.1707 + ItemIt& operator++() {
1.1708 + _id = _huf->nextNode(_id);
1.1709 + return *this;
1.1710 + }
1.1711 +
1.1712 + /// \brief Conversion operator
1.1713 + ///
1.1714 + /// It converts the iterator to the current item.
1.1715 + operator const Item&() const {
1.1716 + return _huf->nodes[_id].item;
1.1717 + }
1.1718 +
1.1719 + /// \brief Equality operator
1.1720 + ///
1.1721 + /// Equality operator
1.1722 + bool operator==(const ItemIt& i) {
1.1723 + return i._id == _id;
1.1724 + }
1.1725 +
1.1726 + /// \brief Inequality operator
1.1727 + ///
1.1728 + /// Inequality operator
1.1729 + bool operator!=(const ItemIt& i) {
1.1730 + return i._id != _id;
1.1731 + }
1.1732 +
1.1733 + /// \brief Equality operator
1.1734 + ///
1.1735 + /// Equality operator
1.1736 + bool operator==(Invalid) {
1.1737 + return _id == _lid;
1.1738 + }
1.1739 +
1.1740 + /// \brief Inequality operator
1.1741 + ///
1.1742 + /// Inequality operator
1.1743 + bool operator!=(Invalid) {
1.1744 + return _id != _lid;
1.1745 + }
1.1746 +
1.1747 + };
1.1748 +
1.1749 + /// \brief Class iterator
1.1750 + ///
1.1751 + /// The iterator stores
1.1752 + class ClassIt {
1.1753 + private:
1.1754 +
1.1755 + const HeapUnionFind* _huf;
1.1756 + int _id;
1.1757 +
1.1758 + public:
1.1759 +
1.1760 + ClassIt(const HeapUnionFind& huf)
1.1761 + : _huf(&huf), _id(huf.first_class) {}
1.1762 +
1.1763 + ClassIt(const HeapUnionFind& huf, int cls)
1.1764 + : _huf(&huf), _id(huf.classes[cls].left) {}
1.1765 +
1.1766 + ClassIt(Invalid) : _huf(0), _id(-1) {}
1.1767 +
1.1768 + const ClassIt& operator++() {
1.1769 + _id = _huf->classes[_id].next;
1.1770 + return *this;
1.1771 + }
1.1772 +
1.1773 + /// \brief Equality operator
1.1774 + ///
1.1775 + /// Equality operator
1.1776 + bool operator==(const ClassIt& i) {
1.1777 + return i._id == _id;
1.1778 + }
1.1779 +
1.1780 + /// \brief Inequality operator
1.1781 + ///
1.1782 + /// Inequality operator
1.1783 + bool operator!=(const ClassIt& i) {
1.1784 + return i._id != _id;
1.1785 + }
1.1786 +
1.1787 + operator int() const {
1.1788 + return _id;
1.1789 + }
1.1790 +
1.1791 + };
1.1792 +
1.1793 + };
1.1794 +
1.1795 + //! @}
1.1796 +
1.1797 +} //namespace lemon
1.1798 +
1.1799 +#endif //LEMON_UNION_FIND_H