Chris@16: // // boost heap: d-ary heap as containter adaptor
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_D_ARY_HEAP_HPP
Chris@16: #define BOOST_HEAP_D_ARY_HEAP_HPP
Chris@16: 
Chris@16: #include <algorithm>
Chris@16: #include <utility>
Chris@16: #include <vector>
Chris@16: 
Chris@16: #include <boost/assert.hpp>
Chris@16: 
Chris@16: #include <boost/mem_fn.hpp>
Chris@16: #include <boost/heap/detail/heap_comparison.hpp>
Chris@16: #include <boost/heap/detail/ordered_adaptor_iterator.hpp>
Chris@16: #include <boost/heap/detail/stable_heap.hpp>
Chris@16: #include <boost/heap/detail/mutable_heap.hpp>
Chris@16: 
Chris@101: #ifdef BOOST_HAS_PRAGMA_ONCE
Chris@101: #pragma once
Chris@101: #endif
Chris@101: 
Chris@101: 
Chris@16: #ifndef BOOST_DOXYGEN_INVOKED
Chris@16: #ifdef BOOST_HEAP_SANITYCHECKS
Chris@16: #define BOOST_HEAP_ASSERT BOOST_ASSERT
Chris@16: #else
Chris@16: #define BOOST_HEAP_ASSERT(expression)
Chris@16: #endif
Chris@16: #endif
Chris@16: 
Chris@16: namespace boost  {
Chris@16: namespace heap   {
Chris@16: namespace detail {
Chris@16: 
Chris@16: struct nop_index_updater
Chris@16: {
Chris@16:     template <typename T>
Chris@16:     static void run(T &, std::size_t)
Chris@16:     {}
Chris@16: };
Chris@16: 
Chris@16: typedef parameter::parameters<boost::parameter::required<tag::arity>,
Chris@16:                               boost::parameter::optional<tag::allocator>,
Chris@16:                               boost::parameter::optional<tag::compare>,
Chris@16:                               boost::parameter::optional<tag::stable>,
Chris@16:                               boost::parameter::optional<tag::stability_counter_type>,
Chris@16:                               boost::parameter::optional<tag::constant_time_size>
Chris@16:                              > d_ary_heap_signature;
Chris@16: 
Chris@16: 
Chris@16: /* base class for d-ary heap */
Chris@16: template <typename T,
Chris@16:           class BoundArgs,
Chris@16:           class IndexUpdater>
Chris@16: class d_ary_heap:
Chris@16:     private make_heap_base<T, BoundArgs, false>::type
Chris@16: {
Chris@16:     typedef make_heap_base<T, BoundArgs, false> heap_base_maker;
Chris@16: 
Chris@16:     typedef typename heap_base_maker::type super_t;
Chris@16:     typedef typename super_t::internal_type internal_type;
Chris@16: 
Chris@16:     typedef typename heap_base_maker::allocator_argument::template rebind<internal_type>::other internal_type_allocator;
Chris@16:     typedef std::vector<internal_type, internal_type_allocator> container_type;
Chris@16:     typedef typename container_type::const_iterator container_iterator;
Chris@16: 
Chris@16:     typedef IndexUpdater index_updater;
Chris@16: 
Chris@16:     container_type q_;
Chris@16: 
Chris@16:     static const unsigned int D = parameter::binding<BoundArgs, tag::arity>::type::value;
Chris@16: 
Chris@16:     template <typename Heap1, typename Heap2>
Chris@16:     friend struct heap_merge_emulate;
Chris@16: 
Chris@16:     struct implementation_defined:
Chris@16:         extract_allocator_types<typename heap_base_maker::allocator_argument>
Chris@16:     {
Chris@16:         typedef T value_type;
Chris@16:         typedef typename detail::extract_allocator_types<typename heap_base_maker::allocator_argument>::size_type size_type;
Chris@16: 
Chris@16:         typedef typename heap_base_maker::compare_argument value_compare;
Chris@16:         typedef typename heap_base_maker::allocator_argument allocator_type;
Chris@16: 
Chris@16:         struct ordered_iterator_dispatcher
Chris@16:         {
Chris@16:             static size_type max_index(const d_ary_heap * heap)
Chris@16:             {
Chris@16:                 return heap->q_.size() - 1;
Chris@16:             }
Chris@16: 
Chris@16:             static bool is_leaf(const d_ary_heap * heap, size_type index)
Chris@16:             {
Chris@16:                 return !heap->not_leaf(index);
Chris@16:             }
Chris@16: 
Chris@16:             static std::pair<size_type, size_type> get_child_nodes(const d_ary_heap * heap, size_type index)
Chris@16:             {
Chris@16:                 BOOST_HEAP_ASSERT(!is_leaf(heap, index));
Chris@16:                 return std::make_pair(d_ary_heap::first_child_index(index),
Chris@16:                                     heap->last_child_index(index));
Chris@16:             }
Chris@16: 
Chris@16:             static internal_type const & get_internal_value(const d_ary_heap * heap, size_type index)
Chris@16:             {
Chris@16:                 return heap->q_[index];
Chris@16:             }
Chris@16: 
Chris@16:             static value_type const & get_value(internal_type const & arg)
Chris@16:             {
Chris@16:                 return super_t::get_value(arg);
Chris@16:             }
Chris@16:         };
Chris@16: 
Chris@16:         typedef detail::ordered_adaptor_iterator<const value_type,
Chris@16:                                                  internal_type,
Chris@16:                                                  d_ary_heap,
Chris@16:                                                  allocator_type,
Chris@16:                                                  typename super_t::internal_compare,
Chris@16:                                                  ordered_iterator_dispatcher
Chris@16:                                                 > ordered_iterator;
Chris@16: 
Chris@16:         typedef detail::stable_heap_iterator<const value_type, container_iterator, super_t> iterator;
Chris@16:         typedef iterator const_iterator;
Chris@16:         typedef void * handle_type;
Chris@16: 
Chris@16:     };
Chris@16: 
Chris@16:     typedef typename implementation_defined::ordered_iterator_dispatcher ordered_iterator_dispatcher;
Chris@16: 
Chris@16: public:
Chris@16:     typedef T value_type;
Chris@16: 
Chris@16:     typedef typename implementation_defined::size_type size_type;
Chris@16:     typedef typename implementation_defined::difference_type difference_type;
Chris@16:     typedef typename implementation_defined::value_compare value_compare;
Chris@16:     typedef typename implementation_defined::allocator_type allocator_type;
Chris@16:     typedef typename implementation_defined::reference reference;
Chris@16:     typedef typename implementation_defined::const_reference const_reference;
Chris@16:     typedef typename implementation_defined::pointer pointer;
Chris@16:     typedef typename implementation_defined::const_pointer const_pointer;
Chris@16:     typedef typename implementation_defined::iterator iterator;
Chris@16:     typedef typename implementation_defined::const_iterator const_iterator;
Chris@16:     typedef typename implementation_defined::ordered_iterator ordered_iterator;
Chris@16:     typedef typename implementation_defined::handle_type handle_type;
Chris@16: 
Chris@16:     static const bool is_stable = extract_stable<BoundArgs>::value;
Chris@16: 
Chris@16:     explicit d_ary_heap(value_compare const & cmp = value_compare()):
Chris@16:         super_t(cmp)
Chris@16:     {}
Chris@16: 
Chris@16:     d_ary_heap(d_ary_heap const & rhs):
Chris@16:         super_t(rhs), q_(rhs.q_)
Chris@16:     {}
Chris@16: 
Chris@16: #ifndef BOOST_NO_CXX11_RVALUE_REFERENCES
Chris@16:     d_ary_heap(d_ary_heap && rhs):
Chris@16:         super_t(std::move(rhs)), q_(std::move(rhs.q_))
Chris@16:     {}
Chris@16: 
Chris@16:     d_ary_heap & operator=(d_ary_heap && rhs)
Chris@16:     {
Chris@16:         super_t::operator=(std::move(rhs));
Chris@16:         q_ = std::move(rhs.q_);
Chris@16:         return *this;
Chris@16:     }
Chris@16: #endif
Chris@16: 
Chris@16:     d_ary_heap & operator=(d_ary_heap const & rhs)
Chris@16:     {
Chris@16:         static_cast<super_t&>(*this) = static_cast<super_t const &>(rhs);
Chris@16:         q_ = rhs.q_;
Chris@16:         return *this;
Chris@16:     }
Chris@16: 
Chris@16:     bool empty(void) const
Chris@16:     {
Chris@16:         return q_.empty();
Chris@16:     }
Chris@16: 
Chris@16:     size_type size(void) const
Chris@16:     {
Chris@16:         return q_.size();
Chris@16:     }
Chris@16: 
Chris@16:     size_type max_size(void) const
Chris@16:     {
Chris@16:         return q_.max_size();
Chris@16:     }
Chris@16: 
Chris@16:     void clear(void)
Chris@16:     {
Chris@16:         q_.clear();
Chris@16:     }
Chris@16: 
Chris@16:     allocator_type get_allocator(void) const
Chris@16:     {
Chris@16:         return q_.get_allocator();
Chris@16:     }
Chris@16: 
Chris@16:     value_type const & top(void) const
Chris@16:     {
Chris@16:         BOOST_ASSERT(!empty());
Chris@16:         return super_t::get_value(q_.front());
Chris@16:     }
Chris@16: 
Chris@16:     void push(value_type const & v)
Chris@16:     {
Chris@16:         q_.push_back(super_t::make_node(v));
Chris@16:         reset_index(size() - 1, size() - 1);
Chris@16:         siftup(q_.size() - 1);
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:     void emplace(Args&&... args)
Chris@16:     {
Chris@16:         q_.emplace_back(super_t::make_node(std::forward<Args>(args)...));
Chris@16:         reset_index(size() - 1, size() - 1);
Chris@16:         siftup(q_.size() - 1);
Chris@16:     }
Chris@16: #endif
Chris@16:     void pop(void)
Chris@16:     {
Chris@16:         BOOST_ASSERT(!empty());
Chris@16:         std::swap(q_.front(), q_.back());
Chris@16:         q_.pop_back();
Chris@16: 
Chris@16:         if (q_.empty())
Chris@16:             return;
Chris@16: 
Chris@16:         reset_index(0, 0);
Chris@16:         siftdown(0);
Chris@16:     }
Chris@16: 
Chris@16:     void swap(d_ary_heap & rhs)
Chris@16:     {
Chris@16:         super_t::swap(rhs);
Chris@16:         q_.swap(rhs.q_);
Chris@16:     }
Chris@16: 
Chris@16:     iterator begin(void) const
Chris@16:     {
Chris@16:         return iterator(q_.begin());
Chris@16:     }
Chris@16: 
Chris@16:     iterator end(void) const
Chris@16:     {
Chris@16:         return iterator(q_.end());
Chris@16:     }
Chris@16: 
Chris@16:     ordered_iterator ordered_begin(void) const
Chris@16:     {
Chris@16:         return ordered_iterator(0, this, super_t::get_internal_cmp());
Chris@16:     }
Chris@16: 
Chris@16:     ordered_iterator ordered_end(void) const
Chris@16:     {
Chris@16:         return ordered_iterator(size(), this, super_t::get_internal_cmp());
Chris@16:     }
Chris@16: 
Chris@16:     void reserve (size_type element_count)
Chris@16:     {
Chris@16:         q_.reserve(element_count);
Chris@16:     }
Chris@16: 
Chris@16:     value_compare const & value_comp(void) const
Chris@16:     {
Chris@16:         return super_t::value_comp();
Chris@16:     }
Chris@16: 
Chris@16: private:
Chris@16:     void reset_index(size_type index, size_type new_index)
Chris@16:     {
Chris@16:         BOOST_HEAP_ASSERT(index < q_.size());
Chris@16:         index_updater::run(q_[index], new_index);
Chris@16:     }
Chris@16: 
Chris@16:     void siftdown(size_type index)
Chris@16:     {
Chris@16:         while (not_leaf(index)) {
Chris@16:             size_type max_child_index = top_child_index(index);
Chris@16:             if (!super_t::operator()(q_[max_child_index], q_[index])) {
Chris@16:                 reset_index(index, max_child_index);
Chris@16:                 reset_index(max_child_index, index);
Chris@16:                 std::swap(q_[max_child_index], q_[index]);
Chris@16:                 index = max_child_index;
Chris@16:             }
Chris@16:             else
Chris@16:                 return;
Chris@16:         }
Chris@16:     }
Chris@16: 
Chris@16:     /* returns new index */
Chris@16:     void siftup(size_type index)
Chris@16:     {
Chris@16:         while (index != 0) {
Chris@16:             size_type parent = parent_index(index);
Chris@16: 
Chris@16:             if (super_t::operator()(q_[parent], q_[index])) {
Chris@16:                 reset_index(index, parent);
Chris@16:                 reset_index(parent, index);
Chris@16:                 std::swap(q_[parent], q_[index]);
Chris@16:                 index = parent;
Chris@16:             }
Chris@16:             else
Chris@16:                 return;
Chris@16:         }
Chris@16:     }
Chris@16: 
Chris@16:     bool not_leaf(size_type index) const
Chris@16:     {
Chris@16:         const size_t first_child = first_child_index(index);
Chris@16:         return first_child < q_.size();
Chris@16:     }
Chris@16: 
Chris@16:     size_type top_child_index(size_type index) const
Chris@16:     {
Chris@16:         // invariant: index is not a leaf, so the iterator range is not empty
Chris@16: 
Chris@16:         const size_t first_index = first_child_index(index);
Chris@16:         typedef typename container_type::const_iterator container_iterator;
Chris@16: 
Chris@16:         const container_iterator first_child = q_.begin() + first_index;
Chris@16:         const container_iterator end = q_.end();
Chris@16: 
Chris@16:         const size_type max_elements = std::distance(first_child, end);
Chris@16: 
Chris@16:         const container_iterator last_child = (max_elements > D) ? first_child + D
Chris@16:                                                                  : end;
Chris@16: 
Chris@16:         const container_iterator min_element = std::max_element(first_child, last_child, static_cast<super_t const &>(*this));
Chris@16: 
Chris@16:         return min_element - q_.begin();
Chris@16:     }
Chris@16: 
Chris@16:     static size_type parent_index(size_type index)
Chris@16:     {
Chris@16:         return (index - 1) / D;
Chris@16:     }
Chris@16: 
Chris@16:     static size_type first_child_index(size_type index)
Chris@16:     {
Chris@16:         return index * D + 1;
Chris@16:     }
Chris@16: 
Chris@16:     size_type last_child_index(size_type index) const
Chris@16:     {
Chris@16:         const size_t first_index = first_child_index(index);
Chris@16:         const size_type last_index = (std::min)(first_index + D - 1, size() - 1);
Chris@16: 
Chris@16:         return last_index;
Chris@16:     }
Chris@16: 
Chris@16:     template<typename U,
Chris@16:              typename V,
Chris@16:              typename W,
Chris@16:              typename X>
Chris@16:     struct rebind {
Chris@16:         typedef d_ary_heap<U, typename d_ary_heap_signature::bind<boost::heap::stable<heap_base_maker::is_stable>,
Chris@16:                                                                   boost::heap::stability_counter_type<typename heap_base_maker::stability_counter_type>,
Chris@16:                                                                   boost::heap::arity<D>,
Chris@16:                                                                   boost::heap::compare<V>,
Chris@16:                                                                   boost::heap::allocator<W>
Chris@16:                                                                     >::type,
Chris@16:                            X
Chris@16:                           > other;
Chris@16:     };
Chris@16: 
Chris@16:     template <class U> friend class priority_queue_mutable_wrapper;
Chris@16: 
Chris@16:     void update(size_type index)
Chris@16:     {
Chris@16:         if (index == 0) {
Chris@16:             siftdown(index);
Chris@16:             return;
Chris@16:         }
Chris@16:         size_type parent = parent_index(index);
Chris@16: 
Chris@16:         if (super_t::operator()(q_[parent], q_[index]))
Chris@16:             siftup(index);
Chris@16:         else
Chris@16:             siftdown(index);
Chris@16:     }
Chris@16: 
Chris@16:     void erase(size_type index)
Chris@16:     {
Chris@16:         while (index != 0)
Chris@16:         {
Chris@16:             size_type parent = parent_index(index);
Chris@16: 
Chris@16:             reset_index(index, parent);
Chris@16:             reset_index(parent, index);
Chris@16:             std::swap(q_[parent], q_[index]);
Chris@16:             index = parent;
Chris@16:         }
Chris@16:         pop();
Chris@16:     }
Chris@16: 
Chris@16:     void increase(size_type index)
Chris@16:     {
Chris@16:         siftup(index);
Chris@16:     }
Chris@16: 
Chris@16:     void decrease(size_type index)
Chris@16:     {
Chris@16:         siftdown(index);
Chris@16:     }
Chris@16: };
Chris@16: 
Chris@16: 
Chris@16: template <typename T, typename BoundArgs>
Chris@16: struct select_dary_heap
Chris@16: {
Chris@16:     static const bool is_mutable = extract_mutable<BoundArgs>::value;
Chris@16: 
Chris@16:     typedef typename mpl::if_c< is_mutable,
Chris@16:                                 priority_queue_mutable_wrapper<d_ary_heap<T, BoundArgs, nop_index_updater > >,
Chris@16:                                 d_ary_heap<T, BoundArgs, nop_index_updater >
Chris@16:                               >::type type;
Chris@16: };
Chris@16: 
Chris@16: } /* namespace detail */
Chris@16: 
Chris@16: 
Chris@16: 
Chris@16: /**
Chris@16:  * \class d_ary_heap
Chris@16:  * \brief d-ary heap class
Chris@16:  *
Chris@16:  * This class implements an immutable priority queue. Internally, the d-ary heap is represented
Chris@16:  * as dynamically sized array (std::vector), that directly stores the values.
Chris@16:  *
Chris@16:  * The template parameter T is the type to be managed by the container.
Chris@16:  * The user can specify additional options and if no options are provided default options are used.
Chris@16:  *
Chris@16:  * The container supports the following options:
Chris@16:  * - \c boost::heap::arity<>, required
Chris@16:  * - \c boost::heap::compare<>, defaults to \c compare<std::less<T> >
Chris@16:  * - \c boost::heap::stable<>, defaults to \c stable<false>
Chris@16:  * - \c boost::heap::stability_counter_type<>, defaults to \c stability_counter_type<boost::uintmax_t>
Chris@16:  * - \c boost::heap::allocator<>, defaults to \c allocator<std::allocator<T> >
Chris@16:  * - \c boost::heap::mutable_<>, defaults to \c mutable_<false>
Chris@16:  *
Chris@16:  */
Chris@16: #ifdef BOOST_DOXYGEN_INVOKED
Chris@16: template<class T, class ...Options>
Chris@16: #else
Chris@16: template <typename T,
Chris@16:           class A0 = boost::parameter::void_,
Chris@16:           class A1 = boost::parameter::void_,
Chris@16:           class A2 = boost::parameter::void_,
Chris@16:           class A3 = boost::parameter::void_,
Chris@16:           class A4 = boost::parameter::void_,
Chris@16:           class A5 = boost::parameter::void_
Chris@16:          >
Chris@16: #endif
Chris@16: class d_ary_heap:
Chris@16:     public detail::select_dary_heap<T, typename detail::d_ary_heap_signature::bind<A0, A1, A2, A3, A4, A5>::type>::type
Chris@16: {
Chris@16:     typedef typename detail::d_ary_heap_signature::bind<A0, A1, A2, A3, A4, A5>::type bound_args;
Chris@16:     typedef typename detail::select_dary_heap<T, bound_args>::type super_t;
Chris@16: 
Chris@16:     template <typename Heap1, typename Heap2>
Chris@16:     friend struct heap_merge_emulate;
Chris@16: 
Chris@16: #ifndef BOOST_DOXYGEN_INVOKED
Chris@16:     static const bool is_mutable = detail::extract_mutable<bound_args>::value;
Chris@16: 
Chris@16: #define BOOST_HEAP_TYPEDEF_FROM_SUPER_T(NAME)   \
Chris@16:     typedef typename super_t::NAME NAME;
Chris@16: 
Chris@16:     struct implementation_defined
Chris@16:     {
Chris@16:         BOOST_HEAP_TYPEDEF_FROM_SUPER_T(size_type)
Chris@16:         BOOST_HEAP_TYPEDEF_FROM_SUPER_T(difference_type)
Chris@16:         BOOST_HEAP_TYPEDEF_FROM_SUPER_T(value_compare)
Chris@16:         BOOST_HEAP_TYPEDEF_FROM_SUPER_T(allocator_type)
Chris@16:         BOOST_HEAP_TYPEDEF_FROM_SUPER_T(reference)
Chris@16:         BOOST_HEAP_TYPEDEF_FROM_SUPER_T(const_reference)
Chris@16:         BOOST_HEAP_TYPEDEF_FROM_SUPER_T(pointer)
Chris@16:         BOOST_HEAP_TYPEDEF_FROM_SUPER_T(const_pointer)
Chris@16:         BOOST_HEAP_TYPEDEF_FROM_SUPER_T(iterator)
Chris@16:         BOOST_HEAP_TYPEDEF_FROM_SUPER_T(const_iterator)
Chris@16:         BOOST_HEAP_TYPEDEF_FROM_SUPER_T(ordered_iterator)
Chris@16:         BOOST_HEAP_TYPEDEF_FROM_SUPER_T(handle_type)
Chris@16:     };
Chris@16: #undef BOOST_HEAP_TYPEDEF_FROM_SUPER_T
Chris@16: 
Chris@16: #endif
Chris@16: public:
Chris@16:     static const bool constant_time_size = true;
Chris@16:     static const bool has_ordered_iterators = true;
Chris@16:     static const bool is_mergable = false;
Chris@16:     static const bool has_reserve = true;
Chris@16:     static const bool is_stable = super_t::is_stable;
Chris@16: 
Chris@16:     typedef T value_type;
Chris@16:     typedef typename implementation_defined::size_type size_type;
Chris@16:     typedef typename implementation_defined::difference_type difference_type;
Chris@16:     typedef typename implementation_defined::value_compare value_compare;
Chris@16:     typedef typename implementation_defined::allocator_type allocator_type;
Chris@16:     typedef typename implementation_defined::reference reference;
Chris@16:     typedef typename implementation_defined::const_reference const_reference;
Chris@16:     typedef typename implementation_defined::pointer pointer;
Chris@16:     typedef typename implementation_defined::const_pointer const_pointer;
Chris@16:     /// \copydoc boost::heap::priority_queue::iterator
Chris@16:     typedef typename implementation_defined::iterator iterator;
Chris@16:     typedef typename implementation_defined::const_iterator const_iterator;
Chris@16:     typedef typename implementation_defined::ordered_iterator ordered_iterator;
Chris@16:     typedef typename implementation_defined::handle_type handle_type;
Chris@16: 
Chris@16:     /// \copydoc boost::heap::priority_queue::priority_queue(value_compare const &)
Chris@16:     explicit d_ary_heap(value_compare const & cmp = value_compare()):
Chris@16:         super_t(cmp)
Chris@16:     {}
Chris@16: 
Chris@16:     /// \copydoc boost::heap::priority_queue::priority_queue(priority_queue const &)
Chris@16:     d_ary_heap(d_ary_heap const & rhs):
Chris@16:         super_t(rhs)
Chris@16:     {}
Chris@16: 
Chris@16: #ifndef BOOST_NO_CXX11_RVALUE_REFERENCES
Chris@16:     /// \copydoc boost::heap::priority_queue::priority_queue(priority_queue &&)
Chris@16:     d_ary_heap(d_ary_heap && rhs):
Chris@16:         super_t(std::move(rhs))
Chris@16:     {}
Chris@16: 
Chris@16:     /// \copydoc boost::heap::priority_queue::operator=(priority_queue &&)
Chris@16:     d_ary_heap & operator=(d_ary_heap && rhs)
Chris@16:     {
Chris@16:         super_t::operator=(std::move(rhs));
Chris@16:         return *this;
Chris@16:     }
Chris@16: #endif
Chris@16: 
Chris@16:     /// \copydoc boost::heap::priority_queue::operator=(priority_queue const &)
Chris@16:     d_ary_heap & operator=(d_ary_heap const & rhs)
Chris@16:     {
Chris@16:         super_t::operator=(rhs);
Chris@16:         return *this;
Chris@16:     }
Chris@16: 
Chris@16:     /// \copydoc boost::heap::priority_queue::empty
Chris@16:     bool empty(void) const
Chris@16:     {
Chris@16:         return super_t::empty();
Chris@16:     }
Chris@16: 
Chris@16:     /// \copydoc boost::heap::priority_queue::size
Chris@16:     size_type size(void) const
Chris@16:     {
Chris@16:         return super_t::size();
Chris@16:     }
Chris@16: 
Chris@16:     /// \copydoc boost::heap::priority_queue::max_size
Chris@16:     size_type max_size(void) const
Chris@16:     {
Chris@16:         return super_t::max_size();
Chris@16:     }
Chris@16: 
Chris@16:     /// \copydoc boost::heap::priority_queue::clear
Chris@16:     void clear(void)
Chris@16:     {
Chris@16:         super_t::clear();
Chris@16:     }
Chris@16: 
Chris@16:     /// \copydoc boost::heap::priority_queue::get_allocator
Chris@16:     allocator_type get_allocator(void) const
Chris@16:     {
Chris@16:         return super_t::get_allocator();
Chris@16:     }
Chris@16: 
Chris@16:     /// \copydoc boost::heap::priority_queue::top
Chris@16:     value_type const & top(void) const
Chris@16:     {
Chris@16:         return super_t::top();
Chris@16:     }
Chris@16: 
Chris@16:     /// \copydoc boost::heap::priority_queue::push
Chris@16:     typename mpl::if_c<is_mutable, handle_type, void>::type push(value_type const & v)
Chris@16:     {
Chris@16:         return super_t::push(v);
Chris@16:     }
Chris@16: 
Chris@16: #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES) && !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
Chris@16:     /// \copydoc boost::heap::priority_queue::emplace
Chris@16:     template <class... Args>
Chris@16:     typename mpl::if_c<is_mutable, handle_type, void>::type emplace(Args&&... args)
Chris@16:     {
Chris@16:         return super_t::emplace(std::forward<Args>(args)...);
Chris@16:     }
Chris@16: #endif
Chris@16: 
Chris@16:     /// \copydoc boost::heap::priority_queue::operator<(HeapType const & rhs) const
Chris@16:     template <typename HeapType>
Chris@16:     bool operator<(HeapType const & rhs) const
Chris@16:     {
Chris@16:         return detail::heap_compare(*this, rhs);
Chris@16:     }
Chris@16: 
Chris@16:     /// \copydoc boost::heap::priority_queue::operator>(HeapType const & rhs) const
Chris@16:     template <typename HeapType>
Chris@16:     bool operator>(HeapType const & rhs) const
Chris@16:     {
Chris@16:         return detail::heap_compare(rhs, *this);
Chris@16:     }
Chris@16: 
Chris@16:     /// \copydoc boost::heap::priority_queue::operator>=(HeapType const & rhs) const
Chris@16:     template <typename HeapType>
Chris@16:     bool operator>=(HeapType const & rhs) const
Chris@16:     {
Chris@16:         return !operator<(rhs);
Chris@16:     }
Chris@16: 
Chris@16:     /// \copydoc boost::heap::priority_queue::operator<=(HeapType const & rhs) const
Chris@16:     template <typename HeapType>
Chris@16:     bool operator<=(HeapType const & rhs) const
Chris@16:     {
Chris@16:         return !operator>(rhs);
Chris@16:     }
Chris@16: 
Chris@16:     /// \copydoc boost::heap::priority_queue::operator==(HeapType const & rhs) const
Chris@16:     template <typename HeapType>
Chris@16:     bool operator==(HeapType const & rhs) const
Chris@16:     {
Chris@16:         return detail::heap_equality(*this, rhs);
Chris@16:     }
Chris@16: 
Chris@16:     /// \copydoc boost::heap::priority_queue::operator!=(HeapType const & rhs) const
Chris@16:     template <typename HeapType>
Chris@16:     bool operator!=(HeapType const & rhs) const
Chris@16:     {
Chris@16:         return !(*this == rhs);
Chris@16:     }
Chris@16: 
Chris@16:     /**
Chris@16:      * \b Effects: Assigns \c v to the element handled by \c handle & updates the priority queue.
Chris@16:      *
Chris@16:      * \b Complexity: Logarithmic.
Chris@16:      *
Chris@16:      * \b Requirement: data structure must be configured as mutable
Chris@16:      * */
Chris@16:     void update(handle_type handle, const_reference v)
Chris@16:     {
Chris@16:         BOOST_STATIC_ASSERT(is_mutable);
Chris@16:         super_t::update(handle, v);
Chris@16:     }
Chris@16: 
Chris@16:     /**
Chris@16:      * \b Effects: Updates the heap after the element handled by \c handle has been changed.
Chris@16:      *
Chris@16:      * \b Complexity: Logarithmic.
Chris@16:      *
Chris@16:      * \b Note: If this is not called, after a handle has been updated, the behavior of the data structure is undefined!
Chris@16:      *
Chris@16:      * \b Requirement: data structure must be configured as mutable
Chris@16:      * */
Chris@16:     void update(handle_type handle)
Chris@16:     {
Chris@16:         BOOST_STATIC_ASSERT(is_mutable);
Chris@16:         super_t::update(handle);
Chris@16:     }
Chris@16: 
Chris@16:      /**
Chris@16:      * \b Effects: Assigns \c v to the element handled by \c handle & updates the priority queue.
Chris@16:      *
Chris@16:      * \b Complexity: Logarithmic.
Chris@16:      *
Chris@16:      * \b Note: The new value is expected to be greater than the current one
Chris@16:      *
Chris@16:      * \b Requirement: data structure must be configured as mutable
Chris@16:      * */
Chris@16:     void increase(handle_type handle, const_reference v)
Chris@16:     {
Chris@16:         BOOST_STATIC_ASSERT(is_mutable);
Chris@16:         super_t::increase(handle, v);
Chris@16:     }
Chris@16: 
Chris@16:     /**
Chris@16:      * \b Effects: Updates the heap after the element handled by \c handle has been changed.
Chris@16:      *
Chris@16:      * \b Complexity: Logarithmic.
Chris@16:      *
Chris@16:      * \b Note: The new value is expected to be greater than the current one. If this is not called, after a handle has been updated, the behavior of the data structure is undefined!
Chris@16:      *
Chris@16:      * \b Requirement: data structure must be configured as mutable
Chris@16:      * */
Chris@16:     void increase(handle_type handle)
Chris@16:     {
Chris@16:         BOOST_STATIC_ASSERT(is_mutable);
Chris@16:         super_t::increase(handle);
Chris@16:     }
Chris@16: 
Chris@16:      /**
Chris@16:      * \b Effects: Assigns \c v to the element handled by \c handle & updates the priority queue.
Chris@16:      *
Chris@16:      * \b Complexity: Logarithmic.
Chris@16:      *
Chris@16:      * \b Note: The new value is expected to be less than the current one
Chris@16:      *
Chris@16:      * \b Requirement: data structure must be configured as mutable
Chris@16:      * */
Chris@16:     void decrease(handle_type handle, const_reference v)
Chris@16:     {
Chris@16:         BOOST_STATIC_ASSERT(is_mutable);
Chris@16:         super_t::decrease(handle, v);
Chris@16:     }
Chris@16: 
Chris@16:     /**
Chris@16:      * \b Effects: Updates the heap after the element handled by \c handle has been changed.
Chris@16:      *
Chris@16:      * \b Complexity: Logarithmic.
Chris@16:      *
Chris@16:      * \b Note: The new value is expected to be less than the current one. If this is not called, after a handle has been updated, the behavior of the data structure is undefined!
Chris@16:      *
Chris@16:      * \b Requirement: data structure must be configured as mutable
Chris@16:      * */
Chris@16:     void decrease(handle_type handle)
Chris@16:     {
Chris@16:         BOOST_STATIC_ASSERT(is_mutable);
Chris@16:         super_t::decrease(handle);
Chris@16:     }
Chris@16: 
Chris@16:     /**
Chris@16:      * \b Effects: Removes the element handled by \c handle from the priority_queue.
Chris@16:      *
Chris@16:      * \b Complexity: Logarithmic.
Chris@16:      *
Chris@16:      * \b Requirement: data structure must be configured as mutable
Chris@16:      * */
Chris@16:     void erase(handle_type handle)
Chris@16:     {
Chris@16:         BOOST_STATIC_ASSERT(is_mutable);
Chris@16:         super_t::erase(handle);
Chris@16:     }
Chris@16: 
Chris@16:     /**
Chris@16:      * \b Effects: Casts an iterator to a node handle.
Chris@16:      *
Chris@16:      * \b Complexity: Constant.
Chris@16:      *
Chris@16:      * \b Requirement: data structure must be configured as mutable
Chris@16:      * */
Chris@16:     static handle_type s_handle_from_iterator(iterator const & it)
Chris@16:     {
Chris@16:         BOOST_STATIC_ASSERT(is_mutable);
Chris@16:         return super_t::s_handle_from_iterator(it);
Chris@16:     }
Chris@16: 
Chris@16:     /// \copydoc boost::heap::priority_queue::pop
Chris@16:     void pop(void)
Chris@16:     {
Chris@16:         super_t::pop();
Chris@16:     }
Chris@16: 
Chris@16:     /// \copydoc boost::heap::priority_queue::swap
Chris@16:     void swap(d_ary_heap & rhs)
Chris@16:     {
Chris@16:         super_t::swap(rhs);
Chris@16:     }
Chris@16: 
Chris@16:     /// \copydoc boost::heap::priority_queue::begin
Chris@16:     const_iterator begin(void) const
Chris@16:     {
Chris@16:         return super_t::begin();
Chris@16:     }
Chris@16: 
Chris@16:     /// \copydoc boost::heap::priority_queue::begin
Chris@16:     iterator begin(void)
Chris@16:     {
Chris@16:         return super_t::begin();
Chris@16:     }
Chris@16: 
Chris@16:     /// \copydoc boost::heap::priority_queue::end
Chris@16:     iterator end(void)
Chris@16:     {
Chris@16:         return super_t::end();
Chris@16:     }
Chris@16: 
Chris@16:     /// \copydoc boost::heap::priority_queue::end
Chris@16:     const_iterator end(void) const
Chris@16:     {
Chris@16:         return super_t::end();
Chris@16:     }
Chris@16: 
Chris@16:     /// \copydoc boost::heap::fibonacci_heap::ordered_begin
Chris@16:     ordered_iterator ordered_begin(void) const
Chris@16:     {
Chris@16:         return super_t::ordered_begin();
Chris@16:     }
Chris@16: 
Chris@16:     /// \copydoc boost::heap::fibonacci_heap::ordered_end
Chris@16:     ordered_iterator ordered_end(void) const
Chris@16:     {
Chris@16:         return super_t::ordered_end();
Chris@16:     }
Chris@16: 
Chris@16:     /// \copydoc boost::heap::priority_queue::reserve
Chris@16:     void reserve (size_type element_count)
Chris@16:     {
Chris@16:         super_t::reserve(element_count);
Chris@16:     }
Chris@16: 
Chris@16:     /// \copydoc boost::heap::priority_queue::value_comp
Chris@16:     value_compare const & value_comp(void) const
Chris@16:     {
Chris@16:         return super_t::value_comp();
Chris@16:     }
Chris@16: };
Chris@16: 
Chris@16: } /* namespace heap */
Chris@16: } /* namespace boost */
Chris@16: 
Chris@16: #undef BOOST_HEAP_ASSERT
Chris@16: 
Chris@16: #endif /* BOOST_HEAP_D_ARY_HEAP_HPP */