turi::mutable_queue< T, Priority > Class Template Reference

#include <core/util/mutable_queue.hpp>

Public Types
typedef std::pair< T, Priority >	heap_element
	An element of the heap.

Public Member Functions
	mutable_queue ()
	Default constructor.
size_t	size () const
	Returns the number of elements in the heap.
bool	empty () const
	Returns true iff the queue is empty.
bool	contains (const T &item) const
	Returns true if the queue contains the given value.
void	push (T item, Priority priority)
	Enqueues a new item in the queue.
const std::pair< T, Priority > &	top () const
	Accesses the item with maximum priority in the queue.
std::pair< T, Priority >	pop ()
Priority	get (T item) const
	Returns the weight associated with a key.
Priority	operator[] (T item) const
	Returns the priority associated with a key.
void	update (T item, Priority priority)
void	push_or_update (T item, Priority priority)
bool	insert_max (T item, Priority priority)
bool	insert_cumulative (T item, Priority priority)
const std::vector< heap_element > &	values () const
	Returns the values (key-priority pairs) in the priority queue.
void	clear ()
	Clears all the values (equivalent to stl clear)
bool	remove (T item)
	Remove an item from the queue.

Protected Types
typedef boost::unordered_map< T, size_t >	index_map_type
	The storage type of the index map.

Protected Member Functions
size_t	left (size_t i) const
	Returns the index of the left child of the supplied index.
size_t	right (size_t i) const
	Returns the index of the right child of the supplied index.
size_t	parent (size_t i) const
	Returns the index of the parent of the supplied index.
Priority	priority_at (size_t i)
	Extracts the priority at a heap location.
bool	less (size_t i, size_t j)
	Compares the priorities at two heap locations.
void	swap (size_t i, size_t j)
	Swaps the heap locations of two elements.
void	heapify (size_t i)
	The traditional heapify function.

Protected Attributes
std::vector< heap_element >	heap
	The heap used to store the elements. The first element is unused.
index_map_type	index_map
	The map used to map from items to indexes in the heap.

Detailed Description

template<typename T, typename Priority>
class turi::mutable_queue< T, Priority >

A heap implementation of a priority queue that supports external priorities and priority updates. Both template arguments must be Assignable, EqualityComparable, and LessThanComparable.

Parameters

T	the type of items stored in the priority queue.
Priority	the type used to prioritize items.

See also

Boost's mutable_queue in boost/pending/mutable_queue.hpp

Definition at line 65 of file mutable_queue.hpp.

Member Function Documentation

insert_cumulative()

template<typename T, typename Priority>

bool turi::mutable_queue< T, Priority >::insert_cumulative ( T  item, Priority  priority  )

inline

If item is already in the queue, sets its priority to the sum of the old priority and the new one. If the item is not in the queue, adds it to the queue.

returns true if the item was already present

Definition at line 284 of file mutable_queue.hpp.

insert_max()

template<typename T, typename Priority>

bool turi::mutable_queue< T, Priority >::insert_max ( T  item, Priority  priority  )

inline

If item is already in the queue, sets its priority to the maximum of the old priority and the new one. If the item is not in the queue, adds it to the queue.

returns true if the items was not already

Definition at line 255 of file mutable_queue.hpp.

pop()

template<typename T, typename Priority>

std::pair<T, Priority> turi::mutable_queue< T, Priority >::pop ( )

inline

Removes the item with maximum priority from the queue, and returns it with its priority.

Definition at line 185 of file mutable_queue.hpp.

push_or_update()

template<typename T, typename Priority>

void turi::mutable_queue< T, Priority >::push_or_update ( T  item, Priority  priority  )

inline

Updates the priority associated with a item in the queue. If the item is not already present, insert it.

Definition at line 230 of file mutable_queue.hpp.

update()

template<typename T, typename Priority>

void turi::mutable_queue< T, Priority >::update ( T  item, Priority  priority  )

inline

Updates the priority associated with a item in the queue. This function fails if the item is not already present.

Definition at line 212 of file mutable_queue.hpp.

---

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

• core/util/mutable_queue.hpp