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