sarray2.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"
 
/*----------------------------------------------------------------------*
 *                                   Sort                               *
 *----------------------------------------------------------------------*/
SARRAY *
sarraySort(SARRAY  *saout,
           SARRAY  *sain,
           l_int32  sortorder)
{
char   **array;
char    *tmp;
l_int32  n, i, j, gap;
 
    PROCNAME("sarraySort");
 
    if (!sain)
        return (SARRAY *)ERROR_PTR("sain not defined", procName, NULL);
 
        /* Make saout if necessary; otherwise do in-place */
    if (!saout)
        saout = sarrayCopy(sain);
    else if (sain != saout)
        return (SARRAY *)ERROR_PTR("invalid: not in-place", procName, NULL);
    array = saout->array;  /* operate directly on the array */
    n = sarrayGetCount(saout);
 
        /* Shell sort */
    for (gap = n/2; gap > 0; gap = gap / 2) {
        for (i = gap; i < n; i++) {
            for (j = i - gap; j >= 0; j -= gap) {
                if ((sortorder == L_SORT_INCREASING &&
                     stringCompareLexical(array[j], array[j + gap])) ||
                    (sortorder == L_SORT_DECREASING &&
                     stringCompareLexical(array[j + gap], array[j])))
                {
                    tmp = array[j];
                    array[j] = array[j + gap];
                    array[j + gap] = tmp;
                }
            }
        }
    }
 
    return saout;
}
 
 
SARRAY *
sarraySortByIndex(SARRAY  *sain,
                  NUMA    *naindex)
{
char    *str;
l_int32  i, n, index;
SARRAY  *saout;
 
    PROCNAME("sarraySortByIndex");
 
    if (!sain)
        return (SARRAY *)ERROR_PTR("sain not defined", procName, NULL);
    if (!naindex)
        return (SARRAY *)ERROR_PTR("naindex not defined", procName, NULL);
 
    n = sarrayGetCount(sain);
    saout = sarrayCreate(n);
    for (i = 0; i < n; i++) {
        numaGetIValue(naindex, i, &index);
        str = sarrayGetString(sain, index, L_COPY);
        sarrayAddString(saout, str, L_INSERT);
    }
 
    return saout;
}
 
 
l_int32
stringCompareLexical(const char *str1,
                     const char *str2)
{
l_int32  i, len1, len2, len;
 
    PROCNAME("sarrayCompareLexical");
 
    if (!str1)
        return ERROR_INT("str1 not defined", procName, 1);
    if (!str2)
        return ERROR_INT("str2 not defined", procName, 1);
 
    len1 = strlen(str1);
    len2 = strlen(str2);
    len = L_MIN(len1, len2);
 
    for (i = 0; i < len; i++) {
        if (str1[i] == str2[i])
            continue;
        if (str1[i] > str2[i])
            return 1;
        else
            return 0;
    }
 
    if (len1 > len2)
        return 1;
    else
        return 0;
}
 
 
/*----------------------------------------------------------------------*
 *                   Set operations using aset (rbtree)                 *
 *----------------------------------------------------------------------*/
