1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/epoc32/include/stdapis/boost/pending/relaxed_heap.hpp Tue Mar 16 16:12:26 2010 +0000
1.3 @@ -0,0 +1,642 @@
1.4 +// Copyright 2004 The Trustees of Indiana University.
1.5 +
1.6 +// Use, modification and distribution is subject to the Boost Software
1.7 +// License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
1.8 +// http://www.boost.org/LICENSE_1_0.txt)
1.9 +
1.10 +// Authors: Douglas Gregor
1.11 +// Andrew Lumsdaine
1.12 +#ifndef BOOST_RELAXED_HEAP_HEADER
1.13 +#define BOOST_RELAXED_HEAP_HEADER
1.14 +
1.15 +#include <functional>
1.16 +#include <boost/property_map.hpp>
1.17 +#include <boost/optional.hpp>
1.18 +#include <vector>
1.19 +
1.20 +#ifdef BOOST_RELAXED_HEAP_DEBUG
1.21 +# include <iostream>
1.22 +#endif // BOOST_RELAXED_HEAP_DEBUG
1.23 +
1.24 +#if defined(BOOST_MSVC)
1.25 +# pragma warning(push)
1.26 +# pragma warning(disable:4355) // complaint about using 'this' to
1.27 +#endif // initialize a member
1.28 +
1.29 +namespace boost {
1.30 +
1.31 +template<typename IndexedType,
1.32 + typename Compare = std::less<IndexedType>,
1.33 + typename ID = identity_property_map>
1.34 +class relaxed_heap
1.35 +{
1.36 + struct group;
1.37 +
1.38 + typedef relaxed_heap self_type;
1.39 + typedef std::size_t rank_type;
1.40 +
1.41 +public:
1.42 + typedef IndexedType value_type;
1.43 + typedef rank_type size_type;
1.44 +
1.45 +private:
1.46 + /**
1.47 + * The kind of key that a group has. The actual values are discussed
1.48 + * in-depth in the documentation of the @c kind field of the @c group
1.49 + * structure. Note that the order of the enumerators *IS* important
1.50 + * and must not be changed.
1.51 + */
1.52 + enum group_key_kind { smallest_key, stored_key, largest_key };
1.53 +
1.54 + struct group {
1.55 + explicit group(group_key_kind kind = largest_key)
1.56 + : kind(kind), parent(this), rank(0) { }
1.57 +
1.58 + /** The value associated with this group. This value is only valid
1.59 + * when @c kind!=largest_key (which indicates a deleted
1.60 + * element). Note that the use of boost::optional increases the
1.61 + * memory requirements slightly but does not result in extraneous
1.62 + * memory allocations or deallocations. The optional could be
1.63 + * eliminated when @c value_type is a model of
1.64 + * DefaultConstructible.
1.65 + */
1.66 + ::boost::optional<value_type> value;
1.67 +
1.68 + /**
1.69 + * The kind of key stored at this group. This may be @c
1.70 + * smallest_key, which indicates that the key is infinitely small;
1.71 + * @c largest_key, which indicates that the key is infinitely
1.72 + * large; or @c stored_key, which means that the key is unknown,
1.73 + * but its relationship to other keys can be determined via the
1.74 + * comparison function object.
1.75 + */
1.76 + group_key_kind kind;
1.77 +
1.78 + /// The parent of this group. Will only be NULL for the dummy root group
1.79 + group* parent;
1.80 +
1.81 + /// The rank of this group. Equivalent to the number of children in
1.82 + /// the group.
1.83 + rank_type rank;
1.84 +
1.85 + /** The children of this group. For the dummy root group, these are
1.86 + * the roots. This is an array of length log n containing pointers
1.87 + * to the child groups.
1.88 + */
1.89 + group** children;
1.90 + };
1.91 +
1.92 + size_type log_base_2(size_type n) // log2 is a macro on some platforms
1.93 + {
1.94 + size_type leading_zeroes = 0;
1.95 + do {
1.96 + size_type next = n << 1;
1.97 + if (n == (next >> 1)) {
1.98 + ++leading_zeroes;
1.99 + n = next;
1.100 + } else {
1.101 + break;
1.102 + }
1.103 + } while (true);
1.104 + return sizeof(size_type) * CHAR_BIT - leading_zeroes - 1;
1.105 + }
1.106 +
1.107 +public:
1.108 + relaxed_heap(size_type n, const Compare& compare = Compare(),
1.109 + const ID& id = ID())
1.110 + : compare(compare), id(id), root(smallest_key), groups(n),
1.111 + smallest_value(0)
1.112 + {
1.113 + if (n == 0) {
1.114 + root.children = new group*[1];
1.115 + return;
1.116 + }
1.117 +
1.118 + log_n = log_base_2(n);
1.119 + if (log_n == 0) log_n = 1;
1.120 + size_type g = n / log_n;
1.121 + if (n % log_n > 0) ++g;
1.122 + size_type log_g = log_base_2(g);
1.123 + size_type r = log_g;
1.124 +
1.125 + // Reserve an appropriate amount of space for data structures, so
1.126 + // that we do not need to expand them.
1.127 + index_to_group.resize(g);
1.128 + A.resize(r + 1, 0);
1.129 + root.rank = r + 1;
1.130 + root.children = new group*[(log_g + 1) * (g + 1)];
1.131 + for (rank_type i = 0; i < r+1; ++i) root.children[i] = 0;
1.132 +
1.133 + // Build initial heap
1.134 + size_type idx = 0;
1.135 + while (idx < g) {
1.136 + root.children[r] = &index_to_group[idx];
1.137 + idx = build_tree(root, idx, r, log_g + 1);
1.138 + if (idx != g)
1.139 + r = static_cast<size_type>(log_base_2(g-idx));
1.140 + }
1.141 + }
1.142 +
1.143 + ~relaxed_heap() { delete [] root.children; }
1.144 +
1.145 + void push(const value_type& x)
1.146 + {
1.147 + groups[get(id, x)] = x;
1.148 + update(x);
1.149 + }
1.150 +
1.151 + void update(const value_type& x)
1.152 + {
1.153 + group* a = &index_to_group[get(id, x) / log_n];
1.154 + if (!a->value
1.155 + || *a->value == x
1.156 + || compare(x, *a->value)) {
1.157 + if (a != smallest_value) smallest_value = 0;
1.158 + a->kind = stored_key;
1.159 + a->value = x;
1.160 + promote(a);
1.161 + }
1.162 + }
1.163 +
1.164 + void remove(const value_type& x)
1.165 + {
1.166 + group* a = &index_to_group[get(id, x) / log_n];
1.167 + assert(groups[get(id, x)] != 0);
1.168 + a->value = x;
1.169 + a->kind = smallest_key;
1.170 + promote(a);
1.171 + smallest_value = a;
1.172 + pop();
1.173 + }
1.174 +
1.175 + value_type& top()
1.176 + {
1.177 + find_smallest();
1.178 + assert(smallest_value->value != 0);
1.179 + return *smallest_value->value;
1.180 + }
1.181 +
1.182 + const value_type& top() const
1.183 + {
1.184 + find_smallest();
1.185 + assert(smallest_value->value != 0);
1.186 + return *smallest_value->value;
1.187 + }
1.188 +
1.189 + bool empty() const
1.190 + {
1.191 + find_smallest();
1.192 + return !smallest_value || (smallest_value->kind == largest_key);
1.193 + }
1.194 +
1.195 + bool contains(const value_type& x) const { return groups[get(id, x)]; }
1.196 +
1.197 + void pop()
1.198 + {
1.199 + // Fill in smallest_value. This is the group x.
1.200 + find_smallest();
1.201 + group* x = smallest_value;
1.202 + smallest_value = 0;
1.203 +
1.204 + // Make x a leaf, giving it the smallest value within its group
1.205 + rank_type r = x->rank;
1.206 + group* p = x->parent;
1.207 + {
1.208 + assert(x->value != 0);
1.209 +
1.210 + // Find x's group
1.211 + size_type start = get(id, *x->value) - get(id, *x->value) % log_n;
1.212 + size_type end = start + log_n;
1.213 + if (end > groups.size()) end = groups.size();
1.214 +
1.215 + // Remove the smallest value from the group, and find the new
1.216 + // smallest value.
1.217 + groups[get(id, *x->value)].reset();
1.218 + x->value.reset();
1.219 + x->kind = largest_key;
1.220 + for (size_type i = start; i < end; ++i) {
1.221 + if (groups[i] && (!x->value || compare(*groups[i], *x->value))) {
1.222 + x->kind = stored_key;
1.223 + x->value = groups[i];
1.224 + }
1.225 + }
1.226 + }
1.227 + x->rank = 0;
1.228 +
1.229 + // Combine prior children of x with x
1.230 + group* y = x;
1.231 + for (size_type c = 0; c < r; ++c) {
1.232 + group* child = x->children[c];
1.233 + if (A[c] == child) A[c] = 0;
1.234 + y = combine(y, child);
1.235 + }
1.236 +
1.237 + // If we got back something other than x, let y take x's place
1.238 + if (y != x) {
1.239 + y->parent = p;
1.240 + p->children[r] = y;
1.241 +
1.242 + assert(r == y->rank);
1.243 + if (A[y->rank] == x)
1.244 + A[y->rank] = do_compare(y, p)? y : 0;
1.245 + }
1.246 + }
1.247 +
1.248 +#ifdef BOOST_RELAXED_HEAP_DEBUG
1.249 + /*************************************************************************
1.250 + * Debugging support *
1.251 + *************************************************************************/
1.252 + void dump_tree() { dump_tree(std::cout); }
1.253 + void dump_tree(std::ostream& out) { dump_tree(out, &root); }
1.254 +
1.255 + void dump_tree(std::ostream& out, group* p, bool in_progress = false)
1.256 + {
1.257 + if (!in_progress) {
1.258 + out << "digraph heap {\n"
1.259 + << " edge[dir=\"back\"];\n";
1.260 + }
1.261 +
1.262 + size_type p_index = 0;
1.263 + if (p != &root) while (&index_to_group[p_index] != p) ++p_index;
1.264 +
1.265 + for (size_type i = 0; i < p->rank; ++i) {
1.266 + group* c = p->children[i];
1.267 + if (c) {
1.268 + size_type c_index = 0;
1.269 + if (c != &root) while (&index_to_group[c_index] != c) ++c_index;
1.270 +
1.271 + out << " ";
1.272 + if (p == &root) out << 'p'; else out << p_index;
1.273 + out << " -> ";
1.274 + if (c == &root) out << 'p'; else out << c_index;
1.275 + if (A[c->rank] == c) out << " [style=\"dotted\"]";
1.276 + out << ";\n";
1.277 + dump_tree(out, c, true);
1.278 +
1.279 + // Emit node information
1.280 + out << " ";
1.281 + if (c == &root) out << 'p'; else out << c_index;
1.282 + out << " [label=\"";
1.283 + if (c == &root) out << 'p'; else out << c_index;
1.284 + out << ":";
1.285 + size_type start = c_index * log_n;
1.286 + size_type end = start + log_n;
1.287 + if (end > groups.size()) end = groups.size();
1.288 + while (start != end) {
1.289 + if (groups[start]) {
1.290 + out << " " << get(id, *groups[start]);
1.291 + if (*groups[start] == *c->value) out << "(*)";
1.292 + }
1.293 + ++start;
1.294 + }
1.295 + out << '"';
1.296 +
1.297 + if (do_compare(c, p)) {
1.298 + out << " ";
1.299 + if (c == &root) out << 'p'; else out << c_index;
1.300 + out << ", style=\"filled\", fillcolor=\"gray\"";
1.301 + }
1.302 + out << "];\n";
1.303 + } else {
1.304 + assert(p->parent == p);
1.305 + }
1.306 + }
1.307 + if (!in_progress) out << "}\n";
1.308 + }
1.309 +
1.310 + bool valid()
1.311 + {
1.312 + // Check that the ranks in the A array match the ranks of the
1.313 + // groups stored there. Also, the active groups must be the last
1.314 + // child of their parent.
1.315 + for (size_type r = 0; r < A.size(); ++r) {
1.316 + if (A[r] && A[r]->rank != r) return false;
1.317 +
1.318 + if (A[r] && A[r]->parent->children[A[r]->parent->rank-1] != A[r])
1.319 + return false;
1.320 + }
1.321 +
1.322 + // The root must have no value and a key of -Infinity
1.323 + if (root.kind != smallest_key) return false;
1.324 +
1.325 + return valid(&root);
1.326 + }
1.327 +
1.328 + bool valid(group* p)
1.329 + {
1.330 + for (size_type i = 0; i < p->rank; ++i) {
1.331 + group* c = p->children[i];
1.332 + if (c) {
1.333 + // Check link structure
1.334 + if (c->parent != p) return false;
1.335 + if (c->rank != i) return false;
1.336 +
1.337 + // A bad group must be active
1.338 + if (do_compare(c, p) && A[i] != c) return false;
1.339 +
1.340 + // Check recursively
1.341 + if (!valid(c)) return false;
1.342 + } else {
1.343 + // Only the root may
1.344 + if (p != &root) return false;
1.345 + }
1.346 + }
1.347 + return true;
1.348 + }
1.349 +
1.350 +#endif // BOOST_RELAXED_HEAP_DEBUG
1.351 +
1.352 +private:
1.353 + size_type
1.354 + build_tree(group& parent, size_type idx, size_type r, size_type max_rank)
1.355 + {
1.356 + group& this_group = index_to_group[idx];
1.357 + this_group.parent = &parent;
1.358 + ++idx;
1.359 +
1.360 + this_group.children = root.children + (idx * max_rank);
1.361 + this_group.rank = r;
1.362 + for (size_type i = 0; i < r; ++i) {
1.363 + this_group.children[i] = &index_to_group[idx];
1.364 + idx = build_tree(this_group, idx, i, max_rank);
1.365 + }
1.366 + return idx;
1.367 + }
1.368 +
1.369 + void find_smallest() const
1.370 + {
1.371 + group** roots = root.children;
1.372 +
1.373 + if (!smallest_value) {
1.374 + std::size_t i;
1.375 + for (i = 0; i < root.rank; ++i) {
1.376 + if (roots[i] &&
1.377 + (!smallest_value || do_compare(roots[i], smallest_value))) {
1.378 + smallest_value = roots[i];
1.379 + }
1.380 + }
1.381 + for (i = 0; i < A.size(); ++i) {
1.382 + if (A[i] && (!smallest_value || do_compare(A[i], smallest_value)))
1.383 + smallest_value = A[i];
1.384 + }
1.385 + }
1.386 + }
1.387 +
1.388 + bool do_compare(group* x, group* y) const
1.389 + {
1.390 + return (x->kind < y->kind
1.391 + || (x->kind == y->kind
1.392 + && x->kind == stored_key
1.393 + && compare(*x->value, *y->value)));
1.394 + }
1.395 +
1.396 + void promote(group* a)
1.397 + {
1.398 + assert(a != 0);
1.399 + rank_type r = a->rank;
1.400 + group* p = a->parent;
1.401 + assert(p != 0);
1.402 + if (do_compare(a, p)) {
1.403 + // s is the rank + 1 sibling
1.404 + group* s = p->rank > r + 1? p->children[r + 1] : 0;
1.405 +
1.406 + // If a is the last child of p
1.407 + if (r == p->rank - 1) {
1.408 + if (!A[r]) A[r] = a;
1.409 + else if (A[r] != a) pair_transform(a);
1.410 + } else {
1.411 + assert(s != 0);
1.412 + if (A[r + 1] == s) active_sibling_transform(a, s);
1.413 + else good_sibling_transform(a, s);
1.414 + }
1.415 + }
1.416 + }
1.417 +
1.418 + group* combine(group* a1, group* a2)
1.419 + {
1.420 + assert(a1->rank == a2->rank);
1.421 + if (do_compare(a2, a1)) do_swap(a1, a2);
1.422 + a1->children[a1->rank++] = a2;
1.423 + a2->parent = a1;
1.424 + clean(a1);
1.425 + return a1;
1.426 + }
1.427 +
1.428 + void clean(group* q)
1.429 + {
1.430 + if (2 > q->rank) return;
1.431 + group* qp = q->children[q->rank-1];
1.432 + rank_type s = q->rank - 2;
1.433 + group* x = q->children[s];
1.434 + group* xp = qp->children[s];
1.435 + assert(s == x->rank);
1.436 +
1.437 + // If x is active, swap x and xp
1.438 + if (A[s] == x) {
1.439 + q->children[s] = xp;
1.440 + xp->parent = q;
1.441 + qp->children[s] = x;
1.442 + x->parent = qp;
1.443 + }
1.444 + }
1.445 +
1.446 + void pair_transform(group* a)
1.447 + {
1.448 +#if defined(BOOST_RELAXED_HEAP_DEBUG) && BOOST_RELAXED_HEAP_DEBUG > 1
1.449 + std::cerr << "- pair transform\n";
1.450 +#endif
1.451 + rank_type r = a->rank;
1.452 +
1.453 + // p is a's parent
1.454 + group* p = a->parent;
1.455 + assert(p != 0);
1.456 +
1.457 + // g is p's parent (a's grandparent)
1.458 + group* g = p->parent;
1.459 + assert(g != 0);
1.460 +
1.461 + // a' <- A(r)
1.462 + assert(A[r] != 0);
1.463 + group* ap = A[r];
1.464 + assert(ap != 0);
1.465 +
1.466 + // A(r) <- nil
1.467 + A[r] = 0;
1.468 +
1.469 + // let a' have parent p'
1.470 + group* pp = ap->parent;
1.471 + assert(pp != 0);
1.472 +
1.473 + // let a' have grandparent g'
1.474 + group* gp = pp->parent;
1.475 + assert(gp != 0);
1.476 +
1.477 + // Remove a and a' from their parents
1.478 + assert(ap == pp->children[pp->rank-1]); // Guaranteed because ap is active
1.479 + --pp->rank;
1.480 +
1.481 + // Guaranteed by caller
1.482 + assert(a == p->children[p->rank-1]);
1.483 + --p->rank;
1.484 +
1.485 + // Note: a, ap, p, pp all have rank r
1.486 + if (do_compare(pp, p)) {
1.487 + do_swap(a, ap);
1.488 + do_swap(p, pp);
1.489 + do_swap(g, gp);
1.490 + }
1.491 +
1.492 + // Assuming k(p) <= k(p')
1.493 + // make p' the rank r child of p
1.494 + assert(r == p->rank);
1.495 + p->children[p->rank++] = pp;
1.496 + pp->parent = p;
1.497 +
1.498 + // Combine a, ap into a rank r+1 group c
1.499 + group* c = combine(a, ap);
1.500 +
1.501 + // make c the rank r+1 child of g'
1.502 + assert(gp->rank > r+1);
1.503 + gp->children[r+1] = c;
1.504 + c->parent = gp;
1.505 +
1.506 +#if defined(BOOST_RELAXED_HEAP_DEBUG) && BOOST_RELAXED_HEAP_DEBUG > 1
1.507 + std::cerr << "After pair transform...\n";
1.508 + dump_tree();
1.509 +#endif
1.510 +
1.511 + if (A[r+1] == pp) A[r+1] = c;
1.512 + else promote(c);
1.513 + }
1.514 +
1.515 + void active_sibling_transform(group* a, group* s)
1.516 + {
1.517 +#if defined(BOOST_RELAXED_HEAP_DEBUG) && BOOST_RELAXED_HEAP_DEBUG > 1
1.518 + std::cerr << "- active sibling transform\n";
1.519 +#endif
1.520 + group* p = a->parent;
1.521 + group* g = p->parent;
1.522 +
1.523 + // remove a, s from their parents
1.524 + assert(s->parent == p);
1.525 + assert(p->children[p->rank-1] == s);
1.526 + --p->rank;
1.527 + assert(p->children[p->rank-1] == a);
1.528 + --p->rank;
1.529 +
1.530 + rank_type r = a->rank;
1.531 + A[r+1] = 0;
1.532 + a = combine(p, a);
1.533 + group* c = combine(a, s);
1.534 +
1.535 + // make c the rank r+2 child of g
1.536 + assert(g->children[r+2] == p);
1.537 + g->children[r+2] = c;
1.538 + c->parent = g;
1.539 + if (A[r+2] == p) A[r+2] = c;
1.540 + else promote(c);
1.541 + }
1.542 +
1.543 + void good_sibling_transform(group* a, group* s)
1.544 + {
1.545 +#if defined(BOOST_RELAXED_HEAP_DEBUG) && BOOST_RELAXED_HEAP_DEBUG > 1
1.546 + std::cerr << "- good sibling transform\n";
1.547 +#endif
1.548 + rank_type r = a->rank;
1.549 + group* c = s->children[s->rank-1];
1.550 + assert(c->rank == r);
1.551 + if (A[r] == c) {
1.552 +#if defined(BOOST_RELAXED_HEAP_DEBUG) && BOOST_RELAXED_HEAP_DEBUG > 1
1.553 + std::cerr << "- good sibling pair transform\n";
1.554 +#endif
1.555 + A[r] = 0;
1.556 + group* p = a->parent;
1.557 +
1.558 + // Remove c from its parent
1.559 + --s->rank;
1.560 +
1.561 + // Make s the rank r child of p
1.562 + s->parent = p;
1.563 + p->children[r] = s;
1.564 +
1.565 + // combine a, c and let the result by the rank r+1 child of p
1.566 + assert(p->rank > r+1);
1.567 + group* x = combine(a, c);
1.568 + x->parent = p;
1.569 + p->children[r+1] = x;
1.570 +
1.571 + if (A[r+1] == s) A[r+1] = x;
1.572 + else promote(x);
1.573 +
1.574 +#if defined(BOOST_RELAXED_HEAP_DEBUG) && BOOST_RELAXED_HEAP_DEBUG > 1
1.575 + dump_tree(std::cerr);
1.576 +#endif
1.577 + // pair_transform(a);
1.578 + } else {
1.579 + // Clean operation
1.580 + group* p = a->parent;
1.581 + s->children[r] = a;
1.582 + a->parent = s;
1.583 + p->children[r] = c;
1.584 + c->parent = p;
1.585 +
1.586 + promote(a);
1.587 + }
1.588 + }
1.589 +
1.590 + static void do_swap(group*& x, group*& y)
1.591 + {
1.592 + group* tmp = x;
1.593 + x = y;
1.594 + y = tmp;
1.595 + }
1.596 +
1.597 + /// Function object that compares two values in the heap
1.598 + Compare compare;
1.599 +
1.600 + /// Mapping from values to indices in the range [0, n).
1.601 + ID id;
1.602 +
1.603 + /** The root group of the queue. This group is special because it will
1.604 + * never store a value, but it acts as a parent to all of the
1.605 + * roots. Thus, its list of children is the list of roots.
1.606 + */
1.607 + group root;
1.608 +
1.609 + /** Mapping from the group index of a value to the group associated
1.610 + * with that value. If a value is not in the queue, then the "value"
1.611 + * field will be empty.
1.612 + */
1.613 + std::vector<group> index_to_group;
1.614 +
1.615 + /** Flat data structure containing the values in each of the
1.616 + * groups. It will be indexed via the id of the values. The groups
1.617 + * are each log_n long, with the last group potentially being
1.618 + * smaller.
1.619 + */
1.620 + std::vector< ::boost::optional<value_type> > groups;
1.621 +
1.622 + /** The list of active groups, indexed by rank. When A[r] is null,
1.623 + * there is no active group of rank r. Otherwise, A[r] is the active
1.624 + * group of rank r.
1.625 + */
1.626 + std::vector<group*> A;
1.627 +
1.628 + /** The group containing the smallest value in the queue, which must
1.629 + * be either a root or an active group. If this group is null, then we
1.630 + * will need to search for this group when it is needed.
1.631 + */
1.632 + mutable group* smallest_value;
1.633 +
1.634 + /// Cached value log_base_2(n)
1.635 + size_type log_n;
1.636 +};
1.637 +
1.638 +
1.639 +} // end namespace boost
1.640 +
1.641 +#if defined(BOOST_MSVC)
1.642 +# pragma warning(pop)
1.643 +#endif
1.644 +
1.645 +#endif // BOOST_RELAXED_HEAP_HEADER