1 /*!
2 \file  gk_mkpqueue2.h
3 \brief Templates for priority queues that do not utilize locators and as such
4        they can use different types of values.
5 
6 \date   Started 4/09/07
7 \author George
8 \version\verbatim $Id: gk_mkpqueue2.h 13005 2012-10-23 22:34:36Z karypis $ \endverbatim
9 */
10 
11 
12 #ifndef _GK_MKPQUEUE2_H
13 #define _GK_MKPQUEUE2_H
14 
15 
16 #define GK_MKPQUEUE2(FPRFX, PQT, KT, VT, KMALLOC, VMALLOC, KMAX, KEY_LT)\
17 /*************************************************************************/\
18 /*! This function creates and initializes a priority queue */\
19 /**************************************************************************/\
20 PQT *FPRFX ## Create2(ssize_t maxnodes)\
21 {\
22   PQT *queue; \
23 \
24   if ((queue = (PQT *)gk_malloc(sizeof(PQT), "gk_pqCreate2: queue")) != NULL) {\
25     memset(queue, 0, sizeof(PQT));\
26     queue->nnodes   = 0;\
27     queue->maxnodes = maxnodes;\
28     queue->keys     = KMALLOC(maxnodes, "gk_pqCreate2: keys");\
29     queue->vals     = VMALLOC(maxnodes, "gk_pqCreate2: vals");\
30 \
31     if (queue->keys == NULL || queue->vals == NULL)\
32       gk_free((void **)&queue->keys, &queue->vals, &queue, LTERM);\
33   }\
34 \
35   return queue;\
36 }\
37 \
38 \
39 /*************************************************************************/\
40 /*! This function resets the priority queue */\
41 /**************************************************************************/\
42 void FPRFX ## Reset2(PQT *queue)\
43 {\
44   queue->nnodes = 0;\
45 }\
46 \
47 \
48 /*************************************************************************/\
49 /*! This function frees the internal datastructures of the priority queue */\
50 /**************************************************************************/\
51 void FPRFX ## Destroy2(PQT **r_queue)\
52 {\
53   PQT *queue = *r_queue; \
54   if (queue == NULL) return;\
55   gk_free((void **)&queue->keys, &queue->vals, &queue, LTERM);\
56   *r_queue = NULL;\
57 }\
58 \
59 \
60 /*************************************************************************/\
61 /*! This function returns the length of the queue */\
62 /**************************************************************************/\
63 size_t FPRFX ## Length2(PQT *queue)\
64 {\
65   return queue->nnodes;\
66 }\
67 \
68 \
69 /*************************************************************************/\
70 /*! This function adds an item in the priority queue. */\
71 /**************************************************************************/\
72 int FPRFX ## Insert2(PQT *queue, VT val, KT key)\
73 {\
74   ssize_t i, j;\
75   KT *keys=queue->keys;\
76   VT *vals=queue->vals;\
77 \
78   ASSERT2(FPRFX ## CheckHeap2(queue));\
79 \
80   if (queue->nnodes == queue->maxnodes) \
81     return 0;\
82 \
83   ASSERT2(FPRFX ## CheckHeap2(queue));\
84 \
85   i = queue->nnodes++;\
86   while (i > 0) {\
87     j = (i-1)>>1;\
88     if (KEY_LT(key, keys[j])) {\
89       keys[i] = keys[j];\
90       vals[i] = vals[j];\
91       i = j;\
92     }\
93     else\
94       break;\
95   }\
96   ASSERT(i >= 0);\
97   keys[i] = key;\
98   vals[i] = val;\
99 \
100   ASSERT2(FPRFX ## CheckHeap2(queue));\
101 \
102   return 1;\
103 }\
104 \
105 \
106 /*************************************************************************/\
107 /*! This function returns the item at the top of the queue and removes\
108     it from the priority queue */\
109 /**************************************************************************/\
110 int FPRFX ## GetTop2(PQT *queue, VT *r_val)\
111 {\
112   ssize_t i, j;\
113   KT key, *keys=queue->keys;\
114   VT val, *vals=queue->vals;\
115 \
116   ASSERT2(FPRFX ## CheckHeap2(queue));\
117 \
118   if (queue->nnodes == 0)\
119     return 0;\
120 \
121   queue->nnodes--;\
122 \
123   *r_val = vals[0];\
124 \
125   if ((i = queue->nnodes) > 0) {\
126     key = keys[i];\
127     val = vals[i];\
128     i = 0;\
129     while ((j=2*i+1) < queue->nnodes) {\
130       if (KEY_LT(keys[j], key)) {\
131         if (j+1 < queue->nnodes && KEY_LT(keys[j+1], keys[j]))\
132           j = j+1;\
133         keys[i] = keys[j];\
134         vals[i] = vals[j];\
135         i = j;\
136       }\
137       else if (j+1 < queue->nnodes && KEY_LT(keys[j+1], key)) {\
138         j = j+1;\
139         keys[i] = keys[j];\
140         vals[i] = vals[j];\
141         i = j;\
142       }\
143       else\
144         break;\
145     }\
146 \
147     keys[i] = key;\
148     vals[i] = val;\
149   }\
150 \
151   ASSERT2(FPRFX ## CheckHeap2(queue));\
152 \
153   return 1;\
154 }\
155 \
156 \
157 /*************************************************************************/\
158 /*! This function returns the item at the top of the queue. The item is not\
159     deleted from the queue. */\
160 /**************************************************************************/\
161 int FPRFX ## SeeTopVal2(PQT *queue, VT *r_val)\
162 {\
163   if (queue->nnodes == 0) \
164     return 0;\
165 \
166   *r_val = queue->vals[0];\
167 \
168   return 1;\
169 }\
170 \
171 \
172 /*************************************************************************/\
173 /*! This function returns the key of the top item. The item is not\
174     deleted from the queue. */\
175 /**************************************************************************/\
176 KT FPRFX ## SeeTopKey2(PQT *queue)\
177 {\
178   return (queue->nnodes == 0 ? KMAX : queue->keys[0]);\
179 }\
180 \
181 \
182 /*************************************************************************/\
183 /*! This functions checks the consistency of the heap */\
184 /**************************************************************************/\
185 int FPRFX ## CheckHeap2(PQT *queue)\
186 {\
187   ssize_t i;\
188   KT *keys=queue->keys;\
189 \
190   if (queue->nnodes == 0)\
191     return 1;\
192 \
193   for (i=1; i<queue->nnodes; i++) {\
194     ASSERT(!KEY_LT(keys[i], keys[(i-1)/2]));\
195   }\
196   for (i=1; i<queue->nnodes; i++)\
197     ASSERT(!KEY_LT(keys[i], keys[0]));\
198 \
199   return 1;\
200 }\
201 
202 
203 #define GK_MKPQUEUE2_PROTO(FPRFX, PQT, KT, VT)\
204   PQT *  FPRFX ## Create2(ssize_t maxnodes);\
205   void   FPRFX ## Reset2(PQT *queue);\
206   void   FPRFX ## Destroy2(PQT **r_queue);\
207   size_t FPRFX ## Length2(PQT *queue);\
208   int    FPRFX ## Insert2(PQT *queue, VT node, KT key);\
209   int    FPRFX ## GetTop2(PQT *queue, VT *r_val);\
210   int    FPRFX ## SeeTopVal2(PQT *queue, VT *r_val);\
211   KT     FPRFX ## SeeTopKey2(PQT *queue);\
212   int    FPRFX ## CheckHeap2(PQT *queue);\
213 
214 
215 #endif
216