L_ASET *
l_asetCreateFromSarray(SARRAY  *sa)
{
char     *str;
l_int32   i, n;
l_uint64  hash;
L_ASET   *set;
RB_TYPE   key;
 
    PROCNAME("l_asetCreateFromSarray");
 
    if (!sa)
        return (L_ASET *)ERROR_PTR("sa not defined", procName, NULL);
 
    set = l_asetCreate(L_UINT_TYPE);
    n = sarrayGetCount(sa);
    for (i = 0; i < n; i++) {
        str = sarrayGetString(sa, i, L_NOCOPY);
        l_hashStringToUint64Fast(str, &hash);
        key.utype = hash;
        l_asetInsert(set, key);
    }
 
    return set;
}
 
 
l_ok
sarrayRemoveDupsByAset(SARRAY   *sas,
                       SARRAY  **psad)
{
char     *str;
l_int32   i, n;
l_uint64  hash;
L_ASET   *set;
RB_TYPE   key;
SARRAY   *sad;
 
    PROCNAME("sarrayRemoveDupsByAset");
 
    if (!psad)
        return ERROR_INT("&sad not defined", procName, 1);
    *psad = NULL;
    if (!sas)
        return ERROR_INT("sas not defined", procName, 1);
 
    set = l_asetCreate(L_UINT_TYPE);
    sad = sarrayCreate(0);
    *psad = sad;
    n = sarrayGetCount(sas);
    for (i = 0; i < n; i++) {
        str = sarrayGetString(sas, i, L_NOCOPY);
        l_hashStringToUint64Fast(str, &hash);
        key.utype = hash;
        if (!l_asetFind(set, key)) {
            sarrayAddString(sad, str, L_COPY);
            l_asetInsert(set, key);
        }
    }
 
    l_asetDestroy(&set);
    return 0;
}
 
 
l_ok
sarrayUnionByAset(SARRAY   *sa1,
                  SARRAY   *sa2,
                  SARRAY  **psad)
{
SARRAY  *sa3;
 
    PROCNAME("sarrayUnionByAset");
 
    if (!psad)
        return ERROR_INT("&sad not defined", procName, 1);
    *psad = NULL;
    if (!sa1)
        return ERROR_INT("sa1 not defined", procName, 1);
    if (!sa2)
        return ERROR_INT("sa2 not defined", procName, 1);
 
        /* Join */
    sa3 = sarrayCopy(sa1);
    if (sarrayJoin(sa3, sa2) == 1) {
        sarrayDestroy(&sa3);
        return ERROR_INT("join failed for sa3", procName, 1);
    }
 
        /* Eliminate duplicates */
    sarrayRemoveDupsByAset(sa3, psad);
    sarrayDestroy(&sa3);
    return 0;
}
 
 
l_ok
sarrayIntersectionByAset(SARRAY   *sa1,
                         SARRAY   *sa2,
                         SARRAY  **psad)
{
char     *str;
l_int32   n1, n2, i, n;
l_uint64  hash;
L_ASET   *set1, *set2;
RB_TYPE   key;
SARRAY   *sa_small, *sa_big, *sad;
 
    PROCNAME("sarrayIntersectionByAset");
 
    if (!psad)
        return ERROR_INT("&sad not defined", procName, 1);
    *psad = NULL;
    if (!sa1)
        return ERROR_INT("sa1 not defined", procName, 1);
    if (!sa2)
        return ERROR_INT("sa2 not defined", procName, 1);
 
        /* Put the elements of the biggest array into a set */
    n1 = sarrayGetCount(sa1);
    n2 = sarrayGetCount(sa2);
    sa_small = (n1 < n2) ? sa1 : sa2;   /* do not destroy sa_small */
    sa_big = (n1 < n2) ? sa2 : sa1;   /* do not destroy sa_big */
    set1 = l_asetCreateFromSarray(sa_big);
 
        /* Build up the intersection of strings */
    sad = sarrayCreate(0);
    *psad = sad;
    n = sarrayGetCount(sa_small);
    set2 = l_asetCreate(L_UINT_TYPE);
    for (i = 0; i < n; i++) {
        str = sarrayGetString(sa_small, i, L_NOCOPY);
        l_hashStringToUint64Fast(str, &hash);
        key.utype = hash;
        if (l_asetFind(set1, key) && !l_asetFind(set2, key)) {
            sarrayAddString(sad, str, L_COPY);
            l_asetInsert(set2, key);
        }
    }
 
    l_asetDestroy(&set1);
    l_asetDestroy(&set2);
    return 0;
}
 
 
/*----------------------------------------------------------------------*
 *                          Hashmap operations                          *
 *----------------------------------------------------------------------*/
