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