heap/detail/stable_heap.hpp

0001 // boost heap: helper classes for stable priority queues
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_DETAIL_STABLE_HEAP_HPP
0010 #define BOOST_HEAP_DETAIL_STABLE_HEAP_HPP
0011
0012 #include <limits>
0013 #include <stdexcept>
0014 #include <type_traits>
0015 #include <utility>
0016
0017 #include <boost/core/allocator_access.hpp>
0018 #include <boost/cstdint.hpp>
0019 #include <boost/iterator/iterator_adaptor.hpp>
0020 #include <boost/throw_exception.hpp>
0021
0022 #include <boost/heap/heap_merge.hpp>
0023 #include <boost/heap/policies.hpp>
0024
0025 namespace boost { namespace heap { namespace detail {
0026
0027 template < bool ConstantSize, class SizeType >
0028 struct size_holder
0029 {
0030     static const bool constant_time_size = ConstantSize;
0031     typedef SizeType  size_type;
0032
0033     size_holder( void ) noexcept :
0034         size_( 0 )
0035     {}
0036
0037     size_holder( size_holder&& rhs ) noexcept :
0038         size_( rhs.size_ )
0039     {
0040         rhs.size_ = 0;
0041     }
0042
0043     size_holder( size_holder const& rhs ) noexcept :
0044         size_( rhs.size_ )
0045     {}
0046
0047     size_holder& operator=( size_holder&& rhs ) noexcept
0048     {
0049         size_     = rhs.size_;
0050         rhs.size_ = 0;
0051         return *this;
0052     }
0053
0054     size_holder& operator=( size_holder const& rhs ) noexcept
0055     {
0056         size_ = rhs.size_;
0057         return *this;
0058     }
0059
0060     SizeType get_size() const noexcept
0061     {
0062         return size_;
0063     }
0064
0065     void set_size( SizeType size ) noexcept
0066     {
0067         size_ = size;
0068     }
0069
0070     void decrement() noexcept
0071     {
0072         --size_;
0073     }
0074
0075     void increment() noexcept
0076     {
0077         ++size_;
0078     }
0079
0080     void add( SizeType value ) noexcept
0081     {
0082         size_ += value;
0083     }
0084
0085     void sub( SizeType value ) noexcept
0086     {
0087         size_ -= value;
0088     }
0089
0090     void swap( size_holder& rhs ) noexcept
0091     {
0092         std::swap( size_, rhs.size_ );
0093     }
0094
0095     SizeType size_;
0096 };
0097
0098 template < class SizeType >
0099 struct size_holder< false, SizeType >
0100 {
0101     static const bool constant_time_size = false;
0102     typedef SizeType  size_type;
0103
0104     size_holder( void ) noexcept
0105     {}
0106
0107     size_holder( size_holder&& ) noexcept
0108     {}
0109
0110     size_holder( size_holder const& ) noexcept
0111     {}
0112
0113     size_holder& operator=( size_holder&& ) noexcept
0114     {
0115         return *this;
0116     }
0117
0118     size_holder& operator=( size_holder const& ) noexcept
0119     {
0120         return *this;
0121     }
0122
0123     size_type get_size() const noexcept
0124     {
0125         return 0;
0126     }
0127
0128     void set_size( size_type ) noexcept
0129     {}
0130
0131     void decrement() noexcept
0132     {}
0133
0134     void increment() noexcept
0135     {}
0136
0137     void add( SizeType /*value*/ ) noexcept
0138     {}
0139
0140     void sub( SizeType /*value*/ ) noexcept
0141     {}
0142
0143     void swap( size_holder& /*rhs*/ ) noexcept
0144     {}
0145 };
0146
0147 // note: MSVC does not implement lookup correctly, we therefore have to place the Cmp object as member inside the
0148 //       struct. of course, this prevents EBO and significantly reduces the readability of this code
0149 template < typename T, typename Cmp, bool constant_time_size, typename StabilityCounterType = boost::uintmax_t, bool stable = false >
0150 struct heap_base :
0151 #ifndef BOOST_MSVC
0152     Cmp,
0153 #endif
0154     size_holder< constant_time_size, size_t >
0155 {
0156     typedef StabilityCounterType                      stability_counter_type;
0157     typedef T                                         value_type;
0158     typedef T                                         internal_type;
0159     typedef size_holder< constant_time_size, size_t > size_holder_type;
0160     typedef Cmp                                       value_compare;
0161     typedef Cmp                                       internal_compare;
0162     static const bool                                 is_stable = stable;
0163
0164 #ifdef BOOST_MSVC
0165     Cmp cmp_;
0166 #endif
0167
0168     heap_base( Cmp const& cmp = Cmp() ) :
0169 #ifndef BOOST_MSVC
0170         Cmp( cmp )
0171 #else
0172         cmp_( cmp )
0173 #endif
0174     {}
0175
0176     heap_base( heap_base&& rhs ) noexcept( std::is_nothrow_move_constructible< Cmp >::value ) :
0177 #ifndef BOOST_MSVC
0178         Cmp( std::move( static_cast< Cmp& >( rhs ) ) ),
0179 #endif
0180         size_holder_type( std::move( static_cast< size_holder_type& >( rhs ) ) )
0181 #ifdef BOOST_MSVC
0182         ,
0183         cmp_( std::move( rhs.cmp_ ) )
0184 #endif
0185     {}
0186
0187     heap_base( heap_base const& rhs ) :
0188 #ifndef BOOST_MSVC
0189         Cmp( static_cast< Cmp const& >( rhs ) ),
0190 #endif
0191         size_holder_type( static_cast< size_holder_type const& >( rhs ) )
0192 #ifdef BOOST_MSVC
0193         ,
0194         cmp_( rhs.value_comp() )
0195 #endif
0196     {}
0197
0198     heap_base& operator=( heap_base&& rhs ) noexcept( std::is_nothrow_move_assignable< Cmp >::value )
0199     {
0200         value_comp_ref().operator=( std::move( rhs.value_comp_ref() ) );
0201         size_holder_type::operator=( std::move( static_cast< size_holder_type& >( rhs ) ) );
0202         return *this;
0203     }
0204
0205     heap_base& operator=( heap_base const& rhs )
0206     {
0207         value_comp_ref().operator=( rhs.value_comp() );
0208         size_holder_type::operator=( static_cast< size_holder_type const& >( rhs ) );
0209         return *this;
0210     }
0211
0212     bool operator()( internal_type const& lhs, internal_type const& rhs ) const
0213     {
0214         return value_comp().operator()( lhs, rhs );
0215     }
0216
0217     internal_type make_node( T const& val )
0218     {
0219         return val;
0220     }
0221
0222     T&& make_node( T&& val )
0223     {
0224         return std::forward< T >( val );
0225     }
0226
0227     template < class... Args >
0228     internal_type make_node( Args&&... val )
0229     {
0230         return internal_type( std::forward< Args >( val )... );
0231     }
0232
0233     static T& get_value( internal_type& val ) noexcept
0234     {
0235         return val;
0236     }
0237
0238     static T const& get_value( internal_type const& val ) noexcept
0239     {
0240         return val;
0241     }
0242
0243     Cmp const& value_comp( void ) const noexcept
0244     {
0245 #ifndef BOOST_MSVC
0246         return *this;
0247 #else
0248         return cmp_;
0249 #endif
0250     }
0251
0252     Cmp const& get_internal_cmp( void ) const noexcept
0253     {
0254         return value_comp();
0255     }
0256
0257     void swap( heap_base& rhs ) noexcept( std::is_nothrow_move_constructible< Cmp >::value
0258                                           && std::is_nothrow_move_assignable< Cmp >::value )
0259     {
0260         std::swap( value_comp_ref(), rhs.value_comp_ref() );
0261         size_holder< constant_time_size, size_t >::swap( rhs );
0262     }
0263
0264     stability_counter_type get_stability_count( void ) const noexcept
0265     {
0266         return 0;
0267     }
0268
0269     void set_stability_count( stability_counter_type ) noexcept
0270     {}
0271
0272     template < typename Heap1, typename Heap2 >
0273     friend struct heap_merge_emulate;
0274
0275 private:
0276     Cmp& value_comp_ref( void )
0277     {
0278 #ifndef BOOST_MSVC
0279         return *this;
0280 #else
0281         return cmp_;
0282 #endif
0283     }
0284 };
0285
0286
0287 template < typename T, typename Cmp, bool constant_time_size, typename StabilityCounterType >
0288 struct heap_base< T, Cmp, constant_time_size, StabilityCounterType, true > :
0289 #ifndef BOOST_MSVC
0290     Cmp,
0291 #endif
0292     size_holder< constant_time_size, size_t >
0293 {
0294     typedef StabilityCounterType stability_counter_type;
0295     typedef T                    value_type;
0296
0297     struct internal_type
0298     {
0299         template < class... Args >
0300         internal_type( stability_counter_type cnt, Args&&... args ) :
0301             first( std::forward< Args >( args )... ),
0302             second( cnt )
0303         {}
0304
0305         internal_type( stability_counter_type const& cnt, T const& value ) :
0306             first( value ),
0307             second( cnt )
0308         {}
0309
0310         T                      first;
0311         stability_counter_type second;
0312     };
0313
0314     typedef size_holder< constant_time_size, size_t > size_holder_type;
0315     typedef Cmp                                       value_compare;
0316
0317 #ifdef BOOST_MSVC
0318     Cmp cmp_;
0319 #endif
0320
0321     heap_base( Cmp const& cmp = Cmp() ) :
0322 #ifndef BOOST_MSVC
0323         Cmp( cmp ),
0324 #else
0325         cmp_( cmp ),
0326 #endif
0327         counter_( 0 )
0328     {}
0329
0330     heap_base( heap_base&& rhs ) noexcept( std::is_nothrow_move_constructible< Cmp >::value ) :
0331 #ifndef BOOST_MSVC
0332         Cmp( std::move( static_cast< Cmp& >( rhs ) ) ),
0333 #else
0334         cmp_( std::move( rhs.cmp_ ) ),
0335 #endif
0336         size_holder_type( std::move( static_cast< size_holder_type& >( rhs ) ) ),
0337         counter_( rhs.counter_ )
0338     {
0339         rhs.counter_ = 0;
0340     }
0341
0342     heap_base( heap_base const& rhs ) :
0343 #ifndef BOOST_MSVC
0344         Cmp( static_cast< Cmp const& >( rhs ) ),
0345 #else
0346         cmp_( rhs.value_comp() ),
0347 #endif
0348         size_holder_type( static_cast< size_holder_type const& >( rhs ) ),
0349         counter_( rhs.counter_ )
0350     {}
0351
0352     heap_base& operator=( heap_base&& rhs ) noexcept( std::is_nothrow_move_assignable< Cmp >::value )
0353     {
0354         value_comp_ref().operator=( std::move( rhs.value_comp_ref() ) );
0355         size_holder_type::operator=( std::move( static_cast< size_holder_type& >( rhs ) ) );
0356
0357         counter_     = rhs.counter_;
0358         rhs.counter_ = 0;
0359         return *this;
0360     }
0361
0362     heap_base& operator=( heap_base const& rhs )
0363     {
0364         value_comp_ref().operator=( rhs.value_comp() );
0365         size_holder_type::operator=( static_cast< size_holder_type const& >( rhs ) );
0366
0367         counter_ = rhs.counter_;
0368         return *this;
0369     }
0370
0371     bool operator()( internal_type const& lhs, internal_type const& rhs ) const
0372     {
0373         return get_internal_cmp()( lhs, rhs );
0374     }
0375
0376     bool operator()( T const& lhs, T const& rhs ) const
0377     {
0378         return value_comp()( lhs, rhs );
0379     }
0380
0381     internal_type make_node( T const& val )
0382     {
0383         stability_counter_type count = ++counter_;
0384         if ( counter_ == ( std::numeric_limits< stability_counter_type >::max )() )
0385             BOOST_THROW_EXCEPTION( std::runtime_error( "boost::heap counter overflow" ) );
0386         return internal_type( count, val );
0387     }
0388
0389     template < class... Args >
0390     internal_type make_node( Args&&... args )
0391     {
0392         stability_counter_type count = ++counter_;
0393         if ( counter_ == ( std::numeric_limits< stability_counter_type >::max )() )
0394             BOOST_THROW_EXCEPTION( std::runtime_error( "boost::heap counter overflow" ) );
0395         return internal_type( count, std::forward< Args >( args )... );
0396     }
0397
0398     static T& get_value( internal_type& val ) noexcept
0399     {
0400         return val.first;
0401     }
0402
0403     static T const& get_value( internal_type const& val ) noexcept
0404     {
0405         return val.first;
0406     }
0407
0408     Cmp const& value_comp( void ) const noexcept
0409     {
0410 #ifndef BOOST_MSVC
0411         return *this;
0412 #else
0413         return cmp_;
0414 #endif
0415     }
0416
0417     struct internal_compare : Cmp
0418     {
0419         internal_compare( Cmp const& cmp = Cmp() ) :
0420             Cmp( cmp )
0421         {}
0422
0423         bool operator()( internal_type const& lhs, internal_type const& rhs ) const
0424         {
0425             if ( Cmp::operator()( lhs.first, rhs.first ) )
0426                 return true;
0427
0428             if ( Cmp::operator()( rhs.first, lhs.first ) )
0429                 return false;
0430
0431             return lhs.second > rhs.second;
0432         }
0433     };
0434
0435     internal_compare get_internal_cmp( void ) const
0436     {
0437         return internal_compare( value_comp() );
0438     }
0439
0440     void swap( heap_base& rhs ) noexcept( std::is_nothrow_move_constructible< Cmp >::value
0441                                           && std::is_nothrow_move_assignable< Cmp >::value )
0442     {
0443 #ifndef BOOST_MSVC
0444         std::swap( static_cast< Cmp& >( *this ), static_cast< Cmp& >( rhs ) );
0445 #else
0446         std::swap( cmp_, rhs.cmp_ );
0447 #endif
0448         std::swap( counter_, rhs.counter_ );
0449         size_holder< constant_time_size, size_t >::swap( rhs );
0450     }
0451
0452     stability_counter_type get_stability_count( void ) const
0453     {
0454         return counter_;
0455     }
0456
0457     void set_stability_count( stability_counter_type new_count )
0458     {
0459         counter_ = new_count;
0460     }
0461
0462     template < typename Heap1, typename Heap2 >
0463     friend struct heap_merge_emulate;
0464
0465 private:
0466     Cmp& value_comp_ref( void ) noexcept
0467     {
0468 #ifndef BOOST_MSVC
0469         return *this;
0470 #else
0471         return cmp_;
0472 #endif
0473     }
0474
0475     stability_counter_type counter_;
0476 };
0477
0478 template < typename node_pointer, typename extractor, typename reference >
0479 struct node_handle
0480 {
0481     explicit node_handle( node_pointer n = 0 ) :
0482         node_( n )
0483     {}
0484
0485     reference operator*() const
0486     {
0487         return extractor::get_value( node_->value );
0488     }
0489
0490     bool operator==( node_handle const& rhs ) const
0491     {
0492         return node_ == rhs.node_;
0493     }
0494
0495     bool operator!=( node_handle const& rhs ) const
0496     {
0497         return node_ != rhs.node_;
0498     }
0499
0500     node_pointer node_;
0501 };
0502
0503 template < typename value_type, typename internal_type, typename extractor >
0504 struct value_extractor
0505 {
0506     value_type const& operator()( internal_type const& data ) const
0507     {
0508         return extractor::get_value( data );
0509     }
0510 };
0511
0512 template < typename T, typename ContainerIterator, typename Extractor >
0513 class stable_heap_iterator :
0514     public boost::iterator_adaptor< stable_heap_iterator< T, ContainerIterator, Extractor >,
0515                                     ContainerIterator,
0516                                     T const,
0517                                     boost::random_access_traversal_tag >
0518 {
0519     typedef boost::iterator_adaptor< stable_heap_iterator, ContainerIterator, T const, boost::random_access_traversal_tag >
0520         super_t;
0521
0522 public:
0523     stable_heap_iterator( void ) :
0524         super_t( 0 )
0525     {}
0526
0527     explicit stable_heap_iterator( ContainerIterator const& it ) :
0528         super_t( it )
0529     {}
0530
0531 private:
0532     friend class boost::iterator_core_access;
0533
0534     T const& dereference() const
0535     {
0536         return Extractor::get_value( *super_t::base() );
0537     }
0538 };
0539
0540 template < typename T, typename Parspec, bool constant_time_size >
0541 struct make_heap_base
0542 {
0543     typedef typename parameter::binding< Parspec, tag::compare, std::less< T > >::type        compare_argument;
0544     typedef typename parameter::binding< Parspec, tag::allocator, std::allocator< T > >::type allocator_argument;
0545     typedef
0546         typename parameter::binding< Parspec, tag::stability_counter_type, boost::uintmax_t >::type stability_counter_type;
0547
0548     static const bool is_stable = extract_stable< Parspec >::value;
0549
0550     typedef heap_base< T, compare_argument, constant_time_size, stability_counter_type, is_stable > type;
0551 };
0552
0553
0554 template < typename Alloc >
0555 struct extract_allocator_types
0556 {
0557     typedef typename boost::allocator_size_type< Alloc >::type       size_type;
0558     typedef typename boost::allocator_difference_type< Alloc >::type difference_type;
0559     typedef typename Alloc::value_type&                              reference;
0560     typedef typename Alloc::value_type const&                        const_reference;
0561     typedef typename boost::allocator_pointer< Alloc >::type         pointer;
0562     typedef typename boost::allocator_const_pointer< Alloc >::type   const_pointer;
0563 };
0564
0565
0566 }}}    // namespace boost::heap::detail
0567
0568 #endif /* BOOST_HEAP_DETAIL_STABLE_HEAP_HPP */