| /*====================================================================* |
| - Copyright (C) 2001 Leptonica. All rights reserved. |
| - This software is distributed in the hope that it will be |
| - useful, but with NO WARRANTY OF ANY KIND. |
| - No author or distributor accepts responsibility to anyone for the |
| - consequences of using this software, or for whether it serves any |
| - particular purpose or works at all, unless he or she says so in |
| - writing. Everyone is granted permission to copy, modify and |
| - redistribute this source code, for commercial or non-commercial |
| - purposes, with the following restrictions: (1) the origin of this |
| - source code must not be misrepresented; (2) modified versions must |
| - be plainly marked as such; and (3) this notice may not be removed |
| - or altered from any source or modified source distribution. |
| *====================================================================*/ |
| |
| /* |
| * heap.c |
| * |
| * Create/Destroy L_Heap |
| * L_HEAP *lheapCreate() |
| * void *lheapDestroy() |
| * |
| * Operations to add/remove to/from the heap |
| * l_int32 lheapAdd() |
| * l_int32 lheapExtendArray() |
| * void *lheapRemove() |
| * |
| * Heap operations |
| * l_int32 lheapSwapUp() |
| * l_int32 lheapSwapDown() |
| * l_int32 lheapSort() |
| * l_int32 lheapSortStrictOrder() |
| * |
| * Accessors |
| * l_int32 lheapGetCount() |
| * |
| * 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 necesary 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. ------------------------------ |
| */ |
| |
| #include <stdio.h> |
| #include <string.h> |
| #include <stdlib.h> |
| #include "allheaders.h" |
| |
| static const l_int32 MIN_BUFFER_SIZE = 20; /* n'importe quoi */ |
| static const l_int32 INITIAL_BUFFER_ARRAYSIZE = 128; /* n'importe quoi */ |
| |
| #define SWAP_ITEMS(i, j) { void *tempitem = lh->array[(i)]; \ |
| lh->array[(i)] = lh->array[(j)]; \ |
| lh->array[(j)] = tempitem; } |
| |
| |
| /*--------------------------------------------------------------------------* |
| * L_Heap create/destroy * |
| *--------------------------------------------------------------------------*/ |
| /*! |
| * 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 |
| */ |
| L_HEAP * |
| lheapCreate(l_int32 nalloc, |
| l_int32 direction) |
| { |
| L_HEAP *lh; |
| |
| PROCNAME("lheapCreate"); |
| |
| if (nalloc < MIN_BUFFER_SIZE) |
| nalloc = MIN_BUFFER_SIZE; |
| |
| /* Allocate ptr array and initialize counters. */ |
| if ((lh = (L_HEAP *)CALLOC(1, sizeof(L_HEAP))) == NULL) |
| return (L_HEAP *)ERROR_PTR("lh not made", procName, NULL); |
| if ((lh->array = (void **)CALLOC(nalloc, sizeof(void *))) == NULL) |
| return (L_HEAP *)ERROR_PTR("ptr array not made", procName, NULL); |
| lh->nalloc = nalloc; |
| lh->n = 0; |
| lh->direction = direction; |
| return lh; |
| } |
| |
| |
| /*! |
| * 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. |
| */ |
| void |
| lheapDestroy(L_HEAP **plh, |
| l_int32 freeflag) |
| { |
| l_int32 i; |
| L_HEAP *lh; |
| |
| PROCNAME("lheapDestroy"); |
| |
| if (plh == NULL) { |
| L_WARNING("ptr address is NULL", procName); |
| return; |
| } |
| if ((lh = *plh) == NULL) |
| return; |
| |
| if (freeflag) { /* free each struct in the array */ |
| for (i = 0; i < lh->n; i++) |
| FREE(lh->array[i]); |
| } |
| else if (lh->n > 0) /* freeflag == FALSE but elements exist on array */ |
| L_WARNING_INT("memory leak of %d items in lheap!", procName, lh->n); |
| |
| if (lh->array) |
| FREE(lh->array); |
| FREE(lh); |
| *plh = NULL; |
| |
| return; |
| } |
| |
| /*--------------------------------------------------------------------------* |
| * Accessors * |
| *--------------------------------------------------------------------------*/ |
| /*! |
| * lheapAdd() |
| * |
| * Input: lheap |
| * item to be added to the tail of the heap |
| * Return: 0 if OK, 1 on error |
| */ |
| l_int32 |
| lheapAdd(L_HEAP *lh, |
| void *item) |
| { |
| PROCNAME("lheapAdd"); |
| |
| if (!lh) |
| return ERROR_INT("lh not defined", procName, 1); |
| if (!item) |
| return ERROR_INT("item not defined", procName, 1); |
| |
| /* If necessary, expand the allocated array by a factor of 2 */ |
| if (lh->n >= lh->nalloc) |
| lheapExtendArray(lh); |
| |
| /* Add the item */ |
| lh->array[lh->n] = item; |
| lh->n++; |
| |
| /* Restore the heap */ |
| lheapSwapUp(lh, lh->n - 1); |
| return 0; |
| } |
| |
| |
| /*! |
| * lheapExtendArray() |
| * |
| * Input: lheap |
| * Return: 0 if OK, 1 on error |
| */ |
| l_int32 |
| lheapExtendArray(L_HEAP *lh) |
| { |
| PROCNAME("lheapExtendArray"); |
| |
| if (!lh) |
| return ERROR_INT("lh not defined", procName, 1); |
| |
| if ((lh->array = (void **)reallocNew((void **)&lh->array, |
| sizeof(void *) * lh->nalloc, |
| 2 * sizeof(void *) * lh->nalloc)) == NULL) |
| return ERROR_INT("new ptr array not returned", procName, 1); |
| |
| lh->nalloc = 2 * lh->nalloc; |
| return 0; |
| } |
| |
| |
| /*! |
| * lheapRemove() |
| * |
| * Input: lheap |
| * Return: ptr to item popped from the root of the heap, |
| * or null if the heap is empty or on error |
| */ |
| void * |
| lheapRemove(L_HEAP *lh) |
| { |
| void *item; |
| |
| PROCNAME("lheapRemove"); |
| |
| if (!lh) |
| return (void *)ERROR_PTR("lh not defined", procName, NULL); |
| |
| if (lh->n == 0) |
| return NULL; |
| |
| item = lh->array[0]; |
| lh->array[0] = lh->array[lh->n - 1]; /* move last to the head */ |
| lh->array[lh->n - 1] = NULL; /* set ptr to null */ |
| lh->n--; |
| |
| lheapSwapDown(lh); /* restore the heap */ |
| return item; |
| } |
| |
| |
| /*! |
| * lheapGetCount() |
| * |
| * Input: lheap |
| * Return: count, or 0 on error |
| */ |
| l_int32 |
| lheapGetCount(L_HEAP *lh) |
| { |
| PROCNAME("lheapGetCount"); |
| |
| if (!lh) |
| return ERROR_INT("lh not defined", procName, 0); |
| |
| return lh->n; |
| } |
| |
| |
| |
| /*--------------------------------------------------------------------------* |
| * Heap operations * |
| *--------------------------------------------------------------------------*/ |
| /*! |
| * 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. |
| */ |
| l_int32 |
| lheapSwapUp(L_HEAP *lh, |
| l_int32 index) |
| { |
| l_int32 ip; /* index to heap for parent; 1 larger than array index */ |
| l_int32 ic; /* index into heap for child */ |
| l_float32 valp, valc; |
| |
| PROCNAME("lheapSwapUp"); |
| |
| if (!lh) |
| return ERROR_INT("lh not defined", procName, 1); |
| if (index < 0 || index >= lh->n) |
| return ERROR_INT("invalid index", procName, 1); |
| |
| ic = index + 1; /* index into heap: add 1 to array index */ |
| if (lh->direction == L_SORT_INCREASING) { |
| while (1) { |
| if (ic == 1) /* root of heap */ |
| break; |
| ip = ic / 2; |
| valc = *(l_float32 *)(lh->array[ic - 1]); |
| valp = *(l_float32 *)(lh->array[ip - 1]); |
| if (valp <= valc) |
| break; |
| SWAP_ITEMS(ip - 1, ic - 1); |
| ic = ip; |
| } |
| } |
| else { /* lh->direction == L_SORT_DECREASING */ |
| while (1) { |
| if (ic == 1) /* root of heap */ |
| break; |
| ip = ic / 2; |
| valc = *(l_float32 *)(lh->array[ic - 1]); |
| valp = *(l_float32 *)(lh->array[ip - 1]); |
| if (valp >= valc) |
| break; |
| SWAP_ITEMS(ip - 1, ic - 1); |
| ic = ip; |
| } |
| } |
| return 0; |
| } |
| |
| |
| /*! |
| * 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 |
| lheapSwapDown(L_HEAP *lh) |
| { |
| l_int32 ip; /* index to heap for parent; 1 larger than array index */ |
| l_int32 icr, icl; /* index into heap for left/right children */ |
| l_float32 valp, valcl, valcr; |
| |
| PROCNAME("lheapSwapDown"); |
| |
| if (!lh) |
| return ERROR_INT("lh not defined", procName, 1); |
| if (lheapGetCount(lh) < 1) |
| return 0; |
| |
| ip = 1; /* index into top of heap: corresponds to array[0] */ |
| if (lh->direction == L_SORT_INCREASING) { |
| while (1) { |
| icl = 2 * ip; |
| if (icl > lh->n) |
| break; |
| valp = *(l_float32 *)(lh->array[ip - 1]); |
| valcl = *(l_float32 *)(lh->array[icl - 1]); |
| icr = icl + 1; |
| if (icr > lh->n) { /* only a left child; no iters below */ |
| if (valp > valcl) |
| SWAP_ITEMS(ip - 1, icl - 1); |
| break; |
| } |
| else { /* both children present; swap with the smallest if bigger */ |
| valcr = *(l_float32 *)(lh->array[icr - 1]); |
| if (valp <= valcl && valp <= valcr) /* smaller than both */ |
| break; |
| if (valcl <= valcr) { /* left smaller; swap */ |
| SWAP_ITEMS(ip - 1, icl - 1); |
| ip = icl; |
| } |
| else { /* right smaller; swap */ |
| SWAP_ITEMS(ip - 1, icr - 1); |
| ip = icr; |
| } |
| } |
| } |
| } |
| else { /* lh->direction == L_SORT_DECREASING */ |
| while (1) { |
| icl = 2 * ip; |
| if (icl > lh->n) |
| break; |
| valp = *(l_float32 *)(lh->array[ip - 1]); |
| valcl = *(l_float32 *)(lh->array[icl - 1]); |
| icr = icl + 1; |
| if (icr > lh->n) { /* only a left child; no iters below */ |
| if (valp < valcl) |
| SWAP_ITEMS(ip - 1, icl - 1); |
| break; |
| } |
| else { /* both children present; swap with the biggest if smaller */ |
| valcr = *(l_float32 *)(lh->array[icr - 1]); |
| if (valp >= valcl && valp >= valcr) /* bigger than both */ |
| break; |
| if (valcl >= valcr) { /* left bigger; swap */ |
| SWAP_ITEMS(ip - 1, icl - 1); |
| ip = icl; |
| } |
| else { /* right bigger; swap */ |
| SWAP_ITEMS(ip - 1, icr - 1); |
| ip = icr; |
| } |
| } |
| } |
| } |
| |
| return 0; |
| } |
| |
| |
| /*! |
| * 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. |
| */ |
| l_int32 |
| lheapSort(L_HEAP *lh) |
| { |
| l_int32 i; |
| |
| PROCNAME("lheapSort"); |
| |
| if (!lh) |
| return ERROR_INT("lh not defined", procName, 1); |
| |
| for (i = 0; i < lh->n; i++) |
| lheapSwapUp(lh, i); |
| |
| return 0; |
| } |
| |
| |
| /*! |
| * 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. |
| */ |
| l_int32 |
| lheapSortStrictOrder(L_HEAP *lh) |
| { |
| l_int32 i, index, size; |
| |
| PROCNAME("lheapSortStrictOrder"); |
| |
| if (!lh) |
| return ERROR_INT("lh not defined", procName, 1); |
| |
| size = lh->n; /* save the actual size */ |
| for (i = 0; i < size; i++) { |
| index = size - i; |
| SWAP_ITEMS(0, index - 1); |
| lh->n--; /* reduce the apparent heap size by 1 */ |
| lheapSwapDown(lh); |
| } |
| lh->n = size; /* restore the size */ |
| |
| for (i = 0; i < size / 2; i++) /* reverse */ |
| SWAP_ITEMS(i, size - i - 1); |
| |
| return 0; |
| } |
| |
| |
| |
| /*---------------------------------------------------------------------* |
| * Debug output * |
| *---------------------------------------------------------------------*/ |
| /*! |
| * lheapPrint() |
| * |
| * Input: stream |
| * lheap |
| * Return: 0 if OK; 1 on error |
| */ |
| l_int32 |
| lheapPrint(FILE *fp, |
| L_HEAP *lh) |
| { |
| l_int32 i; |
| |
| PROCNAME("lheapPrint"); |
| |
| if (!fp) |
| return ERROR_INT("stream not defined", procName, 1); |
| if (!lh) |
| return ERROR_INT("lh not defined", procName, 1); |
| |
| fprintf(fp, "\n L_Heap: nalloc = %d, n = %d, array = %p\n", |
| lh->nalloc, lh->n, lh->array); |
| for (i = 0; i < lh->n; i++) |
| fprintf(fp, "keyval[%d] = %f\n", i, *(l_float32 *)lh->array[i]); |
| |
| return 0; |
| } |
| |
