FIFE
be64c707dea6b3250bd4355bf5c825d25920087d
|
A pq which stores index-value pairs for elements. More...
#include <priorityqueue.h>
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 |
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.
|
private |
Definition at line 122 of file priorityqueue.h.
|
private |
Definition at line 124 of file priorityqueue.h.
|
private |
Definition at line 123 of file priorityqueue.h.
typedef std::pair<index_type, priority_type> FIFE::PriorityQueue< index_type, priority_type >::value_type |
Definition at line 46 of file priorityqueue.h.
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.
|
inline |
Constructor.
Definition at line 51 of file priorityqueue.h.
|
inline |
Constructor.
ordering | The ordering the priority queue should use. |
Definition at line 58 of file priorityqueue.h.
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.
index | The index of the element to change the priority of. |
newPriority | The new priority of the element. |
Definition at line 197 of file priorityqueue.h.
Referenced by FIFE::PriorityQueue< int32_t, double >::PriorityQueue(), FIFE::MultiLayerSearch::searchBetweenTargetsMap(), FIFE::SingleLayerSearch::updateSearch(), and FIFE::MultiLayerSearch::updateSearch().
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(), FIFE::PriorityQueue< int32_t, double >::PriorityQueue(), and FIFE::MultiLayerSearch::updateSearch().
|
private |
The comparison function, used to compare two elements.
a | The l-operand of the comparison operation. |
b | The r-operand of the comparison operation. |
Definition at line 304 of file priorityqueue.h.
Referenced by FIFE::PriorityQueue< int32_t, double >::changeElementPriority(), FIFE::PriorityQueue< int32_t, double >::getElementIterator(), FIFE::PriorityQueue< int32_t, double >::orderDown(), and FIFE::PriorityQueue< int32_t, double >::orderUp().
|
inline |
Determines whether the queue is currently empty.
Definition at line 111 of file priorityqueue.h.
Referenced by FIFE::PriorityQueue< int32_t, double >::getPriorityElement(), FIFE::PriorityQueue< int32_t, double >::popElement(), FIFE::PriorityQueue< int32_t, double >::pushElement(), FIFE::MultiLayerSearch::searchBetweenTargetsMap(), FIFE::RoutePather::update(), FIFE::SingleLayerSearch::updateSearch(), and FIFE::MultiLayerSearch::updateSearch().
|
inlineprivate |
Retrieves the iterator to the element with the given index.
index | A const reference to the index to find. |
Definition at line 154 of file priorityqueue.h.
Referenced by FIFE::PriorityQueue< int32_t, double >::changeElementPriority().
|
inline |
Retrieves the element with the highest priority.
This function will generate an assertion error if the pq is empty.
Definition at line 99 of file priorityqueue.h.
Referenced by FIFE::MultiLayerSearch::searchBetweenTargetsMap(), FIFE::RoutePather::update(), FIFE::SingleLayerSearch::updateSearch(), and FIFE::MultiLayerSearch::updateSearch().
|
private |
Orders a PQ element down the list.
i | An iterator representing the element in the PQ to order down. |
Definition at line 272 of file priorityqueue.h.
Referenced by FIFE::PriorityQueue< int32_t, double >::changeElementPriority().
|
private |
Orders a PQ element up the list.
i | An iterator representing the element in the list to be sorted up. |
Definition at line 227 of file priorityqueue.h.
Referenced by FIFE::PriorityQueue< int32_t, double >::changeElementPriority(), and FIFE::PriorityQueue< int32_t, double >::pushElement().
|
private |
Orders a PQ element up the list.
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.
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::PriorityQueue< int32_t, double >::PriorityQueue(), FIFE::MultiLayerSearch::searchBetweenTargetsMap(), FIFE::RoutePather::update(), FIFE::SingleLayerSearch::updateSearch(), and FIFE::MultiLayerSearch::updateSearch().
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.
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::PriorityQueue< int32_t, double >::PriorityQueue(), FIFE::MultiLayerSearch::searchBetweenTargetsMap(), FIFE::SingleLayerSearch::SingleLayerSearch(), FIFE::RoutePather::solveRoute(), FIFE::SingleLayerSearch::updateSearch(), and FIFE::MultiLayerSearch::updateSearch().
|
inline |
Returns the current size of the queue.
Definition at line 118 of file priorityqueue.h.
|
private |
Definition at line 127 of file priorityqueue.h.
Referenced by FIFE::PriorityQueue< int32_t, double >::changeElementPriority(), FIFE::PriorityQueue< int32_t, double >::clear(), FIFE::PriorityQueue< int32_t, double >::empty(), FIFE::PriorityQueue< int32_t, double >::getPriorityElement(), FIFE::PriorityQueue< int32_t, double >::orderDown(), FIFE::PriorityQueue< int32_t, double >::orderUp(), FIFE::PriorityQueue< int32_t, double >::popElement(), FIFE::PriorityQueue< int32_t, double >::pushElement(), and FIFE::PriorityQueue< int32_t, double >::size().
|
private |
Definition at line 130 of file priorityqueue.h.
Referenced by FIFE::PriorityQueue< int32_t, double >::compare().