Leptonica  1.82.0
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  PROCNAME("lheapCreate");
118 
119  if (n < InitialPtrArraySize || n > MaxPtrArraySize)
121 
122  /* Allocate ptr array and initialize counters. */
123  lh = (L_HEAP *)LEPT_CALLOC(1, sizeof(L_HEAP));
124  if ((lh->array = (void **)LEPT_CALLOC(n, sizeof(void *))) == NULL) {
125  lheapDestroy(&lh, FALSE);
126  return (L_HEAP *)ERROR_PTR("ptr array not made", procName, NULL);
127  }
128  lh->nalloc = n;
129  lh->n = 0;
130  lh->direction = direction;
131  return lh;
132 }
133 
134 
153 void
155  l_int32 freeflag)
156 {
157 l_int32 i;
158 L_HEAP *lh;
159 
160  PROCNAME("lheapDestroy");
161 
162  if (plh == NULL) {
163  L_WARNING("ptr address is NULL\n", procName);
164  return;
165  }
166  if ((lh = *plh) == NULL)
167  return;
168 
169  if (freeflag) { /* free each struct in the array */
170  for (i = 0; i < lh->n; i++)
171  LEPT_FREE(lh->array[i]);
172  } else if (lh->n > 0) { /* freeflag == FALSE but elements exist on array */
173  L_WARNING("memory leak of %d items in lheap!\n", procName, lh->n);
174  }
175 
176  if (lh->array)
177  LEPT_FREE(lh->array);
178  LEPT_FREE(lh);
179  *plh = NULL;
180 }
181 
182 /*--------------------------------------------------------------------------*
183  * Operations to add/remove to/from the heap *
184  *--------------------------------------------------------------------------*/
192 l_ok
194  void *item)
195 {
196  PROCNAME("lheapAdd");
197 
198  if (!lh)
199  return ERROR_INT("lh not defined", procName, 1);
200  if (!item)
201  return ERROR_INT("item not defined", procName, 1);
202 
203  /* If necessary, expand the allocated array by a factor of 2 */
204  if (lh->n >= lh->nalloc) {
205  if (lheapExtendArray(lh))
206  return ERROR_INT("extension failed", procName, 1);
207  }
208 
209  /* Add the item */
210  lh->array[lh->n] = item;
211  lh->n++;
212 
213  /* Restore the heap */
214  lheapSwapUp(lh, lh->n - 1);
215  return 0;
216 }
217 
218 
225 static l_int32
227 {
228  PROCNAME("lheapExtendArray");
229 
230  if (!lh)
231  return ERROR_INT("lh not defined", procName, 1);
232 
233  if ((lh->array = (void **)reallocNew((void **)&lh->array,
234  sizeof(void *) * lh->nalloc,
235  2 * sizeof(void *) * lh->nalloc)) == NULL)
236  return ERROR_INT("new ptr array not returned", procName, 1);
237 
238  lh->nalloc = 2 * lh->nalloc;
239  return 0;
240 }
241 
242 
250 void *
252 {
253 void *item;
254 
255  PROCNAME("lheapRemove");
256 
257  if (!lh)
258  return (void *)ERROR_PTR("lh not defined", procName, NULL);
259 
260  if (lh->n == 0)
261  return NULL;
262 
263  item = lh->array[0];
264  lh->array[0] = lh->array[lh->n - 1]; /* move last to the head */
265  lh->array[lh->n - 1] = NULL; /* set ptr to null */
266  lh->n--;
267 
268  lheapSwapDown(lh); /* restore the heap */
269  return item;
270 }
271 
272 
273 /*--------------------------------------------------------------------------*
274  * Other accessors *
275  *--------------------------------------------------------------------------*/
282 l_int32
284 {
285  PROCNAME("lheapGetCount");
286 
287  if (!lh)
288  return ERROR_INT("lh not defined", procName, 0);
289 
290  return lh->n;
291 }
292 
293 
310 void *
312  l_int32 index)
313 {
314  PROCNAME("lheapGetElement");
315 
316  if (!lh)
317  return ERROR_PTR("lh not defined", procName, NULL);
318  if (index < 0 || index >= lh->n)
319  return ERROR_PTR("invalid index", procName, NULL);
320 
321  return (void *)lh->array[index];
322 }
323 
324 
325 /*--------------------------------------------------------------------------*
326  * Heap sort *
327  *--------------------------------------------------------------------------*/
340 l_ok
342 {
343 l_int32 i;
344 
345  PROCNAME("lheapSort");
346 
347  if (!lh)
348  return ERROR_INT("lh not defined", procName, 1);
349 
350  for (i = 0; i < lh->n; i++)
351  lheapSwapUp(lh, i);
352 
353  return 0;
354 }
355 
356 
374 l_ok
376 {
377 l_int32 i, index, size;
378 
379  PROCNAME("lheapSortStrictOrder");
380 
381  if (!lh)
382  return ERROR_INT("lh not defined", procName, 1);
383 
384  /* Start from a sorted heap */
385  lheapSort(lh);
386 
387  size = lh->n; /* save the actual size */
388  for (i = 0; i < size; i++) {
389  index = size - i;
390  SWAP_ITEMS(0, index - 1);
391  lh->n--; /* reduce the apparent heap size by 1 */
392  lheapSwapDown(lh);
393  }
394  lh->n = size; /* restore the size */
395 
396  for (i = 0; i < size / 2; i++) /* reverse */
397  SWAP_ITEMS(i, size - i - 1);
398 
399  return 0;
400 }
401 
402 
403 /*--------------------------------------------------------------------------*
404  * Low-level heap operations *
405  *--------------------------------------------------------------------------*/
423 static l_ok
425  l_int32 index)
426 {
427 l_int32 ip; /* index to heap for parent; 1 larger than array index */
428 l_int32 ic; /* index into heap for child */
429 l_float32 valp, valc;
430 
431  PROCNAME("lheapSwapUp");
432 
433  if (!lh)
434  return ERROR_INT("lh not defined", procName, 1);
435  if (index < 0 || index >= lh->n)
436  return ERROR_INT("invalid index", procName, 1);
437 
438  ic = index + 1; /* index into heap: add 1 to array index */
439  if (lh->direction == L_SORT_INCREASING) {
440  while (1) {
441  if (ic == 1) /* root of heap */
442  break;
443  ip = ic / 2;
444  valc = *(l_float32 *)(lh->array[ic - 1]);
445  valp = *(l_float32 *)(lh->array[ip - 1]);
446  if (valp <= valc)
447  break;
448  SWAP_ITEMS(ip - 1, ic - 1);
449  ic = ip;
450  }
451  } else { /* lh->direction == L_SORT_DECREASING */
452  while (1) {
453  if (ic == 1) /* root of heap */
454  break;
455  ip = ic / 2;
456  valc = *(l_float32 *)(lh->array[ic - 1]);
457  valp = *(l_float32 *)(lh->array[ip - 1]);
458  if (valp >= valc)
459  break;
460  SWAP_ITEMS(ip - 1, ic - 1);
461  ic = ip;
462  }
463  }
464  return 0;
465 }
466 
467 
489 static l_ok
491 {
492 l_int32 ip; /* index to heap for parent; 1 larger than array index */
493 l_int32 icr, icl; /* index into heap for left/right children */
494 l_float32 valp, valcl, valcr;
495 
496  PROCNAME("lheapSwapDown");
497 
498  if (!lh)
499  return ERROR_INT("lh not defined", procName, 1);
500  if (lheapGetCount(lh) < 1)
501  return 0;
502 
503  ip = 1; /* index into top of heap: corresponds to array[0] */
504  if (lh->direction == L_SORT_INCREASING) {
505  while (1) {
506  icl = 2 * ip;
507  if (icl > lh->n)
508  break;
509  valp = *(l_float32 *)(lh->array[ip - 1]);
510  valcl = *(l_float32 *)(lh->array[icl - 1]);
511  icr = icl + 1;
512  if (icr > lh->n) { /* only a left child; no iters below */
513  if (valp > valcl)
514  SWAP_ITEMS(ip - 1, icl - 1);
515  break;
516  } else { /* both children exist; swap with the smallest if bigger */
517  valcr = *(l_float32 *)(lh->array[icr - 1]);
518  if (valp <= valcl && valp <= valcr) /* smaller than both */
519  break;
520  if (valcl <= valcr) { /* left smaller; swap */
521  SWAP_ITEMS(ip - 1, icl - 1);
522  ip = icl;
523  } else { /* right smaller; swap */
524  SWAP_ITEMS(ip - 1, icr - 1);
525  ip = icr;
526  }
527  }
528  }
529  } else { /* lh->direction == L_SORT_DECREASING */
530  while (1) {
531  icl = 2 * ip;
532  if (icl > lh->n)
533  break;
534  valp = *(l_float32 *)(lh->array[ip - 1]);
535  valcl = *(l_float32 *)(lh->array[icl - 1]);
536  icr = icl + 1;
537  if (icr > lh->n) { /* only a left child; no iters below */
538  if (valp < valcl)
539  SWAP_ITEMS(ip - 1, icl - 1);
540  break;
541  } else { /* both children exist; swap with the biggest if smaller */
542  valcr = *(l_float32 *)(lh->array[icr - 1]);
543  if (valp >= valcl && valp >= valcr) /* bigger than both */
544  break;
545  if (valcl >= valcr) { /* left bigger; swap */
546  SWAP_ITEMS(ip - 1, icl - 1);
547  ip = icl;
548  } else { /* right bigger; swap */
549  SWAP_ITEMS(ip - 1, icr - 1);
550  ip = icr;
551  }
552  }
553  }
554  }
555 
556  return 0;
557 }
558 
559 
560 /*---------------------------------------------------------------------*
561  * Debug output *
562  *---------------------------------------------------------------------*/
570 l_ok
571 lheapPrint(FILE *fp,
572  L_HEAP *lh)
573 {
574 l_int32 i;
575 
576  PROCNAME("lheapPrint");
577 
578  if (!fp)
579  return ERROR_INT("stream not defined", procName, 1);
580  if (!lh)
581  return ERROR_INT("lh not defined", procName, 1);
582 
583  fprintf(fp, "\n L_Heap: nalloc = %d, n = %d, array = %p\n",
584  lh->nalloc, lh->n, lh->array);
585  for (i = 0; i < lh->n; i++)
586  fprintf(fp, "keyval[%d] = %f\n", i, *(l_float32 *)lh->array[i]);
587 
588  return 0;
589 }
l_ok lheapAdd(L_HEAP *lh, void *item)
lheapAdd()
Definition: heap.c:193
l_ok lheapPrint(FILE *fp, L_HEAP *lh)
lheapPrint()
Definition: heap.c:571
void * lheapGetElement(L_HEAP *lh, l_int32 index)
lheapGetElement()
Definition: heap.c:311
l_ok lheapSortStrictOrder(L_HEAP *lh)
lheapSortStrictOrder()
Definition: heap.c:375
void lheapDestroy(L_HEAP **plh, l_int32 freeflag)
lheapDestroy()
Definition: heap.c:154
l_int32 lheapGetCount(L_HEAP *lh)
lheapGetCount()
Definition: heap.c:283
L_HEAP * lheapCreate(l_int32 n, l_int32 direction)
lheapCreate()
Definition: heap.c:112
static l_int32 lheapExtendArray(L_HEAP *lh)
lheapExtendArray()
Definition: heap.c:226
void * lheapRemove(L_HEAP *lh)
lheapRemove()
Definition: heap.c:251
void * reallocNew(void **pindata, size_t oldsize, size_t newsize)
reallocNew()
Definition: utils2.c:1302
static const l_int32 InitialPtrArraySize
Definition: heap.c:89
l_int32 direction
Definition: heap.h:82
static l_ok lheapSwapUp(L_HEAP *lh, l_int32 index)
lheapSwapUp()
Definition: heap.c:424
l_ok lheapSort(L_HEAP *lh)
lheapSort()
Definition: heap.c:341
Definition: heap.h:77
static l_ok lheapSwapDown(L_HEAP *lh)
lheapSwapDown()
Definition: heap.c:490
l_int32 n
Definition: heap.h:80
l_int32 nalloc
Definition: heap.h:79
void ** array
Definition: heap.h:81