| Geant4 Cross Reference |
1 // see license file for original license. 1 // see license file for original license.
2 2
3 #ifndef tools_glutess_priorityq 3 #ifndef tools_glutess_priorityq
4 #define tools_glutess_priorityq 4 #define tools_glutess_priorityq
5 5
6 #include <climits> /* LONG_MAX */ 6 #include <climits> /* LONG_MAX */
7 #include "memalloc" 7 #include "memalloc"
8 8
9 /* Include all the code for the regular heap-b 9 /* Include all the code for the regular heap-based queue here. */
10 10
11 ////////////////////////////////////////////// 11 /////////////////////////////////////////////////////////////////
12 //#include "priorityq-heap.ic" 12 //#include "priorityq-heap.ic"
13 //#include "priorityq-heap" 13 //#include "priorityq-heap"
14 14
15 /* Use #define's so that another heap implemen 15 /* Use #define's so that another heap implementation can use this one */
16 16
17 #define PQkey PQHeapKey 17 #define PQkey PQHeapKey
18 #define PQhandle PQHeapHandle 18 #define PQhandle PQHeapHandle
19 #define PriorityQ PriorityQHeap 19 #define PriorityQ PriorityQHeap
20 20
21 #define pqNewPriorityQ(leq) __gl_pqHeapNewPrio 21 #define pqNewPriorityQ(leq) __gl_pqHeapNewPriorityQ(leq)
22 #define pqDeletePriorityQ(pq) __gl_pqHeapDelet 22 #define pqDeletePriorityQ(pq) __gl_pqHeapDeletePriorityQ(pq)
23 23
24 /* The basic operations are insertion of a new 24 /* The basic operations are insertion of a new key (pqInsert),
25 * and examination/extraction of a key whose v 25 * and examination/extraction of a key whose value is minimum
26 * (pqMinimum/pqExtractMin). Deletion is also 26 * (pqMinimum/pqExtractMin). Deletion is also allowed (pqDelete);
27 * for this purpose pqInsert returns a "handle 27 * for this purpose pqInsert returns a "handle" which is supplied
28 * as the argument. 28 * as the argument.
29 * 29 *
30 * An initial heap may be created efficiently 30 * An initial heap may be created efficiently by calling pqInsert
31 * repeatedly, then calling pqInit. In any ca 31 * repeatedly, then calling pqInit. In any case pqInit must be called
32 * before any operations other than pqInsert a 32 * before any operations other than pqInsert are used.
33 * 33 *
34 * If the heap is empty, pqMinimum/pqExtractMi 34 * If the heap is empty, pqMinimum/pqExtractMin will return a NULL key.
35 * This may also be tested with pqIsEmpty. 35 * This may also be tested with pqIsEmpty.
36 */ 36 */
37 #define pqInit(pq) __gl_pqHeapInit(pq) 37 #define pqInit(pq) __gl_pqHeapInit(pq)
38 #define pqInsert(pq,key) __gl_pqHeapInsert(pq 38 #define pqInsert(pq,key) __gl_pqHeapInsert(pq,key)
39 #define pqMinimum(pq) __gl_pqHeapMinimum(pq) 39 #define pqMinimum(pq) __gl_pqHeapMinimum(pq)
40 #define pqExtractMin(pq) __gl_pqHeapExtractMi 40 #define pqExtractMin(pq) __gl_pqHeapExtractMin(pq)
41 #define pqDelete(pq,handle) __gl_pqHeapDelete( 41 #define pqDelete(pq,handle) __gl_pqHeapDelete(pq,handle)
42 #define pqIsEmpty(pq) __gl_pqHeapIsEmpty(pq) 42 #define pqIsEmpty(pq) __gl_pqHeapIsEmpty(pq)
43 43
44 /* Since we support deletion the data structur 44 /* Since we support deletion the data structure is a little more
45 * complicated than an ordinary heap. "nodes" 45 * complicated than an ordinary heap. "nodes" is the heap itself;
46 * active nodes are stored in the range 1..pq- 46 * active nodes are stored in the range 1..pq->size. When the
47 * heap exceeds its allocated size (pq->max), 47 * heap exceeds its allocated size (pq->max), its size doubles.
48 * The children of node i are nodes 2i and 2i+ 48 * The children of node i are nodes 2i and 2i+1.
49 * 49 *
50 * Each node stores an index into an array "ha 50 * Each node stores an index into an array "handles". Each handle
51 * stores a key, plus a pointer back to the no 51 * stores a key, plus a pointer back to the node which currently
52 * represents that key (ie. nodes[handles[i].n 52 * represents that key (ie. nodes[handles[i].node].handle == i).
53 */ 53 */
54 54
55 typedef void *PQkey; 55 typedef void *PQkey;
56 typedef long PQhandle; 56 typedef long PQhandle;
57 typedef struct PriorityQ PriorityQ; 57 typedef struct PriorityQ PriorityQ;
58 58
59 typedef struct { PQhandle handle; } PQnode; 59 typedef struct { PQhandle handle; } PQnode;
60 typedef struct { PQkey key; PQhandle node; } P 60 typedef struct { PQkey key; PQhandle node; } PQhandleElem;
61 61
62 struct PriorityQ { 62 struct PriorityQ {
63 PQnode *nodes; 63 PQnode *nodes;
64 PQhandleElem *handles; 64 PQhandleElem *handles;
65 long size, max; 65 long size, max;
66 PQhandle freeList; 66 PQhandle freeList;
67 int initialized; 67 int initialized;
68 int (*leq)(PQkey key1, PQkey key2); 68 int (*leq)(PQkey key1, PQkey key2);
69 }; 69 };
70 70
71 #define __gl_pqHeapMinimum(pq) ((pq)->handles 71 #define __gl_pqHeapMinimum(pq) ((pq)->handles[(pq)->nodes[1].handle].key)
72 #define __gl_pqHeapIsEmpty(pq) ((pq)->size == 72 #define __gl_pqHeapIsEmpty(pq) ((pq)->size == 0)
73 73
74 ////////////////////////////////////////////// 74 /////////////////////////////////////////////////////////////////
75 ////////////////////////////////////////////// 75 /////////////////////////////////////////////////////////////////
76 //#define INIT_SIZE 32 76 //#define INIT_SIZE 32
77 inline long INIT_SIZE() { 77 inline long INIT_SIZE() {
78 static const long s_value = 32; 78 static const long s_value = 32;
79 return s_value; 79 return s_value;
80 } 80 }
81 81
82 /* Violates modularity, but a little faster */ 82 /* Violates modularity, but a little faster */
83 #include "geom" 83 #include "geom"
84 #define LEQ(x,y) VertLeq((GLUvertex *)x, (GLU 84 #define LEQ(x,y) VertLeq((GLUvertex *)x, (GLUvertex *)y)
85 85
86 /* really __gl_pqHeapNewPriorityQ */ 86 /* really __gl_pqHeapNewPriorityQ */
87 inline PriorityQ *pqNewPriorityQ( int (*leq)(P 87 inline PriorityQ *pqNewPriorityQ( int (*leq)(PQkey key1, PQkey key2) )
88 { 88 {
89 PriorityQ *pq = (PriorityQ *)memAlloc( sizeo 89 PriorityQ *pq = (PriorityQ *)memAlloc( sizeof( PriorityQ ));
90 if (pq == NULL) return NULL; 90 if (pq == NULL) return NULL;
91 91
92 pq->size = 0; 92 pq->size = 0;
93 pq->max = INIT_SIZE(); 93 pq->max = INIT_SIZE();
94 pq->nodes = (PQnode *)memAlloc( (INIT_SIZE() 94 pq->nodes = (PQnode *)memAlloc( (INIT_SIZE() + 1) * sizeof(pq->nodes[0]) );
95 if (pq->nodes == NULL) { 95 if (pq->nodes == NULL) {
96 memFree(pq); 96 memFree(pq);
97 return NULL; 97 return NULL;
98 } 98 }
99 99
100 pq->handles = (PQhandleElem *)memAlloc( (INI 100 pq->handles = (PQhandleElem *)memAlloc( (INIT_SIZE() + 1) * sizeof(pq->handles[0]) );
101 if (pq->handles == NULL) { 101 if (pq->handles == NULL) {
102 memFree(pq->nodes); 102 memFree(pq->nodes);
103 memFree(pq); 103 memFree(pq);
104 return NULL; 104 return NULL;
105 } 105 }
106 106
107 pq->initialized = TOOLS_GLU_FALSE; 107 pq->initialized = TOOLS_GLU_FALSE;
108 pq->freeList = 0; 108 pq->freeList = 0;
109 pq->leq = leq; 109 pq->leq = leq;
110 110
111 pq->nodes[1].handle = 1; /* so that Minimum 111 pq->nodes[1].handle = 1; /* so that Minimum() returns NULL */
112 pq->handles[1].key = NULL; 112 pq->handles[1].key = NULL;
113 return pq; 113 return pq;
114 } 114 }
115 115
116 /* really __gl_pqHeapDeletePriorityQ */ 116 /* really __gl_pqHeapDeletePriorityQ */
117 inline void pqDeletePriorityQ( PriorityQ *pq ) 117 inline void pqDeletePriorityQ( PriorityQ *pq )
118 { 118 {
119 memFree( pq->handles ); 119 memFree( pq->handles );
120 memFree( pq->nodes ); 120 memFree( pq->nodes );
121 memFree( pq ); 121 memFree( pq );
122 } 122 }
123 123
124 124
125 inline/*static*/ void static_FloatDown( Priori 125 inline/*static*/ void static_FloatDown( PriorityQ *pq, long curr )
126 { 126 {
127 PQnode *n = pq->nodes; 127 PQnode *n = pq->nodes;
128 PQhandleElem *h = pq->handles; 128 PQhandleElem *h = pq->handles;
129 PQhandle hCurr, hChild; 129 PQhandle hCurr, hChild;
130 long child; 130 long child;
131 131
132 hCurr = n[curr].handle; 132 hCurr = n[curr].handle;
133 for( ;; ) { 133 for( ;; ) {
134 child = curr << 1; 134 child = curr << 1;
135 if( child < pq->size && LEQ( h[n[child+1]. 135 if( child < pq->size && LEQ( h[n[child+1].handle].key,
136 h[n[child].handle].key )) { 136 h[n[child].handle].key )) {
137 ++child; 137 ++child;
138 } 138 }
139 139
140 assert(child <= pq->max); 140 assert(child <= pq->max);
141 141
142 hChild = n[child].handle; 142 hChild = n[child].handle;
143 if( child > pq->size || LEQ( h[hCurr].key, 143 if( child > pq->size || LEQ( h[hCurr].key, h[hChild].key )) {
144 n[curr].handle = hCurr; 144 n[curr].handle = hCurr;
145 h[hCurr].node = curr; 145 h[hCurr].node = curr;
146 break; 146 break;
147 } 147 }
148 n[curr].handle = hChild; 148 n[curr].handle = hChild;
149 h[hChild].node = curr; 149 h[hChild].node = curr;
150 curr = child; 150 curr = child;
151 } 151 }
152 } 152 }
153 153
154 154
155 inline/*static*/ void static_FloatUp( Priority 155 inline/*static*/ void static_FloatUp( PriorityQ *pq, long curr )
156 { 156 {
157 PQnode *n = pq->nodes; 157 PQnode *n = pq->nodes;
158 PQhandleElem *h = pq->handles; 158 PQhandleElem *h = pq->handles;
159 PQhandle hCurr, hParent; 159 PQhandle hCurr, hParent;
160 long parent; 160 long parent;
161 161
162 hCurr = n[curr].handle; 162 hCurr = n[curr].handle;
163 for( ;; ) { 163 for( ;; ) {
164 parent = curr >> 1; 164 parent = curr >> 1;
165 hParent = n[parent].handle; 165 hParent = n[parent].handle;
166 if( parent == 0 || LEQ( h[hParent].key, h[ 166 if( parent == 0 || LEQ( h[hParent].key, h[hCurr].key )) {
167 n[curr].handle = hCurr; 167 n[curr].handle = hCurr;
168 h[hCurr].node = curr; 168 h[hCurr].node = curr;
169 break; 169 break;
170 } 170 }
171 n[curr].handle = hParent; 171 n[curr].handle = hParent;
172 h[hParent].node = curr; 172 h[hParent].node = curr;
173 curr = parent; 173 curr = parent;
174 } 174 }
175 } 175 }
176 176
177 /* really __gl_pqHeapInit */ 177 /* really __gl_pqHeapInit */
178 inline void pqInit( PriorityQ *pq ) 178 inline void pqInit( PriorityQ *pq )
179 { 179 {
180 long i; 180 long i;
181 181
182 /* This method of building a heap is O(n), r 182 /* This method of building a heap is O(n), rather than O(n lg n). */
183 183
184 for( i = pq->size; i >= 1; --i ) { 184 for( i = pq->size; i >= 1; --i ) {
185 static_FloatDown( pq, i ); 185 static_FloatDown( pq, i );
186 } 186 }
187 pq->initialized = TOOLS_GLU_TRUE; 187 pq->initialized = TOOLS_GLU_TRUE;
188 } 188 }
189 189
190 /* really __gl_pqHeapInsert */ 190 /* really __gl_pqHeapInsert */
191 /* returns LONG_MAX iff out of memory */ 191 /* returns LONG_MAX iff out of memory */
192 inline PQhandle pqInsert( PriorityQ *pq, PQkey 192 inline PQhandle pqInsert( PriorityQ *pq, PQkey keyNew )
193 { 193 {
194 long curr; 194 long curr;
195 PQhandle free; 195 PQhandle free;
196 196
197 curr = ++ pq->size; 197 curr = ++ pq->size;
198 if( (curr*2) > pq->max ) { 198 if( (curr*2) > pq->max ) {
199 PQnode *saveNodes= pq->nodes; 199 PQnode *saveNodes= pq->nodes;
200 PQhandleElem *saveHandles= pq->handles; 200 PQhandleElem *saveHandles= pq->handles;
201 201
202 /* If the heap overflows, double its size. 202 /* If the heap overflows, double its size. */
203 pq->max <<= 1; 203 pq->max <<= 1;
204 pq->nodes = (PQnode *)memRealloc( pq->node 204 pq->nodes = (PQnode *)memRealloc( pq->nodes,
205 (size_t) 205 (size_t)
206 ((pq->max + 1) * sizeof( pq->node 206 ((pq->max + 1) * sizeof( pq->nodes[0] )));
207 if (pq->nodes == NULL) { 207 if (pq->nodes == NULL) {
208 pq->nodes = saveNodes; /* restore ptr t 208 pq->nodes = saveNodes; /* restore ptr to free upon return */
209 return LONG_MAX; 209 return LONG_MAX;
210 } 210 }
211 pq->handles = (PQhandleElem *)memRealloc( 211 pq->handles = (PQhandleElem *)memRealloc( pq->handles,
212 (size_t) 212 (size_t)
213 ((pq->max + 1) * 213 ((pq->max + 1) *
214 sizeof( pq->handles[0] ))); 214 sizeof( pq->handles[0] )));
215 if (pq->handles == NULL) { 215 if (pq->handles == NULL) {
216 pq->handles = saveHandles; /* restore p 216 pq->handles = saveHandles; /* restore ptr to free upon return */
217 return LONG_MAX; 217 return LONG_MAX;
218 } 218 }
219 } 219 }
220 220
221 if( pq->freeList == 0 ) { 221 if( pq->freeList == 0 ) {
222 free = curr; 222 free = curr;
223 } else { 223 } else {
224 free = pq->freeList; 224 free = pq->freeList;
225 pq->freeList = pq->handles[free].node; 225 pq->freeList = pq->handles[free].node;
226 } 226 }
227 227
228 pq->nodes[curr].handle = free; 228 pq->nodes[curr].handle = free;
229 pq->handles[free].node = curr; 229 pq->handles[free].node = curr;
230 pq->handles[free].key = keyNew; 230 pq->handles[free].key = keyNew;
231 231
232 if( pq->initialized ) { 232 if( pq->initialized ) {
233 static_FloatUp( pq, curr ); 233 static_FloatUp( pq, curr );
234 } 234 }
235 assert(free != LONG_MAX); 235 assert(free != LONG_MAX);
236 return free; 236 return free;
237 } 237 }
238 238
239 /* really __gl_pqHeapExtractMin */ 239 /* really __gl_pqHeapExtractMin */
240 inline PQkey pqExtractMin( PriorityQ *pq ) 240 inline PQkey pqExtractMin( PriorityQ *pq )
241 { 241 {
242 PQnode *n = pq->nodes; 242 PQnode *n = pq->nodes;
243 PQhandleElem *h = pq->handles; 243 PQhandleElem *h = pq->handles;
244 PQhandle hMin = n[1].handle; 244 PQhandle hMin = n[1].handle;
245 PQkey min = h[hMin].key; 245 PQkey min = h[hMin].key;
246 246
247 if( pq->size > 0 ) { 247 if( pq->size > 0 ) {
248 n[1].handle = n[pq->size].handle; 248 n[1].handle = n[pq->size].handle;
249 h[n[1].handle].node = 1; 249 h[n[1].handle].node = 1;
250 250
251 h[hMin].key = NULL; 251 h[hMin].key = NULL;
252 h[hMin].node = pq->freeList; 252 h[hMin].node = pq->freeList;
253 pq->freeList = hMin; 253 pq->freeList = hMin;
254 254
255 if( -- pq->size > 0 ) { 255 if( -- pq->size > 0 ) {
256 static_FloatDown( pq, 1 ); 256 static_FloatDown( pq, 1 );
257 } 257 }
258 } 258 }
259 return min; 259 return min;
260 } 260 }
261 261
262 /* really __gl_pqHeapDelete */ 262 /* really __gl_pqHeapDelete */
263 inline void pqDelete( PriorityQ *pq, PQhandle 263 inline void pqDelete( PriorityQ *pq, PQhandle hCurr )
264 { 264 {
265 PQnode *n = pq->nodes; 265 PQnode *n = pq->nodes;
266 PQhandleElem *h = pq->handles; 266 PQhandleElem *h = pq->handles;
267 long curr; 267 long curr;
268 268
269 assert( hCurr >= 1 && hCurr <= pq->max && h[ 269 assert( hCurr >= 1 && hCurr <= pq->max && h[hCurr].key != NULL );
270 270
271 curr = h[hCurr].node; 271 curr = h[hCurr].node;
272 n[curr].handle = n[pq->size].handle; 272 n[curr].handle = n[pq->size].handle;
273 h[n[curr].handle].node = curr; 273 h[n[curr].handle].node = curr;
274 274
275 if( curr <= -- pq->size ) { 275 if( curr <= -- pq->size ) {
276 if( curr <= 1 || LEQ( h[n[curr>>1].handle] 276 if( curr <= 1 || LEQ( h[n[curr>>1].handle].key, h[n[curr].handle].key )) {
277 static_FloatDown( pq, curr ); 277 static_FloatDown( pq, curr );
278 } else { 278 } else {
279 static_FloatUp( pq, curr ); 279 static_FloatUp( pq, curr );
280 } 280 }
281 } 281 }
282 h[hCurr].key = NULL; 282 h[hCurr].key = NULL;
283 h[hCurr].node = pq->freeList; 283 h[hCurr].node = pq->freeList;
284 pq->freeList = hCurr; 284 pq->freeList = hCurr;
285 } 285 }
286 286
287 /* Now redefine all the function names to map 287 /* Now redefine all the function names to map to their "Sort" versions. */
288 288
289 ////////////////////////////////////////////// 289 /////////////////////////////////////////////////////////////////
290 //#include "priorityq-sort" 290 //#include "priorityq-sort"
291 291
292 #undef PQkey 292 #undef PQkey
293 #undef PQhandle 293 #undef PQhandle
294 #undef PriorityQ 294 #undef PriorityQ
295 #undef pqNewPriorityQ 295 #undef pqNewPriorityQ
296 #undef pqDeletePriorityQ 296 #undef pqDeletePriorityQ
297 #undef pqInit 297 #undef pqInit
298 #undef pqInsert 298 #undef pqInsert
299 #undef pqMinimum 299 #undef pqMinimum
300 #undef pqExtractMin 300 #undef pqExtractMin
301 #undef pqDelete 301 #undef pqDelete
302 #undef pqIsEmpty 302 #undef pqIsEmpty
303 303
304 /* Use #define's so that another heap implemen 304 /* Use #define's so that another heap implementation can use this one */
305 305
306 #define PQkey PQSortKey 306 #define PQkey PQSortKey
307 #define PQhandle PQSortHandle 307 #define PQhandle PQSortHandle
308 #define PriorityQ PriorityQSort 308 #define PriorityQ PriorityQSort
309 309
310 #define pqNewPriorityQ(leq) __gl_pqSortNewPrio 310 #define pqNewPriorityQ(leq) __gl_pqSortNewPriorityQ(leq)
311 #define pqDeletePriorityQ(pq) __gl_pqSortDelet 311 #define pqDeletePriorityQ(pq) __gl_pqSortDeletePriorityQ(pq)
312 312
313 /* The basic operations are insertion of a new 313 /* The basic operations are insertion of a new key (pqInsert),
314 * and examination/extraction of a key whose v 314 * and examination/extraction of a key whose value is minimum
315 * (pqMinimum/pqExtractMin). Deletion is also 315 * (pqMinimum/pqExtractMin). Deletion is also allowed (pqDelete);
316 * for this purpose pqInsert returns a "handle 316 * for this purpose pqInsert returns a "handle" which is supplied
317 * as the argument. 317 * as the argument.
318 * 318 *
319 * An initial heap may be created efficiently 319 * An initial heap may be created efficiently by calling pqInsert
320 * repeatedly, then calling pqInit. In any ca 320 * repeatedly, then calling pqInit. In any case pqInit must be called
321 * before any operations other than pqInsert a 321 * before any operations other than pqInsert are used.
322 * 322 *
323 * If the heap is empty, pqMinimum/pqExtractMi 323 * If the heap is empty, pqMinimum/pqExtractMin will return a NULL key.
324 * This may also be tested with pqIsEmpty. 324 * This may also be tested with pqIsEmpty.
325 */ 325 */
326 #define pqInit(pq) __gl_pqSortInit(pq) 326 #define pqInit(pq) __gl_pqSortInit(pq)
327 #define pqInsert(pq,key) __gl_pqSortInsert(pq 327 #define pqInsert(pq,key) __gl_pqSortInsert(pq,key)
328 #define pqMinimum(pq) __gl_pqSortMinimum(pq) 328 #define pqMinimum(pq) __gl_pqSortMinimum(pq)
329 #define pqExtractMin(pq) __gl_pqSortExtractMi 329 #define pqExtractMin(pq) __gl_pqSortExtractMin(pq)
330 #define pqDelete(pq,handle) __gl_pqSortDelete( 330 #define pqDelete(pq,handle) __gl_pqSortDelete(pq,handle)
331 #define pqIsEmpty(pq) __gl_pqSortIsEmpty(pq) 331 #define pqIsEmpty(pq) __gl_pqSortIsEmpty(pq)
332 332
333 333
334 /* Since we support deletion the data structur 334 /* Since we support deletion the data structure is a little more
335 * complicated than an ordinary heap. "nodes" 335 * complicated than an ordinary heap. "nodes" is the heap itself;
336 * active nodes are stored in the range 1..pq- 336 * active nodes are stored in the range 1..pq->size. When the
337 * heap exceeds its allocated size (pq->max), 337 * heap exceeds its allocated size (pq->max), its size doubles.
338 * The children of node i are nodes 2i and 2i+ 338 * The children of node i are nodes 2i and 2i+1.
339 * 339 *
340 * Each node stores an index into an array "ha 340 * Each node stores an index into an array "handles". Each handle
341 * stores a key, plus a pointer back to the no 341 * stores a key, plus a pointer back to the node which currently
342 * represents that key (ie. nodes[handles[i].n 342 * represents that key (ie. nodes[handles[i].node].handle == i).
343 */ 343 */
344 344
345 typedef PQHeapKey PQkey; 345 typedef PQHeapKey PQkey;
346 typedef PQHeapHandle PQhandle; 346 typedef PQHeapHandle PQhandle;
347 typedef struct PriorityQ PriorityQ; 347 typedef struct PriorityQ PriorityQ;
348 348
349 struct PriorityQ { 349 struct PriorityQ {
350 PriorityQHeap *heap; 350 PriorityQHeap *heap;
351 PQkey *keys; 351 PQkey *keys;
352 PQkey **order; 352 PQkey **order;
353 PQhandle size, max; 353 PQhandle size, max;
354 int initialized; 354 int initialized;
355 int (*leq)(PQkey key1, PQkey key2); 355 int (*leq)(PQkey key1, PQkey key2);
356 }; 356 };
357 357
358 /* really __gl_pqSortNewPriorityQ */ 358 /* really __gl_pqSortNewPriorityQ */
359 inline PriorityQ *pqNewPriorityQ( int (*leq)(P 359 inline PriorityQ *pqNewPriorityQ( int (*leq)(PQkey key1, PQkey key2) )
360 { 360 {
361 PriorityQ *pq = (PriorityQ *)memAlloc( sizeo 361 PriorityQ *pq = (PriorityQ *)memAlloc( sizeof( PriorityQ ));
362 if (pq == NULL) return NULL; 362 if (pq == NULL) return NULL;
363 363
364 pq->heap = __gl_pqHeapNewPriorityQ( leq ); 364 pq->heap = __gl_pqHeapNewPriorityQ( leq );
365 if (pq->heap == NULL) { 365 if (pq->heap == NULL) {
366 memFree(pq); 366 memFree(pq);
367 return NULL; 367 return NULL;
368 } 368 }
369 369
370 pq->keys = (PQHeapKey *)memAlloc( INIT_SIZE( 370 pq->keys = (PQHeapKey *)memAlloc( INIT_SIZE() * sizeof(pq->keys[0]) );
371 if (pq->keys == NULL) { 371 if (pq->keys == NULL) {
372 __gl_pqHeapDeletePriorityQ(pq->heap); 372 __gl_pqHeapDeletePriorityQ(pq->heap);
373 memFree(pq); 373 memFree(pq);
374 return NULL; 374 return NULL;
375 } 375 }
376 376
377 pq->size = 0; 377 pq->size = 0;
378 pq->max = INIT_SIZE(); 378 pq->max = INIT_SIZE();
379 pq->initialized = TOOLS_GLU_FALSE; 379 pq->initialized = TOOLS_GLU_FALSE;
380 pq->leq = leq; 380 pq->leq = leq;
381 return pq; 381 return pq;
382 } 382 }
383 383
384 /* really __gl_pqSortDeletePriorityQ */ 384 /* really __gl_pqSortDeletePriorityQ */
385 inline void pqDeletePriorityQ( PriorityQ *pq ) 385 inline void pqDeletePriorityQ( PriorityQ *pq )
386 { 386 {
387 assert(pq != NULL); 387 assert(pq != NULL);
388 if (pq->heap != NULL) __gl_pqHeapDeletePrior 388 if (pq->heap != NULL) __gl_pqHeapDeletePriorityQ( pq->heap );
389 if (pq->order != NULL) memFree( pq->order ); 389 if (pq->order != NULL) memFree( pq->order );
390 if (pq->keys != NULL) memFree( pq->keys ); 390 if (pq->keys != NULL) memFree( pq->keys );
391 memFree( pq ); 391 memFree( pq );
392 } 392 }
393 393
394 394
395 #define LT(x,y) (! LEQ(y,x)) 395 #define LT(x,y) (! LEQ(y,x))
396 #define GT(x,y) (! LEQ(x,y)) 396 #define GT(x,y) (! LEQ(x,y))
397 //#define pq_Swap(a,b) if(1){PQkey *tmp = *a; 397 //#define pq_Swap(a,b) if(1){PQkey *tmp = *a; *a = *b; *b = tmp;}else
398 #define pq_Swap(a,b) do{PQkey *tmp = *a; *a = 398 #define pq_Swap(a,b) do{PQkey *tmp = *a; *a = *b; *b = tmp;} while(false)
399 399
400 /* really __gl_pqSortInit */ 400 /* really __gl_pqSortInit */
401 inline int pqInit( PriorityQ *pq ) 401 inline int pqInit( PriorityQ *pq )
402 { 402 {
403 PQkey **p, **r, **i, **j, *piv; 403 PQkey **p, **r, **i, **j, *piv;
404 struct { PQkey **p, **r; } Stack[50], *top = 404 struct { PQkey **p, **r; } Stack[50], *top = Stack;
405 unsigned long seed = 2016473283; 405 unsigned long seed = 2016473283;
406 406
407 /* Create an array of indirect pointers to t 407 /* Create an array of indirect pointers to the keys, so that we
408 * the handles we have returned are still va 408 * the handles we have returned are still valid.
409 */ 409 */
410 /* 410 /*
411 pq->order = (PQHeapKey **)memAlloc( (size_t) 411 pq->order = (PQHeapKey **)memAlloc( (size_t)
412 (pq->size * 412 (pq->size * sizeof(pq->order[0])) );
413 */ 413 */
414 pq->order = (PQHeapKey **)memAlloc( (size_t) 414 pq->order = (PQHeapKey **)memAlloc( (size_t)
415 ((pq->size+1 415 ((pq->size+1) * sizeof(pq->order[0])) );
416 /* the previous line is a patch to compensate 416 /* the previous line is a patch to compensate for the fact that IBM */
417 /* machines return a null on a malloc of zero 417 /* machines return a null on a malloc of zero bytes (unlike SGI), */
418 /* so we have to put in this defense to guard 418 /* so we have to put in this defense to guard against a memory */
419 /* fault four lines down. from fossum@austin.i 419 /* fault four lines down. from fossum@austin.ibm.com. */
420 if (pq->order == NULL) return 0; 420 if (pq->order == NULL) return 0;
421 421
422 p = pq->order; 422 p = pq->order;
423 r = p + pq->size - 1; 423 r = p + pq->size - 1;
424 for( piv = pq->keys, i = p; i <= r; ++piv, + 424 for( piv = pq->keys, i = p; i <= r; ++piv, ++i ) {
425 *i = piv; 425 *i = piv;
426 } 426 }
427 427
428 /* Sort the indirect pointers in descending 428 /* Sort the indirect pointers in descending order,
429 * using randomized Quicksort 429 * using randomized Quicksort
430 */ 430 */
431 top->p = p; top->r = r; ++top; 431 top->p = p; top->r = r; ++top;
432 while( --top >= Stack ) { 432 while( --top >= Stack ) {
433 p = top->p; 433 p = top->p;
434 r = top->r; 434 r = top->r;
435 while( r > p + 10 ) { 435 while( r > p + 10 ) {
436 seed = seed * 1539415821 + 1; 436 seed = seed * 1539415821 + 1;
437 i = p + seed % (r - p + 1); 437 i = p + seed % (r - p + 1);
438 piv = *i; 438 piv = *i;
439 *i = *p; 439 *i = *p;
440 *p = piv; 440 *p = piv;
441 i = p - 1; 441 i = p - 1;
442 j = r + 1; 442 j = r + 1;
443 do { 443 do {
444 do { ++i; } while( GT( **i, *piv )); 444 do { ++i; } while( GT( **i, *piv ));
445 do { --j; } while( LT( **j, *piv )); 445 do { --j; } while( LT( **j, *piv ));
446 pq_Swap( i, j ); 446 pq_Swap( i, j );
447 } while( i < j ); 447 } while( i < j );
448 pq_Swap( i, j ); /* Undo last swap */ 448 pq_Swap( i, j ); /* Undo last swap */
449 if( i - p < r - j ) { 449 if( i - p < r - j ) {
450 top->p = j+1; top->r = r; ++top; 450 top->p = j+1; top->r = r; ++top;
451 r = i-1; 451 r = i-1;
452 } else { 452 } else {
453 top->p = p; top->r = i-1; ++top; 453 top->p = p; top->r = i-1; ++top;
454 p = j+1; 454 p = j+1;
455 } 455 }
456 } 456 }
457 /* Insertion sort small lists */ 457 /* Insertion sort small lists */
458 for( i = p+1; i <= r; ++i ) { 458 for( i = p+1; i <= r; ++i ) {
459 piv = *i; 459 piv = *i;
460 for( j = i; j > p && LT( **(j-1), *piv ) 460 for( j = i; j > p && LT( **(j-1), *piv ); --j ) {
461 *j = *(j-1); 461 *j = *(j-1);
462 } 462 }
463 *j = piv; 463 *j = piv;
464 } 464 }
465 } 465 }
466 pq->max = pq->size; 466 pq->max = pq->size;
467 pq->initialized = TOOLS_GLU_TRUE; 467 pq->initialized = TOOLS_GLU_TRUE;
468 __gl_pqHeapInit( pq->heap ); /* always succ 468 __gl_pqHeapInit( pq->heap ); /* always succeeds */
469 469
470 #ifndef NDEBUG 470 #ifndef NDEBUG
471 p = pq->order; 471 p = pq->order;
472 r = p + pq->size - 1; 472 r = p + pq->size - 1;
473 for( i = p; i < r; ++i ) { 473 for( i = p; i < r; ++i ) {
474 assert( LEQ( **(i+1), **i )); 474 assert( LEQ( **(i+1), **i ));
475 } 475 }
476 #endif 476 #endif
477 477
478 return 1; 478 return 1;
479 } 479 }
480 480
481 /* really __gl_pqSortInsert */ 481 /* really __gl_pqSortInsert */
482 /* returns LONG_MAX iff out of memory */ 482 /* returns LONG_MAX iff out of memory */
483 inline PQhandle pqInsert( PriorityQ *pq, PQkey 483 inline PQhandle pqInsert( PriorityQ *pq, PQkey keyNew )
484 { 484 {
485 long curr; 485 long curr;
486 486
487 if( pq->initialized ) { 487 if( pq->initialized ) {
488 return __gl_pqHeapInsert( pq->heap, keyNew 488 return __gl_pqHeapInsert( pq->heap, keyNew );
489 } 489 }
490 curr = pq->size; 490 curr = pq->size;
491 if( ++ pq->size >= pq->max ) { 491 if( ++ pq->size >= pq->max ) {
492 PQkey *saveKey= pq->keys; 492 PQkey *saveKey= pq->keys;
493 493
494 /* If the heap overflows, double its size. 494 /* If the heap overflows, double its size. */
495 pq->max <<= 1; 495 pq->max <<= 1;
496 pq->keys = (PQHeapKey *)memRealloc( pq->ke 496 pq->keys = (PQHeapKey *)memRealloc( pq->keys,
497 (size_t) 497 (size_t)
498 (pq->max * 498 (pq->max * sizeof( pq->keys[0] )));
499 if (pq->keys == NULL) { 499 if (pq->keys == NULL) {
500 pq->keys = saveKey; /* restore ptr to 500 pq->keys = saveKey; /* restore ptr to free upon return */
501 return LONG_MAX; 501 return LONG_MAX;
502 } 502 }
503 } 503 }
504 assert(curr != LONG_MAX); 504 assert(curr != LONG_MAX);
505 pq->keys[curr] = keyNew; 505 pq->keys[curr] = keyNew;
506 506
507 /* Negative handles index the sorted array. 507 /* Negative handles index the sorted array. */
508 return -(curr+1); 508 return -(curr+1);
509 } 509 }
510 510
511 /* really __gl_pqSortExtractMin */ 511 /* really __gl_pqSortExtractMin */
512 inline PQkey pqExtractMin( PriorityQ *pq ) 512 inline PQkey pqExtractMin( PriorityQ *pq )
513 { 513 {
514 PQkey sortMin, heapMin; 514 PQkey sortMin, heapMin;
515 515
516 if( pq->size == 0 ) { 516 if( pq->size == 0 ) {
517 return __gl_pqHeapExtractMin( pq->heap ); 517 return __gl_pqHeapExtractMin( pq->heap );
518 } 518 }
519 sortMin = *(pq->order[pq->size-1]); 519 sortMin = *(pq->order[pq->size-1]);
520 if( ! __gl_pqHeapIsEmpty( pq->heap )) { 520 if( ! __gl_pqHeapIsEmpty( pq->heap )) {
521 heapMin = __gl_pqHeapMinimum( pq->heap ); 521 heapMin = __gl_pqHeapMinimum( pq->heap );
522 if( LEQ( heapMin, sortMin )) { 522 if( LEQ( heapMin, sortMin )) {
523 return __gl_pqHeapExtractMin( pq->heap ) 523 return __gl_pqHeapExtractMin( pq->heap );
524 } 524 }
525 } 525 }
526 do { 526 do {
527 -- pq->size; 527 -- pq->size;
528 } while( pq->size > 0 && *(pq->order[pq->siz 528 } while( pq->size > 0 && *(pq->order[pq->size-1]) == NULL );
529 return sortMin; 529 return sortMin;
530 } 530 }
531 531
532 /* really __gl_pqSortMinimum */ 532 /* really __gl_pqSortMinimum */
533 inline PQkey pqMinimum( PriorityQ *pq ) 533 inline PQkey pqMinimum( PriorityQ *pq )
534 { 534 {
535 PQkey sortMin, heapMin; 535 PQkey sortMin, heapMin;
536 536
537 if( pq->size == 0 ) { 537 if( pq->size == 0 ) {
538 return __gl_pqHeapMinimum( pq->heap ); 538 return __gl_pqHeapMinimum( pq->heap );
539 } 539 }
540 sortMin = *(pq->order[pq->size-1]); 540 sortMin = *(pq->order[pq->size-1]);
541 if( ! __gl_pqHeapIsEmpty( pq->heap )) { 541 if( ! __gl_pqHeapIsEmpty( pq->heap )) {
542 heapMin = __gl_pqHeapMinimum( pq->heap ); 542 heapMin = __gl_pqHeapMinimum( pq->heap );
543 if( LEQ( heapMin, sortMin )) { 543 if( LEQ( heapMin, sortMin )) {
544 return heapMin; 544 return heapMin;
545 } 545 }
546 } 546 }
547 return sortMin; 547 return sortMin;
548 } 548 }
549 549
550 /* really __gl_pqSortIsEmpty */ 550 /* really __gl_pqSortIsEmpty */
551 inline int pqIsEmpty( PriorityQ *pq ) 551 inline int pqIsEmpty( PriorityQ *pq )
552 { 552 {
553 return (pq->size == 0) && __gl_pqHeapIsEmpty 553 return (pq->size == 0) && __gl_pqHeapIsEmpty( pq->heap );
554 } 554 }
555 555
556 /* really __gl_pqSortDelete */ 556 /* really __gl_pqSortDelete */
557 inline void pqDelete( PriorityQ *pq, PQhandle 557 inline void pqDelete( PriorityQ *pq, PQhandle curr )
558 { 558 {
559 if( curr >= 0 ) { 559 if( curr >= 0 ) {
560 __gl_pqHeapDelete( pq->heap, curr ); 560 __gl_pqHeapDelete( pq->heap, curr );
561 return; 561 return;
562 } 562 }
563 curr = -(curr+1); 563 curr = -(curr+1);
564 assert( curr < pq->max && pq->keys[curr] != 564 assert( curr < pq->max && pq->keys[curr] != NULL );
565 565
566 pq->keys[curr] = NULL; 566 pq->keys[curr] = NULL;
567 while( pq->size > 0 && *(pq->order[pq->size- 567 while( pq->size > 0 && *(pq->order[pq->size-1]) == NULL ) {
568 -- pq->size; 568 -- pq->size;
569 } 569 }
570 } 570 }
571 571
572 #endif 572 #endif