Tesseract 3.02

- Main Page
- Related Pages
- Modules
- Namespaces
- Classes
- Files

- File List
- File Members

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