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 { groupboost::relaxed_heap::group54 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 log_base_2(size_type n)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: relaxed_heap(size_type n,const Compare & compare=Compare (),const ID & id=ID ())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 ~relaxed_heap()142 ~relaxed_heap() { delete [] root.children; } 143 push(const value_type & x)144 void push(const value_type& x) 145 { 146 groups[get(id, x)] = x; 147 update(x); 148 } 149 update(const value_type & x)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 remove(const value_type & x)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 top()174 value_type& top() 175 { 176 find_smallest(); 177 assert(smallest_value->value != none); 178 return *smallest_value->value; 179 } 180 top() const181 const value_type& top() const 182 { 183 find_smallest(); 184 assert(smallest_value->value != none); 185 return *smallest_value->value; 186 } 187 empty() const188 bool empty() const 189 { 190 find_smallest(); 191 return !smallest_value || (smallest_value->kind == largest_key); 192 } 193 contains(const value_type & x) const194 bool contains(const value_type& x) const { return groups[get(id, x)]; } 195 pop()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 *************************************************************************/ dump_tree()251 void dump_tree() { dump_tree(std::cout); } dump_tree(std::ostream & out)252 void dump_tree(std::ostream& out) { dump_tree(out, &root); } 253 dump_tree(std::ostream & out,group * p,bool in_progress=false)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 valid()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 valid(group * p)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 build_tree(group & parent,size_type idx,size_type r,size_type max_rank)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 find_smallest() const368 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 do_compare(group * x,group * y) const387 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 promote(group * a)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 combine(group * a1,group * a2)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 clean(group * q)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 pair_transform(group * a)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 active_sibling_transform(group * a,group * s)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 good_sibling_transform(group * a,group * s)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 do_swap(group * & x,group * & y)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 645