boost/heap/priority_queue.hpp
// boost heap: wrapper for stl heap // // 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_PRIORITY_QUEUE_HPP #define BOOST_HEAP_PRIORITY_QUEUE_HPP #include <algorithm> #include <utility> #include <vector> #include <boost/assert.hpp> #include <boost/heap/detail/heap_comparison.hpp> #include <boost/heap/detail/stable_heap.hpp> #ifdef BOOST_HAS_PRAGMA_ONCE # pragma once #endif namespace boost { namespace heap { namespace detail { typedef parameter::parameters< boost::parameter::optional< tag::allocator >, boost::parameter::optional< tag::compare >, boost::parameter::optional< tag::stable >, boost::parameter::optional< tag::stability_counter_type > > priority_queue_signature; } // namespace detail /** * \class priority_queue * \brief priority queue, based on stl heap functions * * The priority_queue class is a wrapper for the stl heap functions.<br> * 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::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> > * */ #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_ > #endif class priority_queue : private detail::make_heap_base< T, typename detail::priority_queue_signature::bind< A0, A1, A2, A3 >::type, false >::type { typedef detail::make_heap_base< T, typename detail::priority_queue_signature::bind< A0, A1, A2, A3 >::type, 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; template < typename Heap1, typename Heap2 > friend struct detail::heap_merge_emulate; container_type q_; #ifndef BOOST_DOXYGEN_INVOKED struct implementation_defined : detail::extract_allocator_types< typename heap_base_maker::allocator_argument > { typedef typename heap_base_maker::compare_argument value_compare; typedef detail::stable_heap_iterator< T, typename container_type::const_iterator, super_t > iterator; typedef iterator const_iterator; typedef typename container_type::allocator_type allocator_type; }; #endif 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; /** * \b Note: The iterator does not traverse the priority queue in order of the priorities. * */ typedef typename implementation_defined::iterator iterator; typedef typename implementation_defined::const_iterator const_iterator; static const bool constant_time_size = true; static const bool has_ordered_iterators = false; static const bool is_mergable = false; static const bool is_stable = heap_base_maker::is_stable; static const bool has_reserve = true; /** * \b Effects: constructs an empty priority queue. * * \b Complexity: Constant. * * */ explicit priority_queue( value_compare const& cmp = value_compare() ) : super_t( cmp ) {} /** * \b Effects: constructs an empty priority queue. * * \b Complexity: Constant. * * */ explicit priority_queue( allocator_type const& alloc ) : q_( alloc ) {} /** * \b Effects: copy-constructs priority queue from rhs. * * \b Complexity: Linear. * * */ priority_queue( priority_queue const& rhs ) : super_t( rhs ), q_( rhs.q_ ) {} #ifndef BOOST_NO_CXX11_RVALUE_REFERENCES /** * \b Effects: C++11-style move constructor. * * \b Complexity: Constant. * * \b Note: Only available, if BOOST_NO_CXX11_RVALUE_REFERENCES is not defined * */ priority_queue( priority_queue&& rhs ) BOOST_NOEXCEPT_IF( boost::is_nothrow_move_constructible< super_t >::value ) : super_t( std::move( rhs ) ), q_( std::move( rhs.q_ ) ) {} /** * \b Effects: C++11-style move assignment. * * \b Complexity: Constant. * * \b Note: Only available, if BOOST_NO_CXX11_RVALUE_REFERENCES is not defined * */ priority_queue& operator=( priority_queue&& rhs ) BOOST_NOEXCEPT_IF( boost::is_nothrow_move_assignable< super_t >::value ) { super_t::operator=( std::move( rhs ) ); q_ = std::move( rhs.q_ ); return *this; } #endif /** * \b Effects: Assigns priority queue from rhs. * * \b Complexity: Linear. * * */ priority_queue& operator=( priority_queue const& rhs ) { static_cast< super_t& >( *this ) = static_cast< super_t const& >( rhs ); q_ = rhs.q_; return *this; } /** * \b Effects: Returns true, if the priority queue contains no elements. * * \b Complexity: Constant. * * */ bool empty( void ) const BOOST_NOEXCEPT { return q_.empty(); } /** * \b Effects: Returns the number of elements contained in the priority queue. * * \b Complexity: Constant. * * */ size_type size( void ) const BOOST_NOEXCEPT { return q_.size(); } /** * \b Effects: Returns the maximum number of elements the priority queue can contain. * * \b Complexity: Constant. * * */ size_type max_size( void ) const BOOST_NOEXCEPT { return q_.max_size(); } /** * \b Effects: Removes all elements from the priority queue. * * \b Complexity: Linear. * * */ void clear( void ) BOOST_NOEXCEPT { q_.clear(); } /** * \b Effects: Returns allocator. * * \b Complexity: Constant. * * */ allocator_type get_allocator( void ) const { return q_.get_allocator(); } /** * \b Effects: Returns a const_reference to the maximum element. * * \b Complexity: Constant. * * */ const_reference top( void ) const { BOOST_ASSERT( !empty() ); return super_t::get_value( q_.front() ); } /** * \b Effects: Adds a new element to the priority queue. * * \b Complexity: Logarithmic (amortized). Linear (worst case). * * */ void push( value_type const& v ) { q_.push_back( super_t::make_node( v ) ); std::push_heap( q_.begin(), q_.end(), static_cast< super_t const& >( *this ) ); } #if !defined( BOOST_NO_CXX11_RVALUE_REFERENCES ) && !defined( BOOST_NO_CXX11_VARIADIC_TEMPLATES ) /** * \b Effects: Adds a new element to the priority queue. The element is directly constructed in-place. * * \b Complexity: Logarithmic (amortized). Linear (worst case). * * */ template < class... Args > void emplace( Args&&... args ) { q_.emplace_back( super_t::make_node( std::forward< Args >( args )... ) ); std::push_heap( q_.begin(), q_.end(), static_cast< super_t const& >( *this ) ); } #endif /** * \b Effects: Removes the top element from the priority queue. * * \b Complexity: Logarithmic (amortized). Linear (worst case). * * */ void pop( void ) { BOOST_ASSERT( !empty() ); std::pop_heap( q_.begin(), q_.end(), static_cast< super_t const& >( *this ) ); q_.pop_back(); } /** * \b Effects: Swaps two priority queues. * * \b Complexity: Constant. * * */ void swap( priority_queue& rhs ) BOOST_NOEXCEPT_IF( boost::is_nothrow_move_constructible< super_t >::value&& boost::is_nothrow_move_assignable< super_t >::value ) { super_t::swap( rhs ); q_.swap( rhs.q_ ); } /** * \b Effects: Returns an iterator to the first element contained in the priority queue. * * \b Complexity: Constant. * * */ iterator begin( void ) const BOOST_NOEXCEPT { return iterator( q_.begin() ); } /** * \b Effects: Returns an iterator to the end of the priority queue. * * \b Complexity: Constant. * * */ iterator end( void ) const BOOST_NOEXCEPT { return iterator( q_.end() ); } /** * \b Effects: Reserves memory for element_count elements * * \b Complexity: Linear. * * \b Node: Invalidates iterators * * */ void reserve( size_type element_count ) { q_.reserve( element_count ); } /** * \b Effect: Returns the value_compare object used by the priority queue * * */ value_compare const& value_comp( void ) const { return super_t::value_comp(); } /** * \b Returns: Element-wise comparison of heap data structures * * \b Requirement: the \c value_compare object of both heaps must match. * * */ template < typename HeapType > bool operator<( HeapType const& rhs ) const { return detail::heap_compare( *this, rhs ); } /** * \b Returns: Element-wise comparison of heap data structures * * \b Requirement: the \c value_compare object of both heaps must match. * * */ template < typename HeapType > bool operator>( HeapType const& rhs ) const { return detail::heap_compare( rhs, *this ); } /** * \b Returns: Element-wise comparison of heap data structures * * \b Requirement: the \c value_compare object of both heaps must match. * * */ template < typename HeapType > bool operator>=( HeapType const& rhs ) const { return !operator<( rhs ); } /** * \b Returns: Element-wise comparison of heap data structures * * \b Requirement: the \c value_compare object of both heaps must match. * * */ template < typename HeapType > bool operator<=( HeapType const& rhs ) const { return !operator>( rhs ); } /** \brief Equivalent comparison * \b Returns: True, if both heap data structures are equivalent. * * \b Requirement: the \c value_compare object of both heaps must match. * * */ template < typename HeapType > bool operator==( HeapType const& rhs ) const { return detail::heap_equality( *this, rhs ); } /** \brief Equivalent comparison * \b Returns: True, if both heap data structures are not equivalent. * * \b Requirement: the \c value_compare object of both heaps must match. * * */ template < typename HeapType > bool operator!=( HeapType const& rhs ) const { return !( *this == rhs ); } }; }} // namespace boost::heap #endif /* BOOST_HEAP_PRIORITY_QUEUE_HPP */