git.sesse.net Git - casparcg/blob - dependencies64/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     fibonacci_heap(fibonacci_heap & rhs):
 247         super_t(rhs), top_element(rhs.top_element)
 248     {
 249         roots.splice(roots.begin(), rhs.roots);
 250         rhs.top_element = NULL;
 251     }
 252
 253     /// \copydoc boost::heap::priority_queue::operator=(priority_queue &&)
 254     fibonacci_heap & operator=(fibonacci_heap && rhs)
 255     {
 256         clear();
 257
 258         super_t::operator=(std::move(rhs));
 259         roots.splice(roots.begin(), rhs.roots);
 260         top_element = rhs.top_element;
 261         rhs.top_element = NULL;
 262         return *this;
 263     }
 264 #endif
 265
 266     /// \copydoc boost::heap::priority_queue::operator=(priority_queue const &)
 267     fibonacci_heap & operator=(fibonacci_heap const & rhs)
 268     {
 269         clear();
 270         size_holder::set_size(rhs.size());
 271         static_cast<super_t&>(*this) = rhs;
 272
 273         if (rhs.empty())
 274             top_element = NULL;
 275         else
 276             clone_forest(rhs);
 277         return *this;
 278     }
 279
 280     ~fibonacci_heap(void)
 281     {
 282         clear();
 283     }
 284
 285     /// \copydoc boost::heap::priority_queue::empty
 286     bool empty(void) const
 287     {
 288         if (constant_time_size)
 289             return size() == 0;
 290         else
 291             return roots.empty();
 292     }
 293
 294     /// \copydoc boost::heap::priority_queue::size
 295     size_type size(void) const
 296     {
 297         if (constant_time_size)
 298             return size_holder::get_size();
 299
 300         if (empty())
 301             return 0;
 302         else
 303             return detail::count_list_nodes<node, node_list_type>(roots);
 304     }
 305
 306     /// \copydoc boost::heap::priority_queue::max_size
 307     size_type max_size(void) const
 308     {
 309         return allocator_type::max_size();
 310     }
 311
 312     /// \copydoc boost::heap::priority_queue::clear
 313     void clear(void)
 314     {
 315         typedef detail::node_disposer<node, typename node_list_type::value_type, allocator_type> disposer;
 316         roots.clear_and_dispose(disposer(*this));
 317
 318         size_holder::set_size(0);
 319         top_element = NULL;
 320     }
 321
 322     /// \copydoc boost::heap::priority_queue::get_allocator
 323     allocator_type get_allocator(void) const
 324     {
 325         return *this;
 326     }
 327
 328     /// \copydoc boost::heap::priority_queue::swap
 329     void swap(fibonacci_heap & rhs)
 330     {
 331         super_t::swap(rhs);
 332         std::swap(top_element, rhs.top_element);
 333         roots.swap(rhs.roots);
 334     }
 335
 336
 337     /// \copydoc boost::heap::priority_queue::top
 338     value_type const & top(void) const
 339     {
 340         BOOST_ASSERT(!empty());
 341
 342         return super_t::get_value(top_element->value);
 343     }
 344
 345     /**
 346      * \b Effects: Adds a new element to the priority queue. Returns handle to element
 347      *
 348      * \b Complexity: Constant.
 349      *
 350      * \b Note: Does not invalidate iterators.
 351      *
 352      * */
 353     handle_type push(value_type const & v)
 354     {
 355         size_holder::increment();
 356
 357         node_pointer n = allocator_type::allocate(1);
 358
 359         new(n) node(super_t::make_node(v));
 360         roots.push_front(*n);
 361
 362         if (!top_element || super_t::operator()(top_element->value, n->value))
 363             top_element = n;
 364         return handle_type(n);
 365     }
 366
 367 #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES) && !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
 368     /**
 369      * \b Effects: Adds a new element to the priority queue. The element is directly constructed in-place. Returns handle to element.
 370      *
 371      * \b Complexity: Constant.
 372      *
 373      * \b Note: Does not invalidate iterators.
 374      *
 375      * */
 376     template <class... Args>
 377     handle_type emplace(Args&&... args)
 378     {
 379         size_holder::increment();
 380
 381         node_pointer n = allocator_type::allocate(1);
 382
 383         new(n) node(super_t::make_node(std::forward<Args>(args)...));
 384         roots.push_front(*n);
 385
 386         if (!top_element || super_t::operator()(top_element->value, n->value))
 387             top_element = n;
 388         return handle_type(n);
 389     }
 390 #endif
 391
 392     /**
 393      * \b Effects: Removes the top element from the priority queue.
 394      *
 395      * \b Complexity: Logarithmic (amortized). Linear (worst case).
 396      *
 397      * */
 398     void pop(void)
 399     {
 400         BOOST_ASSERT(!empty());
 401
 402         node_pointer element = top_element;
 403         roots.erase(node_list_type::s_iterator_to(*element));
 404
 405         finish_erase_or_pop(element);
 406     }
 407
 408     /**
 409      * \b Effects: Assigns \c v to the element handled by \c handle & updates the priority queue.
 410      *
 411      * \b Complexity: Logarithmic if current value < v, Constant otherwise.
 412      *
 413      * */
 414     void update (handle_type handle, const_reference v)
 415     {
 416         if (super_t::operator()(super_t::get_value(handle.node_->value), v))
 417             increase(handle, v);
 418         else
 419             decrease(handle, v);
 420     }
 421
 422     /** \copydoc boost::heap::fibonacci_heap::update(handle_type, const_reference)
 423      *
 424      * \b Rationale: The lazy update function is a modification of the traditional update, that just invalidates
 425      *               the iterator to the object referred to by the handle.
 426      * */
 427     void update_lazy(handle_type handle, const_reference v)
 428     {
 429         handle.node_->value = super_t::make_node(v);
 430         update_lazy(handle);
 431     }
 432
 433     /**
 434      * \b Effects: Updates the heap after the element handled by \c handle has been changed.
 435      *
 436      * \b Complexity: Logarithmic.
 437      *
 438      * \b Note: If this is not called, after a handle has been updated, the behavior of the data structure is undefined!
 439      * */
 440     void update (handle_type handle)
 441     {
 442         node_pointer n = handle.node_;
 443         node_pointer parent = n->get_parent();
 444
 445         if (parent) {
 446             n->parent = NULL;
 447             roots.splice(roots.begin(), parent->children, node_list_type::s_iterator_to(*n));
 448         }
 449         add_children_to_root(n);
 450         consolidate();
 451     }
 452
 453     /** \copydoc boost::heap::fibonacci_heap::update (handle_type handle)
 454      *
 455      * \b Rationale: The lazy update function is a modification of the traditional update, that just invalidates
 456      *               the iterator to the object referred to by the handle.
 457      * */
 458     void update_lazy (handle_type handle)
 459     {
 460         node_pointer n = handle.node_;
 461         node_pointer parent = n->get_parent();
 462
 463         if (parent) {
 464             n->parent = NULL;
 465             roots.splice(roots.begin(), parent->children, node_list_type::s_iterator_to(*n));
 466         }
 467         add_children_to_root(n);
 468     }
 469
 470
 471      /**
 472      * \b Effects: Assigns \c v to the element handled by \c handle & updates the priority queue.
 473      *
 474      * \b Complexity: Constant.
 475      *
 476      * \b Note: The new value is expected to be greater than the current one
 477      * */
 478     void increase (handle_type handle, const_reference v)
 479     {
 480         handle.node_->value = super_t::make_node(v);
 481         increase(handle);
 482     }
 483
 484     /**
 485      * \b Effects: Updates the heap after the element handled by \c handle has been changed.
 486      *
 487      * \b Complexity: Constant.
 488      *
 489      * \b Note: If this is not called, after a handle has been updated, the behavior of the data structure is undefined!
 490      * */
 491     void increase (handle_type handle)
 492     {
 493         node_pointer n = handle.node_;
 494
 495         if (n->parent) {
 496             if (super_t::operator()(n->get_parent()->value, n->value)) {
 497                 node_pointer parent = n->get_parent();
 498                 cut(n);
 499                 cascading_cut(parent);
 500             }
 501         }
 502
 503         if (super_t::operator()(top_element->value, n->value)) {
 504             top_element = n;
 505             return;
 506         }
 507     }
 508
 509     /**
 510      * \b Effects: Assigns \c v to the element handled by \c handle & updates the priority queue.
 511      *
 512      * \b Complexity: Logarithmic.
 513      *
 514      * \b Note: The new value is expected to be less than the current one
 515      * */
 516     void decrease (handle_type handle, const_reference v)
 517     {
 518         handle.node_->value = super_t::make_node(v);
 519         decrease(handle);
 520     }
 521
 522     /**
 523      * \b Effects: Updates the heap after the element handled by \c handle has been changed.
 524      *
 525      * \b Complexity: Logarithmic.
 526      *
 527      * \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!
 528      * */
 529     void decrease (handle_type handle)
 530     {
 531         update(handle);
 532     }
 533
 534     /**
 535      * \b Effects: Removes the element handled by \c handle from the priority_queue.
 536      *
 537      * \b Complexity: Logarithmic.
 538      * */
 539     void erase(handle_type const & handle)
 540     {
 541         node_pointer element = handle.node_;
 542         node_pointer parent = element->get_parent();
 543
 544         if (parent)
 545             parent->children.erase(node_list_type::s_iterator_to(*element));
 546         else
 547             roots.erase(node_list_type::s_iterator_to(*element));
 548
 549         finish_erase_or_pop(element);
 550     }
 551
 552     /// \copydoc boost::heap::priority_queue::begin
 553     iterator begin(void) const
 554     {
 555         return iterator(roots.begin());
 556     }
 557
 558     /// \copydoc boost::heap::priority_queue::end
 559     iterator end(void) const
 560     {
 561         return iterator(roots.end());
 562     }
 563
 564
 565     /**
 566      * \b Effects: Returns an ordered iterator to the first element contained in the priority queue.
 567      *
 568      * \b Note: Ordered iterators traverse the priority queue in heap order.
 569      * */
 570     ordered_iterator ordered_begin(void) const
 571     {
 572         return ordered_iterator(roots.begin(), roots.end(), top_element, super_t::value_comp());
 573     }
 574
 575     /**
 576      * \b Effects: Returns an ordered iterator to the end of the priority queue.
 577      *
 578      * \b Note: Ordered iterators traverse the priority queue in heap order.
 579      * */
 580     ordered_iterator ordered_end(void) const
 581     {
 582         return ordered_iterator(NULL, super_t::value_comp());
 583     }
 584
 585     /**
 586      * \b Effects: Merge with priority queue rhs.
 587      *
 588      * \b Complexity: Constant.
 589      *
 590      * */
 591     void merge(fibonacci_heap & rhs)
 592     {
 593         size_holder::add(rhs.get_size());
 594
 595         if (!top_element ||
 596             (rhs.top_element && super_t::operator()(top_element->value, rhs.top_element->value)))
 597             top_element = rhs.top_element;
 598
 599         roots.splice(roots.end(), rhs.roots);
 600
 601         rhs.top_element = NULL;
 602         rhs.set_size(0);
 603
 604         super_t::set_stability_count((std::max)(super_t::get_stability_count(),
 605                                      rhs.get_stability_count()));
 606         rhs.set_stability_count(0);
 607     }
 608
 609     /// \copydoc boost::heap::d_ary_heap_mutable::s_handle_from_iterator
 610     static handle_type s_handle_from_iterator(iterator const & it)
 611     {
 612         node * ptr = const_cast<node *>(it.get_node());
 613         return handle_type(ptr);
 614     }
 615
 616     /// \copydoc boost::heap::priority_queue::value_comp
 617     value_compare const & value_comp(void) const
 618     {
 619         return super_t::value_comp();
 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 detail::heap_compare(*this, 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_compare(rhs, *this);
 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 !operator<(rhs);
 641     }
 642
 643     /// \copydoc boost::heap::priority_queue::operator<=(HeapType const & rhs) const
 644     template <typename HeapType>
 645     bool operator<=(HeapType const & rhs) const
 646     {
 647         return !operator>(rhs);
 648     }
 649
 650     /// \copydoc boost::heap::priority_queue::operator==(HeapType const & rhs) const
 651     template <typename HeapType>
 652     bool operator==(HeapType const & rhs) const
 653     {
 654         return detail::heap_equality(*this, rhs);
 655     }
 656
 657     /// \copydoc boost::heap::priority_queue::operator!=(HeapType const & rhs) const
 658     template <typename HeapType>
 659     bool operator!=(HeapType const & rhs) const
 660     {
 661         return !(*this == rhs);
 662     }
 663
 664 private:
 665 #if !defined(BOOST_DOXYGEN_INVOKED)
 666     void clone_forest(fibonacci_heap const & rhs)
 667     {
 668         BOOST_HEAP_ASSERT(roots.empty());
 669         typedef typename node::template node_cloner<allocator_type> node_cloner;
 670         roots.clone_from(rhs.roots, node_cloner(*this, NULL), detail::nop_disposer());
 671
 672         top_element = detail::find_max_child<node_list_type, node, internal_compare>(roots, super_t::get_internal_cmp());
 673     }
 674
 675     void cut(node_pointer n)
 676     {
 677         node_pointer parent = n->get_parent();
 678         roots.splice(roots.begin(), parent->children, node_list_type::s_iterator_to(*n));
 679         n->parent = 0;
 680         n->mark = false;
 681     }
 682
 683     void cascading_cut(node_pointer n)
 684     {
 685         node_pointer parent = n->get_parent();
 686
 687         if (parent) {
 688             if (!parent->mark)
 689                 parent->mark = true;
 690             else {
 691                 cut(n);
 692                 cascading_cut(parent);
 693             }
 694         }
 695     }
 696
 697     void add_children_to_root(node_pointer n)
 698     {
 699         for (node_list_iterator it = n->children.begin(); it != n->children.end(); ++it) {
 700             node_pointer child = static_cast<node_pointer>(&*it);
 701             child->parent = 0;
 702         }
 703
 704         roots.splice(roots.end(), n->children);
 705     }
 706
 707     void consolidate(void)
 708     {
 709         if (roots.empty())
 710             return;
 711
 712         static const size_type max_log2 = sizeof(size_type) * 8;
 713         boost::array<node_pointer, max_log2> aux;
 714         aux.assign(NULL);
 715
 716         node_list_iterator it = roots.begin();
 717         top_element = static_cast<node_pointer>(&*it);
 718
 719         do {
 720             node_pointer n = static_cast<node_pointer>(&*it);
 721             ++it;
 722             size_type node_rank = n->child_count();
 723
 724             if (aux[node_rank] == NULL)
 725                 aux[node_rank] = n;
 726             else {
 727                 do {
 728                     node_pointer other = aux[node_rank];
 729                     if (super_t::operator()(n->value, other->value))
 730                         std::swap(n, other);
 731
 732                     if (other->parent)
 733                         n->children.splice(n->children.end(), other->parent->children, node_list_type::s_iterator_to(*other));
 734                     else
 735                         n->children.splice(n->children.end(), roots, node_list_type::s_iterator_to(*other));
 736
 737                     other->parent = n;
 738
 739                     aux[node_rank] = NULL;
 740                     node_rank = n->child_count();
 741                 } while (aux[node_rank] != NULL);
 742                 aux[node_rank] = n;
 743             }
 744
 745             if (super_t::operator()(top_element->value, n->value))
 746                 top_element = n;
 747         }
 748         while (it != roots.end());
 749     }
 750
 751     void finish_erase_or_pop(node_pointer erased_node)
 752     {
 753         add_children_to_root(erased_node);
 754
 755         erased_node->~node();
 756         allocator_type::deallocate(erased_node, 1);
 757
 758         size_holder::decrement();
 759         if (!empty())
 760             consolidate();
 761         else
 762             top_element = NULL;
 763     }
 764
 765     mutable node_pointer top_element;
 766     node_list_type roots;
 767 #endif
 768 };
 769
 770 } /* namespace heap */
 771 } /* namespace boost */
 772
 773 #undef BOOST_HEAP_ASSERT
 774
 775 #endif /* BOOST_HEAP_FIBONACCI_HEAP_HPP */