|
Home | Libraries | People | FAQ | More |
boost::heap::skew_heap — skew heap
// In header: <boost/heap/skew_heap.hpp> template<typename T, class... Options> class skew_heap { 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; 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; // member classes/structs/unions template<typename T, typename A0 = boost::parameter::void_, typename A1 = boost::parameter::void_, typename A2 = boost::parameter::void_, typename A3 = boost::parameter::void_, typename A4 = boost::parameter::void_, typename A5 = boost::parameter::void_, typename A6 = boost::parameter::void_> struct implementation_defined { // types typedef T value_type; typedef base_maker::compare_argument value_compare; typedef base_maker::allocator_type allocator_type; typedef base_maker::node_type node; typedef allocator_type::pointer node_pointer; typedef allocator_type::const_pointer const_node_pointer; typedef unspecified value_extractor; typedef boost::array< node_pointer, 2 > child_list_type; typedef child_list_type::iterator child_list_iterator; typedef unspecified iterator; typedef iterator const_iterator; typedef unspecified ordered_iterator; typedef unspecified reference; typedef unspecified handle_type; }; template<typename T, typename A0 = boost::parameter::void_, typename A1 = boost::parameter::void_, typename A2 = boost::parameter::void_, typename A3 = boost::parameter::void_, typename A4 = boost::parameter::void_, typename A5 = boost::parameter::void_, typename A6 = boost::parameter::void_> struct push_handle { // public static functions static handle_type push(skew_heap *, const_reference); template<class... Args> static handle_type emplace(skew_heap *, Args &&...); }; template<typename T, typename A0 = boost::parameter::void_, typename A1 = boost::parameter::void_, typename A2 = boost::parameter::void_, typename A3 = boost::parameter::void_, typename A4 = boost::parameter::void_, typename A5 = boost::parameter::void_, typename A6 = boost::parameter::void_> struct push_void { // public static functions static void push(skew_heap *, const_reference); template<class... Args> static void emplace(skew_heap *, Args &&...); }; // construct/copy/destruct explicit skew_heap(value_compare const & = value_compare()); skew_heap(skew_heap const &); skew_heap(skew_heap &&); skew_heap & operator=(skew_heap const &); skew_heap & operator=(skew_heap &&); ~skew_heap(void); // public member functions mpl::if_c< is_mutable, handle_type, void >::type push(value_type const &); template<typename... Args> mpl::if_c< is_mutable, handle_type, void >::type emplace(Args &&...); bool empty(void) const; size_type size(void) const; size_type max_size(void) const; void clear(void); allocator_type get_allocator(void) const; void swap(skew_heap &); const_reference top(void) const; void pop(void); iterator begin(void) const; iterator end(void) const; ordered_iterator ordered_begin(void) const; ordered_iterator ordered_end(void) const; void merge(skew_heap &); value_compare const & value_comp(void) const; template<typename HeapType> bool operator<(HeapType const &) const; template<typename HeapType> bool operator>(HeapType const &) const; template<typename HeapType> bool operator>=(HeapType const &) const; template<typename HeapType> bool operator<=(HeapType const &) const; template<typename HeapType> bool operator==(HeapType const &) const; template<typename HeapType> bool operator!=(HeapType const &) const; void erase(handle_type); void update(handle_type, const_reference); void update(handle_type); void increase(handle_type, const_reference); void increase(handle_type); void decrease(handle_type, const_reference); void decrease(handle_type); // public static functions static handle_type s_handle_from_iterator(iterator const &); // private member functions node_pointer push_internal(const_reference); template<class... Args> node_pointer emplace_internal(Args &&...); void unlink_node(node_pointer); void clone_tree(skew_heap const &); void merge_node(node_pointer); node_pointer merge_nodes(node_pointer, node_pointer, node_pointer); node_pointer merge_children(node_pointer); node_pointer merge_nodes_recursive(node_pointer, node_pointer, node_pointer); void sanity_check(void); // public data members static const bool constant_time_size; static const bool has_ordered_iterators; static const bool is_mergable; static const bool is_stable; static const bool has_reserve; static const bool is_mutable; };
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>.
skew_heap
public
construct/copy/destructexplicit skew_heap(value_compare const & cmp = value_compare());
Effects: constructs an empty priority queue.
Complexity: Constant.
skew_heap(skew_heap const & rhs);
Effects: copy-constructs priority queue from rhs.
Complexity: Linear.
skew_heap(skew_heap && rhs);
Effects: C++11-style move constructor.
Complexity: Constant.
Note: Only available, if BOOST_NO_CXX11_RVALUE_REFERENCES is not defined
skew_heap & operator=(skew_heap const & rhs);
Effects: Assigns priority queue from rhs.
Complexity: Linear.
skew_heap & operator=(skew_heap && rhs);
Effects: C++11-style move assignment.
Complexity: Constant.
Note: Only available, if BOOST_NO_CXX11_RVALUE_REFERENCES is not defined
~skew_heap(void);
skew_heap public member functionsmpl::if_c< is_mutable, handle_type, void >::type push(value_type const & v);
Effects: Adds a new element to the priority queue.
Complexity: Logarithmic (amortized).
template<typename... Args> mpl::if_c< is_mutable, handle_type, void >::type emplace(Args &&... args);
Effects: Adds a new element to the priority queue. The element is directly constructed in-place.
Complexity: Logarithmic (amortized).
bool empty(void) const;
Effects: Returns true, if the priority queue contains no elements.
Complexity: Constant.
size_type size(void) const;
Effects: Returns the number of elements contained in the priority queue.
Complexity: Constant, if configured with constant_time_size<true>, otherwise linear.
size_type max_size(void) const;
Effects: Returns the maximum number of elements the priority queue can contain.
Complexity: Constant.
void clear(void);
Effects: Removes all elements from the priority queue.
Complexity: Linear.
allocator_type get_allocator(void) const;
Effects: Returns allocator.
Complexity: Constant.
void swap(skew_heap & rhs);
Effects: Swaps two priority queues.
Complexity: Constant.
const_reference top(void) const;
Effects: Returns a const_reference to the maximum element.
Complexity: Constant.
void pop(void);
Effects: Removes the top element from the priority queue.
Complexity: Logarithmic (amortized).
iterator begin(void) const;
Effects: Returns an iterator to the first element contained in the priority queue.
Complexity: Constant.
iterator end(void) const;
Effects: Returns an iterator to the end of the priority queue.
Complexity: Constant.
ordered_iterator ordered_begin(void) const;
Effects: Returns an ordered iterator to the first element contained in the priority queue.
Note: Ordered iterators traverse the priority queue in heap order.
ordered_iterator ordered_end(void) const;
Effects: Returns an ordered iterator to the first element contained in the priority queue.
Note: Ordered iterators traverse the priority queue in heap order.
void merge(skew_heap & rhs);
Effects: Merge all elements from rhs into this
Complexity: Logarithmic (amortized).
value_compare const & value_comp(void) const;
Effect: Returns the value_compare object used by the priority queue
template<typename HeapType> bool operator<(HeapType const & rhs) const;
Returns: Element-wise comparison of heap data structures
Requirement: the value_compare object of both heaps must match.
template<typename HeapType> bool operator>(HeapType const & rhs) const;
Returns: Element-wise comparison of heap data structures
Requirement: the value_compare object of both heaps must match.
template<typename HeapType> bool operator>=(HeapType const & rhs) const;
Returns: Element-wise comparison of heap data structures
Requirement: the value_compare object of both heaps must match.
template<typename HeapType> bool operator<=(HeapType const & rhs) const;
Returns: Element-wise comparison of heap data structures
Requirement: the value_compare object of both heaps must match.
template<typename HeapType> bool operator==(HeapType const & rhs) const;Equivalent comparison Returns: True, if both heap data structures are equivalent.
Requirement: the value_compare object of both heaps must match.
template<typename HeapType> bool operator!=(HeapType const & rhs) const;Equivalent comparison Returns: True, if both heap data structures are not equivalent.
Requirement: the value_compare object of both heaps must match.
void erase(handle_type object);
Effects: Removes the element handled by handle from the priority_queue.
Complexity: Logarithmic (amortized).
void update(handle_type handle, const_reference v);
Effects: Assigns v to the element handled by handle & updates the priority queue.
Complexity: Logarithmic (amortized).
void update(handle_type handle);
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!
void increase(handle_type handle, const_reference v);
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
void increase(handle_type handle);
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!
void decrease(handle_type handle, const_reference v);
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
void decrease(handle_type handle);
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!
skew_heap private member functionsnode_pointer push_internal(const_reference v);
template<class... Args> node_pointer emplace_internal(Args &&... args);
void unlink_node(node_pointer node);
void clone_tree(skew_heap const & rhs);
void merge_node(node_pointer other);
node_pointer merge_nodes(node_pointer node1, node_pointer node2, node_pointer new_parent);
node_pointer merge_children(node_pointer node);
node_pointer merge_nodes_recursive(node_pointer node1, node_pointer node2, node_pointer new_parent);
void sanity_check(void);