Tesseract  3.02
tesseract-ocr/cutil/oldheap.cpp
Go to the documentation of this file.
00001 /******************************************************************************
00002  **     Filename:       heap.c
00003  **     Purpose:        Routines for managing heaps (smallest at root)
00004  **     Author:         Dan Johnson
00005  **     History:        3/13/89, DSJ, Created.
00006  **
00007  **     (c) Copyright Hewlett-Packard Company, 1988.
00008  ** Licensed under the Apache License, Version 2.0 (the "License");
00009  ** you may not use this file except in compliance with the License.
00010  ** You may obtain a copy of the License at
00011  ** http://www.apache.org/licenses/LICENSE-2.0
00012  ** Unless required by applicable law or agreed to in writing, software
00013  ** distributed under the License is distributed on an "AS IS" BASIS,
00014  ** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
00015  ** See the License for the specific language governing permissions and
00016  ** limitations under the License.
00017  ******************************************************************************/
00018 /*-----------------------------------------------------------------------------
00019           Include Files and Type Defines
00020 -----------------------------------------------------------------------------*/
00021 #include "oldheap.h"
00022 #include "freelist.h"
00023 #include "danerror.h"
00024 #include "emalloc.h"
00025 #include <stdio.h>
00026 
00027 #define FATHER(N) ((N)>>1)
00028 #define LEFTSON(N)  ((N)<<1)
00029 #define RIGHTSON(N) ((N)<<1 + 1)
00030 
00031 /*-----------------------------------------------------------------------------
00032               Public Code
00033 -----------------------------------------------------------------------------*/
00034 /*---------------------------------------------------------------------------*/
00049 HEAP *MakeHeap(int Size) {
00050   HEAP *NewHeap;
00051 
00052   NewHeap = (HEAP *) Emalloc (sizeof (HEAP) + Size * sizeof (HEAPENTRY));
00053 
00054   NewHeap->Size = Size;
00055   NewHeap->FirstFree = 1;
00056   return (NewHeap);
00057 }                                /* MakeHeap */
00058 
00059 
00060 /*---------------------------------------------------------------------------*/
00076 int HeapPop(HEAP *Heap, FLOAT32 *Key, void *out_ptr) {
00077   inT32 Hole;
00078   FLOAT32 HoleKey;
00079   inT32 Son;
00080   void **Data = (void **) out_ptr;
00081 
00082   if (Heap->FirstFree <= 1)
00083     return (EMPTY);
00084 
00085   *Key = Heap->Entry[1].Key;
00086   *Data = Heap->Entry[1].Data;
00087 
00088   Heap->FirstFree--;
00089 
00090   /* imagine the hole at the root is filled with the last entry in the heap */
00091   HoleKey = Heap->Entry[Heap->FirstFree].Key;
00092   Hole = 1;
00093 
00094                                  /* while hole has 2 sons */
00095   while ((Son = LEFTSON (Hole)) < Heap->FirstFree) {
00096     /* find the son with the smallest key */
00097     if (Heap->Entry[Son].Key > Heap->Entry[Son + 1].Key)
00098       Son++;
00099 
00100     /* if key for hole is greater than key for son, sift hole down */
00101     if (HoleKey > Heap->Entry[Son].Key) {
00102       Heap->Entry[Hole].Key = Heap->Entry[Son].Key;
00103       Heap->Entry[Hole].Data = Heap->Entry[Son].Data;
00104       Hole = Son;
00105     }
00106     else
00107       break;
00108   }
00109   Heap->Entry[Hole].Key = HoleKey;
00110   Heap->Entry[Hole].Data = Heap->Entry[Heap->FirstFree].Data;
00111   return (TESS_HEAP_OK);
00112 }                                /* HeapPop */
00113 
00114 
00124 int HeapPopWorst(HEAP *Heap, FLOAT32 *Key, void *out_ptr) {
00125   inT32 Index;                   /*current index */
00126   inT32 Hole;
00127   FLOAT32 HoleKey;
00128   inT32 Father;
00129   void *HoleData;
00130   void **Data = (void **) out_ptr;
00131 
00132   if (Heap->FirstFree <= 1)
00133     return (EMPTY);
00134 
00135   HoleKey = Heap->Entry[1].Key;
00136   Hole = 1;
00137   Heap->FirstFree--;
00138   for (Index = Heap->FirstFree, Father = FATHER (Index); Index > Father;
00139     Index--)
00140   if (Heap->Entry[Index].Key > HoleKey) {
00141                                  /*find biggest */
00142     HoleKey = Heap->Entry[Index].Key;
00143     Hole = Index;
00144   }
00145   *Key = HoleKey;
00146   *Data = Heap->Entry[Hole].Data;
00147 
00148   HoleKey = Heap->Entry[Heap->FirstFree].Key;
00149   Heap->Entry[Hole].Key = HoleKey;
00150   HoleData = Heap->Entry[Heap->FirstFree].Data;
00151   Heap->Entry[Hole].Data = HoleData;
00152 
00153   /* now sift last entry to its rightful place */
00154   Father = FATHER (Hole);        /*father of hole */
00155   while (Hole > 1 && Heap->Entry[Father].Key > HoleKey) {
00156                                  /*swap entries */
00157     Heap->Entry[Hole].Key = Heap->Entry[Father].Key;
00158     Heap->Entry[Hole].Data = Heap->Entry[Father].Data;
00159     Heap->Entry[Father].Data = HoleData;
00160     Heap->Entry[Father].Key = HoleKey;
00161     Hole = Father;
00162     Father = FATHER (Hole);
00163   }
00164   return (TESS_HEAP_OK);
00165 }                                /* HeapPop */
00166 
00167 
00168 // Pushes data onto the heap only if there is free space left.
00169 // Returns true if data was added to the heap, false if the heap was full.
00170 bool HeapPushCheckSize(HEAP *Heap, FLOAT32 Key, void *Data) {
00171   if (Heap->FirstFree > Heap->Size) return false;
00172   HeapPush(Heap, Key, Data);
00173   return true;
00174 }
00175 
00176 /*---------------------------------------------------------------------------*/
00195 void HeapPush(HEAP *Heap, FLOAT32 Key, void *Data) {
00196   inT32 Item;
00197   inT32 Father;
00198 
00199   if (Heap->FirstFree > Heap->Size)
00200     DoError (HEAPFULL, "Heap size exceeded");
00201 
00202   Item = Heap->FirstFree;
00203   Heap->FirstFree++;
00204   while (Item != 1) {
00205     Father = FATHER (Item);
00206     if (Heap->Entry[Father].Key > Key) {
00207       Heap->Entry[Item].Key = Heap->Entry[Father].Key;
00208       Heap->Entry[Item].Data = Heap->Entry[Father].Data;
00209       Item = Father;
00210     }
00211     else
00212       break;
00213   }
00214   Heap->Entry[Item].Key = Key;
00215   Heap->Entry[Item].Data = Data;
00216 }                                /* HeapPush */
00217 
00218 
00219 /*---------------------------------------------------------------------------*/
00234 void HeapStore(HEAP *Heap, HEAPENTRY *Entry) {
00235   inT32 Item;
00236   inT32 Father;
00237 
00238   if (Heap->FirstFree > Heap->Size)
00239     DoError (HEAPFULL, "Heap size exceeded");
00240 
00241   Item = Heap->FirstFree;
00242   Heap->FirstFree++;
00243   while (Item != 1) {
00244     Father = FATHER (Item);
00245     if (Heap->Entry[Father].Key > Entry->Key) {
00246       Heap->Entry[Item].Key = Heap->Entry[Father].Key;
00247       Heap->Entry[Item].Data = Heap->Entry[Father].Data;
00248       Item = Father;
00249     }
00250     else
00251       break;
00252   }
00253   Heap->Entry[Item].Key = Entry->Key;
00254   Heap->Entry[Item].Data = Entry->Data;
00255 }                                /* HeapStore */
00256 
00257 
00258 /*---------------------------------------------------------------------------*/
00273 int GetTopOfHeap(HEAP *Heap, HEAPENTRY *Entry) {
00274   inT32 Hole;
00275   FLOAT32 HoleKey;
00276   inT32 Son;
00277 
00278   if (Heap->FirstFree <= 1)
00279     return (EMPTY);
00280 
00281   Entry->Key = Heap->Entry[1].Key;
00282   Entry->Data = Heap->Entry[1].Data;
00283 
00284   Heap->FirstFree--;
00285 
00286   /* imagine the hole at the root is filled with the last entry in the heap */
00287   HoleKey = Heap->Entry[Heap->FirstFree].Key;
00288   Hole = 1;
00289 
00290                                  /* while hole has 2 sons */
00291   while ((Son = LEFTSON (Hole)) < Heap->FirstFree) {
00292     /* find the son with the smallest key */
00293     if (Heap->Entry[Son].Key > Heap->Entry[Son + 1].Key)
00294       Son++;
00295 
00296     /* if key for hole is greater than key for son, sift hole down */
00297     if (HoleKey > Heap->Entry[Son].Key) {
00298       Heap->Entry[Hole].Key = Heap->Entry[Son].Key;
00299       Heap->Entry[Hole].Data = Heap->Entry[Son].Data;
00300       Hole = Son;
00301     }
00302     else
00303       break;
00304   }
00305   Heap->Entry[Hole].Key = HoleKey;
00306   Heap->Entry[Hole].Data = Heap->Entry[Heap->FirstFree].Data;
00307   return (TESS_HEAP_OK);
00308 }                                /* GetTopOfHeap */
00309 
00310 
00311 /*---------------------------------------------------------------------------*/
00327 void FreeHeapData(HEAP *Heap, void_dest destructor) {
00328   HEAPENTRY Entry;
00329 
00330   while (GetTopOfHeap (Heap, &Entry) != EMPTY)
00331     destructor (Entry.Data);
00332 
00333   FreeHeap(Heap);
00334 }                                /* FreeHeapData */