Geant4 Cross Reference

Cross-Referencing   Geant4
Geant4/externals/g4tools/include/tools/glutess/priorityq

Version: [ ReleaseNotes ] [ 1.0 ] [ 1.1 ] [ 2.0 ] [ 3.0 ] [ 3.1 ] [ 3.2 ] [ 4.0 ] [ 4.0.p1 ] [ 4.0.p2 ] [ 4.1 ] [ 4.1.p1 ] [ 5.0 ] [ 5.0.p1 ] [ 5.1 ] [ 5.1.p1 ] [ 5.2 ] [ 5.2.p1 ] [ 5.2.p2 ] [ 6.0 ] [ 6.0.p1 ] [ 6.1 ] [ 6.2 ] [ 6.2.p1 ] [ 6.2.p2 ] [ 7.0 ] [ 7.0.p1 ] [ 7.1 ] [ 7.1.p1 ] [ 8.0 ] [ 8.0.p1 ] [ 8.1 ] [ 8.1.p1 ] [ 8.1.p2 ] [ 8.2 ] [ 8.2.p1 ] [ 8.3 ] [ 8.3.p1 ] [ 8.3.p2 ] [ 9.0 ] [ 9.0.p1 ] [ 9.0.p2 ] [ 9.1 ] [ 9.1.p1 ] [ 9.1.p2 ] [ 9.1.p3 ] [ 9.2 ] [ 9.2.p1 ] [ 9.2.p2 ] [ 9.2.p3 ] [ 9.2.p4 ] [ 9.3 ] [ 9.3.p1 ] [ 9.3.p2 ] [ 9.4 ] [ 9.4.p1 ] [ 9.4.p2 ] [ 9.4.p3 ] [ 9.4.p4 ] [ 9.5 ] [ 9.5.p1 ] [ 9.5.p2 ] [ 9.6 ] [ 9.6.p1 ] [ 9.6.p2 ] [ 9.6.p3 ] [ 9.6.p4 ] [ 10.0 ] [ 10.0.p1 ] [ 10.0.p2 ] [ 10.0.p3 ] [ 10.0.p4 ] [ 10.1 ] [ 10.1.p1 ] [ 10.1.p2 ] [ 10.1.p3 ] [ 10.2 ] [ 10.2.p1 ] [ 10.2.p2 ] [ 10.2.p3 ] [ 10.3 ] [ 10.3.p1 ] [ 10.3.p2 ] [ 10.3.p3 ] [ 10.4 ] [ 10.4.p1 ] [ 10.4.p2 ] [ 10.4.p3 ] [ 10.5 ] [ 10.5.p1 ] [ 10.6 ] [ 10.6.p1 ] [ 10.6.p2 ] [ 10.6.p3 ] [ 10.7 ] [ 10.7.p1 ] [ 10.7.p2 ] [ 10.7.p3 ] [ 10.7.p4 ] [ 11.0 ] [ 11.0.p1 ] [ 11.0.p2 ] [ 11.0.p3, ] [ 11.0.p4 ] [ 11.1 ] [ 11.1.1 ] [ 11.1.2 ] [ 11.1.3 ] [ 11.2 ] [ 11.2.1 ] [ 11.2.2 ] [ 11.3.0 ]

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