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