tesseract-ocr/cutil/oldheap.h File Reference

#include "host.h"
#include "cutil.h"

Go to the source code of this file.

Classes
struct	HEAPENTRY
struct	HEAP
Defines
#define	HEAPFULL   3000
#define	EMPTY   -1
#define	TESS_HEAP_OK   0
#define	FreeHeap(H)   memfree(H)
#define	MaxSizeOfHeap(H)   (H->Size)
#define	SizeOfHeap(H)   (H->FirstFree - 1)
#define	InitHeap(H)   (H->FirstFree = 1)
#define	HeapFull(H)   ((H)->FirstFree > (H)->Size)
#define	HeapEmpty(H)   ((H)->FirstFree <= 1)
#define	HeapKeyFor(H, E)   ((H)->Entry[(E)+1].Key)
#define	HeapDataFor(H, E)   ((H)->Entry[(E)+1].Data)
Functions
HEAP *	MakeHeap (int Size)
int	HeapPop (HEAP *Heap, FLOAT32 *Key, void *out_ptr)
int	HeapPopWorst (HEAP *Heap, FLOAT32 *Key, void *out_ptr)
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)
bool	HeapPushCheckSize (HEAP *Heap, FLOAT32 Key, void *Data)

---

Define Documentation

#define EMPTY   -1

Definition at line 29 of file oldheap.h.

#define FreeHeap

(

H

)

memfree(H)

Definition at line 46 of file oldheap.h.

#define HeapDataFor	(		H,
			E
	)		((H)->Entry[(E)+1].Data)

Definition at line 59 of file oldheap.h.

#define HeapEmpty

(

H

)

((H)->FirstFree <= 1)

Definition at line 51 of file oldheap.h.

#define HEAPFULL   3000

Definition at line 27 of file oldheap.h.

#define HeapFull

(

H

)

((H)->FirstFree > (H)->Size)

Definition at line 50 of file oldheap.h.

#define HeapKeyFor	(		H,
			E
	)		((H)->Entry[(E)+1].Key)

Definition at line 58 of file oldheap.h.

#define InitHeap

(

H

)

(H->FirstFree = 1)

Definition at line 49 of file oldheap.h.

#define MaxSizeOfHeap

(

H

)

(H->Size)

Definition at line 47 of file oldheap.h.

#define SizeOfHeap

(

H

)

(H->FirstFree - 1)

Definition at line 48 of file oldheap.h.

#define TESS_HEAP_OK   0

Definition at line 30 of file oldheap.h.

---

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