3 \brief Templates for priority queues
7 \version\verbatim $Id: gk_mkpqueue.h 13005 2012-10-23 22:34:36Z karypis $ \endverbatim
11 #ifndef _GK_MKPQUEUE_H
12 #define _GK_MKPQUEUE_H
15 #define GK_MKPQUEUE(FPRFX, PQT, KVT, KT, VT, KVMALLOC, KMAX, KEY_LT)\
16 /*************************************************************************/\
17 /*! This function creates and initializes a priority queue */\
18 /**************************************************************************/\
19 PQT *FPRFX ## Create(size_t maxnodes)\
23 queue = (PQT *)gk_malloc(sizeof(PQT), "gk_pqCreate: queue");\
24 FPRFX ## Init(queue, maxnodes);\
30 /*************************************************************************/\
31 /*! This function initializes the data structures of the priority queue */\
32 /**************************************************************************/\
33 void FPRFX ## Init(PQT *queue, size_t maxnodes)\
36 queue->maxnodes = maxnodes;\
38 queue->heap = KVMALLOC(maxnodes, "gk_PQInit: heap");\
39 queue->locator = gk_idxsmalloc(maxnodes, -1, "gk_PQInit: locator");\
43 /*************************************************************************/\
44 /*! This function resets the priority queue */\
45 /**************************************************************************/\
46 void FPRFX ## Reset(PQT *queue)\
49 gk_idx_t *locator=queue->locator;\
50 KVT *heap=queue->heap;\
52 for (i=queue->nnodes-1; i>=0; i--)\
53 locator[heap[i].val] = -1;\
58 /*************************************************************************/\
59 /*! This function frees the internal datastructures of the priority queue */\
60 /**************************************************************************/\
61 void FPRFX ## Free(PQT *queue)\
63 if (queue == NULL) return;\
64 gk_free((void **)&queue->heap, &queue->locator, LTERM);\
69 /*************************************************************************/\
70 /*! This function frees the internal datastructures of the priority queue \
71 and the queue itself */\
72 /**************************************************************************/\
73 void FPRFX ## Destroy(PQT *queue)\
75 if (queue == NULL) return;\
76 FPRFX ## Free(queue);\
77 gk_free((void **)&queue, LTERM);\
81 /*************************************************************************/\
82 /*! This function returns the length of the queue */\
83 /**************************************************************************/\
84 size_t FPRFX ## Length(PQT *queue)\
86 return queue->nnodes;\
90 /*************************************************************************/\
91 /*! This function adds an item in the priority queue */\
92 /**************************************************************************/\
93 int FPRFX ## Insert(PQT *queue, VT node, KT key)\
96 gk_idx_t *locator=queue->locator;\
97 KVT *heap=queue->heap;\
99 ASSERT2(FPRFX ## CheckHeap(queue));\
101 ASSERT(locator[node] == -1);\
103 i = queue->nnodes++;\
106 if (KEY_LT(key, heap[j].key)) {\
108 locator[heap[i].val] = i;\
119 ASSERT2(FPRFX ## CheckHeap(queue));\
125 /*************************************************************************/\
126 /*! This function deletes an item from the priority queue */\
127 /**************************************************************************/\
128 int FPRFX ## Delete(PQT *queue, VT node)\
130 gk_idx_t i, j, nnodes;\
132 gk_idx_t *locator=queue->locator;\
133 KVT *heap=queue->heap;\
135 ASSERT(locator[node] != -1);\
136 ASSERT(heap[locator[node]].val == node);\
138 ASSERT2(FPRFX ## CheckHeap(queue));\
143 if (--queue->nnodes > 0 && heap[queue->nnodes].val != node) {\
144 node = heap[queue->nnodes].val;\
145 newkey = heap[queue->nnodes].key;\
146 oldkey = heap[i].key;\
148 if (KEY_LT(newkey, oldkey)) { /* Filter-up */\
151 if (KEY_LT(newkey, heap[j].key)) {\
153 locator[heap[i].val] = i;\
160 else { /* Filter down */\
161 nnodes = queue->nnodes;\
162 while ((j=(i<<1)+1) < nnodes) {\
163 if (KEY_LT(heap[j].key, newkey)) {\
164 if (j+1 < nnodes && KEY_LT(heap[j+1].key, heap[j].key))\
167 locator[heap[i].val] = i;\
170 else if (j+1 < nnodes && KEY_LT(heap[j+1].key, newkey)) {\
173 locator[heap[i].val] = i;\
181 heap[i].key = newkey;\
186 ASSERT2(FPRFX ## CheckHeap(queue));\
192 /*************************************************************************/\
193 /*! This function updates the key values associated for a particular item */ \
194 /**************************************************************************/\
195 void FPRFX ## Update(PQT *queue, VT node, KT newkey)\
197 gk_idx_t i, j, nnodes;\
199 gk_idx_t *locator=queue->locator;\
200 KVT *heap=queue->heap;\
202 oldkey = heap[locator[node]].key;\
204 ASSERT(locator[node] != -1);\
205 ASSERT(heap[locator[node]].val == node);\
206 ASSERT2(FPRFX ## CheckHeap(queue));\
210 if (KEY_LT(newkey, oldkey)) { /* Filter-up */\
213 if (KEY_LT(newkey, heap[j].key)) {\
215 locator[heap[i].val] = i;\
222 else { /* Filter down */\
223 nnodes = queue->nnodes;\
224 while ((j=(i<<1)+1) < nnodes) {\
225 if (KEY_LT(heap[j].key, newkey)) {\
226 if (j+1 < nnodes && KEY_LT(heap[j+1].key, heap[j].key))\
229 locator[heap[i].val] = i;\
232 else if (j+1 < nnodes && KEY_LT(heap[j+1].key, newkey)) {\
235 locator[heap[i].val] = i;\
243 heap[i].key = newkey;\
247 ASSERT2(FPRFX ## CheckHeap(queue));\
253 /*************************************************************************/\
254 /*! This function returns the item at the top of the queue and removes\
255 it from the priority queue */\
256 /**************************************************************************/\
257 VT FPRFX ## GetTop(PQT *queue)\
265 ASSERT2(FPRFX ## CheckHeap(queue));\
267 if (queue->nnodes == 0)\
273 locator = queue->locator;\
278 if ((i = queue->nnodes) > 0) {\
282 while ((j=2*i+1) < queue->nnodes) {\
283 if (KEY_LT(heap[j].key, key)) {\
284 if (j+1 < queue->nnodes && KEY_LT(heap[j+1].key, heap[j].key))\
287 locator[heap[i].val] = i;\
290 else if (j+1 < queue->nnodes && KEY_LT(heap[j+1].key, key)) {\
293 locator[heap[i].val] = i;\
305 ASSERT2(FPRFX ## CheckHeap(queue));\
310 /*************************************************************************/\
311 /*! This function returns the item at the top of the queue. The item is not\
312 deleted from the queue. */\
313 /**************************************************************************/\
314 VT FPRFX ## SeeTopVal(PQT *queue)\
316 return (queue->nnodes == 0 ? -1 : queue->heap[0].val);\
320 /*************************************************************************/\
321 /*! This function returns the key of the top item. The item is not\
322 deleted from the queue. */\
323 /**************************************************************************/\
324 KT FPRFX ## SeeTopKey(PQT *queue)\
326 return (queue->nnodes == 0 ? KMAX : queue->heap[0].key);\
330 /*************************************************************************/\
331 /*! This function returns the key of a specific item */\
332 /**************************************************************************/\
333 KT FPRFX ## SeeKey(PQT *queue, VT node)\
339 locator = queue->locator;\
341 return heap[locator[node]].key;\
345 /*************************************************************************/\
346 /*! This function returns the first item in a breadth-first traversal of\
347 the heap whose key is less than maxwgt. This function is here due to\
348 hMETIS and is not general!*/\
349 /**************************************************************************/\
351 VT FPRFX ## SeeConstraintTop(PQT *queue, KT maxwgt, KT *wgts)\
355 if (queue->nnodes == 0)\
359 return FPRFX ## SeeTopVal(queue);\
361 for (i=0; i<queue->nnodes; i++) {\
362 if (queue->heap[i].key > 0) {\
363 if (wgts[queue->heap[i].val] <= maxwgt)\
364 return queue->heap[i].val;\
367 if (queue->heap[i/2].key <= 0)\
372 return queue->heap[0].val;\
378 /*************************************************************************/\
379 /*! This functions checks the consistency of the heap */\
380 /**************************************************************************/\
381 int FPRFX ## CheckHeap(PQT *queue)\
389 locator = queue->locator;\
390 nnodes = queue->nnodes;\
395 ASSERT(locator[heap[0].val] == 0);\
396 for (i=1; i<nnodes; i++) {\
397 ASSERT(locator[heap[i].val] == i);\
398 ASSERT(!KEY_LT(heap[i].key, heap[(i-1)/2].key));\
400 for (i=1; i<nnodes; i++)\
401 ASSERT(!KEY_LT(heap[i].key, heap[0].key));\
403 for (j=i=0; i<queue->maxnodes; i++) {\
404 if (locator[i] != -1)\
407 ASSERTP(j == nnodes, ("%jd %jd\n", (intmax_t)j, (intmax_t)nnodes));\
413 #define GK_MKPQUEUE_PROTO(FPRFX, PQT, KT, VT)\
414 PQT * FPRFX ## Create(size_t maxnodes);\
415 void FPRFX ## Init(PQT *queue, size_t maxnodes);\
416 void FPRFX ## Reset(PQT *queue);\
417 void FPRFX ## Free(PQT *queue);\
418 void FPRFX ## Destroy(PQT *queue);\
419 size_t FPRFX ## Length(PQT *queue);\
420 int FPRFX ## Insert(PQT *queue, VT node, KT key);\
421 int FPRFX ## Delete(PQT *queue, VT node);\
422 void FPRFX ## Update(PQT *queue, VT node, KT newkey);\
423 VT FPRFX ## GetTop(PQT *queue);\
424 VT FPRFX ## SeeTopVal(PQT *queue);\
425 KT FPRFX ## SeeTopKey(PQT *queue);\
426 KT FPRFX ## SeeKey(PQT *queue, VT node);\
427 VT FPRFX ## SeeConstraintTop(PQT *queue, KT maxwgt, KT *wgts);\
428 int FPRFX ## CheckHeap(PQT *queue);\
431 /* This is how these macros are used
432 GK_MKPQUEUE(gk_dkvPQ, gk_dkvPQ_t, double, gk_idx_t, gk_dkvmalloc, DBL_MAX)
433 GK_MKPQUEUE_PROTO(gk_dkvPQ, gk_dkvPQ_t, double, gk_idx_t)