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