cutil/oldheap.cpp

Go to the documentation of this file.
00001 
00019 /* =================
00020           Include Files and Type Defines
00021  ==================== */
00022 #include "oldheap.h"
00023 #include "freelist.h"
00024 #include "danerror.h"
00025 #include "emalloc.h"
00026 #include <stdio.h>
00027 
00028 #define FATHER(N) ((N)>>1)
00029 #define LEFTSON(N)  ((N)<<1)
00030 #define RIGHTSON(N) ((N)<<1 + 1)
00031 
00032 /* =================
00033     Public Code
00034  ==================== */
00035 /* =============================== */
00048 HEAP *MakeHeap(int Size) { 
00049   HEAP *NewHeap;
00050 
00051   NewHeap = (HEAP *) Emalloc (sizeof (HEAP) + Size * sizeof (HEAPENTRY));
00052 
00053   NewHeap->Size = Size;
00054   NewHeap->FirstFree = 1;
00055   return (NewHeap);
00056 }                                /* MakeHeap */
00057 
00058 
00059 /* =============================== */
00071 int HeapPop(HEAP *Heap, FLOAT32 *Key, void *out_ptr) { 
00072   INT32 Hole;
00073   FLOAT32 HoleKey;
00074   INT32 Son;
00075   void **Data = (void **) out_ptr;
00076 
00077   if (Heap->FirstFree <= 1)
00078     return (EMPTY);
00079 
00080   *Key = Heap->Entry[1].Key;
00081   *Data = Heap->Entry[1].Data;
00082 
00083   Heap->FirstFree--;
00084 
00085   /* imagine the hole at the root is filled with the last entry in the heap */
00086   HoleKey = Heap->Entry[Heap->FirstFree].Key;
00087   Hole = 1;
00088 
00089                                  /* while hole has 2 sons */
00090   while ((Son = LEFTSON (Hole)) < Heap->FirstFree) {
00091     /* find the son with the smallest key */
00092     if (Heap->Entry[Son].Key > Heap->Entry[Son + 1].Key)
00093       Son++;
00094 
00095     /* if key for hole is greater than key for son, sift hole down */
00096     if (HoleKey > Heap->Entry[Son].Key) {
00097       Heap->Entry[Hole].Key = Heap->Entry[Son].Key;
00098       Heap->Entry[Hole].Data = Heap->Entry[Son].Data;
00099       Hole = Son;
00100     }
00101     else
00102       break;
00103   }
00104   Heap->Entry[Hole].Key = HoleKey;
00105   Heap->Entry[Hole].Data = Heap->Entry[Heap->FirstFree].Data;
00106   return (OK);
00107 }                                /* HeapPop */
00108 
00109 
00110 /* =============================== */
00119 int HeapPopWorst(HEAP *Heap, FLOAT32 *Key, void *out_ptr) { 
00120   INT32 Index;                   /*current index */
00121   INT32 Hole;
00122   FLOAT32 HoleKey;
00123   INT32 Father;
00124   void *HoleData;
00125   void **Data = (void **) out_ptr;
00126 
00127   if (Heap->FirstFree <= 1)
00128     return (EMPTY);
00129 
00130   HoleKey = Heap->Entry[1].Key;
00131   Hole = 1;
00132   Heap->FirstFree--;
00133   for (Index = Heap->FirstFree, Father = FATHER (Index); Index > Father;
00134     Index--)
00135   if (Heap->Entry[Index].Key > HoleKey) {
00136                                  /*find biggest */
00137     HoleKey = Heap->Entry[Index].Key;
00138     Hole = Index;
00139   }
00140   *Key = HoleKey;
00141   *Data = Heap->Entry[Hole].Data;
00142 
00143   HoleKey = Heap->Entry[Heap->FirstFree].Key;
00144   Heap->Entry[Hole].Key = HoleKey;
00145   HoleData = Heap->Entry[Heap->FirstFree].Data;
00146   Heap->Entry[Hole].Data = HoleData;
00147 
00148   /* now sift last entry to its rightful place */
00149   Father = FATHER (Hole);        /*father of hole */
00150   while (Hole > 1 && Heap->Entry[Father].Key > HoleKey) {
00151                                  /*swap entries */
00152     Heap->Entry[Hole].Key = Heap->Entry[Father].Key;
00153     Heap->Entry[Hole].Data = Heap->Entry[Father].Data;
00154     Heap->Entry[Father].Data = HoleData;
00155     Heap->Entry[Father].Key = HoleKey;
00156     Hole = Father;
00157     Father = FATHER (Hole);
00158   }
00159   return (OK);
00160 }                                /* HeapPop */
00161 
00162 
00163 /* =============================== */
00177 void HeapPush(HEAP *Heap, FLOAT32 Key, void *Data) { 
00178   INT32 Item;
00179   INT32 Father;
00180 
00181   if (Heap->FirstFree > Heap->Size)
00182     DoError (HEAPFULL, "Heap size exceeded");
00183 
00184   Item = Heap->FirstFree;
00185   Heap->FirstFree++;
00186   while (Item != 1) {
00187     Father = FATHER (Item);
00188     if (Heap->Entry[Father].Key > Key) {
00189       Heap->Entry[Item].Key = Heap->Entry[Father].Key;
00190       Heap->Entry[Item].Data = Heap->Entry[Father].Data;
00191       Item = Father;
00192     }
00193     else
00194       break;
00195   }
00196   Heap->Entry[Item].Key = Key;
00197   Heap->Entry[Item].Data = Data;
00198 }                                /* HeapPush */
00199 
00200 
00201 /* =============================== */
00214 void HeapStore(HEAP *Heap, HEAPENTRY *Entry) { 
00215   INT32 Item;
00216   INT32 Father;
00217 
00218   if (Heap->FirstFree > Heap->Size)
00219     DoError (HEAPFULL, "Heap size exceeded");
00220 
00221   Item = Heap->FirstFree;
00222   Heap->FirstFree++;
00223   while (Item != 1) {
00224     Father = FATHER (Item);
00225     if (Heap->Entry[Father].Key > Entry->Key) {
00226       Heap->Entry[Item].Key = Heap->Entry[Father].Key;
00227       Heap->Entry[Item].Data = Heap->Entry[Father].Data;
00228       Item = Father;
00229     }
00230     else
00231       break;
00232   }
00233   Heap->Entry[Item].Key = Entry->Key;
00234   Heap->Entry[Item].Data = Entry->Data;
00235 }                                /* HeapStore */
00236 
00237 
00238 /* =============================== */
00248 int GetTopOfHeap(HEAP *Heap, HEAPENTRY *Entry) { 
00249   INT32 Hole;
00250   FLOAT32 HoleKey;
00251   INT32 Son;
00252 
00253   if (Heap->FirstFree <= 1)
00254     return (EMPTY);
00255 
00256   Entry->Key = Heap->Entry[1].Key;
00257   Entry->Data = Heap->Entry[1].Data;
00258 
00259   Heap->FirstFree--;
00260 
00261   /* imagine the hole at the root is filled with the last entry in the heap */
00262   HoleKey = Heap->Entry[Heap->FirstFree].Key;
00263   Hole = 1;
00264 
00265                                  /* while hole has 2 sons */
00266   while ((Son = LEFTSON (Hole)) < Heap->FirstFree) {
00267     /* find the son with the smallest key */
00268     if (Heap->Entry[Son].Key > Heap->Entry[Son + 1].Key)
00269       Son++;
00270 
00271     /* if key for hole is greater than key for son, sift hole down */
00272     if (HoleKey > Heap->Entry[Son].Key) {
00273       Heap->Entry[Hole].Key = Heap->Entry[Son].Key;
00274       Heap->Entry[Hole].Data = Heap->Entry[Son].Data;
00275       Hole = Son;
00276     }
00277     else
00278       break;
00279   }
00280   Heap->Entry[Hole].Key = HoleKey;
00281   Heap->Entry[Hole].Data = Heap->Entry[Heap->FirstFree].Data;
00282   return (OK);
00283 }                                /* GetTopOfHeap */
00284 
00285 
00286 /* =============================== */
00298 void FreeHeapData(HEAP *Heap, void_dest destructor) { 
00299   HEAPENTRY Entry;
00300 
00301   while (GetTopOfHeap (Heap, &Entry) != EMPTY)
00302     destructor (Entry.Data);
00303 
00304   FreeHeap(Heap); 
00305 }                                /* FreeHeapData */

Generated on Wed Feb 28 19:49:10 2007 for Tesseract by  doxygen 1.5.1