Leptonica  1.54
Файл src/heap.c
#include <string.h>
#include "allheaders.h"

Макросы

#define SWAP_ITEMS(i, j)

Функции

L_HEAPlheapCreate (l_int32 nalloc, l_int32 direction)
void lheapDestroy (L_HEAP **plh, l_int32 freeflag)
l_int32 lheapAdd (L_HEAP *lh, void *item)
l_int32 lheapExtendArray (L_HEAP *lh)
void * lheapRemove (L_HEAP *lh)
l_int32 lheapGetCount (L_HEAP *lh)
l_int32 lheapSwapUp (L_HEAP *lh, l_int32 index)
l_int32 lheapSwapDown (L_HEAP *lh)
l_int32 lheapSort (L_HEAP *lh)
l_int32 lheapSortStrictOrder (L_HEAP *lh)
l_int32 lheapPrint (FILE *fp, L_HEAP *lh)

Переменные

static const l_int32 MIN_BUFFER_SIZE = 20
static const l_int32 INITIAL_BUFFER_ARRAYSIZE = 128

Макросы

#define SWAP_ITEMS (   i,
 
)
Макроопределение:
{ void *tempitem = lh->array[(i)]; \
                                 lh->array[(i)] = lh->array[(j)]; \
                                 lh->array[(j)] = tempitem; }

Функции

l_int32 lheapAdd ( L_HEAP lh,
void *  item 
)

lheapAdd()

Input: lheap item to be added to the tail of the heap Return: 0 if OK, 1 on error

L_HEAP* lheapCreate ( l_int32  nalloc,
l_int32  direction 
)

lheapCreate()

Input: size of ptr array to be alloc'd (0 for default) direction (L_SORT_INCREASING, L_SORT_DECREASING) Return: lheap, or null on error

void lheapDestroy ( L_HEAP **  plh,
l_int32  freeflag 
)

lheapDestroy()

Input: &lheap (<to be="" nulled>="">) freeflag (TRUE to free each remaining struct in the array) Return: void

Notes: (1) Use freeflag == TRUE when the items in the array can be simply destroyed using free. If those items require their own destroy function, they must be destroyed before calling this function, and then this function is called with freeflag == FALSE. (2) To destroy the lheap, we destroy the ptr array, then the lheap, and then null the contents of the input ptr.

lheapExtendArray()

Input: lheap Return: 0 if OK, 1 on error

lheapGetCount()

Input: lheap Return: count, or 0 on error

l_int32 lheapPrint ( FILE *  fp,
L_HEAP lh 
)

lheapPrint()

Input: stream lheap Return: 0 if OK; 1 on error

void* lheapRemove ( L_HEAP lh)

lheapRemove()

Input: lheap Return: ptr to item popped from the root of the heap, or null if the heap is empty or on error

lheapSort()

Input: lh (heap, with internal array) Return: 0 if OK, 1 on error

Notes: (1) This sorts an array into heap order. If the heap is already in heap order for the direction given, this has no effect.

lheapSortStrictOrder()

Input: lh (heap, with internal array) Return: 0 if OK, 1 on error

Notes: (1) This sorts a heap into strict order. (2) For each element, starting at the end of the array and working forward, the element is swapped with the head element and then allowed to swap down onto a heap of size reduced by one. The result is that the heap is reversed but in strict order. The array elements are then reversed to put it in the original order.

lheapSwapDown()

Input: lh (heap) Return: 0 if OK, 1 on error

Notes: (1) This is called after an item has been popped off the root of the heap, and the last item in the heap has been placed at the root. (2) To regain the heap order, we let it bubble down, iteratively swapping with one of its children. For a decreasing sort, it swaps with the largest child; for an increasing sort, the smallest. This continues until it either reaches the lowest level in the heap, or the parent finds that neither child should swap with it (e.g., for a decreasing heap, the parent is larger than or equal to both children).

l_int32 lheapSwapUp ( L_HEAP lh,
l_int32  index 
)

lheapSwapUp()

Input: lh (heap) index (of array corresponding to node to be swapped up) Return: 0 if OK, 1 on error

Notes: (1) This is called after a new item is put on the heap, at the bottom of a complete tree. (2) To regain the heap order, we let it bubble up, iteratively swapping with its parent, until it either reaches the root of the heap or it finds a parent that is in the correct position already vis-a-vis the child.


Переменные

const l_int32 INITIAL_BUFFER_ARRAYSIZE = 128 [static]
const l_int32 MIN_BUFFER_SIZE = 20 [static]