boost/heap/d_ary_heap.hpp
// // boost heap: d-ary heap as container 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/heap/detail/heap_comparison.hpp> #include <boost/heap/detail/mutable_heap.hpp> #include <boost/heap/detail/ordered_adaptor_iterator.hpp> #include <boost/heap/detail/stable_heap.hpp> #include <boost/mem_fn.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 boost::allocator_rebind< typename heap_base_maker::allocator_argument, internal_type >::type 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 boost::conditional< 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 boost::conditional< 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 boost::conditional< 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 boost::heap #undef BOOST_HEAP_ASSERT #endif /* BOOST_HEAP_D_ARY_HEAP_HPP */