 |
Leptonica 1.85.0
Image processing and image analysis suite
|
|
Leptonica 1.85.0
Image processing and image analysis suite
|
#include <string.h>#include "allheaders.h"Go to the source code of this file.
Macros | |
| #define | SWAP_ITEMS(i, j) |
Functions | |
| static l_int32 | lheapExtendArray (L_HEAP *lh) |
| static l_ok | lheapSwapUp (L_HEAP *lh, l_int32 index) |
| static l_ok | lheapSwapDown (L_HEAP *lh) |
| L_HEAP * | lheapCreate (l_int32 n, l_int32 direction) |
| void | lheapDestroy (L_HEAP **plh, l_int32 freeflag) |
| l_ok | lheapAdd (L_HEAP *lh, void *item) |
| void * | lheapRemove (L_HEAP *lh) |
| l_int32 | lheapGetCount (L_HEAP *lh) |
| void * | lheapGetElement (L_HEAP *lh, l_int32 index) |
| l_ok | lheapSort (L_HEAP *lh) |
| l_ok | lheapSortStrictOrder (L_HEAP *lh) |
| l_ok | lheapPrint (FILE *fp, L_HEAP *lh) |
Variables | |
| static const l_uint32 | MaxPtrArraySize = 100000 |
| static const l_int32 | InitialPtrArraySize = 20 |
Create/Destroy L_Heap
L_HEAP *lheapCreate()
void lheapDestroy()
Operations to add/remove to/from the heap
l_int32 lheapAdd()
static l_int32 lheapExtendArray()
void *lheapRemove()
Other accessors
l_int32 lheapGetCount()
void *lheapGetElement()
Heap sort
l_int32 lheapSort()
l_int32 lheapSortStrictOrder()
Low-level heap operations
static l_int32 lheapSwapUp()
static l_int32 lheapSwapDown()
Debug output
l_int32 lheapPrint()
The L_Heap is useful to implement a priority queue, that is sorted
on a key in each element of the heap. The heap is an array
of nearly arbitrary structs, with a l_float32 the first field.
This field is the key on which the heap is sorted.
Internally, we keep track of the heap size, n. The item at the
root of the heap is at the head of the array. Items are removed
from the head of the array and added to the end of the array.
When an item is removed from the head, the item at the end
of the array is moved to the head. When items are either
added or removed, it is usually necessary to swap array items
to restore the heap order. It is guaranteed that the number
of swaps does not exceed log(n).
-------------------------- N.B. ------------------------------
The items on the heap (or, equivalently, in the array) are cast
to void*. Their key is a l_float32, and it is REQUIRED that the
key be the first field in the struct. That allows us to get the
key by simply dereferencing the struct. Alternatively, we could
choose (but don't) to pass an application-specific comparison
function into the heap operation functions.
-------------------------- N.B. ------------------------------
Definition in file heap.c.
| #define SWAP_ITEMS | ( | i, | |
| j ) |
| l_ok lheapAdd | ( | L_HEAP * | lh, |
| void * | item ) |
| [in] | lh | heap |
| [in] | item | to be added to the tail of the heap |
Definition at line 189 of file heap.c.
References L_Heap::array, lheapExtendArray(), lheapSwapUp(), L_Heap::n, and L_Heap::nalloc.
| L_HEAP * lheapCreate | ( | l_int32 | n, |
| l_int32 | direction ) |
| [in] | n | size of ptr array to be alloc'd; use 0 for default |
| [in] | direction | L_SORT_INCREASING, L_SORT_DECREASING |
Definition at line 112 of file heap.c.
References L_Heap::array, L_Heap::direction, InitialPtrArraySize, lheapDestroy(), L_Heap::n, and L_Heap::nalloc.
| void lheapDestroy | ( | L_HEAP ** | plh, |
| l_int32 | freeflag ) |
| [in,out] | plh | will be set to null before returning |
| [in] | freeflag | TRUE to free each remaining struct in the array |
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.
Definition at line 152 of file heap.c.
References L_Heap::array, and L_Heap::n.
Referenced by lheapCreate().
|
static |
| [in] | lh | heap |
Definition at line 220 of file heap.c.
References L_Heap::array, and L_Heap::nalloc.
Referenced by lheapAdd().
| l_int32 lheapGetCount | ( | L_HEAP * | lh | ) |
| [in] | lh | heap |
Definition at line 273 of file heap.c.
References L_Heap::n.
Referenced by lheapSwapDown().
| void * lheapGetElement | ( | L_HEAP * | lh, |
| l_int32 | index ) |
| [in] | lh | heap |
| [in] | index | into the internal heap array |
Notes:
(1) This is useful for retrieving an arbitrary element in the
heap array without disturbing the heap. It allows all the
elements on the heap to be queried in linear time; for
example, to find the min or max of some value.
(2) The retrieved element is owned by the heap. Do not destroy it.
Definition at line 299 of file heap.c.
References L_Heap::array, and L_Heap::n.
| l_ok lheapPrint | ( | FILE * | fp, |
| L_HEAP * | lh ) |
| [in] | fp | file stream |
| [in] | lh | heap |
Definition at line 549 of file heap.c.
References L_Heap::array, L_Heap::n, and L_Heap::nalloc.
| void * lheapRemove | ( | L_HEAP * | lh | ) |
| [in] | lh | heap |
Definition at line 243 of file heap.c.
References L_Heap::array, lheapSwapDown(), and L_Heap::n.
| l_ok lheapSort | ( | L_HEAP * | lh | ) |
| [in] | lh | heap, with internal array |
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.
Definition at line 327 of file heap.c.
References lheapSwapUp(), and L_Heap::n.
Referenced by lheapSortStrictOrder().
| l_ok lheapSortStrictOrder | ( | L_HEAP * | lh | ) |
| [in] | lh | heap, with internal array |
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.
Definition at line 359 of file heap.c.
References lheapSort(), lheapSwapDown(), and L_Heap::n.
|
static |
| [in] | lh | heap |
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).
Definition at line 470 of file heap.c.
References L_Heap::array, L_Heap::direction, L_SORT_INCREASING, lheapGetCount(), and L_Heap::n.
Referenced by lheapRemove(), and lheapSortStrictOrder().
|
static |
| [in] | lh | heap |
| [in] | index | of array corresponding to node to be swapped up |
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.
Definition at line 406 of file heap.c.
References L_Heap::array, L_Heap::direction, L_SORT_INCREASING, and L_Heap::n.
Referenced by lheapAdd(), and lheapSort().
|
static |
1.12.0