Leptonica  1.83.1
Image processing and image analysis suite
heap.c
Go to the documentation of this file.
1 /*====================================================================*
2  - Copyright (C) 2001 Leptonica. All rights reserved.
3  -
4  - Redistribution and use in source and binary forms, with or without
5  - modification, are permitted provided that the following conditions
6  - are met:
7  - 1. Redistributions of source code must retain the above copyright
8  - notice, this list of conditions and the following disclaimer.
9  - 2. Redistributions in binary form must reproduce the above
10  - copyright notice, this list of conditions and the following
11  - disclaimer in the documentation and/or other materials
12  - provided with the distribution.
13  -
14  - THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
15  - ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
16  - LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
17  - A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL ANY
18  - CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
19  - EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
20  - PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
21  - PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
22  - OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
23  - NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
24  - SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
25  *====================================================================*/
26 
80 #ifdef HAVE_CONFIG_H
81 #include <config_auto.h>
82 #endif /* HAVE_CONFIG_H */
83 
84 #include <string.h>
85 #include "allheaders.h"
86 
87  /* Bounds on initial array size */
88 static const l_uint32 MaxPtrArraySize = 100000;
89 static const l_int32 InitialPtrArraySize = 20;
91 #define SWAP_ITEMS(i, j) { void *tempitem = lh->array[(i)]; \
92  lh->array[(i)] = lh->array[(j)]; \
93  lh->array[(j)] = tempitem; }
94 
95  /* Static functions */
96 static l_int32 lheapExtendArray(L_HEAP *lh);
97 static l_ok lheapSwapUp(L_HEAP *lh, l_int32 index);
98 static l_ok lheapSwapDown(L_HEAP *lh);
99 
100 
101 /*--------------------------------------------------------------------------*
102  * L_Heap create/destroy *
103  *--------------------------------------------------------------------------*/
111 L_HEAP *
112 lheapCreate(l_int32 n,
113  l_int32 direction)
114 {
115 L_HEAP *lh;
116 
117  if (n < InitialPtrArraySize || n > MaxPtrArraySize)
119 
120  /* Allocate ptr array and initialize counters. */
121  lh = (L_HEAP *)LEPT_CALLOC(1, sizeof(L_HEAP));
122  if ((lh->array = (void **)LEPT_CALLOC(n, sizeof(void *))) == NULL) {
123  lheapDestroy(&lh, FALSE);
124  return (L_HEAP *)ERROR_PTR("ptr array not made", __func__, NULL);
125  }
126  lh->nalloc = n;
127  lh->n = 0;
128  lh->direction = direction;
129  return lh;
130 }
131 
132 
151 void
153  l_int32 freeflag)
154 {
155 l_int32 i;
156 L_HEAP *lh;
157 
158  if (plh == NULL) {
159  L_WARNING("ptr address is NULL\n", __func__);
160  return;
161  }
162  if ((lh = *plh) == NULL)
163  return;
164 
165  if (freeflag) { /* free each struct in the array */
166  for (i = 0; i < lh->n; i++)
167  LEPT_FREE(lh->array[i]);
168  } else if (lh->n > 0) { /* freeflag == FALSE but elements exist on array */
169  L_WARNING("memory leak of %d items in lheap!\n", __func__, lh->n);
170  }
171 
172  if (lh->array)
173  LEPT_FREE(lh->array);
174  LEPT_FREE(lh);
175  *plh = NULL;
176 }
177 
178 /*--------------------------------------------------------------------------*
179  * Operations to add/remove to/from the heap *
180  *--------------------------------------------------------------------------*/
188 l_ok
190  void *item)
191 {
192  if (!lh)
193  return ERROR_INT("lh not defined", __func__, 1);
194  if (!item)
195  return ERROR_INT("item not defined", __func__, 1);
196 
197  /* If necessary, expand the allocated array by a factor of 2 */
198  if (lh->n >= lh->nalloc) {
199  if (lheapExtendArray(lh))
200  return ERROR_INT("extension failed", __func__, 1);
201  }
202 
203  /* Add the item */
204  lh->array[lh->n] = item;
205  lh->n++;
206 
207  /* Restore the heap */
208  lheapSwapUp(lh, lh->n - 1);
209  return 0;
210 }
211 
212 
219 static l_int32
221 {
222  if (!lh)
223  return ERROR_INT("lh not defined", __func__, 1);
224 
225  if ((lh->array = (void **)reallocNew((void **)&lh->array,
226  sizeof(void *) * lh->nalloc,
227  2 * sizeof(void *) * lh->nalloc)) == NULL)
228  return ERROR_INT("new ptr array not returned", __func__, 1);
229 
230  lh->nalloc = 2 * lh->nalloc;
231  return 0;
232 }
233 
234 
242 void *
244 {
245 void *item;
246 
247  if (!lh)
248  return (void *)ERROR_PTR("lh not defined", __func__, NULL);
249 
250  if (lh->n == 0)
251  return NULL;
252 
253  item = lh->array[0];
254  lh->array[0] = lh->array[lh->n - 1]; /* move last to the head */
255  lh->array[lh->n - 1] = NULL; /* set ptr to null */
256  lh->n--;
257 
258  lheapSwapDown(lh); /* restore the heap */
259  return item;
260 }
261 
262 
263 /*--------------------------------------------------------------------------*
264  * Other accessors *
265  *--------------------------------------------------------------------------*/
272 l_int32
274 {
275  if (!lh)
276  return ERROR_INT("lh not defined", __func__, 0);
277 
278  return lh->n;
279 }
280 
281 
298 void *
300  l_int32 index)
301 {
302  if (!lh)
303  return ERROR_PTR("lh not defined", __func__, NULL);
304  if (index < 0 || index >= lh->n)
305  return ERROR_PTR("invalid index", __func__, NULL);
306 
307  return (void *)lh->array[index];
308 }
309 
310 
311 /*--------------------------------------------------------------------------*
312  * Heap sort *
313  *--------------------------------------------------------------------------*/
326 l_ok
328 {
329 l_int32 i;
330 
331  if (!lh)
332  return ERROR_INT("lh not defined", __func__, 1);
333 
334  for (i = 0; i < lh->n; i++)
335  lheapSwapUp(lh, i);
336 
337  return 0;
338 }
339 
340 
358 l_ok
360 {
361 l_int32 i, index, size;
362 
363  if (!lh)
364  return ERROR_INT("lh not defined", __func__, 1);
365 
366  /* Start from a sorted heap */
367  lheapSort(lh);
368 
369  size = lh->n; /* save the actual size */
370  for (i = 0; i < size; i++) {
371  index = size - i;
372  SWAP_ITEMS(0, index - 1);
373  lh->n--; /* reduce the apparent heap size by 1 */
374  lheapSwapDown(lh);
375  }
376  lh->n = size; /* restore the size */
377 
378  for (i = 0; i < size / 2; i++) /* reverse */
379  SWAP_ITEMS(i, size - i - 1);
380 
381  return 0;
382 }
383 
384 
385 /*--------------------------------------------------------------------------*
386  * Low-level heap operations *
387  *--------------------------------------------------------------------------*/
405 static l_ok
407  l_int32 index)
408 {
409 l_int32 ip; /* index to heap for parent; 1 larger than array index */
410 l_int32 ic; /* index into heap for child */
411 l_float32 valp, valc;
412 
413  if (!lh)
414  return ERROR_INT("lh not defined", __func__, 1);
415  if (index < 0 || index >= lh->n)
416  return ERROR_INT("invalid index", __func__, 1);
417 
418  ic = index + 1; /* index into heap: add 1 to array index */
419  if (lh->direction == L_SORT_INCREASING) {
420  while (1) {
421  if (ic == 1) /* root of heap */
422  break;
423  ip = ic / 2;
424  valc = *(l_float32 *)(lh->array[ic - 1]);
425  valp = *(l_float32 *)(lh->array[ip - 1]);
426  if (valp <= valc)
427  break;
428  SWAP_ITEMS(ip - 1, ic - 1);
429  ic = ip;
430  }
431  } else { /* lh->direction == L_SORT_DECREASING */
432  while (1) {
433  if (ic == 1) /* root of heap */
434  break;
435  ip = ic / 2;
436  valc = *(l_float32 *)(lh->array[ic - 1]);
437  valp = *(l_float32 *)(lh->array[ip - 1]);
438  if (valp >= valc)
439  break;
440  SWAP_ITEMS(ip - 1, ic - 1);
441  ic = ip;
442  }
443  }
444  return 0;
445 }
446 
447 
469 static l_ok
471 {
472 l_int32 ip; /* index to heap for parent; 1 larger than array index */
473 l_int32 icr, icl; /* index into heap for left/right children */
474 l_float32 valp, valcl, valcr;
475 
476  if (!lh)
477  return ERROR_INT("lh not defined", __func__, 1);
478  if (lheapGetCount(lh) < 1)
479  return 0;
480 
481  ip = 1; /* index into top of heap: corresponds to array[0] */
482  if (lh->direction == L_SORT_INCREASING) {
483  while (1) {
484  icl = 2 * ip;
485  if (icl > lh->n)
486  break;
487  valp = *(l_float32 *)(lh->array[ip - 1]);
488  valcl = *(l_float32 *)(lh->array[icl - 1]);
489  icr = icl + 1;
490  if (icr > lh->n) { /* only a left child; no iters below */
491  if (valp > valcl)
492  SWAP_ITEMS(ip - 1, icl - 1);
493  break;
494  } else { /* both children exist; swap with the smallest if bigger */
495  valcr = *(l_float32 *)(lh->array[icr - 1]);
496  if (valp <= valcl && valp <= valcr) /* smaller than both */
497  break;
498  if (valcl <= valcr) { /* left smaller; swap */
499  SWAP_ITEMS(ip - 1, icl - 1);
500  ip = icl;
501  } else { /* right smaller; swap */
502  SWAP_ITEMS(ip - 1, icr - 1);
503  ip = icr;
504  }
505  }
506  }
507  } else { /* lh->direction == L_SORT_DECREASING */
508  while (1) {
509  icl = 2 * ip;
510  if (icl > lh->n)
511  break;
512  valp = *(l_float32 *)(lh->array[ip - 1]);
513  valcl = *(l_float32 *)(lh->array[icl - 1]);
514  icr = icl + 1;
515  if (icr > lh->n) { /* only a left child; no iters below */
516  if (valp < valcl)
517  SWAP_ITEMS(ip - 1, icl - 1);
518  break;
519  } else { /* both children exist; swap with the biggest if smaller */
520  valcr = *(l_float32 *)(lh->array[icr - 1]);
521  if (valp >= valcl && valp >= valcr) /* bigger than both */
522  break;
523  if (valcl >= valcr) { /* left bigger; swap */
524  SWAP_ITEMS(ip - 1, icl - 1);
525  ip = icl;
526  } else { /* right bigger; swap */
527  SWAP_ITEMS(ip - 1, icr - 1);
528  ip = icr;
529  }
530  }
531  }
532  }
533 
534  return 0;
535 }
536 
537 
538 /*---------------------------------------------------------------------*
539  * Debug output *
540  *---------------------------------------------------------------------*/
548 l_ok
549 lheapPrint(FILE *fp,
550  L_HEAP *lh)
551 {
552 l_int32 i;
553 
554  if (!fp)
555  return ERROR_INT("stream not defined", __func__, 1);
556  if (!lh)
557  return ERROR_INT("lh not defined", __func__, 1);
558 
559  fprintf(fp, "\n L_Heap: nalloc = %d, n = %d, array = %p\n",
560  lh->nalloc, lh->n, lh->array);
561  for (i = 0; i < lh->n; i++)
562  fprintf(fp, "keyval[%d] = %f\n", i, *(l_float32 *)lh->array[i]);
563 
564  return 0;
565 }
void lheapDestroy(L_HEAP **plh, l_int32 freeflag)
lheapDestroy()
Definition: heap.c:152
static l_ok lheapSwapUp(L_HEAP *lh, l_int32 index)
lheapSwapUp()
Definition: heap.c:406
static const l_int32 InitialPtrArraySize
Definition: heap.c:89
l_ok lheapSortStrictOrder(L_HEAP *lh)
lheapSortStrictOrder()
Definition: heap.c:359
l_ok lheapPrint(FILE *fp, L_HEAP *lh)
lheapPrint()
Definition: heap.c:549
L_HEAP * lheapCreate(l_int32 n, l_int32 direction)
lheapCreate()
Definition: heap.c:112
void * lheapGetElement(L_HEAP *lh, l_int32 index)
lheapGetElement()
Definition: heap.c:299
static l_int32 lheapExtendArray(L_HEAP *lh)
lheapExtendArray()
Definition: heap.c:220
l_ok lheapSort(L_HEAP *lh)
lheapSort()
Definition: heap.c:327
static l_ok lheapSwapDown(L_HEAP *lh)
lheapSwapDown()
Definition: heap.c:470
l_int32 lheapGetCount(L_HEAP *lh)
lheapGetCount()
Definition: heap.c:273
l_ok lheapAdd(L_HEAP *lh, void *item)
lheapAdd()
Definition: heap.c:189
void * lheapRemove(L_HEAP *lh)
lheapRemove()
Definition: heap.c:243
@ L_SORT_INCREASING
Definition: pix.h:522
Definition: heap.h:78
l_int32 direction
Definition: heap.h:82
void ** array
Definition: heap.h:81
l_int32 nalloc
Definition: heap.h:79
l_int32 n
Definition: heap.h:80
void * reallocNew(void **pindata, size_t oldsize, size_t newsize)
reallocNew()
Definition: utils2.c:1262