"Fossies" - the Fresh Open Source Software Archive

Member "tesseract-ocr/doc/html/oldheap_8cpp_source.html" (26 Oct 2012, 56128 Bytes) of package /linux/misc/old/tesseract-ocr-3.02.02-doc-html.tar.gz:


Caution: In this restricted "Fossies" environment the current HTML page may not be correctly presentated and may have some non-functional links. You can here alternatively try to browse the pure source code or just view or download the uninterpreted raw source code. If the rendering is insufficient you may try to find and view the page on the tesseract-ocr-3.02.02-doc-html.tar.gz project site itself.

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