Tesseract  3.02
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
oldheap.cpp
Go to the documentation of this file.
1 /******************************************************************************
2  ** Filename: heap.c
3  ** Purpose: Routines for managing heaps (smallest at root)
4  ** Author: Dan Johnson
5  ** History: 3/13/89, DSJ, Created.
6  **
7  ** (c) Copyright Hewlett-Packard Company, 1988.
8  ** Licensed under the Apache License, Version 2.0 (the "License");
9  ** you may not use this file except in compliance with the License.
10  ** You may obtain a copy of the License at
11  ** http://www.apache.org/licenses/LICENSE-2.0
12  ** Unless required by applicable law or agreed to in writing, software
13  ** distributed under the License is distributed on an "AS IS" BASIS,
14  ** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15  ** See the License for the specific language governing permissions and
16  ** limitations under the License.
17  ******************************************************************************/
18 /*-----------------------------------------------------------------------------
19  Include Files and Type Defines
20 -----------------------------------------------------------------------------*/
21 #include "oldheap.h"
22 #include "freelist.h"
23 #include "danerror.h"
24 #include "emalloc.h"
25 #include <stdio.h>
26 
27 #define FATHER(N) ((N)>>1)
28 #define LEFTSON(N) ((N)<<1)
29 #define RIGHTSON(N) ((N)<<1 + 1)
30 
31 /*-----------------------------------------------------------------------------
32  Public Code
33 -----------------------------------------------------------------------------*/
34 /*---------------------------------------------------------------------------*/
49 HEAP *MakeHeap(int Size) {
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 */
58 
59 
60 /*---------------------------------------------------------------------------*/
76 int HeapPop(HEAP *Heap, FLOAT32 *Key, void *out_ptr) {
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 */
113 
114 
124 int HeapPopWorst(HEAP *Heap, FLOAT32 *Key, void *out_ptr) {
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 */
166 
167 
168 // Pushes data onto the heap only if there is free space left.
169 // Returns true if data was added to the heap, false if the heap was full.
170 bool HeapPushCheckSize(HEAP *Heap, FLOAT32 Key, void *Data) {
171  if (Heap->FirstFree > Heap->Size) return false;
172  HeapPush(Heap, Key, Data);
173  return true;
174 }
175 
176 /*---------------------------------------------------------------------------*/
195 void HeapPush(HEAP *Heap, FLOAT32 Key, void *Data) {
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 */
217 
218 
219 /*---------------------------------------------------------------------------*/
234 void HeapStore(HEAP *Heap, HEAPENTRY *Entry) {
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 */
256 
257 
258 /*---------------------------------------------------------------------------*/
273 int GetTopOfHeap(HEAP *Heap, HEAPENTRY *Entry) {
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 */
309 
310 
311 /*---------------------------------------------------------------------------*/
327 void FreeHeapData(HEAP *Heap, void_dest destructor) {
328  HEAPENTRY Entry;
329 
330  while (GetTopOfHeap (Heap, &Entry) != EMPTY)
331  destructor (Entry.Data);
332 
333  FreeHeap(Heap);
334 } /* FreeHeapData */