1 // boost heap: binomial heap 2 // 3 // Copyright (C) 2010 Tim Blechmann 4 // 5 // Distributed under the Boost Software License, Version 1.0. (See 6 // accompanying file LICENSE_1_0.txt or copy at 7 // http://www.boost.org/LICENSE_1_0.txt) 8 9 #ifndef BOOST_HEAP_BINOMIAL_HEAP_HPP 10 #define BOOST_HEAP_BINOMIAL_HEAP_HPP 11 12 #include <algorithm> 13 #include <utility> 14 #include <vector> 15 16 #include <boost/assert.hpp> 17 18 #include <boost/heap/detail/heap_comparison.hpp> 19 #include <boost/heap/detail/heap_node.hpp> 20 #include <boost/heap/detail/stable_heap.hpp> 21 #include <boost/heap/detail/tree_iterator.hpp> 22 23 #ifdef BOOST_HAS_PRAGMA_ONCE 24 #pragma once 25 #endif 26 27 #ifndef BOOST_DOXYGEN_INVOKED 28 #ifdef BOOST_HEAP_SANITYCHECKS 29 #define BOOST_HEAP_ASSERT BOOST_ASSERT 30 #else 31 #define BOOST_HEAP_ASSERT(expression) 32 #endif 33 #endif 34 35 namespace boost { 36 namespace heap { 37 namespace detail { 38 39 typedef parameter::parameters<boost::parameter::optional<tag::allocator>, 40 boost::parameter::optional<tag::compare>, 41 boost::parameter::optional<tag::stable>, 42 boost::parameter::optional<tag::constant_time_size>, 43 boost::parameter::optional<tag::stability_counter_type> 44 > binomial_heap_signature; 45 46 template <typename T, typename Parspec> 47 struct make_binomial_heap_base 48 { 49 static const bool constant_time_size = parameter::binding<Parspec, 50 tag::constant_time_size, 51 boost::mpl::true_ 52 >::type::value; 53 typedef typename detail::make_heap_base<T, Parspec, constant_time_size>::type base_type; 54 typedef typename detail::make_heap_base<T, Parspec, constant_time_size>::allocator_argument allocator_argument; 55 typedef typename detail::make_heap_base<T, Parspec, constant_time_size>::compare_argument compare_argument; 56 57 typedef parent_pointing_heap_node<typename base_type::internal_type> node_type; 58 59 typedef typename allocator_argument::template rebind<node_type>::other allocator_type; 60 61 struct type: 62 base_type, 63 allocator_type 64 { typeboost::heap::detail::make_binomial_heap_base::type65 type(compare_argument const & arg): 66 base_type(arg) 67 {} 68 69 #ifndef BOOST_NO_CXX11_RVALUE_REFERENCES typeboost::heap::detail::make_binomial_heap_base::type70 type(type const & rhs): 71 base_type(rhs), allocator_type(rhs) 72 {} 73 typeboost::heap::detail::make_binomial_heap_base::type74 type(type && rhs): 75 base_type(std::move(static_cast<base_type&>(rhs))), 76 allocator_type(std::move(static_cast<allocator_type&>(rhs))) 77 {} 78 operator =boost::heap::detail::make_binomial_heap_base::type79 type & operator=(type && rhs) 80 { 81 base_type::operator=(std::move(static_cast<base_type&>(rhs))); 82 allocator_type::operator=(std::move(static_cast<allocator_type&>(rhs))); 83 return *this; 84 } 85 operator =boost::heap::detail::make_binomial_heap_base::type86 type & operator=(type const & rhs) 87 { 88 base_type::operator=(static_cast<base_type const &>(rhs)); 89 allocator_type::operator=(static_cast<allocator_type const &>(rhs)); 90 return *this; 91 } 92 #endif 93 }; 94 }; 95 96 } 97 98 /** 99 * \class binomial_heap 100 * \brief binomial heap 101 * 102 * The template parameter T is the type to be managed by the container. 103 * The user can specify additional options and if no options are provided default options are used. 104 * 105 * The container supports the following options: 106 * - \c boost::heap::stable<>, defaults to \c stable<false> 107 * - \c boost::heap::compare<>, defaults to \c compare<std::less<T> > 108 * - \c boost::heap::allocator<>, defaults to \c allocator<std::allocator<T> > 109 * - \c boost::heap::constant_time_size<>, defaults to \c constant_time_size<true> 110 * - \c boost::heap::stability_counter_type<>, defaults to \c stability_counter_type<boost::uintmax_t> 111 * 112 */ 113 #ifdef BOOST_DOXYGEN_INVOKED 114 template<class T, class ...Options> 115 #else 116 template <typename T, 117 class A0 = boost::parameter::void_, 118 class A1 = boost::parameter::void_, 119 class A2 = boost::parameter::void_, 120 class A3 = boost::parameter::void_ 121 > 122 #endif 123 class binomial_heap: 124 private detail::make_binomial_heap_base<T, 125 typename detail::binomial_heap_signature::bind<A0, A1, A2, A3>::type 126 >::type 127 { 128 typedef typename detail::binomial_heap_signature::bind<A0, A1, A2, A3>::type bound_args; 129 typedef detail::make_binomial_heap_base<T, bound_args> base_maker; 130 typedef typename base_maker::type super_t; 131 132 typedef typename super_t::internal_type internal_type; 133 typedef typename super_t::size_holder_type size_holder; 134 typedef typename super_t::stability_counter_type stability_counter_type; 135 typedef typename base_maker::allocator_argument allocator_argument; 136 137 template <typename Heap1, typename Heap2> 138 friend struct heap_merge_emulate; 139 140 public: 141 static const bool constant_time_size = super_t::constant_time_size; 142 static const bool has_ordered_iterators = true; 143 static const bool is_mergable = true; 144 static const bool is_stable = detail::extract_stable<bound_args>::value; 145 static const bool has_reserve = false; 146 147 private: 148 #ifndef BOOST_DOXYGEN_INVOKED 149 struct implementation_defined: 150 detail::extract_allocator_types<typename base_maker::allocator_argument> 151 { 152 typedef T value_type; 153 typedef typename detail::extract_allocator_types<typename base_maker::allocator_argument>::size_type size_type; 154 typedef typename detail::extract_allocator_types<typename base_maker::allocator_argument>::reference reference; 155 156 typedef typename base_maker::compare_argument value_compare; 157 typedef typename base_maker::allocator_type allocator_type; 158 typedef typename base_maker::node_type node; 159 160 typedef typename allocator_type::pointer node_pointer; 161 typedef typename allocator_type::const_pointer const_node_pointer; 162 163 typedef detail::node_handle<node_pointer, super_t, reference> handle_type; 164 165 typedef typename base_maker::node_type node_type; 166 167 typedef boost::intrusive::list<detail::heap_node_base<false>, 168 boost::intrusive::constant_time_size<true> 169 > node_list_type; 170 171 typedef typename node_list_type::iterator node_list_iterator; 172 typedef typename node_list_type::const_iterator node_list_const_iterator; 173 typedef detail::value_extractor<value_type, internal_type, super_t> value_extractor; 174 175 typedef detail::recursive_tree_iterator<node_type, 176 node_list_const_iterator, 177 const value_type, 178 value_extractor, 179 detail::list_iterator_converter<node_type, node_list_type> 180 > iterator; 181 typedef iterator const_iterator; 182 183 typedef detail::tree_iterator<node_type, 184 const value_type, 185 allocator_type, 186 value_extractor, 187 detail::list_iterator_converter<node_type, node_list_type>, 188 true, 189 true, 190 value_compare 191 > ordered_iterator; 192 }; 193 #endif 194 195 public: 196 typedef T value_type; 197 198 typedef typename implementation_defined::size_type size_type; 199 typedef typename implementation_defined::difference_type difference_type; 200 typedef typename implementation_defined::value_compare value_compare; 201 typedef typename implementation_defined::allocator_type allocator_type; 202 typedef typename implementation_defined::reference reference; 203 typedef typename implementation_defined::const_reference const_reference; 204 typedef typename implementation_defined::pointer pointer; 205 typedef typename implementation_defined::const_pointer const_pointer; 206 /// \copydoc boost::heap::priority_queue::iterator 207 typedef typename implementation_defined::iterator iterator; 208 typedef typename implementation_defined::const_iterator const_iterator; 209 typedef typename implementation_defined::ordered_iterator ordered_iterator; 210 211 typedef typename implementation_defined::handle_type handle_type; 212 213 private: 214 typedef typename implementation_defined::node_type node_type; 215 typedef typename implementation_defined::node_list_type node_list_type; 216 typedef typename implementation_defined::node_pointer node_pointer; 217 typedef typename implementation_defined::const_node_pointer const_node_pointer; 218 typedef typename implementation_defined::node_list_iterator node_list_iterator; 219 typedef typename implementation_defined::node_list_const_iterator node_list_const_iterator; 220 221 typedef typename super_t::internal_compare internal_compare; 222 223 public: 224 /// \copydoc boost::heap::priority_queue::priority_queue(value_compare const &) binomial_heap(value_compare const & cmp=value_compare ())225 explicit binomial_heap(value_compare const & cmp = value_compare()): 226 super_t(cmp), top_element(0) 227 {} 228 229 /// \copydoc boost::heap::priority_queue::priority_queue(priority_queue const &) binomial_heap(binomial_heap const & rhs)230 binomial_heap(binomial_heap const & rhs): 231 super_t(rhs), top_element(0) 232 { 233 if (rhs.empty()) 234 return; 235 236 clone_forest(rhs); 237 size_holder::set_size(rhs.get_size()); 238 } 239 240 /// \copydoc boost::heap::priority_queue::operator=(priority_queue const &) operator =(binomial_heap const & rhs)241 binomial_heap & operator=(binomial_heap const & rhs) 242 { 243 clear(); 244 size_holder::set_size(rhs.get_size()); 245 static_cast<super_t&>(*this) = rhs; 246 247 if (rhs.empty()) 248 top_element = NULL; 249 else 250 clone_forest(rhs); 251 return *this; 252 } 253 254 #ifndef BOOST_NO_CXX11_RVALUE_REFERENCES 255 /// \copydoc boost::heap::priority_queue::priority_queue(priority_queue &&) binomial_heap(binomial_heap && rhs)256 binomial_heap(binomial_heap && rhs): 257 super_t(std::move(rhs)), top_element(rhs.top_element) 258 { 259 trees.splice(trees.begin(), rhs.trees); 260 rhs.top_element = NULL; 261 } 262 263 /// \copydoc boost::heap::priority_queue::operator=(priority_queue &&) operator =(binomial_heap && rhs)264 binomial_heap & operator=(binomial_heap && rhs) 265 { 266 clear(); 267 super_t::operator=(std::move(rhs)); 268 trees.splice(trees.begin(), rhs.trees); 269 top_element = rhs.top_element; 270 rhs.top_element = NULL; 271 return *this; 272 } 273 #endif 274 ~binomial_heap(void)275 ~binomial_heap(void) 276 { 277 clear(); 278 } 279 280 /// \copydoc boost::heap::priority_queue::empty empty(void) const281 bool empty(void) const 282 { 283 return top_element == NULL; 284 } 285 286 /** 287 * \b Effects: Returns the number of elements contained in the priority queue. 288 * 289 * \b Complexity: Constant, if configured with constant_time_size<true>, otherwise linear. 290 * 291 * */ size(void) const292 size_type size(void) const 293 { 294 if (constant_time_size) 295 return size_holder::get_size(); 296 297 if (empty()) 298 return 0; 299 else 300 return detail::count_list_nodes<node_type, node_list_type>(trees); 301 } 302 303 /// \copydoc boost::heap::priority_queue::max_size max_size(void) const304 size_type max_size(void) const 305 { 306 return allocator_type::max_size(); 307 } 308 309 /// \copydoc boost::heap::priority_queue::clear clear(void)310 void clear(void) 311 { 312 typedef detail::node_disposer<node_type, typename node_list_type::value_type, allocator_type> disposer; 313 trees.clear_and_dispose(disposer(*this)); 314 315 size_holder::set_size(0); 316 top_element = NULL; 317 } 318 319 /// \copydoc boost::heap::priority_queue::get_allocator get_allocator(void) const320 allocator_type get_allocator(void) const 321 { 322 return *this; 323 } 324 325 /// \copydoc boost::heap::priority_queue::swap swap(binomial_heap & rhs)326 void swap(binomial_heap & rhs) 327 { 328 super_t::swap(rhs); 329 std::swap(top_element, rhs.top_element); 330 trees.swap(rhs.trees); 331 } 332 333 /// \copydoc boost::heap::priority_queue::top top(void) const334 const_reference top(void) const 335 { 336 BOOST_ASSERT(!empty()); 337 338 return super_t::get_value(top_element->value); 339 } 340 341 /** 342 * \b Effects: Adds a new element to the priority queue. Returns handle to element 343 * 344 * \b Complexity: Logarithmic. 345 * 346 * */ push(value_type const & v)347 handle_type push(value_type const & v) 348 { 349 node_pointer n = allocator_type::allocate(1); 350 new(n) node_type(super_t::make_node(v)); 351 352 insert_node(trees.begin(), n); 353 354 if (!top_element || super_t::operator()(top_element->value, n->value)) 355 top_element = n; 356 357 size_holder::increment(); 358 sanity_check(); 359 return handle_type(n); 360 } 361 362 #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES) && !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) 363 /** 364 * \b Effects: Adds a new element to the priority queue. The element is directly constructed in-place. Returns handle to element. 365 * 366 * \b Complexity: Logarithmic. 367 * 368 * */ 369 template <class... Args> emplace(Args &&...args)370 handle_type emplace(Args&&... args) 371 { 372 node_pointer n = allocator_type::allocate(1); 373 new(n) node_type(super_t::make_node(std::forward<Args>(args)...)); 374 375 insert_node(trees.begin(), n); 376 377 if (!top_element || super_t::operator()(top_element->value, n->value)) 378 top_element = n; 379 380 size_holder::increment(); 381 sanity_check(); 382 return handle_type(n); 383 } 384 #endif 385 386 /** 387 * \b Effects: Removes the top element from the priority queue. 388 * 389 * \b Complexity: Logarithmic. 390 * 391 * */ pop(void)392 void pop(void) 393 { 394 BOOST_ASSERT(!empty()); 395 396 node_pointer element = top_element; 397 398 trees.erase(node_list_type::s_iterator_to(*element)); 399 size_holder::decrement(); 400 401 if (element->child_count()) { 402 size_type sz = (1 << element->child_count()) - 1; 403 404 binomial_heap children(value_comp(), element->children, sz); 405 if (trees.empty()) { 406 stability_counter_type stability_count = super_t::get_stability_count(); 407 swap(children); 408 super_t::set_stability_count(stability_count); 409 } else 410 merge_and_clear_nodes(children); 411 412 } 413 414 if (trees.empty()) 415 top_element = NULL; 416 else 417 update_top_element(); 418 419 element->~node_type(); 420 allocator_type::deallocate(element, 1); 421 sanity_check(); 422 } 423 424 /** 425 * \b Effects: Assigns \c v to the element handled by \c handle & updates the priority queue. 426 * 427 * \b Complexity: Logarithmic. 428 * 429 * */ update(handle_type handle,const_reference v)430 void update (handle_type handle, const_reference v) 431 { 432 if (super_t::operator()(super_t::get_value(handle.node_->value), v)) 433 increase(handle, v); 434 else 435 decrease(handle, v); 436 } 437 438 /** 439 * \b Effects: Updates the heap after the element handled by \c handle has been changed. 440 * 441 * \b Complexity: Logarithmic. 442 * 443 * \b Note: If this is not called, after a handle has been updated, the behavior of the data structure is undefined! 444 * */ update(handle_type handle)445 void update (handle_type handle) 446 { 447 node_pointer this_node = handle.node_; 448 449 if (this_node->parent) { 450 if (super_t::operator()(super_t::get_value(this_node->parent->value), super_t::get_value(this_node->value))) 451 increase(handle); 452 else 453 decrease(handle); 454 } 455 else 456 decrease(handle); 457 } 458 459 /** 460 * \b Effects: Assigns \c v to the element handled by \c handle & updates the priority queue. 461 * 462 * \b Complexity: Logarithmic. 463 * 464 * \b Note: The new value is expected to be greater than the current one 465 * */ increase(handle_type handle,const_reference v)466 void increase (handle_type handle, const_reference v) 467 { 468 handle.node_->value = super_t::make_node(v); 469 increase(handle); 470 } 471 472 /** 473 * \b Effects: Updates the heap after the element handled by \c handle has been changed. 474 * 475 * \b Complexity: Logarithmic. 476 * 477 * \b Note: If this is not called, after a handle has been updated, the behavior of the data structure is undefined! 478 * */ increase(handle_type handle)479 void increase (handle_type handle) 480 { 481 node_pointer n = handle.node_; 482 siftup(n, *this); 483 484 update_top_element(); 485 sanity_check(); 486 } 487 488 /** 489 * \b Effects: Assigns \c v to the element handled by \c handle & updates the priority queue. 490 * 491 * \b Complexity: Logarithmic. 492 * 493 * \b Note: The new value is expected to be less than the current one 494 * */ decrease(handle_type handle,const_reference v)495 void decrease (handle_type handle, const_reference v) 496 { 497 handle.node_->value = super_t::make_node(v); 498 decrease(handle); 499 } 500 501 /** 502 * \b Effects: Updates the heap after the element handled by \c handle has been changed. 503 * 504 * \b Complexity: Logarithmic. 505 * 506 * \b Note: The new value is expected to be less than the current one. If this is not called, after a handle has been updated, the behavior of the data structure is undefined! 507 * */ decrease(handle_type handle)508 void decrease (handle_type handle) 509 { 510 node_pointer n = handle.node_; 511 512 siftdown(n); 513 514 if (n == top_element) 515 update_top_element(); 516 } 517 518 /** 519 * \b Effects: Merge with priority queue rhs. 520 * 521 * \b Complexity: Logarithmic. 522 * 523 * */ merge(binomial_heap & rhs)524 void merge(binomial_heap & rhs) 525 { 526 if (rhs.empty()) 527 return; 528 529 if (empty()) { 530 swap(rhs); 531 return; 532 } 533 534 size_type new_size = size_holder::get_size() + rhs.get_size(); 535 merge_and_clear_nodes(rhs); 536 537 size_holder::set_size(new_size); 538 rhs.set_size(0); 539 rhs.top_element = NULL; 540 541 super_t::set_stability_count((std::max)(super_t::get_stability_count(), 542 rhs.get_stability_count())); 543 rhs.set_stability_count(0); 544 } 545 546 public: 547 /// \copydoc boost::heap::priority_queue::begin begin(void) const548 iterator begin(void) const 549 { 550 return iterator(trees.begin()); 551 } 552 553 /// \copydoc boost::heap::priority_queue::end end(void) const554 iterator end(void) const 555 { 556 return iterator(trees.end()); 557 } 558 559 /// \copydoc boost::heap::fibonacci_heap::ordered_begin ordered_begin(void) const560 ordered_iterator ordered_begin(void) const 561 { 562 return ordered_iterator(trees.begin(), trees.end(), top_element, super_t::value_comp()); 563 } 564 565 /// \copydoc boost::heap::fibonacci_heap::ordered_end ordered_end(void) const566 ordered_iterator ordered_end(void) const 567 { 568 return ordered_iterator(NULL, super_t::value_comp()); 569 } 570 571 /** 572 * \b Effects: Removes the element handled by \c handle from the priority_queue. 573 * 574 * \b Complexity: Logarithmic. 575 * */ erase(handle_type handle)576 void erase(handle_type handle) 577 { 578 node_pointer n = handle.node_; 579 siftup(n, force_inf()); 580 top_element = n; 581 pop(); 582 } 583 584 /// \copydoc boost::heap::d_ary_heap_mutable::s_handle_from_iterator s_handle_from_iterator(iterator const & it)585 static handle_type s_handle_from_iterator(iterator const & it) 586 { 587 node_type * ptr = const_cast<node_type *>(it.get_node()); 588 return handle_type(ptr); 589 } 590 591 /// \copydoc boost::heap::priority_queue::value_comp value_comp(void) const592 value_compare const & value_comp(void) const 593 { 594 return super_t::value_comp(); 595 } 596 597 /// \copydoc boost::heap::priority_queue::operator<(HeapType const & rhs) const 598 template <typename HeapType> operator <(HeapType const & rhs) const599 bool operator<(HeapType const & rhs) const 600 { 601 return detail::heap_compare(*this, rhs); 602 } 603 604 /// \copydoc boost::heap::priority_queue::operator>(HeapType const & rhs) const 605 template <typename HeapType> operator >(HeapType const & rhs) const606 bool operator>(HeapType const & rhs) const 607 { 608 return detail::heap_compare(rhs, *this); 609 } 610 611 /// \copydoc boost::heap::priority_queue::operator>=(HeapType const & rhs) const 612 template <typename HeapType> operator >=(HeapType const & rhs) const613 bool operator>=(HeapType const & rhs) const 614 { 615 return !operator<(rhs); 616 } 617 618 /// \copydoc boost::heap::priority_queue::operator<=(HeapType const & rhs) const 619 template <typename HeapType> operator <=(HeapType const & rhs) const620 bool operator<=(HeapType const & rhs) const 621 { 622 return !operator>(rhs); 623 } 624 625 /// \copydoc boost::heap::priority_queue::operator==(HeapType const & rhs) const 626 template <typename HeapType> operator ==(HeapType const & rhs) const627 bool operator==(HeapType const & rhs) const 628 { 629 return detail::heap_equality(*this, rhs); 630 } 631 632 /// \copydoc boost::heap::priority_queue::operator!=(HeapType const & rhs) const 633 template <typename HeapType> operator !=(HeapType const & rhs) const634 bool operator!=(HeapType const & rhs) const 635 { 636 return !(*this == rhs); 637 } 638 639 private: 640 #if !defined(BOOST_DOXYGEN_INVOKED) merge_and_clear_nodes(binomial_heap & rhs)641 void merge_and_clear_nodes(binomial_heap & rhs) 642 { 643 BOOST_HEAP_ASSERT (!empty()); 644 BOOST_HEAP_ASSERT (!rhs.empty()); 645 646 node_list_iterator this_iterator = trees.begin(); 647 node_pointer carry_node = NULL; 648 649 while (!rhs.trees.empty()) { 650 node_pointer rhs_node = static_cast<node_pointer>(&rhs.trees.front()); 651 size_type rhs_degree = rhs_node->child_count(); 652 653 if (super_t::operator()(top_element->value, rhs_node->value)) 654 top_element = rhs_node; 655 656 try_again: 657 node_pointer this_node = static_cast<node_pointer>(&*this_iterator); 658 size_type this_degree = this_node->child_count(); 659 sorted_by_degree(); 660 rhs.sorted_by_degree(); 661 662 if (this_degree == rhs_degree) { 663 if (carry_node) { 664 if (carry_node->child_count() < this_degree) { 665 trees.insert(this_iterator, *carry_node); 666 carry_node = NULL; 667 } else { 668 rhs.trees.pop_front(); 669 carry_node = merge_trees(carry_node, rhs_node); 670 } 671 ++this_iterator; 672 } else { 673 this_iterator = trees.erase(this_iterator); 674 rhs.trees.pop_front(); 675 carry_node = merge_trees(this_node, rhs_node); 676 } 677 678 if (this_iterator == trees.end()) 679 break; 680 else 681 continue; 682 } 683 684 if (this_degree < rhs_degree) { 685 if (carry_node) { 686 if (carry_node->child_count() < this_degree) { 687 trees.insert(this_iterator, *carry_node); 688 carry_node = NULL; 689 ++this_iterator; 690 } else if (carry_node->child_count() == rhs_degree) { 691 rhs.trees.pop_front(); 692 carry_node = merge_trees(carry_node, rhs_node); 693 continue; 694 } else { 695 this_iterator = trees.erase(this_iterator); 696 carry_node = merge_trees(this_node, carry_node); 697 } 698 goto try_again; 699 } else { 700 ++this_iterator; 701 if (this_iterator == trees.end()) 702 break; 703 goto try_again; 704 } 705 706 if (this_iterator == trees.end()) 707 break; 708 else 709 continue; 710 } 711 712 if (this_degree > rhs_degree) { 713 rhs.trees.pop_front(); 714 if (carry_node) { 715 if (carry_node->child_count() < rhs_degree) { 716 trees.insert(this_iterator, *carry_node); 717 trees.insert(this_iterator, *rhs_node); 718 carry_node = NULL; 719 } else 720 carry_node = merge_trees(rhs_node, carry_node); 721 } else 722 trees.insert(this_iterator, *rhs_node); 723 } 724 } 725 726 if (!rhs.trees.empty()) { 727 if (carry_node) { 728 node_list_iterator rhs_it = rhs.trees.begin(); 729 while (static_cast<node_pointer>(&*rhs_it)->child_count() < carry_node->child_count()) 730 ++rhs_it; 731 rhs.insert_node(rhs_it, carry_node); 732 rhs.increment(); 733 sorted_by_degree(); 734 rhs.sorted_by_degree(); 735 if (trees.empty()) { 736 trees.splice(trees.end(), rhs.trees, rhs.trees.begin(), rhs.trees.end()); 737 update_top_element(); 738 } else 739 merge_and_clear_nodes(rhs); 740 } else 741 trees.splice(trees.end(), rhs.trees, rhs.trees.begin(), rhs.trees.end()); 742 return; 743 } 744 745 if (carry_node) 746 insert_node(this_iterator, carry_node); 747 } 748 clone_forest(binomial_heap const & rhs)749 void clone_forest(binomial_heap const & rhs) 750 { 751 BOOST_HEAP_ASSERT(trees.empty()); 752 typedef typename node_type::template node_cloner<allocator_type> node_cloner; 753 trees.clone_from(rhs.trees, node_cloner(*this, NULL), detail::nop_disposer()); 754 755 update_top_element(); 756 } 757 758 struct force_inf 759 { 760 template <typename X> operator ()boost::heap::binomial_heap::force_inf761 bool operator()(X const &, X const &) const 762 { 763 return false; 764 } 765 }; 766 767 template <typename Compare> siftup(node_pointer n,Compare const & cmp)768 void siftup(node_pointer n, Compare const & cmp) 769 { 770 while (n->parent) { 771 node_pointer parent = n->parent; 772 node_pointer grand_parent = parent->parent; 773 if (cmp(n->value, parent->value)) 774 return; 775 776 n->remove_from_parent(); 777 778 n->swap_children(parent); 779 n->update_children(); 780 parent->update_children(); 781 782 if (grand_parent) { 783 parent->remove_from_parent(); 784 grand_parent->add_child(n); 785 } else { 786 node_list_iterator it = trees.erase(node_list_type::s_iterator_to(*parent)); 787 trees.insert(it, *n); 788 } 789 n->add_child(parent); 790 BOOST_HEAP_ASSERT(parent->child_count() == n->child_count()); 791 } 792 } 793 siftdown(node_pointer n)794 void siftdown(node_pointer n) 795 { 796 while (n->child_count()) { 797 node_pointer max_child = detail::find_max_child<node_list_type, node_type, internal_compare>(n->children, super_t::get_internal_cmp()); 798 799 if (super_t::operator()(max_child->value, n->value)) 800 return; 801 802 max_child->remove_from_parent(); 803 804 n->swap_children(max_child); 805 n->update_children(); 806 max_child->update_children(); 807 808 node_pointer parent = n->parent; 809 if (parent) { 810 n->remove_from_parent(); 811 max_child->add_child(n); 812 parent->add_child(max_child); 813 } else { 814 node_list_iterator position = trees.erase(node_list_type::s_iterator_to(*n)); 815 max_child->add_child(n); 816 trees.insert(position, *max_child); 817 } 818 } 819 } 820 insert_node(node_list_iterator it,node_pointer n)821 void insert_node(node_list_iterator it, node_pointer n) 822 { 823 if (it != trees.end()) 824 BOOST_HEAP_ASSERT(static_cast<node_pointer>(&*it)->child_count() >= n->child_count()); 825 826 while(true) { 827 BOOST_HEAP_ASSERT(!n->is_linked()); 828 if (it == trees.end()) 829 break; 830 831 node_pointer this_node = static_cast<node_pointer>(&*it); 832 size_type this_degree = this_node->child_count(); 833 size_type n_degree = n->child_count(); 834 if (this_degree == n_degree) { 835 BOOST_HEAP_ASSERT(it->is_linked()); 836 it = trees.erase(it); 837 838 n = merge_trees(n, this_node); 839 } else 840 break; 841 } 842 trees.insert(it, *n); 843 } 844 845 // private constructor, just used in pop() binomial_heap(value_compare const & cmp,node_list_type & child_list,size_type size)846 explicit binomial_heap(value_compare const & cmp, node_list_type & child_list, size_type size): 847 super_t(cmp) 848 { 849 size_holder::set_size(size); 850 if (size) 851 top_element = static_cast<node_pointer>(&*child_list.begin()); // not correct, but we will reset it later 852 else 853 top_element = NULL; 854 855 for (node_list_iterator it = child_list.begin(); it != child_list.end(); ++it) { 856 node_pointer n = static_cast<node_pointer>(&*it); 857 n->parent = NULL; 858 } 859 860 trees.splice(trees.end(), child_list, child_list.begin(), child_list.end()); 861 862 trees.sort(detail::cmp_by_degree<node_type>()); 863 } 864 merge_trees(node_pointer node1,node_pointer node2)865 node_pointer merge_trees (node_pointer node1, node_pointer node2) 866 { 867 BOOST_HEAP_ASSERT(node1->child_count() == node2->child_count()); 868 869 if (super_t::operator()(node1->value, node2->value)) 870 std::swap(node1, node2); 871 872 if (node2->parent) 873 node2->remove_from_parent(); 874 875 node1->add_child(node2); 876 return node1; 877 } 878 update_top_element(void)879 void update_top_element(void) 880 { 881 top_element = detail::find_max_child<node_list_type, node_type, internal_compare>(trees, super_t::get_internal_cmp()); 882 } 883 sorted_by_degree(void) const884 void sorted_by_degree(void) const 885 { 886 #ifdef BOOST_HEAP_SANITYCHECKS 887 int degree = -1; 888 889 for (node_list_const_iterator it = trees.begin(); it != trees.end(); ++it) { 890 const_node_pointer n = static_cast<const_node_pointer>(&*it); 891 BOOST_HEAP_ASSERT(int(n->child_count()) > degree); 892 degree = n->child_count(); 893 894 BOOST_HEAP_ASSERT((detail::is_heap<node_type, super_t>(n, *this))); 895 896 size_type child_nodes = detail::count_nodes<node_type>(n); 897 BOOST_HEAP_ASSERT(child_nodes == size_type(1 << static_cast<const_node_pointer>(&*it)->child_count())); 898 } 899 #endif 900 } 901 sanity_check(void)902 void sanity_check(void) 903 { 904 #ifdef BOOST_HEAP_SANITYCHECKS 905 sorted_by_degree(); 906 907 if (!empty()) { 908 node_pointer found_top = detail::find_max_child<node_list_type, node_type, internal_compare>(trees, super_t::get_internal_cmp()); 909 BOOST_HEAP_ASSERT(top_element == found_top); 910 } 911 912 if (constant_time_size) { 913 size_t counted = detail::count_list_nodes<node_type, node_list_type>(trees); 914 size_t stored = size_holder::get_size(); 915 BOOST_HEAP_ASSERT(counted == stored); 916 } 917 #endif 918 } 919 920 node_pointer top_element; 921 node_list_type trees; 922 #endif // BOOST_DOXYGEN_INVOKED 923 }; 924 925 926 } /* namespace heap */ 927 } /* namespace boost */ 928 929 #undef BOOST_HEAP_ASSERT 930 931 #endif /* BOOST_HEAP_D_ARY_HEAP_HPP */ 932