ceph/src/boost/libs/heap/include/boost/heap/binomial_heap.hpp

   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     {
  65         type(compare_argument const & arg):
  66             base_type(arg)
  67         {}
  68
  69 #ifndef BOOST_NO_CXX11_RVALUE_REFERENCES
  70         type(type const & rhs):
  71             base_type(rhs), allocator_type(rhs)
  72         {}
  73
  74         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
  79         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
  86         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 &)
 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 &)
 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 &)
 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 &&)
 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 &&)
 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
 275     ~binomial_heap(void)
 276     {
 277         clear();
 278     }
 279
 280     /// \copydoc boost::heap::priority_queue::empty
 281     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      * */
 292     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
 304     size_type max_size(void) const
 305     {
 306         return allocator_type::max_size();
 307     }
 308
 309     /// \copydoc boost::heap::priority_queue::clear
 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
 320     allocator_type get_allocator(void) const
 321     {
 322         return *this;
 323     }
 324
 325     /// \copydoc boost::heap::priority_queue::swap
 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
 334     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      * */
 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>
 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      * */
 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                 size_t size = constant_time_size ? size_holder::get_size()
 408                                                  : 0;
 409                 swap(children);
 410                 super_t::set_stability_count(stability_count);
 411
 412                 if (constant_time_size)
 413                     size_holder::set_size( size );
 414             } else
 415                 merge_and_clear_nodes(children);
 416
 417         }
 418
 419         if (trees.empty())
 420             top_element = NULL;
 421         else
 422             update_top_element();
 423
 424         element->~node_type();
 425         allocator_type::deallocate(element, 1);
 426         sanity_check();
 427     }
 428
 429     /**
 430      * \b Effects: Assigns \c v to the element handled by \c handle & updates the priority queue.
 431      *
 432      * \b Complexity: Logarithmic.
 433      *
 434      * */
 435     void update (handle_type handle, const_reference v)
 436     {
 437         if (super_t::operator()(super_t::get_value(handle.node_->value), v))
 438             increase(handle, v);
 439         else
 440             decrease(handle, v);
 441     }
 442
 443     /**
 444      * \b Effects: Updates the heap after the element handled by \c handle has been changed.
 445      *
 446      * \b Complexity: Logarithmic.
 447      *
 448      * \b Note: If this is not called, after a handle has been updated, the behavior of the data structure is undefined!
 449      * */
 450     void update (handle_type handle)
 451     {
 452         node_pointer this_node = handle.node_;
 453
 454         if (this_node->parent) {
 455             if (super_t::operator()(super_t::get_value(this_node->parent->value), super_t::get_value(this_node->value)))
 456                 increase(handle);
 457             else
 458                 decrease(handle);
 459         }
 460         else
 461             decrease(handle);
 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      * \b Note: The new value is expected to be greater than the current one
 470      * */
 471     void increase (handle_type handle, const_reference v)
 472     {
 473         handle.node_->value = super_t::make_node(v);
 474         increase(handle);
 475     }
 476
 477     /**
 478      * \b Effects: Updates the heap after the element handled by \c handle has been changed.
 479      *
 480      * \b Complexity: Logarithmic.
 481      *
 482      * \b Note: If this is not called, after a handle has been updated, the behavior of the data structure is undefined!
 483      * */
 484     void increase (handle_type handle)
 485     {
 486         node_pointer n = handle.node_;
 487         siftup(n, *this);
 488
 489         update_top_element();
 490         sanity_check();
 491     }
 492
 493     /**
 494      * \b Effects: Assigns \c v to the element handled by \c handle & updates the priority queue.
 495      *
 496      * \b Complexity: Logarithmic.
 497      *
 498      * \b Note: The new value is expected to be less than the current one
 499      * */
 500     void decrease (handle_type handle, const_reference v)
 501     {
 502         handle.node_->value = super_t::make_node(v);
 503         decrease(handle);
 504     }
 505
 506     /**
 507      * \b Effects: Updates the heap after the element handled by \c handle has been changed.
 508      *
 509      * \b Complexity: Logarithmic.
 510      *
 511      * \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!
 512      * */
 513     void decrease (handle_type handle)
 514     {
 515         node_pointer n = handle.node_;
 516
 517         siftdown(n);
 518
 519         update_top_element();
 520     }
 521
 522     /**
 523      * \b Effects: Merge with priority queue rhs.
 524      *
 525      * \b Complexity: Logarithmic.
 526      *
 527      * */
 528     void merge(binomial_heap & rhs)
 529     {
 530         if (rhs.empty())
 531             return;
 532
 533         if (empty()) {
 534             swap(rhs);
 535             return;
 536         }
 537
 538         size_type new_size = size_holder::get_size() + rhs.get_size();
 539         merge_and_clear_nodes(rhs);
 540
 541         size_holder::set_size(new_size);
 542         rhs.set_size(0);
 543         rhs.top_element = NULL;
 544
 545         super_t::set_stability_count((std::max)(super_t::get_stability_count(),
 546                                      rhs.get_stability_count()));
 547         rhs.set_stability_count(0);
 548     }
 549
 550 public:
 551     /// \copydoc boost::heap::priority_queue::begin
 552     iterator begin(void) const
 553     {
 554         return iterator(trees.begin());
 555     }
 556
 557     /// \copydoc boost::heap::priority_queue::end
 558     iterator end(void) const
 559     {
 560         return iterator(trees.end());
 561     }
 562
 563     /// \copydoc boost::heap::fibonacci_heap::ordered_begin
 564     ordered_iterator ordered_begin(void) const
 565     {
 566         return ordered_iterator(trees.begin(), trees.end(), top_element, super_t::value_comp());
 567     }
 568
 569     /// \copydoc boost::heap::fibonacci_heap::ordered_end
 570     ordered_iterator ordered_end(void) const
 571     {
 572         return ordered_iterator(NULL, super_t::value_comp());
 573     }
 574
 575     /**
 576      * \b Effects: Removes the element handled by \c handle from the priority_queue.
 577      *
 578      * \b Complexity: Logarithmic.
 579      * */
 580     void erase(handle_type handle)
 581     {
 582         node_pointer n = handle.node_;
 583         siftup(n, force_inf());
 584         top_element = n;
 585         pop();
 586     }
 587
 588     /// \copydoc boost::heap::d_ary_heap_mutable::s_handle_from_iterator
 589     static handle_type s_handle_from_iterator(iterator const & it)
 590     {
 591         node_type * ptr = const_cast<node_type *>(it.get_node());
 592         return handle_type(ptr);
 593     }
 594
 595     /// \copydoc boost::heap::priority_queue::value_comp
 596     value_compare const & value_comp(void) const
 597     {
 598         return super_t::value_comp();
 599     }
 600
 601     /// \copydoc boost::heap::priority_queue::operator<(HeapType const & rhs) const
 602     template <typename HeapType>
 603     bool operator<(HeapType const & rhs) const
 604     {
 605         return detail::heap_compare(*this, rhs);
 606     }
 607
 608     /// \copydoc boost::heap::priority_queue::operator>(HeapType const & rhs) const
 609     template <typename HeapType>
 610     bool operator>(HeapType const & rhs) const
 611     {
 612         return detail::heap_compare(rhs, *this);
 613     }
 614
 615     /// \copydoc boost::heap::priority_queue::operator>=(HeapType const & rhs) const
 616     template <typename HeapType>
 617     bool operator>=(HeapType const & rhs) const
 618     {
 619         return !operator<(rhs);
 620     }
 621
 622     /// \copydoc boost::heap::priority_queue::operator<=(HeapType const & rhs) const
 623     template <typename HeapType>
 624     bool operator<=(HeapType const & rhs) const
 625     {
 626         return !operator>(rhs);
 627     }
 628
 629     /// \copydoc boost::heap::priority_queue::operator==(HeapType const & rhs) const
 630     template <typename HeapType>
 631     bool operator==(HeapType const & rhs) const
 632     {
 633         return detail::heap_equality(*this, rhs);
 634     }
 635
 636     /// \copydoc boost::heap::priority_queue::operator!=(HeapType const & rhs) const
 637     template <typename HeapType>
 638     bool operator!=(HeapType const & rhs) const
 639     {
 640         return !(*this == rhs);
 641     }
 642
 643 private:
 644 #if !defined(BOOST_DOXYGEN_INVOKED)
 645     void merge_and_clear_nodes(binomial_heap & rhs)
 646     {
 647         BOOST_HEAP_ASSERT (!empty());
 648         BOOST_HEAP_ASSERT (!rhs.empty());
 649
 650         node_list_iterator this_iterator = trees.begin();
 651         node_pointer carry_node = NULL;
 652
 653         while (!rhs.trees.empty()) {
 654             node_pointer rhs_node = static_cast<node_pointer>(&rhs.trees.front());
 655             size_type rhs_degree = rhs_node->child_count();
 656
 657             if (super_t::operator()(top_element->value, rhs_node->value))
 658                 top_element = rhs_node;
 659
 660         try_again:
 661             node_pointer this_node = static_cast<node_pointer>(&*this_iterator);
 662             size_type this_degree = this_node->child_count();
 663             sorted_by_degree();
 664             rhs.sorted_by_degree();
 665
 666             if (this_degree == rhs_degree) {
 667                 if (carry_node) {
 668                     if (carry_node->child_count() < this_degree) {
 669                         trees.insert(this_iterator, *carry_node);
 670                         carry_node = NULL;
 671                     } else {
 672                         rhs.trees.pop_front();
 673                         carry_node = merge_trees(carry_node, rhs_node);
 674                     }
 675                     ++this_iterator;
 676                 } else {
 677                     this_iterator = trees.erase(this_iterator);
 678                     rhs.trees.pop_front();
 679                     carry_node = merge_trees(this_node, rhs_node);
 680                 }
 681
 682                 if (this_iterator == trees.end())
 683                     break;
 684                 else
 685                     continue;
 686             }
 687
 688             if (this_degree < rhs_degree) {
 689                 if (carry_node) {
 690                     if (carry_node->child_count() < this_degree) {
 691                         trees.insert(this_iterator, *carry_node);
 692                         carry_node = NULL;
 693                         ++this_iterator;
 694                     } else if (carry_node->child_count() == rhs_degree) {
 695                         rhs.trees.pop_front();
 696                         carry_node = merge_trees(carry_node, rhs_node);
 697                         continue;
 698                     } else {
 699                         this_iterator = trees.erase(this_iterator);
 700                         carry_node = merge_trees(this_node, carry_node);
 701                     }
 702                     goto try_again;
 703                 } else {
 704                     ++this_iterator;
 705                     if (this_iterator == trees.end())
 706                         break;
 707                     goto try_again;
 708                 }
 709
 710                 if (this_iterator == trees.end())
 711                     break;
 712                 else
 713                     continue;
 714             }
 715
 716             if (this_degree > rhs_degree) {
 717                 rhs.trees.pop_front();
 718                 if (carry_node) {
 719                     if (carry_node->child_count() < rhs_degree) {
 720                         trees.insert(this_iterator, *carry_node);
 721                         trees.insert(this_iterator, *rhs_node);
 722                         carry_node = NULL;
 723                     } else
 724                         carry_node = merge_trees(rhs_node, carry_node);
 725                 } else
 726                     trees.insert(this_iterator, *rhs_node);
 727             }
 728         }
 729
 730         if (!rhs.trees.empty()) {
 731             if (carry_node) {
 732                 node_list_iterator rhs_it = rhs.trees.begin();
 733                 while (static_cast<node_pointer>(&*rhs_it)->child_count() < carry_node->child_count())
 734                     ++rhs_it;
 735                 rhs.insert_node(rhs_it, carry_node);
 736                 rhs.increment();
 737                 sorted_by_degree();
 738                 rhs.sorted_by_degree();
 739                 if (trees.empty()) {
 740                     trees.splice(trees.end(), rhs.trees, rhs.trees.begin(), rhs.trees.end());
 741                     update_top_element();
 742                 } else
 743                     merge_and_clear_nodes(rhs);
 744             } else
 745                 trees.splice(trees.end(), rhs.trees, rhs.trees.begin(), rhs.trees.end());
 746             return;
 747         }
 748
 749         if (carry_node)
 750             insert_node(this_iterator, carry_node);
 751     }
 752
 753     void clone_forest(binomial_heap const & rhs)
 754     {
 755         BOOST_HEAP_ASSERT(trees.empty());
 756         typedef typename node_type::template node_cloner<allocator_type> node_cloner;
 757         trees.clone_from(rhs.trees, node_cloner(*this, NULL), detail::nop_disposer());
 758
 759         update_top_element();
 760     }
 761
 762     struct force_inf
 763     {
 764         template <typename X>
 765         bool operator()(X const &, X const &) const
 766         {
 767             return false;
 768         }
 769     };
 770
 771     template <typename Compare>
 772     void siftup(node_pointer n, Compare const & cmp)
 773     {
 774         while (n->parent) {
 775             node_pointer parent = n->parent;
 776             node_pointer grand_parent = parent->parent;
 777             if (cmp(n->value, parent->value))
 778                 return;
 779
 780             n->remove_from_parent();
 781
 782             n->swap_children(parent);
 783             n->update_children();
 784             parent->update_children();
 785
 786             if (grand_parent) {
 787                 parent->remove_from_parent();
 788                 grand_parent->add_child(n);
 789             } else {
 790                 node_list_iterator it = trees.erase(node_list_type::s_iterator_to(*parent));
 791                 trees.insert(it, *n);
 792             }
 793             n->add_child(parent);
 794         }
 795     }
 796
 797     void siftdown(node_pointer n)
 798     {
 799         while (n->child_count()) {
 800             node_pointer max_child = detail::find_max_child<node_list_type, node_type, internal_compare>(n->children, super_t::get_internal_cmp());
 801
 802             if (super_t::operator()(max_child->value, n->value))
 803                 return;
 804
 805             max_child->remove_from_parent();
 806
 807             n->swap_children(max_child);
 808             n->update_children();
 809             max_child->update_children();
 810
 811             node_pointer parent = n->parent;
 812             if (parent) {
 813                 n->remove_from_parent();
 814                 max_child->add_child(n);
 815                 parent->add_child(max_child);
 816             } else {
 817                 node_list_iterator position = trees.erase(node_list_type::s_iterator_to(*n));
 818                 max_child->add_child(n);
 819                 trees.insert(position, *max_child);
 820             }
 821         }
 822     }
 823
 824     void insert_node(node_list_iterator it, node_pointer n)
 825     {
 826         if (it != trees.end())
 827             BOOST_HEAP_ASSERT(static_cast<node_pointer>(&*it)->child_count() >= n->child_count());
 828
 829         while(true) {
 830             BOOST_HEAP_ASSERT(!n->is_linked());
 831             if (it == trees.end())
 832                 break;
 833
 834             node_pointer this_node = static_cast<node_pointer>(&*it);
 835             size_type this_degree = this_node->child_count();
 836             size_type n_degree = n->child_count();
 837             if (this_degree == n_degree) {
 838                 BOOST_HEAP_ASSERT(it->is_linked());
 839                 it = trees.erase(it);
 840
 841                 n = merge_trees(n, this_node);
 842             } else
 843                 break;
 844         }
 845         trees.insert(it, *n);
 846     }
 847
 848     // private constructor, just used in pop()
 849     explicit binomial_heap(value_compare const & cmp, node_list_type & child_list, size_type size):
 850         super_t(cmp)
 851     {
 852         size_holder::set_size(size);
 853         if (size)
 854             top_element = static_cast<node_pointer>(&*child_list.begin()); // not correct, but we will reset it later
 855         else
 856             top_element = NULL;
 857
 858         for (node_list_iterator it = child_list.begin(); it != child_list.end(); ++it) {
 859             node_pointer n = static_cast<node_pointer>(&*it);
 860             n->parent = NULL;
 861         }
 862
 863         trees.splice(trees.end(), child_list, child_list.begin(), child_list.end());
 864
 865         trees.sort(detail::cmp_by_degree<node_type>());
 866     }
 867
 868     node_pointer merge_trees (node_pointer node1, node_pointer node2)
 869     {
 870         BOOST_HEAP_ASSERT(node1->child_count() == node2->child_count());
 871
 872         if (super_t::operator()(node1->value, node2->value))
 873             std::swap(node1, node2);
 874
 875         if (node2->parent)
 876             node2->remove_from_parent();
 877
 878         node1->add_child(node2);
 879         return node1;
 880     }
 881
 882     void update_top_element(void)
 883     {
 884         top_element = detail::find_max_child<node_list_type, node_type, internal_compare>(trees, super_t::get_internal_cmp());
 885     }
 886
 887     void sorted_by_degree(void) const
 888     {
 889 #ifdef BOOST_HEAP_SANITYCHECKS
 890         int degree = -1;
 891
 892         for (node_list_const_iterator it = trees.begin(); it != trees.end(); ++it) {
 893             const_node_pointer n = static_cast<const_node_pointer>(&*it);
 894             BOOST_HEAP_ASSERT(int(n->child_count()) > degree);
 895             degree = n->child_count();
 896
 897             BOOST_HEAP_ASSERT((detail::is_heap<node_type, super_t>(n, *this)));
 898
 899             size_type child_nodes = detail::count_nodes<node_type>(n);
 900             BOOST_HEAP_ASSERT(child_nodes == size_type(1 << static_cast<const_node_pointer>(&*it)->child_count()));
 901         }
 902 #endif
 903     }
 904
 905     void sanity_check(void)
 906     {
 907 #ifdef BOOST_HEAP_SANITYCHECKS
 908         sorted_by_degree();
 909
 910         if (!empty()) {
 911             node_pointer found_top = detail::find_max_child<node_list_type, node_type, internal_compare>(trees, super_t::get_internal_cmp());
 912             BOOST_HEAP_ASSERT(top_element == found_top);
 913         }
 914
 915         if (constant_time_size) {
 916             size_t counted = detail::count_list_nodes<node_type, node_list_type>(trees);
 917             size_t stored = size_holder::get_size();
 918             BOOST_HEAP_ASSERT(counted == stored);
 919         }
 920 #endif
 921     }
 922
 923     node_pointer top_element;
 924     node_list_type trees;
 925 #endif // BOOST_DOXYGEN_INVOKED
 926 };
 927
 928
 929 } /* namespace heap */
 930 } /* namespace boost */
 931
 932 #undef BOOST_HEAP_ASSERT
 933
 934 #endif /* BOOST_HEAP_D_ARY_HEAP_HPP */