ceph/src/boost/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 #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     {
  66         type(compare_argument const & arg):
  67             base_type(arg)
  68         {}
  69
  70 #ifndef BOOST_NO_CXX11_RVALUE_REFERENCES
  71         type(type const & rhs):
  72             base_type(rhs), allocator_type(rhs)
  73         {}
  74
  75         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
  80         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
  87         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 &)
 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 &)
 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 &)
 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 &&)
 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 &&)
 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
 276     ~binomial_heap(void)
 277     {
 278         clear();
 279     }
 280
 281     /// \copydoc boost::heap::priority_queue::empty
 282     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      * */
 293     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
 305     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
 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
 322     allocator_type get_allocator(void) const
 323     {
 324         return *this;
 325     }
 326
 327     /// \copydoc boost::heap::priority_queue::swap
 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
 336     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      * */
 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>
 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      * */
 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      * */
 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      * */
 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      * */
 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      * */
 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      * */
 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      * */
 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      * */
 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
 555     iterator begin(void) const
 556     {
 557         return iterator(trees.begin());
 558     }
 559
 560     /// \copydoc boost::heap::priority_queue::end
 561     iterator end(void) const
 562     {
 563         return iterator(trees.end());
 564     }
 565
 566     /// \copydoc boost::heap::fibonacci_heap::ordered_begin
 567     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
 573     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      * */
 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
 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
 599     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>
 606     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>
 613     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>
 620     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>
 627     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>
 634     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>
 641     bool operator!=(HeapType const & rhs) const
 642     {
 643         return !(*this == rhs);
 644     }
 645
 646 private:
 647 #if !defined(BOOST_DOXYGEN_INVOKED)
 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
 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>
 768         bool operator()(X const &, X const &) const
 769         {
 770             return false;
 771         }
 772     };
 773
 774     template <typename Compare>
 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
 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
 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()
 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
 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
 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
 890     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
 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 */