Tesseract  3.02
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
Macros | Functions
oldheap.cpp File Reference
#include "oldheap.h"
#include "freelist.h"
#include "danerror.h"
#include "emalloc.h"
#include <stdio.h>

Go to the source code of this file.

Macros

#define FATHER(N)   ((N)>>1)
 
#define LEFTSON(N)   ((N)<<1)
 
#define RIGHTSON(N)   ((N)<<1 + 1)
 

Functions

HEAP * MakeHeap (int Size)
 
int HeapPop (HEAP *Heap, FLOAT32 *Key, void *out_ptr)
 
int HeapPopWorst (HEAP *Heap, FLOAT32 *Key, void *out_ptr)
 
bool HeapPushCheckSize (HEAP *Heap, FLOAT32 Key, void *Data)
 
void HeapPush (HEAP *Heap, FLOAT32 Key, void *Data)
 
void HeapStore (HEAP *Heap, HEAPENTRY *Entry)
 
int GetTopOfHeap (HEAP *Heap, HEAPENTRY *Entry)
 
void FreeHeapData (HEAP *Heap, void_dest destructor)
 

Macro Definition Documentation

#define FATHER (   N)    ((N)>>1)

Definition at line 27 of file oldheap.cpp.

#define LEFTSON (   N)    ((N)<<1)

Definition at line 28 of file oldheap.cpp.

#define RIGHTSON (   N)    ((N)<<1 + 1)

Definition at line 29 of file oldheap.cpp.

Function Documentation

void FreeHeapData ( HEAP *  Heap,
void_dest  destructor 
)

This routine is similar to FreeHeap in that it deallocates the memory consumed by the heap. However, it also calls Deallocator for each item in the heap so that this data is also deallocated.

Parameters
Heapheap whose data is to be freed
destructorfunction to be used to deallocate data

Globals:

  • None
Note
Exceptions: none
History: Tue May 15 08:52:04 1990, DSJ, Created.

Definition at line 327 of file oldheap.cpp.

327  {
328  HEAPENTRY Entry;
329 
330  while (GetTopOfHeap (Heap, &Entry) != EMPTY)
331  destructor (Entry.Data);
332 
333  FreeHeap(Heap);
334 } /* FreeHeapData */
FreeHeap
#define FreeHeap(H)
Definition: oldheap.h:46
GetTopOfHeap
int GetTopOfHeap(HEAP *Heap, HEAPENTRY *Entry)
Definition: oldheap.cpp:273
HEAPENTRY::Data
void * Data
Definition: oldheap.h:34
EMPTY
#define EMPTY
Definition: oldheap.h:29
int GetTopOfHeap ( HEAP *  Heap,
HEAPENTRY *  Entry 
)

This routine removes the top item on the heap and copies its contents into Entry.

Parameters
Heapptr to heap whose top is to be removed and returned
Entryptr to heap entry to be filled with top entry on Heap

Globals:

  • None
Returns
OK if top entry returned, EMPTY if heap is empty
Note
Exceptions: None
History: 3/13/89, DSJ, Created.

Definition at line 273 of file oldheap.cpp.

