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