/*====================================================================*
- 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.
*====================================================================*/
/*!
* \file map.c
*
*
* This is an interface for map and set functions, based on using
* red-black binary search trees. Because these trees are sorted,
* they are O(nlogn) to build. They allow logn insertion, find
* and deletion of elements.
*
* Both the map and set are ordered by key value, with unique keys.
* For the map, the elements are key/value pairs.
* For the set we only store unique, ordered keys, and the value
* (set to 0 in the implementation) is ignored.
*
* The keys for the map and set can be any of the three types in the
* l_rbtree_keytype enum. The values stored can be any of the four
* types in the rb_type union.
*
* In-order forward and reverse iterators are provided for maps and sets.
* To forward iterate over the map for any type of key (in this example,
* uint32), extracting integer values:
*
* L_AMAP *m = l_amapCreate(L_UINT_TYPE);
* [add elements to the map ...]
* L_AMAP_NODE *n = l_amapGetFirst(m);
* while (n) {
* l_int32 val = n->value.itype;
* // do something ...
* n = l_amapGetNext(n);
* }
*
* If the nodes are deleted during the iteration:
*
* L_AMAP *m = l_amapCreate(L_UINT_TYPE);
* [add elements to the map ...]
* L_AMAP_NODE *n = l_amapGetFirst(m);
* L_AMAP_NODE *nn;
* while (n) {
* nn = l_amapGetNext(n);
* l_int32 val = n->value.itype;
* l_uint32 key = n->key.utype;
* // do something ...
* l_amapDelete(m, n->key);
* n = nn;
* }
*
* See prog/maptest.c and prog/settest.c for more examples of usage.
*
* Interface to (a) map using a general key and storing general values
* L_AMAP *l_amapCreate()
* RB_TYPE *l_amapFind()
* void l_amapInsert()
* void l_amapDelete()
* void l_amapDestroy()
* L_AMAP_NODE *l_amapGetFirst()
* L_AMAP_NODE *l_amapGetNext()
* L_AMAP_NODE *l_amapGetLast()
* L_AMAP_NODE *l_amapGetPrev()
* l_int32 l_amapSize()
*
* Interface to (a) set using a general key
* L_ASET *l_asetCreate()
* RB_TYPE *l_asetFind()
* void l_asetInsert()
* void l_asetDelete()
* void l_asetDestroy()
* L_ASET_NODE *l_asetGetFirst()
* L_ASET_NODE *l_asetGetNext()
* L_ASET_NODE *l_asetGetLast()
* L_ASET_NODE *l_asetGetPrev()
* l_int32 l_asetSize()
*
*/
#ifdef HAVE_CONFIG_H
#include
#endif /* HAVE_CONFIG_H */
#include "allheaders.h"
/* ------------------------------------------------------------- *
* Interface to Map *
* ------------------------------------------------------------- */
L_AMAP *
l_amapCreate(l_int32 keytype)
{
L_AMAP *m;
PROCNAME("l_amapCreate");
if (keytype != L_INT_TYPE && keytype != L_UINT_TYPE &&
keytype != L_FLOAT_TYPE)
return (L_AMAP *)ERROR_PTR("invalid keytype", procName, NULL);
m = (L_AMAP *)LEPT_CALLOC(1, sizeof(L_AMAP));
m->keytype = keytype;
return m;
}
RB_TYPE *
l_amapFind(L_AMAP *m,
RB_TYPE key)
{
return l_rbtreeLookup(m, key);
}
void
l_amapInsert(L_AMAP *m,
RB_TYPE key,
RB_TYPE value)
{
l_rbtreeInsert(m, key, value);
}
void
l_amapDelete(L_AMAP *m,
RB_TYPE key)
{
l_rbtreeDelete(m, key);
}
void
l_amapDestroy(L_AMAP **pm)
{
l_rbtreeDestroy(pm);
}
L_AMAP_NODE *
l_amapGetFirst(L_AMAP *m)
{
return l_rbtreeGetFirst(m);
}
L_AMAP_NODE *
l_amapGetNext(L_AMAP_NODE *n)
{
return l_rbtreeGetNext(n);
}
L_AMAP_NODE *
l_amapGetLast(L_AMAP *m)
{
return l_rbtreeGetLast(m);
}
L_AMAP_NODE *
l_amapGetPrev(L_AMAP_NODE *n)
{
return l_rbtreeGetPrev(n);
}
l_int32
l_amapSize(L_AMAP *m)
{
return l_rbtreeGetCount(m);
}
/* ------------------------------------------------------------- *
* Interface to Set *
* ------------------------------------------------------------- */
L_ASET *
l_asetCreate(l_int32 keytype)
{
L_ASET *s;
PROCNAME("l_asetCreate");
if (keytype != L_INT_TYPE && keytype != L_UINT_TYPE &&
keytype != L_FLOAT_TYPE)
return (L_ASET *)ERROR_PTR("invalid keytype", procName, NULL);
s = (L_ASET *)LEPT_CALLOC(1, sizeof(L_ASET));
s->keytype = keytype;
return s;
}
/*
* l_asetFind()
*
* This returns NULL if not found, non-null if it is. In the latter
* case, the value stored in the returned pointer has no significance.
*/
RB_TYPE *
l_asetFind(L_ASET *s,
RB_TYPE key)
{
return l_rbtreeLookup(s, key);
}
void
l_asetInsert(L_ASET *s,
RB_TYPE key)
{
RB_TYPE value;
value.itype = 0; /* meaningless */
l_rbtreeInsert(s, key, value);
}
void
l_asetDelete(L_ASET *s,
RB_TYPE key)
{
l_rbtreeDelete(s, key);
}
void
l_asetDestroy(L_ASET **ps)
{
l_rbtreeDestroy(ps);
}
L_ASET_NODE *
l_asetGetFirst(L_ASET *s)
{
return l_rbtreeGetFirst(s);
}
L_ASET_NODE *
l_asetGetNext(L_ASET_NODE *n)
{
return l_rbtreeGetNext(n);
}
L_ASET_NODE *
l_asetGetLast(L_ASET *s)
{
return l_rbtreeGetLast(s);
}
L_ASET_NODE *
l_asetGetPrev(L_ASET_NODE *n)
{
return l_rbtreeGetPrev(n);
}
l_int32
l_asetSize(L_ASET *s)
{
return l_rbtreeGetCount(s);
}