ceph/src/boost/boost/heap/fibonacci_heap.hpp

   1 // boost heap: fibonacci 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_FIBONACCI_HEAP_HPP
  10 #define BOOST_HEAP_FIBONACCI_HEAP_HPP
  11
  12 #include <algorithm>
  13 #include <utility>
  14 #include <vector>
  15
  16 #include <boost/array.hpp>
  17 #include <boost/assert.hpp>
  18
  19 #include <boost/heap/detail/heap_comparison.hpp>
  20 #include <boost/heap/detail/heap_node.hpp>
  21 #include <boost/heap/detail/stable_heap.hpp>
  22 #include <boost/heap/detail/tree_iterator.hpp>
  23
  24 #ifdef BOOST_HAS_PRAGMA_ONCE
  25 #pragma once
  26 #endif
  27
  28
  29 #ifndef BOOST_DOXYGEN_INVOKED
  30 #ifdef BOOST_HEAP_SANITYCHECKS
  31 #define BOOST_HEAP_ASSERT BOOST_ASSERT
  32 #else
  33 #define BOOST_HEAP_ASSERT(expression)
  34 #endif
  35 #endif
  36
  37 namespace boost  {
  38 namespace heap   {
  39 namespace detail {
  40
  41 typedef parameter::parameters<boost::parameter::optional<tag::allocator>,
  42                               boost::parameter::optional<tag::compare>,
  43                               boost::parameter::optional<tag::stable>,
  44                               boost::parameter::optional<tag::constant_time_size>,
  45                               boost::parameter::optional<tag::stability_counter_type>
  46                              > fibonacci_heap_signature;
  47
  48 template <typename T, typename Parspec>
  49 struct make_fibonacci_heap_base
  50 {
  51     static const bool constant_time_size = parameter::binding<Parspec,
  52                                                               tag::constant_time_size,
  53                                                               boost::mpl::true_
  54                                                              >::type::value;
  55
  56     typedef typename detail::make_heap_base<T, Parspec, constant_time_size>::type base_type;
  57     typedef typename detail::make_heap_base<T, Parspec, constant_time_size>::allocator_argument allocator_argument;
  58     typedef typename detail::make_heap_base<T, Parspec, constant_time_size>::compare_argument compare_argument;
  59     typedef marked_heap_node<typename base_type::internal_type> node_type;
  60
  61     typedef typename allocator_argument::template rebind<node_type>::other allocator_type;
  62
  63     struct type:
  64         base_type,
  65         allocator_type
  66     {
  67         type(compare_argument const & arg):
  68             base_type(arg)
  69         {}
  70
  71         type(type const & rhs):
  72             base_type(static_cast<base_type const &>(rhs)),
  73             allocator_type(static_cast<allocator_type const &>(rhs))
  74         {}
  75
  76         type & operator=(type const & rhs)
  77         {
  78             base_type::operator=(static_cast<base_type const &>(rhs));
  79             allocator_type::operator=(static_cast<allocator_type const &>(rhs));
  80             return *this;
  81         }
  82
  83 #ifndef BOOST_NO_CXX11_RVALUE_REFERENCES
  84         type(type && rhs):
  85             base_type(std::move(static_cast<base_type&>(rhs))),
  86             allocator_type(std::move(static_cast<allocator_type&>(rhs)))
  87         {}
  88
  89         type & operator=(type && rhs)
  90         {
  91             base_type::operator=(std::move(static_cast<base_type&>(rhs)));
  92             allocator_type::operator=(std::move(static_cast<allocator_type&>(rhs)));
  93             return *this;
  94         }
  95 #endif
  96     };
  97 };
  98
  99 }
 100
 101
 102
 103 /**
 104  * \class fibonacci_heap
 105  * \brief fibonacci 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           class A4 = boost::parameter::void_
 127          >
 128 #endif
 129 class fibonacci_heap:
 130     private detail::make_fibonacci_heap_base<T,
 131                                              typename detail::fibonacci_heap_signature::bind<A0, A1, A2, A3, A4>::type
 132                                             >::type
 133 {
 134     typedef typename detail::fibonacci_heap_signature::bind<A0, A1, A2, A3, A4>::type bound_args;
 135     typedef detail::make_fibonacci_heap_base<T, bound_args> base_maker;
 136     typedef typename base_maker::type super_t;
 137
 138     typedef typename super_t::size_holder_type size_holder;
 139     typedef typename super_t::internal_type internal_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 private:
 146 #ifndef BOOST_DOXYGEN_INVOKED
 147     struct implementation_defined:
 148         detail::extract_allocator_types<typename base_maker::allocator_argument>
 149     {
 150         typedef T value_type;
 151         typedef typename detail::extract_allocator_types<typename base_maker::allocator_argument>::size_type size_type;
 152         typedef typename detail::extract_allocator_types<typename base_maker::allocator_argument>::reference reference;
 153
 154         typedef typename base_maker::compare_argument value_compare;
 155         typedef typename base_maker::allocator_type allocator_type;
 156
 157         typedef typename allocator_type::pointer node_pointer;
 158         typedef typename allocator_type::const_pointer const_node_pointer;
 159
 160         typedef detail::heap_node_list node_list_type;
 161         typedef typename node_list_type::iterator node_list_iterator;
 162         typedef typename node_list_type::const_iterator node_list_const_iterator;
 163
 164         typedef typename base_maker::node_type node;
 165
 166         typedef detail::value_extractor<value_type, internal_type, super_t> value_extractor;
 167         typedef typename super_t::internal_compare internal_compare;
 168         typedef detail::node_handle<node_pointer, super_t, reference> handle_type;
 169
 170         typedef detail::recursive_tree_iterator<node,
 171                                                 node_list_const_iterator,
 172                                                 const value_type,
 173                                                 value_extractor,
 174                                                 detail::list_iterator_converter<node, node_list_type>
 175                                                > iterator;
 176         typedef iterator const_iterator;
 177
 178         typedef detail::tree_iterator<node,
 179                                       const value_type,
 180                                       allocator_type,
 181                                       value_extractor,
 182                                       detail::list_iterator_converter<node, node_list_type>,
 183                                       true,
 184                                       true,
 185                                       value_compare
 186                                     > ordered_iterator;
 187     };
 188
 189     typedef typename implementation_defined::node node;
 190     typedef typename implementation_defined::node_pointer node_pointer;
 191     typedef typename implementation_defined::node_list_type node_list_type;
 192     typedef typename implementation_defined::node_list_iterator node_list_iterator;
 193     typedef typename implementation_defined::node_list_const_iterator node_list_const_iterator;
 194     typedef typename implementation_defined::internal_compare internal_compare;
 195 #endif
 196
 197 public:
 198     typedef T value_type;
 199
 200     typedef typename implementation_defined::size_type size_type;
 201     typedef typename implementation_defined::difference_type difference_type;
 202     typedef typename implementation_defined::value_compare value_compare;
 203     typedef typename implementation_defined::allocator_type allocator_type;
 204     typedef typename implementation_defined::reference reference;
 205     typedef typename implementation_defined::const_reference const_reference;
 206     typedef typename implementation_defined::pointer pointer;
 207     typedef typename implementation_defined::const_pointer const_pointer;
 208     /// \copydoc boost::heap::priority_queue::iterator
 209     typedef typename implementation_defined::iterator iterator;
 210     typedef typename implementation_defined::const_iterator const_iterator;
 211     typedef typename implementation_defined::ordered_iterator ordered_iterator;
 212
 213     typedef typename implementation_defined::handle_type handle_type;
 214
 215     static const bool constant_time_size = base_maker::constant_time_size;
 216     static const bool has_ordered_iterators = true;
 217     static const bool is_mergable = true;
 218     static const bool is_stable = detail::extract_stable<bound_args>::value;
 219     static const bool has_reserve = false;
 220
 221     /// \copydoc boost::heap::priority_queue::priority_queue(value_compare const &)
 222     explicit fibonacci_heap(value_compare const & cmp = value_compare()):
 223         super_t(cmp), top_element(0)
 224     {}
 225
 226     /// \copydoc boost::heap::priority_queue::priority_queue(priority_queue const &)
 227     fibonacci_heap(fibonacci_heap const & rhs):
 228         super_t(rhs), top_element(0)
 229     {
 230         if (rhs.empty())
 231             return;
 232
 233         clone_forest(rhs);
 234         size_holder::set_size(rhs.size());
 235     }
 236
 237 #ifndef BOOST_NO_CXX11_RVALUE_REFERENCES
 238     /// \copydoc boost::heap::priority_queue::priority_queue(priority_queue &&)
 239     fibonacci_heap(fibonacci_heap && rhs):
 240         super_t(std::move(rhs)), top_element(rhs.top_element)
 241     {
 242         roots.splice(roots.begin(), rhs.roots);
 243         rhs.top_element = NULL;
 244     }
 245
 246     /// \copydoc boost::heap::priority_queue::operator=(priority_queue &&)
 247     fibonacci_heap & operator=(fibonacci_heap && rhs)
 248     {
 249         clear();
 250
 251         super_t::operator=(std::move(rhs));
 252         roots.splice(roots.begin(), rhs.roots);
 253         top_element = rhs.top_element;
 254         rhs.top_element = NULL;
 255         return *this;
 256     }
 257 #endif
 258
 259     /// \copydoc boost::heap::priority_queue::operator=(priority_queue const &)
 260     fibonacci_heap & operator=(fibonacci_heap const & rhs)
 261     {
 262         clear();
 263         size_holder::set_size(rhs.size());
 264         static_cast<super_t&>(*this) = rhs;
 265
 266         if (rhs.empty())
 267             top_element = NULL;
 268         else
 269             clone_forest(rhs);
 270         return *this;
 271     }
 272
 273     ~fibonacci_heap(void)
 274     {
 275         clear();
 276     }
 277
 278     /// \copydoc boost::heap::priority_queue::empty
 279     bool empty(void) const
 280     {
 281         if (constant_time_size)
 282             return size() == 0;
 283         else
 284             return roots.empty();
 285     }
 286
 287     /// \copydoc boost::heap::priority_queue::size
 288     size_type size(void) const
 289     {
 290         if (constant_time_size)
 291             return size_holder::get_size();
 292
 293         if (empty())
 294             return 0;
 295         else
 296             return detail::count_list_nodes<node, node_list_type>(roots);
 297     }
 298
 299     /// \copydoc boost::heap::priority_queue::max_size
 300     size_type max_size(void) const
 301     {
 302         return allocator_type::max_size();
 303     }
 304
 305     /// \copydoc boost::heap::priority_queue::clear
 306     void clear(void)
 307     {
 308         typedef detail::node_disposer<node, typename node_list_type::value_type, allocator_type> disposer;
 309         roots.clear_and_dispose(disposer(*this));
 310
 311         size_holder::set_size(0);
 312         top_element = NULL;
 313     }
 314
 315     /// \copydoc boost::heap::priority_queue::get_allocator
 316     allocator_type get_allocator(void) const
 317     {
 318         return *this;
 319     }
 320
 321     /// \copydoc boost::heap::priority_queue::swap
 322     void swap(fibonacci_heap & rhs)
 323     {
 324         super_t::swap(rhs);
 325         std::swap(top_element, rhs.top_element);
 326         roots.swap(rhs.roots);
 327     }
 328
 329
 330     /// \copydoc boost::heap::priority_queue::top
 331     value_type const & top(void) const
 332     {
 333         BOOST_ASSERT(!empty());
 334
 335         return super_t::get_value(top_element->value);
 336     }
 337
 338     /**
 339      * \b Effects: Adds a new element to the priority queue. Returns handle to element
 340      *
 341      * \b Complexity: Constant.
 342      *
 343      * \b Note: Does not invalidate iterators.
 344      *
 345      * */
 346     handle_type push(value_type const & v)
 347     {
 348         size_holder::increment();
 349
 350         node_pointer n = allocator_type::allocate(1);
 351
 352         new(n) node(super_t::make_node(v));
 353         roots.push_front(*n);
 354
 355         if (!top_element || super_t::operator()(top_element->value, n->value))
 356             top_element = n;
 357         return handle_type(n);
 358     }
 359
 360 #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES) && !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
 361     /**
 362      * \b Effects: Adds a new element to the priority queue. The element is directly constructed in-place. Returns handle to element.
 363      *
 364      * \b Complexity: Constant.
 365      *
 366      * \b Note: Does not invalidate iterators.
 367      *
 368      * */
 369     template <class... Args>
 370     handle_type emplace(Args&&... args)
 371     {
 372         size_holder::increment();
 373
 374         node_pointer n = allocator_type::allocate(1);
 375
 376         new(n) node(super_t::make_node(std::forward<Args>(args)...));
 377         roots.push_front(*n);
 378
 379         if (!top_element || super_t::operator()(top_element->value, n->value))
 380             top_element = n;
 381         return handle_type(n);
 382     }
 383 #endif
 384
 385     /**
 386      * \b Effects: Removes the top element from the priority queue.
 387      *
 388      * \b Complexity: Logarithmic (amortized). Linear (worst case).
 389      *
 390      * */
 391     void pop(void)
 392     {
 393         BOOST_ASSERT(!empty());
 394
 395         node_pointer element = top_element;
 396         roots.erase(node_list_type::s_iterator_to(*element));
 397
 398         finish_erase_or_pop(element);
 399     }
 400
 401     /**
 402      * \b Effects: Assigns \c v to the element handled by \c handle & updates the priority queue.
 403      *
 404      * \b Complexity: Logarithmic if current value < v, Constant otherwise.
 405      *
 406      * */
 407     void update (handle_type handle, const_reference v)
 408     {
 409         if (super_t::operator()(super_t::get_value(handle.node_->value), v))
 410             increase(handle, v);
 411         else
 412             decrease(handle, v);
 413     }
 414
 415     /** \copydoc boost::heap::fibonacci_heap::update(handle_type, const_reference)
 416      *
 417      * \b Rationale: The lazy update function is a modification of the traditional update, that just invalidates
 418      *               the iterator to the object referred to by the handle.
 419      * */
 420     void update_lazy(handle_type handle, const_reference v)
 421     {
 422         handle.node_->value = super_t::make_node(v);
 423         update_lazy(handle);
 424     }
 425
 426     /**
 427      * \b Effects: Updates the heap after the element handled by \c handle has been changed.
 428      *
 429      * \b Complexity: Logarithmic.
 430      *
 431      * \b Note: If this is not called, after a handle has been updated, the behavior of the data structure is undefined!
 432      * */
 433     void update (handle_type handle)
 434     {
 435         update_lazy(handle);
 436         consolidate();
 437     }
 438
 439     /** \copydoc boost::heap::fibonacci_heap::update (handle_type handle)
 440      *
 441      * \b Rationale: The lazy update function is a modification of the traditional update, that just invalidates
 442      *               the iterator to the object referred to by the handle.
 443      * */
 444     void update_lazy (handle_type handle)
 445     {
 446         node_pointer n = handle.node_;
 447         node_pointer parent = n->get_parent();
 448
 449         if (parent) {
 450             n->parent = NULL;
 451             roots.splice(roots.begin(), parent->children, node_list_type::s_iterator_to(*n));
 452         }
 453         add_children_to_root(n);
 454
 455         if (super_t::operator()(top_element->value, n->value))
 456             top_element = n;
 457     }
 458
 459
 460      /**
 461      * \b Effects: Assigns \c v to the element handled by \c handle & updates the priority queue.
 462      *
 463      * \b Complexity: Constant.
 464      *
 465      * \b Note: The new value is expected to be greater than the current one
 466      * */
 467     void increase (handle_type handle, const_reference v)
 468     {
 469         handle.node_->value = super_t::make_node(v);
 470         increase(handle);
 471     }
 472
 473     /**
 474      * \b Effects: Updates the heap after the element handled by \c handle has been changed.
 475      *
 476      * \b Complexity: Constant.
 477      *
 478      * \b Note: If this is not called, after a handle has been updated, the behavior of the data structure is undefined!
 479      * */
 480     void increase (handle_type handle)
 481     {
 482         node_pointer n = handle.node_;
 483
 484         if (n->parent) {
 485             if (super_t::operator()(n->get_parent()->value, n->value)) {
 486                 node_pointer parent = n->get_parent();
 487                 cut(n);
 488                 cascading_cut(parent);
 489             }
 490         }
 491
 492         if (super_t::operator()(top_element->value, n->value)) {
 493             top_element = n;
 494             return;
 495         }
 496     }
 497
 498     /**
 499      * \b Effects: Assigns \c v to the element handled by \c handle & updates the priority queue.
 500      *
 501      * \b Complexity: Logarithmic.
 502      *
 503      * \b Note: The new value is expected to be less than the current one
 504      * */
 505     void decrease (handle_type handle, const_reference v)
 506     {
 507         handle.node_->value = super_t::make_node(v);
 508         decrease(handle);
 509     }
 510
 511     /**
 512      * \b Effects: Updates the heap after the element handled by \c handle has been changed.
 513      *
 514      * \b Complexity: Logarithmic.
 515      *
 516      * \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!
 517      * */
 518     void decrease (handle_type handle)
 519     {
 520         update(handle);
 521     }
 522
 523     /**
 524      * \b Effects: Removes the element handled by \c handle from the priority_queue.
 525      *
 526      * \b Complexity: Logarithmic.
 527      * */
 528     void erase(handle_type const & handle)
 529     {
 530         node_pointer element = handle.node_;
 531         node_pointer parent = element->get_parent();
 532
 533         if (parent)
 534             parent->children.erase(node_list_type::s_iterator_to(*element));
 535         else
 536             roots.erase(node_list_type::s_iterator_to(*element));
 537
 538         finish_erase_or_pop(element);
 539     }
 540
 541     /// \copydoc boost::heap::priority_queue::begin
 542     iterator begin(void) const
 543     {
 544         return iterator(roots.begin());
 545     }
 546
 547     /// \copydoc boost::heap::priority_queue::end
 548     iterator end(void) const
 549     {
 550         return iterator(roots.end());
 551     }
 552
 553
 554     /**
 555      * \b Effects: Returns an ordered iterator to the first element contained in the priority queue.
 556      *
 557      * \b Note: Ordered iterators traverse the priority queue in heap order.
 558      * */
 559     ordered_iterator ordered_begin(void) const
 560     {
 561         return ordered_iterator(roots.begin(), roots.end(), top_element, super_t::value_comp());
 562     }
 563
 564     /**
 565      * \b Effects: Returns an ordered iterator to the end of the priority queue.
 566      *
 567      * \b Note: Ordered iterators traverse the priority queue in heap order.
 568      * */
 569     ordered_iterator ordered_end(void) const
 570     {
 571         return ordered_iterator(NULL, super_t::value_comp());
 572     }
 573
 574     /**
 575      * \b Effects: Merge with priority queue rhs.
 576      *
 577      * \b Complexity: Constant.
 578      *
 579      * */
 580     void merge(fibonacci_heap & rhs)
 581     {
 582         size_holder::add(rhs.get_size());
 583
 584         if (!top_element ||
 585             (rhs.top_element && super_t::operator()(top_element->value, rhs.top_element->value)))
 586             top_element = rhs.top_element;
 587
 588         roots.splice(roots.end(), rhs.roots);
 589
 590         rhs.top_element = NULL;
 591         rhs.set_size(0);
 592
 593         super_t::set_stability_count((std::max)(super_t::get_stability_count(),
 594                                      rhs.get_stability_count()));
 595         rhs.set_stability_count(0);
 596     }
 597
 598     /// \copydoc boost::heap::d_ary_heap_mutable::s_handle_from_iterator
 599     static handle_type s_handle_from_iterator(iterator const & it)
 600     {
 601         node * ptr = const_cast<node *>(it.get_node());
 602         return handle_type(ptr);
 603     }
 604
 605     /// \copydoc boost::heap::priority_queue::value_comp
 606     value_compare const & value_comp(void) const
 607     {
 608         return super_t::value_comp();
 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(*this, rhs);
 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 detail::heap_compare(rhs, *this);
 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 !operator>(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 detail::heap_equality(*this, rhs);
 644     }
 645
 646     /// \copydoc boost::heap::priority_queue::operator!=(HeapType const & rhs) const
 647     template <typename HeapType>
 648     bool operator!=(HeapType const & rhs) const
 649     {
 650         return !(*this == rhs);
 651     }
 652
 653 private:
 654 #if !defined(BOOST_DOXYGEN_INVOKED)
 655     void clone_forest(fibonacci_heap const & rhs)
 656     {
 657         BOOST_HEAP_ASSERT(roots.empty());
 658         typedef typename node::template node_cloner<allocator_type> node_cloner;
 659         roots.clone_from(rhs.roots, node_cloner(*this, NULL), detail::nop_disposer());
 660
 661         top_element = detail::find_max_child<node_list_type, node, internal_compare>(roots, super_t::get_internal_cmp());
 662     }
 663
 664     void cut(node_pointer n)
 665     {
 666         node_pointer parent = n->get_parent();
 667         roots.splice(roots.begin(), parent->children, node_list_type::s_iterator_to(*n));
 668         n->parent = 0;
 669         n->mark = false;
 670     }
 671
 672     void cascading_cut(node_pointer n)
 673     {
 674         node_pointer parent = n->get_parent();
 675
 676         if (parent) {
 677             if (!parent->mark)
 678                 parent->mark = true;
 679             else {
 680                 cut(n);
 681                 cascading_cut(parent);
 682             }
 683         }
 684     }
 685
 686     void add_children_to_root(node_pointer n)
 687     {
 688         for (node_list_iterator it = n->children.begin(); it != n->children.end(); ++it) {
 689             node_pointer child = static_cast<node_pointer>(&*it);
 690             child->parent = 0;
 691         }
 692
 693         roots.splice(roots.end(), n->children);
 694     }
 695
 696     void consolidate(void)
 697     {
 698         if (roots.empty())
 699             return;
 700
 701         static const size_type max_log2 = sizeof(size_type) * 8;
 702         boost::array<node_pointer, max_log2> aux;
 703         aux.assign(NULL);
 704
 705         node_list_iterator it = roots.begin();
 706         top_element = static_cast<node_pointer>(&*it);
 707
 708         do {
 709             node_pointer n = static_cast<node_pointer>(&*it);
 710             ++it;
 711             size_type node_rank = n->child_count();
 712
 713             if (aux[node_rank] == NULL)
 714                 aux[node_rank] = n;
 715             else {
 716                 do {
 717                     node_pointer other = aux[node_rank];
 718                     if (super_t::operator()(n->value, other->value))
 719                         std::swap(n, other);
 720
 721                     if (other->parent)
 722                         n->children.splice(n->children.end(), other->parent->children, node_list_type::s_iterator_to(*other));
 723                     else
 724                         n->children.splice(n->children.end(), roots, node_list_type::s_iterator_to(*other));
 725
 726                     other->parent = n;
 727
 728                     aux[node_rank] = NULL;
 729                     node_rank = n->child_count();
 730                 } while (aux[node_rank] != NULL);
 731                 aux[node_rank] = n;
 732             }
 733
 734             if (!super_t::operator()(n->value, top_element->value))
 735                 top_element = n;
 736         }
 737         while (it != roots.end());
 738     }
 739
 740     void finish_erase_or_pop(node_pointer erased_node)
 741     {
 742         add_children_to_root(erased_node);
 743
 744         erased_node->~node();
 745         allocator_type::deallocate(erased_node, 1);
 746
 747         size_holder::decrement();
 748         if (!empty())
 749             consolidate();
 750         else
 751             top_element = NULL;
 752     }
 753
 754     mutable node_pointer top_element;
 755     node_list_type roots;
 756 #endif
 757 };
 758
 759 } /* namespace heap */
 760 } /* namespace boost */
 761
 762 #undef BOOST_HEAP_ASSERT
 763
 764 #endif /* BOOST_HEAP_FIBONACCI_HEAP_HPP */