1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 package org.apache.commons.collections4.trie;
18
19 import static org.junit.jupiter.api.Assertions.assertEquals;
20 import static org.junit.jupiter.api.Assertions.assertFalse;
21 import static org.junit.jupiter.api.Assertions.assertNotNull;
22 import static org.junit.jupiter.api.Assertions.assertNull;
23 import static org.junit.jupiter.api.Assertions.assertSame;
24 import static org.junit.jupiter.api.Assertions.assertThrows;
25 import static org.junit.jupiter.api.Assertions.assertTrue;
26
27 import java.util.ArrayList;
28 import java.util.Arrays;
29 import java.util.ConcurrentModificationException;
30 import java.util.HashSet;
31 import java.util.Iterator;
32 import java.util.Map;
33 import java.util.NoSuchElementException;
34 import java.util.Set;
35 import java.util.SortedMap;
36
37 import org.apache.commons.collections4.Trie;
38 import org.apache.commons.collections4.map.AbstractSortedMapTest;
39 import org.apache.commons.lang3.StringUtils;
40 import org.junit.jupiter.api.Test;
41
42
43
44
45
46
47 public class PatriciaTrieTest<V> extends AbstractSortedMapTest<String, V> {
48
49 @Override
50 public String getCompatibilityVersion() {
51 return "4";
52 }
53
54 @Override
55 public boolean isAllowNullKey() {
56 return false;
57 }
58
59 @Override
60 public SortedMap<String, V> makeObject() {
61 return new PatriciaTrie<>();
62 }
63
64 @Test
65 public void testPrefixMap() {
66 final PatriciaTrie<String> trie = new PatriciaTrie<>();
67
68 final String[] keys = {
69 StringUtils.EMPTY,
70 "Albert", "Xavier", "XyZ", "Anna", "Alien", "Alberto",
71 "Alberts", "Allie", "Alliese", "Alabama", "Banane",
72 "Blabla", "Amber", "Ammun", "Akka", "Akko", "Albertoo",
73 "Amma"
74 };
75
76 for (final String key : keys) {
77 trie.put(key, key);
78 }
79
80 SortedMap<String, String> map;
81 Iterator<String> iterator;
82 Iterator<Map.Entry<String, String>> entryIterator;
83 Map.Entry<String, String> entry;
84
85 map = trie.prefixMap("Al");
86 assertEquals(8, map.size());
87 assertEquals("Alabama", map.firstKey());
88 assertEquals("Alliese", map.lastKey());
89 assertEquals("Albertoo", map.get("Albertoo"));
90 assertNotNull(trie.get("Xavier"));
91 assertNull(map.get("Xavier"));
92 assertNull(trie.get("Alice"));
93 assertNull(map.get("Alice"));
94 iterator = map.values().iterator();
95 assertEquals("Alabama", iterator.next());
96 assertEquals("Albert", iterator.next());
97 assertEquals("Alberto", iterator.next());
98 assertEquals("Albertoo", iterator.next());
99 assertEquals("Alberts", iterator.next());
100 assertEquals("Alien", iterator.next());
101 assertEquals("Allie", iterator.next());
102 assertEquals("Alliese", iterator.next());
103 assertFalse(iterator.hasNext());
104
105 map = trie.prefixMap("Albert");
106 iterator = map.keySet().iterator();
107 assertEquals("Albert", iterator.next());
108 assertEquals("Alberto", iterator.next());
109 assertEquals("Albertoo", iterator.next());
110 assertEquals("Alberts", iterator.next());
111 assertFalse(iterator.hasNext());
112 assertEquals(4, map.size());
113 assertEquals("Albert", map.firstKey());
114 assertEquals("Alberts", map.lastKey());
115 assertNull(trie.get("Albertz"));
116 map.put("Albertz", "Albertz");
117 assertEquals("Albertz", trie.get("Albertz"));
118 assertEquals(5, map.size());
119 assertEquals("Albertz", map.lastKey());
120 iterator = map.keySet().iterator();
121 assertEquals("Albert", iterator.next());
122 assertEquals("Alberto", iterator.next());
123 assertEquals("Albertoo", iterator.next());
124 assertEquals("Alberts", iterator.next());
125 assertEquals("Albertz", iterator.next());
126 assertFalse(iterator.hasNext());
127 assertEquals("Albertz", map.remove("Albertz"));
128
129 map = trie.prefixMap("Alberto");
130 assertEquals(2, map.size());
131 assertEquals("Alberto", map.firstKey());
132 assertEquals("Albertoo", map.lastKey());
133 entryIterator = map.entrySet().iterator();
134 entry = entryIterator.next();
135 assertEquals("Alberto", entry.getKey());
136 assertEquals("Alberto", entry.getValue());
137 entry = entryIterator.next();
138 assertEquals("Albertoo", entry.getKey());
139 assertEquals("Albertoo", entry.getValue());
140 assertFalse(entryIterator.hasNext());
141 trie.put("Albertoad", "Albertoad");
142 assertEquals(3, map.size());
143 assertEquals("Alberto", map.firstKey());
144 assertEquals("Albertoo", map.lastKey());
145 entryIterator = map.entrySet().iterator();
146 entry = entryIterator.next();
147 assertEquals("Alberto", entry.getKey());
148 assertEquals("Alberto", entry.getValue());
149 entry = entryIterator.next();
150 assertEquals("Albertoad", entry.getKey());
151 assertEquals("Albertoad", entry.getValue());
152 entry = entryIterator.next();
153 assertEquals("Albertoo", entry.getKey());
154 assertEquals("Albertoo", entry.getValue());
155 assertFalse(entryIterator.hasNext());
156 assertEquals("Albertoo", trie.remove("Albertoo"));
157 assertEquals("Alberto", map.firstKey());
158 assertEquals("Albertoad", map.lastKey());
159 assertEquals(2, map.size());
160 entryIterator = map.entrySet().iterator();
161 entry = entryIterator.next();
162 assertEquals("Alberto", entry.getKey());
163 assertEquals("Alberto", entry.getValue());
164 entry = entryIterator.next();
165 assertEquals("Albertoad", entry.getKey());
166 assertEquals("Albertoad", entry.getValue());
167 assertFalse(entryIterator.hasNext());
168 assertEquals("Albertoad", trie.remove("Albertoad"));
169 trie.put("Albertoo", "Albertoo");
170
171 map = trie.prefixMap("X");
172 assertEquals(2, map.size());
173 assertFalse(map.containsKey("Albert"));
174 assertTrue(map.containsKey("Xavier"));
175 assertFalse(map.containsKey("Xalan"));
176 iterator = map.values().iterator();
177 assertEquals("Xavier", iterator.next());
178 assertEquals("XyZ", iterator.next());
179 assertFalse(iterator.hasNext());
180
181 map = trie.prefixMap("An");
182 assertEquals(1, map.size());
183 assertEquals("Anna", map.firstKey());
184 assertEquals("Anna", map.lastKey());
185 iterator = map.keySet().iterator();
186 assertEquals("Anna", iterator.next());
187 assertFalse(iterator.hasNext());
188
189 map = trie.prefixMap("Ban");
190 assertEquals(1, map.size());
191 assertEquals("Banane", map.firstKey());
192 assertEquals("Banane", map.lastKey());
193 iterator = map.keySet().iterator();
194 assertEquals("Banane", iterator.next());
195 assertFalse(iterator.hasNext());
196
197 map = trie.prefixMap("Am");
198 assertFalse(map.isEmpty());
199 assertEquals(3, map.size());
200 assertEquals("Amber", trie.remove("Amber"));
201 iterator = map.keySet().iterator();
202 assertEquals("Amma", iterator.next());
203 assertEquals("Ammun", iterator.next());
204 assertFalse(iterator.hasNext());
205 iterator = map.keySet().iterator();
206 map.put("Amber", "Amber");
207 assertEquals(3, map.size());
208
209 final Iterator<String> iterator1 = iterator;
210 assertThrows(ConcurrentModificationException.class, () -> iterator1.next());
211
212 assertEquals("Amber", map.firstKey());
213 assertEquals("Ammun", map.lastKey());
214
215 map = trie.prefixMap("Ak\0");
216 assertTrue(map.isEmpty());
217
218 map = trie.prefixMap("Ak");
219 assertEquals(2, map.size());
220 assertEquals("Akka", map.firstKey());
221 assertEquals("Akko", map.lastKey());
222 map.put("Ak", "Ak");
223 assertEquals("Ak", map.firstKey());
224 assertEquals("Akko", map.lastKey());
225 assertEquals(3, map.size());
226 trie.put("Al", "Al");
227 assertEquals(3, map.size());
228 assertEquals("Ak", map.remove("Ak"));
229 assertEquals("Akka", map.firstKey());
230 assertEquals("Akko", map.lastKey());
231 assertEquals(2, map.size());
232 iterator = map.keySet().iterator();
233 assertEquals("Akka", iterator.next());
234 assertEquals("Akko", iterator.next());
235 assertFalse(iterator.hasNext());
236 assertEquals("Al", trie.remove("Al"));
237
238 map = trie.prefixMap("Akka");
239 assertEquals(1, map.size());
240 assertEquals("Akka", map.firstKey());
241 assertEquals("Akka", map.lastKey());
242 iterator = map.keySet().iterator();
243 assertEquals("Akka", iterator.next());
244 assertFalse(iterator.hasNext());
245
246 map = trie.prefixMap("Ab");
247 assertTrue(map.isEmpty());
248 assertEquals(0, map.size());
249
250 final SortedMap<String, String> map1 = map;
251 assertThrows(NoSuchElementException.class, () -> map1.firstKey());
252
253 final SortedMap<String, String> map2 = map;
254 assertThrows(NoSuchElementException.class, () -> map2.lastKey());
255
256 iterator = map.values().iterator();
257 assertFalse(iterator.hasNext());
258
259 map = trie.prefixMap("Albertooo");
260 assertTrue(map.isEmpty());
261 assertEquals(0, map.size());
262
263 final SortedMap<String, String> map3 = map;
264 assertThrows(NoSuchElementException.class, () -> map3.firstKey(),
265 () -> "got a first key: " + map3.firstKey());
266
267 final SortedMap<String, String> map4 = map;
268 assertThrows(NoSuchElementException.class, () -> map4.lastKey(),
269 () -> "got a last key: " + map4.lastKey());
270
271 iterator = map.values().iterator();
272 assertFalse(iterator.hasNext());
273
274 map = trie.prefixMap(StringUtils.EMPTY);
275 assertSame(trie, map);
276
277 map = trie.prefixMap("\0");
278 assertTrue(map.isEmpty());
279 assertEquals(0, map.size());
280
281 final SortedMap<String, String> map5 = map;
282 assertThrows(NoSuchElementException.class, () -> map5.firstKey(),
283 () -> "got a first key: " + map5.firstKey());
284
285 final SortedMap<String, String> map6 = map;
286 assertThrows(NoSuchElementException.class, () -> map6.lastKey(),
287 () -> "got a last key: " + map6.lastKey());
288
289 iterator = map.values().iterator();
290 assertFalse(iterator.hasNext());
291 }
292
293 @Test
294 public void testPrefixMapClear() {
295 final Trie<String, Integer> trie = new PatriciaTrie<>();
296 trie.put("Anna", 1);
297 trie.put("Anael", 2);
298 trie.put("Analu", 3);
299 trie.put("Andreas", 4);
300 trie.put("Andrea", 5);
301 trie.put("Andres", 6);
302 trie.put("Anatole", 7);
303 final SortedMap<String, Integer> prefixMap = trie.prefixMap("And");
304 assertEquals(new HashSet<>(Arrays.asList("Andrea", "Andreas", "Andres")), prefixMap.keySet());
305 assertEquals(Arrays.asList(5, 4, 6), new ArrayList<>(prefixMap.values()));
306
307 prefixMap.clear();
308 assertTrue(prefixMap.isEmpty());
309 assertTrue(prefixMap.isEmpty());
310 assertTrue(prefixMap.isEmpty());
311 assertEquals(new HashSet<>(Arrays.asList("Anael", "Analu", "Anatole", "Anna")), trie.keySet());
312 assertEquals(Arrays.asList(2, 3, 7, 1), new ArrayList<>(trie.values()));
313 }
314
315 @Test
316 public void testPrefixMapClearNothing() {
317 final Trie<String, Integer> trie = new PatriciaTrie<>();
318 final SortedMap<String, Integer> prefixMap = trie.prefixMap("And");
319 assertEquals(new HashSet<>(), prefixMap.keySet());
320 assertEquals(new ArrayList<>(0), new ArrayList<>(prefixMap.values()));
321
322 prefixMap.clear();
323 assertTrue(prefixMap.isEmpty());
324 assertTrue(prefixMap.isEmpty());
325 assertTrue(prefixMap.isEmpty());
326 assertEquals(new HashSet<>(), trie.keySet());
327 assertEquals(new ArrayList<>(0), new ArrayList<>(trie.values()));
328 }
329
330 @Test
331 public void testPrefixMapClearUsingRemove() {
332 final Trie<String, Integer> trie = new PatriciaTrie<>();
333 trie.put("Anna", 1);
334 trie.put("Anael", 2);
335 trie.put("Analu", 3);
336 trie.put("Andreas", 4);
337 trie.put("Andrea", 5);
338 trie.put("Andres", 6);
339 trie.put("Anatole", 7);
340 final SortedMap<String, Integer> prefixMap = trie.prefixMap("And");
341 assertEquals(new HashSet<>(Arrays.asList("Andrea", "Andreas", "Andres")), prefixMap.keySet());
342 assertEquals(Arrays.asList(5, 4, 6), new ArrayList<>(prefixMap.values()));
343
344 final Set<String> keys = new HashSet<>(prefixMap.keySet());
345 for (final String key : keys) {
346 prefixMap.remove(key);
347 }
348 assertTrue(prefixMap.isEmpty());
349 assertTrue(prefixMap.isEmpty());
350 assertEquals(new HashSet<>(Arrays.asList("Anael", "Analu", "Anatole", "Anna")), trie.keySet());
351 assertEquals(Arrays.asList(2, 3, 7, 1), new ArrayList<>(trie.values()));
352 }
353
354 @Test
355 public void testPrefixMapRemoval() {
356 final PatriciaTrie<String> trie = new PatriciaTrie<>();
357
358 final String[] keys = {
359 "Albert", "Xavier", "XyZ", "Anna", "Alien", "Alberto",
360 "Alberts", "Allie", "Alliese", "Alabama", "Banane",
361 "Blabla", "Amber", "Ammun", "Akka", "Akko", "Albertoo",
362 "Amma"
363 };
364
365 for (final String key : keys) {
366 trie.put(key, key);
367 }
368
369 SortedMap<String, String> map = trie.prefixMap("Al");
370 assertEquals(8, map.size());
371 Iterator<String> iter = map.keySet().iterator();
372 assertEquals("Alabama", iter.next());
373 assertEquals("Albert", iter.next());
374 assertEquals("Alberto", iter.next());
375 assertEquals("Albertoo", iter.next());
376 assertEquals("Alberts", iter.next());
377 assertEquals("Alien", iter.next());
378 iter.remove();
379 assertEquals(7, map.size());
380 assertEquals("Allie", iter.next());
381 assertEquals("Alliese", iter.next());
382 assertFalse(iter.hasNext());
383
384 map = trie.prefixMap("Ak");
385 assertEquals(2, map.size());
386 iter = map.keySet().iterator();
387 assertEquals("Akka", iter.next());
388 iter.remove();
389 assertEquals(1, map.size());
390 assertEquals("Akko", iter.next());
391
392 final Iterator<String> iter1 = iter;
393 assertFalse(iter.hasNext(), () -> "shouldn't have next (but was: " + iter1.next() + ")");
394
395 assertFalse(iter.hasNext());
396 }
397
398 @Test
399 public void testPrefixMapSizes() {
400
401 final PatriciaTrie<String> aTree = new PatriciaTrie<>();
402 aTree.put("点评", "测试");
403 aTree.put("书评", "测试");
404 assertTrue(aTree.prefixMap("点").containsKey("点评"));
405 assertEquals("测试", aTree.prefixMap("点").get("点评"));
406 assertFalse(aTree.prefixMap("点").isEmpty());
407 assertEquals(1, aTree.prefixMap("点").size());
408 assertEquals(1, aTree.prefixMap("点").size());
409 assertEquals(1, aTree.prefixMap("点").entrySet().size());
410 assertEquals(1, aTree.prefixMap("点评").size());
411
412 aTree.clear();
413 aTree.put("点评", "联盟");
414 aTree.put("点版", "定向");
415 assertEquals(2, aTree.prefixMap("点").size());
416 assertEquals(2, aTree.prefixMap("点").size());
417 }
418
419 @Test
420 public void testPrefixMapSizes2() {
421 final char u8000 = Character.toChars(32768)[0];
422 final char char_b = 'b';
423
424 final PatriciaTrie<String> trie = new PatriciaTrie<>();
425 final String prefixString = StringUtils.EMPTY + char_b;
426 final String longerString = prefixString + u8000;
427
428 assertEquals(1, prefixString.length());
429 assertEquals(2, longerString.length());
430
431 assertTrue(longerString.startsWith(prefixString));
432
433 trie.put(prefixString, "prefixString");
434 trie.put(longerString, "longerString");
435
436 assertEquals(2, trie.prefixMap(prefixString).size());
437 assertTrue(trie.prefixMap(prefixString).containsKey(longerString));
438 }
439
440
441
442
443
444
445
446
447
448
449
450
451 }