priorityqueue.h
00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022 #ifndef FIFE_SOLVER_INDEXEDPQ_H
00023 #define FIFE_SOLVER_INDEXEDPQ_H
00024
00025 #include <cassert>
00026 #include <list>
00027
00028 namespace FIFE {
00029
00035 template<typename index_type, typename priority_type>
00036 class PriorityQueue {
00037 public:
00041 enum Ordering {
00042 Ascending,
00043 Descending
00044 };
00045
00046 typedef std::pair<index_type, priority_type> value_type;
00047
00051 PriorityQueue(void) : m_ordering(Ascending) {
00052 }
00053
00058 PriorityQueue(const Ordering ordering) : m_ordering(ordering) {
00059 }
00060
00068 void pushElement(const value_type& element);
00069
00074 void popElement(void);
00075
00085 bool changeElementPriority(const index_type& index, const priority_type& newPriority);
00086
00090 void clear(void);
00091
00099 const value_type getPriorityElement(void) const {
00100
00101 assert(!empty());
00102
00103 return m_elements.front();
00104
00105 }
00106
00111 bool empty(void) const {
00112 return m_elements.empty();
00113 }
00114
00118 size_t size(void) const {
00119 return m_elements.size();
00120 }
00121 private:
00122 typedef std::list<value_type> ElementList;
00123 typedef typename ElementList::iterator ElementListIt;
00124 typedef typename ElementList::const_iterator ElementListConstIt;
00125
00126
00127 ElementList m_elements;
00128
00129
00130 Ordering m_ordering;
00131
00136 void orderUp(ElementListIt i);
00142 void orderUp(const value_type& entry);
00143
00148 void orderDown(ElementListIt i);
00149
00154 ElementListIt getElementIterator(const index_type& index) {
00155
00156 for(ElementListIt i = m_elements.begin(); i != m_elements.end(); ++i) {
00157 if(i->first == index) {
00158 return i;
00159 }
00160 }
00161
00162 return m_elements.end();
00163
00164 }
00165
00173 int compare(const value_type& a, const value_type& b);
00174 };
00175 }
00176
00177 template<typename index_type, typename priority_type>
00178 void FIFE::PriorityQueue<index_type, priority_type>::pushElement(const value_type& element) {
00179 if(empty()) {
00180 m_elements.push_front(element);
00181 }
00182 else {
00183 orderUp(element);
00184 }
00185 }
00186
00187 template<typename index_type, typename priority_type>
00188 void FIFE::PriorityQueue<index_type, priority_type>::popElement(void) {
00189
00190 if(!empty()) {
00191 m_elements.pop_front();
00192 }
00193
00194 }
00195
00196 template<typename index_type, typename priority_type>
00197 bool FIFE::PriorityQueue<index_type, priority_type>::changeElementPriority(const index_type& index, const priority_type& newPriority) {
00198
00199 ElementListIt i = getElementIterator(index);
00200
00201 if(i == m_elements.end()) {
00202 return false;
00203 }
00204
00205 int compare_res = compare(value_type(index, newPriority), (*i));
00206
00207 i->second = newPriority;
00208
00209 if(compare_res > 0 && i != m_elements.begin()) {
00210 orderDown(i);
00211 } else if(compare_res < 0) {
00212 orderUp(i);
00213 }
00214
00215 return true;
00216
00217 }
00218
00219 template<typename index_type, typename priority_type>
00220 void FIFE::PriorityQueue<index_type, priority_type>::clear(void) {
00221
00222 m_elements.clear();
00223
00224 }
00225
00226 template<typename index_type, typename priority_type>
00227 void FIFE::PriorityQueue<index_type, priority_type>::orderUp(ElementListIt i) {
00228
00229 assert(i != m_elements.end() && L"Invalid iterator passed to function");
00230
00231 value_type vt = (*i);
00232
00233 i = m_elements.erase(i);
00234
00235 while(i != m_elements.end()) {
00236
00237 if(compare(vt, (*i)) > 0) {
00238
00239 m_elements.insert(i, vt);
00240
00241 return;
00242 }
00243
00244 ++i;
00245 }
00246
00247 m_elements.push_back(vt);
00248
00249 }
00250
00251 template<class index_type, class priority_type>
00252 void FIFE::PriorityQueue<index_type, priority_type>::orderUp(const value_type& val)
00253 {
00254 for(ElementListIt i = m_elements.begin(); i != m_elements.end(); ++i)
00255 {
00256 assert(val.first != i->first);
00257
00258 if(compare(val, (*i)) > 0)
00259 {
00260 assert(val.first != i->first);
00261
00262 m_elements.insert(i, val);
00263
00264 return;
00265 }
00266 }
00267
00268 m_elements.push_back(val);
00269 }
00270
00271 template<typename index_type, typename priority_type>
00272 void FIFE::PriorityQueue<index_type, priority_type>::orderDown(ElementListIt i) {
00273
00274 assert(i != m_elements.end());
00275
00276 value_type vt = (*i);
00277
00278 i = m_elements.erase(i);
00279
00280 if(i == m_elements.end()) {
00281 --i;
00282 }
00283
00284 ElementListIt j = i;
00285
00286 ++j;
00287
00288 while(i != m_elements.begin()) {
00289 if(compare(vt, (*i)) < 0) {
00290
00291 m_elements.insert(j, vt);
00292
00293 return;
00294 }
00295
00296 --i;
00297 --j;
00298 }
00299
00300 m_elements.push_front(vt);
00301 }
00302
00303 template<typename index_type, typename priority_type>
00304 int FIFE::PriorityQueue<index_type, priority_type>::compare(const value_type& a, const value_type& b) {
00305
00306 if(m_ordering == Descending) {
00307
00308 if(a.second > b.second) {
00309 return 1;
00310 } else if(b.second > a.second) {
00311 return -1;
00312 }
00313
00314 } else {
00315
00316 if(a.second < b.second) {
00317 return 1;
00318 } else if(b.second < a.second) {
00319 return -1;
00320 }
00321 }
00322
00323 return 0;
00324 }
00325
00326 #endif