om::util::PriorityQueue< T, SizeType, AllocatorType > Class Template Reference

A class that implements a max-heap-based priority queue. More...

#include <omPriorityQueue.h>

Public Member Functions
	PriorityQueue ()
	Create a new empty priority queue with the default capacity. More...
	PriorityQueue (Size newCapacity)
	Create a new empty priority queue with the specified initial capacity. More...
	PriorityQueue (const PriorityQueue< T > &other)
	Create a copy of an existing priority queue, performing a deep copy. More...
	~PriorityQueue ()
	Destroy a priority queue. More...
PriorityQueue< T > &	operator= (const PriorityQueue< T > &other)
	Assign this priority queue with the contents of another, performing a deep copy. More...
Bool	operator== (const PriorityQueue< T > &other) const
	Return whether or not whether every entry in this queue is equal to another queue's entries. More...
Bool	operator!= (const PriorityQueue< T > &other) const
void	add (const T &newElement)
	Add a new element to this priority queue. More...
void	remove ()
	Remove the largest element from the priority queue. More...
Bool	remove (const T &element)
	Remove the element with the specified value from the priority queue. More...
void	removeAtIndex (SizeType i)
	Remove the element at the specified index from the priority queue. More...
void	update (SizeType i)
	Ensure that the heap is propery ordered after the specified element was changed. More...
Bool	getIndex (const T &value, SizeType &index) const
	Get the index of the specified value in this priority queue. More...
Bool	contains (const T &element) const
	Return whether or not the specified element is in the priority queue. More...
T &	getFirst ()
	Return a reference to the largest element in the priority queue. More...
const T &	getFirst () const
	Return a const reference to the largest element in the priority queue. More...
T &	operator[] (SizeType i)
	Return a reference to the element in this priority queue at the specified index. More...
const T &	operator[] (SizeType i) const
	Return a const reference to the element in this priority queue at the specified index. More...
void	clear ()
	Clear the contents of this priority queue. More...
void	reset ()
	Clear the contents of this priority queue and reclaim the allocated memory. More...
void	reset (SizeType newCapacity)
	Clear the contents of this priority queue and reclaim the allocated memory. More...
Bool	isEmpty () const
	Return whether or not the priority queue has any elements. More...
SizeType	getSize () const
	Get the number of elements in the priority queue. More...
SizeType	getCapacity () const
	Get the current capacity of the priority queue. More...

Static Public Member Functions
static SizeType	getParentIndex (SizeType child)
	Return the index of a child elements's parent element given the child element's index. More...
static SizeType	getChildIndex1 (SizeType parent)
	Return the index of the left child element given the parent element's index. More...
static SizeType	getChildIndex2 (SizeType parent)
	Return the index of the right child element given the parent element's index. More...

Detailed Description

template<typename T, typename SizeType = Size, typename AllocatorType = Allocator>
class om::util::PriorityQueue< T, SizeType, AllocatorType >

A class that implements a max-heap-based priority queue.

The class uses an array-based heap where larger elements are stored towards the front. When elements are added or removed from the heap, internal state is kept consistent so that the first item in the queue is the largest. Element comparisons are done using the greater-than operator (>). Therefore, any class that the user wishes to use with this implementation must provide an overloaded greater-than operator.

Constructor & Destructor Documentation

template<typename T, typename SizeType = Size, typename AllocatorType = Allocator>

om::util::PriorityQueue< T, SizeType, AllocatorType >::PriorityQueue ( )

inline

Create a new empty priority queue with the default capacity.

template<typename T, typename SizeType = Size, typename AllocatorType = Allocator>

om::util::PriorityQueue< T, SizeType, AllocatorType >::PriorityQueue ( Size  newCapacity )

inline

Create a new empty priority queue with the specified initial capacity.

template<typename T, typename SizeType = Size, typename AllocatorType = Allocator>

om::util::PriorityQueue< T, SizeType, AllocatorType >::PriorityQueue ( const PriorityQueue< T > &  other )

inline

Create a copy of an existing priority queue, performing a deep copy.

template<typename T, typename SizeType = Size, typename AllocatorType = Allocator>

om::util::PriorityQueue< T, SizeType, AllocatorType >::~PriorityQueue ( )

inline

Destroy a priority queue.

This destructor reclaims all memory previously used by this priority queue.

Member Function Documentation

template<typename T, typename SizeType = Size, typename AllocatorType = Allocator>

PriorityQueue<T>& om::util::PriorityQueue< T, SizeType, AllocatorType >::operator= ( const PriorityQueue< T > &  other )

inline

Assign this priority queue with the contents of another, performing a deep copy.

template<typename T, typename SizeType = Size, typename AllocatorType = Allocator>

Bool om::util::PriorityQueue< T, SizeType, AllocatorType >::operator== ( const PriorityQueue< T > &  other ) const

inline

Return whether or not whether every entry in this queue is equal to another queue's entries.

template<typename T, typename SizeType = Size, typename AllocatorType = Allocator>

Bool om::util::PriorityQueue< T, SizeType, AllocatorType >::operator!= ( const PriorityQueue< T > &  other ) const

inline

template<typename T, typename SizeType = Size, typename AllocatorType = Allocator>

void om::util::PriorityQueue< T, SizeType, AllocatorType >::add ( const T &  newElement )

inline

Add a new element to this priority queue.

template<typename T, typename SizeType = Size, typename AllocatorType = Allocator>

void om::util::PriorityQueue< T, SizeType, AllocatorType >::remove ( )

inline

