| // boost heap: helper classes for stable priority queues |
| // |
| // Copyright (C) 2010 Tim Blechmann |
| // |
| // Distributed under the Boost Software License, Version 1.0. (See |
| // accompanying file LICENSE_1_0.txt or copy at |
| // http://www.boost.org/LICENSE_1_0.txt) |
| |
| #ifndef BOOST_HEAP_DETAIL_STABLE_HEAP_HPP |
| #define BOOST_HEAP_DETAIL_STABLE_HEAP_HPP |
| |
| #include <limits> |
| #include <stdexcept> |
| #include <utility> |
| |
| #include <boost/cstdint.hpp> |
| #include <boost/throw_exception.hpp> |
| #include <boost/iterator/iterator_adaptor.hpp> |
| |
| #include <boost/heap/policies.hpp> |
| #include <boost/heap/heap_merge.hpp> |
| |
| namespace boost { |
| namespace heap { |
| namespace detail { |
| |
| template<bool ConstantSize, class SizeType> |
| struct size_holder |
| { |
| static const bool constant_time_size = ConstantSize; |
| typedef SizeType size_type; |
| |
| size_holder(void): |
| size_(0) |
| {} |
| |
| #ifndef BOOST_NO_CXX11_RVALUE_REFERENCES |
| size_holder(size_holder && rhs): |
| size_(rhs.size_) |
| { |
| rhs.size_ = 0; |
| } |
| |
| size_holder(size_holder const & rhs): |
| size_(rhs.size_) |
| {} |
| |
| size_holder & operator=(size_holder && rhs) |
| { |
| size_ = rhs.size_; |
| rhs.size_ = 0; |
| return *this; |
| } |
| |
| size_holder & operator=(size_holder const & rhs) |
| { |
| size_ = rhs.size_; |
| return *this; |
| } |
| #endif |
| |
| SizeType get_size() const |
| { return size_; } |
| |
| void set_size(SizeType size) |
| { size_ = size; } |
| |
| void decrement() |
| { --size_; } |
| |
| void increment() |
| { ++size_; } |
| |
| void add(SizeType value) |
| { size_ += value; } |
| |
| void sub(SizeType value) |
| { size_ -= value; } |
| |
| void swap(size_holder & rhs) |
| { std::swap(size_, rhs.size_); } |
| |
| SizeType size_; |
| }; |
| |
| template<class SizeType> |
| struct size_holder<false, SizeType> |
| { |
| static const bool constant_time_size = false; |
| typedef SizeType size_type; |
| |
| size_holder(void) |
| {} |
| |
| #ifndef BOOST_NO_CXX11_RVALUE_REFERENCES |
| size_holder(size_holder && rhs) |
| {} |
| |
| size_holder(size_holder const & rhs) |
| {} |
| |
| size_holder & operator=(size_holder && rhs) |
| { |
| return *this; |
| } |
| |
| size_holder & operator=(size_holder const & rhs) |
| { |
| return *this; |
| } |
| #endif |
| |
| size_type get_size() const |
| { return 0; } |
| |
| void set_size(size_type) |
| {} |
| |
| void decrement() |
| {} |
| |
| void increment() |
| {} |
| |
| void add(SizeType value) |
| {} |
| |
| void sub(SizeType value) |
| {} |
| |
| void swap(size_holder & rhs) |
| {} |
| }; |
| |
| // note: MSVC does not implement lookup correctly, we therefore have to place the Cmp object as member inside the |
| // struct. of course, this prevents EBO and significantly reduces the readability of this code |
| template <typename T, |
| typename Cmp, |
| bool constant_time_size, |
| typename StabilityCounterType = boost::uintmax_t, |
| bool stable = false |
| > |
| struct heap_base: |
| #ifndef BOOST_MSVC |
| Cmp, |
| #endif |
| size_holder<constant_time_size, size_t> |
| { |
| typedef StabilityCounterType stability_counter_type; |
| typedef T value_type; |
| typedef T internal_type; |
| typedef size_holder<constant_time_size, size_t> size_holder_type; |
| typedef Cmp value_compare; |
| typedef Cmp internal_compare; |
| static const bool is_stable = stable; |
| |
| #ifdef BOOST_MSVC |
| Cmp cmp_; |
| #endif |
| |
| heap_base (Cmp const & cmp = Cmp()): |
| #ifndef BOOST_MSVC |
| Cmp(cmp) |
| #else |
| cmp_(cmp) |
| #endif |
| {} |
| |
| #ifndef BOOST_NO_CXX11_RVALUE_REFERENCES |
| heap_base(heap_base && rhs): |
| #ifndef BOOST_MSVC |
| Cmp(std::move(static_cast<Cmp&>(rhs))), |
| #else |
| cmp_(std::move(rhs.cmp_)), |
| #endif |
| size_holder_type(std::move(static_cast<size_holder_type&>(rhs))) |
| {} |
| |
| heap_base(heap_base const & rhs): |
| #ifndef BOOST_MSVC |
| Cmp(static_cast<Cmp const &>(rhs)), |
| #else |
| cmp_(rhs.value_comp()), |
| #endif |
| size_holder_type(static_cast<size_holder_type const &>(rhs)) |
| {} |
| |
| heap_base & operator=(heap_base && rhs) |
| { |
| value_comp_ref().operator=(std::move(rhs.value_comp_ref())); |
| size_holder_type::operator=(std::move(static_cast<size_holder_type&>(rhs))); |
| return *this; |
| } |
| |
| heap_base & operator=(heap_base const & rhs) |
| { |
| value_comp_ref().operator=(rhs.value_comp()); |
| size_holder_type::operator=(static_cast<size_holder_type const &>(rhs)); |
| return *this; |
| } |
| #endif |
| |
| bool operator()(internal_type const & lhs, internal_type const & rhs) const |
| { |
| return value_comp().operator()(lhs, rhs); |
| } |
| |
| internal_type make_node(T const & val) |
| { |
| return val; |
| } |
| |
| #ifndef BOOST_NO_CXX11_RVALUE_REFERENCES |
| T && make_node(T && val) |
| { |
| return std::forward<T>(val); |
| } |
| #endif |
| |
| #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES) && !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) |
| template <class... Args> |
| internal_type make_node(Args && ... val) |
| { |
| return internal_type(std::forward<Args>(val)...); |
| } |
| #endif |
| |
| static T & get_value(internal_type & val) |
| { |
| return val; |
| } |
| |
| static T const & get_value(internal_type const & val) |
| { |
| return val; |
| } |
| |
| Cmp const & value_comp(void) const |
| { |
| #ifndef BOOST_MSVC |
| return *this; |
| #else |
| return cmp_; |
| #endif |
| } |
| |
| Cmp const & get_internal_cmp(void) const |
| { |
| return value_comp(); |
| } |
| |
| void swap(heap_base & rhs) |
| { |
| std::swap(value_comp_ref(), rhs.value_comp_ref()); |
| size_holder<constant_time_size, size_t>::swap(rhs); |
| } |
| |
| stability_counter_type get_stability_count(void) const |
| { |
| return 0; |
| } |
| |
| void set_stability_count(stability_counter_type) |
| {} |
| |
| template <typename Heap1, typename Heap2> |
| friend struct heap_merge_emulate; |
| |
| private: |
| Cmp & value_comp_ref(void) |
| { |
| #ifndef BOOST_MSVC |
| return *this; |
| #else |
| return cmp_; |
| #endif |
| } |
| }; |
| |
| |
| template <typename T, |
| typename Cmp, |
| bool constant_time_size, |
| typename StabilityCounterType |
| > |
| struct heap_base<T, Cmp, constant_time_size, StabilityCounterType, true>: |
| #ifndef BOOST_MSVC |
| Cmp, |
| #endif |
| size_holder<constant_time_size, size_t> |
| { |
| typedef StabilityCounterType stability_counter_type; |
| typedef T value_type; |
| |
| struct internal_type |
| { |
| #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES) && !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) |
| template <class ...Args> |
| internal_type(stability_counter_type cnt, Args && ... args): |
| first(std::forward<Args>(args)...), second(cnt) |
| {} |
| #endif |
| |
| internal_type(stability_counter_type const & cnt, T const & value): |
| first(value), second(cnt) |
| {} |
| |
| T first; |
| stability_counter_type second; |
| }; |
| |
| typedef size_holder<constant_time_size, size_t> size_holder_type; |
| typedef Cmp value_compare; |
| |
| #ifdef BOOST_MSVC |
| Cmp cmp_; |
| #endif |
| |
| heap_base (Cmp const & cmp = Cmp()): |
| #ifndef BOOST_MSVC |
| Cmp(cmp), |
| #else |
| cmp_(cmp), |
| #endif |
| counter_(0) |
| {} |
| |
| #ifndef BOOST_NO_CXX11_RVALUE_REFERENCES |
| heap_base(heap_base && rhs): |
| #ifndef BOOST_MSVC |
| Cmp(std::move(static_cast<Cmp&>(rhs))), |
| #else |
| cmp_(std::move(rhs.cmp_)), |
| #endif |
| size_holder_type(std::move(static_cast<size_holder_type&>(rhs))), counter_(rhs.counter_) |
| { |
| rhs.counter_ = 0; |
| } |
| |
| heap_base(heap_base const & rhs): |
| #ifndef BOOST_MSVC |
| Cmp(static_cast<Cmp const&>(rhs)), |
| #else |
| cmp_(rhs.value_comp()), |
| #endif |
| size_holder_type(static_cast<size_holder_type const &>(rhs)), counter_(rhs.counter_) |
| {} |
| |
| heap_base & operator=(heap_base && rhs) |
| { |
| value_comp_ref().operator=(std::move(rhs.value_comp_ref())); |
| size_holder_type::operator=(std::move(static_cast<size_holder_type&>(rhs))); |
| |
| counter_ = rhs.counter_; |
| rhs.counter_ = 0; |
| return *this; |
| } |
| |
| heap_base & operator=(heap_base const & rhs) |
| { |
| value_comp_ref().operator=(rhs.value_comp()); |
| size_holder_type::operator=(static_cast<size_holder_type const &>(rhs)); |
| |
| counter_ = rhs.counter_; |
| return *this; |
| } |
| #endif |
| |
| bool operator()(internal_type const & lhs, internal_type const & rhs) const |
| { |
| return get_internal_cmp()(lhs, rhs); |
| } |
| |
| bool operator()(T const & lhs, T const & rhs) const |
| { |
| return value_comp()(lhs, rhs); |
| } |
| |
| internal_type make_node(T const & val) |
| { |
| stability_counter_type count = ++counter_; |
| if (counter_ == (std::numeric_limits<stability_counter_type>::max)()) |
| BOOST_THROW_EXCEPTION(std::runtime_error("boost::heap counter overflow")); |
| return internal_type(count, val); |
| } |
| |
| #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES) && !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) |
| template <class... Args> |
| internal_type make_node(Args&&... args) |
| { |
| stability_counter_type count = ++counter_; |
| if (counter_ == (std::numeric_limits<stability_counter_type>::max)()) |
| BOOST_THROW_EXCEPTION(std::runtime_error("boost::heap counter overflow")); |
| return internal_type (count, std::forward<Args>(args)...); |
| } |
| #endif |
| |
| static T & get_value(internal_type & val) |
| { |
| return val.first; |
| } |
| |
| static T const & get_value(internal_type const & val) |
| { |
| return val.first; |
| } |
| |
| Cmp const & value_comp(void) const |
| { |
| #ifndef BOOST_MSVC |
| return *this; |
| #else |
| return cmp_; |
| #endif |
| } |
| |
| struct internal_compare: |
| Cmp |
| { |
| internal_compare(Cmp const & cmp = Cmp()): |
| Cmp(cmp) |
| {} |
| |
| bool operator()(internal_type const & lhs, internal_type const & rhs) const |
| { |
| if (Cmp::operator()(lhs.first, rhs.first)) |
| return true; |
| |
| if (Cmp::operator()(rhs.first, lhs.first)) |
| return false; |
| |
| return lhs.second > rhs.second; |
| } |
| }; |
| |
| internal_compare get_internal_cmp(void) const |
| { |
| return internal_compare(value_comp()); |
| } |
| |
| void swap(heap_base & rhs) |
| { |
| #ifndef BOOST_MSVC |
| std::swap(static_cast<Cmp&>(*this), static_cast<Cmp&>(rhs)); |
| #else |
| std::swap(cmp_, rhs.cmp_); |
| #endif |
| std::swap(counter_, rhs.counter_); |
| size_holder<constant_time_size, size_t>::swap(rhs); |
| } |
| |
| stability_counter_type get_stability_count(void) const |
| { |
| return counter_; |
| } |
| |
| void set_stability_count(stability_counter_type new_count) |
| { |
| counter_ = new_count; |
| } |
| |
| template <typename Heap1, typename Heap2> |
| friend struct heap_merge_emulate; |
| |
| private: |
| Cmp & value_comp_ref(void) |
| { |
| #ifndef BOOST_MSVC |
| return *this; |
| #else |
| return cmp_; |
| #endif |
| } |
| |
| stability_counter_type counter_; |
| }; |
| |
| template <typename node_pointer, |
| typename extractor, |
| typename reference |
| > |
| struct node_handle |
| { |
| explicit node_handle(node_pointer n = 0): |
| node_(n) |
| {} |
| |
| reference operator*() const |
| { |
| return extractor::get_value(node_->value); |
| } |
| |
| bool operator==(node_handle const & rhs) const |
| { |
| return node_ == rhs.node_; |
| } |
| |
| bool operator!=(node_handle const & rhs) const |
| { |
| return node_ != rhs.node_; |
| } |
| |
| node_pointer node_; |
| }; |
| |
| template <typename value_type, |
| typename internal_type, |
| typename extractor |
| > |
| struct value_extractor |
| { |
| value_type const & operator()(internal_type const & data) const |
| { |
| return extractor::get_value(data); |
| } |
| }; |
| |
| template <typename T, |
| typename ContainerIterator, |
| typename Extractor> |
| class stable_heap_iterator: |
| public boost::iterator_adaptor<stable_heap_iterator<T, ContainerIterator, Extractor>, |
| ContainerIterator, |
| T const, |
| boost::random_access_traversal_tag> |
| { |
| typedef boost::iterator_adaptor<stable_heap_iterator, |
| ContainerIterator, |
| T const, |
| boost::random_access_traversal_tag> super_t; |
| |
| public: |
| stable_heap_iterator(void): |
| super_t(0) |
| {} |
| |
| explicit stable_heap_iterator(ContainerIterator const & it): |
| super_t(it) |
| {} |
| |
| private: |
| friend class boost::iterator_core_access; |
| |
| T const & dereference() const |
| { |
| return Extractor::get_value(*super_t::base()); |
| } |
| }; |
| |
| template <typename T, typename Parspec, bool constant_time_size> |
| struct make_heap_base |
| { |
| typedef typename parameter::binding<Parspec, tag::compare, std::less<T> >::type compare_argument; |
| typedef typename parameter::binding<Parspec, tag::allocator, std::allocator<T> >::type allocator_argument; |
| typedef typename parameter::binding<Parspec, tag::stability_counter_type, boost::uintmax_t >::type stability_counter_type; |
| |
| static const bool is_stable = extract_stable<Parspec>::value; |
| |
| typedef heap_base<T, compare_argument, constant_time_size, stability_counter_type, is_stable> type; |
| }; |
| |
| |
| template <typename Alloc> |
| struct extract_allocator_types |
| { |
| typedef typename Alloc::size_type size_type; |
| typedef typename Alloc::difference_type difference_type; |
| typedef typename Alloc::reference reference; |
| typedef typename Alloc::const_reference const_reference; |
| typedef typename Alloc::pointer pointer; |
| typedef typename Alloc::const_pointer const_pointer; |
| }; |
| |
| |
| } /* namespace detail */ |
| } /* namespace heap */ |
| } /* namespace boost */ |
| |
| #endif /* BOOST_HEAP_DETAIL_STABLE_HEAP_HPP */ |