Leptonica  1.83.1
Image processing and image analysis suite
dnafunc1.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 
77 #ifdef HAVE_CONFIG_H
78 #include <config_auto.h>
79 #endif /* HAVE_CONFIG_H */
80 
81 #include "allheaders.h"
82 #include "array_internal.h"
83 
84 
85 /*----------------------------------------------------------------------*
86  * Rearrangements *
87  *----------------------------------------------------------------------*/
104 l_ok
106  L_DNA *das,
107  l_int32 istart,
108  l_int32 iend)
109 {
110 l_int32 n, i;
111 l_float64 val;
112 
113  if (!dad)
114  return ERROR_INT("dad not defined", __func__, 1);
115  if (!das)
116  return 0;
117 
118  if (istart < 0)
119  istart = 0;
120  n = l_dnaGetCount(das);
121  if (iend < 0 || iend >= n)
122  iend = n - 1;
123  if (istart > iend)
124  return ERROR_INT("istart > iend; nothing to add", __func__, 1);
125 
126  for (i = istart; i <= iend; i++) {
127  l_dnaGetDValue(das, i, &val);
128  if (l_dnaAddNumber(dad, val) == 1) {
129  L_ERROR("failed to add double at i = %d\n", __func__, i);
130  return 1;
131  }
132 
133  }
134  return 0;
135 }
136 
137 
151 L_DNA *
153 {
154 l_int32 i, nalloc;
155 L_DNA *da, *dad;
156 L_DNA **array;
157 
158  if (!daa)
159  return (L_DNA *)ERROR_PTR("daa not defined", __func__, NULL);
160 
161  nalloc = daa->nalloc;
162  array = daa->dna;
163  dad = l_dnaCreate(0);
164  for (i = 0; i < nalloc; i++) {
165  da = array[i];
166  if (!da) continue;
167  l_dnaJoin(dad, da, 0, -1);
168  }
169 
170  return dad;
171 }
172 
173 
182 L_DNA *
184  l_int32 first,
185  l_int32 last)
186 {
187 l_int32 n, i;
188 l_float64 dval;
189 L_DNA *dad;
190 
191  if (!das)
192  return (L_DNA *)ERROR_PTR("das not defined", __func__, NULL);
193  if ((n = l_dnaGetCount(das)) == 0) {
194  L_WARNING("das is empty\n", __func__);
195  return l_dnaCopy(das);
196  }
197  first = L_MAX(0, first);
198  if (last < 0) last = n - 1;
199  if (first >= n)
200  return (L_DNA *)ERROR_PTR("invalid first", __func__, NULL);
201  if (last >= n) {
202  L_WARNING("last = %d is beyond max index = %d; adjusting\n",
203  __func__, last, n - 1);
204  last = n - 1;
205  }
206  if (first > last)
207  return (L_DNA *)ERROR_PTR("first > last", __func__, NULL);
208 
209  dad = l_dnaCreate(last - first + 1);
210  for (i = first; i <= last; i++) {
211  l_dnaGetDValue(das, i, &dval);
212  l_dnaAddNumber(dad, dval);
213  }
214  return dad;
215 }
216 
217 
218 /*----------------------------------------------------------------------*
219  * Conversion between numa and dna *
220  *----------------------------------------------------------------------*/
227 NUMA *
229 {
230 l_int32 i, n;
231 l_float64 val;
232 NUMA *na;
233 
234  if (!da)
235  return (NUMA *)ERROR_PTR("da not defined", __func__, NULL);
236 
237  n = l_dnaGetCount(da);
238  na = numaCreate(n);
239  for (i = 0; i < n; i++) {
240  l_dnaGetDValue(da, i, &val);
241  numaAddNumber(na, val);
242  }
243  return na;
244 }
245 
246 
253 L_DNA *
255 {
256 l_int32 i, n;
257 l_float32 val;
258 L_DNA *da;
259 
260  if (!na)
261  return (L_DNA *)ERROR_PTR("na not defined", __func__, NULL);
262 
263  n = numaGetCount(na);
264  da = l_dnaCreate(n);
265  for (i = 0; i < n; i++) {
266  numaGetFValue(na, i, &val);
267  l_dnaAddNumber(da, val);
268  }
269  return da;
270 }
271 
272 
273 /*----------------------------------------------------------------------*
274  * Conversion from pix data to dna *
275  *----------------------------------------------------------------------*/
287 L_DNA *
289 {
290 l_int32 i, j, w, h, wpl;
291 l_uint32 *data, *line;
292 L_DNA *da;
293 
294  if (!pix)
295  return (L_DNA *)ERROR_PTR("pix not defined", __func__, NULL);
296  if (pixGetDepth(pix) != 32)
297  return (L_DNA *)ERROR_PTR("pix not 32 bpp", __func__, NULL);
298 
299  pixGetDimensions(pix, &w, &h, NULL);
300  data = pixGetData(pix);
301  wpl = pixGetWpl(pix);
302  da = l_dnaCreate(w * h);
303  for (i = 0; i < h; i++) {
304  line = data + i * wpl;
305  for (j = 0; j < w; j++)
306  l_dnaAddNumber(da, (l_float64)line[j]);
307  }
308  return da;
309 }
310 
311 
312 /*----------------------------------------------------------------------*
313  * Set operations using aset (rbtree) *
314  *----------------------------------------------------------------------*/
321 L_ASET *
323 {
324 l_int32 i, n;
325 l_float64 val;
326 L_ASET *set;
327 RB_TYPE key;
328 
329  if (!da)
330  return (L_ASET *)ERROR_PTR("da not defined", __func__, NULL);
331 
332  set = l_asetCreate(L_FLOAT_TYPE);
333  n = l_dnaGetCount(da);
334  for (i = 0; i < n; i++) {
335  l_dnaGetDValue(da, i, &val);
336  key.ftype = val;
337  l_asetInsert(set, key);
338  }
339 
340  return set;
341 }
342 
343 
351 l_ok
353  L_DNA **pdad)
354 {
355 l_int32 i, n;
356 l_float64 val;
357 L_DNA *dad;
358 L_ASET *set;
359 RB_TYPE key;
360 
361  if (!pdad)
362  return ERROR_INT("&dad not defined", __func__, 1);
363  *pdad = NULL;
364  if (!das)
365  return ERROR_INT("das not defined", __func__, 1);
366 
367  set = l_asetCreate(L_FLOAT_TYPE);
368  dad = l_dnaCreate(0);
369  *pdad = dad;
370  n = l_dnaGetCount(das);
371  for (i = 0; i < n; i++) {
372  l_dnaGetDValue(das, i, &val);
373  key.ftype = val;
374  if (!l_asetFind(set, key)) {
375  l_dnaAddNumber(dad, val);
376  l_asetInsert(set, key);
377  }
378  }
379 
380  l_asetDestroy(&set);
381  return 0;
382 }
383 
384 
401 l_ok
403  L_DNA *da2,
404  L_DNA **pdad)
405 {
406 L_DNA *da3;
407 
408  if (!pdad)
409  return ERROR_INT("&dad not defined", __func__, 1);
410  if (!da1)
411  return ERROR_INT("da1 not defined", __func__, 1);
412  if (!da2)
413  return ERROR_INT("da2 not defined", __func__, 1);
414 
415  /* Join */
416  da3 = l_dnaCopy(da1);
417  if (l_dnaJoin(da3, da2, 0, -1) == 1) {
418  l_dnaDestroy(&da3);
419  return ERROR_INT("join failed for da3", __func__, 1);
420  }
421 
422  /* Eliminate duplicates */
423  l_dnaRemoveDupsByAset(da3, pdad);
424  l_dnaDestroy(&da3);
425  return 0;
426 }
427 
428 
445 l_ok
447  L_DNA *da2,
448  L_DNA **pdad)
449 {
450 l_int32 n1, n2, i, n;
451 l_float64 val;
452 L_ASET *set1, *set2;
453 RB_TYPE key;
454 L_DNA *da_small, *da_big, *dad;
455 
456  if (!pdad)
457  return ERROR_INT("&dad not defined", __func__, 1);
458  *pdad = NULL;
459  if (!da1)
460  return ERROR_INT("&da1 not defined", __func__, 1);
461  if (!da2)
462  return ERROR_INT("&da2 not defined", __func__, 1);
463 
464  /* Put the elements of the largest array into a set */
465  n1 = l_dnaGetCount(da1);
466  n2 = l_dnaGetCount(da2);
467  da_small = (n1 < n2) ? da1 : da2; /* do not destroy da_small */
468  da_big = (n1 < n2) ? da2 : da1; /* do not destroy da_big */
469  set1 = l_asetCreateFromDna(da_big);
470 
471  /* Build up the intersection of doubles */
472  dad = l_dnaCreate(0);
473  *pdad = dad;
474  n = l_dnaGetCount(da_small);
475  set2 = l_asetCreate(L_FLOAT_TYPE);
476  for (i = 0; i < n; i++) {
477  l_dnaGetDValue(da_small, i, &val);
478  key.ftype = val;
479  if (l_asetFind(set1, key) && !l_asetFind(set2, key)) {
480  l_dnaAddNumber(dad, val);
481  l_asetInsert(set2, key);
482  }
483  }
484 
485  l_asetDestroy(&set1);
486  l_asetDestroy(&set2);
487  return 0;
488 }
489 
490 
491 /*--------------------------------------------------------------------------*
492  * Hashmap operations *
493  *--------------------------------------------------------------------------*/
507 L_HASHMAP *
509 {
510 l_int32 i, n;
511 l_uint64 key;
512 l_float64 dval;
513 L_HASHITEM *hitem;
514 L_HASHMAP *hmap;
515 
516  if (!da)
517  return (L_HASHMAP *)ERROR_PTR("da not defined", __func__, NULL);
518 
519  n = l_dnaGetCount(da);
520  hmap = l_hmapCreate(0, 0);
521  for (i = 0; i < n; i++) {
522  l_dnaGetDValue(da, i, &dval);
523  l_hashFloat64ToUint64(dval, &key);
524  hitem = l_hmapLookup(hmap, key, i, L_HMAP_CREATE);
525  }
526  return hmap;
527 }
528 
529 
544 l_ok
546  L_DNA **pdad,
547  L_HASHMAP **phmap)
548 {
549 l_int32 i, tabsize;
550 l_float64 dval;
551 L_DNA *dad;
552 L_HASHITEM *hitem;
553 L_HASHMAP *hmap;
554 
555  if (phmap) *phmap = NULL;
556  if (!pdad)
557  return ERROR_INT("&dad not defined", __func__, 1);
558  *pdad = NULL;
559  if (!das)
560  return ERROR_INT("das not defined", __func__, 1);
561 
562  /* Traverse the hashtable lists */
563  if ((hmap = l_hmapCreateFromDna(das)) == NULL)
564  return ERROR_INT("hmap not made", __func__, 1);
565  dad = l_dnaCreate(0);
566  *pdad = dad;
567  tabsize = hmap->tabsize;
568  for (i = 0; i < tabsize; i++) {
569  hitem = hmap->hashtab[i];
570  while (hitem) {
571  l_dnaGetDValue(das, hitem->val, &dval);
572  l_dnaAddNumber(dad, dval);
573  hitem = hitem->next;
574  }
575  }
576 
577  if (phmap)
578  *phmap = hmap;
579  else
580  l_hmapDestroy(&hmap);
581  return 0;
582 }
583 
584 
598 l_ok
600  L_DNA *da2,
601  L_DNA **pdad)
602 {
603 L_DNA *da3;
604 
605  if (!pdad)
606  return ERROR_INT("&dad not defined", __func__, 1);
607  *pdad = NULL;
608  if (!da1)
609  return ERROR_INT("da1 not defined", __func__, 1);
610  if (!da2)
611  return ERROR_INT("da2 not defined", __func__, 1);
612 
613  da3 = l_dnaCopy(da1);
614  if (l_dnaJoin(da3, da2, 0, -1) == 1) {
615  l_dnaDestroy(&da3);
616  return ERROR_INT("da3 join failed", __func__, 1);
617  }
618  l_dnaRemoveDupsByHmap(da3, pdad, NULL);
619  l_dnaDestroy(&da3);
620  return 0;
621 }
622 
623 
638 l_ok
640  L_DNA *da2,
641  L_DNA **pdad)
642 {
643 l_int32 i, n1, n2, n;
644 l_uint64 key;
645 l_float64 dval;
646 L_DNA *da_small, *da_big, *dad;
647 L_HASHITEM *hitem;
648 L_HASHMAP *hmap;
649 
650  if (!pdad)
651  return ERROR_INT("&dad not defined", __func__, 1);
652  *pdad = NULL;
653  if (!da1)
654  return ERROR_INT("da1 not defined", __func__, 1);
655  if (!da2)
656  return ERROR_INT("da2 not defined", __func__, 1);
657 
658  /* Make a hashmap for the elements of the biggest array */
659  n1 = l_dnaGetCount(da1);
660  n2 = l_dnaGetCount(da2);
661  da_small = (n1 < n2) ? da1 : da2; /* do not destroy da_small */
662  da_big = (n1 < n2) ? da2 : da1; /* do not destroy da_big */
663  if ((hmap = l_hmapCreateFromDna(da_big)) == NULL)
664  return ERROR_INT("hmap not made", __func__, 1);
665 
666  /* Go through the smallest array, doing a lookup of its dval into
667  * the big array hashmap. If an hitem is returned, check the count.
668  * If the count is 0, ignore; otherwise, add the dval to the
669  * output dad and set the count in the hitem to 0, indicating
670  * that the dval has already been added. */
671  dad = l_dnaCreate(0);
672  *pdad = dad;
673  n = l_dnaGetCount(da_small);
674  for (i = 0; i < n; i++) {
675  l_dnaGetDValue(da_small, i, &dval);
676  l_hashFloat64ToUint64(dval, &key);
677  hitem = l_hmapLookup(hmap, key, i, L_HMAP_CHECK);
678  if (!hitem || hitem->count == 0)
679  continue;
680  l_dnaAddNumber(dad, dval);
681  hitem->count = 0;
682  }
683  l_hmapDestroy(&hmap);
684  return 0;
685 }
686 
687 
702 l_ok
704  L_DNA **pdav,
705  L_DNA **pdac)
706 {
707 l_int32 i, tabsize;
708 l_float64 dval;
709 L_DNA *dac, *dav;
710 L_HASHITEM *hitem;
711 L_HASHMAP *hmap;
712 
713  if (pdav) *pdav = NULL;
714  if (pdac) *pdac = NULL;
715  if (!das)
716  return ERROR_INT("das not defined", __func__, 1);
717  if (!pdav)
718  return ERROR_INT("&dav not defined", __func__, 1);
719  if (!pdac)
720  return ERROR_INT("&dac not defined", __func__, 1);
721 
722  /* Traverse the hashtable lists */
723  if ((hmap = l_hmapCreateFromDna(das)) == NULL)
724  return ERROR_INT("hmap not made", __func__, 1);
725  dav = l_dnaCreate(0);
726  *pdav = dav;
727  dac = l_dnaCreate(0);
728  *pdac = dac;
729  tabsize = hmap->tabsize;
730  for (i = 0; i < tabsize; i++) {
731  hitem = hmap->hashtab[i];
732  while (hitem) {
733  l_dnaGetDValue(das, hitem->val, &dval);
734  l_dnaAddNumber(dav, dval);
735  l_dnaAddNumber(dac, hitem->count);
736  hitem = hitem->next;
737  }
738  }
739 
740  l_hmapDestroy(&hmap);
741  return 0;
742 }
743 
744 
745 /*----------------------------------------------------------------------*
746  * Miscellaneous operations *
747  *----------------------------------------------------------------------*/
755 L_DNA *
757 {
758 l_int32 i, n, prev, cur;
759 L_DNA *dad;
760 
761  if (!das)
762  return (L_DNA *)ERROR_PTR("das not defined", __func__, NULL);
763  n = l_dnaGetCount(das);
764  dad = l_dnaCreate(n - 1);
765  prev = 0;
766  for (i = 1; i < n; i++) {
767  l_dnaGetIValue(das, i, &cur);
768  l_dnaAddNumber(dad, cur - prev);
769  prev = cur;
770  }
771  return dad;
772 }
773 
L_DNA * l_dnaCreate(l_int32 n)
l_dnaCreate()
Definition: dnabasic.c:179
l_ok l_dnaGetIValue(L_DNA *da, l_int32 index, l_int32 *pival)
l_dnaGetIValue()
Definition: dnabasic.c:693
l_ok l_dnaAddNumber(L_DNA *da, l_float64 val)
l_dnaAddNumber()
Definition: dnabasic.c:430
l_ok l_dnaGetDValue(L_DNA *da, l_int32 index, l_float64 *pval)
l_dnaGetDValue()
Definition: dnabasic.c:660
void l_dnaDestroy(L_DNA **pda)
l_dnaDestroy()
Definition: dnabasic.c:323
L_DNA * l_dnaCopy(L_DNA *da)
l_dnaCopy()
Definition: dnabasic.c:357
l_int32 l_dnaGetCount(L_DNA *da)
l_dnaGetCount()
Definition: dnabasic.c:603
L_DNA * l_dnaSelectRange(L_DNA *das, l_int32 first, l_int32 last)
l_dnaSelectRange()
Definition: dnafunc1.c:183
l_ok l_dnaUnionByAset(L_DNA *da1, L_DNA *da2, L_DNA **pdad)
l_dnaUnionByAset()
Definition: dnafunc1.c:402
l_ok l_dnaUnionByHmap(L_DNA *da1, L_DNA *da2, L_DNA **pdad)
l_dnaUnionByHmap()
Definition: dnafunc1.c:599
NUMA * l_dnaConvertToNuma(L_DNA *da)
l_dnaConvertToNuma()
Definition: dnafunc1.c:228
L_ASET * l_asetCreateFromDna(L_DNA *da)
l_asetCreateFromDna()
Definition: dnafunc1.c:322
L_DNA * l_dnaDiffAdjValues(L_DNA *das)
l_dnaDiffAdjValues()
Definition: dnafunc1.c:756
l_ok l_dnaJoin(L_DNA *dad, L_DNA *das, l_int32 istart, l_int32 iend)
l_dnaJoin()
Definition: dnafunc1.c:105
l_ok l_dnaMakeHistoByHmap(L_DNA *das, L_DNA **pdav, L_DNA **pdac)
l_dnaMakeHistoByHmap()
Definition: dnafunc1.c:703
l_ok l_dnaRemoveDupsByHmap(L_DNA *das, L_DNA **pdad, L_HASHMAP **phmap)
l_dnaRemoveDupsByHmap()
Definition: dnafunc1.c:545
L_DNA * numaConvertToDna(NUMA *na)
numaConvertToDna
Definition: dnafunc1.c:254
L_DNA * l_dnaaFlattenToDna(L_DNAA *daa)
l_dnaaFlattenToDna()
Definition: dnafunc1.c:152
l_ok l_dnaRemoveDupsByAset(L_DNA *das, L_DNA **pdad)
l_dnaRemoveDupsByAset()
Definition: dnafunc1.c:352
l_ok l_dnaIntersectionByAset(L_DNA *da1, L_DNA *da2, L_DNA **pdad)
l_dnaIntersectionByAset()
Definition: dnafunc1.c:446
l_ok l_dnaIntersectionByHmap(L_DNA *da1, L_DNA *da2, L_DNA **pdad)
l_dnaIntersectionByHmap()
Definition: dnafunc1.c:639
L_DNA * pixConvertDataToDna(PIX *pix)
pixConvertDataToDna()
Definition: dnafunc1.c:288
L_HASHMAP * l_hmapCreateFromDna(L_DNA *da)
l_hmapCreateFromDna()
Definition: dnafunc1.c:508
l_ok numaAddNumber(NUMA *na, l_float32 val)
numaAddNumber()
Definition: numabasic.c:460
l_ok numaGetFValue(NUMA *na, l_int32 index, l_float32 *pval)
numaGetFValue()
Definition: numabasic.c:687
NUMA * numaCreate(l_int32 n)
numaCreate()
Definition: numabasic.c:193
l_int32 numaGetCount(NUMA *na)
numaGetCount()
Definition: numabasic.c:630
l_uint32 * pixGetData(PIX *pix)
pixGetData()
Definition: pix1.c:1642
l_ok pixGetDimensions(const PIX *pix, l_int32 *pw, l_int32 *ph, l_int32 *pd)
pixGetDimensions()
Definition: pix1.c:1074
l_int32 nalloc
struct L_Dna ** dna
l_uint64 val
Definition: hashmap.h:117
l_int32 count
Definition: hashmap.h:118
struct L_Hashitem * next
Definition: hashmap.h:119
struct L_Hashitem ** hashtab
Definition: hashmap.h:106
l_int32 tabsize
Definition: hashmap.h:107
Definition: rbtree.h:62
l_ok l_hashFloat64ToUint64(l_float64 val, l_uint64 *phash)
l_hashFloat64ToUint64()
Definition: utils1.c:821