![]() |
Leptonica
1.82.0
Image processing and image analysis suite
|
#include "allheaders.h"
Go to the source code of this file.
Functions | |
L_AMAP * | l_amapCreate (l_int32 keytype) |
RB_TYPE * | l_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_NODE * | l_amapGetFirst (L_AMAP *m) |
L_AMAP_NODE * | l_amapGetNext (L_AMAP_NODE *n) |
L_AMAP_NODE * | l_amapGetLast (L_AMAP *m) |
L_AMAP_NODE * | l_amapGetPrev (L_AMAP_NODE *n) |
l_int32 | l_amapSize (L_AMAP *m) |
L_ASET * | l_asetCreate (l_int32 keytype) |
RB_TYPE * | l_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_NODE * | l_asetGetFirst (L_ASET *s) |
L_ASET_NODE * | l_asetGetNext (L_ASET_NODE *n) |
L_ASET_NODE * | l_asetGetLast (L_ASET *s) |
L_ASET_NODE * | l_asetGetPrev (L_ASET_NODE *n) |
l_int32 | l_asetSize (L_ASET *s) |
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.