heap.c

Go to the documentation of this file.

/*====================================================================*
 -  Copyright (C) 2001 Leptonica.  All rights reserved.
 -
 -  Redistribution and use in source and binary forms, with or without
 -  modification, are permitted provided that the following conditions
 -  are met:
 -  1. Redistributions of source code must retain the above copyright
 -     notice, this list of conditions and the following disclaimer.
 -  2. Redistributions in binary form must reproduce the above
 -     copyright notice, this list of conditions and the following
 -     disclaimer in the documentation and/or other materials
 -     provided with the distribution.
 -
 -  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 -  ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 -  LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 -  A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL ANY
 -  CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 -  EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 -  PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
 -  PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
 -  OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
 -  NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 -  SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *====================================================================*/
 
#ifdef HAVE_CONFIG_H
#include <config_auto.h>
#endif  /* HAVE_CONFIG_H */
 
#include <string.h>
#include "allheaders.h"
 
    /* Bounds on initial array size */
static const l_uint32  MaxPtrArraySize = 100000;
static const l_int32 InitialPtrArraySize = 20;      
#define SWAP_ITEMS(i, j)       { void *tempitem = lh->array[(i)]; \
                                 lh->array[(i)] = lh->array[(j)]; \
                                 lh->array[(j)] = tempitem; }
 
    /* Static 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 create/destroy                           *
 *--------------------------------------------------------------------------*/
L_HEAP *
lheapCreate(l_int32  n,
            l_int32  direction)
{
L_HEAP  *lh;
 
    PROCNAME("lheapCreate");
 
    if (n < InitialPtrArraySize || n > MaxPtrArraySize)
        n = InitialPtrArraySize;
 
        /* Allocate ptr array and initialize counters. */
    lh = (L_HEAP *)LEPT_CALLOC(1, sizeof(L_HEAP));
    if ((lh->array = (void **)LEPT_CALLOC(n, sizeof(void *))) == NULL) {
        lheapDestroy(&lh, FALSE);
        return (L_HEAP *)ERROR_PTR("ptr array not made", procName, NULL);
    }
    lh->nalloc = n;
    lh->n = 0;
    lh->direction = direction;
    return lh;
}
 
 
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\n", procName);
        return;
    }
    if ((lh = *plh) == NULL)
        return;
 
    if (freeflag) {  /* free each struct in the array */
        for (i = 0; i < lh->n; i++)
            LEPT_FREE(lh->array[i]);
    } else if (lh->n > 0) {  /* freeflag == FALSE but elements exist on array */
        L_WARNING("memory leak of %d items in lheap!\n", procName, lh->n);
    }
 
    if (lh->array)
        LEPT_FREE(lh->array);
    LEPT_FREE(lh);
    *plh = NULL;
}
 
/*--------------------------------------------------------------------------*
 *                Operations to add/remove to/from the heap                 *
 *--------------------------------------------------------------------------*/
l_ok
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) {
        if (lheapExtendArray(lh))
            return ERROR_INT("extension failed", procName, 1);
    }
 
        /* Add the item */
    lh->array[lh->n] = item;
    lh->n++;
 
        /* Restore the heap */
    lheapSwapUp(lh, lh->n - 1);
    return 0;
}
 
 
static 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;
}
 
 
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;
}
 
 
/*--------------------------------------------------------------------------*
 *                            Other accessors                               *
 *--------------------------------------------------------------------------*/
l_int32
lheapGetCount(L_HEAP  *lh)
{
    PROCNAME("lheapGetCount");
 
    if (!lh)
        return ERROR_INT("lh not defined", procName, 0);
 
    return lh->n;
}
 
 
void *
lheapGetElement(L_HEAP  *lh,
                l_int32  index)
{
    PROCNAME("lheapGetElement");
 
    if (!lh)
        return ERROR_PTR("lh not defined", procName, NULL);
    if (index < 0 || index >= lh->n)
        return ERROR_PTR("invalid index", procName, NULL);
 
    return (void *)lh->array[index];
}
 
 
/*--------------------------------------------------------------------------*
 *                                 Heap sort                                *
 *--------------------------------------------------------------------------*/
l_ok
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;
}
 
 
l_ok
lheapSortStrictOrder(L_HEAP  *lh)
{
l_int32  i, index, size;
 
  PROCNAME("lheapSortStrictOrder");
 
  if (!lh)
      return ERROR_INT("lh not defined", procName, 1);
 
      /* Start from a sorted heap */
  lheapSort(lh);
 
  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;
}
 
 
/*--------------------------------------------------------------------------*
 *                         Low-level heap operations                        *
 *--------------------------------------------------------------------------*/
static l_ok
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;
}
 
 
static l_ok
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 exist; 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 exist; 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;
}
 
 
/*---------------------------------------------------------------------*
 *                            Debug output                             *
 *---------------------------------------------------------------------*/
l_ok
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;
}