glu-2.2: src/heap/heap.c Source File

00001 
00023 #include "heapInt.h"
00024 
00025 
00026 /*---------------------------------------------------------------------------*/
00027 /* Constant declarations                                                     */
00028 /*---------------------------------------------------------------------------*/
00029 
00030 
00031 /*---------------------------------------------------------------------------*/
00032 /* Stucture declarations                                                     */
00033 /*---------------------------------------------------------------------------*/
00034 
00035 
00036 /*---------------------------------------------------------------------------*/
00037 /* Type declarations                                                         */
00038 /*---------------------------------------------------------------------------*/
00039 
00040 
00041 /*---------------------------------------------------------------------------*/
00042 /* Variable declarations                                                     */
00043 /*---------------------------------------------------------------------------*/
00044 
00045 #ifndef lint
00046 static char rcsid[] UNUSED = "$Id: heap.c,v 1.18 2005/05/18 19:25:43 jinh Exp $";
00047 #endif
00048 
00049 
00050 /*---------------------------------------------------------------------------*/
00051 /* Macro declarations                                                        */
00052 /*---------------------------------------------------------------------------*/
00053 
00054 
00055 
00058 /*---------------------------------------------------------------------------*/
00059 /* Static function prototypes                                                */
00060 /*---------------------------------------------------------------------------*/
00061 
00062 static void HeapHeapify ARGS((Heap_t *heap));
00063 static void HeapHeapifyCompare ARGS((Heap_t *heap));
00064 static int HeapResize ARGS((Heap_t *heap));
00065 
00069 /*---------------------------------------------------------------------------*/
00070 /* Definition of exported functions                                          */
00071 /*---------------------------------------------------------------------------*/
00072 
00073 
00088 Heap_t *
00089 Heap_HeapInit(
00090   int length)
00091 {
00092   Heap_t *heap;
00093 
00094   heap = ALLOC(Heap_t, 1);
00095   if (heap == NIL(Heap_t)) return NIL(Heap_t);
00096   heap->length = length;
00097   heap->nitems = 0;
00098   heap->compare = 0;
00099   heap->slots = ALLOC(HeapSlot_t, length);
00100   if (heap->slots == NIL(HeapSlot_t)) {
00101     FREE(heap);
00102     return NIL(Heap_t);
00103   }
00104   return heap;
00105 
00106 } /* Heap_HeapInit */
00107 
00108 
00123 Heap_t *
00124 Heap_HeapInitCompare(
00125   int length, int (*compare)(const void *, const void *))
00126 {
00127   Heap_t *heap;
00128 
00129   heap = ALLOC(Heap_t, 1);
00130   if (heap == NIL(Heap_t)) return NIL(Heap_t);
00131   heap->length = length;
00132   heap->nitems = 0;
00133   heap->compare = compare;
00134   heap->slots = ALLOC(HeapSlot_t, length);
00135   if (heap->slots == NIL(HeapSlot_t)) {
00136     FREE(heap);
00137     return NIL(Heap_t);
00138   }
00139   return heap;
00140 
00141 } /* Heap_HeapInitCompare */
00142 
00143 
00155 void
00156 Heap_HeapFree(
00157   Heap_t *heap)
00158 {
00159   FREE(heap->slots);
00160   FREE(heap);
00161   return;
00162 
00163 } /* Heap_HeapFree */
00164 
00165 
00178 int
00179 Heap_HeapInsert(
00180   Heap_t *heap,
00181   void *item,
00182   long key)
00183 {
00184   HeapSlot_t *slots;
00185   int i = heap->nitems;
00186 
00187   if (i == heap->length && !HeapResize(heap)) return 0;
00188   slots = heap->slots;
00189   heap->nitems++;
00190   while (i > 0 && KEY(slots, PARENT(i)) > key) {
00191     ITEM(slots, i) = ITEM(slots, PARENT(i));
00192     KEY(slots, i) = KEY(slots, PARENT(i));
00193     i = PARENT(i);
00194   }
00195   ITEM(slots, i) = item;
00196   KEY(slots, i) = key;
00197   return 1;
00198 
00199 } /* Heap_HeapInsert */
00200 
00213 int
00214 Heap_HeapInsertCompare(
00215   Heap_t *heap,
00216   void *item,
00217   long key)
00218 {
00219   HeapSlot_t *slots;
00220   int i = heap->nitems;
00221 
00222   if (i == heap->length && !HeapResize(heap)) return 0;
00223   slots = heap->slots;
00224   heap->nitems++;
00225   while (i > 0 && (*(heap->compare))((char *)(long)KEY(slots, PARENT(i)), (char *)(long)key)) {
00226     ITEM(slots, i) = ITEM(slots, PARENT(i));
00227     KEY(slots, i) = KEY(slots, PARENT(i));
00228     i = PARENT(i);
00229   }
00230   ITEM(slots, i) = item;
00231   KEY(slots, i) = key;
00232   return 1;
00233 
00234 } /* Heap_HeapInsertCompare */
00235 
00236 
00237 
00252 int
00253 Heap_HeapExtractMin(
00254   Heap_t *heap,
00255   void *item,
00256   long *key)
00257 {
00258   HeapSlot_t *slots = heap->slots;
00259 
00260   if (heap->nitems == 0) return 0;
00261   *(void **)item = ITEM(slots, 0);
00262   *key = KEY(slots, 0);
00263   heap->nitems--;
00264   /* The next three lines are redundant if the queue is empty. */
00265   ITEM(slots, 0) = ITEM(slots, heap->nitems);
00266   KEY(slots, 0) = KEY(slots, heap->nitems);
00267   if(heap->compare) HeapHeapifyCompare(heap);
00268   else              HeapHeapify(heap);
00269 
00270   return 1;
00271 
00272 } /* Heap_HeapExtractMin */
00273 
00274 
00286 int
00287 Heap_HeapCount(
00288   Heap_t *heap)
00289 {
00290   return(heap->nitems);
00291 
00292 } /* Heap_HeapCount */
00293 
00294 
00306 Heap_t *
00307 Heap_HeapClone(
00308   Heap_t *source)
00309 {
00310   Heap_t *dest;
00311   int i;
00312   int nitems = source->nitems;
00313   HeapSlot_t *sslots = source->slots;
00314   HeapSlot_t *dslots;
00315 
00316   dest = Heap_HeapInit(source->length);
00317   if (dest == NULL) return(NULL);
00318   dest->nitems = nitems;
00319   dslots = dest->slots;
00320   for (i = 0; i < nitems; i++) {
00321     KEY(dslots, i) = KEY(sslots, i);
00322     ITEM(dslots, i) = ITEM(sslots, i);
00323   }
00324   return(dest);
00325 
00326 } /* Heap_HeapClone */
00327 
00328 
00341 int
00342 Heap_HeapTest(
00343   Heap_t *heap)
00344 {
00345   HeapSlot_t *slots = heap->slots;
00346   int nitems = heap->nitems;
00347   int i;
00348 
00349   for (i = 1; i < nitems; i++) {
00350     if (KEY(slots,i) < KEY(slots, PARENT(i)))
00351       return 0;
00352   }
00353   return 1;
00354 
00355 } /* Heap_HeapTest */
00356 
00369 int
00370 Heap_HeapTestCompare(
00371   Heap_t *heap)
00372 {
00373   HeapSlot_t *slots = heap->slots;
00374   int nitems = heap->nitems;
00375   int i;
00376 
00377   for (i = 1; i < nitems; i++) {
00378     if ((*(heap->compare))((char *)(long)KEY(slots, PARENT(i)), (char *)(long)KEY(slots,i)))
00379       return 0;
00380   }
00381   return 1;
00382 
00383 } /* Heap_HeapTest */
00384 
00385 
00386 
00387 
00388 /*---------------------------------------------------------------------------*/
00389 /* Definition of internal functions                                          */
00390 /*---------------------------------------------------------------------------*/
00391 
00392 
00393 /*---------------------------------------------------------------------------*/
00394 /* Definition of static functions                                            */
00395 /*---------------------------------------------------------------------------*/
00396 
00397 
00409 static void
00410 HeapHeapify(
00411   Heap_t *heap)
00412 {
00413   int nitems = heap->nitems;
00414   HeapSlot_t *slots = heap->slots;
00415   int i = 0;
00416   int smallest = 0;
00417   void *item = ITEM(slots, 0);
00418   long key = KEY(slots, 0);
00419 
00420   while (1) {
00421     int left = LEFT(i);
00422     int right = RIGHT(i);
00423     int minkey;
00424     if (left < nitems && (minkey = KEY(slots, left)) < key) {
00425       smallest = left;
00426     } else {
00427       minkey = key;
00428     }
00429     if (right < nitems && KEY(slots, right) < minkey) {
00430       smallest = right;
00431     }
00432     if (smallest == i) break;
00433     KEY(slots, i) = KEY(slots, smallest);
00434     ITEM(slots, i) = ITEM(slots, smallest);
00435     i = smallest;
00436   }
00437   KEY(slots, i) = key;
00438   ITEM(slots, i) = item;
00439   return;
00440 
00441 } /* HeapHeapify */
00442 
00455 static void
00456 HeapHeapifyCompare(
00457   Heap_t *heap)
00458 {
00459   int nitems = heap->nitems;
00460   HeapSlot_t *slots = heap->slots;
00461   int i = 0;
00462   int smallest = 0;
00463   void *item = ITEM(slots, 0);
00464   int key = KEY(slots, 0);
00465   int minkey;
00466 
00467 
00468   while (1) {
00469     int left = LEFT(i);
00470     int right = RIGHT(i);
00471     if (left < nitems && (*(heap->compare))((char *)(long)key, (char *)(long)(minkey = KEY(slots, left)))) {
00472       smallest = left;
00473     } else {
00474       minkey = key;
00475     }
00476     if (right < nitems && (*(heap->compare))((char *)(long)minkey, (char *)(long)KEY(slots, right))) {
00477       smallest = right;
00478     }
00479     if (smallest == i) break;
00480     KEY(slots, i) = KEY(slots, smallest);
00481     ITEM(slots, i) = ITEM(slots, smallest);
00482     i = smallest;
00483   }
00484   KEY(slots, i) = key;
00485   ITEM(slots, i) = item;
00486   return;
00487 
00488 } /* HeapHeapifyCompare */
00489 
00490 
00503 static int
00504 HeapResize(
00505   Heap_t *heap)
00506 {
00507   int oldlength = heap->length;
00508   int newlength = 2 * oldlength;
00509   HeapSlot_t *oldslots = heap->slots;
00510   HeapSlot_t *newslots = REALLOC(HeapSlot_t, oldslots, newlength);
00511   if (newslots == NIL(HeapSlot_t)) return 0;
00512   heap->length = newlength;
00513   heap->slots = newslots;
00514   if (heap->compare) {
00515     assert(Heap_HeapTestCompare(heap));
00516   }
00517   else {
00518     assert(Heap_HeapTest(heap));
00519   }
00520   return 1;
00521 
00522 } /* HeapResize */
00523 
00536 void
00537 Heap_HeapApplyForEachElement(Heap_t *heap, int (*compare)(const void *))
00538 {
00539 int i;
00540 
00541   for(i=0; i<heap->nitems; i++) {
00542     (*compare)(heap->slots[i].item);
00543   }
00544   return;
00545 }