boost/heap/fibonacci_heap.hpp

0001 // boost heap: fibonacci heap
0002 //
0003 // Copyright (C) 2010 Tim Blechmann
0004 //
0005 // Distributed under the Boost Software License, Version 1.0. (See
0006 // accompanying file LICENSE_1_0.txt or copy at
0007 // http://www.boost.org/LICENSE_1_0.txt)
0008
0009 #ifndef BOOST_HEAP_FIBONACCI_HEAP_HPP
0010 #define BOOST_HEAP_FIBONACCI_HEAP_HPP
0011
0012 #include <algorithm>
0013 #include <array>
0014 #include <type_traits>
0015 #include <utility>
0016
0017 #include <boost/assert.hpp>
0018
0019 #include <boost/heap/detail/heap_comparison.hpp>
0020 #include <boost/heap/detail/heap_node.hpp>
0021 #include <boost/heap/detail/stable_heap.hpp>
0022 #include <boost/heap/detail/tree_iterator.hpp>
0023 #include <boost/type_traits/integral_constant.hpp>
0024
0025 #ifdef BOOST_HAS_PRAGMA_ONCE
0026 #    pragma once
0027 #endif
0028
0029
0030 #ifndef BOOST_DOXYGEN_INVOKED
0031 #    ifdef BOOST_HEAP_SANITYCHECKS
0032 #        define BOOST_HEAP_ASSERT BOOST_ASSERT
0033 #    else
0034 #        define BOOST_HEAP_ASSERT( expression ) static_assert( true, "force semicolon" )
0035 #    endif
0036 #endif
0037
0038 namespace boost { namespace heap {
0039 namespace detail {
0040
0041 typedef parameter::parameters< boost::parameter::optional< tag::allocator >,
0042                                boost::parameter::optional< tag::compare >,
0043                                boost::parameter::optional< tag::stable >,
0044                                boost::parameter::optional< tag::constant_time_size >,
0045                                boost::parameter::optional< tag::stability_counter_type > >
0046     fibonacci_heap_signature;
0047
0048 template < typename T, typename Parspec >
0049 struct make_fibonacci_heap_base
0050 {
0051     static const bool constant_time_size
0052         = parameter::binding< Parspec, tag::constant_time_size, std::true_type >::type::value;
0053
0054     typedef typename detail::make_heap_base< T, Parspec, constant_time_size >::type               base_type;
0055     typedef typename detail::make_heap_base< T, Parspec, constant_time_size >::allocator_argument allocator_argument;
0056     typedef typename detail::make_heap_base< T, Parspec, constant_time_size >::compare_argument   compare_argument;
0057     typedef marked_heap_node< typename base_type::internal_type >                                 node_type;
0058
0059     typedef typename boost::allocator_rebind< allocator_argument, node_type >::type allocator_type;
0060
0061     struct type : base_type, allocator_type
0062     {
0063         type( compare_argument const& arg ) :
0064             base_type( arg )
0065         {}
0066
0067         type( allocator_type const& arg ) :
0068             allocator_type( arg )
0069         {}
0070
0071         type( type const& rhs ) :
0072             base_type( static_cast< base_type const& >( rhs ) ),
0073             allocator_type( static_cast< allocator_type const& >( rhs ) )
0074         {}
0075
0076         type& operator=( type const& rhs )
0077         {
0078             base_type::operator=( static_cast< base_type const& >( rhs ) );
0079             allocator_type::operator=( static_cast< allocator_type const& >( rhs ) );
0080             return *this;
0081         }
0082
0083         type( type&& rhs ) :
0084             base_type( std::move( static_cast< base_type& >( rhs ) ) ),
0085             allocator_type( std::move( static_cast< allocator_type& >( rhs ) ) )
0086         {}
0087
0088         type& operator=( type&& rhs )
0089         {
0090             base_type::operator=( std::move( static_cast< base_type& >( rhs ) ) );
0091             allocator_type::operator=( std::move( static_cast< allocator_type& >( rhs ) ) );
0092             return *this;
0093         }
0094     };
0095 };
0096
0097 } // namespace detail
0098
0099
0100 /**
0101  * \class fibonacci_heap
0102  * \brief fibonacci heap
0103  *
0104  * The template parameter T is the type to be managed by the container.
0105  * The user can specify additional options and if no options are provided default options are used.
0106  *
0107  * The container supports the following options:
0108  * - \c boost::heap::stable<>, defaults to \c stable<false>
0109  * - \c boost::heap::compare<>, defaults to \c compare<std::less<T> >
0110  * - \c boost::heap::allocator<>, defaults to \c allocator<std::allocator<T> >
0111  * - \c boost::heap::constant_time_size<>, defaults to \c constant_time_size<true>
0112  * - \c boost::heap::stability_counter_type<>, defaults to \c stability_counter_type<boost::uintmax_t>
0113  *
0114  */
0115 #ifdef BOOST_DOXYGEN_INVOKED
0116 template < class T, class... Options >
0117 #else
0118 template < typename T,
0119            class A0 = boost::parameter::void_,
0120            class A1 = boost::parameter::void_,
0121            class A2 = boost::parameter::void_,
0122            class A3 = boost::parameter::void_,
0123            class A4 = boost::parameter::void_ >
0124 #endif
0125 class fibonacci_heap :
0126     private detail::
0127         make_fibonacci_heap_base< T, typename detail::fibonacci_heap_signature::bind< A0, A1, A2, A3, A4 >::type >::type
0128 {
0129     typedef typename detail::fibonacci_heap_signature::bind< A0, A1, A2, A3, A4 >::type bound_args;
0130     typedef detail::make_fibonacci_heap_base< T, bound_args >                           base_maker;
0131     typedef typename base_maker::type                                                   super_t;
0132
0133     typedef typename super_t::size_holder_type      size_holder;
0134     typedef typename super_t::internal_type         internal_type;
0135     typedef typename base_maker::allocator_argument allocator_argument;
0136
0137     template < typename Heap1, typename Heap2 >
0138     friend struct heap_merge_emulate;
0139
0140 private:
0141 #ifndef BOOST_DOXYGEN_INVOKED
0142     struct implementation_defined : detail::extract_allocator_types< typename base_maker::allocator_argument >
0143     {
0144         typedef T value_type;
0145         typedef typename detail::extract_allocator_types< typename base_maker::allocator_argument >::size_type size_type;
0146         typedef typename detail::extract_allocator_types< typename base_maker::allocator_argument >::reference reference;
0147
0148         typedef typename base_maker::compare_argument value_compare;
0149         typedef typename base_maker::allocator_type   allocator_type;
0150
0151         typedef typename boost::allocator_pointer< allocator_type >::type       node_pointer;
0152         typedef typename boost::allocator_const_pointer< allocator_type >::type const_node_pointer;
0153
0154         typedef detail::heap_node_list                  node_list_type;
0155         typedef typename node_list_type::iterator       node_list_iterator;
0156         typedef typename node_list_type::const_iterator node_list_const_iterator;
0157
0158         typedef typename base_maker::node_type node;
0159
0160         typedef detail::value_extractor< value_type, internal_type, super_t > value_extractor;
0161         typedef typename super_t::internal_compare                            internal_compare;
0162         typedef detail::node_handle< node_pointer, super_t, reference >       handle_type;
0163
0164         typedef detail::recursive_tree_iterator< node,
0165                                                  node_list_const_iterator,
0166                                                  const value_type,
0167                                                  value_extractor,
0168                                                  detail::list_iterator_converter< node, node_list_type > >
0169                          iterator;
0170         typedef iterator const_iterator;
0171
0172         typedef detail::tree_iterator< node,
0173                                        const value_type,
0174                                        allocator_type,
0175                                        value_extractor,
0176                                        detail::list_iterator_converter< node, node_list_type >,
0177                                        true,
0178                                        true,
0179                                        value_compare >
0180             ordered_iterator;
0181     };
0182
0183     typedef typename implementation_defined::node                     node;
0184     typedef typename implementation_defined::node_pointer             node_pointer;
0185     typedef typename implementation_defined::node_list_type           node_list_type;
0186     typedef typename implementation_defined::node_list_iterator       node_list_iterator;
0187     typedef typename implementation_defined::node_list_const_iterator node_list_const_iterator;
0188     typedef typename implementation_defined::internal_compare         internal_compare;
0189 #endif
0190
0191 public:
0192     typedef T value_type;
0193
0194     typedef typename implementation_defined::size_type        size_type;
0195     typedef typename implementation_defined::difference_type  difference_type;
0196     typedef typename implementation_defined::value_compare    value_compare;
0197     typedef typename implementation_defined::allocator_type   allocator_type;
0198     typedef typename implementation_defined::reference        reference;
0199     typedef typename implementation_defined::const_reference  const_reference;
0200     typedef typename implementation_defined::pointer          pointer;
0201     typedef typename implementation_defined::const_pointer    const_pointer;
0202     /// \copydoc boost::heap::priority_queue::iterator
0203     typedef typename implementation_defined::iterator         iterator;
0204     typedef typename implementation_defined::const_iterator   const_iterator;
0205     typedef typename implementation_defined::ordered_iterator ordered_iterator;
0206
0207     typedef typename implementation_defined::handle_type handle_type;
0208
0209     static const bool constant_time_size    = base_maker::constant_time_size;
0210     static const bool has_ordered_iterators = true;
0211     static const bool is_mergable           = true;
0212     static const bool is_stable             = detail::extract_stable< bound_args >::value;
0213     static const bool has_reserve           = false;
0214
0215     /// \copydoc boost::heap::priority_queue::priority_queue(value_compare const &)
0216     explicit fibonacci_heap( value_compare const& cmp = value_compare() ) :
0217         super_t( cmp ),
0218         top_element( 0 )
0219     {}
0220
0221     /// \copydoc boost::heap::priority_queue::priority_queue(allocator_type const &)
0222     explicit fibonacci_heap( allocator_type const& alloc ) :
0223         super_t( alloc ),
0224         top_element( 0 )
0225     {}
0226
0227     /// \copydoc boost::heap::priority_queue::priority_queue(priority_queue const &)
0228     fibonacci_heap( fibonacci_heap const& rhs ) :
0229         super_t( rhs ),
0230         top_element( 0 )
0231     {
0232         if ( rhs.empty() )
0233             return;
0234
0235         clone_forest( rhs );
0236         size_holder::set_size( rhs.size() );
0237     }
0238
0239     /// \copydoc boost::heap::priority_queue::priority_queue(priority_queue &&)
0240     fibonacci_heap( fibonacci_heap&& rhs ) :
0241         super_t( std::move( rhs ) ),
0242         top_element( rhs.top_element )
0243     {
0244         roots.splice( roots.begin(), rhs.roots );
0245         rhs.top_element = nullptr;
0246     }
0247
0248     /// \copydoc boost::heap::priority_queue::operator=(priority_queue &&)
0249     fibonacci_heap& operator=( fibonacci_heap&& rhs )
0250     {
0251         clear();
0252
0253         super_t::operator=( std::move( rhs ) );
0254         roots.splice( roots.begin(), rhs.roots );
0255         top_element     = rhs.top_element;
0256         rhs.top_element = nullptr;
0257         return *this;
0258     }
0259
0260     /// \copydoc boost::heap::priority_queue::operator=(priority_queue const &)
0261     fibonacci_heap& operator=( fibonacci_heap const& rhs )
0262     {
0263         clear();
0264         size_holder::set_size( rhs.size() );
0265         static_cast< super_t& >( *this ) = rhs;
0266
0267         if ( rhs.empty() )
0268             top_element = nullptr;
0269         else
0270             clone_forest( rhs );
0271         return *this;
0272     }
0273
0274     ~fibonacci_heap( void )
0275     {
0276         clear();
0277     }
0278
0279     /// \copydoc boost::heap::priority_queue::empty
0280     bool empty( void ) const
0281     {
0282         if ( constant_time_size )
0283             return size() == 0;
0284         else
0285             return roots.empty();
0286     }
0287
0288     /// \copydoc boost::heap::priority_queue::size
0289     size_type size( void ) const
0290     {
0291         if ( constant_time_size )
0292             return size_holder::get_size();
0293
0294         if ( empty() )
0295             return 0;
0296         else
0297             return detail::count_list_nodes< node, node_list_type >( roots );
0298     }
0299
0300     /// \copydoc boost::heap::priority_queue::max_size
0301     size_type max_size( void ) const
0302     {
0303         const allocator_type& alloc = *this;
0304         return boost::allocator_max_size( alloc );
0305     }
0306
0307     /// \copydoc boost::heap::priority_queue::clear
0308     void clear( void )
0309     {
0310         typedef detail::node_disposer< node, typename node_list_type::value_type, allocator_type > disposer;
0311         roots.clear_and_dispose( disposer( *this ) );
0312
0313         size_holder::set_size( 0 );
0314         top_element = nullptr;
0315     }
0316
0317     /// \copydoc boost::heap::priority_queue::get_allocator
0318     allocator_type get_allocator( void ) const
0319     {
0320         return *this;
0321     }
0322
0323     /// \copydoc boost::heap::priority_queue::swap
0324     void swap( fibonacci_heap& rhs )
0325     {
0326         super_t::swap( rhs );
0327         std::swap( top_element, rhs.top_element );
0328         roots.swap( rhs.roots );
0329     }
0330
0331
0332     /// \copydoc boost::heap::priority_queue::top
0333     value_type const& top( void ) const
0334     {
0335         BOOST_ASSERT( !empty() );
0336
0337         return super_t::get_value( top_element->value );
0338     }
0339
0340     /**
0341      * \b Effects: Adds a new element to the priority queue. Returns handle to element
0342      *
0343      * \b Complexity: Constant.
0344      *
0345      * \b Note: Does not invalidate iterators.
0346      *
0347      * */
0348     handle_type push( value_type const& v )
0349     {
0350         size_holder::increment();
0351
0352         allocator_type& alloc = *this;
0353         node_pointer    n     = alloc.allocate( 1 );
0354         new ( n ) node( super_t::make_node( v ) );
0355         roots.push_front( *n );
0356
0357         if ( !top_element || super_t::operator()( top_element->value, n->value ) )
0358             top_element = n;
0359         return handle_type( n );
0360     }
0361
0362     /**
0363      * \b Effects: Adds a new element to the priority queue. The element is directly constructed in-place. Returns
0364      * handle to element.
0365      *
0366      * \b Complexity: Constant.
0367      *
0368      * \b Note: Does not invalidate iterators.
0369      *
0370      * */
0371     template < class... Args >
0372     handle_type emplace( Args&&... args )
0373     {
0374         size_holder::increment();
0375
0376         allocator_type& alloc = *this;
0377         node_pointer    n     = alloc.allocate( 1 );
0378         new ( n ) node( super_t::make_node( std::forward< Args >( args )... ) );
0379         roots.push_front( *n );
0380
0381         if ( !top_element || super_t::operator()( top_element->value, n->value ) )
0382             top_element = n;
0383         return handle_type( n );
0384     }
0385
0386     /**
0387      * \b Effects: Removes the top element from the priority queue.
0388      *
0389      * \b Complexity: Logarithmic (amortized). Linear (worst case).
0390      *
0391      * */
0392     void pop( void )
0393     {
0394         BOOST_ASSERT( !empty() );
0395
0396         node_pointer element = top_element;
0397         roots.erase( node_list_type::s_iterator_to( *element ) );
0398
0399         finish_erase_or_pop( element );
0400     }
0401
0402     /**
0403      * \b Effects: Assigns \c v to the element handled by \c handle & updates the priority queue.
0404      *
0405      * \b Complexity: Logarithmic if current value < v, Constant otherwise.
0406      *
0407      * */
0408     void update( handle_type handle, const_reference v )
0409     {
0410         if ( super_t::operator()( super_t::get_value( handle.node_->value ), v ) )
0411             increase( handle, v );
0412         else
0413             decrease( handle, v );
0414     }
0415
0416     /** \copydoc boost::heap::fibonacci_heap::update(handle_type, const_reference)
0417      *
0418      * \b Rationale: The lazy update function is a modification of the traditional update, that just invalidates
0419      *               the iterator to the object referred to by the handle.
0420      * */
0421     void update_lazy( handle_type handle, const_reference v )
0422     {
0423         handle.node_->value = super_t::make_node( v );
0424         update_lazy( handle );
0425     }
0426
0427     /**
0428      * \b Effects: Updates the heap after the element handled by \c handle has been changed.
0429      *
0430      * \b Complexity: Logarithmic.
0431      *
0432      * \b Note: If this is not called, after a handle has been updated, the behavior of the data structure is undefined!
0433      * */
0434     void update( handle_type handle )
0435     {
0436         update_lazy( handle );
0437         consolidate();
0438     }
0439
0440     /** \copydoc boost::heap::fibonacci_heap::update (handle_type handle)
0441      *
0442      * \b Rationale: The lazy update function is a modification of the traditional update, that just invalidates
0443      *               the iterator to the object referred to by the handle.
0444      * */
0445     void update_lazy( handle_type handle )
0446     {
0447         node_pointer n      = handle.node_;
0448         node_pointer parent = n->get_parent();
0449
0450         if ( parent ) {
0451             n->parent = nullptr;
0452             roots.splice( roots.begin(), parent->children, node_list_type::s_iterator_to( *n ) );
0453         }
0454         add_children_to_root( n );
0455
0456         if ( super_t::operator()( top_element->value, n->value ) )
0457             top_element = n;
0458     }
0459
0460
0461     /**
0462      * \b Effects: Assigns \c v to the element handled by \c handle & updates the priority queue.
0463      *
0464      * \b Complexity: Constant.
0465      *
0466      * \b Note: The new value is expected to be greater than the current one
0467      * */
0468     void increase( handle_type handle, const_reference v )
0469     {
0470         handle.node_->value = super_t::make_node( v );
0471         increase( handle );
0472     }
0473
0474     /**
0475      * \b Effects: Updates the heap after the element handled by \c handle has been changed.
0476      *
0477      * \b Complexity: Constant.
0478      *
0479      * \b Note: If this is not called, after a handle has been updated, the behavior of the data structure is undefined!
0480      * */
0481     void increase( handle_type handle )
0482     {
0483         node_pointer n = handle.node_;
0484
0485         if ( n->parent ) {
0486             if ( super_t::operator()( n->get_parent()->value, n->value ) ) {
0487                 node_pointer parent = n->get_parent();
0488                 cut( n );
0489                 cascading_cut( parent );
0490             }
0491         }
0492
0493         if ( super_t::operator()( top_element->value, n->value ) ) {
0494             top_element = n;
0495             return;
0496         }
0497     }
0498
0499     /**
0500      * \b Effects: Assigns \c v to the element handled by \c handle & updates the priority queue.
0501      *
0502      * \b Complexity: Logarithmic.
0503      *
0504      * \b Note: The new value is expected to be less than the current one
0505      * */
0506     void decrease( handle_type handle, const_reference v )
0507     {
0508         handle.node_->value = super_t::make_node( v );
0509         decrease( handle );
0510     }
0511
0512     /**
0513      * \b Effects: Updates the heap after the element handled by \c handle has been changed.
0514      *
0515      * \b Complexity: Logarithmic.
0516      *
0517      * \b Note: The new value is expected to be less than the current one. If this is not called, after a handle has
0518      * been updated, the behavior of the data structure is undefined!
0519      * */
0520     void decrease( handle_type handle )
0521     {
0522         update( handle );
0523     }
0524
0525     /**
0526      * \b Effects: Removes the element handled by \c handle from the priority_queue.
0527      *
0528      * \b Complexity: Logarithmic.
0529      * */
0530     void erase( handle_type const& handle )
0531     {
0532         node_pointer element = handle.node_;
0533         node_pointer parent  = element->get_parent();
0534
0535         if ( parent )
0536             parent->children.erase( node_list_type::s_iterator_to( *element ) );
0537         else
0538             roots.erase( node_list_type::s_iterator_to( *element ) );
0539
0540         finish_erase_or_pop( element );
0541     }
0542
0543     /// \copydoc boost::heap::priority_queue::begin
0544     iterator begin( void ) const
0545     {
0546         return iterator( roots.begin() );
0547     }
0548
0549     /// \copydoc boost::heap::priority_queue::end
0550     iterator end( void ) const
0551     {
0552         return iterator( roots.end() );
0553     }
0554
0555
0556     /**
0557      * \b Effects: Returns an ordered iterator to the first element contained in the priority queue.
0558      *
0559      * \b Note: Ordered iterators traverse the priority queue in heap order.
0560      * */
0561     ordered_iterator ordered_begin( void ) const
0562     {
0563         return ordered_iterator( roots.begin(), roots.end(), top_element, super_t::value_comp() );
0564     }
0565
0566     /**
0567      * \b Effects: Returns an ordered iterator to the end of the priority queue.
0568      *
0569      * \b Note: Ordered iterators traverse the priority queue in heap order.
0570      * */
0571     ordered_iterator ordered_end( void ) const
0572     {
0573         return ordered_iterator( nullptr, super_t::value_comp() );
0574     }
0575
0576     /**
0577      * \b Effects: Merge with priority queue rhs.
0578      *
0579      * \b Complexity: Constant.
0580      *
0581      * */
0582     void merge( fibonacci_heap& rhs )
0583     {
0584         size_holder::add( rhs.get_size() );
0585
0586         if ( !top_element || ( rhs.top_element && super_t::operator()( top_element->value, rhs.top_element->value ) ) )
0587             top_element = rhs.top_element;
0588
0589         roots.splice( roots.end(), rhs.roots );
0590
0591         rhs.top_element = nullptr;
0592         rhs.set_size( 0 );
0593
0594         super_t::set_stability_count( ( std::max )( super_t::get_stability_count(), rhs.get_stability_count() ) );
0595         rhs.set_stability_count( 0 );
0596     }
0597
0598     /// \copydoc boost::heap::d_ary_heap_mutable::s_handle_from_iterator
0599     static handle_type s_handle_from_iterator( iterator const& it )
0600     {
0601         node* ptr = const_cast< node* >( it.get_node() );
0602         return handle_type( ptr );
0603     }
0604
0605     /// \copydoc boost::heap::priority_queue::value_comp
0606     value_compare const& value_comp( void ) const
0607     {
0608         return super_t::value_comp();
0609     }
0610
0611     /// \copydoc boost::heap::priority_queue::operator<(HeapType const & rhs) const
0612     template < typename HeapType >
0613     bool operator<( HeapType const& rhs ) const
0614     {
0615         return detail::heap_compare( *this, rhs );
0616     }
0617
0618     /// \copydoc boost::heap::priority_queue::operator>(HeapType const & rhs) const
0619     template < typename HeapType >
0620     bool operator>( HeapType const& rhs ) const
0621     {
0622         return detail::heap_compare( rhs, *this );
0623     }
0624
0625     /// \copydoc boost::heap::priority_queue::operator>=(HeapType const & rhs) const
0626     template < typename HeapType >
0627     bool operator>=( HeapType const& rhs ) const
0628     {
0629         return !operator<( rhs );
0630     }
0631
0632     /// \copydoc boost::heap::priority_queue::operator<=(HeapType const & rhs) const
0633     template < typename HeapType >
0634     bool operator<=( HeapType const& rhs ) const
0635     {
0636         return !operator>( rhs );
0637     }
0638
0639     /// \copydoc boost::heap::priority_queue::operator==(HeapType const & rhs) const
0640     template < typename HeapType >
0641     bool operator==( HeapType const& rhs ) const
0642     {
0643         return detail::heap_equality( *this, rhs );
0644     }
0645
0646     /// \copydoc boost::heap::priority_queue::operator!=(HeapType const & rhs) const
0647     template < typename HeapType >
0648     bool operator!=( HeapType const& rhs ) const
0649     {
0650         return !( *this == rhs );
0651     }
0652
0653 private:
0654 #if !defined( BOOST_DOXYGEN_INVOKED )
0655     void clone_forest( fibonacci_heap const& rhs )
0656     {
0657         BOOST_HEAP_ASSERT( roots.empty() );
0658         typedef typename node::template node_cloner< allocator_type > node_cloner;
0659         roots.clone_from( rhs.roots, node_cloner( *this, nullptr ), detail::nop_disposer() );
0660
0661         top_element
0662             = detail::find_max_child< node_list_type, node, internal_compare >( roots, super_t::get_internal_cmp() );
0663     }
0664
0665     void cut( node_pointer n )
0666     {
0667         node_pointer parent = n->get_parent();
0668         roots.splice( roots.begin(), parent->children, node_list_type::s_iterator_to( *n ) );
0669         n->parent = 0;
0670         n->mark   = false;
0671     }
0672
0673     void cascading_cut( node_pointer n )
0674     {
0675         node_pointer parent = n->get_parent();
0676
0677         if ( parent ) {
0678             if ( !parent->mark )
0679                 parent->mark = true;
0680             else {
0681                 cut( n );
0682                 cascading_cut( parent );
0683             }
0684         }
0685     }
0686
0687     void add_children_to_root( node_pointer n )
0688     {
0689         for ( node_list_iterator it = n->children.begin(); it != n->children.end(); ++it ) {
0690             node_pointer child = static_cast< node_pointer >( &*it );
0691             child->parent      = 0;
0692         }
0693
0694         roots.splice( roots.end(), n->children );
0695     }
0696
0697     void consolidate( void )
0698     {
0699         if ( roots.empty() )
0700             return;
0701
0702         static const size_type               max_log2 = sizeof( size_type ) * 8;
0703         std::array< node_pointer, max_log2 > aux {};
0704
0705         node_list_iterator it = roots.begin();
0706         top_element           = static_cast< node_pointer >( &*it );
0707
0708         do {
0709             node_pointer n = static_cast< node_pointer >( &*it );
0710             ++it;
0711             size_type node_rank = n->child_count();
0712
0713             if ( aux[ node_rank ] == nullptr )
0714                 aux[ node_rank ] = n;
0715             else {
0716                 do {
0717                     node_pointer other = aux[ node_rank ];
0718                     if ( super_t::operator()( n->value, other->value ) )
0719                         std::swap( n, other );
0720
0721                     if ( other->parent )
0722                         n->children.splice( n->children.end(),
0723                                             other->parent->children,
0724                                             node_list_type::s_iterator_to( *other ) );
0725                     else
0726                         n->children.splice( n->children.end(), roots, node_list_type::s_iterator_to( *other ) );
0727
0728                     other->parent = n;
0729
0730                     aux[ node_rank ] = nullptr;
0731                     node_rank        = n->child_count();
0732                 } while ( aux[ node_rank ] != nullptr );
0733                 aux[ node_rank ] = n;
0734             }
0735
0736             if ( !super_t::operator()( n->value, top_element->value ) )
0737                 top_element = n;
0738         } while ( it != roots.end() );
0739     }
0740
0741     void finish_erase_or_pop( node_pointer erased_node )
0742     {
0743         add_children_to_root( erased_node );
0744
0745         erased_node->~node();
0746         allocator_type& alloc = *this;
0747         alloc.deallocate( erased_node, 1 );
0748
0749         size_holder::decrement();
0750         if ( !empty() )
0751             consolidate();
0752         else
0753             top_element = nullptr;
0754     }
0755
0756     mutable node_pointer top_element;
0757     node_list_type       roots;
0758 #endif
0759 };
0760
0761 }} // namespace boost::heap
0762
0763 #undef BOOST_HEAP_ASSERT
0764
0765 #endif /* BOOST_HEAP_FIBONACCI_HEAP_HPP */