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