FIFE  6e1afdbeda11afe9ac53e6023a4be96ef88f1dc6
priorityqueue.h
Go to the documentation of this file.
1 /***************************************************************************
2  * Copyright (C) 2005-2017 by the FIFE team *
3  * http://www.fifengine.net *
4  * This file is part of FIFE. *
5  * *
6  * FIFE is free software; you can redistribute it and/or *
7  * modify it under the terms of the GNU Lesser General Public *
8  * License as published by the Free Software Foundation; either *
9  * version 2.1 of the License, or (at your option) any later version. *
10  * *
11  * This library is distributed in the hope that it will be useful, *
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of *
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU *
14  * Lesser General Public License for more details. *
15  * *
16  * You should have received a copy of the GNU Lesser General Public *
17  * License along with this library; if not, write to the *
18  * Free Software Foundation, Inc., *
19  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA *
20  ***************************************************************************/
21 
22 #ifndef FIFE_SOLVER_INDEXEDPQ_H
23 #define FIFE_SOLVER_INDEXEDPQ_H
24 
25 #include <cassert>
26 #include <list>
27 
28 namespace FIFE {
29 
35  template<typename index_type, typename priority_type>
36  class PriorityQueue {
37  public:
41  enum Ordering {
44  };
45 
46  typedef std::pair<index_type, priority_type> value_type;
47 
52  }
53 
58  PriorityQueue(const Ordering ordering) : m_ordering(ordering) {
59  }
60 
68  void pushElement(const value_type& element);
69 
74  void popElement(void);
75 
85  bool changeElementPriority(const index_type& index, const priority_type& newPriority);
86 
90  void clear(void);
91 
99  const value_type getPriorityElement(void) const {
100 
101  assert(!empty());
102 
103  return m_elements.front();
104 
105  }
106 
111  bool empty(void) const {
112  return m_elements.empty();
113  }
114 
118  size_t size(void) const {
119  return m_elements.size();
120  }
121  private:
122  typedef std::list<value_type> ElementList;
123  typedef typename ElementList::iterator ElementListIt;
124  typedef typename ElementList::const_iterator ElementListConstIt;
125 
126  //A list of valuetype pairs that represents the pq.
127  ElementList m_elements;
128 
129  //The order to use when sorting the pq.
131 
136  void orderUp(ElementListIt i);
142  void orderUp(const value_type& entry);
143 
148  void orderDown(ElementListIt i);
149 
154  ElementListIt getElementIterator(const index_type& index) {
155 
156  for(ElementListIt i = m_elements.begin(); i != m_elements.end(); ++i) {
157  if(i->first == index) {
158  return i;
159  }
160  }
161 
162  return m_elements.end();
163 
164  }
165 
173  int32_t compare(const value_type& a, const value_type& b);
174  };
175 }
176 
177 template<typename index_type, typename priority_type>
179  if(empty()) {
180  m_elements.push_front(element);
181  }
182  else {
183  orderUp(element);
184  }
185 }
186 
187 template<typename index_type, typename priority_type>
189 
190  if(!empty()) {
191  m_elements.pop_front();
192  }
193 
194 }
195 
196 template<typename index_type, typename priority_type>
197 bool FIFE::PriorityQueue<index_type, priority_type>::changeElementPriority(const index_type& index, const priority_type& newPriority) {
198 
200 
201  if(i == m_elements.end()) {
202  return false;
203  }
204 
205  int32_t compare_res = compare(value_type(index, newPriority), (*i));
206 
207  i->second = newPriority;
208 
209  if(compare_res > 0 && i != m_elements.begin()) {
210  orderDown(i);
211  } else if(compare_res < 0) {
212  orderUp(i);
213  }
214 
215  return true;
216 
217 }
218 
219 template<typename index_type, typename priority_type>
221 
222  m_elements.clear();
223 
224 }
225 
226 template<typename index_type, typename priority_type>
228 
229  assert(i != m_elements.end() && L"Invalid iterator passed to function");
230 
231  value_type vt = (*i);
232 
233  i = m_elements.erase(i);
234 
235  while(i != m_elements.end()) {
236 
237  if(compare(vt, (*i)) > 0) {
238 
239  m_elements.insert(i, vt);
240 
241  return;
242  }
243 
244  ++i;
245  }
246 
247  m_elements.push_back(vt);
248 
249 }
250 
251 template<class index_type, class priority_type>
253 {
254  for(ElementListIt i = m_elements.begin(); i != m_elements.end(); ++i)
255  {
256  assert(val.first != i->first);
257 
258  if(compare(val, (*i)) > 0)
259  {
260  assert(val.first != i->first);
261 
262  m_elements.insert(i, val);
263 
264  return;
265  }
266  }
267 
268  m_elements.push_back(val);
269 }
270 
271 template<typename index_type, typename priority_type>
273 
274  assert(i != m_elements.end());
275 
276  value_type vt = (*i);
277 
278  i = m_elements.erase(i);
279 
280  if(i == m_elements.end()) {
281  --i;
282  }
283 
284  ElementListIt j = i;
285 
286  ++j;
287 
288  while(i != m_elements.begin()) {
289  if(compare(vt, (*i)) < 0) {
290 
291  m_elements.insert(j, vt);
292 
293  return;
294  }
295 
296  --i;
297  --j;
298  }
299 
300  m_elements.push_front(vt);
301 }
302 
303 template<typename index_type, typename priority_type>
305 
306  if(m_ordering == Descending) {
307 
308  if(a.second > b.second) {
309  return 1;
310  } else if(b.second > a.second) {
311  return -1;
312  }
313 
314  } else {
315 
316  if(a.second < b.second) {
317  return 1;
318  } else if(b.second < a.second) {
319  return -1;
320  }
321  }
322 
323  return 0;
324 }
325 
326 #endif
void orderUp(ElementListIt i)
Orders a PQ element up the list.
PriorityQueue(void)
Constructor.
Definition: priorityqueue.h:51
ElementList m_elements
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.
Definition: priorityqueue.h:99
std::list< value_type > ElementList
Ordering
Used for element ordering.
Definition: priorityqueue.h:41
ElementListIt getElementIterator(const index_type &index)
Retrieves the iterator to the element with the given index.
lowest priority first.
Definition: priorityqueue.h:42
std::pair< index_type, priority_type > value_type
Definition: priorityqueue.h:46
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.
highest priority first.
Definition: priorityqueue.h:43
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.
Definition: priorityqueue.h:36
PriorityQueue(const Ordering ordering)
Constructor.
Definition: priorityqueue.h:58
ElementList::const_iterator ElementListConstIt