cutil/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.

Defines

Functions

Define Documentation

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

Note:
File: heap.cpp
Routines for managing heaps (smallest at root)
Author:
Dan Johnson
Date:
3/13/89, DSJ, Created. 
 **	(c) Copyright Hewlett-Packard Company, 1988.
 ** Licensed under the Apache License, Version 2.0 (the "License");
 ** you may not use this file except in compliance with the License.
 ** You may obtain a copy of the License at
 ** http://www.apache.org/licenses/LICENSE-2.0
 ** Unless required by applicable law or agreed to in writing, software
 ** distributed under the License is distributed on an "AS IS" BASIS,
 ** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 ** See the License for the specific language governing permissions and
 ** limitations under the License.

Definition at line 28 of file oldheap.cpp.

Referenced by HeapPopWorst(), HeapPush(), and HeapStore().

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

Definition at line 29 of file oldheap.cpp.

Referenced by GetTopOfHeap(), and HeapPop().

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

Definition at line 30 of file oldheap.cpp.

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