1 // Copyright 2004 The Trustees of Indiana University.

     2 

     3 // Use, modification and distribution is subject to the Boost Software

     4 // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at

     5 // http://www.boost.org/LICENSE_1_0.txt)

     6 

     7 //  Authors: Douglas Gregor

     8 //           Andrew Lumsdaine

     9 #ifndef BOOST_RELAXED_HEAP_HEADER

    10 #define BOOST_RELAXED_HEAP_HEADER

    11 

    12 #include <functional>

    13 #include <boost/property_map.hpp>

    14 #include <boost/optional.hpp>

    15 #include <vector>

    16 

    17 #ifdef BOOST_RELAXED_HEAP_DEBUG

    18 #  include <iostream>

    19 #endif // BOOST_RELAXED_HEAP_DEBUG

    20 

    21 #if defined(BOOST_MSVC)

    22 #  pragma warning(push)

    23 #  pragma warning(disable:4355) // complaint about using 'this' to

    24 #endif                          // initialize a member

    25 

    26 namespace boost {

    27 

    28 template<typename IndexedType,

    29          typename Compare = std::less<IndexedType>,

    30          typename ID = identity_property_map>

    31 class relaxed_heap

    32 {

    33   struct group;

    34 

    35   typedef relaxed_heap self_type;

    36   typedef std::size_t  rank_type;

    37 

    38 public:

    39   typedef IndexedType  value_type;

    40   typedef rank_type    size_type;

    41 

    42 private:

    43   /**

    44    * The kind of key that a group has. The actual values are discussed

    45    * in-depth in the documentation of the @c kind field of the @c group

    46    * structure. Note that the order of the enumerators *IS* important

    47    * and must not be changed.

    48    */

    49   enum group_key_kind { smallest_key, stored_key, largest_key };

    50 

    51   struct group {

    52     explicit group(group_key_kind kind = largest_key)

    53       : kind(kind), parent(this), rank(0) { }

    54 

    55     /** The value associated with this group. This value is only valid

    56      *  when @c kind!=largest_key (which indicates a deleted

    57      *  element). Note that the use of boost::optional increases the

    58      *  memory requirements slightly but does not result in extraneous

    59      *  memory allocations or deallocations. The optional could be

    60      *  eliminated when @c value_type is a model of

    61      *  DefaultConstructible.

    62      */

    63     ::boost::optional<value_type> value;

    64 

    65     /**

    66      * The kind of key stored at this group. This may be @c

    67      * smallest_key, which indicates that the key is infinitely small;

    68      * @c largest_key, which indicates that the key is infinitely

    69      * large; or @c stored_key, which means that the key is unknown,

    70      * but its relationship to other keys can be determined via the

    71      * comparison function object.

    72      */

    73     group_key_kind        kind;

    74 

    75     /// The parent of this group. Will only be NULL for the dummy root group

    76     group*                parent;

    77 

    78     /// The rank of this group. Equivalent to the number of children in

    79     /// the group.

    80     rank_type            rank;

    81 

    82     /** The children of this group. For the dummy root group, these are

    83      * the roots. This is an array of length log n containing pointers

    84      * to the child groups.

    85      */

    86     group**               children;

    87   };

    88 

    89   size_type log_base_2(size_type n) // log2 is a macro on some platforms

    90   {

    91     size_type leading_zeroes = 0;

    92     do {

    93       size_type next = n << 1;

    94       if (n == (next >> 1)) {

    95         ++leading_zeroes;

    96         n = next;

    97       } else {

    98         break;

    99       }

   100     } while (true);

   101     return sizeof(size_type) * CHAR_BIT - leading_zeroes - 1;

   102   }

   103 

   104 public:

   105   relaxed_heap(size_type n, const Compare& compare = Compare(),

   106                const ID& id = ID())

   107     : compare(compare), id(id), root(smallest_key), groups(n),

   108       smallest_value(0)

   109   {

   110     if (n == 0) {

   111       root.children = new group*[1];

   112       return;

   113     }

   114 

   115     log_n = log_base_2(n);

   116     if (log_n == 0) log_n = 1;

   117     size_type g = n / log_n;

   118     if (n % log_n > 0) ++g;

   119     size_type log_g = log_base_2(g);

   120     size_type r = log_g;

   121 

   122     // Reserve an appropriate amount of space for data structures, so

   123     // that we do not need to expand them.

   124     index_to_group.resize(g);

   125     A.resize(r + 1, 0);

   126     root.rank = r + 1;

   127     root.children = new group*[(log_g + 1) * (g + 1)];

   128     for (rank_type i = 0; i < r+1; ++i) root.children[i] = 0;

   129 

   130     // Build initial heap

   131     size_type idx = 0;

   132     while (idx < g) {

   133       root.children[r] = &index_to_group[idx];

   134       idx = build_tree(root, idx, r, log_g + 1);

   135       if (idx != g)

   136         r = static_cast<size_type>(log_base_2(g-idx));

   137     }

   138   }

   139 

   140   ~relaxed_heap() { delete [] root.children; }

   141 

   142   void push(const value_type& x)

   143   {

   144     groups[get(id, x)] = x;

   145     update(x);

   146   }

   147 

   148   void update(const value_type& x)

   149   {

   150     group* a = &index_to_group[get(id, x) / log_n];

   151     if (!a->value

   152         || *a->value == x

   153         || compare(x, *a->value)) {

   154       if (a != smallest_value) smallest_value = 0;

   155       a->kind = stored_key;

   156       a->value = x;

   157       promote(a);

   158     }

   159   }

   160 

   161   void remove(const value_type& x)

   162   {

   163     group* a = &index_to_group[get(id, x) / log_n];

   164     assert(groups[get(id, x)] != 0);

   165     a->value = x;

   166     a->kind = smallest_key;

   167     promote(a);

   168     smallest_value = a;

   169     pop();

   170   }

   171 

   172   value_type& top()

   173   {

   174     find_smallest();

   175     assert(smallest_value->value != 0);

   176     return *smallest_value->value;

   177   }

   178 

   179   const value_type& top() const

   180   {

   181     find_smallest();

   182     assert(smallest_value->value != 0);

   183     return *smallest_value->value;

   184   }

   185 

   186   bool empty() const

   187   {

   188     find_smallest();

   189     return !smallest_value || (smallest_value->kind == largest_key);

   190   }

   191 

   192   bool contains(const value_type& x) const { return groups[get(id, x)]; }

   193 

   194   void pop()

   195   {

   196     // Fill in smallest_value. This is the group x.

   197     find_smallest();

   198     group* x = smallest_value;

   199     smallest_value = 0;

   200 

   201     // Make x a leaf, giving it the smallest value within its group

   202     rank_type r = x->rank;

   203     group* p = x->parent;

   204     {

   205       assert(x->value != 0);

   206 

   207       // Find x's group

   208       size_type start = get(id, *x->value) - get(id, *x->value) % log_n;

   209       size_type end = start + log_n;

   210       if (end > groups.size()) end = groups.size();

   211 

   212       // Remove the smallest value from the group, and find the new

   213       // smallest value.

   214       groups[get(id, *x->value)].reset();

   215       x->value.reset();

   216       x->kind = largest_key;

   217       for (size_type i = start; i < end; ++i) {

   218         if (groups[i] && (!x->value || compare(*groups[i], *x->value))) {

   219           x->kind = stored_key;

   220           x->value = groups[i];

   221         }

   222       }

   223     }

   224     x->rank = 0;

   225 

   226     // Combine prior children of x with x

   227     group* y = x;

   228     for (size_type c = 0; c < r; ++c) {

   229       group* child = x->children[c];

   230       if (A[c] == child) A[c] = 0;

   231       y = combine(y, child);

   232     }

   233 

   234     // If we got back something other than x, let y take x's place

   235     if (y != x) {

   236       y->parent = p;

   237       p->children[r] = y;

   238 

   239       assert(r == y->rank);

   240       if (A[y->rank] == x)

   241         A[y->rank] = do_compare(y, p)? y : 0;

   242     }

   243   }

   244 

   245 #ifdef BOOST_RELAXED_HEAP_DEBUG

   246   /*************************************************************************

   247    * Debugging support                                                     *

   248    *************************************************************************/

   249   void dump_tree() { dump_tree(std::cout); }

   250   void dump_tree(std::ostream& out) { dump_tree(out, &root); }

   251 

   252   void dump_tree(std::ostream& out, group* p, bool in_progress = false)

   253   {

   254     if (!in_progress) {

   255       out << "digraph heap {\n"

   256           << "  edge[dir=\"back\"];\n";

   257     }

   258 

   259     size_type p_index = 0;

   260     if (p != &root) while (&index_to_group[p_index] != p) ++p_index;

   261 

   262     for (size_type i = 0; i < p->rank; ++i) {

   263       group* c = p->children[i];

   264       if (c) {

   265         size_type c_index = 0;

   266         if (c != &root) while (&index_to_group[c_index] != c) ++c_index;

   267 

   268         out << "  ";

   269         if (p == &root) out << 'p'; else out << p_index;

   270         out << " -> ";

   271         if (c == &root) out << 'p'; else out << c_index;

   272         if (A[c->rank] == c) out << " [style=\"dotted\"]";

   273         out << ";\n";

   274         dump_tree(out, c, true);

   275 

   276         // Emit node information

   277         out << "  ";

   278         if (c == &root) out << 'p'; else out << c_index;

   279         out << " [label=\"";

   280         if (c == &root) out << 'p'; else out << c_index;

   281         out << ":";

   282         size_type start = c_index * log_n;

   283         size_type end = start + log_n;

   284         if (end > groups.size()) end = groups.size();

   285         while (start != end) {

   286           if (groups[start]) {

   287             out << " " << get(id, *groups[start]);

   288             if (*groups[start] == *c->value) out << "(*)";

   289           }

   290           ++start;

   291         }

   292         out << '"';

   293 

   294         if (do_compare(c, p)) {

   295           out << "  ";

   296           if (c == &root) out << 'p'; else out << c_index;

   297           out << ", style=\"filled\", fillcolor=\"gray\"";

   298         }

   299         out << "];\n";

   300       } else {

   301         assert(p->parent == p);

   302       }

   303     }

   304     if (!in_progress) out << "}\n";

   305   }

   306 

   307   bool valid()

   308   {

   309     // Check that the ranks in the A array match the ranks of the

   310     // groups stored there. Also, the active groups must be the last

   311     // child of their parent.

   312     for (size_type r = 0; r < A.size(); ++r) {

   313       if (A[r] && A[r]->rank != r) return false;

   314 

   315       if (A[r] && A[r]->parent->children[A[r]->parent->rank-1] != A[r])

   316         return false;

   317     }

   318 

   319     // The root must have no value and a key of -Infinity

   320     if (root.kind != smallest_key) return false;

   321 

   322     return valid(&root);

   323   }

   324 

   325   bool valid(group* p)

   326   {

   327     for (size_type i = 0; i < p->rank; ++i) {

   328       group* c = p->children[i];

   329       if (c) {

   330         // Check link structure

   331         if (c->parent != p) return false;

   332         if (c->rank != i) return false;

   333 

   334         // A bad group must be active

   335         if (do_compare(c, p) && A[i] != c) return false;

   336 

   337         // Check recursively

   338         if (!valid(c)) return false;

   339       } else {

   340         // Only the root may

   341         if (p != &root) return false;

   342       }

   343     }

   344     return true;

   345   }

   346 

   347 #endif // BOOST_RELAXED_HEAP_DEBUG

   348 

   349 private:

   350   size_type

   351   build_tree(group& parent, size_type idx, size_type r, size_type max_rank)

   352   {

   353     group& this_group = index_to_group[idx];

   354     this_group.parent = &parent;

   355     ++idx;

   356 

   357     this_group.children = root.children + (idx * max_rank);

   358     this_group.rank = r;

   359     for (size_type i = 0; i < r; ++i) {

   360       this_group.children[i] = &index_to_group[idx];

   361       idx = build_tree(this_group, idx, i, max_rank);

   362     }

   363     return idx;

   364   }

   365 

   366   void find_smallest() const

   367   {

   368     group** roots = root.children;

   369 

   370     if (!smallest_value) {

   371       std::size_t i;

   372       for (i = 0; i < root.rank; ++i) {

   373         if (roots[i] &&

   374             (!smallest_value || do_compare(roots[i], smallest_value))) {

   375           smallest_value = roots[i];

   376         }

   377       }

   378       for (i = 0; i < A.size(); ++i) {

   379         if (A[i] && (!smallest_value || do_compare(A[i], smallest_value)))

   380           smallest_value = A[i];

   381       }

   382     }

   383   }

   384 

   385   bool do_compare(group* x, group* y) const

   386   {

   387     return (x->kind < y->kind

   388             || (x->kind == y->kind

   389                 && x->kind == stored_key

   390                 && compare(*x->value, *y->value)));

   391   }

   392 

   393   void promote(group* a)

   394   {

   395     assert(a != 0);

   396     rank_type r = a->rank;

   397     group* p = a->parent;

   398     assert(p != 0);

   399     if (do_compare(a, p)) {

   400       // s is the rank + 1 sibling

   401       group* s = p->rank > r + 1? p->children[r + 1] : 0;

   402 

   403       // If a is the last child of p

   404       if (r == p->rank - 1) {

   405         if (!A[r]) A[r] = a;

   406         else if (A[r] != a) pair_transform(a);

   407       } else {

   408         assert(s != 0);

   409         if (A[r + 1] == s) active_sibling_transform(a, s);

   410         else good_sibling_transform(a, s);

   411       }

   412     }

   413   }

   414 

   415   group* combine(group* a1, group* a2)

   416   {

   417     assert(a1->rank == a2->rank);

   418     if (do_compare(a2, a1)) do_swap(a1, a2);

   419     a1->children[a1->rank++] = a2;

   420     a2->parent = a1;

   421     clean(a1);

   422     return a1;

   423   }

   424 

   425   void clean(group* q)

   426   {

   427     if (2 > q->rank) return;

   428     group* qp = q->children[q->rank-1];

   429     rank_type s = q->rank - 2;

   430     group* x = q->children[s];

   431     group* xp = qp->children[s];

   432     assert(s == x->rank);

   433 

   434     // If x is active, swap x and xp

   435     if (A[s] == x) {

   436       q->children[s] = xp;

   437       xp->parent = q;

   438       qp->children[s] = x;

   439       x->parent = qp;

   440     }

   441   }

   442 

   443   void pair_transform(group* a)

   444   {

   445 #if defined(BOOST_RELAXED_HEAP_DEBUG) && BOOST_RELAXED_HEAP_DEBUG > 1

   446     std::cerr << "- pair transform\n";

   447 #endif

   448     rank_type r = a->rank;

   449 

   450     // p is a's parent

   451     group* p = a->parent;

   452     assert(p != 0);

   453 

   454     // g is p's parent (a's grandparent)

   455     group* g = p->parent;

   456     assert(g != 0);

   457 

   458     // a' <- A(r)

   459     assert(A[r] != 0);

   460     group* ap = A[r];

   461     assert(ap != 0);

   462 

   463     // A(r) <- nil

   464     A[r] = 0;

   465 

   466     // let a' have parent p'

   467     group* pp = ap->parent;

   468     assert(pp != 0);

   469 

   470     // let a' have grandparent g'

   471     group* gp = pp->parent;

   472     assert(gp != 0);

   473 

   474     // Remove a and a' from their parents

   475     assert(ap == pp->children[pp->rank-1]); // Guaranteed because ap is active

   476     --pp->rank;

   477 

   478     // Guaranteed by caller

   479     assert(a == p->children[p->rank-1]);

   480     --p->rank;

   481 

   482     // Note: a, ap, p, pp all have rank r

   483     if (do_compare(pp, p)) {

   484       do_swap(a, ap);

   485       do_swap(p, pp);

   486       do_swap(g, gp);

   487     }

   488 

   489     // Assuming k(p) <= k(p')

   490     // make p' the rank r child of p

   491     assert(r == p->rank);

   492     p->children[p->rank++] = pp;

   493     pp->parent = p;

   494 

   495     // Combine a, ap into a rank r+1 group c

   496     group* c = combine(a, ap);

   497 

   498     // make c the rank r+1 child of g'

   499     assert(gp->rank > r+1);

   500     gp->children[r+1] = c;

   501     c->parent = gp;

   502 

   503 #if defined(BOOST_RELAXED_HEAP_DEBUG) && BOOST_RELAXED_HEAP_DEBUG > 1

   504     std::cerr << "After pair transform...\n";

   505     dump_tree();

   506 #endif

   507 

   508     if (A[r+1] == pp) A[r+1] = c;

   509     else promote(c);

   510   }

   511 

   512   void active_sibling_transform(group* a, group* s)

   513   {

   514 #if defined(BOOST_RELAXED_HEAP_DEBUG) && BOOST_RELAXED_HEAP_DEBUG > 1

   515     std::cerr << "- active sibling transform\n";

   516 #endif

   517     group* p = a->parent;

   518     group* g = p->parent;

   519 

   520     // remove a, s from their parents

   521     assert(s->parent == p);

   522     assert(p->children[p->rank-1] == s);

   523     --p->rank;

   524     assert(p->children[p->rank-1] == a);

   525     --p->rank;

   526 

   527     rank_type r = a->rank;

   528     A[r+1] = 0;

   529     a = combine(p, a);

   530     group* c = combine(a, s);

   531 

   532     // make c the rank r+2 child of g

   533     assert(g->children[r+2] == p);

   534     g->children[r+2] = c;

   535     c->parent = g;

   536     if (A[r+2] == p) A[r+2] = c;

   537     else promote(c);

   538   }

   539 

   540   void good_sibling_transform(group* a, group* s)

   541   {

   542 #if defined(BOOST_RELAXED_HEAP_DEBUG) && BOOST_RELAXED_HEAP_DEBUG > 1

   543     std::cerr << "- good sibling transform\n";

   544 #endif

   545     rank_type r = a->rank;

   546     group* c = s->children[s->rank-1];

   547     assert(c->rank == r);

   548     if (A[r] == c) {

   549 #if defined(BOOST_RELAXED_HEAP_DEBUG) && BOOST_RELAXED_HEAP_DEBUG > 1

   550       std::cerr << "- good sibling pair transform\n";

   551 #endif

   552       A[r] = 0;

   553       group* p = a->parent;

   554 

   555       // Remove c from its parent

   556       --s->rank;

   557 

   558       // Make s the rank r child of p

   559       s->parent = p;

   560       p->children[r] = s;

   561 

   562       // combine a, c and let the result by the rank r+1 child of p

   563       assert(p->rank > r+1);

   564       group* x = combine(a, c);

   565       x->parent = p;

   566       p->children[r+1] = x;

   567 

   568       if (A[r+1] == s) A[r+1] = x;

   569       else promote(x);

   570 

   571 #if defined(BOOST_RELAXED_HEAP_DEBUG) && BOOST_RELAXED_HEAP_DEBUG > 1

   572       dump_tree(std::cerr);

   573 #endif

   574       //      pair_transform(a);

   575     } else {

   576       // Clean operation

   577       group* p = a->parent;

   578       s->children[r] = a;

   579       a->parent = s;

   580       p->children[r] = c;

   581       c->parent = p;

   582 

   583       promote(a);

   584     }

   585   }

   586 

   587   static void do_swap(group*& x, group*& y)

   588   {

   589     group* tmp = x;

   590     x = y;

   591     y = tmp;

   592   }

   593 

   594   /// Function object that compares two values in the heap

   595   Compare compare;

   596 

   597   /// Mapping from values to indices in the range [0, n).

   598   ID id;

   599 

   600   /** The root group of the queue. This group is special because it will

   601    *  never store a value, but it acts as a parent to all of the

   602    *  roots. Thus, its list of children is the list of roots.

   603    */

   604   group root;

   605 

   606   /** Mapping from the group index of a value to the group associated

   607    *  with that value. If a value is not in the queue, then the "value"

   608    *  field will be empty.

   609    */

   610   std::vector<group> index_to_group;

   611 

   612   /** Flat data structure containing the values in each of the

   613    *  groups. It will be indexed via the id of the values. The groups

   614    *  are each log_n long, with the last group potentially being

   615    *  smaller.

   616    */

   617   std::vector< ::boost::optional<value_type> > groups;

   618 

   619   /** The list of active groups, indexed by rank. When A[r] is null,

   620    *  there is no active group of rank r. Otherwise, A[r] is the active

   621    *  group of rank r.

   622    */

   623   std::vector<group*> A;

   624 

   625   /** The group containing the smallest value in the queue, which must

   626    *  be either a root or an active group. If this group is null, then we

   627    *  will need to search for this group when it is needed.

   628    */

   629   mutable group* smallest_value;

   630 

   631   /// Cached value log_base_2(n)

   632   size_type log_n;

   633 };

   634 

   635 

   636 } // end namespace boost

   637 

   638 #if defined(BOOST_MSVC)

   639 #  pragma warning(pop)

   640 #endif

   641 

   642 #endif // BOOST_RELAXED_HEAP_HEADER