A pq which stores index-value pairs for elements. More...

#include <priorityqueue.h>

Inheritance diagram for FIFE::PriorityQueue< index_type, priority_type >:

Collaboration diagram for FIFE::PriorityQueue< index_type, priority_type >:

Public Types
enum	Ordering { Ascending, Descending }
	Used for element ordering. More...

typedef std::pair< index_type, priority_type >	value_type

Public Member Functions
	PriorityQueue (void)
	Constructor. More...

	PriorityQueue (const Ordering ordering)
	Constructor. More...

void	pushElement (const value_type &element)
	Pushes a new element onto the queue. More...

void	popElement (void)
	Pops the element with the highest priority from the queue. More...

bool	changeElementPriority (const index_type &index, const priority_type &newPriority)
	Changes the priority of an element. More...

void	clear (void)
	Removes all elements from the priority queue. More...

const value_type	getPriorityElement (void) const
	Retrieves the element with the highest priority. More...

bool	empty (void) const
	Determines whether the queue is currently empty. More...

size_t	size (void) const
	Returns the current size of the queue. More...

Private Types
typedef std::list< value_type >	ElementList

typedef ElementList::iterator	ElementListIt

typedef ElementList::const_iterator	ElementListConstIt

Private Member Functions
void	orderUp (ElementListIt i)
	Orders a PQ element up the list. More...

void	orderUp (const value_type &entry)
	Orders a PQ element up the list. More...

void	orderDown (ElementListIt i)
	Orders a PQ element down the list. More...

ElementListIt	getElementIterator (const index_type &index)
	Retrieves the iterator to the element with the given index. More...

int32_t	compare (const value_type &a, const value_type &b)
	The comparison function, used to compare two elements. More...

Private Attributes
ElementList	m_elements

Ordering	m_ordering

Detailed Description

template<typename index_type, typename priority_type>
class FIFE::PriorityQueue< index_type, priority_type >

A pq which stores index-value pairs for elements.

This acts as a normal PQ but stores some extra information about the elements that it's storing, namely a special unique index.

Definition at line 36 of file priorityqueue.h.

Member Typedef Documentation

template<typename index_type, typename priority_type>

typedef std::list<value_type> FIFE::PriorityQueue< index_type, priority_type >::ElementList

private

Definition at line 122 of file priorityqueue.h.

template<typename index_type, typename priority_type>

typedef ElementList::const_iterator FIFE::PriorityQueue< index_type, priority_type >::ElementListConstIt

private

Definition at line 124 of file priorityqueue.h.

template<typename index_type, typename priority_type>

typedef ElementList::iterator FIFE::PriorityQueue< index_type, priority_type >::ElementListIt

private

Definition at line 123 of file priorityqueue.h.

template<typename index_type, typename priority_type>

typedef std::pair<index_type, priority_type> FIFE::PriorityQueue< index_type, priority_type >::value_type

Definition at line 46 of file priorityqueue.h.

Member Enumeration Documentation

template<typename index_type, typename priority_type>

enum FIFE::PriorityQueue::Ordering

Used for element ordering.

Enumerator
Ascending	lowest priority first.
Descending	highest priority first.

Definition at line 41 of file priorityqueue.h.

Constructor & Destructor Documentation

template<typename index_type, typename priority_type>

FIFE::PriorityQueue< index_type, priority_type >::PriorityQueue ( void )

inline

Constructor.

Definition at line 51 of file priorityqueue.h.

template<typename index_type, typename priority_type>

FIFE::PriorityQueue< index_type, priority_type >::PriorityQueue ( const Ordering ordering )

inline

Constructor.

Parameters

ordering The ordering the priority queue should use.

Definition at line 58 of file priorityqueue.h.

Member Function Documentation

template<typename index_type, typename priority_type>

bool FIFE::PriorityQueue< index_type, priority_type >::changeElementPriority	(	const index_type &	index,
		const priority_type &	newPriority
	)

Changes the priority of an element.

Locates the element with the given index and changes it's priority to the given priority, it then re-orders the priority queue to take account of this new information.

Parameters

index	The index of the element to change the priority of.
newPriority	The new priority of the element.

Returns: True if the element could be found, false otherwise.

Definition at line 197 of file priorityqueue.h.

Referenced by FIFE::MultiLayerSearch::searchBetweenTargetsMap(), FIFE::SingleLayerSearch::updateSearch(), and FIFE::MultiLayerSearch::updateSearch().

Here is the caller graph for this function:

template<typename index_type , typename priority_type >

void FIFE::PriorityQueue< index_type, priority_type >::clear ( void )

Removes all elements from the priority queue.

Definition at line 220 of file priorityqueue.h.

Referenced by FIFE::MultiLayerSearch::createSearchFrontier(), and FIFE::MultiLayerSearch::updateSearch().

Here is the caller graph for this function:

template<typename index_type , typename priority_type >

int32_t FIFE::PriorityQueue< index_type, priority_type >::compare	(	const value_type &	a,
		const value_type &	b
	)

private

The comparison function, used to compare two elements.

Parameters

a	The l-operand of the comparison operation.
b	The r-operand of the comparison operation.

