FIFE  6e1afdbeda11afe9ac53e6023a4be96ef88f1dc6
FIFE::PriorityQueue< index_type, priority_type > Class Template Reference

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

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_typeElementList
 
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
orderingThe 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
indexThe index of the element to change the priority of.
newPriorityThe new priority of the element.
Returns
True if the element could be found, false otherwise.

Definition at line 197 of file priorityqueue.h.

References FIFE::PriorityQueue< index_type, priority_type >::compare(), FIFE::PriorityQueue< index_type, priority_type >::getElementIterator(), FIFE::PriorityQueue< index_type, priority_type >::m_elements, FIFE::PriorityQueue< index_type, priority_type >::orderDown(), and FIFE::PriorityQueue< index_type, priority_type >::orderUp().

Referenced by FIFE::PriorityQueue< int32_t, double >::PriorityQueue(), 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.

References FIFE::PriorityQueue< index_type, priority_type >::m_elements.

Referenced by FIFE::MultiLayerSearch::createSearchFrontier(), FIFE::PriorityQueue< int32_t, double >::PriorityQueue(), 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
aThe l-operand of the comparison operation.
bThe 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.

References FIFE::PriorityQueue< index_type, priority_type >::Descending, and FIFE::PriorityQueue< index_type, priority_type >::m_ordering.

Referenced by FIFE::PriorityQueue< index_type, priority_type >::changeElementPriority(), FIFE::PriorityQueue< int32_t, double >::getElementIterator(), FIFE::PriorityQueue< index_type, priority_type >::orderDown(), and FIFE::PriorityQueue< index_type, priority_type >::orderUp().

+ Here is the caller graph for this function:

template<typename index_type, typename priority_type>
bool FIFE::PriorityQueue< index_type, priority_type >::empty ( void  ) const
inline
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
indexA const reference to the index to find.

Definition at line 154 of file priorityqueue.h.

Referenced by FIFE::PriorityQueue< index_type, priority_type >::changeElementPriority().

+ Here is the caller graph for this function:

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
iAn iterator representing the element in the PQ to order down.

Definition at line 272 of file priorityqueue.h.

References FIFE::PriorityQueue< index_type, priority_type >::compare(), and FIFE::PriorityQueue< index_type, priority_type >::m_elements.

Referenced by FIFE::PriorityQueue< index_type, priority_type >::changeElementPriority().

+ Here is the caller graph for this function:

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
iAn iterator representing the element in the list to be sorted up.

Definition at line 227 of file priorityqueue.h.

References FIFE::PriorityQueue< index_type, priority_type >::compare(), and FIFE::PriorityQueue< index_type, priority_type >::m_elements.

Referenced by FIFE::PriorityQueue< index_type, priority_type >::changeElementPriority(), and FIFE::PriorityQueue< index_type, priority_type >::pushElement().

+ Here is the caller graph for this function:

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
entryA const reference to a value_type which represents the element to be added to the pq.

Definition at line 252 of file priorityqueue.h.

References FIFE::PriorityQueue< index_type, priority_type >::compare(), and FIFE::PriorityQueue< index_type, priority_type >::m_elements.

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.

References FIFE::PriorityQueue< index_type, priority_type >::empty(), and FIFE::PriorityQueue< index_type, priority_type >::m_elements.

Referenced by FIFE::PriorityQueue< int32_t, double >::PriorityQueue(), 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
elementOf type value_type which contains both the index and the priority of the element.

Definition at line 178 of file priorityqueue.h.

References FIFE::PriorityQueue< index_type, priority_type >::empty(), FIFE::PriorityQueue< index_type, priority_type >::m_elements, and FIFE::PriorityQueue< index_type, priority_type >::orderUp().

Referenced by FIFE::MultiLayerSearch::createSearchFrontier(), FIFE::PriorityQueue< int32_t, double >::PriorityQueue(), 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>
Ordering FIFE::PriorityQueue< index_type, priority_type >::m_ordering
private

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