22 #ifndef FIFE_SOLVER_INDEXEDPQ_H
23 #define FIFE_SOLVER_INDEXEDPQ_H
35 template<
typename index_type,
typename priority_type>
157 if(i->first == index) {
177 template<
typename index_type,
typename priority_type>
180 m_elements.push_front(element);
187 template<
typename index_type,
typename priority_type>
191 m_elements.pop_front();
196 template<
typename index_type,
typename priority_type>
201 if(i == m_elements.end()) {
205 int32_t compare_res = compare(
value_type(index, newPriority), (*i));
207 i->second = newPriority;
209 if(compare_res > 0 && i != m_elements.begin()) {
211 }
else if(compare_res < 0) {
219 template<
typename index_type,
typename priority_type>
226 template<
typename index_type,
typename priority_type>
229 assert(i != m_elements.end() && L
"Invalid iterator passed to function");
233 i = m_elements.erase(i);
235 while(i != m_elements.end()) {
237 if(compare(vt, (*i)) > 0) {
239 m_elements.insert(i, vt);
247 m_elements.push_back(vt);
251 template<
class index_type,
class priority_type>
254 for(
ElementListIt i = m_elements.begin(); i != m_elements.end(); ++i)
256 assert(val.first != i->first);
258 if(compare(val, (*i)) > 0)
260 assert(val.first != i->first);
262 m_elements.insert(i, val);
268 m_elements.push_back(val);
271 template<
typename index_type,
typename priority_type>
274 assert(i != m_elements.end());
278 i = m_elements.erase(i);
280 if(i == m_elements.end()) {
288 while(i != m_elements.begin()) {
289 if(compare(vt, (*i)) < 0) {
291 m_elements.insert(j, vt);
300 m_elements.push_front(vt);
303 template<
typename index_type,
typename priority_type>
306 if(m_ordering == Descending) {
308 if(a.second > b.second) {
310 }
else if(b.second > a.second) {
316 if(a.second < b.second) {
318 }
else if(b.second < a.second) {
void orderUp(ElementListIt i)
Orders a PQ element up the list.
PriorityQueue(void)
Constructor.
void pushElement(const value_type &element)
Pushes a new element onto the queue.
const value_type getPriorityElement(void) const
Retrieves the element with the highest priority.
std::list< value_type > ElementList
Ordering
Used for element ordering.
ElementListIt getElementIterator(const index_type &index)
Retrieves the iterator to the element with the given index.
std::pair< index_type, priority_type > value_type
void clear(void)
Removes all elements from the priority queue.
void popElement(void)
Pops the element with the highest priority from the queue.
ElementList::iterator ElementListIt
int32_t compare(const value_type &a, const value_type &b)
The comparison function, used to compare two elements.
bool changeElementPriority(const index_type &index, const priority_type &newPriority)
Changes the priority of an element.
void orderDown(ElementListIt i)
Orders a PQ element down the list.
bool empty(void) const
Determines whether the queue is currently empty.
size_t size(void) const
Returns the current size of the queue.
A pq which stores index-value pairs for elements.
PriorityQueue(const Ordering ordering)
Constructor.
ElementList::const_iterator ElementListConstIt