Update INSTALL file.
1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
3 * This file is a part of LEMON, a generic C++ optimization library.
5 * Copyright (C) 2003-2008
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(nodes[jd].left, nodes[jd].next)) {
1181 nodes[nodes[jd].next].prio = nodes[nodes[jd].left].prio;
1182 nodes[nodes[jd].next].item = nodes[nodes[jd].left].item;
1188 int ld = nodes[nodes[jd].next].left;
1189 popLeft(nodes[jd].next);
1191 if (less(ld, nodes[jd].left)) {
1192 nodes[jd].item = nodes[ld].item;
1193 nodes[jd].prio = nodes[jd].prio;
1195 if (nodes[nodes[jd].next].item == nodes[ld].item) {
1196 setPrio(nodes[jd].next);
1198 jd = nodes[jd].left;
1202 jd = nodes[jd].left;
1207 void repairRight(int id) {
1208 int jd = ~(classes[id].parent);
1209 while (nodes[jd].right != -1) {
1210 int kd = nodes[jd].right;
1211 if (nodes[jd].size == 1) {
1212 if (nodes[jd].parent < 0) {
1213 classes[id].parent = ~kd;
1214 classes[id].depth -= 1;
1215 nodes[kd].parent = ~id;
1219 int pd = nodes[jd].parent;
1220 if (nodes[nodes[jd].prev].size < cmax) {
1221 pushRight(nodes[jd].prev, nodes[jd].right);
1222 if (less(nodes[jd].right, nodes[jd].prev)) {
1223 nodes[nodes[jd].prev].prio = nodes[nodes[jd].right].prio;
1224 nodes[nodes[jd].prev].item = nodes[nodes[jd].right].item;
1230 int ld = nodes[nodes[jd].prev].right;
1231 popRight(nodes[jd].prev);
1233 if (less(ld, nodes[jd].right)) {
1234 nodes[jd].item = nodes[ld].item;
1235 nodes[jd].prio = nodes[jd].prio;
1237 if (nodes[nodes[jd].prev].item == nodes[ld].item) {
1238 setPrio(nodes[jd].prev);
1240 jd = nodes[jd].right;
1244 jd = nodes[jd].right;
1250 bool less(int id, int jd) const {
1251 return comp(nodes[id].prio, nodes[jd].prio);
1254 bool equal(int id, int jd) const {
1255 return !less(id, jd) && !less(jd, id);
1261 /// \brief Returns true when the given class is alive.
1263 /// Returns true when the given class is alive, ie. the class is
1264 /// not nested into other class.
1265 bool alive(int cls) const {
1266 return classes[cls].parent < 0;
1269 /// \brief Returns true when the given class is trivial.
1271 /// Returns true when the given class is trivial, ie. the class
1272 /// contains just one item directly.
1273 bool trivial(int cls) const {
1274 return classes[cls].left == -1;
1277 /// \brief Constructs the union-find.
1279 /// Constructs the union-find.
1280 /// \brief _index The index map of the union-find. The data
1281 /// structure uses internally for store references.
1282 HeapUnionFind(ItemIntMap& _index)
1283 : index(_index), first_class(-1),
1284 first_free_class(-1), first_free_node(-1) {}
1286 /// \brief Insert a new node into a new component.
1288 /// Insert a new node into a new component.
1289 /// \param item The item of the new node.
1290 /// \param prio The priority of the new node.
1291 /// \return The class id of the one-item-heap.
1292 int insert(const Item& item, const Value& prio) {
1294 nodes[id].item = item;
1295 nodes[id].prio = prio;
1298 nodes[id].prev = -1;
1299 nodes[id].next = -1;
1301 nodes[id].left = -1;
1302 nodes[id].right = -1;
1304 nodes[id].item = item;
1307 int class_id = newClass();
1308 classes[class_id].parent = ~id;
1309 classes[class_id].depth = 0;
1311 classes[class_id].left = -1;
1312 classes[class_id].right = -1;
1314 if (first_class != -1) {
1315 classes[first_class].prev = class_id;
1317 classes[class_id].next = first_class;
1318 classes[class_id].prev = -1;
1319 first_class = class_id;
1321 nodes[id].parent = ~class_id;
1326 /// \brief The class of the item.
1328 /// \return The alive class id of the item, which is not nested into
1331 /// The time complexity is O(log(n)).
1332 int find(const Item& item) const {
1333 return findClass(index[item]);
1336 /// \brief Joins the classes.
1338 /// The current function joins the given classes. The parameter is
1339 /// an STL range which should be contains valid class ids. The
1340 /// time complexity is O(log(n)*k) where n is the overall number
1341 /// of the joined nodes and k is the number of classes.
1342 /// \return The class of the joined classes.
1343 /// \pre The range should contain at least two class ids.
1344 template <typename Iterator>
1345 int join(Iterator begin, Iterator end) {
1346 std::vector<int> cs;
1347 for (Iterator it = begin; it != end; ++it) {
1351 int class_id = newClass();
1352 { // creation union-find
1354 if (first_class != -1) {
1355 classes[first_class].prev = class_id;
1357 classes[class_id].next = first_class;
1358 classes[class_id].prev = -1;
1359 first_class = class_id;
1361 classes[class_id].depth = classes[cs[0]].depth;
1362 classes[class_id].parent = classes[cs[0]].parent;
1363 nodes[~(classes[class_id].parent)].parent = ~class_id;
1367 classes[class_id].left = l;
1368 classes[class_id].right = l;
1370 if (classes[l].next != -1) {
1371 classes[classes[l].next].prev = classes[l].prev;
1373 classes[classes[l].prev].next = classes[l].next;
1375 classes[l].prev = -1;
1376 classes[l].next = -1;
1378 classes[l].depth = leftNode(l);
1379 classes[l].parent = class_id;
1383 { // merging of heap
1385 for (int ci = 1; ci < int(cs.size()); ++ci) {
1387 int rln = leftNode(r);
1388 if (classes[l].depth > classes[r].depth) {
1389 int id = ~(classes[l].parent);
1390 for (int i = classes[r].depth + 1; i < classes[l].depth; ++i) {
1391 id = nodes[id].right;
1393 while (id >= 0 && nodes[id].size == cmax) {
1394 int new_id = newNode();
1395 int right_id = nodes[id].right;
1398 if (nodes[id].item == nodes[right_id].item) {
1401 push(new_id, right_id);
1402 pushRight(new_id, ~(classes[r].parent));
1405 id = nodes[id].parent;
1406 classes[r].parent = ~new_id;
1409 int new_parent = newNode();
1410 nodes[new_parent].next = -1;
1411 nodes[new_parent].prev = -1;
1412 nodes[new_parent].parent = ~l;
1414 push(new_parent, ~(classes[l].parent));
1415 pushRight(new_parent, ~(classes[r].parent));
1416 setPrio(new_parent);
1418 classes[l].parent = ~new_parent;
1419 classes[l].depth += 1;
1421 pushRight(id, ~(classes[r].parent));
1422 while (id >= 0 && less(~(classes[r].parent), id)) {
1423 nodes[id].prio = nodes[~(classes[r].parent)].prio;
1424 nodes[id].item = nodes[~(classes[r].parent)].item;
1425 id = nodes[id].parent;
1428 } else if (classes[r].depth > classes[l].depth) {
1429 int id = ~(classes[r].parent);
1430 for (int i = classes[l].depth + 1; i < classes[r].depth; ++i) {
1431 id = nodes[id].left;
1433 while (id >= 0 && nodes[id].size == cmax) {
1434 int new_id = newNode();
1435 int left_id = nodes[id].left;
1438 if (nodes[id].prio == nodes[left_id].prio) {
1441 push(new_id, left_id);
1442 pushLeft(new_id, ~(classes[l].parent));
1445 id = nodes[id].parent;
1446 classes[l].parent = ~new_id;
1450 int new_parent = newNode();
1451 nodes[new_parent].next = -1;
1452 nodes[new_parent].prev = -1;
1453 nodes[new_parent].parent = ~l;
1455 push(new_parent, ~(classes[r].parent));
1456 pushLeft(new_parent, ~(classes[l].parent));
1457 setPrio(new_parent);
1459 classes[r].parent = ~new_parent;
1460 classes[r].depth += 1;
1462 pushLeft(id, ~(classes[l].parent));
1463 while (id >= 0 && less(~(classes[l].parent), id)) {
1464 nodes[id].prio = nodes[~(classes[l].parent)].prio;
1465 nodes[id].item = nodes[~(classes[l].parent)].item;
1466 id = nodes[id].parent;
1469 nodes[~(classes[r].parent)].parent = ~l;
1470 classes[l].parent = classes[r].parent;
1471 classes[l].depth = classes[r].depth;
1473 if (classes[l].depth != 0 &&
1474 nodes[~(classes[l].parent)].size +
1475 nodes[~(classes[r].parent)].size <= cmax) {
1476 splice(~(classes[l].parent), ~(classes[r].parent));
1477 deleteNode(~(classes[r].parent));
1478 if (less(~(classes[r].parent), ~(classes[l].parent))) {
1479 nodes[~(classes[l].parent)].prio =
1480 nodes[~(classes[r].parent)].prio;
1481 nodes[~(classes[l].parent)].item =
1482 nodes[~(classes[r].parent)].item;
1485 int new_parent = newNode();
1486 nodes[new_parent].next = nodes[new_parent].prev = -1;
1487 push(new_parent, ~(classes[l].parent));
1488 pushRight(new_parent, ~(classes[r].parent));
1489 setPrio(new_parent);
1491 classes[l].parent = ~new_parent;
1492 classes[l].depth += 1;
1493 nodes[new_parent].parent = ~l;
1496 if (classes[r].next != -1) {
1497 classes[classes[r].next].prev = classes[r].prev;
1499 classes[classes[r].prev].next = classes[r].next;
1501 classes[r].prev = classes[l].right;
1502 classes[classes[l].right].next = r;
1503 classes[l].right = r;
1504 classes[r].parent = l;
1506 classes[r].next = -1;
1507 classes[r].depth = rln;
1513 /// \brief Split the class to subclasses.
1515 /// The current function splits the given class. The join, which
1516 /// made the current class, stored a reference to the
1517 /// subclasses. The \c splitClass() member restores the classes
1518 /// and creates the heaps. The parameter is an STL output iterator
1519 /// which will be filled with the subclass ids. The time
1520 /// complexity is O(log(n)*k) where n is the overall number of
1521 /// nodes in the splitted classes and k is the number of the
1523 template <typename Iterator>
1524 void split(int cls, Iterator out) {
1525 std::vector<int> cs;
1526 { // splitting union-find
1528 int l = classes[id].left;
1530 classes[l].parent = classes[id].parent;
1531 classes[l].depth = classes[id].depth;
1533 nodes[~(classes[l].parent)].parent = ~l;
1539 l = classes[l].next;
1542 classes[classes[id].right].next = first_class;
1543 classes[first_class].prev = classes[id].right;
1544 first_class = classes[id].left;
1546 if (classes[id].next != -1) {
1547 classes[classes[id].next].prev = classes[id].prev;
1549 classes[classes[id].prev].next = classes[id].next;
1555 for (int i = 1; i < int(cs.size()); ++i) {
1556 int l = classes[cs[i]].depth;
1557 while (nodes[nodes[l].parent].left == l) {
1558 l = nodes[l].parent;
1561 while (nodes[l].parent >= 0) {
1562 l = nodes[l].parent;
1563 int new_node = newNode();
1565 nodes[new_node].prev = -1;
1566 nodes[new_node].next = -1;
1569 pushAfter(l, new_node);
1574 classes[cs[i]].parent = ~r;
1575 classes[cs[i]].depth = classes[~(nodes[l].parent)].depth;
1576 nodes[r].parent = ~cs[i];
1581 repairRight(~(nodes[l].parent));
1589 /// \brief Gives back the priority of the current item.
1591 /// \return Gives back the priority of the current item.
1592 const Value& operator[](const Item& item) const {
1593 return nodes[index[item]].prio;
1596 /// \brief Sets the priority of the current item.
1598 /// Sets the priority of the current item.
1599 void set(const Item& item, const Value& prio) {
1600 if (comp(prio, nodes[index[item]].prio)) {
1601 decrease(item, prio);
1602 } else if (!comp(prio, nodes[index[item]].prio)) {
1603 increase(item, prio);
1607 /// \brief Increase the priority of the current item.
1609 /// Increase the priority of the current item.
1610 void increase(const Item& item, const Value& prio) {
1611 int id = index[item];
1612 int kd = nodes[id].parent;
1613 nodes[id].prio = prio;
1614 while (kd >= 0 && nodes[kd].item == item) {
1616 kd = nodes[kd].parent;
1620 /// \brief Increase the priority of the current item.
1622 /// Increase the priority of the current item.
1623 void decrease(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 && less(id, kd)) {
1628 nodes[kd].prio = prio;
1629 nodes[kd].item = item;
1630 kd = nodes[kd].parent;
1634 /// \brief Gives back the minimum priority of the class.
1636 /// \return Gives back the minimum priority of the class.
1637 const Value& classPrio(int cls) const {
1638 return nodes[~(classes[cls].parent)].prio;
1641 /// \brief Gives back the minimum priority item of the class.
1643 /// \return Gives back the minimum priority item of the class.
1644 const Item& classTop(int cls) const {
1645 return nodes[~(classes[cls].parent)].item;
1648 /// \brief Gives back a representant item of the class.
1650 /// The representant is indpendent from the priorities of the
1652 /// \return Gives back a representant item of the class.
1653 const Item& classRep(int id) const {
1654 int parent = classes[id].parent;
1655 return nodes[parent >= 0 ? classes[id].depth : leftNode(id)].item;
1658 /// \brief LEMON style iterator for the items of a class.
1660 /// ClassIt is a lemon style iterator for the components. It iterates
1661 /// on the items of a class. By example if you want to iterate on
1662 /// each items of each classes then you may write the next code.
1664 /// for (ClassIt cit(huf); cit != INVALID; ++cit) {
1665 /// std::cout << "Class: ";
1666 /// for (ItemIt iit(huf, cit); iit != INVALID; ++iit) {
1667 /// std::cout << toString(iit) << ' ' << std::endl;
1669 /// std::cout << std::endl;
1675 const HeapUnionFind* _huf;
1680 /// \brief Default constructor
1682 /// Default constructor
1685 ItemIt(const HeapUnionFind& huf, int cls) : _huf(&huf) {
1687 int parent = _huf->classes[id].parent;
1689 _id = _huf->classes[id].depth;
1690 if (_huf->classes[id].next != -1) {
1691 _lid = _huf->classes[_huf->classes[id].next].depth;
1696 _id = _huf->leftNode(id);
1701 /// \brief Increment operator
1703 /// It steps to the next item in the class.
1704 ItemIt& operator++() {
1705 _id = _huf->nextNode(_id);
1709 /// \brief Conversion operator
1711 /// It converts the iterator to the current item.
1712 operator const Item&() const {
1713 return _huf->nodes[_id].item;
1716 /// \brief Equality operator
1718 /// Equality operator
1719 bool operator==(const ItemIt& i) {
1720 return i._id == _id;
1723 /// \brief Inequality operator
1725 /// Inequality operator
1726 bool operator!=(const ItemIt& i) {
1727 return i._id != _id;
1730 /// \brief Equality operator
1732 /// Equality operator
1733 bool operator==(Invalid) {
1737 /// \brief Inequality operator
1739 /// Inequality operator
1740 bool operator!=(Invalid) {
1746 /// \brief Class iterator
1748 /// The iterator stores
1752 const HeapUnionFind* _huf;
1757 ClassIt(const HeapUnionFind& huf)
1758 : _huf(&huf), _id(huf.first_class) {}
1760 ClassIt(const HeapUnionFind& huf, int cls)
1761 : _huf(&huf), _id(huf.classes[cls].left) {}
1763 ClassIt(Invalid) : _huf(0), _id(-1) {}
1765 const ClassIt& operator++() {
1766 _id = _huf->classes[_id].next;
1770 /// \brief Equality operator
1772 /// Equality operator
1773 bool operator==(const ClassIt& i) {
1774 return i._id == _id;
1777 /// \brief Inequality operator
1779 /// Inequality operator
1780 bool operator!=(const ClassIt& i) {
1781 return i._id != _id;
1784 operator int() const {
1796 #endif //LEMON_UNION_FIND_H