priority-queue.hpp
Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */ 00002 /* 00003 * Main authors: 00004 * Christian Schulte <schulte@gecode.org> 00005 * Guido Tack <tack@gecode.org> 00006 * 00007 * Copyright: 00008 * Christian Schulte, 2002 00009 * Guido Tack, 2004 00010 * 00011 * Last modified: 00012 * $Date: 2009-09-08 21:10:29 +0200 (Tue, 08 Sep 2009) $ by $Author: schulte $ 00013 * $Revision: 9692 $ 00014 * 00015 * This file is part of Gecode, the generic constraint 00016 * development environment: 00017 * http://www.gecode.org 00018 * 00019 * Permission is hereby granted, free of charge, to any person obtaining 00020 * a copy of this software and associated documentation files (the 00021 * "Software"), to deal in the Software without restriction, including 00022 * without limitation the rights to use, copy, modify, merge, publish, 00023 * distribute, sublicense, and/or sell copies of the Software, and to 00024 * permit persons to whom the Software is furnished to do so, subject to 00025 * the following conditions: 00026 * 00027 * The above copyright notice and this permission notice shall be 00028 * included in all copies or substantial portions of the Software. 00029 * 00030 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 00031 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 00032 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 00033 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE 00034 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION 00035 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION 00036 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 00037 * 00038 */ 00039 00040 #include <algorithm> 00041 00042 namespace Gecode { namespace Iter { 00043 00054 template<class T, class Less> 00055 class PriorityQueue { 00056 private: 00058 class SharedPriorityQueue { 00059 public: 00061 int n; 00063 int size; 00065 unsigned int ref; 00067 Less l; 00069 T pq[1]; 00070 00072 static SharedPriorityQueue* allocate(int n, const Less& l); 00074 void fixdown(void); 00076 void fixup(int n); 00077 }; 00079 SharedPriorityQueue* spq; 00080 00081 public: 00083 PriorityQueue(void); 00085 PriorityQueue(int n, const Less& l); 00087 void init(int, const Less&); 00089 PriorityQueue(const PriorityQueue& p); 00091 const PriorityQueue& operator =(const PriorityQueue&); 00093 ~PriorityQueue(void); 00094 00096 bool empty(void) const; 00098 void insert(const T& x); 00100 void remove(void); 00102 T& top(void); 00104 void fix(void); 00105 00107 void update(const PriorityQueue<T,Less>& p, bool share); 00108 }; 00109 00110 template<class T, class Less> 00111 forceinline typename PriorityQueue<T,Less>::SharedPriorityQueue* 00112 PriorityQueue<T,Less>::SharedPriorityQueue::allocate(int n, const Less& l) { 00113 SharedPriorityQueue* spq 00114 = static_cast<SharedPriorityQueue*> 00115 (heap.ralloc(sizeof(SharedPriorityQueue) + (n-1)*sizeof(T))); 00116 spq->size = n; 00117 spq->n = 0; 00118 spq->ref = 1; 00119 spq->l = l; 00120 return spq; 00121 } 00122 00123 template<class T, class Less> 00124 forceinline void 00125 PriorityQueue<T,Less>::SharedPriorityQueue::fixdown(void) { 00126 int k = 0; 00127 while ((k << 1) < n) { 00128 int j = k << 1; 00129 if (j < n-1 && l(pq[j],pq[j+1])) 00130 j++; 00131 if (!l(pq[k],pq[j])) 00132 break; 00133 std::swap(pq[k], pq[j]); 00134 k = j; 00135 } 00136 } 00137 00138 template<class T, class Less> 00139 forceinline void 00140 PriorityQueue<T,Less>::SharedPriorityQueue::fixup(int k) { 00141 while (k > 0 && l(pq[k >> 1],pq[k])) { 00142 std::swap(pq[k],pq[k >> 1]); 00143 k >>= 1; 00144 } 00145 } 00146 00147 template<class T, class Less> 00148 forceinline 00149 PriorityQueue<T,Less>::PriorityQueue(void) 00150 : spq(NULL) {} 00151 00152 template<class T, class Less> 00153 forceinline 00154 PriorityQueue<T,Less>::PriorityQueue(int n, const Less& l) 00155 : spq(SharedPriorityQueue::allocate(n,l)) {} 00156 00157 template<class T, class Less> 00158 forceinline void 00159 PriorityQueue<T,Less>::init(int n, const Less& l) { 00160 spq = SharedPriorityQueue::allocate(n,l); 00161 } 00162 00163 template<class T, class Less> 00164 forceinline 00165 PriorityQueue<T,Less>::PriorityQueue(const PriorityQueue<T,Less>& p) 00166 : spq(p.spq) { 00167 if (spq != NULL) 00168 spq->ref++; 00169 } 00170 00171 template<class T, class Less> 00172 forceinline const PriorityQueue<T,Less>& 00173 PriorityQueue<T,Less>::operator =(const PriorityQueue<T,Less>& p) { 00174 if (this != &p) { 00175 if ((spq != NULL) && (--spq->ref == 0)) 00176 heap.rfree(spq); 00177 spq = p.spq; 00178 if (spq != NULL) 00179 spq->ref++; 00180 } 00181 return *this; 00182 } 00183 00184 template<class T, class Less> 00185 forceinline void 00186 PriorityQueue<T,Less>::update(const PriorityQueue<T,Less>& p, bool share) { 00187 if (share) { 00188 spq = p.spq; 00189 if (spq != NULL) 00190 spq->ref++; 00191 } else { 00192 if (p.spq != NULL) { 00193 spq = allocate(p.spq->n,p.spq->l); 00194 } else { 00195 spq = NULL; 00196 } 00197 } 00198 } 00199 00200 template<class T, class Less> 00201 forceinline 00202 PriorityQueue<T,Less>::~PriorityQueue(void) { 00203 if ((spq != NULL) && (--spq->ref == 0)) 00204 heap.rfree(spq); 00205 } 00206 00207 template<class T, class Less> 00208 forceinline bool 00209 PriorityQueue<T,Less>::empty(void) const { 00210 return (spq == NULL) || (spq->n == 0); 00211 } 00212 00213 00214 template<class T, class Less> 00215 forceinline void 00216 PriorityQueue<T,Less>::insert(const T& x) { 00217 spq->pq[spq->n++] = x; 00218 spq->fixup(spq->n-1); 00219 } 00220 00221 template<class T, class Less> 00222 forceinline void 00223 PriorityQueue<T,Less>::remove(void) { 00224 spq->pq[0] = spq->pq[--spq->n]; 00225 spq->fixdown(); 00226 } 00227 00228 template<class T, class Less> 00229 forceinline T& 00230 PriorityQueue<T,Less>::top(void) { 00231 return spq->pq[0]; 00232 } 00233 00234 template<class T, class Less> 00235 forceinline void 00236 PriorityQueue<T,Less>::fix(void) { 00237 spq->fixdown(); 00238 } 00239 00240 }} 00241 00242 // STATISTICS: support-any