priorityqueue.h

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
Generated by  doxygen 1.6.2-20100208