boost/heap/binomial_heap.hpp

0001 // boost heap: binomial 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_BINOMIAL_HEAP_HPP
0010 #define BOOST_HEAP_BINOMIAL_HEAP_HPP
0011
0012 #include <algorithm>
0013 #include <type_traits>
0014 #include <utility>
0015
0016 #include <boost/assert.hpp>
0017
0018 #include <boost/heap/detail/heap_comparison.hpp>
0019 #include <boost/heap/detail/heap_node.hpp>
0020 #include <boost/heap/detail/stable_heap.hpp>
0021 #include <boost/heap/detail/tree_iterator.hpp>
0022 #include <boost/type_traits/integral_constant.hpp>
0023
0024 #ifdef BOOST_HAS_PRAGMA_ONCE
0025 #    pragma once
0026 #endif
0027
0028 #ifndef BOOST_DOXYGEN_INVOKED
0029 #    ifdef BOOST_HEAP_SANITYCHECKS
0030 #        define BOOST_HEAP_ASSERT BOOST_ASSERT
0031 #    else
0032 #        define BOOST_HEAP_ASSERT( expression ) static_assert( true, "force semicolon" )
0033 #    endif
0034 #endif
0035
0036 namespace boost { namespace heap {
0037 namespace detail {
0038
0039 typedef parameter::parameters< boost::parameter::optional< tag::allocator >,
0040                                boost::parameter::optional< tag::compare >,
0041                                boost::parameter::optional< tag::stable >,
0042                                boost::parameter::optional< tag::constant_time_size >,
0043                                boost::parameter::optional< tag::stability_counter_type > >
0044     binomial_heap_signature;
0045
0046 template < typename T, typename Parspec >
0047 struct make_binomial_heap_base
0048 {
0049     static const bool constant_time_size
0050         = parameter::binding< Parspec, tag::constant_time_size, std::true_type >::type::value;
0051     typedef typename detail::make_heap_base< T, Parspec, constant_time_size >::type               base_type;
0052     typedef typename detail::make_heap_base< T, Parspec, constant_time_size >::allocator_argument allocator_argument;
0053     typedef typename detail::make_heap_base< T, Parspec, constant_time_size >::compare_argument   compare_argument;
0054
0055     typedef parent_pointing_heap_node< typename base_type::internal_type > node_type;
0056
0057     typedef typename boost::allocator_rebind< allocator_argument, node_type >::type allocator_type;
0058
0059     struct type : base_type, allocator_type
0060     {
0061         type( compare_argument const& arg ) :
0062             base_type( arg )
0063         {}
0064
0065         type( allocator_type const& alloc ) :
0066             allocator_type( alloc )
0067         {}
0068
0069         type( type const& rhs ) :
0070             base_type( rhs ),
0071             allocator_type( rhs )
0072         {}
0073
0074         type( type&& rhs ) :
0075             base_type( std::move( static_cast< base_type& >( rhs ) ) ),
0076             allocator_type( std::move( static_cast< allocator_type& >( rhs ) ) )
0077         {}
0078
0079         type& operator=( type&& rhs )
0080         {
0081             base_type::operator=( std::move( static_cast< base_type& >( rhs ) ) );
0082             allocator_type::operator=( std::move( static_cast< allocator_type& >( rhs ) ) );
0083             return *this;
0084         }
0085
0086         type& operator=( type const& rhs )
0087         {
0088             base_type::operator=( static_cast< base_type const& >( rhs ) );
0089             allocator_type::operator=( static_cast< allocator_type const& >( rhs ) );
0090             return *this;
0091         }
0092     };
0093 };
0094
0095 } // namespace detail
0096
0097 /**
0098  * \class binomial_heap
0099  * \brief binomial heap
0100  *
0101  * The template parameter T is the type to be managed by the container.
0102  * The user can specify additional options and if no options are provided default options are used.
0103  *
0104  * The container supports the following options:
0105  * - \c boost::heap::stable<>, defaults to \c stable<false>
0106  * - \c boost::heap::compare<>, defaults to \c compare<std::less<T> >
0107  * - \c boost::heap::allocator<>, defaults to \c allocator<std::allocator<T> >
0108  * - \c boost::heap::constant_time_size<>, defaults to \c constant_time_size<true>
0109  * - \c boost::heap::stability_counter_type<>, defaults to \c stability_counter_type<boost::uintmax_t>
0110  *
0111  */
0112 #ifdef BOOST_DOXYGEN_INVOKED
0113 template < class T, class... Options >
0114 #else
0115 template < typename T,
0116            class A0 = boost::parameter::void_,
0117            class A1 = boost::parameter::void_,
0118            class A2 = boost::parameter::void_,
0119            class A3 = boost::parameter::void_ >
0120 #endif
0121 class binomial_heap :
0122     private detail::make_binomial_heap_base< T, typename detail::binomial_heap_signature::bind< A0, A1, A2, A3 >::type >::type
0123 {
0124     typedef typename detail::binomial_heap_signature::bind< A0, A1, A2, A3 >::type bound_args;
0125     typedef detail::make_binomial_heap_base< T, bound_args >                       base_maker;
0126     typedef typename base_maker::type                                              super_t;
0127
0128     typedef typename super_t::internal_type          internal_type;
0129     typedef typename super_t::size_holder_type       size_holder;
0130     typedef typename super_t::stability_counter_type stability_counter_type;
0131     typedef typename base_maker::allocator_argument  allocator_argument;
0132
0133     template < typename Heap1, typename Heap2 >
0134     friend struct heap_merge_emulate;
0135
0136 public:
0137     static const bool constant_time_size    = super_t::constant_time_size;
0138     static const bool has_ordered_iterators = true;
0139     static const bool is_mergable           = true;
0140     static const bool is_stable             = detail::extract_stable< bound_args >::value;
0141     static const bool has_reserve           = false;
0142
0143 private:
0144 #ifndef BOOST_DOXYGEN_INVOKED
0145     struct implementation_defined : detail::extract_allocator_types< typename base_maker::allocator_argument >
0146     {
0147         typedef T value_type;
0148         typedef typename detail::extract_allocator_types< typename base_maker::allocator_argument >::size_type size_type;
0149         typedef typename detail::extract_allocator_types< typename base_maker::allocator_argument >::reference reference;
0150
0151         typedef typename base_maker::compare_argument value_compare;
0152         typedef typename base_maker::allocator_type   allocator_type;
0153         typedef typename base_maker::node_type        node;
0154
0155         typedef typename boost::allocator_pointer< allocator_type >::type       node_pointer;
0156         typedef typename boost::allocator_const_pointer< allocator_type >::type const_node_pointer;
0157
0158         typedef detail::node_handle< node_pointer, super_t, reference > handle_type;
0159
0160         typedef typename base_maker::node_type node_type;
0161
0162         typedef boost::intrusive::list< detail::heap_node_base< false >, boost::intrusive::constant_time_size< true > >
0163             node_list_type;
0164
0165         typedef typename node_list_type::iterator                             node_list_iterator;
0166         typedef typename node_list_type::const_iterator                       node_list_const_iterator;
0167         typedef detail::value_extractor< value_type, internal_type, super_t > value_extractor;
0168
0169         typedef detail::recursive_tree_iterator< node_type,
0170                                                  node_list_const_iterator,
0171                                                  const value_type,
0172                                                  value_extractor,
0173                                                  detail::list_iterator_converter< node_type, node_list_type > >
0174                          iterator;
0175         typedef iterator const_iterator;
0176
0177         typedef detail::tree_iterator< node_type,
0178                                        const value_type,
0179                                        allocator_type,
0180                                        value_extractor,
0181                                        detail::list_iterator_converter< node_type, node_list_type >,
0182                                        true,
0183                                        true,
0184                                        value_compare >
0185             ordered_iterator;
0186     };
0187 #endif
0188
0189 public:
0190     typedef T value_type;
0191
0192     typedef typename implementation_defined::size_type        size_type;
0193     typedef typename implementation_defined::difference_type  difference_type;
0194     typedef typename implementation_defined::value_compare    value_compare;
0195     typedef typename implementation_defined::allocator_type   allocator_type;
0196     typedef typename implementation_defined::reference        reference;
0197     typedef typename implementation_defined::const_reference  const_reference;
0198     typedef typename implementation_defined::pointer          pointer;
0199     typedef typename implementation_defined::const_pointer    const_pointer;
0200     /// \copydoc boost::heap::priority_queue::iterator
0201     typedef typename implementation_defined::iterator         iterator;
0202     typedef typename implementation_defined::const_iterator   const_iterator;
0203     typedef typename implementation_defined::ordered_iterator ordered_iterator;
0204
0205     typedef typename implementation_defined::handle_type handle_type;
0206
0207 private:
0208     typedef typename implementation_defined::node_type                node_type;
0209     typedef typename implementation_defined::node_list_type           node_list_type;
0210     typedef typename implementation_defined::node_pointer             node_pointer;
0211     typedef typename implementation_defined::const_node_pointer       const_node_pointer;
0212     typedef typename implementation_defined::node_list_iterator       node_list_iterator;
0213     typedef typename implementation_defined::node_list_const_iterator node_list_const_iterator;
0214
0215     typedef typename super_t::internal_compare internal_compare;
0216
0217 public:
0218     /// \copydoc boost::heap::priority_queue::priority_queue(value_compare const &)
0219     explicit binomial_heap( value_compare const& cmp = value_compare() ) :
0220         super_t( cmp ),
0221         top_element( 0 )
0222     {}
0223
0224     /// \copydoc boost::heap::priority_queue::priority_queue(allocator_type const &)
0225     explicit binomial_heap( allocator_type const& alloc ) :
0226         super_t( alloc ),
0227         top_element( 0 )
0228     {}
0229
0230     /// \copydoc boost::heap::priority_queue::priority_queue(priority_queue const &)
0231     binomial_heap( binomial_heap const& rhs ) :
0232         super_t( rhs ),
0233         top_element( 0 )
0234     {
0235         if ( rhs.empty() )
0236             return;
0237
0238         clone_forest( rhs );
0239         size_holder::set_size( rhs.get_size() );
0240     }
0241
0242     /// \copydoc boost::heap::priority_queue::operator=(priority_queue const &)
0243     binomial_heap& operator=( binomial_heap const& rhs )
0244     {
0245         clear();
0246         size_holder::set_size( rhs.get_size() );
0247         static_cast< super_t& >( *this ) = rhs;
0248
0249         if ( rhs.empty() )
0250             top_element = nullptr;
0251         else
0252             clone_forest( rhs );
0253         return *this;
0254     }
0255
0256     /// \copydoc boost::heap::priority_queue::priority_queue(priority_queue &&)
0257     binomial_heap( binomial_heap&& rhs ) :
0258         super_t( std::move( rhs ) ),
0259         top_element( rhs.top_element )
0260     {
0261         trees.splice( trees.begin(), rhs.trees );
0262         rhs.top_element = nullptr;
0263     }
0264
0265     /// \copydoc boost::heap::priority_queue::operator=(priority_queue &&)
0266     binomial_heap& operator=( binomial_heap&& rhs )
0267     {
0268         clear();
0269         super_t::operator=( std::move( rhs ) );
0270         trees.splice( trees.begin(), rhs.trees );
0271         top_element     = rhs.top_element;
0272         rhs.top_element = nullptr;
0273         return *this;
0274     }
0275
0276     ~binomial_heap( void )
0277     {
0278         clear();
0279     }
0280
0281     /// \copydoc boost::heap::priority_queue::empty
0282     bool empty( void ) const
0283     {
0284         return top_element == nullptr;
0285     }
0286
0287     /**
0288      * \b Effects: Returns the number of elements contained in the priority queue.
0289      *
0290      * \b Complexity: Constant, if configured with constant_time_size<true>, otherwise linear.
0291      *
0292      * */
0293     size_type size( void ) const
0294     {
0295         if ( constant_time_size )
0296             return size_holder::get_size();
0297
0298         if ( empty() )
0299             return 0;
0300         else
0301             return detail::count_list_nodes< node_type, node_list_type >( trees );
0302     }
0303
0304     /// \copydoc boost::heap::priority_queue::max_size
0305     size_type max_size( void ) const
0306     {
0307         const allocator_type& alloc = *this;
0308         return boost::allocator_max_size( alloc );
0309     }
0310
0311     /// \copydoc boost::heap::priority_queue::clear
0312     void clear( void )
0313     {
0314         typedef detail::node_disposer< node_type, typename node_list_type::value_type, allocator_type > disposer;
0315         trees.clear_and_dispose( disposer( *this ) );
0316
0317         size_holder::set_size( 0 );
0318         top_element = nullptr;
0319     }
0320
0321     /// \copydoc boost::heap::priority_queue::get_allocator
0322     allocator_type get_allocator( void ) const
0323     {
0324         return *this;
0325     }
0326
0327     /// \copydoc boost::heap::priority_queue::swap
0328     void swap( binomial_heap& rhs )
0329     {
0330         super_t::swap( rhs );
0331         std::swap( top_element, rhs.top_element );
0332         trees.swap( rhs.trees );
0333     }
0334
0335     /// \copydoc boost::heap::priority_queue::top
0336     const_reference top( void ) const
0337     {
0338         BOOST_ASSERT( !empty() );
0339
0340         return super_t::get_value( top_element->value );
0341     }
0342
0343     /**
0344      * \b Effects: Adds a new element to the priority queue. Returns handle to element
0345      *
0346      * \b Complexity: Logarithmic.
0347      *
0348      * */
0349     handle_type push( value_type const& v )
0350     {
0351         allocator_type& alloc = *this;
0352         node_pointer    n     = alloc.allocate( 1 );
0353         new ( n ) node_type( super_t::make_node( v ) );
0354         insert_node( trees.begin(), n );
0355
0356         if ( !top_element || super_t::operator()( top_element->value, n->value ) )
0357             top_element = n;
0358
0359         size_holder::increment();
0360         sanity_check();
0361         return handle_type( n );
0362     }
0363
0364     /**
0365      * \b Effects: Adds a new element to the priority queue. The element is directly constructed in-place. Returns
0366      * handle to element.
0367      *
0368      * \b Complexity: Logarithmic.
0369      *
0370      * */
0371     template < class... Args >
0372     handle_type emplace( Args&&... args )
0373     {
0374         allocator_type& alloc = *this;
0375         node_pointer    n     = alloc.allocate( 1 );
0376         new ( n ) node_type( super_t::make_node( std::forward< Args >( args )... ) );
0377         insert_node( trees.begin(), n );
0378
0379         if ( !top_element || super_t::operator()( top_element->value, n->value ) )
0380             top_element = n;
0381
0382         size_holder::increment();
0383         sanity_check();
0384         return handle_type( n );
0385     }
0386
0387     /**
0388      * \b Effects: Removes the top element from the priority queue.
0389      *
0390      * \b Complexity: Logarithmic.
0391      *
0392      * */
0393     void pop( void )
0394     {
0395         BOOST_ASSERT( !empty() );
0396
0397         node_pointer element = top_element;
0398
0399         trees.erase( node_list_type::s_iterator_to( *element ) );
0400         size_holder::decrement();
0401
0402         if ( element->child_count() ) {
0403             size_type sz = ( 1 << element->child_count() ) - 1;
0404
0405             binomial_heap children( value_comp(), element->children, sz );
0406             if ( trees.empty() ) {
0407                 stability_counter_type stability_count = super_t::get_stability_count();
0408                 size_t                 size            = constant_time_size ? size_holder::get_size() : 0;
0409                 swap( children );
0410                 super_t::set_stability_count( stability_count );
0411
0412                 if ( constant_time_size )
0413                     size_holder::set_size( size );
0414             } else
0415                 merge_and_clear_nodes( children );
0416         }
0417
0418         if ( trees.empty() )
0419             top_element = nullptr;
0420         else
0421             update_top_element();
0422
0423         element->~node_type();
0424         allocator_type& alloc = *this;
0425         alloc.deallocate( element, 1 );
0426         sanity_check();
0427     }
0428
0429     /**
0430      * \b Effects: Assigns \c v to the element handled by \c handle & updates the priority queue.
0431      *
0432      * \b Complexity: Logarithmic.
0433      *
0434      * */
0435     void update( handle_type handle, const_reference v )
0436     {
0437         if ( super_t::operator()( super_t::get_value( handle.node_->value ), v ) )
0438             increase( handle, v );
0439         else
0440             decrease( handle, v );
0441     }
0442
0443     /**
0444      * \b Effects: Updates the heap after the element handled by \c handle has been changed.
0445      *
0446      * \b Complexity: Logarithmic.
0447      *
0448      * \b Note: If this is not called, after a handle has been updated, the behavior of the data structure is undefined!
0449      * */
0450     void update( handle_type handle )
0451     {
0452         node_pointer this_node = handle.node_;
0453
0454         if ( this_node->parent ) {
0455             if ( super_t::operator()( super_t::get_value( this_node->parent->value ),
0456                                       super_t::get_value( this_node->value ) ) )
0457                 increase( handle );
0458             else
0459                 decrease( handle );
0460         } else
0461             decrease( handle );
0462     }
0463
0464     /**
0465      * \b Effects: Assigns \c v to the element handled by \c handle & updates the priority queue.
0466      *
0467      * \b Complexity: Logarithmic.
0468      *
0469      * \b Note: The new value is expected to be greater than the current one
0470      * */
0471     void increase( handle_type handle, const_reference v )
0472     {
0473         handle.node_->value = super_t::make_node( v );
0474         increase( handle );
0475     }
0476
0477     /**
0478      * \b Effects: Updates the heap after the element handled by \c handle has been changed.
0479      *
0480      * \b Complexity: Logarithmic.
0481      *
0482      * \b Note: If this is not called, after a handle has been updated, the behavior of the data structure is undefined!
0483      * */
0484     void increase( handle_type handle )
0485     {
0486         node_pointer n = handle.node_;
0487         siftup( n, *this );
0488
0489         update_top_element();
0490         sanity_check();
0491     }
0492
0493     /**
0494      * \b Effects: Assigns \c v to the element handled by \c handle & updates the priority queue.
0495      *
0496      * \b Complexity: Logarithmic.
0497      *
0498      * \b Note: The new value is expected to be less than the current one
0499      * */
0500     void decrease( handle_type handle, const_reference v )
0501     {
0502         handle.node_->value = super_t::make_node( v );
0503         decrease( handle );
0504     }
0505
0506     /**
0507      * \b Effects: Updates the heap after the element handled by \c handle has been changed.
0508      *
0509      * \b Complexity: Logarithmic.
0510      *
0511      * \b Note: The new value is expected to be less than the current one. If this is not called, after a handle has
0512      * been updated, the behavior of the data structure is undefined!
0513      * */
0514     void decrease( handle_type handle )
0515     {
0516         node_pointer n = handle.node_;
0517
0518         siftdown( n );
0519
0520         update_top_element();
0521     }
0522
0523     /**
0524      * \b Effects: Merge with priority queue rhs.
0525      *
0526      * \b Complexity: Logarithmic.
0527      *
0528      * */
0529     void merge( binomial_heap& rhs )
0530     {
0531         if ( rhs.empty() )
0532             return;
0533
0534         if ( empty() ) {
0535             swap( rhs );
0536             return;
0537         }
0538
0539         size_type new_size = size_holder::get_size() + rhs.get_size();
0540         merge_and_clear_nodes( rhs );
0541
0542         size_holder::set_size( new_size );
0543         rhs.set_size( 0 );
0544         rhs.top_element = nullptr;
0545
0546         super_t::set_stability_count( ( std::max )( super_t::get_stability_count(), rhs.get_stability_count() ) );
0547         rhs.set_stability_count( 0 );
0548     }
0549
0550 public:
0551     /// \copydoc boost::heap::priority_queue::begin
0552     iterator begin( void ) const
0553     {
0554         return iterator( trees.begin() );
0555     }
0556
0557     /// \copydoc boost::heap::priority_queue::end
0558     iterator end( void ) const
0559     {
0560         return iterator( trees.end() );
0561     }
0562
0563     /// \copydoc boost::heap::fibonacci_heap::ordered_begin
0564     ordered_iterator ordered_begin( void ) const
0565     {
0566         return ordered_iterator( trees.begin(), trees.end(), top_element, super_t::value_comp() );
0567     }
0568
0569     /// \copydoc boost::heap::fibonacci_heap::ordered_end
0570     ordered_iterator ordered_end( void ) const
0571     {
0572         return ordered_iterator( nullptr, super_t::value_comp() );
0573     }
0574
0575     /**
0576      * \b Effects: Removes the element handled by \c handle from the priority_queue.
0577      *
0578      * \b Complexity: Logarithmic.
0579      * */
0580     void erase( handle_type handle )
0581     {
0582         node_pointer n = handle.node_;
0583         siftup( n, force_inf() );
0584         top_element = n;
0585         pop();
0586     }
0587
0588     /// \copydoc boost::heap::d_ary_heap_mutable::s_handle_from_iterator
0589     static handle_type s_handle_from_iterator( iterator const& it )
0590     {
0591         node_type* ptr = const_cast< node_type* >( it.get_node() );
0592         return handle_type( ptr );
0593     }
0594
0595     /// \copydoc boost::heap::priority_queue::value_comp
0596     value_compare const& value_comp( void ) const
0597     {
0598         return super_t::value_comp();
0599     }
0600
0601     /// \copydoc boost::heap::priority_queue::operator<(HeapType const & rhs) const
0602     template < typename HeapType >
0603     bool operator<( HeapType const& rhs ) const
0604     {
0605         return detail::heap_compare( *this, rhs );
0606     }
0607
0608     /// \copydoc boost::heap::priority_queue::operator>(HeapType const & rhs) const
0609     template < typename HeapType >
0610     bool operator>( HeapType const& rhs ) const
0611     {
0612         return detail::heap_compare( rhs, *this );
0613     }
0614
0615     /// \copydoc boost::heap::priority_queue::operator>=(HeapType const & rhs) const
0616     template < typename HeapType >
0617     bool operator>=( HeapType const& rhs ) const
0618     {
0619         return !operator<( rhs );
0620     }
0621
0622     /// \copydoc boost::heap::priority_queue::operator<=(HeapType const & rhs) const
0623     template < typename HeapType >
0624     bool operator<=( HeapType const& rhs ) const
0625     {
0626         return !operator>( rhs );
0627     }
0628
0629     /// \copydoc boost::heap::priority_queue::operator==(HeapType const & rhs) const
0630     template < typename HeapType >
0631     bool operator==( HeapType const& rhs ) const
0632     {
0633         return detail::heap_equality( *this, rhs );
0634     }
0635
0636     /// \copydoc boost::heap::priority_queue::operator!=(HeapType const & rhs) const
0637     template < typename HeapType >
0638     bool operator!=( HeapType const& rhs ) const
0639     {
0640         return !( *this == rhs );
0641     }
0642
0643 private:
0644 #if !defined( BOOST_DOXYGEN_INVOKED )
0645     void merge_and_clear_nodes( binomial_heap& rhs )
0646     {
0647         BOOST_HEAP_ASSERT( !empty() );
0648         BOOST_HEAP_ASSERT( !rhs.empty() );
0649
0650         node_list_iterator this_iterator = trees.begin();
0651         node_pointer       carry_node    = nullptr;
0652
0653         while ( !rhs.trees.empty() ) {
0654             node_pointer rhs_node   = static_cast< node_pointer >( &rhs.trees.front() );
0655             size_type    rhs_degree = rhs_node->child_count();
0656
0657             if ( super_t::operator()( top_element->value, rhs_node->value ) )
0658                 top_element = rhs_node;
0659
0660 try_again:
0661             node_pointer this_node   = static_cast< node_pointer >( &*this_iterator );
0662             size_type    this_degree = this_node->child_count();
0663             sorted_by_degree();
0664             rhs.sorted_by_degree();
0665
0666             if ( this_degree == rhs_degree ) {
0667                 if ( carry_node ) {
0668                     if ( carry_node->child_count() < this_degree ) {
0669                         trees.insert( this_iterator, *carry_node );
0670                         carry_node = nullptr;
0671                     } else {
0672                         rhs.trees.pop_front();
0673                         carry_node = merge_trees( carry_node, rhs_node );
0674                     }
0675                     ++this_iterator;
0676                 } else {
0677                     this_iterator = trees.erase( this_iterator );
0678                     rhs.trees.pop_front();
0679                     carry_node = merge_trees( this_node, rhs_node );
0680                 }
0681
0682                 if ( this_iterator == trees.end() )
0683                     break;
0684                 else
0685                     continue;
0686             }
0687
0688             if ( this_degree < rhs_degree ) {
0689                 if ( carry_node ) {
0690                     if ( carry_node->child_count() < this_degree ) {
0691                         trees.insert( this_iterator, *carry_node );
0692                         carry_node = nullptr;
0693                         ++this_iterator;
0694                     } else if ( carry_node->child_count() == rhs_degree ) {
0695                         rhs.trees.pop_front();
0696                         carry_node = merge_trees( carry_node, rhs_node );
0697                         continue;
0698                     } else {
0699                         this_iterator = trees.erase( this_iterator );
0700                         carry_node    = merge_trees( this_node, carry_node );
0701                     }
0702                     goto try_again;
0703                 } else {
0704                     ++this_iterator;
0705                     if ( this_iterator == trees.end() )
0706                         break;
0707                     goto try_again;
0708                 }
0709
0710                 if ( this_iterator == trees.end() )
0711                     break;
0712                 else
0713                     continue;
0714             }
0715
0716             if ( this_degree > rhs_degree ) {
0717                 rhs.trees.pop_front();
0718                 if ( carry_node ) {
0719                     if ( carry_node->child_count() < rhs_degree ) {
0720                         trees.insert( this_iterator, *carry_node );
0721                         trees.insert( this_iterator, *rhs_node );
0722                         carry_node = nullptr;
0723                     } else
0724                         carry_node = merge_trees( rhs_node, carry_node );
0725                 } else
0726                     trees.insert( this_iterator, *rhs_node );
0727             }
0728         }
0729
0730         if ( !rhs.trees.empty() ) {
0731             if ( carry_node ) {
0732                 node_list_iterator rhs_it = rhs.trees.begin();
0733                 while ( static_cast< node_pointer >( &*rhs_it )->child_count() < carry_node->child_count() )
0734                     ++rhs_it;
0735                 rhs.insert_node( rhs_it, carry_node );
0736                 rhs.increment();
0737                 sorted_by_degree();
0738                 rhs.sorted_by_degree();
0739                 if ( trees.empty() ) {
0740                     trees.splice( trees.end(), rhs.trees, rhs.trees.begin(), rhs.trees.end() );
0741                     update_top_element();
0742                 } else
0743                     merge_and_clear_nodes( rhs );
0744             } else
0745                 trees.splice( trees.end(), rhs.trees, rhs.trees.begin(), rhs.trees.end() );
0746             return;
0747         }
0748
0749         if ( carry_node )
0750             insert_node( this_iterator, carry_node );
0751     }
0752
0753     void clone_forest( binomial_heap const& rhs )
0754     {
0755         BOOST_HEAP_ASSERT( trees.empty() );
0756         typedef typename node_type::template node_cloner< allocator_type > node_cloner;
0757         trees.clone_from( rhs.trees, node_cloner( *this, nullptr ), detail::nop_disposer() );
0758
0759         update_top_element();
0760     }
0761
0762     struct force_inf
0763     {
0764         template < typename X >
0765         bool operator()( X const&, X const& ) const
0766         {
0767             return false;
0768         }
0769     };
0770
0771     template < typename Compare >
0772     void siftup( node_pointer n, Compare const& cmp )
0773     {
0774         while ( n->parent ) {
0775             node_pointer parent       = n->parent;
0776             node_pointer grand_parent = parent->parent;
0777             if ( cmp( n->value, parent->value ) )
0778                 return;
0779
0780             n->remove_from_parent();
0781
0782             n->swap_children( parent );
0783             n->update_children();
0784             parent->update_children();
0785
0786             if ( grand_parent ) {
0787                 parent->remove_from_parent();
0788                 grand_parent->add_child( n );
0789             } else {
0790                 node_list_iterator it = trees.erase( node_list_type::s_iterator_to( *parent ) );
0791                 trees.insert( it, *n );
0792             }
0793             n->add_child( parent );
0794         }
0795     }
0796
0797     void siftdown( node_pointer n )
0798     {
0799         while ( n->child_count() ) {
0800             node_pointer max_child
0801                 = detail::find_max_child< node_list_type, node_type, internal_compare >( n->children,
0802                                                                                          super_t::get_internal_cmp() );
0803
0804             if ( super_t::operator()( max_child->value, n->value ) )
0805                 return;
0806
0807             max_child->remove_from_parent();
0808
0809             n->swap_children( max_child );
0810             n->update_children();
0811             max_child->update_children();
0812
0813             node_pointer parent = n->parent;
0814             if ( parent ) {
0815                 n->remove_from_parent();
0816                 max_child->add_child( n );
0817                 parent->add_child( max_child );
0818             } else {
0819                 node_list_iterator position = trees.erase( node_list_type::s_iterator_to( *n ) );
0820                 max_child->add_child( n );
0821                 trees.insert( position, *max_child );
0822             }
0823         }
0824     }
0825
0826     void insert_node( node_list_iterator it, node_pointer n )
0827     {
0828         if ( it != trees.end() )
0829             BOOST_HEAP_ASSERT( static_cast< node_pointer >( &*it )->child_count() >= n->child_count() );
0830
0831         while ( true ) {
0832             BOOST_HEAP_ASSERT( !n->is_linked() );
0833             if ( it == trees.end() )
0834                 break;
0835
0836             node_pointer this_node   = static_cast< node_pointer >( &*it );
0837             size_type    this_degree = this_node->child_count();
0838             size_type    n_degree    = n->child_count();
0839             if ( this_degree == n_degree ) {
0840                 BOOST_HEAP_ASSERT( it->is_linked() );
0841                 it = trees.erase( it );
0842
0843                 n = merge_trees( n, this_node );
0844             } else
0845                 break;
0846         }
0847         trees.insert( it, *n );
0848     }
0849
0850     // private constructor, just used in pop()
0851     explicit binomial_heap( value_compare const& cmp, node_list_type& child_list, size_type size ) :
0852         super_t( cmp )
0853     {
0854         size_holder::set_size( size );
0855         if ( size )
0856             top_element = static_cast< node_pointer >( &*child_list.begin() ); // not correct, but we will reset it later
0857         else
0858             top_element = nullptr;
0859
0860         for ( node_list_iterator it = child_list.begin(); it != child_list.end(); ++it ) {
0861             node_pointer n = static_cast< node_pointer >( &*it );
0862             n->parent      = nullptr;
0863         }
0864
0865         trees.splice( trees.end(), child_list, child_list.begin(), child_list.end() );
0866
0867         trees.sort( detail::cmp_by_degree< node_type >() );
0868     }
0869
0870     node_pointer merge_trees( node_pointer node1, node_pointer node2 )
0871     {
0872         BOOST_HEAP_ASSERT( node1->child_count() == node2->child_count() );
0873
0874         if ( super_t::operator()( node1->value, node2->value ) )
0875             std::swap( node1, node2 );
0876
0877         if ( node2->parent )
0878             node2->remove_from_parent();
0879
0880         node1->add_child( node2 );
0881         return node1;
0882     }
0883
0884     void update_top_element( void )
0885     {
0886         top_element
0887             = detail::find_max_child< node_list_type, node_type, internal_compare >( trees,
0888                                                                                      super_t::get_internal_cmp() );
0889     }
0890
0891     void sorted_by_degree( void ) const
0892     {
0893 #    ifdef BOOST_HEAP_SANITYCHECKS
0894         int degree = -1;
0895
0896         for ( node_list_const_iterator it = trees.begin(); it != trees.end(); ++it ) {
0897             const_node_pointer n = static_cast< const_node_pointer >( &*it );
0898             BOOST_HEAP_ASSERT( int( n->child_count() ) > degree );
0899             degree = n->child_count();
0900
0901             BOOST_HEAP_ASSERT( ( detail::is_heap< node_type, super_t >( n, *this ) ) );
0902
0903             size_type child_nodes = detail::count_nodes< node_type >( n );
0904             BOOST_HEAP_ASSERT( child_nodes
0905                                == size_type( 1 << static_cast< const_node_pointer >( &*it )->child_count() ) );
0906         }
0907 #    endif
0908     }
0909
0910     void sanity_check( void )
0911     {
0912 #    ifdef BOOST_HEAP_SANITYCHECKS
0913         sorted_by_degree();
0914
0915         if ( !empty() ) {
0916             node_pointer found_top
0917                 = detail::find_max_child< node_list_type, node_type, internal_compare >( trees,
0918                                                                                          super_t::get_internal_cmp() );
0919             BOOST_HEAP_ASSERT( top_element == found_top );
0920         }
0921
0922         if ( constant_time_size ) {
0923             size_t counted = detail::count_list_nodes< node_type, node_list_type >( trees );
0924             size_t stored  = size_holder::get_size();
0925             BOOST_HEAP_ASSERT( counted == stored );
0926         }
0927 #    endif
0928     }
0929
0930     node_pointer   top_element;
0931     node_list_type trees;
0932 #endif // BOOST_DOXYGEN_INVOKED
0933 };
0934
0935
0936 }} // namespace boost::heap
0937
0938 #undef BOOST_HEAP_ASSERT
0939
0940 #endif /* BOOST_HEAP_D_ARY_HEAP_HPP */