| // 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/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 |