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