PriorityQueueBinaryHeapDynamicKeys< T, GetHandle, Key, GetKey, CompareKeys, Sequence > Class Template Reference

A priority queue with dynamic keys implemented with a binary heap. More...

#include <PriorityQueueBinaryHeapDynamicKeys.h>

Inheritance diagram for PriorityQueueBinaryHeapDynamicKeys< T, GetHandle, Key, GetKey, CompareKeys, Sequence >:

List of all members.

Public Types
typedef base_type::element_type	element_type
	The element type.
typedef base_type::const_reference	const_reference
	A const reference to the element type.
typedef base_type::key_type	key_type
	The key type.
typedef base_type::size_type	size_type
	The size type.
typedef base_type::value_type	value_type
	The type stored in the binary heap.
typedef base_type::iterator	iterator
	An iterator on the value type.
typedef base_type::difference_type	difference_type
	Difference between iterators.
Public Member Functions
	PriorityQueueBinaryHeapDynamicKeys (const get_handle_functor &get_handle=get_handle_functor(), const sequence_type &container=sequence_type())
	Make from a container of values.
	PriorityQueueBinaryHeapDynamicKeys (size_type n, const get_handle_functor &get_handle=get_handle_functor())
	Construct and reserve memory for n elements.
template<class InputIterator >
	PriorityQueueBinaryHeapDynamicKeys (InputIterator first, InputIterator last, const get_handle_functor &get_handle=get_handle_functor(), const sequence_type &container=sequence_type())
	Add the values in the range to the container then make the heap.
virtual	~PriorityQueueBinaryHeapDynamicKeys ()
	Destructor.
size_type	size () const
	Return the number of elements in the priority queue.
bool	empty () const
	Return true if the priority queue is empty.
const_reference	top () const
	Return the element at the top of the priority queue.
void	push (element_type x)
	Add an element to the priority queue.
void	pop ()
	Remove the element at the top of the priority queue.
void	decrease (element_type x)
	The key of the element has decreased, adjust its position in the heap.
Protected Types
typedef PriorityQueue< T, Key, GetKey, CompareKeys, Sequence >	base_type
	The base priority queue.
typedef GetHandle	get_handle_functor
	Functor that gets a handle to an element.
typedef base_type::get_key_functor	get_key_functor
	Functor for getting the key of an element.
typedef base_type::compare_keys_functor	compare_keys_functor
	Functor for comparing keys.
typedef base_type::sequence_type	sequence_type
	The container type.
typedef ads::binary_compose_binary_unary < compare_keys_functor, get_key_functor, get_key_functor >	compare_values_functor
	Functor for comparing elements.
Protected Member Functions
void	make ()
	Make a heap from the elements in the container.
void	decrease (iterator iter)
	The key of the element has decreased, adjust its position in the heap.
void	swap (iterator a, iterator b)
	Swap two elements in the container.
void	copy (iterator a, iterator b)
	Copy b into a.
void	set_handles ()
	Set the heap pointers of the elements.
difference_type	small_child (difference_type parent)
	Return the index of the smaller child.
Protected Attributes
get_handle_functor	_get_handle
	The functor for getting an elements handle.
compare_values_functor	_compare
	The value type comparison functor.
sequence_type	_container
	The container for storing the values.

---

Detailed Description

template<typename T, class GetHandle, typename Key = typename std::iterator_traits<T>::value_type, class GetKey = Dereference<T>, class CompareKeys = std::less<Key>, class Sequence = std::vector<T>>
class PriorityQueueBinaryHeapDynamicKeys< T, GetHandle, Key, GetKey, CompareKeys, Sequence >

A priority queue with dynamic keys implemented with a binary heap.

This priority queue is similar to ads::PriorityQueueBinaryHeap, but it supports dynamic keys and the implementation does not use the STL heap functions. It has the additional template parameter GetHandle. This class is useful when the keys changes while their associated elements are in the heap.

The element type and the functor to get heap handles are required parameters. The remaining parameters have default values. By default, it is assumed that the element type is a handle and that the key is obtained by dereferencing this handle.

Parameters:

	T	is the element type.
	GetHandle	is a functor that takes an element and returns a reference to the handle to that element. This handle must be stored in some data structure.
	Key	is the key type.
	GetKey	is the functor that gets the key from the element.
	CompareKeys	is a functor that takes two keys as arguments and returns a boolean. It is used to order the objects in the priority queue. For less than comparisons, the top of the priority queue holds the element with minimum key. This is the default behavior.
	Sequence	is the container for the binary heap. It is std::vector<T> by default.

---

Constructor & Destructor Documentation

template<typename T, class GetHandle, typename Key = typename std::iterator_traits<T>::value_type, class GetKey = Dereference<T>, class CompareKeys = std::less<Key>, class Sequence = std::vector<T>>

PriorityQueueBinaryHeapDynamicKeys< T, GetHandle, Key, GetKey, CompareKeys, Sequence >::PriorityQueueBinaryHeapDynamicKeys	(	const get_handle_functor &	get_handle = get_handle_functor(),
		const sequence_type &	container = sequence_type()
	)			[inline, explicit]

Make from a container of values.

The default constructor makes an empty queue.

---

The documentation for this class was generated from the following file:

• PriorityQueueBinaryHeapDynamicKeys.h