1 /*====================================================================*
2 - Copyright (C) 2001 Leptonica. All rights reserved.
3 -
4 - Redistribution and use in source and binary forms, with or without
5 - modification, are permitted provided that the following conditions
6 - are met:
7 - 1. Redistributions of source code must retain the above copyright
8 - notice, this list of conditions and the following disclaimer.
9 - 2. Redistributions in binary form must reproduce the above
10 - copyright notice, this list of conditions and the following
11 - disclaimer in the documentation and/or other materials
12 - provided with the distribution.
13 -
14 - THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
15 - ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
16 - LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
17 - A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL ANY
18 - CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
19 - EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
20 - PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
21 - PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
22 - OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
23 - NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
24 - SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
25 *====================================================================*/
26
27 /*!
28 * \file map.c
29 * <pre>
30 *
31 * This is an interface for map and set functions, based on using
32 * red-black binary search trees. Because these trees are sorted,
33 * they are O(nlogn) to build. They allow logn insertion, find
34 * and deletion of elements.
35 *
36 * Both the map and set are ordered by key value, with unique keys.
37 * For the map, the elements are key/value pairs.
38 * For the set we only store unique, ordered keys, and the value
39 * (set to 0 in the implementation) is ignored.
40 *
41 * The keys for the map and set can be any of the three types in the
42 * l_rbtree_keytype enum. The values stored can be any of the four
43 * types in the rb_type union.
44 *
45 * In-order forward and reverse iterators are provided for maps and sets.
46 * To forward iterate over the map for any type of key (in this example,
47 * uint32), extracting integer values:
48 *
49 * L_AMAP *m = l_amapCreate(L_UINT_TYPE);
50 * [add elements to the map ...]
51 * L_AMAP_NODE *n = l_amapGetFirst(m);
52 * while (n) {
53 * l_int32 val = n->value.itype;
54 * // do something ...
55 * n = l_amapGetNext(n);
56 * }
57 *
58 * If the nodes are deleted during the iteration:
59 *
60 * L_AMAP *m = l_amapCreate(L_UINT_TYPE);
61 * [add elements to the map ...]
62 * L_AMAP_NODE *n = l_amapGetFirst(m);
63 * L_AMAP_NODE *nn;
64 * while (n) {
65 * nn = l_amapGetNext(n);
66 * l_int32 val = n->value.itype;
67 * l_uint32 key = n->key.utype;
68 * // do something ...
69 * l_amapDelete(m, n->key);
70 * n = nn;
71 * }
72 *
73 * See prog/maptest.c and prog/settest.c for more examples of usage.
74 *
75 * Interface to (a) map using a general key and storing general values
76 * L_AMAP *l_amapCreate()
77 * RB_TYPE *l_amapFind()
78 * void l_amapInsert()
79 * void l_amapDelete()
80 * void l_amapDestroy()
81 * L_AMAP_NODE *l_amapGetFirst()
82 * L_AMAP_NODE *l_amapGetNext()
83 * L_AMAP_NODE *l_amapGetLast()
84 * L_AMAP_NODE *l_amapGetPrev()
85 * l_int32 l_amapSize()
86 *
87 * Interface to (a) set using a general key
88 * L_ASET *l_asetCreate()
89 * RB_TYPE *l_asetFind()
90 * void l_asetInsert()
91 * void l_asetDelete()
92 * void l_asetDestroy()
93 * L_ASET_NODE *l_asetGetFirst()
94 * L_ASET_NODE *l_asetGetNext()
95 * L_ASET_NODE *l_asetGetLast()
96 * L_ASET_NODE *l_asetGetPrev()
97 * l_int32 l_asetSize()
98 * </pre>
99 */
100
101 #include "allheaders.h"
102
103 /* ------------------------------------------------------------- *
104 * Interface to Map *
105 * ------------------------------------------------------------- */
106 L_AMAP *
l_amapCreate(l_int32 keytype)107 l_amapCreate(l_int32 keytype)
108 {
109 PROCNAME("l_amapCreate");
110
111 if (keytype != L_INT_TYPE && keytype != L_UINT_TYPE &&
112 keytype != L_FLOAT_TYPE)
113 return (L_AMAP *)ERROR_PTR("invalid keytype", procName, NULL);
114
115 L_AMAP *m = (L_AMAP *)LEPT_CALLOC(1, sizeof(L_AMAP));
116 m->keytype = keytype;
117 return m;
118 }
119
120 RB_TYPE *
l_amapFind(L_AMAP * m,RB_TYPE key)121 l_amapFind(L_AMAP *m,
122 RB_TYPE key)
123 {
124 return l_rbtreeLookup(m, key);
125 }
126
127 void
l_amapInsert(L_AMAP * m,RB_TYPE key,RB_TYPE value)128 l_amapInsert(L_AMAP *m,
129 RB_TYPE key,
130 RB_TYPE value)
131 {
132 return l_rbtreeInsert(m, key, value);
133 }
134
135 void
l_amapDelete(L_AMAP * m,RB_TYPE key)136 l_amapDelete(L_AMAP *m,
137 RB_TYPE key)
138 {
139 l_rbtreeDelete(m, key);
140 }
141
142 void
l_amapDestroy(L_AMAP ** pm)143 l_amapDestroy(L_AMAP **pm)
144 {
145 l_rbtreeDestroy(pm);
146 }
147
148 L_AMAP_NODE *
l_amapGetFirst(L_AMAP * m)149 l_amapGetFirst(L_AMAP *m)
150 {
151 return l_rbtreeGetFirst(m);
152 }
153
154 L_AMAP_NODE *
l_amapGetNext(L_AMAP_NODE * n)155 l_amapGetNext(L_AMAP_NODE *n)
156 {
157 return l_rbtreeGetNext(n);
158 }
159
160 L_AMAP_NODE *
l_amapGetLast(L_AMAP * m)161 l_amapGetLast(L_AMAP *m)
162 {
163 return l_rbtreeGetLast(m);
164 }
165
166 L_AMAP_NODE *
l_amapGetPrev(L_AMAP_NODE * n)167 l_amapGetPrev(L_AMAP_NODE *n)
168 {
169 return l_rbtreeGetPrev(n);
170 }
171
172 l_int32
l_amapSize(L_AMAP * m)173 l_amapSize(L_AMAP *m)
174 {
175 return l_rbtreeGetCount(m);
176 }
177
178
179 /* ------------------------------------------------------------- *
180 * Interface to Set *
181 * ------------------------------------------------------------- */
182 L_ASET *
l_asetCreate(l_int32 keytype)183 l_asetCreate(l_int32 keytype)
184 {
185 PROCNAME("l_asetCreate");
186
187 if (keytype != L_INT_TYPE && keytype != L_UINT_TYPE &&
188 keytype != L_FLOAT_TYPE)
189 return (L_ASET *)ERROR_PTR("invalid keytype", procName, NULL);
190
191 L_ASET *s = (L_ASET *)LEPT_CALLOC(1, sizeof(L_ASET));
192 s->keytype = keytype;
193 return s;
194 }
195
196 /*
197 * l_asetFind()
198 *
199 * This returns NULL if not found, non-null if it is. In the latter
200 * case, the value stored in the returned pointer has no significance.
201 */
202 RB_TYPE *
l_asetFind(L_ASET * s,RB_TYPE key)203 l_asetFind(L_ASET *s,
204 RB_TYPE key)
205 {
206 return l_rbtreeLookup(s, key);
207 }
208
209 void
l_asetInsert(L_ASET * s,RB_TYPE key)210 l_asetInsert(L_ASET *s,
211 RB_TYPE key)
212 {
213 RB_TYPE value;
214
215 value.itype = 0; /* meaningless */
216 return l_rbtreeInsert(s, key, value);
217 }
218
219 void
l_asetDelete(L_ASET * s,RB_TYPE key)220 l_asetDelete(L_ASET *s,
221 RB_TYPE key)
222 {
223 l_rbtreeDelete(s, key);
224 }
225
226 void
l_asetDestroy(L_ASET ** ps)227 l_asetDestroy(L_ASET **ps)
228 {
229 l_rbtreeDestroy(ps);
230 }
231
232 L_ASET_NODE *
l_asetGetFirst(L_ASET * s)233 l_asetGetFirst(L_ASET *s)
234 {
235 return l_rbtreeGetFirst(s);
236 }
237
238 L_ASET_NODE *
l_asetGetNext(L_ASET_NODE * n)239 l_asetGetNext(L_ASET_NODE *n)
240 {
241 return l_rbtreeGetNext(n);
242 }
243
244 L_ASET_NODE *
l_asetGetLast(L_ASET * s)245 l_asetGetLast(L_ASET *s)
246 {
247 return l_rbtreeGetLast(s);
248 }
249
250 L_ASET_NODE *
l_asetGetPrev(L_ASET_NODE * n)251 l_asetGetPrev(L_ASET_NODE *n)
252 {
253 return l_rbtreeGetPrev(n);
254 }
255
256 l_int32
l_asetSize(L_ASET * s)257 l_asetSize(L_ASET *s)
258 {
259 return l_rbtreeGetCount(s);
260 }
261