|
1 /* -*- C++ -*- |
|
2 * |
|
3 * This file is a part of LEMON, a generic C++ optimization library |
|
4 * |
|
5 * Copyright (C) 2003-2008 |
|
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
|
7 * (Egervary Research Group on Combinatorial Optimization, EGRES). |
|
8 * |
|
9 * Permission to use, modify and distribute this software is granted |
|
10 * provided that this copyright notice appears in all copies. For |
|
11 * precise terms see the accompanying LICENSE file. |
|
12 * |
|
13 * This software is provided "AS IS" with no warranty of any kind, |
|
14 * express or implied, and with no claim as to its suitability for any |
|
15 * purpose. |
|
16 * |
|
17 */ |
|
18 |
|
19 #ifndef LEMON_UNION_FIND_H |
|
20 #define LEMON_UNION_FIND_H |
|
21 |
|
22 //!\ingroup auxdat |
|
23 //!\file |
|
24 //!\brief Union-Find data structures. |
|
25 //! |
|
26 |
|
27 #include <vector> |
|
28 #include <list> |
|
29 #include <utility> |
|
30 #include <algorithm> |
|
31 #include <functional> |
|
32 |
|
33 #include <lemon/bits/invalid.h> |
|
34 |
|
35 namespace lemon { |
|
36 |
|
37 /// \ingroup auxdat |
|
38 /// |
|
39 /// \brief A \e Union-Find data structure implementation |
|
40 /// |
|
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. |
|
47 /// |
|
48 /// It is primarily used in Kruskal algorithm for finding minimal |
|
49 /// cost spanning tree in a graph. |
|
50 /// \sa kruskal() |
|
51 /// |
|
52 /// \pre You need to add all the elements by the \ref insert() |
|
53 /// method. |
|
54 template <typename _ItemIntMap> |
|
55 class UnionFind { |
|
56 public: |
|
57 |
|
58 typedef _ItemIntMap ItemIntMap; |
|
59 typedef typename ItemIntMap::Key Item; |
|
60 |
|
61 private: |
|
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; |
|
66 ItemIntMap& index; |
|
67 |
|
68 bool rep(int idx) const { |
|
69 return items[idx] < 0; |
|
70 } |
|
71 |
|
72 int repIndex(int idx) const { |
|
73 int k = idx; |
|
74 while (!rep(k)) { |
|
75 k = items[k] ; |
|
76 } |
|
77 while (idx != k) { |
|
78 int next = items[idx]; |
|
79 const_cast<int&>(items[idx]) = k; |
|
80 idx = next; |
|
81 } |
|
82 return k; |
|
83 } |
|
84 |
|
85 public: |
|
86 |
|
87 /// \brief Constructor |
|
88 /// |
|
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 |
|
93 /// the union-find. |
|
94 UnionFind(ItemIntMap& m) : index(m) {} |
|
95 |
|
96 /// \brief Returns the index of the element's component. |
|
97 /// |
|
98 /// The method returns the index of the element's component. |
|
99 /// This is an integer between zero and the number of inserted elements. |
|
100 /// |
|
101 int find(const Item& a) { |
|
102 return repIndex(index[a]); |
|
103 } |
|
104 |
|
105 /// \brief Clears the union-find data structure |
|
106 /// |
|
107 /// Erase each item from the data structure. |
|
108 void clear() { |
|
109 items.clear(); |
|
110 } |
|
111 |
|
112 /// \brief Inserts a new element into the structure. |
|
113 /// |
|
114 /// This method inserts a new element into the data structure. |
|
115 /// |
|
116 /// The method returns the index of the new component. |
|
117 int insert(const Item& a) { |
|
118 int n = items.size(); |
|
119 items.push_back(-1); |
|
120 index.set(a,n); |
|
121 return n; |
|
122 } |
|
123 |
|
124 /// \brief Joining the components of element \e a and element \e b. |
|
125 /// |
|
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]); |
|
133 |
|
134 if ( ka == kb ) |
|
135 return false; |
|
136 |
|
137 if (items[ka] < items[kb]) { |
|
138 items[ka] += items[kb]; |
|
139 items[kb] = ka; |
|
140 } else { |
|
141 items[kb] += items[ka]; |
|
142 items[ka] = kb; |
|
143 } |
|
144 return true; |
|
145 } |
|
146 |
|
147 /// \brief Returns the size of the component of element \e a. |
|
148 /// |
|
149 /// Returns the size of the component of element \e a. |
|
150 int size(const Item& a) { |
|
151 int k = repIndex(index[a]); |
|
152 return - items[k]; |
|
153 } |
|
154 |
|
155 }; |
|
156 |
|
157 /// \ingroup auxdat |
|
158 /// |
|
159 /// \brief A \e Union-Find data structure implementation which |
|
160 /// is able to enumerate the components. |
|
161 /// |
|
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. |
|
166 /// |
|
167 /// The union operation uses rank heuristic, while |
|
168 /// the find operation uses path compression. |
|
169 /// |
|
170 /// \pre You need to add all the elements by the \ref insert() |
|
171 /// method. |
|
172 /// |
|
173 template <typename _ItemIntMap> |
|
174 class UnionFindEnum { |
|
175 public: |
|
176 |
|
177 typedef _ItemIntMap ItemIntMap; |
|
178 typedef typename ItemIntMap::Key Item; |
|
179 |
|
180 private: |
|
181 |
|
182 ItemIntMap& index; |
|
183 |
|
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. |
|
187 // |
|
188 // The \c next and \c prev provides the double-linked |
|
189 // cyclic list of one component's items. |
|
190 struct ItemT { |
|
191 int parent; |
|
192 Item item; |
|
193 |
|
194 int next, prev; |
|
195 }; |
|
196 |
|
197 std::vector<ItemT> items; |
|
198 int firstFreeItem; |
|
199 |
|
200 struct ClassT { |
|
201 int size; |
|
202 int firstItem; |
|
203 int next, prev; |
|
204 }; |
|
205 |
|
206 std::vector<ClassT> classes; |
|
207 int firstClass, firstFreeClass; |
|
208 |
|
209 int newClass() { |
|
210 if (firstFreeClass == -1) { |
|
211 int cdx = classes.size(); |
|
212 classes.push_back(ClassT()); |
|
213 return cdx; |
|
214 } else { |
|
215 int cdx = firstFreeClass; |
|
216 firstFreeClass = classes[firstFreeClass].next; |
|
217 return cdx; |
|
218 } |
|
219 } |
|
220 |
|
221 int newItem() { |
|
222 if (firstFreeItem == -1) { |
|
223 int idx = items.size(); |
|
224 items.push_back(ItemT()); |
|
225 return idx; |
|
226 } else { |
|
227 int idx = firstFreeItem; |
|
228 firstFreeItem = items[firstFreeItem].next; |
|
229 return idx; |
|
230 } |
|
231 } |
|
232 |
|
233 |
|
234 bool rep(int idx) const { |
|
235 return items[idx].parent < 0; |
|
236 } |
|
237 |
|
238 int repIndex(int idx) const { |
|
239 int k = idx; |
|
240 while (!rep(k)) { |
|
241 k = items[k].parent; |
|
242 } |
|
243 while (idx != k) { |
|
244 int next = items[idx].parent; |
|
245 const_cast<int&>(items[idx].parent) = k; |
|
246 idx = next; |
|
247 } |
|
248 return k; |
|
249 } |
|
250 |
|
251 int classIndex(int idx) const { |
|
252 return ~(items[repIndex(idx)].parent); |
|
253 } |
|
254 |
|
255 void singletonItem(int idx) { |
|
256 items[idx].next = idx; |
|
257 items[idx].prev = idx; |
|
258 } |
|
259 |
|
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; |
|
265 } |
|
266 |
|
267 void unlaceItem(int idx) { |
|
268 items[items[idx].prev].next = items[idx].next; |
|
269 items[items[idx].next].prev = items[idx].prev; |
|
270 |
|
271 items[idx].next = firstFreeItem; |
|
272 firstFreeItem = idx; |
|
273 } |
|
274 |
|
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; |
|
281 |
|
282 } |
|
283 |
|
284 void laceClass(int cls) { |
|
285 if (firstClass != -1) { |
|
286 classes[firstClass].prev = cls; |
|
287 } |
|
288 classes[cls].next = firstClass; |
|
289 classes[cls].prev = -1; |
|
290 firstClass = cls; |
|
291 } |
|
292 |
|
293 void unlaceClass(int cls) { |
|
294 if (classes[cls].prev != -1) { |
|
295 classes[classes[cls].prev].next = classes[cls].next; |
|
296 } else { |
|
297 firstClass = classes[cls].next; |
|
298 } |
|
299 if (classes[cls].next != -1) { |
|
300 classes[classes[cls].next].prev = classes[cls].prev; |
|
301 } |
|
302 |
|
303 classes[cls].next = firstFreeClass; |
|
304 firstFreeClass = cls; |
|
305 } |
|
306 |
|
307 public: |
|
308 |
|
309 UnionFindEnum(ItemIntMap& _index) |
|
310 : index(_index), items(), firstFreeItem(-1), |
|
311 firstClass(-1), firstFreeClass(-1) {} |
|
312 |
|
313 /// \brief Inserts the given element into a new component. |
|
314 /// |
|
315 /// This method creates a new component consisting only of the |
|
316 /// given element. |
|
317 /// |
|
318 int insert(const Item& item) { |
|
319 int idx = newItem(); |
|
320 |
|
321 index.set(item, idx); |
|
322 |
|
323 singletonItem(idx); |
|
324 items[idx].item = item; |
|
325 |
|
326 int cdx = newClass(); |
|
327 |
|
328 items[idx].parent = ~cdx; |
|
329 |
|
330 laceClass(cdx); |
|
331 classes[cdx].size = 1; |
|
332 classes[cdx].firstItem = idx; |
|
333 |
|
334 firstClass = cdx; |
|
335 |
|
336 return cdx; |
|
337 } |
|
338 |
|
339 /// \brief Inserts the given element into the component of the others. |
|
340 /// |
|
341 /// This methods inserts the element \e a into the component of the |
|
342 /// element \e comp. |
|
343 void insert(const Item& item, int cls) { |
|
344 int rdx = classes[cls].firstItem; |
|
345 int idx = newItem(); |
|
346 |
|
347 index.set(item, idx); |
|
348 |
|
349 laceItem(idx, rdx); |
|
350 |
|
351 items[idx].item = item; |
|
352 items[idx].parent = rdx; |
|
353 |
|
354 ++classes[~(items[rdx].parent)].size; |
|
355 } |
|
356 |
|
357 /// \brief Clears the union-find data structure |
|
358 /// |
|
359 /// Erase each item from the data structure. |
|
360 void clear() { |
|
361 items.clear(); |
|
362 firstClass = -1; |
|
363 firstFreeItem = -1; |
|
364 } |
|
365 |
|
366 /// \brief Finds the component of the given element. |
|
367 /// |
|
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); |
|
371 } |
|
372 |
|
373 /// \brief Joining the component of element \e a and element \e b. |
|
374 /// |
|
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) { |
|
380 |
|
381 int ak = repIndex(index[a]); |
|
382 int bk = repIndex(index[b]); |
|
383 |
|
384 if (ak == bk) { |
|
385 return -1; |
|
386 } |
|
387 |
|
388 int acx = ~(items[ak].parent); |
|
389 int bcx = ~(items[bk].parent); |
|
390 |
|
391 int rcx; |
|
392 |
|
393 if (classes[acx].size > classes[bcx].size) { |
|
394 classes[acx].size += classes[bcx].size; |
|
395 items[bk].parent = ak; |
|
396 unlaceClass(bcx); |
|
397 rcx = acx; |
|
398 } else { |
|
399 classes[bcx].size += classes[acx].size; |
|
400 items[ak].parent = bk; |
|
401 unlaceClass(acx); |
|
402 rcx = bcx; |
|
403 } |
|
404 spliceItems(ak, bk); |
|
405 |
|
406 return rcx; |
|
407 } |
|
408 |
|
409 /// \brief Returns the size of the class. |
|
410 /// |
|
411 /// Returns the size of the class. |
|
412 int size(int cls) const { |
|
413 return classes[cls].size; |
|
414 } |
|
415 |
|
416 /// \brief Splits up the component. |
|
417 /// |
|
418 /// Splitting the component into singleton components (component |
|
419 /// of size one). |
|
420 void split(int cls) { |
|
421 int fdx = classes[cls].firstItem; |
|
422 int idx = items[fdx].next; |
|
423 while (idx != fdx) { |
|
424 int next = items[idx].next; |
|
425 |
|
426 singletonItem(idx); |
|
427 |
|
428 int cdx = newClass(); |
|
429 items[idx].parent = ~cdx; |
|
430 |
|
431 laceClass(cdx); |
|
432 classes[cdx].size = 1; |
|
433 classes[cdx].firstItem = idx; |
|
434 |
|
435 idx = next; |
|
436 } |
|
437 |
|
438 items[idx].prev = idx; |
|
439 items[idx].next = idx; |
|
440 |
|
441 classes[~(items[idx].parent)].size = 1; |
|
442 |
|
443 } |
|
444 |
|
445 /// \brief Removes the given element from the structure. |
|
446 /// |
|
447 /// Removes the element from its component and if the component becomes |
|
448 /// empty then removes that component from the component list. |
|
449 /// |
|
450 /// \warning It is an error to remove an element which is not in |
|
451 /// the structure. |
|
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; |
|
457 |
|
458 int cdx = classIndex(idx); |
|
459 if (idx == fdx) { |
|
460 unlaceClass(cdx); |
|
461 items[idx].next = firstFreeItem; |
|
462 firstFreeItem = idx; |
|
463 return; |
|
464 } else { |
|
465 classes[cdx].firstItem = fdx; |
|
466 --classes[cdx].size; |
|
467 items[fdx].parent = ~cdx; |
|
468 |
|
469 unlaceItem(idx); |
|
470 idx = items[fdx].next; |
|
471 while (idx != fdx) { |
|
472 items[idx].parent = fdx; |
|
473 idx = items[idx].next; |
|
474 } |
|
475 |
|
476 } |
|
477 |
|
478 } |
|
479 |
|
480 /// \brief Gives back a representant item of the component. |
|
481 /// |
|
482 /// Gives back a representant item of the component. |
|
483 Item item(int cls) const { |
|
484 return items[classes[cls].firstItem].item; |
|
485 } |
|
486 |
|
487 /// \brief Removes the component of the given element from the structure. |
|
488 /// |
|
489 /// Removes the component of the given element from the structure. |
|
490 /// |
|
491 /// \warning It is an error to give an element which is not in the |
|
492 /// structure. |
|
493 void eraseClass(int cls) { |
|
494 int fdx = classes[cls].firstItem; |
|
495 unlaceClass(cls); |
|
496 items[items[fdx].prev].next = firstFreeItem; |
|
497 firstFreeItem = fdx; |
|
498 } |
|
499 |
|
500 /// \brief Lemon style iterator for the representant items. |
|
501 /// |
|
502 /// ClassIt is a lemon style iterator for the components. It iterates |
|
503 /// on the ids of the classes. |
|
504 class ClassIt { |
|
505 public: |
|
506 /// \brief Constructor of the iterator |
|
507 /// |
|
508 /// Constructor of the iterator |
|
509 ClassIt(const UnionFindEnum& ufe) : unionFind(&ufe) { |
|
510 cdx = unionFind->firstClass; |
|
511 } |
|
512 |
|
513 /// \brief Constructor to get invalid iterator |
|
514 /// |
|
515 /// Constructor to get invalid iterator |
|
516 ClassIt(Invalid) : unionFind(0), cdx(-1) {} |
|
517 |
|
518 /// \brief Increment operator |
|
519 /// |
|
520 /// It steps to the next representant item. |
|
521 ClassIt& operator++() { |
|
522 cdx = unionFind->classes[cdx].next; |
|
523 return *this; |
|
524 } |
|
525 |
|
526 /// \brief Conversion operator |
|
527 /// |
|
528 /// It converts the iterator to the current representant item. |
|
529 operator int() const { |
|
530 return cdx; |
|
531 } |
|
532 |
|
533 /// \brief Equality operator |
|
534 /// |
|
535 /// Equality operator |
|
536 bool operator==(const ClassIt& i) { |
|
537 return i.cdx == cdx; |
|
538 } |
|
539 |
|
540 /// \brief Inequality operator |
|
541 /// |
|
542 /// Inequality operator |
|
543 bool operator!=(const ClassIt& i) { |
|
544 return i.cdx != cdx; |
|
545 } |
|
546 |
|
547 private: |
|
548 const UnionFindEnum* unionFind; |
|
549 int cdx; |
|
550 }; |
|
551 |
|
552 /// \brief Lemon style iterator for the items of a component. |
|
553 /// |
|
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. |
|
557 ///\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; |
|
562 /// } |
|
563 /// std::cout << std::endl; |
|
564 /// } |
|
565 ///\endcode |
|
566 class ItemIt { |
|
567 public: |
|
568 /// \brief Constructor of the iterator |
|
569 /// |
|
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; |
|
574 } |
|
575 |
|
576 /// \brief Constructor to get invalid iterator |
|
577 /// |
|
578 /// Constructor to get invalid iterator |
|
579 ItemIt(Invalid) : unionFind(0), idx(-1) {} |
|
580 |
|
581 /// \brief Increment operator |
|
582 /// |
|
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; |
|
587 return *this; |
|
588 } |
|
589 |
|
590 /// \brief Conversion operator |
|
591 /// |
|
592 /// It converts the iterator to the current item. |
|
593 operator const Item&() const { |
|
594 return unionFind->items[idx].item; |
|
595 } |
|
596 |
|
597 /// \brief Equality operator |
|
598 /// |
|
599 /// Equality operator |
|
600 bool operator==(const ItemIt& i) { |
|
601 return i.idx == idx; |
|
602 } |
|
603 |
|
604 /// \brief Inequality operator |
|
605 /// |
|
606 /// Inequality operator |
|
607 bool operator!=(const ItemIt& i) { |
|
608 return i.idx != idx; |
|
609 } |
|
610 |
|
611 private: |
|
612 const UnionFindEnum* unionFind; |
|
613 int idx, fdx; |
|
614 }; |
|
615 |
|
616 }; |
|
617 |
|
618 /// \ingroup auxdat |
|
619 /// |
|
620 /// \brief A \e Extend-Find data structure implementation which |
|
621 /// is able to enumerate the components. |
|
622 /// |
|
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. |
|
627 /// |
|
628 /// \pre You need to add all the elements by the \ref insert() |
|
629 /// method. |
|
630 template <typename _ItemIntMap> |
|
631 class ExtendFindEnum { |
|
632 public: |
|
633 |
|
634 typedef _ItemIntMap ItemIntMap; |
|
635 typedef typename ItemIntMap::Key Item; |
|
636 |
|
637 private: |
|
638 |
|
639 ItemIntMap& index; |
|
640 |
|
641 struct ItemT { |
|
642 int cls; |
|
643 Item item; |
|
644 int next, prev; |
|
645 }; |
|
646 |
|
647 std::vector<ItemT> items; |
|
648 int firstFreeItem; |
|
649 |
|
650 struct ClassT { |
|
651 int firstItem; |
|
652 int next, prev; |
|
653 }; |
|
654 |
|
655 std::vector<ClassT> classes; |
|
656 |
|
657 int firstClass, firstFreeClass; |
|
658 |
|
659 int newClass() { |
|
660 if (firstFreeClass != -1) { |
|
661 int cdx = firstFreeClass; |
|
662 firstFreeClass = classes[cdx].next; |
|
663 return cdx; |
|
664 } else { |
|
665 classes.push_back(ClassT()); |
|
666 return classes.size() - 1; |
|
667 } |
|
668 } |
|
669 |
|
670 int newItem() { |
|
671 if (firstFreeItem != -1) { |
|
672 int idx = firstFreeItem; |
|
673 firstFreeItem = items[idx].next; |
|
674 return idx; |
|
675 } else { |
|
676 items.push_back(ItemT()); |
|
677 return items.size() - 1; |
|
678 } |
|
679 } |
|
680 |
|
681 public: |
|
682 |
|
683 /// \brief Constructor |
|
684 ExtendFindEnum(ItemIntMap& _index) |
|
685 : index(_index), items(), firstFreeItem(-1), |
|
686 classes(), firstClass(-1), firstFreeClass(-1) {} |
|
687 |
|
688 /// \brief Inserts the given element into a new component. |
|
689 /// |
|
690 /// This method creates a new component consisting only of the |
|
691 /// given element. |
|
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; |
|
698 } |
|
699 firstClass = cdx; |
|
700 |
|
701 int idx = newItem(); |
|
702 items[idx].item = item; |
|
703 items[idx].cls = cdx; |
|
704 items[idx].prev = idx; |
|
705 items[idx].next = idx; |
|
706 |
|
707 classes[cdx].firstItem = idx; |
|
708 |
|
709 index.set(item, idx); |
|
710 |
|
711 return cdx; |
|
712 } |
|
713 |
|
714 /// \brief Inserts the given element into the given component. |
|
715 /// |
|
716 /// This methods inserts the element \e item a into the \e cls class. |
|
717 void insert(const Item& item, int cls) { |
|
718 int idx = newItem(); |
|
719 int rdx = classes[cls].firstItem; |
|
720 items[idx].item = item; |
|
721 items[idx].cls = cls; |
|
722 |
|
723 items[idx].prev = rdx; |
|
724 items[idx].next = items[rdx].next; |
|
725 items[items[rdx].next].prev = idx; |
|
726 items[rdx].next = idx; |
|
727 |
|
728 index.set(item, idx); |
|
729 } |
|
730 |
|
731 /// \brief Clears the union-find data structure |
|
732 /// |
|
733 /// Erase each item from the data structure. |
|
734 void clear() { |
|
735 items.clear(); |
|
736 classes.clear; |
|
737 firstClass = firstFreeClass = firstFreeItem = -1; |
|
738 } |
|
739 |
|
740 /// \brief Gives back the class of the \e item. |
|
741 /// |
|
742 /// Gives back the class of the \e item. |
|
743 int find(const Item &item) const { |
|
744 return items[index[item]].cls; |
|
745 } |
|
746 |
|
747 /// \brief Gives back a representant item of the component. |
|
748 /// |
|
749 /// Gives back a representant item of the component. |
|
750 Item item(int cls) const { |
|
751 return items[classes[cls].firstItem].item; |
|
752 } |
|
753 |
|
754 /// \brief Removes the given element from the structure. |
|
755 /// |
|
756 /// Removes the element from its component and if the component becomes |
|
757 /// empty then removes that component from the component list. |
|
758 /// |
|
759 /// \warning It is an error to remove an element which is not in |
|
760 /// the structure. |
|
761 void erase(const Item &item) { |
|
762 int idx = index[item]; |
|
763 int cdx = items[idx].cls; |
|
764 |
|
765 if (idx == items[idx].next) { |
|
766 if (classes[cdx].prev != -1) { |
|
767 classes[classes[cdx].prev].next = classes[cdx].next; |
|
768 } else { |
|
769 firstClass = classes[cdx].next; |
|
770 } |
|
771 if (classes[cdx].next != -1) { |
|
772 classes[classes[cdx].next].prev = classes[cdx].prev; |
|
773 } |
|
774 classes[cdx].next = firstFreeClass; |
|
775 firstFreeClass = cdx; |
|
776 } else { |
|
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; |
|
780 } |
|
781 items[idx].next = firstFreeItem; |
|
782 firstFreeItem = idx; |
|
783 |
|
784 } |
|
785 |
|
786 |
|
787 /// \brief Removes the component of the given element from the structure. |
|
788 /// |
|
789 /// Removes the component of the given element from the structure. |
|
790 /// |
|
791 /// \warning It is an error to give an element which is not in the |
|
792 /// structure. |
|
793 void eraseClass(int cdx) { |
|
794 int idx = classes[cdx].firstItem; |
|
795 items[items[idx].prev].next = firstFreeItem; |
|
796 firstFreeItem = idx; |
|
797 |
|
798 if (classes[cdx].prev != -1) { |
|
799 classes[classes[cdx].prev].next = classes[cdx].next; |
|
800 } else { |
|
801 firstClass = classes[cdx].next; |
|
802 } |
|
803 if (classes[cdx].next != -1) { |
|
804 classes[classes[cdx].next].prev = classes[cdx].prev; |
|
805 } |
|
806 classes[cdx].next = firstFreeClass; |
|
807 firstFreeClass = cdx; |
|
808 } |
|
809 |
|
810 /// \brief Lemon style iterator for the classes. |
|
811 /// |
|
812 /// ClassIt is a lemon style iterator for the components. It iterates |
|
813 /// on the ids of classes. |
|
814 class ClassIt { |
|
815 public: |
|
816 /// \brief Constructor of the iterator |
|
817 /// |
|
818 /// Constructor of the iterator |
|
819 ClassIt(const ExtendFindEnum& ufe) : extendFind(&ufe) { |
|
820 cdx = extendFind->firstClass; |
|
821 } |
|
822 |
|
823 /// \brief Constructor to get invalid iterator |
|
824 /// |
|
825 /// Constructor to get invalid iterator |
|
826 ClassIt(Invalid) : extendFind(0), cdx(-1) {} |
|
827 |
|
828 /// \brief Increment operator |
|
829 /// |
|
830 /// It steps to the next representant item. |
|
831 ClassIt& operator++() { |
|
832 cdx = extendFind->classes[cdx].next; |
|
833 return *this; |
|
834 } |
|
835 |
|
836 /// \brief Conversion operator |
|
837 /// |
|
838 /// It converts the iterator to the current class id. |
|
839 operator int() const { |
|
840 return cdx; |
|
841 } |
|
842 |
|
843 /// \brief Equality operator |
|
844 /// |
|
845 /// Equality operator |
|
846 bool operator==(const ClassIt& i) { |
|
847 return i.cdx == cdx; |
|
848 } |
|
849 |
|
850 /// \brief Inequality operator |
|
851 /// |
|
852 /// Inequality operator |
|
853 bool operator!=(const ClassIt& i) { |
|
854 return i.cdx != cdx; |
|
855 } |
|
856 |
|
857 private: |
|
858 const ExtendFindEnum* extendFind; |
|
859 int cdx; |
|
860 }; |
|
861 |
|
862 /// \brief Lemon style iterator for the items of a component. |
|
863 /// |
|
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. |
|
867 ///\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; |
|
872 /// } |
|
873 /// std::cout << std::endl; |
|
874 /// } |
|
875 ///\endcode |
|
876 class ItemIt { |
|
877 public: |
|
878 /// \brief Constructor of the iterator |
|
879 /// |
|
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; |
|
884 } |
|
885 |
|
886 /// \brief Constructor to get invalid iterator |
|
887 /// |
|
888 /// Constructor to get invalid iterator |
|
889 ItemIt(Invalid) : extendFind(0), idx(-1) {} |
|
890 |
|
891 /// \brief Increment operator |
|
892 /// |
|
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; |
|
897 return *this; |
|
898 } |
|
899 |
|
900 /// \brief Conversion operator |
|
901 /// |
|
902 /// It converts the iterator to the current item. |
|
903 operator const Item&() const { |
|
904 return extendFind->items[idx].item; |
|
905 } |
|
906 |
|
907 /// \brief Equality operator |
|
908 /// |
|
909 /// Equality operator |
|
910 bool operator==(const ItemIt& i) { |
|
911 return i.idx == idx; |
|
912 } |
|
913 |
|
914 /// \brief Inequality operator |
|
915 /// |
|
916 /// Inequality operator |
|
917 bool operator!=(const ItemIt& i) { |
|
918 return i.idx != idx; |
|
919 } |
|
920 |
|
921 private: |
|
922 const ExtendFindEnum* extendFind; |
|
923 int idx, fdx; |
|
924 }; |
|
925 |
|
926 }; |
|
927 |
|
928 /// \ingroup auxdat |
|
929 /// |
|
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 |
|
932 /// each class. |
|
933 /// |
|
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. |
|
939 /// |
|
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 |
|
947 /// after the split. |
|
948 /// |
|
949 /// \pre You need to add all the elements by the \ref insert() |
|
950 /// method. |
|
951 /// |
|
952 template <typename _Value, typename _ItemIntMap, |
|
953 typename _Comp = std::less<_Value> > |
|
954 class HeapUnionFind { |
|
955 public: |
|
956 |
|
957 typedef _Value Value; |
|
958 typedef typename _ItemIntMap::Key Item; |
|
959 |
|
960 typedef _ItemIntMap ItemIntMap; |
|
961 |
|
962 typedef _Comp Comp; |
|
963 |
|
964 private: |
|
965 |
|
966 static const int cmax = 16; |
|
967 |
|
968 ItemIntMap& index; |
|
969 |
|
970 struct ClassNode { |
|
971 int parent; |
|
972 int depth; |
|
973 |
|
974 int left, right; |
|
975 int next, prev; |
|
976 }; |
|
977 |
|
978 int first_class; |
|
979 int first_free_class; |
|
980 std::vector<ClassNode> classes; |
|
981 |
|
982 int newClass() { |
|
983 if (first_free_class < 0) { |
|
984 int id = classes.size(); |
|
985 classes.push_back(ClassNode()); |
|
986 return id; |
|
987 } else { |
|
988 int id = first_free_class; |
|
989 first_free_class = classes[id].next; |
|
990 return id; |
|
991 } |
|
992 } |
|
993 |
|
994 void deleteClass(int id) { |
|
995 classes[id].next = first_free_class; |
|
996 first_free_class = id; |
|
997 } |
|
998 |
|
999 struct ItemNode { |
|
1000 int parent; |
|
1001 Item item; |
|
1002 Value prio; |
|
1003 int next, prev; |
|
1004 int left, right; |
|
1005 int size; |
|
1006 }; |
|
1007 |
|
1008 int first_free_node; |
|
1009 std::vector<ItemNode> nodes; |
|
1010 |
|
1011 int newNode() { |
|
1012 if (first_free_node < 0) { |
|
1013 int id = nodes.size(); |
|
1014 nodes.push_back(ItemNode()); |
|
1015 return id; |
|
1016 } else { |
|
1017 int id = first_free_node; |
|
1018 first_free_node = nodes[id].next; |
|
1019 return id; |
|
1020 } |
|
1021 } |
|
1022 |
|
1023 void deleteNode(int id) { |
|
1024 nodes[id].next = first_free_node; |
|
1025 first_free_node = id; |
|
1026 } |
|
1027 |
|
1028 Comp comp; |
|
1029 |
|
1030 int findClass(int id) const { |
|
1031 int kd = id; |
|
1032 while (kd >= 0) { |
|
1033 kd = nodes[kd].parent; |
|
1034 } |
|
1035 return ~kd; |
|
1036 } |
|
1037 |
|
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; |
|
1042 } |
|
1043 return kd; |
|
1044 } |
|
1045 |
|
1046 int nextNode(int id) const { |
|
1047 int depth = 0; |
|
1048 while (id >= 0 && nodes[id].next == -1) { |
|
1049 id = nodes[id].parent; |
|
1050 ++depth; |
|
1051 } |
|
1052 if (id < 0) { |
|
1053 return -1; |
|
1054 } |
|
1055 id = nodes[id].next; |
|
1056 while (depth--) { |
|
1057 id = nodes[id].left; |
|
1058 } |
|
1059 return id; |
|
1060 } |
|
1061 |
|
1062 |
|
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; |
|
1068 while (jd != -1) { |
|
1069 if (comp(nodes[jd].prio, nodes[id].prio)) { |
|
1070 nodes[id].prio = nodes[jd].prio; |
|
1071 nodes[id].item = nodes[jd].item; |
|
1072 } |
|
1073 jd = nodes[jd].next; |
|
1074 } |
|
1075 } |
|
1076 |
|
1077 void push(int id, int jd) { |
|
1078 nodes[id].size = 1; |
|
1079 nodes[id].left = nodes[id].right = jd; |
|
1080 nodes[jd].next = nodes[jd].prev = -1; |
|
1081 nodes[jd].parent = id; |
|
1082 } |
|
1083 |
|
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; |
|
1088 if (kd >= 0) { |
|
1089 nodes[kd].size += 1; |
|
1090 } |
|
1091 } else { |
|
1092 if (kd >= 0) { |
|
1093 nodes[kd].right = jd; |
|
1094 nodes[kd].size += 1; |
|
1095 } |
|
1096 } |
|
1097 nodes[jd].next = nodes[id].next; |
|
1098 nodes[jd].prev = id; |
|
1099 nodes[id].next = jd; |
|
1100 nodes[jd].parent = kd; |
|
1101 } |
|
1102 |
|
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; |
|
1110 } |
|
1111 |
|
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; |
|
1117 } |
|
1118 |
|
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; |
|
1124 while (kd != -1) { |
|
1125 nodes[kd].parent = id; |
|
1126 kd = nodes[kd].next; |
|
1127 } |
|
1128 nodes[id].right = nodes[jd].right; |
|
1129 } |
|
1130 |
|
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; |
|
1135 |
|
1136 nodes[jd].left = id; |
|
1137 nodes[id].prev = -1; |
|
1138 int num = 0; |
|
1139 while (id != -1) { |
|
1140 nodes[id].parent = jd; |
|
1141 nodes[jd].right = id; |
|
1142 id = nodes[id].next; |
|
1143 ++num; |
|
1144 } |
|
1145 nodes[kd].size -= num; |
|
1146 nodes[jd].size = num; |
|
1147 } |
|
1148 |
|
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; |
|
1156 } |
|
1157 |
|
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; |
|
1163 } |
|
1164 |
|
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; |
|
1174 deleteNode(jd); |
|
1175 jd = kd; |
|
1176 } else { |
|
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; |
|
1183 } |
|
1184 popLeft(pd); |
|
1185 deleteNode(jd); |
|
1186 jd = pd; |
|
1187 } else { |
|
1188 int ld = nodes[nodes[jd].next].left; |
|
1189 popLeft(nodes[jd].next); |
|
1190 pushRight(jd, ld); |
|
1191 if (less(ld, nodes[jd].left)) { |
|
1192 nodes[jd].item = nodes[ld].item; |
|
1193 nodes[jd].prio = nodes[jd].prio; |
|
1194 } |
|
1195 if (nodes[nodes[jd].next].item == nodes[ld].item) { |
|
1196 setPrio(nodes[jd].next); |
|
1197 } |
|
1198 jd = nodes[jd].left; |
|
1199 } |
|
1200 } |
|
1201 } else { |
|
1202 jd = nodes[jd].left; |
|
1203 } |
|
1204 } |
|
1205 } |
|
1206 |
|
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; |
|
1216 deleteNode(jd); |
|
1217 jd = kd; |
|
1218 } else { |
|
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; |
|
1225 } |
|
1226 popRight(pd); |
|
1227 deleteNode(jd); |
|
1228 jd = pd; |
|
1229 } else { |
|
1230 int ld = nodes[nodes[jd].prev].right; |
|
1231 popRight(nodes[jd].prev); |
|
1232 pushLeft(jd, ld); |
|
1233 if (less(ld, nodes[jd].right)) { |
|
1234 nodes[jd].item = nodes[ld].item; |
|
1235 nodes[jd].prio = nodes[jd].prio; |
|
1236 } |
|
1237 if (nodes[nodes[jd].prev].item == nodes[ld].item) { |
|
1238 setPrio(nodes[jd].prev); |
|
1239 } |
|
1240 jd = nodes[jd].right; |
|
1241 } |
|
1242 } |
|
1243 } else { |
|
1244 jd = nodes[jd].right; |
|
1245 } |
|
1246 } |
|
1247 } |
|
1248 |
|
1249 |
|
1250 bool less(int id, int jd) const { |
|
1251 return comp(nodes[id].prio, nodes[jd].prio); |
|
1252 } |
|
1253 |
|
1254 bool equal(int id, int jd) const { |
|
1255 return !less(id, jd) && !less(jd, id); |
|
1256 } |
|
1257 |
|
1258 |
|
1259 public: |
|
1260 |
|
1261 /// \brief Returns true when the given class is alive. |
|
1262 /// |
|
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; |
|
1267 } |
|
1268 |
|
1269 /// \brief Returns true when the given class is trivial. |
|
1270 /// |
|
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; |
|
1275 } |
|
1276 |
|
1277 /// \brief Constructs the union-find. |
|
1278 /// |
|
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) {} |
|
1285 |
|
1286 /// \brief Insert a new node into a new component. |
|
1287 /// |
|
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) { |
|
1293 int id = newNode(); |
|
1294 nodes[id].item = item; |
|
1295 nodes[id].prio = prio; |
|
1296 nodes[id].size = 0; |
|
1297 |
|
1298 nodes[id].prev = -1; |
|
1299 nodes[id].next = -1; |
|
1300 |
|
1301 nodes[id].left = -1; |
|
1302 nodes[id].right = -1; |
|
1303 |
|
1304 nodes[id].item = item; |
|
1305 index[item] = id; |
|
1306 |
|
1307 int class_id = newClass(); |
|
1308 classes[class_id].parent = ~id; |
|
1309 classes[class_id].depth = 0; |
|
1310 |
|
1311 classes[class_id].left = -1; |
|
1312 classes[class_id].right = -1; |
|
1313 |
|
1314 if (first_class != -1) { |
|
1315 classes[first_class].prev = class_id; |
|
1316 } |
|
1317 classes[class_id].next = first_class; |
|
1318 classes[class_id].prev = -1; |
|
1319 first_class = class_id; |
|
1320 |
|
1321 nodes[id].parent = ~class_id; |
|
1322 |
|
1323 return class_id; |
|
1324 } |
|
1325 |
|
1326 /// \brief The class of the item. |
|
1327 /// |
|
1328 /// \return The alive class id of the item, which is not nested into |
|
1329 /// other classes. |
|
1330 /// |
|
1331 /// The time complexity is O(log(n)). |
|
1332 int find(const Item& item) const { |
|
1333 return findClass(index[item]); |
|
1334 } |
|
1335 |
|
1336 /// \brief Joins the classes. |
|
1337 /// |
|
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) { |
|
1348 cs.push_back(*it); |
|
1349 } |
|
1350 |
|
1351 int class_id = newClass(); |
|
1352 { // creation union-find |
|
1353 |
|
1354 if (first_class != -1) { |
|
1355 classes[first_class].prev = class_id; |
|
1356 } |
|
1357 classes[class_id].next = first_class; |
|
1358 classes[class_id].prev = -1; |
|
1359 first_class = class_id; |
|
1360 |
|
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; |
|
1364 |
|
1365 int l = cs[0]; |
|
1366 |
|
1367 classes[class_id].left = l; |
|
1368 classes[class_id].right = l; |
|
1369 |
|
1370 if (classes[l].next != -1) { |
|
1371 classes[classes[l].next].prev = classes[l].prev; |
|
1372 } |
|
1373 classes[classes[l].prev].next = classes[l].next; |
|
1374 |
|
1375 classes[l].prev = -1; |
|
1376 classes[l].next = -1; |
|
1377 |
|
1378 classes[l].depth = leftNode(l); |
|
1379 classes[l].parent = class_id; |
|
1380 |
|
1381 } |
|
1382 |
|
1383 { // merging of heap |
|
1384 int l = class_id; |
|
1385 for (int ci = 1; ci < int(cs.size()); ++ci) { |
|
1386 int r = cs[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; |
|
1392 } |
|
1393 while (id >= 0 && nodes[id].size == cmax) { |
|
1394 int new_id = newNode(); |
|
1395 int right_id = nodes[id].right; |
|
1396 |
|
1397 popRight(id); |
|
1398 if (nodes[id].item == nodes[right_id].item) { |
|
1399 setPrio(id); |
|
1400 } |
|
1401 push(new_id, right_id); |
|
1402 pushRight(new_id, ~(classes[r].parent)); |
|
1403 setPrio(new_id); |
|
1404 |
|
1405 id = nodes[id].parent; |
|
1406 classes[r].parent = ~new_id; |
|
1407 } |
|
1408 if (id < 0) { |
|
1409 int new_parent = newNode(); |
|
1410 nodes[new_parent].next = -1; |
|
1411 nodes[new_parent].prev = -1; |
|
1412 nodes[new_parent].parent = ~l; |
|
1413 |
|
1414 push(new_parent, ~(classes[l].parent)); |
|
1415 pushRight(new_parent, ~(classes[r].parent)); |
|
1416 setPrio(new_parent); |
|
1417 |
|
1418 classes[l].parent = ~new_parent; |
|
1419 classes[l].depth += 1; |
|
1420 } else { |
|
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; |
|
1426 } |
|
1427 } |
|
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; |
|
1432 } |
|
1433 while (id >= 0 && nodes[id].size == cmax) { |
|
1434 int new_id = newNode(); |
|
1435 int left_id = nodes[id].left; |
|
1436 |
|
1437 popLeft(id); |
|
1438 if (nodes[id].prio == nodes[left_id].prio) { |
|
1439 setPrio(id); |
|
1440 } |
|
1441 push(new_id, left_id); |
|
1442 pushLeft(new_id, ~(classes[l].parent)); |
|
1443 setPrio(new_id); |
|
1444 |
|
1445 id = nodes[id].parent; |
|
1446 classes[l].parent = ~new_id; |
|
1447 |
|
1448 } |
|
1449 if (id < 0) { |
|
1450 int new_parent = newNode(); |
|
1451 nodes[new_parent].next = -1; |
|
1452 nodes[new_parent].prev = -1; |
|
1453 nodes[new_parent].parent = ~l; |
|
1454 |
|
1455 push(new_parent, ~(classes[r].parent)); |
|
1456 pushLeft(new_parent, ~(classes[l].parent)); |
|
1457 setPrio(new_parent); |
|
1458 |
|
1459 classes[r].parent = ~new_parent; |
|
1460 classes[r].depth += 1; |
|
1461 } else { |
|
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; |
|
1467 } |
|
1468 } |
|
1469 nodes[~(classes[r].parent)].parent = ~l; |
|
1470 classes[l].parent = classes[r].parent; |
|
1471 classes[l].depth = classes[r].depth; |
|
1472 } else { |
|
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; |
|
1483 } |
|
1484 } else { |
|
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); |
|
1490 |
|
1491 classes[l].parent = ~new_parent; |
|
1492 classes[l].depth += 1; |
|
1493 nodes[new_parent].parent = ~l; |
|
1494 } |
|
1495 } |
|
1496 if (classes[r].next != -1) { |
|
1497 classes[classes[r].next].prev = classes[r].prev; |
|
1498 } |
|
1499 classes[classes[r].prev].next = classes[r].next; |
|
1500 |
|
1501 classes[r].prev = classes[l].right; |
|
1502 classes[classes[l].right].next = r; |
|
1503 classes[l].right = r; |
|
1504 classes[r].parent = l; |
|
1505 |
|
1506 classes[r].next = -1; |
|
1507 classes[r].depth = rln; |
|
1508 } |
|
1509 } |
|
1510 return class_id; |
|
1511 } |
|
1512 |
|
1513 /// \brief Split the class to subclasses. |
|
1514 /// |
|
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 |
|
1522 /// classes. |
|
1523 template <typename Iterator> |
|
1524 void split(int cls, Iterator out) { |
|
1525 std::vector<int> cs; |
|
1526 { // splitting union-find |
|
1527 int id = cls; |
|
1528 int l = classes[id].left; |
|
1529 |
|
1530 classes[l].parent = classes[id].parent; |
|
1531 classes[l].depth = classes[id].depth; |
|
1532 |
|
1533 nodes[~(classes[l].parent)].parent = ~l; |
|
1534 |
|
1535 *out++ = l; |
|
1536 |
|
1537 while (l != -1) { |
|
1538 cs.push_back(l); |
|
1539 l = classes[l].next; |
|
1540 } |
|
1541 |
|
1542 classes[classes[id].right].next = first_class; |
|
1543 classes[first_class].prev = classes[id].right; |
|
1544 first_class = classes[id].left; |
|
1545 |
|
1546 if (classes[id].next != -1) { |
|
1547 classes[classes[id].next].prev = classes[id].prev; |
|
1548 } |
|
1549 classes[classes[id].prev].next = classes[id].next; |
|
1550 |
|
1551 deleteClass(id); |
|
1552 } |
|
1553 |
|
1554 { |
|
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; |
|
1559 } |
|
1560 int r = l; |
|
1561 while (nodes[l].parent >= 0) { |
|
1562 l = nodes[l].parent; |
|
1563 int new_node = newNode(); |
|
1564 |
|
1565 nodes[new_node].prev = -1; |
|
1566 nodes[new_node].next = -1; |
|
1567 |
|
1568 split(r, new_node); |
|
1569 pushAfter(l, new_node); |
|
1570 setPrio(l); |
|
1571 setPrio(new_node); |
|
1572 r = new_node; |
|
1573 } |
|
1574 classes[cs[i]].parent = ~r; |
|
1575 classes[cs[i]].depth = classes[~(nodes[l].parent)].depth; |
|
1576 nodes[r].parent = ~cs[i]; |
|
1577 |
|
1578 nodes[l].next = -1; |
|
1579 nodes[r].prev = -1; |
|
1580 |
|
1581 repairRight(~(nodes[l].parent)); |
|
1582 repairLeft(cs[i]); |
|
1583 |
|
1584 *out++ = cs[i]; |
|
1585 } |
|
1586 } |
|
1587 } |
|
1588 |
|
1589 /// \brief Gives back the priority of the current item. |
|
1590 /// |
|
1591 /// \return Gives back the priority of the current item. |
|
1592 const Value& operator[](const Item& item) const { |
|
1593 return nodes[index[item]].prio; |
|
1594 } |
|
1595 |
|
1596 /// \brief Sets the priority of the current item. |
|
1597 /// |
|
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); |
|
1604 } |
|
1605 } |
|
1606 |
|
1607 /// \brief Increase the priority of the current item. |
|
1608 /// |
|
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) { |
|
1615 setPrio(kd); |
|
1616 kd = nodes[kd].parent; |
|
1617 } |
|
1618 } |
|
1619 |
|
1620 /// \brief Increase the priority of the current item. |
|
1621 /// |
|
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; |
|
1631 } |
|
1632 } |
|
1633 |
|
1634 /// \brief Gives back the minimum priority of the class. |
|
1635 /// |
|
1636 /// \return Gives back the minimum priority of the class. |
|
1637 const Value& classPrio(int cls) const { |
|
1638 return nodes[~(classes[cls].parent)].prio; |
|
1639 } |
|
1640 |
|
1641 /// \brief Gives back the minimum priority item of the class. |
|
1642 /// |
|
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; |
|
1646 } |
|
1647 |
|
1648 /// \brief Gives back a representant item of the class. |
|
1649 /// |
|
1650 /// The representant is indpendent from the priorities of the |
|
1651 /// items. |
|
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; |
|
1656 } |
|
1657 |
|
1658 /// \brief Lemon style iterator for the items of a class. |
|
1659 /// |
|
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. |
|
1663 ///\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; |
|
1668 /// } |
|
1669 /// std::cout << std::endl; |
|
1670 /// } |
|
1671 ///\endcode |
|
1672 class ItemIt { |
|
1673 private: |
|
1674 |
|
1675 const HeapUnionFind* _huf; |
|
1676 int _id, _lid; |
|
1677 |
|
1678 public: |
|
1679 |
|
1680 /// \brief Default constructor |
|
1681 /// |
|
1682 /// Default constructor |
|
1683 ItemIt() {} |
|
1684 |
|
1685 ItemIt(const HeapUnionFind& huf, int cls) : _huf(&huf) { |
|
1686 int id = cls; |
|
1687 int parent = _huf->classes[id].parent; |
|
1688 if (parent >= 0) { |
|
1689 _id = _huf->classes[id].depth; |
|
1690 if (_huf->classes[id].next != -1) { |
|
1691 _lid = _huf->classes[_huf->classes[id].next].depth; |
|
1692 } else { |
|
1693 _lid = -1; |
|
1694 } |
|
1695 } else { |
|
1696 _id = _huf->leftNode(id); |
|
1697 _lid = -1; |
|
1698 } |
|
1699 } |
|
1700 |
|
1701 /// \brief Increment operator |
|
1702 /// |
|
1703 /// It steps to the next item in the class. |
|
1704 ItemIt& operator++() { |
|
1705 _id = _huf->nextNode(_id); |
|
1706 return *this; |
|
1707 } |
|
1708 |
|
1709 /// \brief Conversion operator |
|
1710 /// |
|
1711 /// It converts the iterator to the current item. |
|
1712 operator const Item&() const { |
|
1713 return _huf->nodes[_id].item; |
|
1714 } |
|
1715 |
|
1716 /// \brief Equality operator |
|
1717 /// |
|
1718 /// Equality operator |
|
1719 bool operator==(const ItemIt& i) { |
|
1720 return i._id == _id; |
|
1721 } |
|
1722 |
|
1723 /// \brief Inequality operator |
|
1724 /// |
|
1725 /// Inequality operator |
|
1726 bool operator!=(const ItemIt& i) { |
|
1727 return i._id != _id; |
|
1728 } |
|
1729 |
|
1730 /// \brief Equality operator |
|
1731 /// |
|
1732 /// Equality operator |
|
1733 bool operator==(Invalid) { |
|
1734 return _id == _lid; |
|
1735 } |
|
1736 |
|
1737 /// \brief Inequality operator |
|
1738 /// |
|
1739 /// Inequality operator |
|
1740 bool operator!=(Invalid) { |
|
1741 return _id != _lid; |
|
1742 } |
|
1743 |
|
1744 }; |
|
1745 |
|
1746 /// \brief Class iterator |
|
1747 /// |
|
1748 /// The iterator stores |
|
1749 class ClassIt { |
|
1750 private: |
|
1751 |
|
1752 const HeapUnionFind* _huf; |
|
1753 int _id; |
|
1754 |
|
1755 public: |
|
1756 |
|
1757 ClassIt(const HeapUnionFind& huf) |
|
1758 : _huf(&huf), _id(huf.first_class) {} |
|
1759 |
|
1760 ClassIt(const HeapUnionFind& huf, int cls) |
|
1761 : _huf(&huf), _id(huf.classes[cls].left) {} |
|
1762 |
|
1763 ClassIt(Invalid) : _huf(0), _id(-1) {} |
|
1764 |
|
1765 const ClassIt& operator++() { |
|
1766 _id = _huf->classes[_id].next; |
|
1767 return *this; |
|
1768 } |
|
1769 |
|
1770 /// \brief Equality operator |
|
1771 /// |
|
1772 /// Equality operator |
|
1773 bool operator==(const ClassIt& i) { |
|
1774 return i._id == _id; |
|
1775 } |
|
1776 |
|
1777 /// \brief Inequality operator |
|
1778 /// |
|
1779 /// Inequality operator |
|
1780 bool operator!=(const ClassIt& i) { |
|
1781 return i._id != _id; |
|
1782 } |
|
1783 |
|
1784 operator int() const { |
|
1785 return _id; |
|
1786 } |
|
1787 |
|
1788 }; |
|
1789 |
|
1790 }; |
|
1791 |
|
1792 //! @} |
|
1793 |
|
1794 } //namespace lemon |
|
1795 |
|
1796 #endif //LEMON_UNION_FIND_H |