00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040 #include <algorithm>
00041
00042 namespace Gecode { namespace Support {
00043
00054 template <class T, class Less>
00055 class PQueue {
00056 private:
00058 class SharedPQueue {
00059 public:
00061 int n;
00063 int size;
00065 unsigned int ref;
00067 Less l;
00069 T pq[1];
00070
00072 static SharedPQueue* allocate(int n, const Less& l);
00074 void fixdown(void);
00076 void fixup(int n);
00077 };
00079 SharedPQueue* spq;
00080
00081 public:
00083 PQueue(void);
00085 PQueue(int n, const Less& l);
00087 void init(int, const Less&);
00089 PQueue(const PQueue& p);
00091 const PQueue& operator=(const PQueue&);
00093 ~PQueue(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 PQueue<T,Less>& p, bool share);
00108 };
00109
00110 template <class T, class Less>
00111 forceinline typename PQueue<T,Less>::SharedPQueue*
00112 PQueue<T,Less>::SharedPQueue::allocate(int n, const Less& l) {
00113 SharedPQueue* spq
00114 = static_cast<SharedPQueue*>
00115 (Memory::malloc(sizeof(SharedPQueue) + (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 PQueue<T,Less>::SharedPQueue::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 PQueue<T,Less>::SharedPQueue::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 PQueue<T,Less>::PQueue(void)
00150 : spq(NULL) {}
00151
00152 template <class T, class Less>
00153 forceinline
00154 PQueue<T,Less>::PQueue(int n, const Less& l)
00155 : spq(SharedPQueue::allocate(n,l)) {}
00156
00157 template <class T, class Less>
00158 forceinline void
00159 PQueue<T,Less>::init(int n, const Less& l) {
00160 spq = SharedPQueue::allocate(n,l);
00161 }
00162
00163 template <class T, class Less>
00164 forceinline
00165 PQueue<T,Less>::PQueue(const PQueue<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 PQueue<T,Less>&
00173 PQueue<T,Less>::operator =(const PQueue<T,Less>& p) {
00174 if (this != &p) {
00175 if ((spq != NULL) && (--spq->ref == 0))
00176 Memory::free(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 PQueue<T,Less>::update(const PQueue<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 PQueue<T,Less>::~PQueue(void) {
00203 if ((spq != NULL) && (--spq->ref == 0))
00204 Memory::free(spq);
00205 }
00206
00207 template <class T, class Less>
00208 forceinline bool
00209 PQueue<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 PQueue<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 PQueue<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 PQueue<T,Less>::top(void) {
00231 return spq->pq[0];
00232 }
00233
00234 template <class T, class Less>
00235 forceinline void
00236 PQueue<T,Less>::fix(void) {
00237 spq->fixdown();
00238 }
00239
00240 }}
00241
00242