273  {
274  inT32 Hole;
275  FLOAT32 HoleKey;
276  inT32 Son;
277 
278  if (Heap->FirstFree <= 1)
279  return (EMPTY);
280 
281  Entry->Key = Heap->Entry[1].Key;
282  Entry->Data = Heap->Entry[1].Data;
283 
284  Heap->FirstFree--;
285 
286  /* imagine the hole at the root is filled with the last entry in the heap */
287  HoleKey = Heap->Entry[Heap->FirstFree].Key;
288  Hole = 1;
289 
290  /* while hole has 2 sons */
291  while ((Son = LEFTSON (Hole)) < Heap->FirstFree) {
292  /* find the son with the smallest key */
293  if (Heap->Entry[Son].Key > Heap->Entry[Son + 1].Key)
294  Son++;
295 
296  /* if key for hole is greater than key for son, sift hole down */
297  if (HoleKey > Heap->Entry[Son].Key) {
298  Heap->Entry[Hole].Key = Heap->Entry[Son].Key;
299  Heap->Entry[Hole].Data = Heap->Entry[Son].Data;
300  Hole = Son;
301  }
302  else
303  break;
304  }
305  Heap->Entry[Hole].Key = HoleKey;
306  Heap->Entry[Hole].Data = Heap->Entry[Heap->FirstFree].Data;
307  return (TESS_HEAP_OK);
308 } /* GetTopOfHeap */
inT32
int inT32
Definition: host.h:102
FLOAT32
float FLOAT32
Definition: host.h:111
TESS_HEAP_OK
#define TESS_HEAP_OK
Definition: oldheap.h:30
HEAPENTRY::Data
void * Data
Definition: oldheap.h:34
HEAP::Entry
HEAPENTRY Entry[1]
Definition: oldheap.h:40
HEAPENTRY::Key
FLOAT32 Key
Definition: oldheap.h:33
HEAP::FirstFree
inT32 FirstFree
Definition: oldheap.h:39
LEFTSON
#define LEFTSON(N)
Definition: oldheap.cpp:28
EMPTY
#define EMPTY
Definition: oldheap.h:29
int HeapPop ( HEAP *  Heap,
FLOAT32 *  Key,
void *  out_ptr 
)

This routine removes the top item on the heap and places its contents into Key and Data.

Globals:

  • None
Parameters
Heapptr to heap whose top is to be removed and returned
Keyplace to put key of top heap item
out_ptrplace to put data of top heap item
Returns
OK if top entry returned, EMPTY if heap is empty
Note
Exceptions: None
History: 5/10/91, DSJ, Created (Modified from GetTopOfHeap).

Definition at line 76 of file oldheap.cpp.

76  {
77  inT32 Hole;
78  FLOAT32 HoleKey;
79  inT32 Son;
80  void **Data = (void **) out_ptr;
81 
82  if (Heap->FirstFree <= 1)
83  return (EMPTY);
84 
85  *Key = Heap->Entry[1].Key;
86  *Data = Heap->Entry[1].Data;
87 
88  Heap->FirstFree--;
89 
90  /* imagine the hole at the root is filled with the last entry in the heap */
91  HoleKey = Heap->Entry[Heap->FirstFree].Key;
92  Hole = 1;
93 
94  /* while hole has 2 sons */
95  while ((Son = LEFTSON (Hole)) < Heap->FirstFree) {
96  /* find the son with the smallest key */
97  if (Heap->Entry[Son].Key > Heap->Entry[Son + 1].Key)
98  Son++;
99 
100  /* if key for hole is greater than key for son, sift hole down */
101  if (HoleKey > Heap->Entry[Son].Key) {
102  Heap->Entry[Hole].Key = Heap->Entry[Son].Key;
103  Heap->Entry[Hole].Data = Heap->Entry[Son].Data;
104  Hole = Son;
105  }
106  else
107  break;
108  }
109  Heap->Entry[Hole].Key = HoleKey;
110  Heap->Entry[Hole].Data = Heap->Entry[Heap->FirstFree].Data;
111  return (TESS_HEAP_OK);
112 } /* HeapPop */
inT32
int inT32
Definition: host.h:102
FLOAT32
float FLOAT32
Definition: host.h:111
TESS_HEAP_OK
#define TESS_HEAP_OK
Definition: oldheap.h:30
HEAPENTRY::Data
void * Data
Definition: oldheap.h:34
HEAP::Entry
HEAPENTRY Entry[1]
Definition: oldheap.h:40
HEAPENTRY::Key
FLOAT32 Key
Definition: oldheap.h:33
HEAP::FirstFree
inT32 FirstFree
Definition: oldheap.h:39
LEFTSON
#define LEFTSON(N)
Definition: oldheap.cpp:28
EMPTY
#define EMPTY
Definition: oldheap.h:29
int HeapPopWorst ( HEAP *  Heap,
FLOAT32 *  Key,
void *  out_ptr 
)

HeapPopWorst

Remove the largest item from the heap.

Parameters
Heapptr to heap whose top is to be removed and returned
Keyplace to put key of top heap item
out_ptrplace to put data of top heap item

