Release series 1.0.x has reached its end of life.
1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
3 * This file is a part of LEMON, a generic C++ optimization library.
5 * Copyright (C) 2003-2011
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
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.
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
19 #ifndef LEMON_UNION_FIND_H
20 #define LEMON_UNION_FIND_H
24 //!\brief Union-Find data structures.
33 #include <lemon/core.h>
39 /// \brief A \e Union-Find data structure implementation
41 /// The class implements the \e Union-Find data structure.
42 /// The union operation uses rank heuristic, while
43 /// the find operation uses path compression.
44 /// This is a very simple but efficient implementation, providing
45 /// only four methods: join (union), find, insert and size.
46 /// For more features see the \ref UnionFindEnum class.
48 /// It is primarily used in Kruskal algorithm for finding minimal
49 /// cost spanning tree in a graph.
52 /// \pre You need to add all the elements by the \ref insert()
54 template <typename _ItemIntMap>
58 typedef _ItemIntMap ItemIntMap;
59 typedef typename ItemIntMap::Key Item;
62 // If the items vector stores negative value for an item then
63 // that item is root item and it has -items[it] component size.
64 // Else the items[it] contains the index of the parent.
65 std::vector<int> items;
68 bool rep(int idx) const {
69 return items[idx] < 0;
72 int repIndex(int idx) const {
78 int next = items[idx];
79 const_cast<int&>(items[idx]) = k;
87 /// \brief Constructor
89 /// Constructor of the UnionFind class. You should give an item to
90 /// integer map which will be used from the data structure. If you
91 /// modify directly this map that may cause segmentation fault,
92 /// invalid data structure, or infinite loop when you use again
94 UnionFind(ItemIntMap& m) : index(m) {}
96 /// \brief Returns the index of the element's component.
98 /// The method returns the index of the element's component.
99 /// This is an integer between zero and the number of inserted elements.
101 int find(const Item& a) {
102 return repIndex(index[a]);
105 /// \brief Clears the union-find data structure
107 /// Erase each item from the data structure.
112 /// \brief Inserts a new element into the structure.
114 /// This method inserts a new element into the data structure.
116 /// The method returns the index of the new component.
117 int insert(const Item& a) {
118 int n = items.size();
124 /// \brief Joining the components of element \e a and element \e b.
126 /// This is the \e union operation of the Union-Find structure.
127 /// Joins the component of element \e a and component of
128 /// element \e b. If \e a and \e b are in the same component then
129 /// it returns false otherwise it returns true.
130 bool join(const Item& a, const Item& b) {
131 int ka = repIndex(index[a]);
132 int kb = repIndex(index[b]);
137 if (items[ka] < items[kb]) {
138 items[ka] += items[kb];
141 items[kb] += items[ka];
147 /// \brief Returns the size of the component of element \e a.
149 /// Returns the size of the component of element \e a.
150 int size(const Item& a) {
151 int k = repIndex(index[a]);
159 /// \brief A \e Union-Find data structure implementation which
160 /// is able to enumerate the components.
162 /// The class implements a \e Union-Find data structure
163 /// which is able to enumerate the components and the items in
164 /// a component. If you don't need this feature then perhaps it's
165 /// better to use the \ref UnionFind class which is more efficient.
167 /// The union operation uses rank heuristic, while
168 /// the find operation uses path compression.
170 /// \pre You need to add all the elements by the \ref insert()
173 template <typename _ItemIntMap>
174 class UnionFindEnum {
177 typedef _ItemIntMap ItemIntMap;
178 typedef typename ItemIntMap::Key Item;
184 // If the parent stores negative value for an item then that item
185 // is root item and it has ~(items[it].parent) component id. Else
186 // the items[it].parent contains the index of the parent.
188 // The \c next and \c prev provides the double-linked
189 // cyclic list of one component's items.
197 std::vector<ItemT> items;
206 std::vector<ClassT> classes;
207 int firstClass, firstFreeClass;
210 if (firstFreeClass == -1) {
211 int cdx = classes.size();
212 classes.push_back(ClassT());
215 int cdx = firstFreeClass;
216 firstFreeClass = classes[firstFreeClass].next;
222 if (firstFreeItem == -1) {
223 int idx = items.size();
224 items.push_back(ItemT());
227 int idx = firstFreeItem;
228 firstFreeItem = items[firstFreeItem].next;
234 bool rep(int idx) const {
235 return items[idx].parent < 0;
238 int repIndex(int idx) const {
244 int next = items[idx].parent;
245 const_cast<int&>(items[idx].parent) = k;
251 int classIndex(int idx) const {
252 return ~(items[repIndex(idx)].parent);
255 void singletonItem(int idx) {
256 items[idx].next = idx;
257 items[idx].prev = idx;
260 void laceItem(int idx, int rdx) {
261 items[idx].prev = rdx;
262 items[idx].next = items[rdx].next;
263 items[items[rdx].next].prev = idx;
264 items[rdx].next = idx;
267 void unlaceItem(int idx) {
268 items[items[idx].prev].next = items[idx].next;
269 items[items[idx].next].prev = items[idx].prev;
271 items[idx].next = firstFreeItem;
275 void spliceItems(int ak, int bk) {
276 items[items[ak].prev].next = bk;
277 items[items[bk].prev].next = ak;
278 int tmp = items[ak].prev;
279 items[ak].prev = items[bk].prev;
280 items[bk].prev = tmp;
284 void laceClass(int cls) {
285 if (firstClass != -1) {
286 classes[firstClass].prev = cls;
288 classes[cls].next = firstClass;
289 classes[cls].prev = -1;
293 void unlaceClass(int cls) {
294 if (classes[cls].prev != -1) {
295 classes[classes[cls].prev].next = classes[cls].next;
297 firstClass = classes[cls].next;
299 if (classes[cls].next != -1) {
300 classes[classes[cls].next].prev = classes[cls].prev;
303 classes[cls].next = firstFreeClass;
304 firstFreeClass = cls;
309 UnionFindEnum(ItemIntMap& _index)
310 : index(_index), items(), firstFreeItem(-1),
311 firstClass(-1), firstFreeClass(-1) {}
313 /// \brief Inserts the given element into a new component.
315 /// This method creates a new component consisting only of the
318 int insert(const Item& item) {
321 index.set(item, idx);
324 items[idx].item = item;
326 int cdx = newClass();
328 items[idx].parent = ~cdx;
331 classes[cdx].size = 1;
332 classes[cdx].firstItem = idx;
339 /// \brief Inserts the given element into the component of the others.
341 /// This methods inserts the element \e a into the component of the
343 void insert(const Item& item, int cls) {
344 int rdx = classes[cls].firstItem;
347 index.set(item, idx);
351 items[idx].item = item;
352 items[idx].parent = rdx;
354 ++classes[~(items[rdx].parent)].size;
357 /// \brief Clears the union-find data structure
359 /// Erase each item from the data structure.
366 /// \brief Finds the component of the given element.
368 /// The method returns the component id of the given element.
369 int find(const Item &item) const {
370 return ~(items[repIndex(index[item])].parent);
373 /// \brief Joining the component of element \e a and element \e b.
375 /// This is the \e union operation of the Union-Find structure.
376 /// Joins the component of element \e a and component of
377 /// element \e b. If \e a and \e b are in the same component then
378 /// returns -1 else returns the remaining class.
379 int join(const Item& a, const Item& b) {
381 int ak = repIndex(index[a]);
382 int bk = repIndex(index[b]);
388 int acx = ~(items[ak].parent);
389 int bcx = ~(items[bk].parent);
393 if (classes[acx].size > classes[bcx].size) {
394 classes[acx].size += classes[bcx].size;
395 items[bk].parent = ak;
399 classes[bcx].size += classes[acx].size;
400 items[ak].parent = bk;
409 /// \brief Returns the size of the class.
411 /// Returns the size of the class.
412 int size(int cls) const {
413 return classes[cls].size;
416 /// \brief Splits up the component.
418 /// Splitting the component into singleton components (component
420 void split(int cls) {
421 int fdx = classes[cls].firstItem;
422 int idx = items[fdx].next;
424 int next = items[idx].next;
428 int cdx = newClass();
429 items[idx].parent = ~cdx;
432 classes[cdx].size = 1;
433 classes[cdx].firstItem = idx;
438 items[idx].prev = idx;
439 items[idx].next = idx;
441 classes[~(items[idx].parent)].size = 1;
445 /// \brief Removes the given element from the structure.
447 /// Removes the element from its component and if the component becomes
448 /// empty then removes that component from the component list.
450 /// \warning It is an error to remove an element which is not in
452 /// \warning This running time of this operation is proportional to the
453 /// number of the items in this class.
454 void erase(const Item& item) {
455 int idx = index[item];
456 int fdx = items[idx].next;
458 int cdx = classIndex(idx);
461 items[idx].next = firstFreeItem;
465 classes[cdx].firstItem = fdx;
467 items[fdx].parent = ~cdx;
470 idx = items[fdx].next;
472 items[idx].parent = fdx;
473 idx = items[idx].next;
480 /// \brief Gives back a representant item of the component.
482 /// Gives back a representant item of the component.
483 Item item(int cls) const {
484 return items[classes[cls].firstItem].item;
487 /// \brief Removes the component of the given element from the structure.
489 /// Removes the component of the given element from the structure.
491 /// \warning It is an error to give an element which is not in the
493 void eraseClass(int cls) {
494 int fdx = classes[cls].firstItem;
496 items[items[fdx].prev].next = firstFreeItem;
500 /// \brief LEMON style iterator for the representant items.
502 /// ClassIt is a lemon style iterator for the components. It iterates
503 /// on the ids of the classes.
506 /// \brief Constructor of the iterator
508 /// Constructor of the iterator
509 ClassIt(const UnionFindEnum& ufe) : unionFind(&ufe) {
510 cdx = unionFind->firstClass;
513 /// \brief Constructor to get invalid iterator
515 /// Constructor to get invalid iterator
516 ClassIt(Invalid) : unionFind(0), cdx(-1) {}
518 /// \brief Increment operator
520 /// It steps to the next representant item.
521 ClassIt& operator++() {
522 cdx = unionFind->classes[cdx].next;
526 /// \brief Conversion operator
528 /// It converts the iterator to the current representant item.
529 operator int() const {
533 /// \brief Equality operator
535 /// Equality operator
536 bool operator==(const ClassIt& i) {
540 /// \brief Inequality operator
542 /// Inequality operator
543 bool operator!=(const ClassIt& i) {
548 const UnionFindEnum* unionFind;
552 /// \brief LEMON style iterator for the items of a component.
554 /// ClassIt is a lemon style iterator for the components. It iterates
555 /// on the items of a class. By example if you want to iterate on
556 /// each items of each classes then you may write the next code.
558 /// for (ClassIt cit(ufe); cit != INVALID; ++cit) {
559 /// std::cout << "Class: ";
560 /// for (ItemIt iit(ufe, cit); iit != INVALID; ++iit) {
561 /// std::cout << toString(iit) << ' ' << std::endl;
563 /// std::cout << std::endl;
568 /// \brief Constructor of the iterator
570 /// Constructor of the iterator. The iterator iterates
571 /// on the class of the \c item.
572 ItemIt(const UnionFindEnum& ufe, int cls) : unionFind(&ufe) {
573 fdx = idx = unionFind->classes[cls].firstItem;
576 /// \brief Constructor to get invalid iterator
578 /// Constructor to get invalid iterator
579 ItemIt(Invalid) : unionFind(0), idx(-1) {}
581 /// \brief Increment operator
583 /// It steps to the next item in the class.
584 ItemIt& operator++() {
585 idx = unionFind->items[idx].next;
586 if (idx == fdx) idx = -1;
590 /// \brief Conversion operator
592 /// It converts the iterator to the current item.
593 operator const Item&() const {
594 return unionFind->items[idx].item;
597 /// \brief Equality operator
599 /// Equality operator
600 bool operator==(const ItemIt& i) {
604 /// \brief Inequality operator
606 /// Inequality operator
607 bool operator!=(const ItemIt& i) {
612 const UnionFindEnum* unionFind;
620 /// \brief A \e Extend-Find data structure implementation which
621 /// is able to enumerate the components.
623 /// The class implements an \e Extend-Find data structure which is
624 /// able to enumerate the components and the items in a
625 /// component. The data structure is a simplification of the
626 /// Union-Find structure, and it does not allow to merge two components.
628 /// \pre You need to add all the elements by the \ref insert()
630 template <typename _ItemIntMap>
631 class ExtendFindEnum {
634 typedef _ItemIntMap ItemIntMap;
635 typedef typename ItemIntMap::Key Item;
647 std::vector<ItemT> items;
655 std::vector<ClassT> classes;
657 int firstClass, firstFreeClass;
660 if (firstFreeClass != -1) {
661 int cdx = firstFreeClass;
662 firstFreeClass = classes[cdx].next;
665 classes.push_back(ClassT());
666 return classes.size() - 1;
671 if (firstFreeItem != -1) {
672 int idx = firstFreeItem;
673 firstFreeItem = items[idx].next;
676 items.push_back(ItemT());
677 return items.size() - 1;
683 /// \brief Constructor
684 ExtendFindEnum(ItemIntMap& _index)
685 : index(_index), items(), firstFreeItem(-1),
686 classes(), firstClass(-1), firstFreeClass(-1) {}
688 /// \brief Inserts the given element into a new component.
690 /// This method creates a new component consisting only of the
692 int insert(const Item& item) {
693 int cdx = newClass();
694 classes[cdx].prev = -1;
695 classes[cdx].next = firstClass;
696 if (firstClass != -1) {
697 classes[firstClass].prev = cdx;
702 items[idx].item = item;
703 items[idx].cls = cdx;
704 items[idx].prev = idx;
705 items[idx].next = idx;
707 classes[cdx].firstItem = idx;
709 index.set(item, idx);
714 /// \brief Inserts the given element into the given component.
716 /// This methods inserts the element \e item a into the \e cls class.
717 void insert(const Item& item, int cls) {
719 int rdx = classes[cls].firstItem;
720 items[idx].item = item;
721 items[idx].cls = cls;
723 items[idx].prev = rdx;
724 items[idx].next = items[rdx].next;
725 items[items[rdx].next].prev = idx;
726 items[rdx].next = idx;
728 index.set(item, idx);
731 /// \brief Clears the union-find data structure
733 /// Erase each item from the data structure.
737 firstClass = firstFreeClass = firstFreeItem = -1;
740 /// \brief Gives back the class of the \e item.
742 /// Gives back the class of the \e item.
743 int find(const Item &item) const {
744 return items[index[item]].cls;
747 /// \brief Gives back a representant item of the component.
749 /// Gives back a representant item of the component.
750 Item item(int cls) const {
751 return items[classes[cls].firstItem].item;
754 /// \brief Removes the given element from the structure.
756 /// Removes the element from its component and if the component becomes
757 /// empty then removes that component from the component list.
759 /// \warning It is an error to remove an element which is not in
761 void erase(const Item &item) {
762 int idx = index[item];
763 int cdx = items[idx].cls;
765 if (idx == items[idx].next) {
766 if (classes[cdx].prev != -1) {
767 classes[classes[cdx].prev].next = classes[cdx].next;
769 firstClass = classes[cdx].next;
771 if (classes[cdx].next != -1) {
772 classes[classes[cdx].next].prev = classes[cdx].prev;
774 classes[cdx].next = firstFreeClass;
775 firstFreeClass = cdx;
777 classes[cdx].firstItem = items[idx].next;
778 items[items[idx].next].prev = items[idx].prev;
779 items[items[idx].prev].next = items[idx].next;
781 items[idx].next = firstFreeItem;
787 /// \brief Removes the component of the given element from the structure.
789 /// Removes the component of the given element from the structure.
791 /// \warning It is an error to give an element which is not in the
793 void eraseClass(int cdx) {
794 int idx = classes[cdx].firstItem;
795 items[items[idx].prev].next = firstFreeItem;
798 if (classes[cdx].prev != -1) {
799 classes[classes[cdx].prev].next = classes[cdx].next;
801 firstClass = classes[cdx].next;
803 if (classes[cdx].next != -1) {
804 classes[classes[cdx].next].prev = classes[cdx].prev;
806 classes[cdx].next = firstFreeClass;
807 firstFreeClass = cdx;
810 /// \brief LEMON style iterator for the classes.
812 /// ClassIt is a lemon style iterator for the components. It iterates
813 /// on the ids of classes.
816 /// \brief Constructor of the iterator
818 /// Constructor of the iterator
819 ClassIt(const ExtendFindEnum& ufe) : extendFind(&ufe) {
820 cdx = extendFind->firstClass;
823 /// \brief Constructor to get invalid iterator
825 /// Constructor to get invalid iterator
826 ClassIt(Invalid) : extendFind(0), cdx(-1) {}
828 /// \brief Increment operator
830 /// It steps to the next representant item.
831 ClassIt& operator++() {
832 cdx = extendFind->classes[cdx].next;
836 /// \brief Conversion operator
838 /// It converts the iterator to the current class id.
839 operator int() const {
843 /// \brief Equality operator
845 /// Equality operator
846 bool operator==(const ClassIt& i) {
850 /// \brief Inequality operator
852 /// Inequality operator
853 bool operator!=(const ClassIt& i) {
858 const ExtendFindEnum* extendFind;
862 /// \brief LEMON style iterator for the items of a component.
864 /// ClassIt is a lemon style iterator for the components. It iterates
865 /// on the items of a class. By example if you want to iterate on
866 /// each items of each classes then you may write the next code.
868 /// for (ClassIt cit(ufe); cit != INVALID; ++cit) {
869 /// std::cout << "Class: ";
870 /// for (ItemIt iit(ufe, cit); iit != INVALID; ++iit) {
871 /// std::cout << toString(iit) << ' ' << std::endl;
873 /// std::cout << std::endl;
878 /// \brief Constructor of the iterator
880 /// Constructor of the iterator. The iterator iterates
881 /// on the class of the \c item.
882 ItemIt(const ExtendFindEnum& ufe, int cls) : extendFind(&ufe) {
883 fdx = idx = extendFind->classes[cls].firstItem;
886 /// \brief Constructor to get invalid iterator
888 /// Constructor to get invalid iterator
889 ItemIt(Invalid) : extendFind(0), idx(-1) {}
891 /// \brief Increment operator
893 /// It steps to the next item in the class.
894 ItemIt& operator++() {
895 idx = extendFind->items[idx].next;
896 if (fdx == idx) idx = -1;
900 /// \brief Conversion operator
902 /// It converts the iterator to the current item.
903 operator const Item&() const {
904 return extendFind->items[idx].item;
907 /// \brief Equality operator
909 /// Equality operator
910 bool operator==(const ItemIt& i) {
914 /// \brief Inequality operator
916 /// Inequality operator
917 bool operator!=(const ItemIt& i) {
922 const ExtendFindEnum* extendFind;
930 /// \brief A \e Union-Find data structure implementation which
931 /// is able to store a priority for each item and retrieve the minimum of
934 /// A \e Union-Find data structure implementation which is able to
935 /// store a priority for each item and retrieve the minimum of each
936 /// class. In addition, it supports the joining and splitting the
937 /// components. If you don't need this feature then you makes
938 /// better to use the \ref UnionFind class which is more efficient.
940 /// The union-find data strcuture based on a (2, 16)-tree with a
941 /// tournament minimum selection on the internal nodes. The insert
942 /// operation takes O(1), the find, set, decrease and increase takes
943 /// O(log(n)), where n is the number of nodes in the current
944 /// component. The complexity of join and split is O(log(n)*k),
945 /// where n is the sum of the number of the nodes and k is the
946 /// number of joined components or the number of the components
949 /// \pre You need to add all the elements by the \ref insert()
952 template <typename _Value, typename _ItemIntMap,
953 typename _Comp = std::less<_Value> >
954 class HeapUnionFind {
957 typedef _Value Value;
958 typedef typename _ItemIntMap::Key Item;
960 typedef _ItemIntMap ItemIntMap;
966 static const int cmax = 16;
979 int first_free_class;
980 std::vector<ClassNode> classes;
983 if (first_free_class < 0) {
984 int id = classes.size();
985 classes.push_back(ClassNode());
988 int id = first_free_class;
989 first_free_class = classes[id].next;
994 void deleteClass(int id) {
995 classes[id].next = first_free_class;
996 first_free_class = id;
1008 int first_free_node;
1009 std::vector<ItemNode> nodes;
1012 if (first_free_node < 0) {
1013 int id = nodes.size();
1014 nodes.push_back(ItemNode());
1017 int id = first_free_node;
1018 first_free_node = nodes[id].next;
1023 void deleteNode(int id) {
1024 nodes[id].next = first_free_node;
1025 first_free_node = id;
1030 int findClass(int id) const {
1033 kd = nodes[kd].parent;
1038 int leftNode(int id) const {
1039 int kd = ~(classes[id].parent);
1040 for (int i = 0; i < classes[id].depth; ++i) {
1041 kd = nodes[kd].left;
1046 int nextNode(int id) const {
1048 while (id >= 0 && nodes[id].next == -1) {
1049 id = nodes[id].parent;
1055 id = nodes[id].next;
1057 id = nodes[id].left;
1063 void setPrio(int id) {
1064 int jd = nodes[id].left;
1065 nodes[id].prio = nodes[jd].prio;
1066 nodes[id].item = nodes[jd].item;
1067 jd = nodes[jd].next;
1069 if (comp(nodes[jd].prio, nodes[id].prio)) {
1070 nodes[id].prio = nodes[jd].prio;
1071 nodes[id].item = nodes[jd].item;
1073 jd = nodes[jd].next;
1077 void push(int id, int jd) {
1079 nodes[id].left = nodes[id].right = jd;
1080 nodes[jd].next = nodes[jd].prev = -1;
1081 nodes[jd].parent = id;
1084 void pushAfter(int id, int jd) {
1085 int kd = nodes[id].parent;
1086 if (nodes[id].next != -1) {
1087 nodes[nodes[id].next].prev = jd;
1089 nodes[kd].size += 1;
1093 nodes[kd].right = jd;
1094 nodes[kd].size += 1;
1097 nodes[jd].next = nodes[id].next;
1098 nodes[jd].prev = id;
1099 nodes[id].next = jd;
1100 nodes[jd].parent = kd;
1103 void pushRight(int id, int jd) {
1104 nodes[id].size += 1;
1105 nodes[jd].prev = nodes[id].right;
1106 nodes[jd].next = -1;
1107 nodes[nodes[id].right].next = jd;
1108 nodes[id].right = jd;
1109 nodes[jd].parent = id;
1112 void popRight(int id) {
1113 nodes[id].size -= 1;
1114 int jd = nodes[id].right;
1115 nodes[nodes[jd].prev].next = -1;
1116 nodes[id].right = nodes[jd].prev;
1119 void splice(int id, int jd) {
1120 nodes[id].size += nodes[jd].size;
1121 nodes[nodes[id].right].next = nodes[jd].left;
1122 nodes[nodes[jd].left].prev = nodes[id].right;
1123 int kd = nodes[jd].left;
1125 nodes[kd].parent = id;
1126 kd = nodes[kd].next;
1128 nodes[id].right = nodes[jd].right;
1131 void split(int id, int jd) {
1132 int kd = nodes[id].parent;
1133 nodes[kd].right = nodes[id].prev;
1134 nodes[nodes[id].prev].next = -1;
1136 nodes[jd].left = id;
1137 nodes[id].prev = -1;
1140 nodes[id].parent = jd;
1141 nodes[jd].right = id;
1142 id = nodes[id].next;
1145 nodes[kd].size -= num;
1146 nodes[jd].size = num;
1149 void pushLeft(int id, int jd) {
1150 nodes[id].size += 1;
1151 nodes[jd].next = nodes[id].left;
1152 nodes[jd].prev = -1;
1153 nodes[nodes[id].left].prev = jd;
1154 nodes[id].left = jd;
1155 nodes[jd].parent = id;
1158 void popLeft(int id) {
1159 nodes[id].size -= 1;
1160 int jd = nodes[id].left;
1161 nodes[nodes[jd].next].prev = -1;
1162 nodes[id].left = nodes[jd].next;
1165 void repairLeft(int id) {
1166 int jd = ~(classes[id].parent);
1167 while (nodes[jd].left != -1) {
1168 int kd = nodes[jd].left;
1169 if (nodes[jd].size == 1) {
1170 if (nodes[jd].parent < 0) {
1171 classes[id].parent = ~kd;
1172 classes[id].depth -= 1;
1173 nodes[kd].parent = ~id;
1177 int pd = nodes[jd].parent;
1178 if (nodes[nodes[jd].next].size < cmax) {
1179 pushLeft(nodes[jd].next, nodes[jd].left);
1180 if (less(jd, nodes[jd].next) ||
1181 nodes[jd].item == nodes[pd].item) {
1182 nodes[nodes[jd].next].prio = nodes[jd].prio;
1183 nodes[nodes[jd].next].item = nodes[jd].item;
1189 int ld = nodes[nodes[jd].next].left;
1190 popLeft(nodes[jd].next);
1192 if (less(ld, nodes[jd].left) ||
1193 nodes[ld].item == nodes[pd].item) {
1194 nodes[jd].item = nodes[ld].item;
1195 nodes[jd].prio = nodes[ld].prio;
1197 if (nodes[nodes[jd].next].item == nodes[ld].item) {
1198 setPrio(nodes[jd].next);
1200 jd = nodes[jd].left;
1204 jd = nodes[jd].left;
1209 void repairRight(int id) {
1210 int jd = ~(classes[id].parent);
1211 while (nodes[jd].right != -1) {
1212 int kd = nodes[jd].right;
1213 if (nodes[jd].size == 1) {
1214 if (nodes[jd].parent < 0) {
1215 classes[id].parent = ~kd;
1216 classes[id].depth -= 1;
1217 nodes[kd].parent = ~id;
1221 int pd = nodes[jd].parent;
1222 if (nodes[nodes[jd].prev].size < cmax) {
1223 pushRight(nodes[jd].prev, nodes[jd].right);
1224 if (less(jd, nodes[jd].prev) ||
1225 nodes[jd].item == nodes[pd].item) {
1226 nodes[nodes[jd].prev].prio = nodes[jd].prio;
1227 nodes[nodes[jd].prev].item = nodes[jd].item;
1233 int ld = nodes[nodes[jd].prev].right;
1234 popRight(nodes[jd].prev);
1236 if (less(ld, nodes[jd].right) ||
1237 nodes[ld].item == nodes[pd].item) {
1238 nodes[jd].item = nodes[ld].item;
1239 nodes[jd].prio = nodes[ld].prio;
1241 if (nodes[nodes[jd].prev].item == nodes[ld].item) {
1242 setPrio(nodes[jd].prev);
1244 jd = nodes[jd].right;
1248 jd = nodes[jd].right;
1254 bool less(int id, int jd) const {
1255 return comp(nodes[id].prio, nodes[jd].prio);
1260 /// \brief Returns true when the given class is alive.
1262 /// Returns true when the given class is alive, ie. the class is
1263 /// not nested into other class.
1264 bool alive(int cls) const {
1265 return classes[cls].parent < 0;
1268 /// \brief Returns true when the given class is trivial.
1270 /// Returns true when the given class is trivial, ie. the class
1271 /// contains just one item directly.
1272 bool trivial(int cls) const {
1273 return classes[cls].left == -1;
1276 /// \brief Constructs the union-find.
1278 /// Constructs the union-find.
1279 /// \brief _index The index map of the union-find. The data
1280 /// structure uses internally for store references.
1281 HeapUnionFind(ItemIntMap& _index)
1282 : index(_index), first_class(-1),
1283 first_free_class(-1), first_free_node(-1) {}
1285 /// \brief Insert a new node into a new component.
1287 /// Insert a new node into a new component.
1288 /// \param item The item of the new node.
1289 /// \param prio The priority of the new node.
1290 /// \return The class id of the one-item-heap.
1291 int insert(const Item& item, const Value& prio) {
1293 nodes[id].item = item;
1294 nodes[id].prio = prio;
1297 nodes[id].prev = -1;
1298 nodes[id].next = -1;
1300 nodes[id].left = -1;
1301 nodes[id].right = -1;
1303 nodes[id].item = item;
1306 int class_id = newClass();
1307 classes[class_id].parent = ~id;
1308 classes[class_id].depth = 0;
1310 classes[class_id].left = -1;
1311 classes[class_id].right = -1;
1313 if (first_class != -1) {
1314 classes[first_class].prev = class_id;
1316 classes[class_id].next = first_class;
1317 classes[class_id].prev = -1;
1318 first_class = class_id;
1320 nodes[id].parent = ~class_id;
1325 /// \brief The class of the item.
1327 /// \return The alive class id of the item, which is not nested into
1330 /// The time complexity is O(log(n)).
1331 int find(const Item& item) const {
1332 return findClass(index[item]);
1335 /// \brief Joins the classes.
1337 /// The current function joins the given classes. The parameter is
1338 /// an STL range which should be contains valid class ids. The
1339 /// time complexity is O(log(n)*k) where n is the overall number
1340 /// of the joined nodes and k is the number of classes.
1341 /// \return The class of the joined classes.
1342 /// \pre The range should contain at least two class ids.
1343 template <typename Iterator>
1344 int join(Iterator begin, Iterator end) {
1345 std::vector<int> cs;
1346 for (Iterator it = begin; it != end; ++it) {
1350 int class_id = newClass();
1351 { // creation union-find
1353 if (first_class != -1) {
1354 classes[first_class].prev = class_id;
1356 classes[class_id].next = first_class;
1357 classes[class_id].prev = -1;
1358 first_class = class_id;
1360 classes[class_id].depth = classes[cs[0]].depth;
1361 classes[class_id].parent = classes[cs[0]].parent;
1362 nodes[~(classes[class_id].parent)].parent = ~class_id;
1366 classes[class_id].left = l;
1367 classes[class_id].right = l;
1369 if (classes[l].next != -1) {
1370 classes[classes[l].next].prev = classes[l].prev;
1372 classes[classes[l].prev].next = classes[l].next;
1374 classes[l].prev = -1;
1375 classes[l].next = -1;
1377 classes[l].depth = leftNode(l);
1378 classes[l].parent = class_id;
1382 { // merging of heap
1384 for (int ci = 1; ci < int(cs.size()); ++ci) {
1386 int rln = leftNode(r);
1387 if (classes[l].depth > classes[r].depth) {
1388 int id = ~(classes[l].parent);
1389 for (int i = classes[r].depth + 1; i < classes[l].depth; ++i) {
1390 id = nodes[id].right;
1392 while (id >= 0 && nodes[id].size == cmax) {
1393 int new_id = newNode();
1394 int right_id = nodes[id].right;
1397 if (nodes[id].item == nodes[right_id].item) {
1400 push(new_id, right_id);
1401 pushRight(new_id, ~(classes[r].parent));
1403 if (less(~classes[r].parent, right_id)) {
1404 nodes[new_id].item = nodes[~classes[r].parent].item;
1405 nodes[new_id].prio = nodes[~classes[r].parent].prio;
1407 nodes[new_id].item = nodes[right_id].item;
1408 nodes[new_id].prio = nodes[right_id].prio;
1411 id = nodes[id].parent;
1412 classes[r].parent = ~new_id;
1415 int new_parent = newNode();
1416 nodes[new_parent].next = -1;
1417 nodes[new_parent].prev = -1;
1418 nodes[new_parent].parent = ~l;
1420 push(new_parent, ~(classes[l].parent));
1421 pushRight(new_parent, ~(classes[r].parent));
1422 setPrio(new_parent);
1424 classes[l].parent = ~new_parent;
1425 classes[l].depth += 1;
1427 pushRight(id, ~(classes[r].parent));
1428 while (id >= 0 && less(~(classes[r].parent), id)) {
1429 nodes[id].prio = nodes[~(classes[r].parent)].prio;
1430 nodes[id].item = nodes[~(classes[r].parent)].item;
1431 id = nodes[id].parent;
1434 } else if (classes[r].depth > classes[l].depth) {
1435 int id = ~(classes[r].parent);
1436 for (int i = classes[l].depth + 1; i < classes[r].depth; ++i) {
1437 id = nodes[id].left;
1439 while (id >= 0 && nodes[id].size == cmax) {
1440 int new_id = newNode();
1441 int left_id = nodes[id].left;
1444 if (nodes[id].prio == nodes[left_id].prio) {
1447 push(new_id, left_id);
1448 pushLeft(new_id, ~(classes[l].parent));
1450 if (less(~classes[l].parent, left_id)) {
1451 nodes[new_id].item = nodes[~classes[l].parent].item;
1452 nodes[new_id].prio = nodes[~classes[l].parent].prio;
1454 nodes[new_id].item = nodes[left_id].item;
1455 nodes[new_id].prio = nodes[left_id].prio;
1458 id = nodes[id].parent;
1459 classes[l].parent = ~new_id;
1463 int new_parent = newNode();
1464 nodes[new_parent].next = -1;
1465 nodes[new_parent].prev = -1;
1466 nodes[new_parent].parent = ~l;
1468 push(new_parent, ~(classes[r].parent));
1469 pushLeft(new_parent, ~(classes[l].parent));
1470 setPrio(new_parent);
1472 classes[r].parent = ~new_parent;
1473 classes[r].depth += 1;
1475 pushLeft(id, ~(classes[l].parent));
1476 while (id >= 0 && less(~(classes[l].parent), id)) {
1477 nodes[id].prio = nodes[~(classes[l].parent)].prio;
1478 nodes[id].item = nodes[~(classes[l].parent)].item;
1479 id = nodes[id].parent;
1482 nodes[~(classes[r].parent)].parent = ~l;
1483 classes[l].parent = classes[r].parent;
1484 classes[l].depth = classes[r].depth;
1486 if (classes[l].depth != 0 &&
1487 nodes[~(classes[l].parent)].size +
1488 nodes[~(classes[r].parent)].size <= cmax) {
1489 splice(~(classes[l].parent), ~(classes[r].parent));
1490 deleteNode(~(classes[r].parent));
1491 if (less(~(classes[r].parent), ~(classes[l].parent))) {
1492 nodes[~(classes[l].parent)].prio =
1493 nodes[~(classes[r].parent)].prio;
1494 nodes[~(classes[l].parent)].item =
1495 nodes[~(classes[r].parent)].item;
1498 int new_parent = newNode();
1499 nodes[new_parent].next = nodes[new_parent].prev = -1;
1500 push(new_parent, ~(classes[l].parent));
1501 pushRight(new_parent, ~(classes[r].parent));
1502 setPrio(new_parent);
1504 classes[l].parent = ~new_parent;
1505 classes[l].depth += 1;
1506 nodes[new_parent].parent = ~l;
1509 if (classes[r].next != -1) {
1510 classes[classes[r].next].prev = classes[r].prev;
1512 classes[classes[r].prev].next = classes[r].next;
1514 classes[r].prev = classes[l].right;
1515 classes[classes[l].right].next = r;
1516 classes[l].right = r;
1517 classes[r].parent = l;
1519 classes[r].next = -1;
1520 classes[r].depth = rln;
1526 /// \brief Split the class to subclasses.
1528 /// The current function splits the given class. The join, which
1529 /// made the current class, stored a reference to the
1530 /// subclasses. The \c splitClass() member restores the classes
1531 /// and creates the heaps. The parameter is an STL output iterator
1532 /// which will be filled with the subclass ids. The time
1533 /// complexity is O(log(n)*k) where n is the overall number of
1534 /// nodes in the splitted classes and k is the number of the
1536 template <typename Iterator>
1537 void split(int cls, Iterator out) {
1538 std::vector<int> cs;
1539 { // splitting union-find
1541 int l = classes[id].left;
1543 classes[l].parent = classes[id].parent;
1544 classes[l].depth = classes[id].depth;
1546 nodes[~(classes[l].parent)].parent = ~l;
1552 l = classes[l].next;
1555 classes[classes[id].right].next = first_class;
1556 classes[first_class].prev = classes[id].right;
1557 first_class = classes[id].left;
1559 if (classes[id].next != -1) {
1560 classes[classes[id].next].prev = classes[id].prev;
1562 classes[classes[id].prev].next = classes[id].next;
1568 for (int i = 1; i < int(cs.size()); ++i) {
1569 int l = classes[cs[i]].depth;
1570 while (nodes[nodes[l].parent].left == l) {
1571 l = nodes[l].parent;
1574 while (nodes[l].parent >= 0) {
1575 l = nodes[l].parent;
1576 int new_node = newNode();
1578 nodes[new_node].prev = -1;
1579 nodes[new_node].next = -1;
1582 pushAfter(l, new_node);
1587 classes[cs[i]].parent = ~r;
1588 classes[cs[i]].depth = classes[~(nodes[l].parent)].depth;
1589 nodes[r].parent = ~cs[i];
1594 repairRight(~(nodes[l].parent));
1602 /// \brief Gives back the priority of the current item.
1604 /// \return Gives back the priority of the current item.
1605 const Value& operator[](const Item& item) const {
1606 return nodes[index[item]].prio;
1609 /// \brief Sets the priority of the current item.
1611 /// Sets the priority of the current item.
1612 void set(const Item& item, const Value& prio) {
1613 if (comp(prio, nodes[index[item]].prio)) {
1614 decrease(item, prio);
1615 } else if (!comp(prio, nodes[index[item]].prio)) {
1616 increase(item, prio);
1620 /// \brief Increase the priority of the current item.
1622 /// Increase the priority of the current item.
1623 void increase(const Item& item, const Value& prio) {
1624 int id = index[item];
1625 int kd = nodes[id].parent;
1626 nodes[id].prio = prio;
1627 while (kd >= 0 && nodes[kd].item == item) {
1629 kd = nodes[kd].parent;
1633 /// \brief Increase the priority of the current item.
1635 /// Increase the priority of the current item.
1636 void decrease(const Item& item, const Value& prio) {
1637 int id = index[item];
1638 int kd = nodes[id].parent;
1639 nodes[id].prio = prio;
1640 while (kd >= 0 && less(id, kd)) {
1641 nodes[kd].prio = prio;
1642 nodes[kd].item = item;
1643 kd = nodes[kd].parent;
1647 /// \brief Gives back the minimum priority of the class.
1649 /// \return Gives back the minimum priority of the class.
1650 const Value& classPrio(int cls) const {
1651 return nodes[~(classes[cls].parent)].prio;
1654 /// \brief Gives back the minimum priority item of the class.
1656 /// \return Gives back the minimum priority item of the class.
1657 const Item& classTop(int cls) const {
1658 return nodes[~(classes[cls].parent)].item;
1661 /// \brief Gives back a representant item of the class.
1663 /// The representant is indpendent from the priorities of the
1665 /// \return Gives back a representant item of the class.
1666 const Item& classRep(int id) const {
1667 int parent = classes[id].parent;
1668 return nodes[parent >= 0 ? classes[id].depth : leftNode(id)].item;
1671 /// \brief LEMON style iterator for the items of a class.
1673 /// ClassIt is a lemon style iterator for the components. It iterates
1674 /// on the items of a class. By example if you want to iterate on
1675 /// each items of each classes then you may write the next code.
1677 /// for (ClassIt cit(huf); cit != INVALID; ++cit) {
1678 /// std::cout << "Class: ";
1679 /// for (ItemIt iit(huf, cit); iit != INVALID; ++iit) {
1680 /// std::cout << toString(iit) << ' ' << std::endl;
1682 /// std::cout << std::endl;
1688 const HeapUnionFind* _huf;
1693 /// \brief Default constructor
1695 /// Default constructor
1698 ItemIt(const HeapUnionFind& huf, int cls) : _huf(&huf) {
1700 int parent = _huf->classes[id].parent;
1702 _id = _huf->classes[id].depth;
1703 if (_huf->classes[id].next != -1) {
1704 _lid = _huf->classes[_huf->classes[id].next].depth;
1709 _id = _huf->leftNode(id);
1714 /// \brief Increment operator
1716 /// It steps to the next item in the class.
1717 ItemIt& operator++() {
1718 _id = _huf->nextNode(_id);
1722 /// \brief Conversion operator
1724 /// It converts the iterator to the current item.
1725 operator const Item&() const {
1726 return _huf->nodes[_id].item;
1729 /// \brief Equality operator
1731 /// Equality operator
1732 bool operator==(const ItemIt& i) {
1733 return i._id == _id;
1736 /// \brief Inequality operator
1738 /// Inequality operator
1739 bool operator!=(const ItemIt& i) {
1740 return i._id != _id;
1743 /// \brief Equality operator
1745 /// Equality operator
1746 bool operator==(Invalid) {
1750 /// \brief Inequality operator
1752 /// Inequality operator
1753 bool operator!=(Invalid) {
1759 /// \brief Class iterator
1761 /// The iterator stores
1765 const HeapUnionFind* _huf;
1770 ClassIt(const HeapUnionFind& huf)
1771 : _huf(&huf), _id(huf.first_class) {}
1773 ClassIt(const HeapUnionFind& huf, int cls)
1774 : _huf(&huf), _id(huf.classes[cls].left) {}
1776 ClassIt(Invalid) : _huf(0), _id(-1) {}
1778 const ClassIt& operator++() {
1779 _id = _huf->classes[_id].next;
1783 /// \brief Equality operator
1785 /// Equality operator
1786 bool operator==(const ClassIt& i) {
1787 return i._id == _id;
1790 /// \brief Inequality operator
1792 /// Inequality operator
1793 bool operator!=(const ClassIt& i) {
1794 return i._id != _id;
1797 operator int() const {
1809 #endif //LEMON_UNION_FIND_H