Back to home page

EIC code displayed by LXR
 
 

    

File indexing completed on 2025-12-16 09:53:06 

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

This page was automatically generated by the 2.3.7 LXR engine.

The LXR team
Valid CSS 2.1! Valid HTML 4.01!