dnafunc1.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 "allheaders.h"
#include "array_internal.h"
 
 
/*----------------------------------------------------------------------*
 *                            Rearrangements                            *
 *----------------------------------------------------------------------*/
l_ok
l_dnaJoin(L_DNA   *dad,
          L_DNA   *das,
          l_int32  istart,
          l_int32  iend)
{
l_int32    n, i;
l_float64  val;
 
    if (!dad)
        return ERROR_INT("dad not defined", __func__, 1);
    if (!das)
        return 0;
 
    if (istart < 0)
        istart = 0;
    n = l_dnaGetCount(das);
    if (iend < 0 || iend >= n)
        iend = n - 1;
    if (istart > iend)
        return ERROR_INT("istart > iend; nothing to add", __func__, 1);
 
    for (i = istart; i <= iend; i++) {
        l_dnaGetDValue(das, i, &val);
        if (l_dnaAddNumber(dad, val) == 1) {
            L_ERROR("failed to add double at i = %d\n", __func__, i);
            return 1;
        }
 
    }
    return 0;
}
 
 
L_DNA *
l_dnaaFlattenToDna(L_DNAA  *daa)
{
l_int32  i, nalloc;
L_DNA   *da, *dad;
L_DNA  **array;
 
    if (!daa)
        return (L_DNA *)ERROR_PTR("daa not defined", __func__, NULL);
 
    nalloc = daa->nalloc;
    array = daa->dna;
    dad = l_dnaCreate(0);
    for (i = 0; i < nalloc; i++) {
        da = array[i];
        if (!da) continue;
        l_dnaJoin(dad, da, 0, -1);
    }
 
    return dad;
}
 
 
L_DNA *
l_dnaSelectRange(L_DNA   *das,
                 l_int32  first,
                 l_int32  last)
{
l_int32    n, i;
l_float64  dval;
L_DNA     *dad;
 
    if (!das)
        return (L_DNA *)ERROR_PTR("das not defined", __func__, NULL);
    if ((n = l_dnaGetCount(das)) == 0) {
        L_WARNING("das is empty\n", __func__);
        return l_dnaCopy(das);
    }
    first = L_MAX(0, first);
    if (last < 0) last = n - 1;
    if (first >= n)
        return (L_DNA *)ERROR_PTR("invalid first", __func__, NULL);
    if (last >= n) {
        L_WARNING("last = %d is beyond max index = %d; adjusting\n",
                  __func__, last, n - 1);
        last = n - 1;
    }
    if (first > last)
        return (L_DNA *)ERROR_PTR("first > last", __func__, NULL);
 
    dad = l_dnaCreate(last - first + 1);
    for (i = first; i <= last; i++) {
        l_dnaGetDValue(das, i, &dval);
        l_dnaAddNumber(dad, dval);
    }
    return dad;
}
 
 
/*----------------------------------------------------------------------*
 *                   Conversion between numa and dna                    *
 *----------------------------------------------------------------------*/
NUMA *
l_dnaConvertToNuma(L_DNA  *da)
{
l_int32    i, n;
l_float64  val;
NUMA      *na;
 
    if (!da)
        return (NUMA *)ERROR_PTR("da not defined", __func__, NULL);
 
    n = l_dnaGetCount(da);
    na = numaCreate(n);
    for (i = 0; i < n; i++) {
        l_dnaGetDValue(da, i, &val);
        numaAddNumber(na, val);
    }
    return na;
}
 
 
L_DNA *
numaConvertToDna(NUMA  *na)
{
l_int32    i, n;
l_float32  val;
L_DNA     *da;
 
    if (!na)
        return (L_DNA *)ERROR_PTR("na not defined", __func__, NULL);
 
    n = numaGetCount(na);
    da = l_dnaCreate(n);
    for (i = 0; i < n; i++) {
        numaGetFValue(na, i, &val);
        l_dnaAddNumber(da, val);
    }
    return da;
}
 
 
/*----------------------------------------------------------------------*
 *                    Conversion from pix data to dna                   *
 *----------------------------------------------------------------------*/
