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
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:

  Heap | heap whose data is to be freed
  destructor | function 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.

{
HEAPENTRY Entry;
while (GetTopOfHeap (Heap, &Entry) != EMPTY)
destructor (Entry.Data);
FreeHeap(Heap);
} /* FreeHeapData */

int GetTopOfHeap | ( | HEAP * | Heap,
|  | HEAPENTRY * | Entry
| ) |  |

This routine 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

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.

{
inT32 Hole;
FLOAT32 HoleKey;
inT32 Son;
if (Heap->FirstFree <= 1)
return (EMPTY);
Entry->Key = Heap->Entry[1].Key;
Entry->Data = Heap->Entry[1].Data;
Heap->FirstFree--;
/* imagine the hole at the root is filled with the last entry in the heap */
HoleKey = Heap->Entry[Heap->FirstFree].Key;
Hole = 1;
/* while hole has 2 sons */
while ((Son = LEFTSON (Hole)) < Heap->FirstFree) {
/* find the son with the smallest key */
if (Heap->Entry[Son].Key > Heap->Entry[Son + 1].Key)
Son++;
/* if key for hole is greater than key for son, sift hole down */
if (HoleKey > Heap->Entry[Son].Key) {
Heap->Entry[Hole].Key = Heap->Entry[Son].Key;
Heap->Entry[Hole].Data = Heap->Entry[Son].Data;
Hole = Son;
}
else
break;
}
Heap->Entry[Hole].Key = HoleKey;
Heap->Entry[Hole].Data = Heap->Entry[Heap->FirstFree].Data;
return (TESS_HEAP_OK);
} /* GetTopOfHeap */

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:

  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
  History: 5/10/91, DSJ, Created (Modified from GetTopOfHeap).

Definition at line 76 of file oldheap.cpp.

{
inT32 Hole;
FLOAT32 HoleKey;
inT32 Son;
void **Data = (void **) out_ptr;
if (Heap->FirstFree <= 1)
return (EMPTY);
*Key = Heap->Entry[1].Key;
*Data = Heap->Entry[1].Data;
Heap->FirstFree--;
/* imagine the hole at the root is filled with the last entry in the heap */
HoleKey = Heap->Entry[Heap->FirstFree].Key;
Hole = 1;
/* while hole has 2 sons */
while ((Son = LEFTSON (Hole)) < Heap->FirstFree) {
/* find the son with the smallest key */
if (Heap->Entry[Son].Key > Heap->Entry[Son + 1].Key)
Son++;
/* if key for hole is greater than key for son, sift hole down */
if (HoleKey > Heap->Entry[Son].Key) {
Heap->Entry[Hole].Key = Heap->Entry[Son].Key;
Heap->Entry[Hole].Data = Heap->Entry[Son].Data;
Hole = Son;
}
else
break;
}
Heap->Entry[Hole].Key = HoleKey;
Heap->Entry[Hole].Data = Heap->Entry[Heap->FirstFree].Data;
return (TESS_HEAP_OK);
} /* HeapPop */

int HeapPopWorst | ( | HEAP * | Heap,
|  | FLOAT32 * | Key,
|  | void * | out_ptr
| ) |  |

HeapPopWorst

Remove the largest item from the heap.

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

Definition at line 124 of file oldheap.cpp.

{
inT32 Index; /*current index */
inT32 Hole;
FLOAT32 HoleKey;
inT32 Father;
void *HoleData;
void **Data = (void **) out_ptr;
if (Heap->FirstFree <= 1)
return (EMPTY);
HoleKey = Heap->Entry[1].Key;
Hole = 1;
Heap->FirstFree--;
for (Index = Heap->FirstFree, Father = FATHER (Index); Index > Father;
Index--)
if (Heap->Entry[Index].Key > HoleKey) {
/*find biggest */
HoleKey = Heap->Entry[Index].Key;
Hole = Index;
}
*Key = HoleKey;
*Data = Heap->Entry[Hole].Data;
HoleKey = Heap->Entry[Heap->FirstFree].Key;
Heap->Entry[Hole].Key = HoleKey;
HoleData = Heap->Entry[Heap->FirstFree].Data;
Heap->Entry[Hole].Data = HoleData;
/* now sift last entry to its rightful place */
Father = FATHER (Hole); /*father of hole */
while (Hole > 1 && Heap->Entry[Father].Key > HoleKey) {
/*swap entries */
Heap->Entry[Hole].Key = Heap->Entry[Father].Key;
Heap->Entry[Hole].Data = Heap->Entry[Father].Data;
Heap->Entry[Father].Data = HoleData;
Heap->Entry[Father].Key = HoleKey;
Hole = Father;
Father = FATHER (Hole);
}
return (TESS_HEAP_OK);
} /* HeapPop */

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:

  Heap | ptr to heap to store new item in
  Key | numeric key associated with new item
  Data | ptr 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.

{
inT32 Item;
inT32 Father;
if (Heap->FirstFree > Heap->Size)
DoError (HEAPFULL, "Heap size exceeded");
Item = Heap->FirstFree;
Heap->FirstFree++;
while (Item != 1) {
Father = FATHER (Item);
if (Heap->Entry[Father].Key > Key) {
Heap->Entry[Item].Key = Heap->Entry[Father].Key;
Heap->Entry[Item].Data = Heap->Entry[Father].Data;
Item = Father;
}
else
break;
}
Heap->Entry[Item].Key = Key;
Heap->Entry[Item].Data = Data;
} /* HeapPush */

bool HeapPushCheckSize | ( | HEAP * | Heap,
|  | FLOAT32 | Key,
|  | void * | Data
| ) |  |

Definition at line 170 of file oldheap.cpp.

{
if (Heap->FirstFree > Heap->Size) return false;
HeapPush(Heap, Key, Data);
return true;
}

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:

  Heap | ptr to heap to store new item in
  Entry | ptr 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.

{
inT32 Item;
inT32 Father;
if (Heap->FirstFree > Heap->Size)
DoError (HEAPFULL, "Heap size exceeded");
Item = Heap->FirstFree;
Heap->FirstFree++;
while (Item != 1) {
Father = FATHER (Item);
if (Heap->Entry[Father].Key > Entry->Key) {
Heap->Entry[Item].Key = Heap->Entry[Father].Key;
Heap->Entry[Item].Data = Heap->Entry[Father].Data;
Item = Father;
}
else
break;
}
Heap->Entry[Item].Key = Entry->Key;
Heap->Entry[Item].Data = Entry->Data;
} /* HeapStore */

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:

  Size | maximum 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.

{
HEAP *NewHeap;
NewHeap = (HEAP *) Emalloc (sizeof (HEAP) + Size * sizeof (HEAPENTRY));
NewHeap->Size = Size;
NewHeap->FirstFree = 1;
return (NewHeap);
} /* MakeHeap */