boost/pending/relaxed_heap.hpp
// Copyright 2004 The Trustees of Indiana University. // Use, modification and distribution is subject to the Boost Software // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at // http://www.boost.org/LICENSE_1_0.txt) // Authors: Douglas Gregor // Andrew Lumsdaine #ifndef BOOST_RELAXED_HEAP_HEADER #define BOOST_RELAXED_HEAP_HEADER #include <functional> #include <boost/property_map.hpp> #include <boost/optional.hpp> #include <vector> #include <climits> // for CHAR_BIT #include <boost/none.hpp> #ifdef BOOST_RELAXED_HEAP_DEBUG # include <iostream> #endif // BOOST_RELAXED_HEAP_DEBUG #if defined(BOOST_MSVC) # pragma warning(push) # pragma warning(disable:4355) // complaint about using 'this' to #endif // initialize a member namespace boost { template<typename IndexedType, typename Compare = std::less<IndexedType>, typename ID = identity_property_map> class relaxed_heap { struct group; typedef relaxed_heap self_type; typedef std::size_t rank_type; public: typedef IndexedType value_type; typedef rank_type size_type; private: /** * The kind of key that a group has. The actual values are discussed * in-depth in the documentation of the @c kind field of the @c group * structure. Note that the order of the enumerators *IS* important * and must not be changed. */ enum group_key_kind { smallest_key, stored_key, largest_key }; struct group { explicit group(group_key_kind kind = largest_key) : kind(kind), parent(this), rank(0) { } /** The value associated with this group. This value is only valid * when @c kind!=largest_key (which indicates a deleted * element). Note that the use of boost::optional increases the * memory requirements slightly but does not result in extraneous * memory allocations or deallocations. The optional could be * eliminated when @c value_type is a model of * DefaultConstructible. */ ::boost::optional<value_type> value; /** * The kind of key stored at this group. This may be @c * smallest_key, which indicates that the key is infinitely small; * @c largest_key, which indicates that the key is infinitely * large; or @c stored_key, which means that the key is unknown, * but its relationship to other keys can be determined via the * comparison function object. */ group_key_kind kind; /// The parent of this group. Will only be NULL for the dummy root group group* parent; /// The rank of this group. Equivalent to the number of children in /// the group. rank_type rank; /** The children of this group. For the dummy root group, these are * the roots. This is an array of length log n containing pointers * to the child groups. */ group** children; }; size_type log_base_2(size_type n) // log2 is a macro on some platforms { size_type leading_zeroes = 0; do { size_type next = n << 1; if (n == (next >> 1)) { ++leading_zeroes; n = next; } else { break; } } while (true); return sizeof(size_type) * CHAR_BIT - leading_zeroes - 1; } public: relaxed_heap(size_type n, const Compare& compare = Compare(), const ID& id = ID()) : compare(compare), id(id), root(smallest_key), groups(n), smallest_value(0) { if (n == 0) { root.children = new group*[1]; return; } log_n = log_base_2(n); if (log_n == 0) log_n = 1; size_type g = n / log_n; if (n % log_n > 0) ++g; size_type log_g = log_base_2(g); size_type r = log_g; // Reserve an appropriate amount of space for data structures, so // that we do not need to expand them. index_to_group.resize(g); A.resize(r + 1, 0); root.rank = r + 1; root.children = new group*[(log_g + 1) * (g + 1)]; for (rank_type i = 0; i < r+1; ++i) root.children[i] = 0; // Build initial heap size_type idx = 0; while (idx < g) { root.children[r] = &index_to_group[idx]; idx = build_tree(root, idx, r, log_g + 1); if (idx != g) r = static_cast<size_type>(log_base_2(g-idx)); } } ~relaxed_heap() { delete [] root.children; } void push(const value_type& x) { groups[get(id, x)] = x; update(x); } void update(const value_type& x) { group* a = &index_to_group[get(id, x) / log_n]; if (!a->value || *a->value == x || compare(x, *a->value)) { if (a != smallest_value) smallest_value = 0; a->kind = stored_key; a->value = x; promote(a); } } void remove(const value_type& x) { group* a = &index_to_group[get(id, x) / log_n]; assert(groups[get(id, x)] != 0); a->value = x; a->kind = smallest_key; promote(a); smallest_value = a; pop(); } value_type& top() { find_smallest(); assert(smallest_value->value != none); return *smallest_value->value; } const value_type& top() const { find_smallest(); assert(smallest_value->value != none); return *smallest_value->value; } bool empty() const { find_smallest(); return !smallest_value || (smallest_value->kind == largest_key); } bool contains(const value_type& x) const { return groups[get(id, x)]; } void pop() { // Fill in smallest_value. This is the group x. find_smallest(); group* x = smallest_value; smallest_value = 0; // Make x a leaf, giving it the smallest value within its group rank_type r = x->rank; group* p = x->parent; { assert(x->value != none); // Find x's group size_type start = get(id, *x->value) - get(id, *x->value) % log_n; size_type end = start + log_n; if (end > groups.size()) end = groups.size(); // Remove the smallest value from the group, and find the new // smallest value. groups[get(id, *x->value)].reset(); x->value.reset(); x->kind = largest_key; for (size_type i = start; i < end; ++i) { if (groups[i] && (!x->value || compare(*groups[i], *x->value))) { x->kind = stored_key; x->value = groups[i]; } } } x->rank = 0; // Combine prior children of x with x group* y = x; for (size_type c = 0; c < r; ++c) { group* child = x->children[c]; if (A[c] == child) A[c] = 0; y = combine(y, child); } // If we got back something other than x, let y take x's place if (y != x) { y->parent = p; p->children[r] = y; assert(r == y->rank); if (A[y->rank] == x) A[y->rank] = do_compare(y, p)? y : 0; } } #ifdef BOOST_RELAXED_HEAP_DEBUG /************************************************************************* * Debugging support * *************************************************************************/ void dump_tree() { dump_tree(std::cout); } void dump_tree(std::ostream& out) { dump_tree(out, &root); } void dump_tree(std::ostream& out, group* p, bool in_progress = false) { if (!in_progress) { out << "digraph heap {\n" << " edge[dir=\"back\"];\n"; } size_type p_index = 0; if (p != &root) while (&index_to_group[p_index] != p) ++p_index; for (size_type i = 0; i < p->rank; ++i) { group* c = p->children[i]; if (c) { size_type c_index = 0; if (c != &root) while (&index_to_group[c_index] != c) ++c_index; out << " "; if (p == &root) out << 'p'; else out << p_index; out << " -> "; if (c == &root) out << 'p'; else out << c_index; if (A[c->rank] == c) out << " [style=\"dotted\"]"; out << ";\n"; dump_tree(out, c, true); // Emit node information out << " "; if (c == &root) out << 'p'; else out << c_index; out << " [label=\""; if (c == &root) out << 'p'; else out << c_index; out << ":"; size_type start = c_index * log_n; size_type end = start + log_n; if (end > groups.size()) end = groups.size(); while (start != end) { if (groups[start]) { out << " " << get(id, *groups[start]); if (*groups[start] == *c->value) out << "(*)"; } ++start; } out << '"'; if (do_compare(c, p)) { out << " "; if (c == &root) out << 'p'; else out << c_index; out << ", style=\"filled\", fillcolor=\"gray\""; } out << "];\n"; } else { assert(p->parent == p); } } if (!in_progress) out << "}\n"; } bool valid() { // Check that the ranks in the A array match the ranks of the // groups stored there. Also, the active groups must be the last // child of their parent. for (size_type r = 0; r < A.size(); ++r) { if (A[r] && A[r]->rank != r) return false; if (A[r] && A[r]->parent->children[A[r]->parent->rank-1] != A[r]) return false; } // The root must have no value and a key of -Infinity if (root.kind != smallest_key) return false; return valid(&root); } bool valid(group* p) { for (size_type i = 0; i < p->rank; ++i) { group* c = p->children[i]; if (c) { // Check link structure if (c->parent != p) return false; if (c->rank != i) return false; // A bad group must be active if (do_compare(c, p) && A[i] != c) return false; // Check recursively if (!valid(c)) return false; } else { // Only the root may if (p != &root) return false; } } return true; } #endif // BOOST_RELAXED_HEAP_DEBUG private: size_type build_tree(group& parent, size_type idx, size_type r, size_type max_rank) { group& this_group = index_to_group[idx]; this_group.parent = &parent; ++idx; this_group.children = root.children + (idx * max_rank); this_group.rank = r; for (size_type i = 0; i < r; ++i) { this_group.children[i] = &index_to_group[idx]; idx = build_tree(this_group, idx, i, max_rank); } return idx; } void find_smallest() const { group** roots = root.children; if (!smallest_value) { std::size_t i; for (i = 0; i < root.rank; ++i) { if (roots[i] && (!smallest_value || do_compare(roots[i], smallest_value))) { smallest_value = roots[i]; } } for (i = 0; i < A.size(); ++i) { if (A[i] && (!smallest_value || do_compare(A[i], smallest_value))) smallest_value = A[i]; } } } bool do_compare(group* x, group* y) const { return (x->kind < y->kind || (x->kind == y->kind && x->kind == stored_key && compare(*x->value, *y->value))); } void promote(group* a) { assert(a != 0); rank_type r = a->rank; group* p = a->parent; assert(p != 0); if (do_compare(a, p)) { // s is the rank + 1 sibling group* s = p->rank > r + 1? p->children[r + 1] : 0; // If a is the last child of p if (r == p->rank - 1) { if (!A[r]) A[r] = a; else if (A[r] != a) pair_transform(a); } else { assert(s != 0); if (A[r + 1] == s) active_sibling_transform(a, s); else good_sibling_transform(a, s); } } } group* combine(group* a1, group* a2) { assert(a1->rank == a2->rank); if (do_compare(a2, a1)) do_swap(a1, a2); a1->children[a1->rank++] = a2; a2->parent = a1; clean(a1); return a1; } void clean(group* q) { if (2 > q->rank) return; group* qp = q->children[q->rank-1]; rank_type s = q->rank - 2; group* x = q->children[s]; group* xp = qp->children[s]; assert(s == x->rank); // If x is active, swap x and xp if (A[s] == x) { q->children[s] = xp; xp->parent = q; qp->children[s] = x; x->parent = qp; } } void pair_transform(group* a) { #if defined(BOOST_RELAXED_HEAP_DEBUG) && BOOST_RELAXED_HEAP_DEBUG > 1 std::cerr << "- pair transform\n"; #endif rank_type r = a->rank; // p is a's parent group* p = a->parent; assert(p != 0); // g is p's parent (a's grandparent) group* g = p->parent; assert(g != 0); // a' <- A(r) assert(A[r] != 0); group* ap = A[r]; assert(ap != 0); // A(r) <- nil A[r] = 0; // let a' have parent p' group* pp = ap->parent; assert(pp != 0); // let a' have grandparent g' group* gp = pp->parent; assert(gp != 0); // Remove a and a' from their parents assert(ap == pp->children[pp->rank-1]); // Guaranteed because ap is active --pp->rank; // Guaranteed by caller assert(a == p->children[p->rank-1]); --p->rank; // Note: a, ap, p, pp all have rank r if (do_compare(pp, p)) { do_swap(a, ap); do_swap(p, pp); do_swap(g, gp); } // Assuming k(p) <= k(p') // make p' the rank r child of p assert(r == p->rank); p->children[p->rank++] = pp; pp->parent = p; // Combine a, ap into a rank r+1 group c group* c = combine(a, ap); // make c the rank r+1 child of g' assert(gp->rank > r+1); gp->children[r+1] = c; c->parent = gp; #if defined(BOOST_RELAXED_HEAP_DEBUG) && BOOST_RELAXED_HEAP_DEBUG > 1 std::cerr << "After pair transform...\n"; dump_tree(); #endif if (A[r+1] == pp) A[r+1] = c; else promote(c); } void active_sibling_transform(group* a, group* s) { #if defined(BOOST_RELAXED_HEAP_DEBUG) && BOOST_RELAXED_HEAP_DEBUG > 1 std::cerr << "- active sibling transform\n"; #endif group* p = a->parent; group* g = p->parent; // remove a, s from their parents assert(s->parent == p); assert(p->children[p->rank-1] == s); --p->rank; assert(p->children[p->rank-1] == a); --p->rank; rank_type r = a->rank; A[r+1] = 0; a = combine(p, a); group* c = combine(a, s); // make c the rank r+2 child of g assert(g->children[r+2] == p); g->children[r+2] = c; c->parent = g; if (A[r+2] == p) A[r+2] = c; else promote(c); } void good_sibling_transform(group* a, group* s) { #if defined(BOOST_RELAXED_HEAP_DEBUG) && BOOST_RELAXED_HEAP_DEBUG > 1 std::cerr << "- good sibling transform\n"; #endif rank_type r = a->rank; group* c = s->children[s->rank-1]; assert(c->rank == r); if (A[r] == c) { #if defined(BOOST_RELAXED_HEAP_DEBUG) && BOOST_RELAXED_HEAP_DEBUG > 1 std::cerr << "- good sibling pair transform\n"; #endif A[r] = 0; group* p = a->parent; // Remove c from its parent --s->rank; // Make s the rank r child of p s->parent = p; p->children[r] = s; // combine a, c and let the result by the rank r+1 child of p assert(p->rank > r+1); group* x = combine(a, c); x->parent = p; p->children[r+1] = x; if (A[r+1] == s) A[r+1] = x; else promote(x); #if defined(BOOST_RELAXED_HEAP_DEBUG) && BOOST_RELAXED_HEAP_DEBUG > 1 dump_tree(std::cerr); #endif // pair_transform(a); } else { // Clean operation group* p = a->parent; s->children[r] = a; a->parent = s; p->children[r] = c; c->parent = p; promote(a); } } static void do_swap(group*& x, group*& y) { group* tmp = x; x = y; y = tmp; } /// Function object that compares two values in the heap Compare compare; /// Mapping from values to indices in the range [0, n). ID id; /** The root group of the queue. This group is special because it will * never store a value, but it acts as a parent to all of the * roots. Thus, its list of children is the list of roots. */ group root; /** Mapping from the group index of a value to the group associated * with that value. If a value is not in the queue, then the "value" * field will be empty. */ std::vector<group> index_to_group; /** Flat data structure containing the values in each of the * groups. It will be indexed via the id of the values. The groups * are each log_n long, with the last group potentially being * smaller. */ std::vector< ::boost::optional<value_type> > groups; /** The list of active groups, indexed by rank. When A[r] is null, * there is no active group of rank r. Otherwise, A[r] is the active * group of rank r. */ std::vector<group*> A; /** The group containing the smallest value in the queue, which must * be either a root or an active group. If this group is null, then we * will need to search for this group when it is needed. */ mutable group* smallest_value; /// Cached value log_base_2(n) size_type log_n; }; } // end namespace boost #if defined(BOOST_MSVC) # pragma warning(pop) #endif #endif // BOOST_RELAXED_HEAP_HEADER