L_DNA *
pixConvertDataToDna(PIX  *pix)
{
l_int32    i, j, w, h, wpl;
l_uint32  *data, *line;
L_DNA     *da;
 
    if (!pix)
        return (L_DNA *)ERROR_PTR("pix not defined", __func__, NULL);
    if (pixGetDepth(pix) != 32)
        return (L_DNA *)ERROR_PTR("pix not 32 bpp", __func__, NULL);
 
    pixGetDimensions(pix, &w, &h, NULL);
    data = pixGetData(pix);
    wpl = pixGetWpl(pix);
    da = l_dnaCreate(w * h);
    for (i = 0; i < h; i++) {
        line = data + i * wpl;
        for (j = 0; j < w; j++)
            l_dnaAddNumber(da, (l_float64)line[j]);
    }
    return da;
}
 
 
/*----------------------------------------------------------------------*
 *                   Set operations using aset (rbtree)                 *
 *----------------------------------------------------------------------*/
L_ASET *
l_asetCreateFromDna(L_DNA  *da)
{
l_int32    i, n;
l_float64  val;
L_ASET    *set;
RB_TYPE    key;
 
    if (!da)
        return (L_ASET *)ERROR_PTR("da not defined", __func__, NULL);
 
    set = l_asetCreate(L_FLOAT_TYPE);
    n = l_dnaGetCount(da);
    for (i = 0; i < n; i++) {
        l_dnaGetDValue(da, i, &val);
        key.ftype = val;
        l_asetInsert(set, key);
    }
 
    return set;
}
 
 
l_ok
l_dnaRemoveDupsByAset(L_DNA   *das,
                      L_DNA  **pdad)
{
l_int32    i, n;
l_float64  val;
L_DNA     *dad;
L_ASET    *set;
RB_TYPE    key;
 
    if (!pdad)
        return ERROR_INT("&dad not defined", __func__, 1);
    *pdad = NULL;
    if (!das)
        return ERROR_INT("das not defined", __func__, 1);
 
    set = l_asetCreate(L_FLOAT_TYPE);
    dad = l_dnaCreate(0);
    *pdad = dad;
    n = l_dnaGetCount(das);
    for (i = 0; i < n; i++) {
        l_dnaGetDValue(das, i, &val);
        key.ftype = val;
        if (!l_asetFind(set, key)) {
            l_dnaAddNumber(dad, val);
            l_asetInsert(set, key);
        }
    }
 
    l_asetDestroy(&set);
    return 0;
}
 
 
l_ok
l_dnaUnionByAset(L_DNA   *da1,
                 L_DNA   *da2,
                 L_DNA  **pdad)
{
L_DNA  *da3;
 
    if (!pdad)
        return ERROR_INT("&dad not defined", __func__, 1);
    if (!da1)
        return ERROR_INT("da1 not defined", __func__, 1);
    if (!da2)
        return ERROR_INT("da2 not defined", __func__, 1);
 
        /* Join */
    da3 = l_dnaCopy(da1);
    if (l_dnaJoin(da3, da2, 0, -1) == 1) {
        l_dnaDestroy(&da3);
        return ERROR_INT("join failed for da3", __func__, 1);
    }
 
        /* Eliminate duplicates */
    l_dnaRemoveDupsByAset(da3, pdad);
    l_dnaDestroy(&da3);
    return 0;
}
 
 
l_ok
l_dnaIntersectionByAset(L_DNA   *da1,
                        L_DNA   *da2,
                        L_DNA  **pdad)
{
l_int32    n1, n2, i, n;
l_float64  val;
L_ASET    *set1, *set2;
RB_TYPE    key;
L_DNA     *da_small, *da_big, *dad;
 
    if (!pdad)
        return ERROR_INT("&dad not defined", __func__, 1);
    *pdad = NULL;
    if (!da1)
        return ERROR_INT("&da1 not defined", __func__, 1);
    if (!da2)
        return ERROR_INT("&da2 not defined", __func__, 1);
 
        /* Put the elements of the largest array into a set */
    n1 = l_dnaGetCount(da1);
    n2 = l_dnaGetCount(da2);
    da_small = (n1 < n2) ? da1 : da2;   /* do not destroy da_small */
    da_big = (n1 < n2) ? da2 : da1;   /* do not destroy da_big */
    set1 = l_asetCreateFromDna(da_big);
 
        /* Build up the intersection of doubles */
    dad = l_dnaCreate(0);
    *pdad = dad;
    n = l_dnaGetCount(da_small);
    set2 = l_asetCreate(L_FLOAT_TYPE);
    for (i = 0; i < n; i++) {
        l_dnaGetDValue(da_small, i, &val);
        key.ftype = val;
        if (l_asetFind(set1, key) && !l_asetFind(set2, key)) {
            l_dnaAddNumber(dad, val);
            l_asetInsert(set2, key);
        }
    }
 
    l_asetDestroy(&set1);
    l_asetDestroy(&set2);
    return 0;
}
 
 
/*--------------------------------------------------------------------------*
 *                           Hashmap operations                             *
 *--------------------------------------------------------------------------*/
