epoc32/include/stdapis/boost/pending/relaxed_heap.hpp
author William Roberts <williamr@symbian.org>
Wed, 31 Mar 2010 12:33:34 +0100
branchSymbian3
changeset 4 837f303aceeb
permissions -rw-r--r--
Current Symbian^3 public API header files (from PDK 3.0.h)
This is the epoc32/include tree with the "platform" subtrees removed, and
all but a selected few mbg and rsg files removed.
     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