hunt.collection.TreeTrie source code

1 /*
2  * Hunt - A refined core library for D programming language.
3  *
4  * Copyright (C) 2018-2019 HuntLabs
5  *
6  * Website: https://www.huntlabs.net/
7  *
8  * Licensed under the Apache-2.0 License.
9  *
10  */
11 
12 module hunt.collection.TreeTrie;
13 
14 import hunt.collection.AbstractTrie;
15 import hunt.collection.ArrayList;
16 import hunt.io.ByteBuffer;
17 import hunt.collection.HashSet;
18 import hunt.collection.List;
19 import hunt.collection.Set;
20 
21 import hunt.Exceptions;
22 import hunt.text;
23 import hunt.util.Common;
24 
25 import std.conv;
26 
27 /* ------------------------------------------------------------ */
28 
29 /**
30  * A Trie string lookup data structure using a tree
31  * <p>
32  * This implementation is always case insensitive and is optimal for a variable
33  * number of fixed strings with few special characters.
34  * </p>
35  * <p>
36  * This Trie is stored in a Tree and is unlimited in capacity
37  * </p>
38  * <p>
39  * <p>
40  * This Trie is not Threadsafe and contains no mutual exclusion or deliberate
41  * memory barriers. It is intended for an ArrayTrie to be built by a single
42  * thread and then used concurrently by multiple threads and not mutated during
43  * that access. If concurrent mutations of the Trie is required external locks
44  * need to be applied.
45  * </p>
46  *
47  * @param (V) the entry type
48  */
49 class TreeTrie(V) : AbstractTrie!(V) {
50     private enum int[] __lookup =
51     [// 0   1   2   3   4   5   6   7   8   9   A   B   C   D   E   F
52    /*0*/-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
53    /*1*/-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
54    /*2*/31, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 26, -1, 27, 30, -1,
55    /*3*/-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 28, 29, -1, -1, -1, -1,
56    /*4*/-1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14,
57    /*5*/15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, -1, -1, -1, -1, -1,
58    /*6*/-1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14,
59    /*7*/15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, -1, -1, -1, -1, -1,
60     ];
61     private enum int INDEX = 32;
62     private TreeTrie!(V)[] _nextIndex;
63     private List!(TreeTrie!(V)) _nextOther;
64     private char _c;
65     private string _key;
66     private V _value;
67 
68     this() {
69         this('\0');
70     }
71 
72     private this(char c) {
73         _nextOther = new ArrayList!(TreeTrie!(V))();
74         _nextIndex = new TreeTrie[INDEX];
75         super(true);
76         this._c = c;
77     }
78 
79     override
80     void clear() {
81         _nextIndex[] = null;
82         _nextOther.clear();
83         _key = null;
84         _value = V.init;
85     }
86 
87     override
88     bool put(string s, V v) {
89         TreeTrie!(V) t = this;
90         size_t limit = s.length;
91         for (size_t k = 0; k < limit; k++) {
92             byte c = s[k];
93 
94             int index = c >= 0 && c < 0x7f ? __lookup[c] : -1;
95             if (index >= 0) {
96                 if (t._nextIndex[index] is null)
97                     t._nextIndex[index] = new TreeTrie!(V)(c);
98                 t = t._nextIndex[index];
99             } else {
100                 TreeTrie!(V) n = null;
101                 for (int i = t._nextOther.size(); i-- > 0; ) {
102                     n = t._nextOther.get(i);
103                     if (n._c == c)
104                         break;
105                     n = null;
106                 }
107                 if (n is null) {
108                     n = new TreeTrie!(V)(c);
109                     t._nextOther.add(n);
110                 }
111                 t = n;
112             }
113         }
114         static if(is(V == class)) {
115             t._key = v is null ? null : s;
116         } else {
117             t._key = v == V.init ? null : s;
118         }
119         
120         t._value = v;
121         return true;
122     }
123 
124     override
125     V get(string s, int offset, int len) {
126         TreeTrie!(V) t = this;
127         for (int i = 0; i < len; i++) {
128             byte c = s.charAt(offset + i);
129             int index = c >= 0 && c < 0x7f ? __lookup[c] : -1;
130             if (index >= 0) {
131                 if (t._nextIndex[index] is null)
132                     return V.init;
133                 t = t._nextIndex[index];
134             } else {
135                 TreeTrie!(V) n = null;
136                 for (int j = t._nextOther.size(); j-- > 0; ) {
137                     n = t._nextOther.get(j);
138                     if (n._c == c)
139                         break;
140                     n = null;
141                 }
142                 if (n is null)
143                     return V.init;
144                 t = n;
145             }
146         }
147         return t._value;
148     }
149 
150     override
151     V get(ByteBuffer b, int offset, int len) {
152         TreeTrie!(V) t = this;
153         for (int i = 0; i < len; i++) {
154             byte c = b.get(offset + i);
155             int index = c >= 0 && c < 0x7f ? __lookup[c] : -1;
156             if (index >= 0) {
157                 if (t._nextIndex[index] is null)
158                     return V.init;
159                 t = t._nextIndex[index];
160             } else {
161                 TreeTrie!(V) n = null;
162                 for (int j = t._nextOther.size(); j-- > 0; ) {
163                     n = t._nextOther.get(j);
164                     if (n._c == c)
165                         break;
166                     n = null;
167                 }
168                 if (n is null)
169                     return V.init;
170                 t = n;
171             }
172         }
173         return t._value;
174     }
175 
176     override
177     V getBest(byte[] b, int offset, int len) {
178         TreeTrie!(V) t = this;
179         for (int i = 0; i < len; i++) {
180             byte c = b[offset + i];
181             int index = c >= 0 && c < 0x7f ? __lookup[c] : -1;
182             if (index >= 0) {
183                 if (t._nextIndex[index] is null)
184                     break;
185                 t = t._nextIndex[index];
186             } else {
187                 TreeTrie!(V) n = null;
188                 for (int j = t._nextOther.size(); j-- > 0; ) {
189                     n = t._nextOther.get(j);
190                     if (n._c == c)
191                         break;
192                     n = null;
193                 }
194                 if (n is null)
195                     break;
196                 t = n;
197             }
198 
199             // Is the next Trie is a match
200             if (t._key !is null) {
201                 // Recurse so we can remember this possibility
202                 V best = t.getBest(b, offset + i + 1, len - i - 1);
203                 
204                 static if(is(V == class)) {
205                     if (best !is null)
206                         return best;
207                 } else {
208                     if (best != V.init)
209                         return best;
210                 }
211 
212                 break;
213             }
214         }
215         return t._value;
216     }
217 
218     override
219     V getBest(string s, int offset, int len) {
220         TreeTrie!(V) t = this;
221         for (int i = 0; i < len; i++) {
222             byte c = cast(byte) (0xff & s[offset + i]);
223             int index = c >= 0 && c < 0x7f ? __lookup[c] : -1;
224             if (index >= 0) {
225                 if (t._nextIndex[index] is null)
226                     break;
227                 t = t._nextIndex[index];
228             } else {
229                 TreeTrie!(V) n = null;
230                 for (int j = t._nextOther.size(); j-- > 0; ) {
231                     n = t._nextOther.get(j);
232                     if (n._c == c)
233                         break;
234                     n = null;
235                 }
236                 if (n is null)
237                     break;
238                 t = n;
239             }
240 
241             // Is the next Trie is a match
242             if (t._key !is null) {
243                 // Recurse so we can remember this possibility
244                 V best = t.getBest(s, offset + i + 1, len - i - 1);
245                 static if(is(V == class)) {
246                     if (best !is null)
247                         return best;
248                 } else {
249                     if (best != V.init)
250                         return best;
251                 }
252                 
253                 break;
254             }
255         }
256         return t._value;
257     }
258 
259     override
260     V getBest(ByteBuffer b, int offset, int len) {
261         if (b.hasArray())
262             return getBest(b.array(), b.arrayOffset() + b.position() + offset, len);
263         return getBestByteBuffer(b, offset, len);
264     }
265 
266     private V getBestByteBuffer(ByteBuffer b, int offset, int len) {
267         TreeTrie!(V) t = this;
268         int pos = b.position() + offset;
269         for (int i = 0; i < len; i++) {
270             byte c = b.get(pos++);
271             int index = c >= 0 && c < 0x7f ? __lookup[c] : -1;
272             if (index >= 0) {
273                 if (t._nextIndex[index] is null)
274                     break;
275                 t = t._nextIndex[index];
276             } else {
277                 TreeTrie!(V) n = null;
278                 for (int j = t._nextOther.size(); j-- > 0; ) {
279                     n = t._nextOther.get(j);
280                     if (n._c == c)
281                         break;
282                     n = null;
283                 }
284                 if (n is null)
285                     break;
286                 t = n;
287             }
288 
289             // Is the next Trie is a match
290             if (t._key !is null) {
291                 // Recurse so we can remember this possibility
292                 V best = t.getBest(b, offset + i + 1, len - i - 1);
293 
294                 static if(is(V == class)) {
295                     if (best !is null)
296                         return best;
297                 } else {
298                     if (best != V.init)
299                         return best;
300                 }
301 
302                 break;
303             }
304         }
305         return t._value;
306     }
307 
308 
309     override
310     string toString() {
311         StringBuilder buf = new StringBuilder();
312         toString(buf, this);
313 
314         if (buf.length == 0)
315             return "{}";
316 
317         buf.setCharAt(0, '{');
318         buf.append('}');
319         return buf.toString();
320     }
321 
322     private static void toString(V)(Appendable ot, TreeTrie!(V) t) {
323         if (t is null) 
324             return;
325 
326         void doAppend() {
327             try {
328                 ot.append(',');
329                 ot.append(t._key);
330                 ot.append('=');
331                 ot.append(t._value.to!string());
332             } catch (IOException e) {
333                 throw new RuntimeException(e);
334             }
335         }
336 
337         static if(is(V == class)) {
338             if (t._value !is null)
339                 doAppend();
340         } else {
341             if (t._value != V.init)
342                 doAppend();
343         }
344 
345         for (int i = 0; i < INDEX; i++) {
346             if (t._nextIndex[i] !is null)
347                 toString(ot, t._nextIndex[i]);
348         }
349         for (int i = t._nextOther.size(); i-- > 0; )
350             toString(ot, t._nextOther.get(i));
351     }
352 
353     override
354     Set!(string) keySet() {
355         Set!(string) keys = new HashSet!string();
356         keySet(keys, this);
357         return keys;
358     }
359 
360     private static void keySet(V)(Set!(string) set, TreeTrie!(V) t) {
361         if (t !is null) {
362             if (t._key !is null)
363                 set.add(t._key);
364 
365             for (int i = 0; i < INDEX; i++) {
366                 if (t._nextIndex[i] !is null)
367                     keySet(set, t._nextIndex[i]);
368             }
369             for (int i = t._nextOther.size(); i-- > 0; )
370                 keySet(set, t._nextOther.get(i));
371         }
372     }
373 
374     override
375     bool isFull() {
376         return false;
377     }
378 
379 }