FIFE 2008.0
|
00001 /*************************************************************************** 00002 * Copyright (C) 2005-2008 by the FIFE team * 00003 * http://www.fifengine.de * 00004 * This file is part of FIFE. * 00005 * * 00006 * FIFE is free software; you can redistribute it and/or * 00007 * modify it under the terms of the GNU Lesser General Public * 00008 * License as published by the Free Software Foundation; either * 00009 * version 2.1 of the License, or (at your option) any later version. * 00010 * * 00011 * This library is distributed in the hope that it will be useful, * 00012 * but WITHOUT ANY WARRANTY; without even the implied warranty of * 00013 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU * 00014 * Lesser General Public License for more details. * 00015 * * 00016 * You should have received a copy of the GNU Lesser General Public * 00017 * License along with this library; if not, write to the * 00018 * Free Software Foundation, Inc., * 00019 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA * 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 //A list of valuetype pairs that represents the pq. 00127 ElementList m_elements; 00128 00129 //The order to use when sorting the pq. 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