Definition at line 124 of file oldheap.cpp.

124  {
125  inT32 Index; /*current index */
126  inT32 Hole;
127  FLOAT32 HoleKey;
128  inT32 Father;
129  void *HoleData;
130  void **Data = (void **) out_ptr;
131 
132  if (Heap->FirstFree <= 1)
133  return (EMPTY);
134 
135  HoleKey = Heap->Entry[1].Key;
136  Hole = 1;
137  Heap->FirstFree--;
138  for (Index = Heap->FirstFree, Father = FATHER (Index); Index > Father;
139  Index--)
140  if (Heap->Entry[Index].Key > HoleKey) {
141  /*find biggest */
142  HoleKey = Heap->Entry[Index].Key;
143  Hole = Index;
144  }
145  *Key = HoleKey;
146  *Data = Heap->Entry[Hole].Data;
147 
148  HoleKey = Heap->Entry[Heap->FirstFree].Key;
149  Heap->Entry[Hole].Key = HoleKey;
150  HoleData = Heap->Entry[Heap->FirstFree].Data;
151  Heap->Entry[Hole].Data = HoleData;
152 
153  /* now sift last entry to its rightful place */
154  Father = FATHER (Hole); /*father of hole */
155  while (Hole > 1 && Heap->Entry[Father].Key > HoleKey) {
156  /*swap entries */
157  Heap->Entry[Hole].Key = Heap->Entry[Father].Key;
158  Heap->Entry[Hole].Data = Heap->Entry[Father].Data;
159  Heap->Entry[Father].Data = HoleData;
160  Heap->Entry[Father].Key = HoleKey;
161  Hole = Father;
162  Father = FATHER (Hole);
163  }
164  return (TESS_HEAP_OK);
165 } /* HeapPop */
inT32
int inT32
Definition: host.h:102
FLOAT32
float FLOAT32
Definition: host.h:111
FATHER
#define FATHER(N)
Definition: oldheap.cpp:27
TESS_HEAP_OK
#define TESS_HEAP_OK
Definition: oldheap.h:30
HEAPENTRY::Data
void * Data
Definition: oldheap.h:34
HEAP::Entry
HEAPENTRY Entry[1]
Definition: oldheap.h:40
HEAPENTRY::Key
FLOAT32 Key
Definition: oldheap.h:33
HEAP::FirstFree
inT32 FirstFree
Definition: oldheap.h:39
EMPTY
#define EMPTY
Definition: oldheap.h:29
void HeapPush ( HEAP *  Heap,
FLOAT32  Key,
void *  Data 
)

This routine stores Data into Heap and associates it with Key. The heap is maintained in such a way that the item with the lowest key is always at the top of the heap.

Globals:

  • None
Parameters
Heapptr to heap to store new item in
Keynumeric key associated with new item
Dataptr to data contents of new item
Note
Exceptions:
  • HEAPFULL error if heap size is exceeded
History: 5/10/91, DSJ, Created (Modified version of HeapStore).

Definition at line 195 of file oldheap.cpp.

195  {
196  inT32 Item;
197  inT32 Father;
198 
199  if (Heap->FirstFree > Heap->Size)
200  DoError (HEAPFULL, "Heap size exceeded");
201 
202  Item = Heap->FirstFree;
203  Heap->FirstFree++;
204  while (Item != 1) {
205  Father = FATHER (Item);
206  if (Heap->Entry[Father].Key > Key) {
207  Heap->Entry[Item].Key = Heap->Entry[Father].Key;
208  Heap->Entry[Item].Data = Heap->Entry[Father].Data;
209  Item = Father;
210  }
211  else
212  break;
213  }
214  Heap->Entry[Item].Key = Key;
215  Heap->Entry[Item].Data = Data;
216 } /* HeapPush */
DoError
void DoError(int Error, const char *Message)
Definition: danerror.cpp:32
inT32
int inT32
Definition: host.h:102
FATHER
#define FATHER(N)
Definition: oldheap.cpp:27
HEAP::Size
inT32 Size
Definition: oldheap.h:38
HEAPENTRY::Data
void * Data
Definition: oldheap.h:34
HEAPFULL
#define HEAPFULL
Definition: oldheap.h:27
HEAP::Entry
HEAPENTRY Entry[1]
Definition: oldheap.h:40
HEAPENTRY::Key
FLOAT32 Key
Definition: oldheap.h:33
HEAP::FirstFree
inT32 FirstFree
Definition: oldheap.h:39
bool HeapPushCheckSize ( HEAP *  Heap,
FLOAT32  Key,
void *  Data 
)

