1 /*!
2 \file  gk_mkpqueue.h
3 \brief Templates for priority queues
4 
5 \date   Started 4/09/07
6 \author George
7 \version\verbatim $Id: gk_mkpqueue.h 13005 2012-10-23 22:34:36Z karypis $ \endverbatim
8 */
9 
10 
11 #ifndef _GK_MKPQUEUE_H
12 #define _GK_MKPQUEUE_H
13 
14 
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)\
20 {\
21   PQT *queue; \
22 \
23   queue = (PQT *)gk_malloc(sizeof(PQT), "gk_pqCreate: queue");\
24   FPRFX ## Init(queue, maxnodes);\
25 \
26   return queue;\
27 }\
28 \
29 \
30 /*************************************************************************/\
31 /*! This function initializes the data structures of the priority queue */\
32 /**************************************************************************/\
33 void FPRFX ## Init(PQT *queue, size_t maxnodes)\
34 {\
35   queue->nnodes = 0;\
36   queue->maxnodes = maxnodes;\
37 \
38   queue->heap    = KVMALLOC(maxnodes, "gk_PQInit: heap");\
39   queue->locator = gk_idxsmalloc(maxnodes, -1, "gk_PQInit: locator");\
40 }\
41 \
42 \
43 /*************************************************************************/\
44 /*! This function resets the priority queue */\
45 /**************************************************************************/\
46 void FPRFX ## Reset(PQT *queue)\
47 {\
48   gk_idx_t i;\
49   gk_idx_t *locator=queue->locator;\
50   KVT *heap=queue->heap;\
51 \
52   for (i=queue->nnodes-1; i>=0; i--)\
53     locator[heap[i].val] = -1;\
54   queue->nnodes = 0;\
55 }\
56 \
57 \
58 /*************************************************************************/\
59 /*! This function frees the internal datastructures of the priority queue */\
60 /**************************************************************************/\
61 void FPRFX ## Free(PQT *queue)\
62 {\
63   if (queue == NULL) return;\
64   gk_free((void **)&queue->heap, &queue->locator, LTERM);\
65   queue->maxnodes = 0;\
66 }\
67 \
68 \
69 /*************************************************************************/\
70 /*! This function frees the internal datastructures of the priority queue \
71     and the queue itself */\
72 /**************************************************************************/\
73 void FPRFX ## Destroy(PQT *queue)\
74 {\
75   if (queue == NULL) return;\
76   FPRFX ## Free(queue);\
77   gk_free((void **)&queue, LTERM);\
78 }\
79 \
80 \
81 /*************************************************************************/\
82 /*! This function returns the length of the queue */\
83 /**************************************************************************/\
84 size_t FPRFX ## Length(PQT *queue)\
85 {\
86   return queue->nnodes;\
87 }\
88 \
89 \
90 /*************************************************************************/\
91 /*! This function adds an item in the priority queue */\
92 /**************************************************************************/\
93 int FPRFX ## Insert(PQT *queue, VT node, KT key)\
94 {\
95   gk_idx_t i, j;\
96   gk_idx_t *locator=queue->locator;\
97   KVT *heap=queue->heap;\
98 \
99   ASSERT2(FPRFX ## CheckHeap(queue));\
100 \
101   ASSERT(locator[node] == -1);\
102 \
103   i = queue->nnodes++;\
104   while (i > 0) {\
105     j = (i-1)>>1;\
106     if (KEY_LT(key, heap[j].key)) {\
107       heap[i] = heap[j];\
108       locator[heap[i].val] = i;\
109       i = j;\
110     }\
111     else\
112       break;\
113   }\
114   ASSERT(i >= 0);\
115   heap[i].key   = key;\
116   heap[i].val   = node;\
117   locator[node] = i;\
118 \
119   ASSERT2(FPRFX ## CheckHeap(queue));\
120 \
121   return 0;\
122 }\
123 \
124 \
125 /*************************************************************************/\
126 /*! This function deletes an item from the priority queue */\
127 /**************************************************************************/\
128 int FPRFX ## Delete(PQT *queue, VT node)\
129 {\
130   gk_idx_t i, j, nnodes;\
131   KT newkey, oldkey;\
132   gk_idx_t *locator=queue->locator;\
133   KVT *heap=queue->heap;\
134 \
135   ASSERT(locator[node] != -1);\
136   ASSERT(heap[locator[node]].val == node);\
137 \
138   ASSERT2(FPRFX ## CheckHeap(queue));\
139 \
140   i = locator[node];\
141   locator[node] = -1;\
142 \
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;\
147 \
148     if (KEY_LT(newkey, oldkey)) { /* Filter-up */\
149       while (i > 0) {\
150         j = (i-1)>>1;\
151         if (KEY_LT(newkey, heap[j].key)) {\
152           heap[i] = heap[j];\
153           locator[heap[i].val] = i;\
154           i = j;\
155         }\
156         else\
157           break;\
158       }\
159     }\
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))\
165             j++;\
166           heap[i] = heap[j];\
167           locator[heap[i].val] = i;\
168           i = j;\
169         }\
170         else if (j+1 < nnodes && KEY_LT(heap[j+1].key, newkey)) {\
171           j++;\
172           heap[i] = heap[j];\
173           locator[heap[i].val] = i;\
174           i = j;\
175         }\
176         else\
177           break;\
178       }\
179     }\
180 \
181     heap[i].key   = newkey;\
182     heap[i].val   = node;\
183     locator[node] = i;\
184   }\
185 \
186   ASSERT2(FPRFX ## CheckHeap(queue));\
187 \
188   return 0;\
189 }\
190 \
191 \
192 /*************************************************************************/\
193 /*! This function updates the key values associated for a particular item */ \
194 /**************************************************************************/\
195 void FPRFX ## Update(PQT *queue, VT node, KT newkey)\
196 {\
197   gk_idx_t i, j, nnodes;\
198   KT oldkey;\
199   gk_idx_t *locator=queue->locator;\
200   KVT *heap=queue->heap;\
201 \
202   oldkey = heap[locator[node]].key;\
203 \
204   ASSERT(locator[node] != -1);\
205   ASSERT(heap[locator[node]].val == node);\
206   ASSERT2(FPRFX ## CheckHeap(queue));\
207 \
208   i = locator[node];\
209 \
210   if (KEY_LT(newkey, oldkey)) { /* Filter-up */\
211     while (i > 0) {\
212       j = (i-1)>>1;\
213       if (KEY_LT(newkey, heap[j].key)) {\
214         heap[i] = heap[j];\
215         locator[heap[i].val] = i;\
216         i = j;\
217       }\
218       else\
219         break;\
220     }\
221   }\
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))\
227           j++;\
228         heap[i] = heap[j];\
229         locator[heap[i].val] = i;\
230         i = j;\
231       }\
232       else if (j+1 < nnodes && KEY_LT(heap[j+1].key, newkey)) {\
233         j++;\
234         heap[i] = heap[j];\
235         locator[heap[i].val] = i;\
236         i = j;\
237       }\
238       else\
239         break;\
240     }\
241   }\
242 \
243   heap[i].key   = newkey;\
244   heap[i].val   = node;\
245   locator[node] = i;\
246 \
247   ASSERT2(FPRFX ## CheckHeap(queue));\
248 \
249   return;\
250 }\
251 \
252 \
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)\
258 {\
259   gk_idx_t i, j;\
260   gk_idx_t *locator;\
261   KVT *heap;\
262   VT vtx, node;\
263   KT key;\
264 \
265   ASSERT2(FPRFX ## CheckHeap(queue));\
266 \
267   if (queue->nnodes == 0)\
268     return -1;\
269 \
270   queue->nnodes--;\
271 \
272   heap    = queue->heap;\
273   locator = queue->locator;\
274 \
275   vtx = heap[0].val;\
276   locator[vtx] = -1;\
277 \
278   if ((i = queue->nnodes) > 0) {\
279     key  = heap[i].key;\
280     node = heap[i].val;\
281     i = 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))\
285           j = j+1;\
286         heap[i] = heap[j];\
287         locator[heap[i].val] = i;\
288         i = j;\
289       }\
290       else if (j+1 < queue->nnodes && KEY_LT(heap[j+1].key, key)) {\
291         j = j+1;\
292         heap[i] = heap[j];\
293         locator[heap[i].val] = i;\
294         i = j;\
295       }\
296       else\
297         break;\
298     }\
299 \
300     heap[i].key   = key;\
301     heap[i].val   = node;\
302     locator[node] = i;\
303   }\
304 \
305   ASSERT2(FPRFX ## CheckHeap(queue));\
306   return vtx;\
307 }\
308 \
309 \
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)\
315 {\
316   return (queue->nnodes == 0 ? -1 : queue->heap[0].val);\
317 }\
318 \
319 \
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)\
325 {\
326   return (queue->nnodes == 0 ? KMAX : queue->heap[0].key);\
327 }\
328 \
329 \
330 /*************************************************************************/\
331 /*! This function returns the key of a specific item */\
332 /**************************************************************************/\
333 KT FPRFX ## SeeKey(PQT *queue, VT node)\
334 {\
335   gk_idx_t *locator;\
336   KVT *heap;\
337 \
338   heap    = queue->heap;\
339   locator = queue->locator;\
340 \
341   return heap[locator[node]].key;\
342 }\
343 \
344 \
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 /**************************************************************************/\
350 /*\
351 VT FPRFX ## SeeConstraintTop(PQT *queue, KT maxwgt, KT *wgts)\
352 {\
353   gk_idx_t i;\
354 \
355   if (queue->nnodes == 0)\
356     return -1;\
357 \
358   if (maxwgt <= 1000)\
359     return FPRFX ## SeeTopVal(queue);\
360 \
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;\
365     }\
366     else {\
367       if (queue->heap[i/2].key <= 0)\
368         break;\
369     }\
370   }\
371 \
372   return queue->heap[0].val;\
373 \
374 }\
375 */\
376 \
377 \
378 /*************************************************************************/\
379 /*! This functions checks the consistency of the heap */\
380 /**************************************************************************/\
381 int FPRFX ## CheckHeap(PQT *queue)\
382 {\
383   gk_idx_t i, j;\
384   size_t nnodes;\
385   gk_idx_t *locator;\
386   KVT *heap;\
387 \
388   heap    = queue->heap;\
389   locator = queue->locator;\
390   nnodes  = queue->nnodes;\
391 \
392   if (nnodes == 0)\
393     return 1;\
394 \
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));\
399   }\
400   for (i=1; i<nnodes; i++)\
401     ASSERT(!KEY_LT(heap[i].key, heap[0].key));\
402 \
403   for (j=i=0; i<queue->maxnodes; i++) {\
404     if (locator[i] != -1)\
405       j++;\
406   }\
407   ASSERTP(j == nnodes, ("%jd %jd\n", (intmax_t)j, (intmax_t)nnodes));\
408 \
409   return 1;\
410 }\
411 
412 
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);\
429 
430 
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)
434 */
435 
436 
437 #endif
438