Leptonica  1.83.1
Image processing and image analysis suite
heap.c File Reference
#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_HEAPlheapCreate (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
 

Detailed Description


     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.

Macro Definition Documentation

◆ SWAP_ITEMS

#define SWAP_ITEMS (   i,
 
)
Value:
{ void *tempitem = lh->array[(i)]; \
lh->array[(i)] = lh->array[(j)]; \
lh->array[(j)] = tempitem; }

Definition at line 91 of file heap.c.

Function Documentation

◆ lheapAdd()

l_ok lheapAdd ( L_HEAP lh,
void *  item 
)

lheapAdd()

Parameters
[in]lhheap
[in]itemto be added to the tail of the heap
Returns
0 if OK, 1 on error

Definition at line 189 of file heap.c.

References L_Heap::array, lheapExtendArray(), lheapSwapUp(), L_Heap::n, and L_Heap::nalloc.

◆ lheapCreate()

L_HEAP* lheapCreate ( l_int32  n,
l_int32  direction 
)

lheapCreate()

Parameters
[in]nsize of ptr array to be alloc'd; use 0 for default
[in]directionL_SORT_INCREASING, L_SORT_DECREASING
Returns
lheap, or NULL on error

Definition at line 112 of file heap.c.

Referenced by pixSearchGrayMaze(), and wshedApply().

◆ lheapDestroy()

void lheapDestroy ( L_HEAP **  plh,
l_int32  freeflag 
)

lheapDestroy()

Parameters
[in,out]plhwill be set to null before returning
[in]freeflagTRUE to free each remaining struct in the array
Returns
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.

Definition at line 152 of file heap.c.

References L_Heap::array, and L_Heap::n.

◆ lheapExtendArray()

static l_int32 lheapExtendArray ( L_HEAP lh)
static

lheapExtendArray()

Parameters
[in]lhheap
Returns
0 if OK, 1 on error

Definition at line 220 of file heap.c.

References L_Heap::array, L_Heap::nalloc, and reallocNew().

Referenced by lheapAdd().

◆ lheapGetCount()

l_int32 lheapGetCount ( L_HEAP lh)

lheapGetCount()

Parameters
[in]lhheap
Returns
count, or 0 on error

Definition at line 273 of file heap.c.

References L_Heap::n.

Referenced by lheapSwapDown(), and pixcmapGenerateFromMedianCuts().

◆ lheapGetElement()

void* lheapGetElement ( L_HEAP lh,
l_int32  index 
)

lheapGetElement()

Parameters
[in]lhheap
[in]indexinto the internal heap array
Returns
ptr to the element at array[index], or NULL on error
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.

◆ lheapPrint()

l_ok lheapPrint ( FILE *  fp,
L_HEAP lh 
)

lheapPrint()

Parameters
[in]fpfile stream
[in]lhheap
Returns
0 if OK; 1 on error

Definition at line 549 of file heap.c.

References L_Heap::array, L_Heap::n, and L_Heap::nalloc.

◆ lheapRemove()

void* lheapRemove ( L_HEAP lh)

lheapRemove()

Parameters
[in]lhheap
Returns
ptr to item popped from the root of the heap, or NULL if the heap is empty or on error

Definition at line 243 of file heap.c.

References L_Heap::array, lheapSwapDown(), and L_Heap::n.

Referenced by pixcmapGenerateFromMedianCuts().

◆ lheapSort()

l_ok lheapSort ( L_HEAP lh)

lheapSort()

Parameters
[in]lhheap, with internal array
Returns
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.

Definition at line 327 of file heap.c.

References lheapSwapUp(), and L_Heap::n.

Referenced by lheapSortStrictOrder().

◆ lheapSortStrictOrder()

l_ok lheapSortStrictOrder ( L_HEAP lh)

lheapSortStrictOrder()

Parameters
[in]lhheap, with internal array
Returns
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.

Definition at line 359 of file heap.c.

References lheapSort(), and L_Heap::n.

◆ lheapSwapDown()

static l_ok lheapSwapDown ( L_HEAP lh)
static

lheapSwapDown()

Parameters
[in]lhheap
Returns
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).

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().

◆ lheapSwapUp()

static l_ok lheapSwapUp ( L_HEAP lh,
l_int32  index 
)
static

lheapSwapUp()

Parameters
[in]lhheap
[in]indexof array corresponding to node to be swapped up
Returns
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.

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().

Variable Documentation

◆ InitialPtrArraySize

const l_int32 InitialPtrArraySize = 20
static

n'importe quoi

Definition at line 89 of file heap.c.