Geant4 Cross Reference |
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-b 10 11 ////////////////////////////////////////////// 12 //#include "priorityq-heap.ic" 13 //#include "priorityq-heap" 14 15 /* Use #define's so that another heap implemen 16 17 #define PQkey PQHeapKey 18 #define PQhandle PQHeapHandle 19 #define PriorityQ PriorityQHeap 20 21 #define pqNewPriorityQ(leq) __gl_pqHeapNewPrio 22 #define pqDeletePriorityQ(pq) __gl_pqHeapDelet 23 24 /* The basic operations are insertion of a new 25 * and examination/extraction of a key whose v 26 * (pqMinimum/pqExtractMin). Deletion is also 27 * for this purpose pqInsert returns a "handle 28 * as the argument. 29 * 30 * An initial heap may be created efficiently 31 * repeatedly, then calling pqInit. In any ca 32 * before any operations other than pqInsert a 33 * 34 * If the heap is empty, pqMinimum/pqExtractMi 35 * This may also be tested with pqIsEmpty. 36 */ 37 #define pqInit(pq) __gl_pqHeapInit(pq) 38 #define pqInsert(pq,key) __gl_pqHeapInsert(pq 39 #define pqMinimum(pq) __gl_pqHeapMinimum(pq) 40 #define pqExtractMin(pq) __gl_pqHeapExtractMi 41 #define pqDelete(pq,handle) __gl_pqHeapDelete( 42 #define pqIsEmpty(pq) __gl_pqHeapIsEmpty(pq) 43 44 /* Since we support deletion the data structur 45 * complicated than an ordinary heap. "nodes" 46 * active nodes are stored in the range 1..pq- 47 * heap exceeds its allocated size (pq->max), 48 * The children of node i are nodes 2i and 2i+ 49 * 50 * Each node stores an index into an array "ha 51 * stores a key, plus a pointer back to the no 52 * represents that key (ie. nodes[handles[i].n 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; } P 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 72 #define __gl_pqHeapIsEmpty(pq) ((pq)->size == 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, (GLU 85 86 /* really __gl_pqHeapNewPriorityQ */ 87 inline PriorityQ *pqNewPriorityQ( int (*leq)(P 88 { 89 PriorityQ *pq = (PriorityQ *)memAlloc( sizeo 90 if (pq == NULL) return NULL; 91 92 pq->size = 0; 93 pq->max = INIT_SIZE(); 94 pq->nodes = (PQnode *)memAlloc( (INIT_SIZE() 95 if (pq->nodes == NULL) { 96 memFree(pq); 97 return NULL; 98 } 99 100 pq->handles = (PQhandleElem *)memAlloc( (INI 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 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( Priori 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]. 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, 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( Priority 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[ 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), r 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 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->node 205 (size_t) 206 ((pq->max + 1) * sizeof( pq->node 207 if (pq->nodes == NULL) { 208 pq->nodes = saveNodes; /* restore ptr t 209 return LONG_MAX; 210 } 211 pq->handles = (PQhandleElem *)memRealloc( 212 (size_t) 213 ((pq->max + 1) * 214 sizeof( pq->handles[0] ))); 215 if (pq->handles == NULL) { 216 pq->handles = saveHandles; /* restore p 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 264 { 265 PQnode *n = pq->nodes; 266 PQhandleElem *h = pq->handles; 267 long curr; 268 269 assert( hCurr >= 1 && hCurr <= pq->max && h[ 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] 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 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 implemen 305 306 #define PQkey PQSortKey 307 #define PQhandle PQSortHandle 308 #define PriorityQ PriorityQSort 309 310 #define pqNewPriorityQ(leq) __gl_pqSortNewPrio 311 #define pqDeletePriorityQ(pq) __gl_pqSortDelet 312 313 /* The basic operations are insertion of a new 314 * and examination/extraction of a key whose v 315 * (pqMinimum/pqExtractMin). Deletion is also 316 * for this purpose pqInsert returns a "handle 317 * as the argument. 318 * 319 * An initial heap may be created efficiently 320 * repeatedly, then calling pqInit. In any ca 321 * before any operations other than pqInsert a 322 * 323 * If the heap is empty, pqMinimum/pqExtractMi 324 * This may also be tested with pqIsEmpty. 325 */ 326 #define pqInit(pq) __gl_pqSortInit(pq) 327 #define pqInsert(pq,key) __gl_pqSortInsert(pq 328 #define pqMinimum(pq) __gl_pqSortMinimum(pq) 329 #define pqExtractMin(pq) __gl_pqSortExtractMi 330 #define pqDelete(pq,handle) __gl_pqSortDelete( 331 #define pqIsEmpty(pq) __gl_pqSortIsEmpty(pq) 332 333 334 /* Since we support deletion the data structur 335 * complicated than an ordinary heap. "nodes" 336 * active nodes are stored in the range 1..pq- 337 * heap exceeds its allocated size (pq->max), 338 * The children of node i are nodes 2i and 2i+ 339 * 340 * Each node stores an index into an array "ha 341 * stores a key, plus a pointer back to the no 342 * represents that key (ie. nodes[handles[i].n 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)(P 360 { 361 PriorityQ *pq = (PriorityQ *)memAlloc( sizeo 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( 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_pqHeapDeletePrior 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; 398 #define pq_Swap(a,b) do{PQkey *tmp = *a; *a = 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 = 405 unsigned long seed = 2016473283; 406 407 /* Create an array of indirect pointers to t 408 * the handles we have returned are still va 409 */ 410 /* 411 pq->order = (PQHeapKey **)memAlloc( (size_t) 412 (pq->size * 413 */ 414 pq->order = (PQHeapKey **)memAlloc( (size_t) 415 ((pq->size+1 416 /* the previous line is a patch to compensate 417 /* machines return a null on a malloc of zero 418 /* so we have to put in this defense to guard 419 /* fault four lines down. from fossum@austin.i 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, + 425 *i = piv; 426 } 427 428 /* Sort the indirect pointers in descending 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 ) 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 succ 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 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->ke 497 (size_t) 498 (pq->max * 499 if (pq->keys == NULL) { 500 pq->keys = saveKey; /* restore ptr to 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->siz 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 554 } 555 556 /* really __gl_pqSortDelete */ 557 inline void pqDelete( PriorityQ *pq, PQhandle 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] != 565 566 pq->keys[curr] = NULL; 567 while( pq->size > 0 && *(pq->order[pq->size- 568 -- pq->size; 569 } 570 } 571 572 #endif