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