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