1 // Copyright 2004 The Trustees of Indiana University.
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)
7 // Authors: Douglas Gregor
9 #ifndef BOOST_RELAXED_HEAP_HEADER
10 #define BOOST_RELAXED_HEAP_HEADER
13 #include <boost/property_map/property_map.hpp>
14 #include <boost/optional.hpp>
16 #include <climits> // for CHAR_BIT
17 #include <boost/none.hpp>
19 #ifdef BOOST_RELAXED_HEAP_DEBUG
21 #endif // BOOST_RELAXED_HEAP_DEBUG
23 #if defined(BOOST_MSVC)
24 # pragma warning(push)
25 # pragma warning(disable:4355) // complaint about using 'this' to
26 #endif // initialize a member
30 template<typename IndexedType
,
31 typename Compare
= std::less
<IndexedType
>,
32 typename ID
= identity_property_map
>
37 typedef relaxed_heap self_type
;
38 typedef std::size_t rank_type
;
41 typedef IndexedType value_type
;
42 typedef rank_type size_type
;
46 * The kind of key that a group has. The actual values are discussed
47 * in-depth in the documentation of the @c kind field of the @c group
48 * structure. Note that the order of the enumerators *IS* important
49 * and must not be changed.
51 enum group_key_kind
{ smallest_key
, stored_key
, largest_key
};
54 explicit group(group_key_kind kind
= largest_key
)
55 : kind(kind
), parent(this), rank(0) { }
57 /** The value associated with this group. This value is only valid
58 * when @c kind!=largest_key (which indicates a deleted
59 * element). Note that the use of boost::optional increases the
60 * memory requirements slightly but does not result in extraneous
61 * memory allocations or deallocations. The optional could be
62 * eliminated when @c value_type is a model of
63 * DefaultConstructible.
65 ::boost::optional
<value_type
> value
;
68 * The kind of key stored at this group. This may be @c
69 * smallest_key, which indicates that the key is infinitely small;
70 * @c largest_key, which indicates that the key is infinitely
71 * large; or @c stored_key, which means that the key is unknown,
72 * but its relationship to other keys can be determined via the
73 * comparison function object.
77 /// The parent of this group. Will only be NULL for the dummy root group
80 /// The rank of this group. Equivalent to the number of children in
84 /** The children of this group. For the dummy root group, these are
85 * the roots. This is an array of length log n containing pointers
86 * to the child groups.
91 size_type
log_base_2(size_type n
) // log2 is a macro on some platforms
93 size_type leading_zeroes
= 0;
95 size_type next
= n
<< 1;
96 if (n
== (next
>> 1)) {
103 return sizeof(size_type
) * CHAR_BIT
- leading_zeroes
- 1;
107 relaxed_heap(size_type n
, const Compare
& compare
= Compare(),
109 : compare(compare
), id(id
), root(smallest_key
), groups(n
),
113 root
.children
= new group
*[1];
117 log_n
= log_base_2(n
);
118 if (log_n
== 0) log_n
= 1;
119 size_type g
= n
/ log_n
;
120 if (n
% log_n
> 0) ++g
;
121 size_type log_g
= log_base_2(g
);
124 // Reserve an appropriate amount of space for data structures, so
125 // that we do not need to expand them.
126 index_to_group
.resize(g
);
129 root
.children
= new group
*[(log_g
+ 1) * (g
+ 1)];
130 for (rank_type i
= 0; i
< r
+1; ++i
) root
.children
[i
] = 0;
132 // Build initial heap
135 root
.children
[r
] = &index_to_group
[idx
];
136 idx
= build_tree(root
, idx
, r
, log_g
+ 1);
138 r
= static_cast<size_type
>(log_base_2(g
-idx
));
142 ~relaxed_heap() { delete [] root
.children
; }
144 void push(const value_type
& x
)
146 groups
[get(id
, x
)] = x
;
150 void update(const value_type
& x
)
152 group
* a
= &index_to_group
[get(id
, x
) / log_n
];
155 || compare(x
, *a
->value
)) {
156 if (a
!= smallest_value
) smallest_value
= 0;
157 a
->kind
= stored_key
;
163 void remove(const value_type
& x
)
165 group
* a
= &index_to_group
[get(id
, x
) / log_n
];
166 assert(groups
[get(id
, x
)] != 0);
168 a
->kind
= smallest_key
;
177 assert(smallest_value
->value
!= none
);
178 return *smallest_value
->value
;
181 const value_type
& top() const
184 assert(smallest_value
->value
!= none
);
185 return *smallest_value
->value
;
191 return !smallest_value
|| (smallest_value
->kind
== largest_key
);
194 bool contains(const value_type
& x
) const { return groups
[get(id
, x
)]; }
198 // Fill in smallest_value. This is the group x.
200 group
* x
= smallest_value
;
203 // Make x a leaf, giving it the smallest value within its group
204 rank_type r
= x
->rank
;
205 group
* p
= x
->parent
;
207 assert(x
->value
!= none
);
210 size_type start
= get(id
, *x
->value
) - get(id
, *x
->value
) % log_n
;
211 size_type end
= start
+ log_n
;
212 if (end
> groups
.size()) end
= groups
.size();
214 // Remove the smallest value from the group, and find the new
216 groups
[get(id
, *x
->value
)].reset();
218 x
->kind
= largest_key
;
219 for (size_type i
= start
; i
< end
; ++i
) {
220 if (groups
[i
] && (!x
->value
|| compare(*groups
[i
], *x
->value
))) {
221 x
->kind
= stored_key
;
222 x
->value
= groups
[i
];
228 // Combine prior children of x with x
230 for (size_type c
= 0; c
< r
; ++c
) {
231 group
* child
= x
->children
[c
];
232 if (A
[c
] == child
) A
[c
] = 0;
233 y
= combine(y
, child
);
236 // If we got back something other than x, let y take x's place
241 assert(r
== y
->rank
);
243 A
[y
->rank
] = do_compare(y
, p
)? y
: 0;
247 #ifdef BOOST_RELAXED_HEAP_DEBUG
248 /*************************************************************************
249 * Debugging support *
250 *************************************************************************/
251 void dump_tree() { dump_tree(std::cout
); }
252 void dump_tree(std::ostream
& out
) { dump_tree(out
, &root
); }
254 void dump_tree(std::ostream
& out
, group
* p
, bool in_progress
= false)
257 out
<< "digraph heap {\n"
258 << " edge[dir=\"back\"];\n";
261 size_type p_index
= 0;
262 if (p
!= &root
) while (&index_to_group
[p_index
] != p
) ++p_index
;
264 for (size_type i
= 0; i
< p
->rank
; ++i
) {
265 group
* c
= p
->children
[i
];
267 size_type c_index
= 0;
268 if (c
!= &root
) while (&index_to_group
[c_index
] != c
) ++c_index
;
271 if (p
== &root
) out
<< 'p'; else out
<< p_index
;
273 if (c
== &root
) out
<< 'p'; else out
<< c_index
;
274 if (A
[c
->rank
] == c
) out
<< " [style=\"dotted\"]";
276 dump_tree(out
, c
, true);
278 // Emit node information
280 if (c
== &root
) out
<< 'p'; else out
<< c_index
;
282 if (c
== &root
) out
<< 'p'; else out
<< c_index
;
284 size_type start
= c_index
* log_n
;
285 size_type end
= start
+ log_n
;
286 if (end
> groups
.size()) end
= groups
.size();
287 while (start
!= end
) {
289 out
<< " " << get(id
, *groups
[start
]);
290 if (*groups
[start
] == *c
->value
) out
<< "(*)";
296 if (do_compare(c
, p
)) {
298 if (c
== &root
) out
<< 'p'; else out
<< c_index
;
299 out
<< ", style=\"filled\", fillcolor=\"gray\"";
303 assert(p
->parent
== p
);
306 if (!in_progress
) out
<< "}\n";
311 // Check that the ranks in the A array match the ranks of the
312 // groups stored there. Also, the active groups must be the last
313 // child of their parent.
314 for (size_type r
= 0; r
< A
.size(); ++r
) {
315 if (A
[r
] && A
[r
]->rank
!= r
) return false;
317 if (A
[r
] && A
[r
]->parent
->children
[A
[r
]->parent
->rank
-1] != A
[r
])
321 // The root must have no value and a key of -Infinity
322 if (root
.kind
!= smallest_key
) return false;
329 for (size_type i
= 0; i
< p
->rank
; ++i
) {
330 group
* c
= p
->children
[i
];
332 // Check link structure
333 if (c
->parent
!= p
) return false;
334 if (c
->rank
!= i
) return false;
336 // A bad group must be active
337 if (do_compare(c
, p
) && A
[i
] != c
) return false;
340 if (!valid(c
)) return false;
343 if (p
!= &root
) return false;
349 #endif // BOOST_RELAXED_HEAP_DEBUG
353 build_tree(group
& parent
, size_type idx
, size_type r
, size_type max_rank
)
355 group
& this_group
= index_to_group
[idx
];
356 this_group
.parent
= &parent
;
359 this_group
.children
= root
.children
+ (idx
* max_rank
);
361 for (size_type i
= 0; i
< r
; ++i
) {
362 this_group
.children
[i
] = &index_to_group
[idx
];
363 idx
= build_tree(this_group
, idx
, i
, max_rank
);
368 void find_smallest() const
370 group
** roots
= root
.children
;
372 if (!smallest_value
) {
374 for (i
= 0; i
< root
.rank
; ++i
) {
376 (!smallest_value
|| do_compare(roots
[i
], smallest_value
))) {
377 smallest_value
= roots
[i
];
380 for (i
= 0; i
< A
.size(); ++i
) {
381 if (A
[i
] && (!smallest_value
|| do_compare(A
[i
], smallest_value
)))
382 smallest_value
= A
[i
];
387 bool do_compare(group
* x
, group
* y
) const
389 return (x
->kind
< y
->kind
390 || (x
->kind
== y
->kind
391 && x
->kind
== stored_key
392 && compare(*x
->value
, *y
->value
)));
395 void promote(group
* a
)
398 rank_type r
= a
->rank
;
399 group
* p
= a
->parent
;
401 if (do_compare(a
, p
)) {
402 // s is the rank + 1 sibling
403 group
* s
= p
->rank
> r
+ 1? p
->children
[r
+ 1] : 0;
405 // If a is the last child of p
406 if (r
== p
->rank
- 1) {
408 else if (A
[r
] != a
) pair_transform(a
);
411 if (A
[r
+ 1] == s
) active_sibling_transform(a
, s
);
412 else good_sibling_transform(a
, s
);
417 group
* combine(group
* a1
, group
* a2
)
419 assert(a1
->rank
== a2
->rank
);
420 if (do_compare(a2
, a1
)) do_swap(a1
, a2
);
421 a1
->children
[a1
->rank
++] = a2
;
429 if (2 > q
->rank
) return;
430 group
* qp
= q
->children
[q
->rank
-1];
431 rank_type s
= q
->rank
- 2;
432 group
* x
= q
->children
[s
];
433 group
* xp
= qp
->children
[s
];
434 assert(s
== x
->rank
);
436 // If x is active, swap x and xp
445 void pair_transform(group
* a
)
447 #if defined(BOOST_RELAXED_HEAP_DEBUG) && BOOST_RELAXED_HEAP_DEBUG > 1
448 std::cerr
<< "- pair transform\n";
450 rank_type r
= a
->rank
;
453 group
* p
= a
->parent
;
456 // g is p's parent (a's grandparent)
457 group
* g
= p
->parent
;
468 // let a' have parent p'
469 group
* pp
= ap
->parent
;
472 // let a' have grandparent g'
473 group
* gp
= pp
->parent
;
476 // Remove a and a' from their parents
477 assert(ap
== pp
->children
[pp
->rank
-1]); // Guaranteed because ap is active
480 // Guaranteed by caller
481 assert(a
== p
->children
[p
->rank
-1]);
484 // Note: a, ap, p, pp all have rank r
485 if (do_compare(pp
, p
)) {
491 // Assuming k(p) <= k(p')
492 // make p' the rank r child of p
493 assert(r
== p
->rank
);
494 p
->children
[p
->rank
++] = pp
;
497 // Combine a, ap into a rank r+1 group c
498 group
* c
= combine(a
, ap
);
500 // make c the rank r+1 child of g'
501 assert(gp
->rank
> r
+1);
502 gp
->children
[r
+1] = c
;
505 #if defined(BOOST_RELAXED_HEAP_DEBUG) && BOOST_RELAXED_HEAP_DEBUG > 1
506 std::cerr
<< "After pair transform...\n";
510 if (A
[r
+1] == pp
) A
[r
+1] = c
;
514 void active_sibling_transform(group
* a
, group
* s
)
516 #if defined(BOOST_RELAXED_HEAP_DEBUG) && BOOST_RELAXED_HEAP_DEBUG > 1
517 std::cerr
<< "- active sibling transform\n";
519 group
* p
= a
->parent
;
520 group
* g
= p
->parent
;
522 // remove a, s from their parents
523 assert(s
->parent
== p
);
524 assert(p
->children
[p
->rank
-1] == s
);
526 assert(p
->children
[p
->rank
-1] == a
);
529 rank_type r
= a
->rank
;
532 group
* c
= combine(a
, s
);
534 // make c the rank r+2 child of g
535 assert(g
->children
[r
+2] == p
);
536 g
->children
[r
+2] = c
;
538 if (A
[r
+2] == p
) A
[r
+2] = c
;
542 void good_sibling_transform(group
* a
, group
* s
)
544 #if defined(BOOST_RELAXED_HEAP_DEBUG) && BOOST_RELAXED_HEAP_DEBUG > 1
545 std::cerr
<< "- good sibling transform\n";
547 rank_type r
= a
->rank
;
548 group
* c
= s
->children
[s
->rank
-1];
549 assert(c
->rank
== r
);
551 #if defined(BOOST_RELAXED_HEAP_DEBUG) && BOOST_RELAXED_HEAP_DEBUG > 1
552 std::cerr
<< "- good sibling pair transform\n";
555 group
* p
= a
->parent
;
557 // Remove c from its parent
560 // Make s the rank r child of p
564 // combine a, c and let the result by the rank r+1 child of p
565 assert(p
->rank
> r
+1);
566 group
* x
= combine(a
, c
);
568 p
->children
[r
+1] = x
;
570 if (A
[r
+1] == s
) A
[r
+1] = x
;
573 #if defined(BOOST_RELAXED_HEAP_DEBUG) && BOOST_RELAXED_HEAP_DEBUG > 1
574 dump_tree(std::cerr
);
576 // pair_transform(a);
579 group
* p
= a
->parent
;
589 static void do_swap(group
*& x
, group
*& y
)
596 /// Function object that compares two values in the heap
599 /// Mapping from values to indices in the range [0, n).
602 /** The root group of the queue. This group is special because it will
603 * never store a value, but it acts as a parent to all of the
604 * roots. Thus, its list of children is the list of roots.
608 /** Mapping from the group index of a value to the group associated
609 * with that value. If a value is not in the queue, then the "value"
610 * field will be empty.
612 std::vector
<group
> index_to_group
;
614 /** Flat data structure containing the values in each of the
615 * groups. It will be indexed via the id of the values. The groups
616 * are each log_n long, with the last group potentially being
619 std::vector
< ::boost::optional
<value_type
> > groups
;
621 /** The list of active groups, indexed by rank. When A[r] is null,
622 * there is no active group of rank r. Otherwise, A[r] is the active
625 std::vector
<group
*> A
;
627 /** The group containing the smallest value in the queue, which must
628 * be either a root or an active group. If this group is null, then we
629 * will need to search for this group when it is needed.
631 mutable group
* smallest_value
;
633 /// Cached value log_base_2(n)
638 } // end namespace boost
640 #if defined(BOOST_MSVC)
641 # pragma warning(pop)
644 #endif // BOOST_RELAXED_HEAP_HEADER