L_HASHMAP *
l_hmapCreateFromSarray(SARRAY  *sa)
{
l_int32      i, n;
l_uint64     key;
char        *str;
L_HASHITEM  *hitem;
L_HASHMAP   *hmap;
 
    PROCNAME("l_hmapCreateFromSarray");
 
    if (!sa)
        return (L_HASHMAP *)ERROR_PTR("sa not defined", procName, NULL);
 
    n = sarrayGetCount(sa);
    if ((hmap = l_hmapCreate(0.51 * n, 2)) == NULL)
        return (L_HASHMAP *)ERROR_PTR("hmap not made", procName, NULL);
    for (i = 0; i < n; i++) {
        str = sarrayGetString(sa, i, L_NOCOPY);
        l_hashStringToUint64Fast(str, &key);
        hitem = l_hmapLookup(hmap, key, i, L_HMAP_CREATE);
    }
    return hmap;
}
 
 
l_ok
sarrayRemoveDupsByHmap(SARRAY      *sas,
                       SARRAY     **psad,
                       L_HASHMAP  **phmap)
{
l_int32      i, tabsize;
l_uint64     key;
char        *str;
SARRAY      *sad;
L_HASHITEM  *hitem;
L_HASHMAP   *hmap;
 
    PROCNAME("sarrayRemoveDupsByHmap");
 
    if (phmap) *phmap = NULL;
    if (!psad)
        return ERROR_INT("&sad not defined", procName, 1);
    *psad = NULL;
    if (!sas)
        return ERROR_INT("sas not defined", procName, 1);
 
        /* Traverse the hashtable lists */
    if ((hmap = l_hmapCreateFromSarray(sas)) == NULL)
        return ERROR_INT("hmap not made", procName, 1);
    sad = sarrayCreate(0);
    *psad = sad;
    tabsize = hmap->tabsize;
    for (i = 0; i < tabsize; i++) {
        hitem = hmap->hashtab[i];
        while (hitem) {
            str = sarrayGetString(sas, hitem->val, L_COPY);
            sarrayAddString(sad, str, L_INSERT);
            hitem = hitem->next;
        }
    }
 
    if (phmap)
        *phmap = hmap;
    else
        l_hmapDestroy(&hmap);
    return 0;
}
 
 
l_ok
sarrayUnionByHmap(SARRAY   *sa1,
                  SARRAY   *sa2,
                  SARRAY  **psad)
{
SARRAY  *sa3;
 
    PROCNAME("l_hmapUnionSarray");
 
    if (!psad)
        return ERROR_INT("&sad not defined", procName, 1);
    *psad = NULL;
    if (!sa1)
        return ERROR_INT("sa1 not defined", procName, 1);
    if (!sa2)
        return ERROR_INT("sa2 not defined", procName, 1);
 
    sa3 = sarrayCopy(sa1);
    if (sarrayJoin(sa3, sa2) == 1) {
        sarrayDestroy(&sa3);
        return ERROR_INT("sa3 join failed", procName, 1);
    }
    sarrayRemoveDupsByHmap(sa3, psad, NULL);
    sarrayDestroy(&sa3);
    return 0;
}
 
 
l_ok
sarrayIntersectionByHmap(SARRAY   *sa1,
                         SARRAY   *sa2,
                         SARRAY  **psad)
{
l_int32      i, n1, n2, n;
l_uint64     key;
char        *str;
SARRAY      *sa_small, *sa_big, *sa3, *sad;
L_HASHITEM  *hitem;
L_HASHMAP   *hmap;
 
    PROCNAME("sarrayIntersectionByHmap");
 
    if (!psad)
        return ERROR_INT("&sad not defined", procName, 1);
    *psad = NULL;
    if (!sa1)
        return ERROR_INT("sa1 not defined", procName, 1);
    if (!sa2)
        return ERROR_INT("sa2 not defined", procName, 1);
 
        /* Make a hashmap for the elements of the biggest array */
    n1 = sarrayGetCount(sa1);
    n2 = sarrayGetCount(sa2);
    sa_small = (n1 < n2) ? sa1 : sa2;   /* do not destroy sa_small */
    sa_big = (n1 < n2) ? sa2 : sa1;   /* do not destroy sa_big */
    if ((hmap = l_hmapCreateFromSarray(sa_big)) == NULL)
        return ERROR_INT("hmap not made", procName, 1);
 
        /* Remove duplicates from the smallest array.  Alternatively,
         * we can skip this step and avoid counting duplicates in
         * sa_small by modifying the count fields in the sa_big hashitems;
         * e.g., see l_hmapIntersectionDna(). */
    sarrayRemoveDupsByHmap(sa_small, &sa3, NULL);
 
        /* Go through sa3, the set of strings derived from the smallest array,
         * hashing into the big array table.  Any string found belongs to both,
         * so add it to the output array. */
    sad = sarrayCreate(0);
    *psad = sad;
    n = sarrayGetCount(sa3);
    for (i = 0; i < n; i++) {
        str = sarrayGetString(sa3, i, L_NOCOPY);
        l_hashStringToUint64Fast(str, &key);
        hitem = l_hmapLookup(hmap, key, i, L_HMAP_CHECK);
        if (hitem)
            sarrayAddString(sad, str, L_COPY);
    }
    l_hmapDestroy(&hmap);
    sarrayDestroy(&sa3);
    return 0;
}
 
 
/*----------------------------------------------------------------------*
 *                      Miscellaneous operations                        *
 *----------------------------------------------------------------------*/
SARRAY *
sarrayGenerateIntegers(l_int32  n)
{
char     buf[32];
l_int32  i;
SARRAY  *sa;
 
    PROCNAME("sarrayGenerateIntegers");
 
    if ((sa = sarrayCreate(n)) == NULL)
        return (SARRAY *)ERROR_PTR("sa not made", procName, NULL);
    for (i = 0; i < n; i++) {
        snprintf(buf, sizeof(buf), "%d", i);
        sarrayAddString(sa, buf, L_COPY);
    }
    return sa;
}
 
 
l_ok
sarrayLookupCSKV(SARRAY      *sa,
                 const char  *keystring,
                 char       **pvalstring)
{
char    *key, *val, *str;
l_int32  i, n;
SARRAY  *sa1;
 
    PROCNAME("sarrayLookupCSKV");
 
    if (!pvalstring)
        return ERROR_INT("&valstring not defined", procName, 1);
    *pvalstring = NULL;
    if (!sa)
        return ERROR_INT("sa not defined", procName, 1);
    if (!keystring)
        return ERROR_INT("keystring not defined", procName, 1);
 
    n = sarrayGetCount(sa);
    for (i = 0; i < n; i++) {
        str = sarrayGetString(sa, i, L_NOCOPY);
        sa1 = sarrayCreate(2);
        sarraySplitString(sa1, str, ",");
        if (sarrayGetCount(sa1) != 2) {
            sarrayDestroy(&sa1);
            continue;
        }
        key = sarrayGetString(sa1, 0, L_NOCOPY);
        val = sarrayGetString(sa1, 1, L_NOCOPY);
        if (!strcmp(key, keystring)) {
            *pvalstring = stringNew(val);
            sarrayDestroy(&sa1);
            return 0;
        }
        sarrayDestroy(&sa1);
    }
 
    return 0;
}