Returns: An integer representing the result of the comparison operation. 1 being a is greather than b, -1 being a is less than b and 0 meaning that they're equal.

Definition at line 304 of file priorityqueue.h.

template<typename index_type, typename priority_type>

bool FIFE::PriorityQueue< index_type, priority_type >::empty ( void ) const

inline

Determines whether the queue is currently empty.

Returns: true if it is empty, false otherwise.

Definition at line 111 of file priorityqueue.h.

Referenced by FIFE::PriorityQueue< int32_t, double >::getPriorityElement(), FIFE::MultiLayerSearch::searchBetweenTargetsMap(), FIFE::RoutePather::update(), FIFE::SingleLayerSearch::updateSearch(), and FIFE::MultiLayerSearch::updateSearch().

Here is the caller graph for this function:

template<typename index_type, typename priority_type>

ElementListIt FIFE::PriorityQueue< index_type, priority_type >::getElementIterator ( const index_type & index )

inlineprivate

Retrieves the iterator to the element with the given index.

Parameters

index A const reference to the index to find.

Definition at line 154 of file priorityqueue.h.

template<typename index_type, typename priority_type>

const value_type FIFE::PriorityQueue< index_type, priority_type >::getPriorityElement ( void ) const

inline

Retrieves the element with the highest priority.

This function will generate an assertion error if the pq is empty.

Returns: A const reference to the highest priority element.

Definition at line 99 of file priorityqueue.h.

Referenced by FIFE::MultiLayerSearch::searchBetweenTargetsMap(), FIFE::RoutePather::update(), FIFE::SingleLayerSearch::updateSearch(), and FIFE::MultiLayerSearch::updateSearch().

Here is the caller graph for this function:

template<typename index_type , typename priority_type >

void FIFE::PriorityQueue< index_type, priority_type >::orderDown ( ElementListIt i )

private

Orders a PQ element down the list.

Parameters

i	An iterator representing the element in the PQ to order down.

Definition at line 272 of file priorityqueue.h.

template<typename index_type , typename priority_type >

void FIFE::PriorityQueue< index_type, priority_type >::orderUp ( ElementListIt i )

private

Orders a PQ element up the list.

Parameters

i	An iterator representing the element in the list to be sorted up.

Definition at line 227 of file priorityqueue.h.

template<class index_type , class priority_type >

void FIFE::PriorityQueue< index_type, priority_type >::orderUp ( const value_type & entry )

private

Orders a PQ element up the list.

Parameters

entry A const reference to a value_type which represents the element to be added to the pq.

Definition at line 252 of file priorityqueue.h.

template<typename index_type , typename priority_type >

void FIFE::PriorityQueue< index_type, priority_type >::popElement ( void )

Pops the element with the highest priority from the queue.

Removes and deletes the highest priority element.

Definition at line 188 of file priorityqueue.h.

Referenced by FIFE::MultiLayerSearch::searchBetweenTargetsMap(), FIFE::RoutePather::update(), FIFE::SingleLayerSearch::updateSearch(), and FIFE::MultiLayerSearch::updateSearch().

Here is the caller graph for this function:

template<typename index_type , typename priority_type >

void FIFE::PriorityQueue< index_type, priority_type >::pushElement ( const value_type & element )

Pushes a new element onto the queue.

The element is pushed onto the queue and then moved up the queue until it's in the correct position by priority.

Parameters

element Of type value_type which contains both the index and the priority of the element.

Definition at line 178 of file priorityqueue.h.

Referenced by FIFE::MultiLayerSearch::createSearchFrontier(), FIFE::MultiLayerSearch::searchBetweenTargetsMap(), FIFE::SingleLayerSearch::SingleLayerSearch(), FIFE::RoutePather::solveRoute(), FIFE::SingleLayerSearch::updateSearch(), and FIFE::MultiLayerSearch::updateSearch().

Here is the caller graph for this function:

template<typename index_type, typename priority_type>

size_t FIFE::PriorityQueue< index_type, priority_type >::size ( void ) const

inline

Returns the current size of the queue.

Definition at line 118 of file priorityqueue.h.

Member Data Documentation

template<typename index_type, typename priority_type>

ElementList FIFE::PriorityQueue< index_type, priority_type >::m_elements

private

Definition at line 127 of file priorityqueue.h.

Referenced by FIFE::PriorityQueue< int32_t, double >::empty(), FIFE::PriorityQueue< int32_t, double >::getElementIterator(), FIFE::PriorityQueue< int32_t, double >::getPriorityElement(), and FIFE::PriorityQueue< int32_t, double >::size().

template<typename index_type, typename priority_type>

Ordering FIFE::PriorityQueue< index_type, priority_type >::m_ordering

private

Definition at line 130 of file priorityqueue.h.

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

engine/core/util/structures/priorityqueue.h

Public Types

Public Member Functions

Private Types

Private Member Functions

Private Attributes

Detailed Description

template<typename index_type, typename priority_type> class FIFE::PriorityQueue< index_type, priority_type >

Member Typedef Documentation

Member Enumeration Documentation

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation

template<typename index_type, typename priority_type>
class FIFE::PriorityQueue< index_type, priority_type >