Remove the largest element from the priority queue.

template<typename T, typename SizeType = Size, typename AllocatorType = Allocator>

Bool om::util::PriorityQueue< T, SizeType, AllocatorType >::remove ( const T &  element )

inline

Remove the element with the specified value from the priority queue.

The method returns whether or not the value was able to be removed.

template<typename T, typename SizeType = Size, typename AllocatorType = Allocator>

void om::util::PriorityQueue< T, SizeType, AllocatorType >::removeAtIndex ( SizeType  i )

inline

Remove the element at the specified index from the priority queue.

Indices start at 0 for the largest element in the queue and must be less than the number of elements in the queue.

template<typename T, typename SizeType = Size, typename AllocatorType = Allocator>

void om::util::PriorityQueue< T, SizeType, AllocatorType >::update ( SizeType  i )

inline

Ensure that the heap is propery ordered after the specified element was changed.

template<typename T, typename SizeType = Size, typename AllocatorType = Allocator>

Bool om::util::PriorityQueue< T, SizeType, AllocatorType >::getIndex ( const T &  value, SizeType &  index  ) const

inline

Get the index of the specified value in this priority queue.

The method returns whether or not the given value was contained in the queue.

template<typename T, typename SizeType = Size, typename AllocatorType = Allocator>

Bool om::util::PriorityQueue< T, SizeType, AllocatorType >::contains ( const T &  element ) const

inline

Return whether or not the specified element is in the priority queue.

template<typename T, typename SizeType = Size, typename AllocatorType = Allocator>

T& om::util::PriorityQueue< T, SizeType, AllocatorType >::getFirst ( )

inline

Return a reference to the largest element in the priority queue.

template<typename T, typename SizeType = Size, typename AllocatorType = Allocator>

const T& om::util::PriorityQueue< T, SizeType, AllocatorType >::getFirst ( ) const

inline

Return a const reference to the largest element in the priority queue.

template<typename T, typename SizeType = Size, typename AllocatorType = Allocator>

T& om::util::PriorityQueue< T, SizeType, AllocatorType >::operator[] ( SizeType  i )

inline

Return a reference to the element in this priority queue at the specified index.

template<typename T, typename SizeType = Size, typename AllocatorType = Allocator>

const T& om::util::PriorityQueue< T, SizeType, AllocatorType >::operator[] ( SizeType  i ) const

inline

Return a const reference to the element in this priority queue at the specified index.

template<typename T, typename SizeType = Size, typename AllocatorType = Allocator>

void om::util::PriorityQueue< T, SizeType, AllocatorType >::clear ( )

inline

Clear the contents of this priority queue.

This method calls the destructors of all elements in the priority queue and sets the number of elements to zero while maintaining the queue's capacity.

template<typename T, typename SizeType = Size, typename AllocatorType = Allocator>

void om::util::PriorityQueue< T, SizeType, AllocatorType >::reset ( )

inline

Clear the contents of this priority queue and reclaim the allocated memory.

This method performs the same function as the clear() method, but also deallocates the previously allocated internal array. Calling this method is equivalent to assigning a new queue instance to this one.

template<typename T, typename SizeType = Size, typename AllocatorType = Allocator>

void om::util::PriorityQueue< T, SizeType, AllocatorType >::reset ( SizeType  newCapacity )

inline

Clear the contents of this priority queue and reclaim the allocated memory.

This method performs the same function as the clear() method, but also deallocates the previously allocated internal array and reallocates it to a small initial starting size. Calling this method is equivalent to assigning a new priority queue instance to this one. This version of the reset() method allows the caller to specify the new starting capacity of the queue.

template<typename T, typename SizeType = Size, typename AllocatorType = Allocator>

Bool om::util::PriorityQueue< T, SizeType, AllocatorType >::isEmpty ( ) const

inline

Return whether or not the priority queue has any elements.

This method returns TRUE if the size of the priority queue is greater than zero, and FALSE otherwise.

Returns

whether or not the priority queue has any elements.

template<typename T, typename SizeType = Size, typename AllocatorType = Allocator>

SizeType om::util::PriorityQueue< T, SizeType, AllocatorType >::getSize ( ) const

inline

Get the number of elements in the priority queue.

Returns

the number of elements in the priority queue.

template<typename T, typename SizeType = Size, typename AllocatorType = Allocator>

SizeType om::util::PriorityQueue< T, SizeType, AllocatorType >::getCapacity ( ) const

inline

Get the current capacity of the priority queue.

The capacity is the maximum number of elements that the priority queue can hold before it will have to resize its internal array.

Returns

the current capacity of the priority queue.

template<typename T, typename SizeType = Size, typename AllocatorType = Allocator>

static SizeType om::util::PriorityQueue< T, SizeType, AllocatorType >::getParentIndex ( SizeType  child )

inlinestatic

Return the index of a child elements's parent element given the child element's index.

If the child index is zero, the method returns 0 because this child element is at the top of the heap and has no parent by definition.

template<typename T, typename SizeType = Size, typename AllocatorType = Allocator>

static SizeType om::util::PriorityQueue< T, SizeType, AllocatorType >::getChildIndex1 ( SizeType  parent )

inlinestatic

Return the index of the left child element given the parent element's index.

template<typename T, typename SizeType = Size, typename AllocatorType = Allocator>

static SizeType om::util::PriorityQueue< T, SizeType, AllocatorType >::getChildIndex2 ( SizeType  parent )

inlinestatic

Return the index of the right child element given the parent element's index.

---

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

• omPriorityQueue.h