boost/pending/relaxed_heap.hpp

   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/property_map.hpp>
  14 #include <boost/optional.hpp>
  15 #include <vector>
  16 #include <climits> // for CHAR_BIT
  17 #include <boost/none.hpp>
  18
  19 #ifdef BOOST_RELAXED_HEAP_DEBUG
  20 #  include <iostream>
  21 #endif // BOOST_RELAXED_HEAP_DEBUG
  22
  23 #if defined(BOOST_MSVC)
  24 #  pragma warning(push)
  25 #  pragma warning(disable:4355) // complaint about using 'this' to
  26 #endif                          // initialize a member
  27
  28 namespace boost {
  29
  30 template<typename IndexedType,
  31          typename Compare = std::less<IndexedType>,
  32          typename ID = identity_property_map>
  33 class relaxed_heap
  34 {
  35   struct group;
  36
  37   typedef relaxed_heap self_type;
  38   typedef std::size_t  rank_type;
  39
  40 public:
  41   typedef IndexedType  value_type;
  42   typedef rank_type    size_type;
  43
  44 private:
  45   /**
  46    * The kind of key that a group has. The actual values are discussed
  47    * in-depth in the documentation of the @c kind field of the @c group
  48    * structure. Note that the order of the enumerators *IS* important
  49    * and must not be changed.
  50    */
  51   enum group_key_kind { smallest_key, stored_key, largest_key };
  52
  53   struct group {
  54     explicit group(group_key_kind kind = largest_key)
  55       : kind(kind), parent(this), rank(0) { }
  56
  57     /** The value associated with this group. This value is only valid
  58      *  when @c kind!=largest_key (which indicates a deleted
  59      *  element). Note that the use of boost::optional increases the
  60      *  memory requirements slightly but does not result in extraneous
  61      *  memory allocations or deallocations. The optional could be
  62      *  eliminated when @c value_type is a model of
  63      *  DefaultConstructible.
  64      */
  65     ::boost::optional<value_type> value;
  66
  67     /**
  68      * The kind of key stored at this group. This may be @c
  69      * smallest_key, which indicates that the key is infinitely small;
  70      * @c largest_key, which indicates that the key is infinitely
  71      * large; or @c stored_key, which means that the key is unknown,
  72      * but its relationship to other keys can be determined via the
  73      * comparison function object.
  74      */
  75     group_key_kind        kind;
  76
  77     /// The parent of this group. Will only be NULL for the dummy root group
  78     group*                parent;
  79
  80     /// The rank of this group. Equivalent to the number of children in
  81     /// the group.
  82     rank_type            rank;
  83
  84     /** The children of this group. For the dummy root group, these are
  85      * the roots. This is an array of length log n containing pointers
  86      * to the child groups.
  87      */
  88     group**               children;
  89   };
  90
  91   size_type log_base_2(size_type n) // log2 is a macro on some platforms
  92   {
  93     size_type leading_zeroes = 0;
  94     do {
  95       size_type next = n << 1;
  96       if (n == (next >> 1)) {
  97         ++leading_zeroes;
  98         n = next;
  99       } else {
 100         break;
 101       }
 102     } while (true);
 103     return sizeof(size_type) * CHAR_BIT - leading_zeroes - 1;
 104   }
 105
 106 public:
 107   relaxed_heap(size_type n, const Compare& compare = Compare(),
 108                const ID& id = ID())
 109     : compare(compare), id(id), root(smallest_key), groups(n),
 110       smallest_value(0)
 111   {
 112     if (n == 0) {
 113       root.children = new group*[1];
 114       return;
 115     }
 116
 117     log_n = log_base_2(n);
 118     if (log_n == 0) log_n = 1;
 119     size_type g = n / log_n;
 120     if (n % log_n > 0) ++g;
 121     size_type log_g = log_base_2(g);
 122     size_type r = log_g;
 123
 124     // Reserve an appropriate amount of space for data structures, so
 125     // that we do not need to expand them.
 126     index_to_group.resize(g);
 127     A.resize(r + 1, 0);
 128     root.rank = r + 1;
 129     root.children = new group*[(log_g + 1) * (g + 1)];
 130     for (rank_type i = 0; i < r+1; ++i) root.children[i] = 0;
 131
 132     // Build initial heap
 133     size_type idx = 0;
 134     while (idx < g) {
 135       root.children[r] = &index_to_group[idx];
 136       idx = build_tree(root, idx, r, log_g + 1);
 137       if (idx != g)
 138         r = static_cast<size_type>(log_base_2(g-idx));
 139     }
 140   }
 141
 142   ~relaxed_heap() { delete [] root.children; }
 143
 144   void push(const value_type& x)
 145   {
 146     groups[get(id, x)] = x;
 147     update(x);
 148   }
 149
 150   void update(const value_type& x)
 151   {
 152     group* a = &index_to_group[get(id, x) / log_n];
 153     if (!a->value
 154         || *a->value == x
 155         || compare(x, *a->value)) {
 156       if (a != smallest_value) smallest_value = 0;
 157       a->kind = stored_key;
 158       a->value = x;
 159       promote(a);
 160     }
 161   }
 162
 163   void remove(const value_type& x)
 164   {
 165     group* a = &index_to_group[get(id, x) / log_n];
 166     assert(groups[get(id, x)]);
 167     a->value = x;
 168     a->kind = smallest_key;
 169     promote(a);
 170     smallest_value = a;
 171     pop();
 172   }
 173
 174   value_type& top()
 175   {
 176     find_smallest();
 177     assert(smallest_value->value != none);
 178     return *smallest_value->value;
 179   }
 180
 181   const value_type& top() const
 182   {
 183     find_smallest();
 184     assert(smallest_value->value != none);
 185     return *smallest_value->value;
 186   }
 187
 188   bool empty() const
 189   {
 190     find_smallest();
 191     return !smallest_value || (smallest_value->kind == largest_key);
 192   }
 193
 194   bool contains(const value_type& x) const { return groups[get(id, x)]; }
 195
 196   void pop()
 197   {
 198     // Fill in smallest_value. This is the group x.
 199     find_smallest();
 200     group* x = smallest_value;
 201     smallest_value = 0;
 202
 203     // Make x a leaf, giving it the smallest value within its group
 204     rank_type r = x->rank;
 205     group* p = x->parent;
 206     {
 207       assert(x->value != none);
 208
 209       // Find x's group
 210       size_type start = get(id, *x->value) - get(id, *x->value) % log_n;
 211       size_type end = start + log_n;
 212       if (end > groups.size()) end = groups.size();
 213
 214       // Remove the smallest value from the group, and find the new
 215       // smallest value.
 216       groups[get(id, *x->value)].reset();
 217       x->value.reset();
 218       x->kind = largest_key;
 219       for (size_type i = start; i < end; ++i) {
 220         if (groups[i] && (!x->value || compare(*groups[i], *x->value))) {
 221           x->kind = stored_key;
 222           x->value = groups[i];
 223         }
 224       }
 225     }
 226     x->rank = 0;
 227
 228     // Combine prior children of x with x
 229     group* y = x;
 230     for (size_type c = 0; c < r; ++c) {
 231       group* child = x->children[c];
 232       if (A[c] == child) A[c] = 0;
 233       y = combine(y, child);
 234     }
 235
 236     // If we got back something other than x, let y take x's place
 237     if (y != x) {
 238       y->parent = p;
 239       p->children[r] = y;
 240
 241       assert(r == y->rank);
 242       if (A[y->rank] == x)
 243         A[y->rank] = do_compare(y, p)? y : 0;
 244     }
 245   }
 246
 247 #ifdef BOOST_RELAXED_HEAP_DEBUG
 248   /*************************************************************************
 249    * Debugging support                                                     *
 250    *************************************************************************/
 251   void dump_tree() { dump_tree(std::cout); }
 252   void dump_tree(std::ostream& out) { dump_tree(out, &root); }
 253
 254   void dump_tree(std::ostream& out, group* p, bool in_progress = false)
 255   {
 256     if (!in_progress) {
 257       out << "digraph heap {\n"
 258           << "  edge[dir=\"back\"];\n";
 259     }
 260
 261     size_type p_index = 0;
 262     if (p != &root) while (&index_to_group[p_index] != p) ++p_index;
 263
 264     for (size_type i = 0; i < p->rank; ++i) {
 265       group* c = p->children[i];
 266       if (c) {
 267         size_type c_index = 0;
 268         if (c != &root) while (&index_to_group[c_index] != c) ++c_index;
 269
 270         out << "  ";
 271         if (p == &root) out << 'p'; else out << p_index;
 272         out << " -> ";
 273         if (c == &root) out << 'p'; else out << c_index;
 274         if (A[c->rank] == c) out << " [style=\"dotted\"]";
 275         out << ";\n";
 276         dump_tree(out, c, true);
 277
 278         // Emit node information
 279         out << "  ";
 280         if (c == &root) out << 'p'; else out << c_index;
 281         out << " [label=\"";
 282         if (c == &root) out << 'p'; else out << c_index;
 283         out << ":";
 284         size_type start = c_index * log_n;
 285         size_type end = start + log_n;
 286         if (end > groups.size()) end = groups.size();
 287         while (start != end) {
 288           if (groups[start]) {
 289             out << " " << get(id, *groups[start]);
 290             if (*groups[start] == *c->value) out << "(*)";
 291           }
 292           ++start;
 293         }
 294         out << '"';
 295
 296         if (do_compare(c, p)) {
 297           out << "  ";
 298           if (c == &root) out << 'p'; else out << c_index;
 299           out << ", style=\"filled\", fillcolor=\"gray\"";
 300         }
 301         out << "];\n";
 302       } else {
 303         assert(p->parent == p);
 304       }
 305     }
 306     if (!in_progress) out << "}\n";
 307   }
 308
 309   bool valid()
 310   {
 311     // Check that the ranks in the A array match the ranks of the
 312     // groups stored there. Also, the active groups must be the last
 313     // child of their parent.
 314     for (size_type r = 0; r < A.size(); ++r) {
 315       if (A[r] && A[r]->rank != r) return false;
 316
 317       if (A[r] && A[r]->parent->children[A[r]->parent->rank-1] != A[r])
 318         return false;
 319     }
 320
 321     // The root must have no value and a key of -Infinity
 322     if (root.kind != smallest_key) return false;
 323
 324     return valid(&root);
 325   }
 326
 327   bool valid(group* p)
 328   {
 329     for (size_type i = 0; i < p->rank; ++i) {
 330       group* c = p->children[i];
 331       if (c) {
 332         // Check link structure
 333         if (c->parent != p) return false;
 334         if (c->rank != i) return false;
 335
 336         // A bad group must be active
 337         if (do_compare(c, p) && A[i] != c) return false;
 338
 339         // Check recursively
 340         if (!valid(c)) return false;
 341       } else {
 342         // Only the root may
 343         if (p != &root) return false;
 344       }
 345     }
 346     return true;
 347   }
 348
 349 #endif // BOOST_RELAXED_HEAP_DEBUG
 350
 351 private:
 352   size_type
 353   build_tree(group& parent, size_type idx, size_type r, size_type max_rank)
 354   {
 355     group& this_group = index_to_group[idx];
 356     this_group.parent = &parent;
 357     ++idx;
 358
 359     this_group.children = root.children + (idx * max_rank);
 360     this_group.rank = r;
 361     for (size_type i = 0; i < r; ++i) {
 362       this_group.children[i] = &index_to_group[idx];
 363       idx = build_tree(this_group, idx, i, max_rank);
 364     }
 365     return idx;
 366   }
 367
 368   void find_smallest() const
 369   {
 370     group** roots = root.children;
 371
 372     if (!smallest_value) {
 373       std::size_t i;
 374       for (i = 0; i < root.rank; ++i) {
 375         if (roots[i] &&
 376             (!smallest_value || do_compare(roots[i], smallest_value))) {
 377           smallest_value = roots[i];
 378         }
 379       }
 380       for (i = 0; i < A.size(); ++i) {
 381         if (A[i] && (!smallest_value || do_compare(A[i], smallest_value)))
 382           smallest_value = A[i];
 383       }
 384     }
 385   }
 386
 387   bool do_compare(group* x, group* y) const
 388   {
 389     return (x->kind < y->kind
 390             || (x->kind == y->kind
 391                 && x->kind == stored_key
 392                 && compare(*x->value, *y->value)));
 393   }
 394
 395   void promote(group* a)
 396   {
 397     assert(a != 0);
 398     rank_type r = a->rank;
 399     group* p = a->parent;
 400     assert(p != 0);
 401     if (do_compare(a, p)) {
 402       // s is the rank + 1 sibling
 403       group* s = p->rank > r + 1? p->children[r + 1] : 0;
 404
 405       // If a is the last child of p
 406       if (r == p->rank - 1) {
 407         if (!A[r]) A[r] = a;
 408         else if (A[r] != a) pair_transform(a);
 409       } else {
 410         assert(s != 0);
 411         if (A[r + 1] == s) active_sibling_transform(a, s);
 412         else good_sibling_transform(a, s);
 413       }
 414     }
 415   }
 416
 417   group* combine(group* a1, group* a2)
 418   {
 419     assert(a1->rank == a2->rank);
 420     if (do_compare(a2, a1)) do_swap(a1, a2);
 421     a1->children[a1->rank++] = a2;
 422     a2->parent = a1;
 423     clean(a1);
 424     return a1;
 425   }
 426
 427   void clean(group* q)
 428   {
 429     if (2 > q->rank) return;
 430     group* qp = q->children[q->rank-1];
 431     rank_type s = q->rank - 2;
 432     group* x = q->children[s];
 433     group* xp = qp->children[s];
 434     assert(s == x->rank);
 435
 436     // If x is active, swap x and xp
 437     if (A[s] == x) {
 438       q->children[s] = xp;
 439       xp->parent = q;
 440       qp->children[s] = x;
 441       x->parent = qp;
 442     }
 443   }
 444
 445   void pair_transform(group* a)
 446   {
 447 #if defined(BOOST_RELAXED_HEAP_DEBUG) && BOOST_RELAXED_HEAP_DEBUG > 1
 448     std::cerr << "- pair transform\n";
 449 #endif
 450     rank_type r = a->rank;
 451
 452     // p is a's parent
 453     group* p = a->parent;
 454     assert(p != 0);
 455
 456     // g is p's parent (a's grandparent)
 457     group* g = p->parent;
 458     assert(g != 0);
 459
 460     // a' <- A(r)
 461     assert(A[r] != 0);
 462     group* ap = A[r];
 463     assert(ap != 0);
 464
 465     // A(r) <- nil
 466     A[r] = 0;
 467
 468     // let a' have parent p'
 469     group* pp = ap->parent;
 470     assert(pp != 0);
 471
 472     // let a' have grandparent g'
 473     group* gp = pp->parent;
 474     assert(gp != 0);
 475
 476     // Remove a and a' from their parents
 477     assert(ap == pp->children[pp->rank-1]); // Guaranteed because ap is active
 478     --pp->rank;
 479
 480     // Guaranteed by caller
 481     assert(a == p->children[p->rank-1]);
 482     --p->rank;
 483
 484     // Note: a, ap, p, pp all have rank r
 485     if (do_compare(pp, p)) {
 486       do_swap(a, ap);
 487       do_swap(p, pp);
 488       do_swap(g, gp);
 489     }
 490
 491     // Assuming k(p) <= k(p')
 492     // make p' the rank r child of p
 493     assert(r == p->rank);
 494     p->children[p->rank++] = pp;
 495     pp->parent = p;
 496
 497     // Combine a, ap into a rank r+1 group c
 498     group* c = combine(a, ap);
 499
 500     // make c the rank r+1 child of g'
 501     assert(gp->rank > r+1);
 502     gp->children[r+1] = c;
 503     c->parent = gp;
 504
 505 #if defined(BOOST_RELAXED_HEAP_DEBUG) && BOOST_RELAXED_HEAP_DEBUG > 1
 506     std::cerr << "After pair transform...\n";
 507     dump_tree();
 508 #endif
 509
 510     if (A[r+1] == pp) A[r+1] = c;
 511     else promote(c);
 512   }
 513
 514   void active_sibling_transform(group* a, group* s)
 515   {
 516 #if defined(BOOST_RELAXED_HEAP_DEBUG) && BOOST_RELAXED_HEAP_DEBUG > 1
 517     std::cerr << "- active sibling transform\n";
 518 #endif
 519     group* p = a->parent;
 520     group* g = p->parent;
 521
 522     // remove a, s from their parents
 523     assert(s->parent == p);
 524     assert(p->children[p->rank-1] == s);
 525     --p->rank;
 526     assert(p->children[p->rank-1] == a);
 527     --p->rank;
 528
 529     rank_type r = a->rank;
 530     A[r+1] = 0;
 531     a = combine(p, a);
 532     group* c = combine(a, s);
 533
 534     // make c the rank r+2 child of g
 535     assert(g->children[r+2] == p);
 536     g->children[r+2] = c;
 537     c->parent = g;
 538     if (A[r+2] == p) A[r+2] = c;
 539     else promote(c);
 540   }
 541
 542   void good_sibling_transform(group* a, group* s)
 543   {
 544 #if defined(BOOST_RELAXED_HEAP_DEBUG) && BOOST_RELAXED_HEAP_DEBUG > 1
 545     std::cerr << "- good sibling transform\n";
 546 #endif
 547     rank_type r = a->rank;
 548     group* c = s->children[s->rank-1];
 549     assert(c->rank == r);
 550     if (A[r] == c) {
 551 #if defined(BOOST_RELAXED_HEAP_DEBUG) && BOOST_RELAXED_HEAP_DEBUG > 1
 552       std::cerr << "- good sibling pair transform\n";
 553 #endif
 554       A[r] = 0;
 555       group* p = a->parent;
 556
 557       // Remove c from its parent
 558       --s->rank;
 559
 560       // Make s the rank r child of p
 561       s->parent = p;
 562       p->children[r] = s;
 563
 564       // combine a, c and let the result by the rank r+1 child of p
 565       assert(p->rank > r+1);
 566       group* x = combine(a, c);
 567       x->parent = p;
 568       p->children[r+1] = x;
 569
 570       if (A[r+1] == s) A[r+1] = x;
 571       else promote(x);
 572
 573 #if defined(BOOST_RELAXED_HEAP_DEBUG) && BOOST_RELAXED_HEAP_DEBUG > 1
 574       dump_tree(std::cerr);
 575 #endif
 576       //      pair_transform(a);
 577     } else {
 578       // Clean operation
 579       group* p = a->parent;
 580       s->children[r] = a;
 581       a->parent = s;
 582       p->children[r] = c;
 583       c->parent = p;
 584
 585       promote(a);
 586     }
 587   }
 588
 589   static void do_swap(group*& x, group*& y)
 590   {
 591     group* tmp = x;
 592     x = y;
 593     y = tmp;
 594   }
 595
 596   /// Function object that compares two values in the heap
 597   Compare compare;
 598
 599   /// Mapping from values to indices in the range [0, n).
 600   ID id;
 601
 602   /** The root group of the queue. This group is special because it will
 603    *  never store a value, but it acts as a parent to all of the
 604    *  roots. Thus, its list of children is the list of roots.
 605    */
 606   group root;
 607
 608   /** Mapping from the group index of a value to the group associated
 609    *  with that value. If a value is not in the queue, then the "value"
 610    *  field will be empty.
 611    */
 612   std::vector<group> index_to_group;
 613
 614   /** Flat data structure containing the values in each of the
 615    *  groups. It will be indexed via the id of the values. The groups
 616    *  are each log_n long, with the last group potentially being
 617    *  smaller.
 618    */
 619   std::vector< ::boost::optional<value_type> > groups;
 620
 621   /** The list of active groups, indexed by rank. When A[r] is null,
 622    *  there is no active group of rank r. Otherwise, A[r] is the active
 623    *  group of rank r.
 624    */
 625   std::vector<group*> A;
 626
 627   /** The group containing the smallest value in the queue, which must
 628    *  be either a root or an active group. If this group is null, then we
 629    *  will need to search for this group when it is needed.
 630    */
 631   mutable group* smallest_value;
 632
 633   /// Cached value log_base_2(n)
 634   size_type log_n;
 635 };
 636
 637
 638 } // end namespace boost
 639
 640 #if defined(BOOST_MSVC)
 641 #  pragma warning(pop)
 642 #endif
 643
 644 #endif // BOOST_RELAXED_HEAP_HEADER