22 #ifndef FIFE_SOLVER_INDEXEDPQ_H
23 #define FIFE_SOLVER_INDEXEDPQ_H
35 template<
typename index_type,
typename priority_type>
46 typedef std::pair<index_type, priority_type> value_type;
103 return m_elements.front();
112 return m_elements.empty();
119 return m_elements.size();
122 typedef std::list<value_type> ElementList;
123 typedef typename ElementList::iterator ElementListIt;
124 typedef typename ElementList::const_iterator ElementListConstIt;
127 ElementList m_elements;
136 void orderUp(ElementListIt i);
142 void orderUp(
const value_type& entry);
148 void orderDown(ElementListIt i);
154 ElementListIt getElementIterator(
const index_type& index) {
156 for(ElementListIt i = m_elements.begin(); i != m_elements.end(); ++i) {
157 if(i->first == index) {
162 return m_elements.end();
173 int32_t compare(
const value_type& a,
const value_type& b);
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>
199 ElementListIt i = getElementIterator(index);
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");
231 value_type vt = (*i);
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());
276 value_type vt = (*i);
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 pushElement(const value_type &element)
const value_type getPriorityElement(void) const
bool changeElementPriority(const index_type &index, const priority_type &newPriority)
PriorityQueue(const Ordering ordering)