graphlab::mutable_queue< T, Priority, Compare > Class Template Reference [GraphLab Utility Classes and Functions]

#include <mutable_queue.hpp>

List of all members.

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)
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 std::map< T, size_t, Compare >	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, typename Compare = std::less<T>>
class graphlab::mutable_queue< T, Priority, Compare >

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

Todo:

Add a comparator

Definition at line 80 of file mutable_queue.hpp.

---

Member Function Documentation

template<typename T, typename Priority, typename Compare = std::less<T>>

bool graphlab::mutable_queue< T, Priority, Compare >::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 268 of file mutable_queue.hpp.

template<typename T, typename Priority, typename Compare = std::less<T>>

bool graphlab::mutable_queue< T, Priority, Compare >::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 239 of file mutable_queue.hpp.

template<typename T, typename Priority, typename Compare = std::less<T>>

std::pair<T, Priority> graphlab::mutable_queue< T, Priority, Compare >::pop

(

)

[inline]

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

Definition at line 191 of file mutable_queue.hpp.

template<typename T, typename Priority, typename Compare = std::less<T>>

void graphlab::mutable_queue< T, Priority, Compare >::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 218 of file mutable_queue.hpp.

---

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

• src/graphlab/util/mutable_queue.hpp