Definition at line 170 of file oldheap.cpp.

170  {
171  if (Heap->FirstFree > Heap->Size) return false;
172  HeapPush(Heap, Key, Data);
173  return true;
174 }
HeapPush
void HeapPush(HEAP *Heap, FLOAT32 Key, void *Data)
Definition: oldheap.cpp:195
HEAP::Size
inT32 Size
Definition: oldheap.h:38
HEAP::FirstFree
inT32 FirstFree
Definition: oldheap.h:39
void HeapStore ( HEAP *  Heap,
HEAPENTRY *  Entry 
)

This routine stores Entry into Heap. The heap is maintained in such a way that the item with the lowest key is always at the top of the heap.

Globals:

  • None
Parameters
Heapptr to heap to store new item in
Entryptr to item to be stored in Heap
Note
Exceptions:
  • HEAPFULL error if heap size is exceeded
History: 3/13/89, DSJ, Created.

Definition at line 234 of file oldheap.cpp.

234  {
235  inT32 Item;
236  inT32 Father;
237 
238  if (Heap->FirstFree > Heap->Size)
239  DoError (HEAPFULL, "Heap size exceeded");
240 
241  Item = Heap->FirstFree;
242  Heap->FirstFree++;
243  while (Item != 1) {
244  Father = FATHER (Item);
245  if (Heap->Entry[Father].Key > Entry->Key) {
246  Heap->Entry[Item].Key = Heap->Entry[Father].Key;
247  Heap->Entry[Item].Data = Heap->Entry[Father].Data;
248  Item = Father;
249  }
250  else
251  break;
252  }
253  Heap->Entry[Item].Key = Entry->Key;
254  Heap->Entry[Item].Data = Entry->Data;
255 } /* HeapStore */
DoError
void DoError(int Error, const char *Message)
Definition: danerror.cpp:32
inT32
int inT32
Definition: host.h:102
FATHER
#define FATHER(N)
Definition: oldheap.cpp:27
HEAP::Size
inT32 Size
Definition: oldheap.h:38
HEAPENTRY::Data
void * Data
Definition: oldheap.h:34
HEAPFULL
#define HEAPFULL
Definition: oldheap.h:27
HEAP::Entry
HEAPENTRY Entry[1]
Definition: oldheap.h:40
HEAPENTRY::Key
FLOAT32 Key
Definition: oldheap.h:33
HEAP::FirstFree
inT32 FirstFree
Definition: oldheap.h:39
HEAP* MakeHeap ( int  Size)

This routine creates and initializes a new heap data structure containing Size elements. In actuality, Size + 1 elements are allocated. The first element, element 0, is unused, this makes the index arithmetic easier.

Globals:

  • None
Parameters
Sizemaximum number of entries in the heap
Returns
Pointer to the new heap.
Note
Exceptions: None
History: 3/13/89, DSJ, Created.

Definition at line 49 of file oldheap.cpp.

49  {
50  HEAP *NewHeap;
51 
52  NewHeap = (HEAP *) Emalloc (sizeof (HEAP) + Size * sizeof (HEAPENTRY));
53 
54  NewHeap->Size = Size;
55  NewHeap->FirstFree = 1;
56  return (NewHeap);
57 } /* MakeHeap */
HEAP::Size
inT32 Size
Definition: oldheap.h:38
Emalloc
void * Emalloc(size_t Size)
Definition: emalloc.cpp:35
HEAP
Definition: oldheap.h:37
HEAP::FirstFree
inT32 FirstFree
Definition: oldheap.h:39