]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | // Copyright 2004 The Trustees of Indiana University. |
2 | ||
3 | // Use, modification and distribution is subject to the Boost Software | |
4 | // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at | |
5 | // http://www.boost.org/LICENSE_1_0.txt) | |
6 | ||
7 | // Authors: Douglas Gregor | |
8 | // Andrew Lumsdaine | |
1e59de90 | 9 | |
7c673cae FG |
10 | #ifndef BOOST_RELAXED_HEAP_HEADER |
11 | #define BOOST_RELAXED_HEAP_HEADER | |
12 | ||
92f5a8d4 TL |
13 | #include <boost/config/header_deprecated.hpp> |
14 | BOOST_HEADER_DEPRECATED("the standard heap functions") | |
15 | ||
7c673cae FG |
16 | #include <functional> |
17 | #include <boost/property_map/property_map.hpp> | |
18 | #include <boost/optional.hpp> | |
19 | #include <vector> | |
20 | #include <climits> // for CHAR_BIT | |
21 | #include <boost/none.hpp> | |
22 | ||
23 | #ifdef BOOST_RELAXED_HEAP_DEBUG | |
f67539c2 | 24 | #include <iostream> |
7c673cae FG |
25 | #endif // BOOST_RELAXED_HEAP_DEBUG |
26 | ||
27 | #if defined(BOOST_MSVC) | |
f67539c2 TL |
28 | #pragma warning(push) |
29 | #pragma warning(disable : 4355) // complaint about using 'this' to | |
30 | #endif // initialize a member | |
7c673cae | 31 | |
f67539c2 TL |
32 | namespace boost |
33 | { | |
7c673cae | 34 | |
f67539c2 TL |
35 | template < typename IndexedType, typename Compare = std::less< IndexedType >, |
36 | typename ID = identity_property_map > | |
7c673cae FG |
37 | class relaxed_heap |
38 | { | |
f67539c2 | 39 | struct group; |
7c673cae | 40 | |
f67539c2 TL |
41 | typedef relaxed_heap self_type; |
42 | typedef std::size_t rank_type; | |
7c673cae FG |
43 | |
44 | public: | |
f67539c2 TL |
45 | typedef IndexedType value_type; |
46 | typedef rank_type size_type; | |
7c673cae FG |
47 | |
48 | private: | |
7c673cae | 49 | /** |
f67539c2 TL |
50 | * The kind of key that a group has. The actual values are discussed |
51 | * in-depth in the documentation of the @c kind field of the @c group | |
52 | * structure. Note that the order of the enumerators *IS* important | |
53 | * and must not be changed. | |
7c673cae | 54 | */ |
f67539c2 TL |
55 | enum group_key_kind |
56 | { | |
57 | smallest_key, | |
58 | stored_key, | |
59 | largest_key | |
60 | }; | |
7c673cae | 61 | |
f67539c2 TL |
62 | struct group |
63 | { | |
64 | explicit group(group_key_kind kind = largest_key) | |
65 | : kind(kind), parent(this), rank(0) | |
66 | { | |
67 | } | |
7c673cae | 68 | |
f67539c2 TL |
69 | /** The value associated with this group. This value is only valid |
70 | * when @c kind!=largest_key (which indicates a deleted | |
71 | * element). Note that the use of boost::optional increases the | |
72 | * memory requirements slightly but does not result in extraneous | |
73 | * memory allocations or deallocations. The optional could be | |
74 | * eliminated when @c value_type is a model of | |
75 | * DefaultConstructible. | |
76 | */ | |
77 | ::boost::optional< value_type > value; | |
78 | ||
79 | /** | |
80 | * The kind of key stored at this group. This may be @c | |
81 | * smallest_key, which indicates that the key is infinitely small; | |
82 | * @c largest_key, which indicates that the key is infinitely | |
83 | * large; or @c stored_key, which means that the key is unknown, | |
84 | * but its relationship to other keys can be determined via the | |
85 | * comparison function object. | |
86 | */ | |
87 | group_key_kind kind; | |
88 | ||
89 | /// The parent of this group. Will only be NULL for the dummy root group | |
90 | group* parent; | |
91 | ||
92 | /// The rank of this group. Equivalent to the number of children in | |
93 | /// the group. | |
94 | rank_type rank; | |
95 | ||
96 | /** The children of this group. For the dummy root group, these are | |
97 | * the roots. This is an array of length log n containing pointers | |
98 | * to the child groups. | |
99 | */ | |
100 | group** children; | |
101 | }; | |
102 | ||
103 | size_type log_base_2(size_type n) // log2 is a macro on some platforms | |
104 | { | |
105 | size_type leading_zeroes = 0; | |
106 | do | |
107 | { | |
108 | size_type next = n << 1; | |
109 | if (n == (next >> 1)) | |
110 | { | |
111 | ++leading_zeroes; | |
112 | n = next; | |
113 | } | |
114 | else | |
115 | { | |
116 | break; | |
117 | } | |
118 | } while (true); | |
119 | return sizeof(size_type) * CHAR_BIT - leading_zeroes - 1; | |
120 | } | |
7c673cae FG |
121 | |
122 | public: | |
f67539c2 TL |
123 | relaxed_heap( |
124 | size_type n, const Compare& compare = Compare(), const ID& id = ID()) | |
125 | : compare(compare), id(id), root(smallest_key), groups(n), smallest_value(0) | |
126 | { | |
127 | if (n == 0) | |
128 | { | |
129 | root.children = new group*[1]; | |
130 | return; | |
131 | } | |
7c673cae | 132 | |
f67539c2 TL |
133 | log_n = log_base_2(n); |
134 | if (log_n == 0) | |
135 | log_n = 1; | |
136 | size_type g = n / log_n; | |
137 | if (n % log_n > 0) | |
138 | ++g; | |
139 | size_type log_g = log_base_2(g); | |
140 | size_type r = log_g; | |
141 | ||
142 | // Reserve an appropriate amount of space for data structures, so | |
143 | // that we do not need to expand them. | |
144 | index_to_group.resize(g); | |
145 | A.resize(r + 1, 0); | |
146 | root.rank = r + 1; | |
147 | root.children = new group*[(log_g + 1) * (g + 1)]; | |
148 | for (rank_type i = 0; i < r + 1; ++i) | |
149 | root.children[i] = 0; | |
150 | ||
151 | // Build initial heap | |
152 | size_type idx = 0; | |
153 | while (idx < g) | |
154 | { | |
155 | root.children[r] = &index_to_group[idx]; | |
156 | idx = build_tree(root, idx, r, log_g + 1); | |
157 | if (idx != g) | |
158 | r = static_cast< size_type >(log_base_2(g - idx)); | |
159 | } | |
7c673cae | 160 | } |
f67539c2 TL |
161 | |
162 | ~relaxed_heap() { delete[] root.children; } | |
163 | ||
164 | void push(const value_type& x) | |
165 | { | |
166 | groups[get(id, x)] = x; | |
167 | update(x); | |
7c673cae | 168 | } |
f67539c2 TL |
169 | |
170 | void update(const value_type& x) | |
7c673cae | 171 | { |
f67539c2 TL |
172 | group* a = &index_to_group[get(id, x) / log_n]; |
173 | if (!a->value || *a->value == x || compare(x, *a->value)) | |
174 | { | |
175 | if (a != smallest_value) | |
176 | smallest_value = 0; | |
177 | a->kind = stored_key; | |
178 | a->value = x; | |
179 | promote(a); | |
7c673cae | 180 | } |
7c673cae | 181 | } |
f67539c2 TL |
182 | |
183 | void remove(const value_type& x) | |
184 | { | |
185 | group* a = &index_to_group[get(id, x) / log_n]; | |
186 | assert(groups[get(id, x)]); | |
187 | a->value = x; | |
188 | a->kind = smallest_key; | |
189 | promote(a); | |
190 | smallest_value = a; | |
191 | pop(); | |
7c673cae FG |
192 | } |
193 | ||
f67539c2 TL |
194 | value_type& top() |
195 | { | |
196 | find_smallest(); | |
197 | assert(smallest_value->value != none); | |
198 | return *smallest_value->value; | |
199 | } | |
7c673cae | 200 | |
f67539c2 TL |
201 | const value_type& top() const |
202 | { | |
203 | find_smallest(); | |
204 | assert(smallest_value->value != none); | |
205 | return *smallest_value->value; | |
7c673cae | 206 | } |
7c673cae | 207 | |
f67539c2 TL |
208 | bool empty() const |
209 | { | |
210 | find_smallest(); | |
211 | return !smallest_value || (smallest_value->kind == largest_key); | |
7c673cae FG |
212 | } |
213 | ||
f67539c2 TL |
214 | bool contains(const value_type& x) const |
215 | { | |
216 | return static_cast< bool >(groups[get(id, x)]); | |
217 | } | |
218 | ||
219 | void pop() | |
220 | { | |
221 | // Fill in smallest_value. This is the group x. | |
222 | find_smallest(); | |
223 | group* x = smallest_value; | |
224 | smallest_value = 0; | |
225 | ||
226 | // Make x a leaf, giving it the smallest value within its group | |
227 | rank_type r = x->rank; | |
228 | group* p = x->parent; | |
229 | { | |
230 | assert(x->value != none); | |
231 | ||
232 | // Find x's group | |
233 | size_type start = get(id, *x->value) - get(id, *x->value) % log_n; | |
234 | size_type end = start + log_n; | |
235 | if (end > groups.size()) | |
236 | end = groups.size(); | |
237 | ||
238 | // Remove the smallest value from the group, and find the new | |
239 | // smallest value. | |
240 | groups[get(id, *x->value)].reset(); | |
241 | x->value.reset(); | |
242 | x->kind = largest_key; | |
243 | for (size_type i = start; i < end; ++i) | |
244 | { | |
245 | if (groups[i] && (!x->value || compare(*groups[i], *x->value))) | |
246 | { | |
247 | x->kind = stored_key; | |
248 | x->value = groups[i]; | |
249 | } | |
250 | } | |
251 | } | |
252 | x->rank = 0; | |
253 | ||
254 | // Combine prior children of x with x | |
255 | group* y = x; | |
256 | for (size_type c = 0; c < r; ++c) | |
257 | { | |
258 | group* child = x->children[c]; | |
259 | if (A[c] == child) | |
260 | A[c] = 0; | |
261 | y = combine(y, child); | |
7c673cae | 262 | } |
7c673cae | 263 | |
f67539c2 TL |
264 | // If we got back something other than x, let y take x's place |
265 | if (y != x) | |
266 | { | |
267 | y->parent = p; | |
268 | p->children[r] = y; | |
269 | ||
270 | assert(r == y->rank); | |
271 | if (A[y->rank] == x) | |
272 | A[y->rank] = do_compare(y, p) ? y : 0; | |
7c673cae | 273 | } |
7c673cae FG |
274 | } |
275 | ||
f67539c2 TL |
276 | #ifdef BOOST_RELAXED_HEAP_DEBUG |
277 | /************************************************************************* | |
278 | * Debugging support * | |
279 | *************************************************************************/ | |
280 | void dump_tree() { dump_tree(std::cout); } | |
281 | void dump_tree(std::ostream& out) { dump_tree(out, &root); } | |
7c673cae | 282 | |
f67539c2 TL |
283 | void dump_tree(std::ostream& out, group* p, bool in_progress = false) |
284 | { | |
285 | if (!in_progress) | |
286 | { | |
287 | out << "digraph heap {\n" | |
288 | << " edge[dir=\"back\"];\n"; | |
289 | } | |
7c673cae | 290 | |
f67539c2 TL |
291 | size_type p_index = 0; |
292 | if (p != &root) | |
293 | while (&index_to_group[p_index] != p) | |
294 | ++p_index; | |
295 | ||
296 | for (size_type i = 0; i < p->rank; ++i) | |
297 | { | |
298 | group* c = p->children[i]; | |
299 | if (c) | |
300 | { | |
301 | size_type c_index = 0; | |
302 | if (c != &root) | |
303 | while (&index_to_group[c_index] != c) | |
304 | ++c_index; | |
305 | ||
306 | out << " "; | |
307 | if (p == &root) | |
308 | out << 'p'; | |
309 | else | |
310 | out << p_index; | |
311 | out << " -> "; | |
312 | if (c == &root) | |
313 | out << 'p'; | |
314 | else | |
315 | out << c_index; | |
316 | if (A[c->rank] == c) | |
317 | out << " [style=\"dotted\"]"; | |
318 | out << ";\n"; | |
319 | dump_tree(out, c, true); | |
320 | ||
321 | // Emit node information | |
322 | out << " "; | |
323 | if (c == &root) | |
324 | out << 'p'; | |
325 | else | |
326 | out << c_index; | |
327 | out << " [label=\""; | |
328 | if (c == &root) | |
329 | out << 'p'; | |
330 | else | |
331 | out << c_index; | |
332 | out << ":"; | |
333 | size_type start = c_index * log_n; | |
334 | size_type end = start + log_n; | |
335 | if (end > groups.size()) | |
336 | end = groups.size(); | |
337 | while (start != end) | |
338 | { | |
339 | if (groups[start]) | |
340 | { | |
341 | out << " " << get(id, *groups[start]); | |
342 | if (*groups[start] == *c->value) | |
343 | out << "(*)"; | |
344 | } | |
345 | ++start; | |
346 | } | |
347 | out << '"'; | |
348 | ||
349 | if (do_compare(c, p)) | |
350 | { | |
351 | out << " "; | |
352 | if (c == &root) | |
353 | out << 'p'; | |
354 | else | |
355 | out << c_index; | |
356 | out << ", style=\"filled\", fillcolor=\"gray\""; | |
357 | } | |
358 | out << "];\n"; | |
359 | } | |
360 | else | |
361 | { | |
362 | assert(p->parent == p); | |
363 | } | |
7c673cae | 364 | } |
f67539c2 TL |
365 | if (!in_progress) |
366 | out << "}\n"; | |
7c673cae | 367 | } |
7c673cae | 368 | |
f67539c2 TL |
369 | bool valid() |
370 | { | |
371 | // Check that the ranks in the A array match the ranks of the | |
372 | // groups stored there. Also, the active groups must be the last | |
373 | // child of their parent. | |
374 | for (size_type r = 0; r < A.size(); ++r) | |
375 | { | |
376 | if (A[r] && A[r]->rank != r) | |
377 | return false; | |
378 | ||
379 | if (A[r] && A[r]->parent->children[A[r]->parent->rank - 1] != A[r]) | |
380 | return false; | |
381 | } | |
7c673cae | 382 | |
f67539c2 TL |
383 | // The root must have no value and a key of -Infinity |
384 | if (root.kind != smallest_key) | |
385 | return false; | |
7c673cae | 386 | |
f67539c2 TL |
387 | return valid(&root); |
388 | } | |
7c673cae | 389 | |
f67539c2 TL |
390 | bool valid(group* p) |
391 | { | |
392 | for (size_type i = 0; i < p->rank; ++i) | |
393 | { | |
394 | group* c = p->children[i]; | |
395 | if (c) | |
396 | { | |
397 | // Check link structure | |
398 | if (c->parent != p) | |
399 | return false; | |
400 | if (c->rank != i) | |
401 | return false; | |
402 | ||
403 | // A bad group must be active | |
404 | if (do_compare(c, p) && A[i] != c) | |
405 | return false; | |
406 | ||
407 | // Check recursively | |
408 | if (!valid(c)) | |
409 | return false; | |
410 | } | |
411 | else | |
412 | { | |
413 | // Only the root may | |
414 | if (p != &root) | |
415 | return false; | |
416 | } | |
417 | } | |
418 | return true; | |
419 | } | |
7c673cae | 420 | |
f67539c2 | 421 | #endif // BOOST_RELAXED_HEAP_DEBUG |
7c673cae | 422 | |
f67539c2 TL |
423 | private: |
424 | size_type build_tree( | |
425 | group& parent, size_type idx, size_type r, size_type max_rank) | |
426 | { | |
427 | group& this_group = index_to_group[idx]; | |
428 | this_group.parent = &parent; | |
429 | ++idx; | |
430 | ||
431 | this_group.children = root.children + (idx * max_rank); | |
432 | this_group.rank = r; | |
433 | for (size_type i = 0; i < r; ++i) | |
434 | { | |
435 | this_group.children[i] = &index_to_group[idx]; | |
436 | idx = build_tree(this_group, idx, i, max_rank); | |
437 | } | |
438 | return idx; | |
439 | } | |
7c673cae | 440 | |
f67539c2 TL |
441 | void find_smallest() const |
442 | { | |
443 | group** roots = root.children; | |
444 | ||
445 | if (!smallest_value) | |
446 | { | |
447 | std::size_t i; | |
448 | for (i = 0; i < root.rank; ++i) | |
449 | { | |
450 | if (roots[i] | |
451 | && (!smallest_value | |
452 | || do_compare(roots[i], smallest_value))) | |
453 | { | |
454 | smallest_value = roots[i]; | |
455 | } | |
456 | } | |
457 | for (i = 0; i < A.size(); ++i) | |
458 | { | |
459 | if (A[i] | |
460 | && (!smallest_value || do_compare(A[i], smallest_value))) | |
461 | smallest_value = A[i]; | |
462 | } | |
463 | } | |
464 | } | |
7c673cae | 465 | |
f67539c2 TL |
466 | bool do_compare(group* x, group* y) const |
467 | { | |
468 | return (x->kind < y->kind | |
469 | || (x->kind == y->kind && x->kind == stored_key | |
470 | && compare(*x->value, *y->value))); | |
471 | } | |
7c673cae | 472 | |
f67539c2 TL |
473 | void promote(group* a) |
474 | { | |
475 | assert(a != 0); | |
476 | rank_type r = a->rank; | |
477 | group* p = a->parent; | |
478 | assert(p != 0); | |
479 | if (do_compare(a, p)) | |
480 | { | |
481 | // s is the rank + 1 sibling | |
482 | group* s = p->rank > r + 1 ? p->children[r + 1] : 0; | |
483 | ||
484 | // If a is the last child of p | |
485 | if (r == p->rank - 1) | |
486 | { | |
487 | if (!A[r]) | |
488 | A[r] = a; | |
489 | else if (A[r] != a) | |
490 | pair_transform(a); | |
491 | } | |
492 | else | |
493 | { | |
494 | assert(s != 0); | |
495 | if (A[r + 1] == s) | |
496 | active_sibling_transform(a, s); | |
497 | else | |
498 | good_sibling_transform(a, s); | |
499 | } | |
500 | } | |
501 | } | |
7c673cae | 502 | |
f67539c2 TL |
503 | group* combine(group* a1, group* a2) |
504 | { | |
505 | assert(a1->rank == a2->rank); | |
506 | if (do_compare(a2, a1)) | |
507 | do_swap(a1, a2); | |
508 | a1->children[a1->rank++] = a2; | |
509 | a2->parent = a1; | |
510 | clean(a1); | |
511 | return a1; | |
512 | } | |
7c673cae | 513 | |
f67539c2 TL |
514 | void clean(group* q) |
515 | { | |
516 | if (2 > q->rank) | |
517 | return; | |
518 | group* qp = q->children[q->rank - 1]; | |
519 | rank_type s = q->rank - 2; | |
520 | group* x = q->children[s]; | |
521 | group* xp = qp->children[s]; | |
522 | assert(s == x->rank); | |
523 | ||
524 | // If x is active, swap x and xp | |
525 | if (A[s] == x) | |
526 | { | |
527 | q->children[s] = xp; | |
528 | xp->parent = q; | |
529 | qp->children[s] = x; | |
530 | x->parent = qp; | |
531 | } | |
7c673cae FG |
532 | } |
533 | ||
f67539c2 TL |
534 | void pair_transform(group* a) |
535 | { | |
536 | #if defined(BOOST_RELAXED_HEAP_DEBUG) && BOOST_RELAXED_HEAP_DEBUG > 1 | |
537 | std::cerr << "- pair transform\n"; | |
538 | #endif | |
539 | rank_type r = a->rank; | |
540 | ||
541 | // p is a's parent | |
542 | group* p = a->parent; | |
543 | assert(p != 0); | |
544 | ||
545 | // g is p's parent (a's grandparent) | |
546 | group* g = p->parent; | |
547 | assert(g != 0); | |
548 | ||
549 | // a' <- A(r) | |
550 | assert(A[r] != 0); | |
551 | group* ap = A[r]; | |
552 | assert(ap != 0); | |
553 | ||
554 | // A(r) <- nil | |
555 | A[r] = 0; | |
556 | ||
557 | // let a' have parent p' | |
558 | group* pp = ap->parent; | |
559 | assert(pp != 0); | |
560 | ||
561 | // let a' have grandparent g' | |
562 | group* gp = pp->parent; | |
563 | assert(gp != 0); | |
564 | ||
565 | // Remove a and a' from their parents | |
566 | assert(ap | |
567 | == pp->children[pp->rank - 1]); // Guaranteed because ap is active | |
568 | --pp->rank; | |
569 | ||
570 | // Guaranteed by caller | |
571 | assert(a == p->children[p->rank - 1]); | |
572 | --p->rank; | |
573 | ||
574 | // Note: a, ap, p, pp all have rank r | |
575 | if (do_compare(pp, p)) | |
576 | { | |
577 | do_swap(a, ap); | |
578 | do_swap(p, pp); | |
579 | do_swap(g, gp); | |
580 | } | |
581 | ||
582 | // Assuming k(p) <= k(p') | |
583 | // make p' the rank r child of p | |
584 | assert(r == p->rank); | |
585 | p->children[p->rank++] = pp; | |
586 | pp->parent = p; | |
7c673cae | 587 | |
f67539c2 TL |
588 | // Combine a, ap into a rank r+1 group c |
589 | group* c = combine(a, ap); | |
7c673cae | 590 | |
f67539c2 TL |
591 | // make c the rank r+1 child of g' |
592 | assert(gp->rank > r + 1); | |
593 | gp->children[r + 1] = c; | |
594 | c->parent = gp; | |
7c673cae FG |
595 | |
596 | #if defined(BOOST_RELAXED_HEAP_DEBUG) && BOOST_RELAXED_HEAP_DEBUG > 1 | |
f67539c2 TL |
597 | std::cerr << "After pair transform...\n"; |
598 | dump_tree(); | |
7c673cae FG |
599 | #endif |
600 | ||
f67539c2 TL |
601 | if (A[r + 1] == pp) |
602 | A[r + 1] = c; | |
603 | else | |
604 | promote(c); | |
605 | } | |
7c673cae | 606 | |
f67539c2 TL |
607 | void active_sibling_transform(group* a, group* s) |
608 | { | |
7c673cae | 609 | #if defined(BOOST_RELAXED_HEAP_DEBUG) && BOOST_RELAXED_HEAP_DEBUG > 1 |
f67539c2 | 610 | std::cerr << "- active sibling transform\n"; |
7c673cae | 611 | #endif |
f67539c2 TL |
612 | group* p = a->parent; |
613 | group* g = p->parent; | |
614 | ||
615 | // remove a, s from their parents | |
616 | assert(s->parent == p); | |
617 | assert(p->children[p->rank - 1] == s); | |
618 | --p->rank; | |
619 | assert(p->children[p->rank - 1] == a); | |
620 | --p->rank; | |
621 | ||
622 | rank_type r = a->rank; | |
623 | A[r + 1] = 0; | |
624 | a = combine(p, a); | |
625 | group* c = combine(a, s); | |
626 | ||
627 | // make c the rank r+2 child of g | |
628 | assert(g->children[r + 2] == p); | |
629 | g->children[r + 2] = c; | |
630 | c->parent = g; | |
631 | if (A[r + 2] == p) | |
632 | A[r + 2] = c; | |
633 | else | |
634 | promote(c); | |
635 | } | |
636 | ||
637 | void good_sibling_transform(group* a, group* s) | |
638 | { | |
7c673cae | 639 | #if defined(BOOST_RELAXED_HEAP_DEBUG) && BOOST_RELAXED_HEAP_DEBUG > 1 |
f67539c2 | 640 | std::cerr << "- good sibling transform\n"; |
7c673cae | 641 | #endif |
f67539c2 TL |
642 | rank_type r = a->rank; |
643 | group* c = s->children[s->rank - 1]; | |
644 | assert(c->rank == r); | |
645 | if (A[r] == c) | |
646 | { | |
7c673cae | 647 | #if defined(BOOST_RELAXED_HEAP_DEBUG) && BOOST_RELAXED_HEAP_DEBUG > 1 |
f67539c2 | 648 | std::cerr << "- good sibling pair transform\n"; |
7c673cae | 649 | #endif |
f67539c2 TL |
650 | A[r] = 0; |
651 | group* p = a->parent; | |
7c673cae | 652 | |
f67539c2 TL |
653 | // Remove c from its parent |
654 | --s->rank; | |
7c673cae | 655 | |
f67539c2 TL |
656 | // Make s the rank r child of p |
657 | s->parent = p; | |
658 | p->children[r] = s; | |
7c673cae | 659 | |
f67539c2 TL |
660 | // combine a, c and let the result by the rank r+1 child of p |
661 | assert(p->rank > r + 1); | |
662 | group* x = combine(a, c); | |
663 | x->parent = p; | |
664 | p->children[r + 1] = x; | |
7c673cae | 665 | |
f67539c2 TL |
666 | if (A[r + 1] == s) |
667 | A[r + 1] = x; | |
668 | else | |
669 | promote(x); | |
7c673cae FG |
670 | |
671 | #if defined(BOOST_RELAXED_HEAP_DEBUG) && BOOST_RELAXED_HEAP_DEBUG > 1 | |
f67539c2 | 672 | dump_tree(std::cerr); |
7c673cae | 673 | #endif |
f67539c2 TL |
674 | // pair_transform(a); |
675 | } | |
676 | else | |
677 | { | |
678 | // Clean operation | |
679 | group* p = a->parent; | |
680 | s->children[r] = a; | |
681 | a->parent = s; | |
682 | p->children[r] = c; | |
683 | c->parent = p; | |
684 | ||
685 | promote(a); | |
686 | } | |
7c673cae | 687 | } |
7c673cae | 688 | |
f67539c2 TL |
689 | static void do_swap(group*& x, group*& y) |
690 | { | |
691 | group* tmp = x; | |
692 | x = y; | |
693 | y = tmp; | |
694 | } | |
695 | ||
696 | /// Function object that compares two values in the heap | |
697 | Compare compare; | |
698 | ||
699 | /// Mapping from values to indices in the range [0, n). | |
700 | ID id; | |
701 | ||
702 | /** The root group of the queue. This group is special because it will | |
703 | * never store a value, but it acts as a parent to all of the | |
704 | * roots. Thus, its list of children is the list of roots. | |
705 | */ | |
706 | group root; | |
707 | ||
708 | /** Mapping from the group index of a value to the group associated | |
709 | * with that value. If a value is not in the queue, then the "value" | |
710 | * field will be empty. | |
711 | */ | |
712 | std::vector< group > index_to_group; | |
713 | ||
714 | /** Flat data structure containing the values in each of the | |
715 | * groups. It will be indexed via the id of the values. The groups | |
716 | * are each log_n long, with the last group potentially being | |
717 | * smaller. | |
718 | */ | |
719 | std::vector< ::boost::optional< value_type > > groups; | |
720 | ||
721 | /** The list of active groups, indexed by rank. When A[r] is null, | |
722 | * there is no active group of rank r. Otherwise, A[r] is the active | |
723 | * group of rank r. | |
724 | */ | |
725 | std::vector< group* > A; | |
726 | ||
727 | /** The group containing the smallest value in the queue, which must | |
728 | * be either a root or an active group. If this group is null, then we | |
729 | * will need to search for this group when it is needed. | |
730 | */ | |
731 | mutable group* smallest_value; | |
732 | ||
733 | /// Cached value log_base_2(n) | |
734 | size_type log_n; | |
735 | }; | |
7c673cae FG |
736 | |
737 | } // end namespace boost | |
738 | ||
739 | #if defined(BOOST_MSVC) | |
f67539c2 | 740 | #pragma warning(pop) |
7c673cae FG |
741 | #endif |
742 | ||
743 | #endif // BOOST_RELAXED_HEAP_HEADER |