skew heap More...
#include <skew_heap.hpp>
Public Types | |
typedef T | value_type |
typedef implementation_defined::size_type | size_type |
typedef implementation_defined::difference_type | difference_type |
typedef implementation_defined::value_compare | value_compare |
typedef implementation_defined::allocator_type | allocator_type |
typedef implementation_defined::reference | reference |
typedef implementation_defined::const_reference | const_reference |
typedef implementation_defined::pointer | pointer |
typedef implementation_defined::const_pointer | const_pointer |
typedef implementation_defined::iterator | iterator |
Note: The iterator does not traverse the priority queue in order of the priorities. More... | |
typedef implementation_defined::const_iterator | const_iterator |
typedef implementation_defined::ordered_iterator | ordered_iterator |
typedef mpl::if_c< is_mutable, typename implementation_defined::handle_type, void * >::type | handle_type |
Public Member Functions | |
skew_heap (value_compare const &cmp=value_compare()) | |
Effects: constructs an empty priority queue. More... | |
skew_heap (skew_heap const &rhs) | |
Effects: copy-constructs priority queue from rhs. More... | |
skew_heap & | operator= (skew_heap const &rhs) |
Effects: Assigns priority queue from rhs. More... | |
skew_heap (skew_heap &&rhs) | |
Effects: C++11-style move constructor. More... | |
skew_heap & | operator= (skew_heap &&rhs) |
Effects: C++11-style move assignment. More... | |
~skew_heap (void) | |
mpl::if_c< is_mutable, handle_type, void >::type | push (value_type const &v) |
Effects: Adds a new element to the priority queue. More... | |
template<typename... Args> | |
mpl::if_c< is_mutable, handle_type, void >::type | emplace (Args &&...args) |
Effects: Adds a new element to the priority queue. More... | |
bool | empty (void) const |
Effects: Returns true, if the priority queue contains no elements. More... | |
size_type | size (void) const |
Effects: Returns the number of elements contained in the priority queue. More... | |
size_type | max_size (void) const |
Effects: Returns the maximum number of elements the priority queue can contain. More... | |
void | clear (void) |
Effects: Removes all elements from the priority queue. More... | |
allocator_type | get_allocator (void) const |
Effects: Returns allocator. More... | |
void | swap (skew_heap &rhs) |
Effects: Swaps two priority queues. More... | |
const_reference | top (void) const |
Effects: Returns a const_reference to the maximum element. More... | |
void | pop (void) |
Effects: Removes the top element from the priority queue. More... | |
iterator | begin (void) const |
Effects: Returns an iterator to the first element contained in the priority queue. More... | |
iterator | end (void) const |
Effects: Returns an iterator to the end of the priority queue. More... | |
ordered_iterator | ordered_begin (void) const |
Effects: Returns an ordered iterator to the first element contained in the priority queue. More... | |
ordered_iterator | ordered_end (void) const |
Effects: Returns an ordered iterator to the first element contained in the priority queue. More... | |
void | merge (skew_heap &rhs) |
Effects: Merge all elements from rhs into this More... | |
value_compare const & | value_comp (void) const |
Effect: Returns the value_compare object used by the priority queue More... | |
template<typename HeapType > | |
bool | operator< (HeapType const &rhs) const |
Returns: Element-wise comparison of heap data structures More... | |
template<typename HeapType > | |
bool | operator> (HeapType const &rhs) const |
Returns: Element-wise comparison of heap data structures More... | |
template<typename HeapType > | |
bool | operator>= (HeapType const &rhs) const |
Returns: Element-wise comparison of heap data structures More... | |
template<typename HeapType > | |
bool | operator<= (HeapType const &rhs) const |
Returns: Element-wise comparison of heap data structures More... | |
template<typename HeapType > | |
bool | operator== (HeapType const &rhs) const |
Equivalent comparison Returns: True, if both heap data structures are equivalent. More... | |
template<typename HeapType > | |
bool | operator!= (HeapType const &rhs) const |
Equivalent comparison Returns: True, if both heap data structures are not equivalent. More... | |
void | erase (handle_type object) |
Effects: Removes the element handled by handle from the priority_queue. More... | |
void | update (handle_type handle, const_reference v) |
Effects: Assigns v to the element handled by handle & updates the priority queue. More... | |
void | update (handle_type handle) |
Effects: Updates the heap after the element handled by handle has been changed. More... | |
void | increase (handle_type handle, const_reference v) |
Effects: Assigns v to the element handled by handle & updates the priority queue. More... | |
void | increase (handle_type handle) |
Effects: Updates the heap after the element handled by handle has been changed. More... | |
void | decrease (handle_type handle, const_reference v) |
Effects: Assigns v to the element handled by handle & updates the priority queue. More... | |
void | decrease (handle_type handle) |
Effects: Updates the heap after the element handled by handle has been changed. More... | |
Static Public Member Functions | |
static handle_type | s_handle_from_iterator (iterator const &it) |
Effects: Casts an iterator to a node handle. More... | |
Static Public Attributes | |
static const bool | constant_time_size = super_t::constant_time_size |
static const bool | has_ordered_iterators = true |
static const bool | is_mergable = true |
static const bool | is_stable = detail::extract_stable<bound_args>::value |
static const bool | has_reserve = false |
static const bool | is_mutable = detail::extract_mutable<bound_args>::value |
Friends | |
template<typename Heap1 , typename Heap2 > | |
struct | heap_merge_emulate |
skew heap
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:
boost::heap::compare<>
, defaults to compare<std::less<T>
>boost::heap::stable<>
, defaults to stable<false>
boost::heap::stability_counter_type<>
, defaults to stability_counter_type<boost::uintmax_t>
boost::heap::allocator<>
, defaults to allocator<std::allocator<T>
>boost::heap::constant_time_size<>
, defaults to constant_time_size<true>
boost::heap::store_parent_pointer<>
, defaults to store_parent_pointer<true>
. Maintaining a parent pointer adds some maintenance and size overhead, but iterating a heap is more efficient.boost::heap::mutable<>
, defaults to mutable<false>
. typedef implementation_defined::allocator_type boost::heap::skew_heap< T, A0, A1, A2, A3, A4, A5, A6 >::allocator_type |
typedef implementation_defined::const_iterator boost::heap::skew_heap< T, A0, A1, A2, A3, A4, A5, A6 >::const_iterator |
typedef implementation_defined::const_pointer boost::heap::skew_heap< T, A0, A1, A2, A3, A4, A5, A6 >::const_pointer |
typedef implementation_defined::const_reference boost::heap::skew_heap< T, A0, A1, A2, A3, A4, A5, A6 >::const_reference |
typedef implementation_defined::difference_type boost::heap::skew_heap< T, A0, A1, A2, A3, A4, A5, A6 >::difference_type |
typedef mpl::if_c<is_mutable, typename implementation_defined::handle_type, void*>::type boost::heap::skew_heap< T, A0, A1, A2, A3, A4, A5, A6 >::handle_type |
typedef implementation_defined::iterator boost::heap::skew_heap< T, A0, A1, A2, A3, A4, A5, A6 >::iterator |
Note: The iterator does not traverse the priority queue in order of the priorities.
typedef implementation_defined::ordered_iterator boost::heap::skew_heap< T, A0, A1, A2, A3, A4, A5, A6 >::ordered_iterator |
typedef implementation_defined::pointer boost::heap::skew_heap< T, A0, A1, A2, A3, A4, A5, A6 >::pointer |
typedef implementation_defined::reference boost::heap::skew_heap< T, A0, A1, A2, A3, A4, A5, A6 >::reference |
typedef implementation_defined::size_type boost::heap::skew_heap< T, A0, A1, A2, A3, A4, A5, A6 >::size_type |
typedef implementation_defined::value_compare boost::heap::skew_heap< T, A0, A1, A2, A3, A4, A5, A6 >::value_compare |
typedef T boost::heap::skew_heap< T, A0, A1, A2, A3, A4, A5, A6 >::value_type |
|
inlineexplicit |
Effects: constructs an empty priority queue.
Complexity: Constant.
|
inline |
Effects: copy-constructs priority queue from rhs.
Complexity: Linear.
References boost::heap::skew_heap< T, A0, A1, A2, A3, A4, A5, A6 >::empty().
|
inline |
Effects: C++11-style move constructor.
Complexity: Constant.
Note: Only available, if BOOST_NO_CXX11_RVALUE_REFERENCES is not defined
|
inline |
|
inline |
Effects: Returns an iterator to the first element contained in the priority queue.
Complexity: Constant.
|
inline |
Effects: Removes all elements from the priority queue.
Complexity: Linear.
References boost::heap::skew_heap< T, A0, A1, A2, A3, A4, A5, A6 >::empty().
Referenced by boost::heap::skew_heap< T, A0, A1, A2, A3, A4, A5, A6 >::operator=(), and boost::heap::skew_heap< T, A0, A1, A2, A3, A4, A5, A6 >::~skew_heap().
|
inline |
Effects: Assigns v
to the element handled by handle
& updates the priority queue.
Complexity: Logarithmic (amortized).
Note: The new value is expected to be less than the current one
References boost::BOOST_STATIC_ASSERT().
Referenced by boost::heap::skew_heap< T, A0, A1, A2, A3, A4, A5, A6 >::update().
|
inline |
Effects: Updates the heap after the element handled by handle
has been changed.
Complexity: Logarithmic (amortized).
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!
References boost::BOOST_STATIC_ASSERT().
|
inline |
Effects: Adds a new element to the priority queue.
The element is directly constructed in-place.
Complexity: Logarithmic (amortized).
References boost::python::args().
|
inline |
Effects: Returns true, if the priority queue contains no elements.
Complexity: Constant.
Referenced by boost::heap::skew_heap< T, A0, A1, A2, A3, A4, A5, A6 >::clear(), boost::heap::skew_heap< T, A0, A1, A2, A3, A4, A5, A6 >::merge(), boost::heap::skew_heap< T, A0, A1, A2, A3, A4, A5, A6 >::pop(), boost::heap::skew_heap< T, A0, A1, A2, A3, A4, A5, A6 >::skew_heap(), and boost::heap::skew_heap< T, A0, A1, A2, A3, A4, A5, A6 >::top().
|
inline |
Effects: Returns an iterator to the end of the priority queue.
Complexity: Constant.
|
inline |
Effects: Removes the element handled by handle
from the priority_queue.
Complexity: Logarithmic (amortized).
References boost::BOOST_STATIC_ASSERT().
|
inline |
Effects: Returns allocator.
Complexity: Constant.
|
inline |
Effects: Assigns v
to the element handled by handle
& updates the priority queue.
Complexity: Logarithmic (amortized).
Note: The new value is expected to be greater than the current one
References boost::BOOST_STATIC_ASSERT().
Referenced by boost::heap::skew_heap< T, A0, A1, A2, A3, A4, A5, A6 >::update().
|
inline |
Effects: Updates the heap after the element handled by handle
has been changed.
Complexity: Logarithmic (amortized).
Note: If this is not called, after a handle has been updated, the behavior of the data structure is undefined!
References boost::BOOST_STATIC_ASSERT().
|
inline |
Effects: Returns the maximum number of elements the priority queue can contain.
Complexity: Constant.
|
inline |
Effects: Merge all elements from rhs into this
Complexity: Logarithmic (amortized).
References boost::icl::add(), boost::heap::skew_heap< T, A0, A1, A2, A3, A4, A5, A6 >::empty(), and boost::accumulators::extract::max.
|
inline |
Equivalent comparison Returns: True, if both heap data structures are not equivalent.
Requirement: the value_compare
object of both heaps must match.
|
inline |
Returns: Element-wise comparison of heap data structures
Requirement: the value_compare
object of both heaps must match.
Referenced by boost::heap::skew_heap< T, A0, A1, A2, A3, A4, A5, A6 >::operator>=().
|
inline |
Returns: Element-wise comparison of heap data structures
Requirement: the value_compare
object of both heaps must match.
References boost::heap::skew_heap< T, A0, A1, A2, A3, A4, A5, A6 >::operator>().
|
inline |
Effects: Assigns priority queue from rhs.
Complexity: Linear.
References boost::heap::skew_heap< T, A0, A1, A2, A3, A4, A5, A6 >::clear().
|
inline |
Effects: C++11-style move assignment.
Complexity: Constant.
Note: Only available, if BOOST_NO_CXX11_RVALUE_REFERENCES is not defined
References boost::fusion::move(), and boost::heap::detail::make_skew_heap_base< T, BoundArgs >::type::operator=().
|
inline |
Equivalent comparison Returns: True, if both heap data structures are equivalent.
Requirement: the value_compare
object of both heaps must match.
|
inline |
Returns: Element-wise comparison of heap data structures
Requirement: the value_compare
object of both heaps must match.
Referenced by boost::heap::skew_heap< T, A0, A1, A2, A3, A4, A5, A6 >::operator<=().
|
inline |
Returns: Element-wise comparison of heap data structures
Requirement: the value_compare
object of both heaps must match.
References boost::heap::skew_heap< T, A0, A1, A2, A3, A4, A5, A6 >::operator<().
|
inline |
Effects: Returns an ordered iterator to the first element contained in the priority queue.
Note: Ordered iterators traverse the priority queue in heap order.
|
inline |
Effects: Returns an ordered iterator to the first element contained in the priority queue.
Note: Ordered iterators traverse the priority queue in heap order.
|
inline |
Effects: Removes the top element from the priority queue.
Complexity: Logarithmic (amortized).
References BOOST_ASSERT, BOOST_HEAP_ASSERT, boost::heap::skew_heap< T, A0, A1, A2, A3, A4, A5, A6 >::empty(), and boost::heap::skew_heap< T, A0, A1, A2, A3, A4, A5, A6 >::top().
|
inline |
Effects: Adds a new element to the priority queue.
Complexity: Logarithmic (amortized).
References boost::xpressive::push.
|
inlinestatic |
Effects: Casts an iterator to a node handle.
Complexity: Constant.
Requirement: data structure must be configured as mutable
References boost::python::ptr().
|
inline |
Effects: Returns the number of elements contained in the priority queue.
Complexity: Constant, if configured with constant_time_size<true>, otherwise linear.
|
inline |
|
inline |
Effects: Returns a const_reference to the maximum element.
Complexity: Constant.
References BOOST_ASSERT, and boost::heap::skew_heap< T, A0, A1, A2, A3, A4, A5, A6 >::empty().
Referenced by boost::heap::skew_heap< T, A0, A1, A2, A3, A4, A5, A6 >::pop().
|
inline |
Effects: Assigns v
to the element handled by handle
& updates the priority queue.
Complexity: Logarithmic (amortized).
References boost::BOOST_STATIC_ASSERT(), boost::heap::skew_heap< T, A0, A1, A2, A3, A4, A5, A6 >::decrease(), and boost::heap::skew_heap< T, A0, A1, A2, A3, A4, A5, A6 >::increase().
|
inline |
Effects: Updates the heap after the element handled by handle
has been changed.
Complexity: Logarithmic (amortized).
Note: If this is not called, after a handle has been updated, the behavior of the data structure is undefined!
References boost::BOOST_STATIC_ASSERT(), boost::heap::skew_heap< T, A0, A1, A2, A3, A4, A5, A6 >::decrease(), and boost::heap::skew_heap< T, A0, A1, A2, A3, A4, A5, A6 >::increase().
|
inline |
Effect: Returns the value_compare object used by the priority queue
|
friend |
|
static |
|
static |
|
static |
|
static |
|
static |
|
static |