L_HASHMAP *
l_hmapCreateFromDna(L_DNA  *da)
{
l_int32      i, n;
l_uint64     key;
l_float64    dval;
L_HASHMAP   *hmap;
 
    if (!da)
        return (L_HASHMAP *)ERROR_PTR("da not defined", __func__, NULL);
 
    n = l_dnaGetCount(da);
    hmap = l_hmapCreate(0, 0);
    for (i = 0; i < n; i++) {
        l_dnaGetDValue(da, i, &dval);
        l_hashFloat64ToUint64(dval, &key);
        l_hmapLookup(hmap, key, i, L_HMAP_CREATE);
    }
    return hmap;
}
 
 
l_ok
l_dnaRemoveDupsByHmap(L_DNA       *das,
                      L_DNA      **pdad,
                      L_HASHMAP  **phmap)
{
l_int32      i, tabsize;
l_float64    dval;
L_DNA       *dad;
L_HASHITEM  *hitem;
L_HASHMAP   *hmap;
 
    if (phmap) *phmap = NULL;
    if (!pdad)
        return ERROR_INT("&dad not defined", __func__, 1);
    *pdad = NULL;
    if (!das)
        return ERROR_INT("das not defined", __func__, 1);
 
        /* Traverse the hashtable lists */
    if ((hmap = l_hmapCreateFromDna(das)) == NULL)
        return ERROR_INT("hmap not made", __func__, 1);
    dad = l_dnaCreate(0);
    *pdad = dad;
    tabsize = hmap->tabsize;
    for (i = 0; i < tabsize; i++) {
        hitem = hmap->hashtab[i];
        while (hitem) {
            l_dnaGetDValue(das, hitem->val, &dval);
            l_dnaAddNumber(dad, dval);
            hitem = hitem->next;
        }
    }
 
    if (phmap)
        *phmap = hmap;
    else
        l_hmapDestroy(&hmap);
    return 0;
}
 
 
l_ok
l_dnaUnionByHmap(L_DNA   *da1,
                 L_DNA   *da2,
                 L_DNA  **pdad)
{
L_DNA  *da3;
 
    if (!pdad)
        return ERROR_INT("&dad not defined", __func__, 1);
    *pdad = NULL;
    if (!da1)
        return ERROR_INT("da1 not defined", __func__, 1);
    if (!da2)
        return ERROR_INT("da2 not defined", __func__, 1);
 
    da3 = l_dnaCopy(da1);
    if (l_dnaJoin(da3, da2, 0, -1) == 1) {
        l_dnaDestroy(&da3);
        return ERROR_INT("da3 join failed", __func__, 1);
    }
    l_dnaRemoveDupsByHmap(da3, pdad, NULL);
    l_dnaDestroy(&da3);
    return 0;
}
 
 
l_ok
l_dnaIntersectionByHmap(L_DNA   *da1,
                        L_DNA   *da2,
                        L_DNA  **pdad)
{
l_int32      i, n1, n2, n;
l_uint64     key;
l_float64    dval;
L_DNA       *da_small, *da_big, *dad;
L_HASHITEM  *hitem;
L_HASHMAP   *hmap;
 
    if (!pdad)
        return ERROR_INT("&dad not defined", __func__, 1);
    *pdad = NULL;
    if (!da1)
        return ERROR_INT("da1 not defined", __func__, 1);
    if (!da2)
        return ERROR_INT("da2 not defined", __func__, 1);
 
        /* Make a hashmap for the elements of the biggest array */
    n1 = l_dnaGetCount(da1);
    n2 = l_dnaGetCount(da2);
    da_small = (n1 < n2) ? da1 : da2;   /* do not destroy da_small */
    da_big = (n1 < n2) ? da2 : da1;   /* do not destroy da_big */
    if ((hmap = l_hmapCreateFromDna(da_big)) == NULL)
        return ERROR_INT("hmap not made", __func__, 1);
 
        /* Go through the smallest array, doing a lookup of its dval into
         * the big array hashmap.  If an hitem is returned, check the count.
         * If the count is 0, ignore; otherwise, add the dval to the
         * output dad and set the count in the hitem to 0, indicating
         * that the dval has already been added. */
    dad = l_dnaCreate(0);
    *pdad = dad;
    n = l_dnaGetCount(da_small);
    for (i = 0; i < n; i++) {
        l_dnaGetDValue(da_small, i, &dval);
        l_hashFloat64ToUint64(dval, &key);
        hitem = l_hmapLookup(hmap, key, i, L_HMAP_CHECK);
        if (!hitem || hitem->count == 0)
            continue;
        l_dnaAddNumber(dad, dval);
        hitem->count = 0;
    }
    l_hmapDestroy(&hmap);
    return 0;
}
 
 
l_ok
l_dnaMakeHistoByHmap(L_DNA   *das,
                     L_DNA  **pdav,
                     L_DNA  **pdac)
{
l_int32      i, tabsize;
l_float64    dval;
L_DNA       *dac, *dav;
L_HASHITEM  *hitem;
L_HASHMAP   *hmap;
 
    if (pdav) *pdav = NULL;
    if (pdac) *pdac = NULL;
    if (!das)
        return ERROR_INT("das not defined", __func__, 1);
    if (!pdav)
        return ERROR_INT("&dav not defined", __func__, 1);
    if (!pdac)
        return ERROR_INT("&dac not defined", __func__, 1);
 
        /* Traverse the hashtable lists */
    if ((hmap = l_hmapCreateFromDna(das)) == NULL)
        return ERROR_INT("hmap not made", __func__, 1);
    dav = l_dnaCreate(0);
    *pdav = dav;
    dac = l_dnaCreate(0);
    *pdac = dac;
    tabsize = hmap->tabsize;
    for (i = 0; i < tabsize; i++) {
        hitem = hmap->hashtab[i];
        while (hitem) {
            l_dnaGetDValue(das, hitem->val, &dval);
            l_dnaAddNumber(dav, dval);
            l_dnaAddNumber(dac, hitem->count);
            hitem = hitem->next;
        }
    }
 
    l_hmapDestroy(&hmap);
    return 0;
}
 
 
/*----------------------------------------------------------------------*
 *                       Miscellaneous operations                       *
 *----------------------------------------------------------------------*/
L_DNA *
l_dnaDiffAdjValues(L_DNA  *das)
{
l_int32  i, n, prev, cur;
L_DNA   *dad;
 
    if (!das)
        return (L_DNA *)ERROR_PTR("das not defined", __func__, NULL);
    n = l_dnaGetCount(das);
    dad = l_dnaCreate(n - 1);
    prev = 0;
    for (i = 1; i < n; i++) {
        l_dnaGetIValue(das, i, &cur);
        l_dnaAddNumber(dad, cur - prev);
        prev = cur;
    }
    return dad;
}