cutil/oldheap.h File Reference

#include "general.h"
#include "cutil.h"

Go to the source code of this file.

Classes

Defines

Functions


Define Documentation

#define EMPTY   -1

Definition at line 32 of file oldheap.h.

Referenced by CreateClusterTree(), FreeHeapData(), GetTopOfHeap(), HeapPop(), HeapPopWorst(), and PrintBadWords().

#define FreeHeap (  )     memfree(H)

Definition at line 58 of file oldheap.h.

Referenced by CreateClusterTree(), FreeHeapData(), and pick_good_seam().

#define HeapDataFor ( H,
 )     ((H)->Entry[(E)+1].Data)

Definition at line 75 of file oldheap.h.

#define HeapEmpty (  )     ((H)->FirstFree <= 1)

Definition at line 63 of file oldheap.h.

#define HeapFull (  )     ((H)->FirstFree > (H)->Size)

Definition at line 62 of file oldheap.h.

Referenced by SaveBadWord().

#define HEAPFULL   3000

Error ID

Definition at line 29 of file oldheap.h.

Referenced by HeapPush(), and HeapStore().

#define HeapKeyFor ( H,
 )     ((H)->Entry[(E)+1].Key)

macros for accessing elements in heap by index.

The indicies vary from 0 to SizeOfHeap-1. No bounds checking is done. Elements accessed in this manner are in random order relative to the Key values.

These macros should never be used as the LHS (Left Hand Side) of an assignment statement as this will corrupt the heap.

Definition at line 74 of file oldheap.h.

#define InitHeap (  )     (H->FirstFree = 1)

Definition at line 61 of file oldheap.h.

Referenced by SaveBadWord().

#define MaxSizeOfHeap (  )     (H->Size)

Definition at line 59 of file oldheap.h.

Referenced by push_queue().

#define OK   0

Definition at line 31 of file oldheap.h.

Referenced by GetTopOfHeap(), HeapPop(), pick_good_seam(), and pop_queue().

#define SizeOfHeap (  )     (H->FirstFree - 1)

Definition at line 60 of file oldheap.h.

Referenced by add_point_to_list(), and push_queue().


Function Documentation

void FreeHeapData ( HEAP Heap,
void_dest  destructor 
)

Similarily to FreeHeap, deallocates the memory consumed by the heap but also calls Deallocator for each item in the heap so that this data is also deallocated.

Parameters:
Heap Heap whose data is to be freed
destructor Function to be used to destroy data
Returns:
none
Note:
Exceptions: none
Date:
Tue May 15 08:52:04 1990, DSJ, Created.

Definition at line 298 of file oldheap.cpp.

References HEAPENTRY::Data, EMPTY, FreeHeap, GetTopOfHeap(), and Heap.

Referenced by delete_search().

00298                                                     { 
00299   HEAPENTRY Entry;
00300 
00301   while (GetTopOfHeap (Heap, &Entry) != EMPTY)
00302     destructor (Entry.Data);
00303 
00304   FreeHeap(Heap); 
00305 }                                /* FreeHeapData */

int GetTopOfHeap ( HEAP Heap,
HEAPENTRY Entry 
)

Removes the top item on the heap and copies its contents into Entry.

Parameters:
Heap Ptr to heap whose top is to be removed and returned
Entry Ptr to heap entry to be filled with top entry on Heap
Returns:
OK if top entry returned, EMPTY if heap is empty
Note:
Exceptions: None
Date:
3/13/89, DSJ, Created.

Definition at line 248 of file oldheap.cpp.

References HEAPENTRY::Data, EMPTY, HEAP::Entry, HEAP::FirstFree, Heap, HEAPENTRY::Key, LEFTSON, and OK.

Referenced by CreateClusterTree(), FreeHeapData(), pop_queue(), and PrintBadWords().

00248                                                { 
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 */

int HeapPop ( HEAP Heap,
FLOAT32 Key,
void *  out_ptr 
)

Removes the top item on the heap and places its contents into Key and Data.

Parameters:
Heap Ptr to heap whose top is to be removed and returned
Key Place to put key of top heap item
out_ptr Place to put data of top heap item
Returns:
OK if top entry returned, EMPTY if heap is empty
Note:
Exceptions: None
Date:
5/10/91, DSJ, Created (Modified from GetTopOfHeap).

Definition at line 71 of file oldheap.cpp.

References HEAPENTRY::Data, EMPTY, HEAP::Entry, HEAP::FirstFree, Heap, HEAPENTRY::Key, LEFTSON, and OK.

Referenced by pick_good_seam().

00071                                                      { 
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 */

int HeapPopWorst ( HEAP Heap,
FLOAT32 Key,
void *  out_ptr 
)

Remove the largest item from the heap.

Parameters:
Heap Pointer to heap whose top is to be removed and returned
Key Place to put key of top heap item
out_ptr Place to put data of top heap item
Returns:
OK if top entry returned, EMPTY if heap is empty

Definition at line 119 of file oldheap.cpp.

References EMPTY, HEAP::Entry, FATHER, HEAP::FirstFree, Heap, and HEAPENTRY::Key.

Referenced by junk_worst_seam().

00119                                                           { 
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 */

void HeapPush ( HEAP Heap,
FLOAT32  Key,
void *  Data 
)

Stores Data into Heap and associates it with Key.

Parameters:
Heap Ptr to heap to store new item in
Key Numeric key associated with new item
Data Ptr to data contents of new item
Returns:
None
The heap is maintained in such a way that the item with the lowest key is always at the top of the heap.
Note:
Exceptions: HEAPFULL error if heap size is exceeded
Date:
5/10/91, DSJ, Created (Modified version of HeapStore).

Definition at line 177 of file oldheap.cpp.

References HEAPENTRY::Data, DoError(), HEAP::Entry, FATHER, HEAP::FirstFree, Heap, HEAPFULL, HEAPENTRY::Key, and HEAP::Size.

Referenced by junk_worst_seam().

00177                                                    { 
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 */

void HeapStore ( HEAP Heap,
HEAPENTRY Entry 
)

Stores Entry into Heap.

Parameters:
Heap Ptr to heap to store new item in
Entry Ptr to item to be stored in Heap
Returns:
None
The heap is maintained in such a way that the item with the lowest key is always at the top of the heap.
Note:
Exceptions: HEAPFULL error if heap size is exceeded
Date:
3/13/89, DSJ, Created.

Definition at line 214 of file oldheap.cpp.

References HEAPENTRY::Data, DoError(), HEAP::Entry, FATHER, HEAP::FirstFree, Heap, HEAPFULL, HEAPENTRY::Key, and HEAP::Size.

Referenced by add_point_to_list(), CreateClusterTree(), MakePotentialClusters(), push_queue(), and SaveBadWord().

00214                                              { 
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 */

HEAP* MakeHeap ( int  Size  ) 

Creates and initializes a new heap data structure containing Size elements.

Parameters:
Size Maximum number of entries in the heap
Returns:
Pointer to the new heap.
In actuality, Size + 1 elements are allocated. The first element, element 0, is unused, this makes the index arithmetic easier.
Note:
Exceptions: None
Date:
3/13/89, DSJ, Created.

Definition at line 48 of file oldheap.cpp.

References Emalloc(), HEAP::FirstFree, and HEAP::Size.

Referenced by CreateClusterTree(), new_search(), pick_good_seam(), and SaveBadWord().

00048                          { 
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 */


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