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