1.1 --- a/lemon/unionfind.h Sun Jul 13 16:46:56 2008 +0100
1.2 +++ b/lemon/unionfind.h Sun Jul 13 19:51:02 2008 +0100
1.3 @@ -1,6 +1,6 @@
1.4 -/* -*- C++ -*-
1.5 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
1.6 *
1.7 - * This file is a part of LEMON, a generic C++ optimization library
1.8 + * This file is a part of LEMON, a generic C++ optimization library.
1.9 *
1.10 * Copyright (C) 2003-2008
1.11 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.12 @@ -38,10 +38,10 @@
1.13 ///
1.14 /// \brief A \e Union-Find data structure implementation
1.15 ///
1.16 - /// The class implements the \e Union-Find data structure.
1.17 + /// The class implements the \e Union-Find data structure.
1.18 /// The union operation uses rank heuristic, while
1.19 /// the find operation uses path compression.
1.20 - /// This is a very simple but efficient implementation, providing
1.21 + /// This is a very simple but efficient implementation, providing
1.22 /// only four methods: join (union), find, insert and size.
1.23 /// For more features see the \ref UnionFindEnum class.
1.24 ///
1.25 @@ -50,7 +50,7 @@
1.26 /// \sa kruskal()
1.27 ///
1.28 /// \pre You need to add all the elements by the \ref insert()
1.29 - /// method.
1.30 + /// method.
1.31 template <typename _ItemIntMap>
1.32 class UnionFind {
1.33 public:
1.34 @@ -111,7 +111,7 @@
1.35
1.36 /// \brief Inserts a new element into the structure.
1.37 ///
1.38 - /// This method inserts a new element into the data structure.
1.39 + /// This method inserts a new element into the data structure.
1.40 ///
1.41 /// The method returns the index of the new component.
1.42 int insert(const Item& a) {
1.43 @@ -123,7 +123,7 @@
1.44
1.45 /// \brief Joining the components of element \e a and element \e b.
1.46 ///
1.47 - /// This is the \e union operation of the Union-Find structure.
1.48 + /// This is the \e union operation of the Union-Find structure.
1.49 /// Joins the component of element \e a and component of
1.50 /// element \e b. If \e a and \e b are in the same component then
1.51 /// it returns false otherwise it returns true.
1.52 @@ -131,15 +131,15 @@
1.53 int ka = repIndex(index[a]);
1.54 int kb = repIndex(index[b]);
1.55
1.56 - if ( ka == kb )
1.57 - return false;
1.58 + if ( ka == kb )
1.59 + return false;
1.60
1.61 if (items[ka] < items[kb]) {
1.62 - items[ka] += items[kb];
1.63 - items[kb] = ka;
1.64 + items[ka] += items[kb];
1.65 + items[kb] = ka;
1.66 } else {
1.67 - items[kb] += items[ka];
1.68 - items[ka] = kb;
1.69 + items[kb] += items[ka];
1.70 + items[ka] = kb;
1.71 }
1.72 return true;
1.73 }
1.74 @@ -173,12 +173,12 @@
1.75 template <typename _ItemIntMap>
1.76 class UnionFindEnum {
1.77 public:
1.78 -
1.79 +
1.80 typedef _ItemIntMap ItemIntMap;
1.81 typedef typename ItemIntMap::Key Item;
1.82
1.83 private:
1.84 -
1.85 +
1.86 ItemIntMap& index;
1.87
1.88 // If the parent stores negative value for an item then that item
1.89 @@ -202,31 +202,31 @@
1.90 int firstItem;
1.91 int next, prev;
1.92 };
1.93 -
1.94 +
1.95 std::vector<ClassT> classes;
1.96 int firstClass, firstFreeClass;
1.97
1.98 int newClass() {
1.99 if (firstFreeClass == -1) {
1.100 - int cdx = classes.size();
1.101 - classes.push_back(ClassT());
1.102 - return cdx;
1.103 + int cdx = classes.size();
1.104 + classes.push_back(ClassT());
1.105 + return cdx;
1.106 } else {
1.107 - int cdx = firstFreeClass;
1.108 - firstFreeClass = classes[firstFreeClass].next;
1.109 - return cdx;
1.110 + int cdx = firstFreeClass;
1.111 + firstFreeClass = classes[firstFreeClass].next;
1.112 + return cdx;
1.113 }
1.114 }
1.115
1.116 int newItem() {
1.117 if (firstFreeItem == -1) {
1.118 - int idx = items.size();
1.119 - items.push_back(ItemT());
1.120 - return idx;
1.121 + int idx = items.size();
1.122 + items.push_back(ItemT());
1.123 + return idx;
1.124 } else {
1.125 - int idx = firstFreeItem;
1.126 - firstFreeItem = items[firstFreeItem].next;
1.127 - return idx;
1.128 + int idx = firstFreeItem;
1.129 + firstFreeItem = items[firstFreeItem].next;
1.130 + return idx;
1.131 }
1.132 }
1.133
1.134 @@ -267,7 +267,7 @@
1.135 void unlaceItem(int idx) {
1.136 items[items[idx].prev].next = items[idx].next;
1.137 items[items[idx].next].prev = items[idx].prev;
1.138 -
1.139 +
1.140 items[idx].next = firstFreeItem;
1.141 firstFreeItem = idx;
1.142 }
1.143 @@ -278,7 +278,7 @@
1.144 int tmp = items[ak].prev;
1.145 items[ak].prev = items[bk].prev;
1.146 items[bk].prev = tmp;
1.147 -
1.148 +
1.149 }
1.150
1.151 void laceClass(int cls) {
1.152 @@ -288,7 +288,7 @@
1.153 classes[cls].next = firstClass;
1.154 classes[cls].prev = -1;
1.155 firstClass = cls;
1.156 - }
1.157 + }
1.158
1.159 void unlaceClass(int cls) {
1.160 if (classes[cls].prev != -1) {
1.161 @@ -299,17 +299,17 @@
1.162 if (classes[cls].next != -1) {
1.163 classes[classes[cls].next].prev = classes[cls].prev;
1.164 }
1.165 -
1.166 +
1.167 classes[cls].next = firstFreeClass;
1.168 firstFreeClass = cls;
1.169 - }
1.170 + }
1.171
1.172 public:
1.173
1.174 - UnionFindEnum(ItemIntMap& _index)
1.175 - : index(_index), items(), firstFreeItem(-1),
1.176 - firstClass(-1), firstFreeClass(-1) {}
1.177 -
1.178 + UnionFindEnum(ItemIntMap& _index)
1.179 + : index(_index), items(), firstFreeItem(-1),
1.180 + firstClass(-1), firstFreeClass(-1) {}
1.181 +
1.182 /// \brief Inserts the given element into a new component.
1.183 ///
1.184 /// This method creates a new component consisting only of the
1.185 @@ -332,14 +332,14 @@
1.186 classes[cdx].firstItem = idx;
1.187
1.188 firstClass = cdx;
1.189 -
1.190 +
1.191 return cdx;
1.192 }
1.193
1.194 /// \brief Inserts the given element into the component of the others.
1.195 ///
1.196 /// This methods inserts the element \e a into the component of the
1.197 - /// element \e comp.
1.198 + /// element \e comp.
1.199 void insert(const Item& item, int cls) {
1.200 int rdx = classes[cls].firstItem;
1.201 int idx = newItem();
1.202 @@ -372,7 +372,7 @@
1.203
1.204 /// \brief Joining the component of element \e a and element \e b.
1.205 ///
1.206 - /// This is the \e union operation of the Union-Find structure.
1.207 + /// This is the \e union operation of the Union-Find structure.
1.208 /// Joins the component of element \e a and component of
1.209 /// element \e b. If \e a and \e b are in the same component then
1.210 /// returns -1 else returns the remaining class.
1.211 @@ -382,7 +382,7 @@
1.212 int bk = repIndex(index[b]);
1.213
1.214 if (ak == bk) {
1.215 - return -1;
1.216 + return -1;
1.217 }
1.218
1.219 int acx = ~(items[ak].parent);
1.220 @@ -391,15 +391,15 @@
1.221 int rcx;
1.222
1.223 if (classes[acx].size > classes[bcx].size) {
1.224 - classes[acx].size += classes[bcx].size;
1.225 - items[bk].parent = ak;
1.226 + classes[acx].size += classes[bcx].size;
1.227 + items[bk].parent = ak;
1.228 unlaceClass(bcx);
1.229 - rcx = acx;
1.230 + rcx = acx;
1.231 } else {
1.232 - classes[bcx].size += classes[acx].size;
1.233 - items[ak].parent = bk;
1.234 + classes[bcx].size += classes[acx].size;
1.235 + items[ak].parent = bk;
1.236 unlaceClass(acx);
1.237 - rcx = bcx;
1.238 + rcx = bcx;
1.239 }
1.240 spliceItems(ak, bk);
1.241
1.242 @@ -413,7 +413,7 @@
1.243 return classes[cls].size;
1.244 }
1.245
1.246 - /// \brief Splits up the component.
1.247 + /// \brief Splits up the component.
1.248 ///
1.249 /// Splitting the component into singleton components (component
1.250 /// of size one).
1.251 @@ -423,15 +423,15 @@
1.252 while (idx != fdx) {
1.253 int next = items[idx].next;
1.254
1.255 - singletonItem(idx);
1.256 + singletonItem(idx);
1.257
1.258 - int cdx = newClass();
1.259 + int cdx = newClass();
1.260 items[idx].parent = ~cdx;
1.261
1.262 - laceClass(cdx);
1.263 - classes[cdx].size = 1;
1.264 - classes[cdx].firstItem = idx;
1.265 -
1.266 + laceClass(cdx);
1.267 + classes[cdx].size = 1;
1.268 + classes[cdx].firstItem = idx;
1.269 +
1.270 idx = next;
1.271 }
1.272
1.273 @@ -439,7 +439,7 @@
1.274 items[idx].next = idx;
1.275
1.276 classes[~(items[idx].parent)].size = 1;
1.277 -
1.278 +
1.279 }
1.280
1.281 /// \brief Removes the given element from the structure.
1.282 @@ -457,22 +457,22 @@
1.283
1.284 int cdx = classIndex(idx);
1.285 if (idx == fdx) {
1.286 - unlaceClass(cdx);
1.287 - items[idx].next = firstFreeItem;
1.288 - firstFreeItem = idx;
1.289 - return;
1.290 + unlaceClass(cdx);
1.291 + items[idx].next = firstFreeItem;
1.292 + firstFreeItem = idx;
1.293 + return;
1.294 } else {
1.295 - classes[cdx].firstItem = fdx;
1.296 - --classes[cdx].size;
1.297 - items[fdx].parent = ~cdx;
1.298 + classes[cdx].firstItem = fdx;
1.299 + --classes[cdx].size;
1.300 + items[fdx].parent = ~cdx;
1.301
1.302 - unlaceItem(idx);
1.303 - idx = items[fdx].next;
1.304 - while (idx != fdx) {
1.305 - items[idx].parent = fdx;
1.306 - idx = items[idx].next;
1.307 - }
1.308 -
1.309 + unlaceItem(idx);
1.310 + idx = items[fdx].next;
1.311 + while (idx != fdx) {
1.312 + items[idx].parent = fdx;
1.313 + idx = items[idx].next;
1.314 + }
1.315 +
1.316 }
1.317
1.318 }
1.319 @@ -514,7 +514,7 @@
1.320 ///
1.321 /// Constructor to get invalid iterator
1.322 ClassIt(Invalid) : unionFind(0), cdx(-1) {}
1.323 -
1.324 +
1.325 /// \brief Increment operator
1.326 ///
1.327 /// It steps to the next representant item.
1.328 @@ -522,7 +522,7 @@
1.329 cdx = unionFind->classes[cdx].next;
1.330 return *this;
1.331 }
1.332 -
1.333 +
1.334 /// \brief Conversion operator
1.335 ///
1.336 /// It converts the iterator to the current representant item.
1.337 @@ -533,17 +533,17 @@
1.338 /// \brief Equality operator
1.339 ///
1.340 /// Equality operator
1.341 - bool operator==(const ClassIt& i) {
1.342 + bool operator==(const ClassIt& i) {
1.343 return i.cdx == cdx;
1.344 }
1.345
1.346 /// \brief Inequality operator
1.347 ///
1.348 /// Inequality operator
1.349 - bool operator!=(const ClassIt& i) {
1.350 + bool operator!=(const ClassIt& i) {
1.351 return i.cdx != cdx;
1.352 }
1.353 -
1.354 +
1.355 private:
1.356 const UnionFindEnum* unionFind;
1.357 int cdx;
1.358 @@ -577,7 +577,7 @@
1.359 ///
1.360 /// Constructor to get invalid iterator
1.361 ItemIt(Invalid) : unionFind(0), idx(-1) {}
1.362 -
1.363 +
1.364 /// \brief Increment operator
1.365 ///
1.366 /// It steps to the next item in the class.
1.367 @@ -586,7 +586,7 @@
1.368 if (idx == fdx) idx = -1;
1.369 return *this;
1.370 }
1.371 -
1.372 +
1.373 /// \brief Conversion operator
1.374 ///
1.375 /// It converts the iterator to the current item.
1.376 @@ -597,17 +597,17 @@
1.377 /// \brief Equality operator
1.378 ///
1.379 /// Equality operator
1.380 - bool operator==(const ItemIt& i) {
1.381 + bool operator==(const ItemIt& i) {
1.382 return i.idx == idx;
1.383 }
1.384
1.385 /// \brief Inequality operator
1.386 ///
1.387 /// Inequality operator
1.388 - bool operator!=(const ItemIt& i) {
1.389 + bool operator!=(const ItemIt& i) {
1.390 return i.idx != idx;
1.391 }
1.392 -
1.393 +
1.394 private:
1.395 const UnionFindEnum* unionFind;
1.396 int idx, fdx;
1.397 @@ -630,12 +630,12 @@
1.398 template <typename _ItemIntMap>
1.399 class ExtendFindEnum {
1.400 public:
1.401 -
1.402 +
1.403 typedef _ItemIntMap ItemIntMap;
1.404 typedef typename ItemIntMap::Key Item;
1.405
1.406 private:
1.407 -
1.408 +
1.409 ItemIntMap& index;
1.410
1.411 struct ItemT {
1.412 @@ -658,33 +658,33 @@
1.413
1.414 int newClass() {
1.415 if (firstFreeClass != -1) {
1.416 - int cdx = firstFreeClass;
1.417 - firstFreeClass = classes[cdx].next;
1.418 - return cdx;
1.419 + int cdx = firstFreeClass;
1.420 + firstFreeClass = classes[cdx].next;
1.421 + return cdx;
1.422 } else {
1.423 - classes.push_back(ClassT());
1.424 - return classes.size() - 1;
1.425 + classes.push_back(ClassT());
1.426 + return classes.size() - 1;
1.427 }
1.428 }
1.429
1.430 int newItem() {
1.431 if (firstFreeItem != -1) {
1.432 - int idx = firstFreeItem;
1.433 - firstFreeItem = items[idx].next;
1.434 - return idx;
1.435 + int idx = firstFreeItem;
1.436 + firstFreeItem = items[idx].next;
1.437 + return idx;
1.438 } else {
1.439 - items.push_back(ItemT());
1.440 - return items.size() - 1;
1.441 + items.push_back(ItemT());
1.442 + return items.size() - 1;
1.443 }
1.444 }
1.445
1.446 public:
1.447
1.448 /// \brief Constructor
1.449 - ExtendFindEnum(ItemIntMap& _index)
1.450 - : index(_index), items(), firstFreeItem(-1),
1.451 - classes(), firstClass(-1), firstFreeClass(-1) {}
1.452 -
1.453 + ExtendFindEnum(ItemIntMap& _index)
1.454 + : index(_index), items(), firstFreeItem(-1),
1.455 + classes(), firstClass(-1), firstFreeClass(-1) {}
1.456 +
1.457 /// \brief Inserts the given element into a new component.
1.458 ///
1.459 /// This method creates a new component consisting only of the
1.460 @@ -694,10 +694,10 @@
1.461 classes[cdx].prev = -1;
1.462 classes[cdx].next = firstClass;
1.463 if (firstClass != -1) {
1.464 - classes[firstClass].prev = cdx;
1.465 + classes[firstClass].prev = cdx;
1.466 }
1.467 firstClass = cdx;
1.468 -
1.469 +
1.470 int idx = newItem();
1.471 items[idx].item = item;
1.472 items[idx].cls = cdx;
1.473 @@ -707,7 +707,7 @@
1.474 classes[cdx].firstItem = idx;
1.475
1.476 index.set(item, idx);
1.477 -
1.478 +
1.479 return cdx;
1.480 }
1.481
1.482 @@ -750,7 +750,7 @@
1.483 Item item(int cls) const {
1.484 return items[classes[cls].firstItem].item;
1.485 }
1.486 -
1.487 +
1.488 /// \brief Removes the given element from the structure.
1.489 ///
1.490 /// Removes the element from its component and if the component becomes
1.491 @@ -761,29 +761,29 @@
1.492 void erase(const Item &item) {
1.493 int idx = index[item];
1.494 int cdx = items[idx].cls;
1.495 -
1.496 +
1.497 if (idx == items[idx].next) {
1.498 - if (classes[cdx].prev != -1) {
1.499 - classes[classes[cdx].prev].next = classes[cdx].next;
1.500 - } else {
1.501 - firstClass = classes[cdx].next;
1.502 - }
1.503 - if (classes[cdx].next != -1) {
1.504 - classes[classes[cdx].next].prev = classes[cdx].prev;
1.505 - }
1.506 - classes[cdx].next = firstFreeClass;
1.507 - firstFreeClass = cdx;
1.508 + if (classes[cdx].prev != -1) {
1.509 + classes[classes[cdx].prev].next = classes[cdx].next;
1.510 + } else {
1.511 + firstClass = classes[cdx].next;
1.512 + }
1.513 + if (classes[cdx].next != -1) {
1.514 + classes[classes[cdx].next].prev = classes[cdx].prev;
1.515 + }
1.516 + classes[cdx].next = firstFreeClass;
1.517 + firstFreeClass = cdx;
1.518 } else {
1.519 - classes[cdx].firstItem = items[idx].next;
1.520 - items[items[idx].next].prev = items[idx].prev;
1.521 - items[items[idx].prev].next = items[idx].next;
1.522 + classes[cdx].firstItem = items[idx].next;
1.523 + items[items[idx].next].prev = items[idx].prev;
1.524 + items[items[idx].prev].next = items[idx].next;
1.525 }
1.526 items[idx].next = firstFreeItem;
1.527 firstFreeItem = idx;
1.528 -
1.529 - }
1.530
1.531 -
1.532 + }
1.533 +
1.534 +
1.535 /// \brief Removes the component of the given element from the structure.
1.536 ///
1.537 /// Removes the component of the given element from the structure.
1.538 @@ -796,12 +796,12 @@
1.539 firstFreeItem = idx;
1.540
1.541 if (classes[cdx].prev != -1) {
1.542 - classes[classes[cdx].prev].next = classes[cdx].next;
1.543 + classes[classes[cdx].prev].next = classes[cdx].next;
1.544 } else {
1.545 - firstClass = classes[cdx].next;
1.546 + firstClass = classes[cdx].next;
1.547 }
1.548 if (classes[cdx].next != -1) {
1.549 - classes[classes[cdx].next].prev = classes[cdx].prev;
1.550 + classes[classes[cdx].next].prev = classes[cdx].prev;
1.551 }
1.552 classes[cdx].next = firstFreeClass;
1.553 firstFreeClass = cdx;
1.554 @@ -824,7 +824,7 @@
1.555 ///
1.556 /// Constructor to get invalid iterator
1.557 ClassIt(Invalid) : extendFind(0), cdx(-1) {}
1.558 -
1.559 +
1.560 /// \brief Increment operator
1.561 ///
1.562 /// It steps to the next representant item.
1.563 @@ -832,7 +832,7 @@
1.564 cdx = extendFind->classes[cdx].next;
1.565 return *this;
1.566 }
1.567 -
1.568 +
1.569 /// \brief Conversion operator
1.570 ///
1.571 /// It converts the iterator to the current class id.
1.572 @@ -843,17 +843,17 @@
1.573 /// \brief Equality operator
1.574 ///
1.575 /// Equality operator
1.576 - bool operator==(const ClassIt& i) {
1.577 + bool operator==(const ClassIt& i) {
1.578 return i.cdx == cdx;
1.579 }
1.580
1.581 /// \brief Inequality operator
1.582 ///
1.583 /// Inequality operator
1.584 - bool operator!=(const ClassIt& i) {
1.585 + bool operator!=(const ClassIt& i) {
1.586 return i.cdx != cdx;
1.587 }
1.588 -
1.589 +
1.590 private:
1.591 const ExtendFindEnum* extendFind;
1.592 int cdx;
1.593 @@ -887,16 +887,16 @@
1.594 ///
1.595 /// Constructor to get invalid iterator
1.596 ItemIt(Invalid) : extendFind(0), idx(-1) {}
1.597 -
1.598 +
1.599 /// \brief Increment operator
1.600 ///
1.601 /// It steps to the next item in the class.
1.602 ItemIt& operator++() {
1.603 idx = extendFind->items[idx].next;
1.604 - if (fdx == idx) idx = -1;
1.605 + if (fdx == idx) idx = -1;
1.606 return *this;
1.607 }
1.608 -
1.609 +
1.610 /// \brief Conversion operator
1.611 ///
1.612 /// It converts the iterator to the current item.
1.613 @@ -907,17 +907,17 @@
1.614 /// \brief Equality operator
1.615 ///
1.616 /// Equality operator
1.617 - bool operator==(const ItemIt& i) {
1.618 + bool operator==(const ItemIt& i) {
1.619 return i.idx == idx;
1.620 }
1.621
1.622 /// \brief Inequality operator
1.623 ///
1.624 /// Inequality operator
1.625 - bool operator!=(const ItemIt& i) {
1.626 + bool operator!=(const ItemIt& i) {
1.627 return i.idx != idx;
1.628 }
1.629 -
1.630 +
1.631 private:
1.632 const ExtendFindEnum* extendFind;
1.633 int idx, fdx;
1.634 @@ -949,11 +949,11 @@
1.635 /// \pre You need to add all the elements by the \ref insert()
1.636 /// method.
1.637 ///
1.638 - template <typename _Value, typename _ItemIntMap,
1.639 + template <typename _Value, typename _ItemIntMap,
1.640 typename _Comp = std::less<_Value> >
1.641 class HeapUnionFind {
1.642 public:
1.643 -
1.644 +
1.645 typedef _Value Value;
1.646 typedef typename _ItemIntMap::Key Item;
1.647
1.648 @@ -1054,7 +1054,7 @@
1.649 }
1.650 id = nodes[id].next;
1.651 while (depth--) {
1.652 - id = nodes[id].left;
1.653 + id = nodes[id].left;
1.654 }
1.655 return id;
1.656 }
1.657 @@ -1132,7 +1132,7 @@
1.658 int kd = nodes[id].parent;
1.659 nodes[kd].right = nodes[id].prev;
1.660 nodes[nodes[id].prev].next = -1;
1.661 -
1.662 +
1.663 nodes[jd].left = id;
1.664 nodes[id].prev = -1;
1.665 int num = 0;
1.666 @@ -1141,7 +1141,7 @@
1.667 nodes[jd].right = id;
1.668 id = nodes[id].next;
1.669 ++num;
1.670 - }
1.671 + }
1.672 nodes[kd].size -= num;
1.673 nodes[jd].size = num;
1.674 }
1.675 @@ -1165,84 +1165,84 @@
1.676 void repairLeft(int id) {
1.677 int jd = ~(classes[id].parent);
1.678 while (nodes[jd].left != -1) {
1.679 - int kd = nodes[jd].left;
1.680 - if (nodes[jd].size == 1) {
1.681 - if (nodes[jd].parent < 0) {
1.682 - classes[id].parent = ~kd;
1.683 - classes[id].depth -= 1;
1.684 - nodes[kd].parent = ~id;
1.685 - deleteNode(jd);
1.686 - jd = kd;
1.687 - } else {
1.688 - int pd = nodes[jd].parent;
1.689 - if (nodes[nodes[jd].next].size < cmax) {
1.690 - pushLeft(nodes[jd].next, nodes[jd].left);
1.691 - if (less(nodes[jd].left, nodes[jd].next)) {
1.692 - nodes[nodes[jd].next].prio = nodes[nodes[jd].left].prio;
1.693 - nodes[nodes[jd].next].item = nodes[nodes[jd].left].item;
1.694 - }
1.695 - popLeft(pd);
1.696 - deleteNode(jd);
1.697 - jd = pd;
1.698 - } else {
1.699 - int ld = nodes[nodes[jd].next].left;
1.700 - popLeft(nodes[jd].next);
1.701 - pushRight(jd, ld);
1.702 - if (less(ld, nodes[jd].left)) {
1.703 - nodes[jd].item = nodes[ld].item;
1.704 - nodes[jd].prio = nodes[jd].prio;
1.705 - }
1.706 - if (nodes[nodes[jd].next].item == nodes[ld].item) {
1.707 - setPrio(nodes[jd].next);
1.708 - }
1.709 - jd = nodes[jd].left;
1.710 - }
1.711 - }
1.712 - } else {
1.713 - jd = nodes[jd].left;
1.714 - }
1.715 + int kd = nodes[jd].left;
1.716 + if (nodes[jd].size == 1) {
1.717 + if (nodes[jd].parent < 0) {
1.718 + classes[id].parent = ~kd;
1.719 + classes[id].depth -= 1;
1.720 + nodes[kd].parent = ~id;
1.721 + deleteNode(jd);
1.722 + jd = kd;
1.723 + } else {
1.724 + int pd = nodes[jd].parent;
1.725 + if (nodes[nodes[jd].next].size < cmax) {
1.726 + pushLeft(nodes[jd].next, nodes[jd].left);
1.727 + if (less(nodes[jd].left, nodes[jd].next)) {
1.728 + nodes[nodes[jd].next].prio = nodes[nodes[jd].left].prio;
1.729 + nodes[nodes[jd].next].item = nodes[nodes[jd].left].item;
1.730 + }
1.731 + popLeft(pd);
1.732 + deleteNode(jd);
1.733 + jd = pd;
1.734 + } else {
1.735 + int ld = nodes[nodes[jd].next].left;
1.736 + popLeft(nodes[jd].next);
1.737 + pushRight(jd, ld);
1.738 + if (less(ld, nodes[jd].left)) {
1.739 + nodes[jd].item = nodes[ld].item;
1.740 + nodes[jd].prio = nodes[jd].prio;
1.741 + }
1.742 + if (nodes[nodes[jd].next].item == nodes[ld].item) {
1.743 + setPrio(nodes[jd].next);
1.744 + }
1.745 + jd = nodes[jd].left;
1.746 + }
1.747 + }
1.748 + } else {
1.749 + jd = nodes[jd].left;
1.750 + }
1.751 }
1.752 - }
1.753 + }
1.754
1.755 void repairRight(int id) {
1.756 int jd = ~(classes[id].parent);
1.757 while (nodes[jd].right != -1) {
1.758 - int kd = nodes[jd].right;
1.759 - if (nodes[jd].size == 1) {
1.760 - if (nodes[jd].parent < 0) {
1.761 - classes[id].parent = ~kd;
1.762 - classes[id].depth -= 1;
1.763 - nodes[kd].parent = ~id;
1.764 - deleteNode(jd);
1.765 - jd = kd;
1.766 - } else {
1.767 - int pd = nodes[jd].parent;
1.768 - if (nodes[nodes[jd].prev].size < cmax) {
1.769 - pushRight(nodes[jd].prev, nodes[jd].right);
1.770 - if (less(nodes[jd].right, nodes[jd].prev)) {
1.771 - nodes[nodes[jd].prev].prio = nodes[nodes[jd].right].prio;
1.772 - nodes[nodes[jd].prev].item = nodes[nodes[jd].right].item;
1.773 - }
1.774 - popRight(pd);
1.775 - deleteNode(jd);
1.776 - jd = pd;
1.777 - } else {
1.778 - int ld = nodes[nodes[jd].prev].right;
1.779 - popRight(nodes[jd].prev);
1.780 - pushLeft(jd, ld);
1.781 - if (less(ld, nodes[jd].right)) {
1.782 - nodes[jd].item = nodes[ld].item;
1.783 - nodes[jd].prio = nodes[jd].prio;
1.784 - }
1.785 - if (nodes[nodes[jd].prev].item == nodes[ld].item) {
1.786 - setPrio(nodes[jd].prev);
1.787 - }
1.788 - jd = nodes[jd].right;
1.789 - }
1.790 - }
1.791 - } else {
1.792 - jd = nodes[jd].right;
1.793 - }
1.794 + int kd = nodes[jd].right;
1.795 + if (nodes[jd].size == 1) {
1.796 + if (nodes[jd].parent < 0) {
1.797 + classes[id].parent = ~kd;
1.798 + classes[id].depth -= 1;
1.799 + nodes[kd].parent = ~id;
1.800 + deleteNode(jd);
1.801 + jd = kd;
1.802 + } else {
1.803 + int pd = nodes[jd].parent;
1.804 + if (nodes[nodes[jd].prev].size < cmax) {
1.805 + pushRight(nodes[jd].prev, nodes[jd].right);
1.806 + if (less(nodes[jd].right, nodes[jd].prev)) {
1.807 + nodes[nodes[jd].prev].prio = nodes[nodes[jd].right].prio;
1.808 + nodes[nodes[jd].prev].item = nodes[nodes[jd].right].item;
1.809 + }
1.810 + popRight(pd);
1.811 + deleteNode(jd);
1.812 + jd = pd;
1.813 + } else {
1.814 + int ld = nodes[nodes[jd].prev].right;
1.815 + popRight(nodes[jd].prev);
1.816 + pushLeft(jd, ld);
1.817 + if (less(ld, nodes[jd].right)) {
1.818 + nodes[jd].item = nodes[ld].item;
1.819 + nodes[jd].prio = nodes[jd].prio;
1.820 + }
1.821 + if (nodes[nodes[jd].prev].item == nodes[ld].item) {
1.822 + setPrio(nodes[jd].prev);
1.823 + }
1.824 + jd = nodes[jd].right;
1.825 + }
1.826 + }
1.827 + } else {
1.828 + jd = nodes[jd].right;
1.829 + }
1.830 }
1.831 }
1.832
1.833 @@ -1276,12 +1276,12 @@
1.834
1.835 /// \brief Constructs the union-find.
1.836 ///
1.837 - /// Constructs the union-find.
1.838 + /// Constructs the union-find.
1.839 /// \brief _index The index map of the union-find. The data
1.840 /// structure uses internally for store references.
1.841 - HeapUnionFind(ItemIntMap& _index)
1.842 - : index(_index), first_class(-1),
1.843 - first_free_class(-1), first_free_node(-1) {}
1.844 + HeapUnionFind(ItemIntMap& _index)
1.845 + : index(_index), first_class(-1),
1.846 + first_free_class(-1), first_free_node(-1) {}
1.847
1.848 /// \brief Insert a new node into a new component.
1.849 ///
1.850 @@ -1303,14 +1303,14 @@
1.851
1.852 nodes[id].item = item;
1.853 index[item] = id;
1.854 -
1.855 +
1.856 int class_id = newClass();
1.857 classes[class_id].parent = ~id;
1.858 classes[class_id].depth = 0;
1.859
1.860 classes[class_id].left = -1;
1.861 classes[class_id].right = -1;
1.862 -
1.863 +
1.864 if (first_class != -1) {
1.865 classes[first_class].prev = class_id;
1.866 }
1.867 @@ -1319,7 +1319,7 @@
1.868 first_class = class_id;
1.869
1.870 nodes[id].parent = ~class_id;
1.871 -
1.872 +
1.873 return class_id;
1.874 }
1.875
1.876 @@ -1332,7 +1332,7 @@
1.877 int find(const Item& item) const {
1.878 return findClass(index[item]);
1.879 }
1.880 -
1.881 +
1.882 /// \brief Joins the classes.
1.883 ///
1.884 /// The current function joins the given classes. The parameter is
1.885 @@ -1371,13 +1371,13 @@
1.886 classes[classes[l].next].prev = classes[l].prev;
1.887 }
1.888 classes[classes[l].prev].next = classes[l].next;
1.889 -
1.890 +
1.891 classes[l].prev = -1;
1.892 classes[l].next = -1;
1.893
1.894 classes[l].depth = leftNode(l);
1.895 classes[l].parent = class_id;
1.896 -
1.897 +
1.898 }
1.899
1.900 { // merging of heap
1.901 @@ -1455,7 +1455,7 @@
1.902 push(new_parent, ~(classes[r].parent));
1.903 pushLeft(new_parent, ~(classes[l].parent));
1.904 setPrio(new_parent);
1.905 -
1.906 +
1.907 classes[r].parent = ~new_parent;
1.908 classes[r].depth += 1;
1.909 } else {
1.910 @@ -1470,15 +1470,15 @@
1.911 classes[l].parent = classes[r].parent;
1.912 classes[l].depth = classes[r].depth;
1.913 } else {
1.914 - if (classes[l].depth != 0 &&
1.915 - nodes[~(classes[l].parent)].size +
1.916 + if (classes[l].depth != 0 &&
1.917 + nodes[~(classes[l].parent)].size +
1.918 nodes[~(classes[r].parent)].size <= cmax) {
1.919 splice(~(classes[l].parent), ~(classes[r].parent));
1.920 deleteNode(~(classes[r].parent));
1.921 if (less(~(classes[r].parent), ~(classes[l].parent))) {
1.922 - nodes[~(classes[l].parent)].prio =
1.923 + nodes[~(classes[l].parent)].prio =
1.924 nodes[~(classes[r].parent)].prio;
1.925 - nodes[~(classes[l].parent)].item =
1.926 + nodes[~(classes[l].parent)].item =
1.927 nodes[~(classes[r].parent)].item;
1.928 }
1.929 } else {
1.930 @@ -1487,7 +1487,7 @@
1.931 push(new_parent, ~(classes[l].parent));
1.932 pushRight(new_parent, ~(classes[r].parent));
1.933 setPrio(new_parent);
1.934 -
1.935 +
1.936 classes[l].parent = ~new_parent;
1.937 classes[l].depth += 1;
1.938 nodes[new_parent].parent = ~l;
1.939 @@ -1542,12 +1542,12 @@
1.940 classes[classes[id].right].next = first_class;
1.941 classes[first_class].prev = classes[id].right;
1.942 first_class = classes[id].left;
1.943 -
1.944 +
1.945 if (classes[id].next != -1) {
1.946 classes[classes[id].next].prev = classes[id].prev;
1.947 }
1.948 classes[classes[id].prev].next = classes[id].next;
1.949 -
1.950 +
1.951 deleteClass(id);
1.952 }
1.953
1.954 @@ -1557,7 +1557,7 @@
1.955 while (nodes[nodes[l].parent].left == l) {
1.956 l = nodes[l].parent;
1.957 }
1.958 - int r = l;
1.959 + int r = l;
1.960 while (nodes[l].parent >= 0) {
1.961 l = nodes[l].parent;
1.962 int new_node = newNode();
1.963 @@ -1580,7 +1580,7 @@
1.964
1.965 repairRight(~(nodes[l].parent));
1.966 repairLeft(cs[i]);
1.967 -
1.968 +
1.969 *out++ = cs[i];
1.970 }
1.971 }
1.972 @@ -1603,7 +1603,7 @@
1.973 increase(item, prio);
1.974 }
1.975 }
1.976 -
1.977 +
1.978 /// \brief Increase the priority of the current item.
1.979 ///
1.980 /// Increase the priority of the current item.
1.981 @@ -1630,7 +1630,7 @@
1.982 kd = nodes[kd].parent;
1.983 }
1.984 }
1.985 -
1.986 +
1.987 /// \brief Gives back the minimum priority of the class.
1.988 ///
1.989 /// \return Gives back the minimum priority of the class.
1.990 @@ -1646,9 +1646,9 @@
1.991 }
1.992
1.993 /// \brief Gives back a representant item of the class.
1.994 - ///
1.995 + ///
1.996 /// The representant is indpendent from the priorities of the
1.997 - /// items.
1.998 + /// items.
1.999 /// \return Gives back a representant item of the class.
1.1000 const Item& classRep(int id) const {
1.1001 int parent = classes[id].parent;
1.1002 @@ -1674,12 +1674,12 @@
1.1003
1.1004 const HeapUnionFind* _huf;
1.1005 int _id, _lid;
1.1006 -
1.1007 +
1.1008 public:
1.1009
1.1010 - /// \brief Default constructor
1.1011 + /// \brief Default constructor
1.1012 ///
1.1013 - /// Default constructor
1.1014 + /// Default constructor
1.1015 ItemIt() {}
1.1016
1.1017 ItemIt(const HeapUnionFind& huf, int cls) : _huf(&huf) {
1.1018 @@ -1695,9 +1695,9 @@
1.1019 } else {
1.1020 _id = _huf->leftNode(id);
1.1021 _lid = -1;
1.1022 - }
1.1023 + }
1.1024 }
1.1025 -
1.1026 +
1.1027 /// \brief Increment operator
1.1028 ///
1.1029 /// It steps to the next item in the class.
1.1030 @@ -1712,40 +1712,40 @@
1.1031 operator const Item&() const {
1.1032 return _huf->nodes[_id].item;
1.1033 }
1.1034 -
1.1035 +
1.1036 /// \brief Equality operator
1.1037 ///
1.1038 /// Equality operator
1.1039 - bool operator==(const ItemIt& i) {
1.1040 + bool operator==(const ItemIt& i) {
1.1041 return i._id == _id;
1.1042 }
1.1043
1.1044 /// \brief Inequality operator
1.1045 ///
1.1046 /// Inequality operator
1.1047 - bool operator!=(const ItemIt& i) {
1.1048 + bool operator!=(const ItemIt& i) {
1.1049 return i._id != _id;
1.1050 }
1.1051
1.1052 /// \brief Equality operator
1.1053 ///
1.1054 /// Equality operator
1.1055 - bool operator==(Invalid) {
1.1056 + bool operator==(Invalid) {
1.1057 return _id == _lid;
1.1058 }
1.1059
1.1060 /// \brief Inequality operator
1.1061 ///
1.1062 /// Inequality operator
1.1063 - bool operator!=(Invalid) {
1.1064 + bool operator!=(Invalid) {
1.1065 return _id != _lid;
1.1066 }
1.1067 -
1.1068 +
1.1069 };
1.1070
1.1071 /// \brief Class iterator
1.1072 ///
1.1073 - /// The iterator stores
1.1074 + /// The iterator stores
1.1075 class ClassIt {
1.1076 private:
1.1077
1.1078 @@ -1754,37 +1754,37 @@
1.1079
1.1080 public:
1.1081
1.1082 - ClassIt(const HeapUnionFind& huf)
1.1083 + ClassIt(const HeapUnionFind& huf)
1.1084 : _huf(&huf), _id(huf.first_class) {}
1.1085
1.1086 - ClassIt(const HeapUnionFind& huf, int cls)
1.1087 + ClassIt(const HeapUnionFind& huf, int cls)
1.1088 : _huf(&huf), _id(huf.classes[cls].left) {}
1.1089
1.1090 ClassIt(Invalid) : _huf(0), _id(-1) {}
1.1091 -
1.1092 +
1.1093 const ClassIt& operator++() {
1.1094 _id = _huf->classes[_id].next;
1.1095 - return *this;
1.1096 + return *this;
1.1097 }
1.1098
1.1099 /// \brief Equality operator
1.1100 ///
1.1101 /// Equality operator
1.1102 - bool operator==(const ClassIt& i) {
1.1103 + bool operator==(const ClassIt& i) {
1.1104 return i._id == _id;
1.1105 }
1.1106
1.1107 /// \brief Inequality operator
1.1108 ///
1.1109 /// Inequality operator
1.1110 - bool operator!=(const ClassIt& i) {
1.1111 + bool operator!=(const ClassIt& i) {
1.1112 return i._id != _id;
1.1113 - }
1.1114 -
1.1115 + }
1.1116 +
1.1117 operator int() const {
1.1118 - return _id;
1.1119 + return _id;
1.1120 }
1.1121 -
1.1122 +
1.1123 };
1.1124
1.1125 };