Mercurial > fife-parpg

comparison engine/core/util/structures/priorityqueue.h @ 0:4a0efb7baf70

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
* Datasets becomes the new trunk and retires after that :-)
author mvbarracuda@33b003aa-7bff-0310-803a-e67f0ece8222
date Sun, 29 Jun 2008 18:44:17 +0000
parents
children 90005975cdbb
comparison
equal deleted inserted replaced
-1:000000000000 0:4a0efb7baf70
1 /***************************************************************************
2 * Copyright (C) 2005-2008 by the FIFE team *
3 * http://www.fifengine.de *
4 * This file is part of FIFE. *
5 * *
6 * FIFE is free software; you can redistribute it and/or modify *
7 * it under the terms of the GNU General Public License as published by *
8 * the Free Software Foundation; either version 2 of the License, or *
9 * (at your option) any later version. *
10 * *
11 * This program 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 *
14 * GNU General Public License for more details. *
15 * *
16 * You should have received a copy of the GNU General Public License *
17 * along with this program; if not, write to the *
18 * Free Software Foundation, Inc., *
19 * 51 Franklin St, 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
30 /** A pq which stores index-value pairs for elements.
31 *
32 * This acts as a normal PQ but stores some extra information about the
33 * elements that it's storing, namely a special unique index.
34 */
35 template<typename index_type, typename priority_type>
36 class PriorityQueue {
37 public:
38 /** Used for element ordering.
39 *
40 */
41 enum Ordering {
42 Ascending, //!< lowest priority first.
43 Descending //!< highest priority first.
44 };
45
46 typedef std::pair<index_type, priority_type> value_type;
47
48 /** Constructor
49 *
50 */
51 PriorityQueue(void) : m_ordering(Ascending) {
52 }
53
54 /** Constructor
55 *
56 * @param ordering The ordering the priority queue should use.
57 */
58 PriorityQueue(const Ordering ordering) : m_ordering(ordering) {
59 }
60
61 /** Pushes a new element onto the queue.
62 *
63 * The element is pushed onto the queue and then moved up the queue until it's
64 * in the correct position by priority.
65 *
66 * @param element Of type value_type which contains both the index and the priority of the element.
67 */
68 void pushElement(const value_type& element);
69
70 /** Pops the element with the highest priority from the queue.
71 *
72 * Removes and deletes the highest priority element.
73 */
74 void popElement(void);
75
76 /** Changes the priority of an element.
77 *
78 * Locates the element with the given index and changes it's priority to the given
79 * priority, it then re-orders the priority queue to take account of this new information.
80 *
81 * @param index The index of the element to change the priority of.
82 * @param newPriority The new priority of the element.
83 * @return True if the element could be found, false otherwise.
84 */
85 bool changeElementPriority(const index_type& index, const priority_type& newPriority);
86
87 /** Removes all elements from the priority queue.
88 *
89 */
90 void clear(void);
91
92 /** Retrieves the element with the highest priority.
93 *
94 * This function will generate an assertion error if the pq is
95 * empty.
96 *
97 * @return A const reference to the highest priority element.
98 */
99 const value_type getPriorityElement(void) const {
100
101 assert(!empty());
102
103 return m_elements.front();
104
105 }
106
107 /** Determines whether the queue is currently empty.
108 *
109 * @return true if it is empty, false otherwise.
110 */
111 bool empty(void) const {
112 return m_elements.empty();
113 }
114
115 /** Returns the current size of the queue.
116 *
117 */
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.
130 Ordering m_ordering;
131
132 /** Orders a PQ element up the list.
133 *
134 * @param i An iterator representing the element in the list to be sorted up.
135 */
136 void orderUp(ElementListIt i);
137 /** Orders a PQ element up the list.
138 *
139 * @param entry A const reference to a value_type which represents the element to be added to the
140 * pq.
141 */
142 void orderUp(const value_type& entry);
143
144 /** Orders a PQ element down the list.
145 *
146 * @param An iterator representing the element in the PQ to order down.
147 */
148 void orderDown(ElementListIt i);
149
150 /** Retrieves the iterator to the element with the given index.
151 *
152 * @param index A const reference to the index to find.
153 */
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
166 /** The comparison function, used to compare two elements.
167 *
168 * @param a The l-operand of the comparison operation.
169 * @param b The r-operand of the comparison operation.
170 * @return An integer representing the result of the comparison operation. 1 being a is greather than b,
171 * -1 being a is less than b and 0 meaning that they're equal.
172 */
173 int compare(const value_type& a, const value_type& b);
174 };
175 }
176
177 template<typename index_type, typename priority_type>
178 void FIFE::PriorityQueue<index_type, priority_type>::pushElement(const value_type& element) {
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>
188 void FIFE::PriorityQueue<index_type, priority_type>::popElement(void) {
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
199 ElementListIt i = getElementIterator(index);
200
201 if(i == m_elements.end()) {
202 return false;
203 }
204
205 int 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>
220 void FIFE::PriorityQueue<index_type, priority_type>::clear(void) {
221
222 m_elements.clear();
223
224 }
225
226 template<typename index_type, typename priority_type>
227 void FIFE::PriorityQueue<index_type, priority_type>::orderUp(ElementListIt i) {
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>
252 void FIFE::PriorityQueue<index_type, priority_type>::orderUp(const value_type& val)
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>
272 void FIFE::PriorityQueue<index_type, priority_type>::orderDown(ElementListIt i) {
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>
304 int FIFE::PriorityQueue<index_type, priority_type>::compare(const value_type& a, const value_type& b) {
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