Boost C++ Libraries

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_ )
    {}

    /**
     * \b Effects: C++11-style move constructor.
     *
     * \b Complexity: Constant.
     *
     * */
    priority_queue( priority_queue&& rhs ) noexcept( std::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.
     *
     * */
    priority_queue& operator=( priority_queue&& rhs ) noexcept( std::is_nothrow_move_assignable< super_t >::value )
    {
        super_t::operator=( std::move( rhs ) );
        q_ = std::move( rhs.q_ );
        return *this;
    }

    /**
     * \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 noexcept
    {
        return q_.empty();
    }

    /**
     * \b Effects: Returns the number of elements contained in the priority queue.
     *
     * \b Complexity: Constant.
     *
     * */
    size_type size( void ) const 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 noexcept
    {
        return q_.max_size();
    }

    /**
     * \b Effects: Removes all elements from the priority queue.
     *
     * \b Complexity: Linear.
     *
     * */
    void clear( void ) 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 ) );
    }

    /**
     * \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 ) );
    }

    /**
     * \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 ) noexcept( std::is_nothrow_move_constructible< super_t >::value
                                               && std::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 noexcept
    {
        return iterator( q_.begin() );
    }

    /**
     * \b Effects: Returns an iterator to the end of the priority queue.
     *
     * \b Complexity: Constant.
     *
     * */
    iterator end( void ) const 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 */