heap.c

Go to the documentation of this file.

/*====================================================================*
 -  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;
}