00001
00024 #ifndef PQUEUE_H_
00025 #define PQUEUE_H_
00026 #include "GMetisConfig.h"
00027 #include <algorithm>
00028 #include <vector>
00029 using namespace std;
00030
00031 template<class T>
00032 struct ListNode{
00033 ListNode(){
00034 prev=NULL;
00035 next=NULL;
00036 }
00037 T value;
00038 ListNode* prev;
00039 ListNode* next;
00040 };
00041
00042 template<class T>
00043 struct KeyValue {
00044 int key;
00045 T value;
00046 };
00047
00054 template <class T>
00055 class SuperPQueue{
00056 public:
00057 virtual void insert(T value, int priority) = 0;
00058 virtual void remove(T value, int priority) = 0;
00059 virtual void update(T value, int oldPriority, int newPriority) = 0;
00060 virtual T getMax() = 0;
00061 virtual void reset() = 0;
00062 virtual int size() = 0;
00063 virtual ~SuperPQueue(){};
00064 };
00065
00066 template <class T>
00067 class HeapQueue: public SuperPQueue<T>{
00068 public:
00069 HeapQueue(int maxNumNodes, int maxPriority, int (*mapToInt)(T)){
00070 numNodes = 0;
00071 heap.resize(maxNumNodes);
00072 locator.resize(maxNumNodes);
00073 this->mapToInt = mapToInt;
00074
00075 fill(locator.begin(),locator.end(), -1);
00076 this->maxNumNodes = maxNumNodes;
00077 }
00078 virtual ~HeapQueue(){
00079 }
00080 void insert(T value, int priority) {
00081
00082 int i = numNodes;
00083 numNodes++;
00084 while (i > 0) {
00085 int j = (i - 1) / 2;
00086 if (heap[j].key < priority) {
00087 heap[i].key = heap[j].key;
00088 heap[i].value = heap[j].value;
00089 locator[(*mapToInt)(heap[i].value)] = i;
00090 i = j;
00091 } else {
00092 break;
00093 }
00094 }
00095
00096 heap[i].key = priority;
00097 heap[i].value = value;
00098 locator[(*mapToInt)(value)] = i;
00099 }
00100 void remove(T value, int priority) {
00101 int id = (*mapToInt)(value);
00102 int i = locator[id];
00103 locator[id] = -1;
00104 if (--numNodes > 0 && (*mapToInt)(heap[numNodes].value) != id) {
00105 value = heap[numNodes].value;
00106 int newPriority = heap[numNodes].key;
00107 int oldPriority = heap[i].key;
00108
00109 if (oldPriority < newPriority) {
00110 while (i > 0) {
00111 int j = (i - 1) >> 1;
00112 if (heap[j].key < newPriority) {
00113 heap[i].value = heap[j].value;
00114 heap[i].key = heap[j].key;
00115 locator[(*mapToInt)(heap[i].value)] = i;
00116 i = j;
00117 } else
00118 break;
00119 }
00120 } else {
00121 int j = 0;
00122 while ((j = 2 * i + 1) < numNodes) {
00123 if (heap[j].key > newPriority) {
00124 if (j + 1 < numNodes && heap[j + 1].key > heap[j].key)
00125 j = j + 1;
00126 heap[i].value = heap[j].value;
00127 heap[i].key = heap[j].key;
00128 locator[(*mapToInt)(heap[i].value)] = i;
00129 i = j;
00130 } else if (j + 1 < numNodes && heap[j + 1].key > newPriority) {
00131 j = j + 1;
00132 heap[i].value = heap[j].value;
00133 heap[i].key = heap[j].key;
00134 locator[(*mapToInt)(heap[i].value)] = i;
00135 i = j;
00136 } else
00137 break;
00138 }
00139 }
00140 heap[i].key = newPriority;
00141 heap[i].value = value;
00142 locator[(*mapToInt)(value)] = i;
00143 }
00144 }
00145 void update(T value, int oldPriority, int newPriority) {
00146 int i = locator[(*mapToInt)(value)];
00147 if (oldPriority < newPriority) {
00148 while (i > 0) {
00149 int j = (i - 1) >> 1;
00150 if (heap[j].key < newPriority) {
00151 heap[i].value = heap[j].value;
00152 heap[i].key = heap[j].key;
00153 locator[(*mapToInt)(heap[i].value)] = i;
00154 i = j;
00155 } else
00156 break;
00157 }
00158 } else {
00159 int j = 0;
00160 while ((j = 2 * i + 1) < numNodes) {
00161 if (heap[j].key > newPriority) {
00162 if (j + 1 < numNodes && heap[j + 1].key > heap[j].key)
00163 j = j + 1;
00164 heap[i].value = heap[j].value;
00165 heap[i].key = heap[j].key;
00166 locator[(*mapToInt)(heap[i].value)] = i;
00167 i = j;
00168 } else if (j + 1 < numNodes && heap[j + 1].key > newPriority) {
00169 j = j + 1;
00170 heap[i].value = heap[j].value;
00171 heap[i].key = heap[j].key;
00172 locator[(*mapToInt)(heap[i].value)] = i;
00173 i = j;
00174 } else
00175 break;
00176 }
00177 }
00178 heap[i].key = newPriority;
00179 heap[i].value = value;
00180 locator[(*mapToInt)(value)] = i;
00181 }
00182
00183 T getMax(){
00184 if(numNodes == 0){
00185 assert (false);
00186 return T();
00187 }
00188 numNodes -- ;
00189 T vtx = heap[0].value;
00190 locator[(*mapToInt)(vtx)] = -1;
00191 int i = numNodes;
00192 if (i > 0) {
00193 int priority = heap[i].key;
00194 T node = heap[i].value;
00195 i = 0;
00196 int j = 0;
00197 while ((j = 2 * i + 1) < numNodes) {
00198 if (heap[j].key > priority) {
00199 if (j + 1 < numNodes && heap[j + 1].key > heap[j].key)
00200 j = j + 1;
00201 heap[i].value = heap[j].value;
00202 heap[i].key = heap[j].key;
00203 locator[(*mapToInt)(heap[i].value)] = i;
00204 i = j;
00205 } else if (j + 1 < numNodes && heap[j + 1].key > priority) {
00206 j = j + 1;
00207 heap[i].value = heap[j].value;
00208 heap[i].key = heap[j].key;
00209 locator[(*mapToInt)(heap[i].value)] = i;
00210 i = j;
00211 } else
00212 break;
00213 }
00214 heap[i].key = priority;
00215 heap[i].value = node;
00216 locator[(*mapToInt)(node)] = i;
00217 }
00218 return vtx;
00219 }
00220 void reset(){
00221 numNodes = 0;
00222
00223 fill(locator.begin(),locator.end(), -1);
00224 }
00225 int size(){
00226 return numNodes;
00227 }
00228
00229 private:
00230 typedef KeyValue<T> TKV;
00231 vector<TKV> heap;
00232 vector<int> locator;
00233 int (*mapToInt)(T);
00234 int numNodes;
00235 int maxNumNodes;;
00236 };
00237
00238 template <class T>
00239 class LimitedPriorityQueue: public SuperPQueue<T>{
00240 public:
00241 LimitedPriorityQueue(int maxNumNodes, int maxPriority, int (*mapToInt)(T)):PLUS_PRIORITYSPAN(500), NEG_PRIORITYSPAN(500){
00242 pPrioritySpan = min(PLUS_PRIORITYSPAN, maxPriority);
00243 nPrioritySpan = min(NEG_PRIORITYSPAN, maxPriority);
00244 nodes = new ListNode<T>[maxNumNodes];
00245 bucketSize = pPrioritySpan + nPrioritySpan + 1;
00246 buckets.resize(bucketSize);
00247 for(int i=0;i<pPrioritySpan + nPrioritySpan + 1;i++){
00248 buckets[i] = NULL;
00249 }
00250 bucketIndex = nPrioritySpan;
00251 _maxPriority = 0;
00252 _maxPriority = -nPrioritySpan;
00253 _mapToInt = mapToInt;
00254 numNodes = 0;
00255 }
00256 virtual ~LimitedPriorityQueue(){
00257 delete[] nodes;
00258 }
00259 void insert(T value, int priority) {
00260 numNodes++;
00261 int id = (*_mapToInt)(value);
00262
00263 nodes[id].value = value;
00264 ListNode<T>* newNode = &nodes[id];
00265 newNode->prev = NULL;
00266 newNode->next = buckets[priority + bucketIndex];
00267 if (newNode->next != NULL)
00268 newNode->next->prev = newNode;
00269
00270 buckets[priority + bucketIndex] = newNode;
00271 if (_maxPriority < priority){
00272 _maxPriority = priority;
00273 }
00274 }
00275 void remove(T value, int priority) {
00276 numNodes--;
00277 ListNode<T>* node = &nodes[(*_mapToInt)(value)];
00278 if (node->prev != NULL)
00279 node->prev->next = node->next;
00280 else
00281 buckets[priority + bucketIndex] = node->next;
00282 if (node->next != NULL)
00283 node->next->prev = node->prev;
00284
00285 if (buckets[priority + bucketIndex] == NULL && priority == _maxPriority) {
00286 if (numNodes == 0)
00287 _maxPriority = -nPrioritySpan;
00288 else
00289 for (; buckets[_maxPriority + bucketIndex] == NULL; _maxPriority--);
00290 }
00291 }
00292 void update(T value, int oldPriority, int newPriority) {
00293 remove(value, oldPriority);
00294 insert(value, newPriority);
00295 }
00296 T getMax() {
00297 if (numNodes == 0){
00298 cout<<"queue empty..........."<<endl;
00299 assert (false);
00300 return T();
00301 }
00302 ListNode<T>* tptr = NULL;
00303 numNodes--;
00304 tptr = buckets[_maxPriority + bucketIndex];
00305 buckets[_maxPriority + bucketIndex] = tptr->next;
00306 if (tptr->next!=NULL) {
00307 tptr->next->prev = NULL;
00308 } else {
00309 if (numNodes == 0) {
00310 _maxPriority = -nPrioritySpan;
00311 } else {
00312 for (; buckets[_maxPriority + bucketIndex] == NULL ; _maxPriority--){
00313 };
00314 }
00315 }
00316 return tptr->value;
00317 }
00318
00319 int size(){
00320 return numNodes;
00321 }
00322 void reset(){
00323 numNodes = 0;
00324 _maxPriority = -nPrioritySpan;
00325
00326 for (int i = 0; i < bucketSize; i++) {
00327 buckets[i] = NULL;
00328 }
00329 bucketIndex = nPrioritySpan;
00330 }
00331
00332 private:
00333 int numNodes;
00334 int _maxPriority;
00335 int pPrioritySpan;
00336 int nPrioritySpan;
00337 ListNode<T>* nodes;
00338 vector<ListNode<T>*> buckets;
00339 int bucketSize;
00340 int bucketIndex;
00341 const int PLUS_PRIORITYSPAN;
00342 const int NEG_PRIORITYSPAN;
00343 int (*_mapToInt)(T);
00344 };
00345
00346 class PQueue{
00347 public:
00348 PQueue(int maxNumNodes, int maxGain) {
00349 if (maxGain > PLUS_GAINSPAN || maxNumNodes < 500) {
00350
00351 internalQueue = new HeapQueue<GNode>(maxNumNodes, maxGain, &gNodeToInt);
00352 } else {
00353
00354 internalQueue = new LimitedPriorityQueue<GNode>(maxNumNodes, maxGain, &gNodeToInt);
00355 }
00356 }
00357 ~PQueue(){
00358 delete internalQueue;
00359 }
00360
00364 void insert(GNode node, int gain) {
00365 internalQueue->insert(node, gain);
00366 }
00367
00371 void remove(GNode value, int gain) {
00372 internalQueue->remove(value, gain);
00373 }
00374
00378 void update(GNode value, int oldgain, int newgain) {
00379 internalQueue->update(value, oldgain, newgain);
00380 }
00381
00385 GNode getMax() {
00386 return internalQueue->getMax();
00387 }
00388
00389 int size(){
00390 return internalQueue->size();
00391 }
00395 void reset() {
00396 internalQueue->reset();
00397 }
00398
00399 private:
00400
00401
00402 SuperPQueue<GNode>* internalQueue;
00403 static const int PLUS_GAINSPAN = 500;
00404 };
00405
00406
00407
00408 #endif
