Leptonica  1.82.0
Image processing and image analysis suite
map.c File Reference
#include "allheaders.h"

Go to the source code of this file.

Functions

L_AMAPl_amapCreate (l_int32 keytype)
 
RB_TYPEl_amapFind (L_AMAP *m, RB_TYPE key)
 
void l_amapInsert (L_AMAP *m, RB_TYPE key, RB_TYPE value)
 
void l_amapDelete (L_AMAP *m, RB_TYPE key)
 
void l_amapDestroy (L_AMAP **pm)
 
L_AMAP_NODEl_amapGetFirst (L_AMAP *m)
 
L_AMAP_NODEl_amapGetNext (L_AMAP_NODE *n)
 
L_AMAP_NODEl_amapGetLast (L_AMAP *m)
 
L_AMAP_NODEl_amapGetPrev (L_AMAP_NODE *n)
 
l_int32 l_amapSize (L_AMAP *m)
 
L_ASETl_asetCreate (l_int32 keytype)
 
RB_TYPEl_asetFind (L_ASET *s, RB_TYPE key)
 
void l_asetInsert (L_ASET *s, RB_TYPE key)
 
void l_asetDelete (L_ASET *s, RB_TYPE key)
 
void l_asetDestroy (L_ASET **ps)
 
L_ASET_NODEl_asetGetFirst (L_ASET *s)
 
L_ASET_NODEl_asetGetNext (L_ASET_NODE *n)
 
L_ASET_NODEl_asetGetLast (L_ASET *s)
 
L_ASET_NODEl_asetGetPrev (L_ASET_NODE *n)
 
l_int32 l_asetSize (L_ASET *s)
 

Detailed Description


 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()

Definition in file map.c.