1 | |
|
2 | |
|
3 | |
|
4 | |
|
5 | |
|
6 | |
|
7 | |
|
8 | |
|
9 | |
|
10 | |
|
11 | |
|
12 | |
|
13 | |
|
14 | |
|
15 | |
|
16 | |
|
17 | |
|
18 | |
|
19 | |
|
20 | |
|
21 | |
|
22 | |
|
23 | |
|
24 | |
|
25 | |
|
26 | |
package net.sf.triemap; |
27 | |
|
28 | |
import java.io.IOException; |
29 | |
import java.io.ObjectInputStream; |
30 | |
import java.io.ObjectOutputStream; |
31 | |
import java.io.Serializable; |
32 | |
import java.util.ArrayList; |
33 | |
import java.util.Collection; |
34 | |
import java.util.Collections; |
35 | |
import java.util.Enumeration; |
36 | |
import java.util.HashMap; |
37 | |
import java.util.HashSet; |
38 | |
import java.util.Iterator; |
39 | |
import java.util.LinkedList; |
40 | |
import java.util.List; |
41 | |
import java.util.Map; |
42 | |
import java.util.Properties; |
43 | |
import java.util.Set; |
44 | |
import java.util.TreeMap; |
45 | |
import java.util.TreeSet; |
46 | |
import java.util.concurrent.locks.ReentrantReadWriteLock; |
47 | |
|
48 | |
import org.apache.commons.lang.StringUtils; |
49 | |
|
50 | |
|
51 | |
|
52 | |
|
53 | |
|
54 | |
|
55 | |
|
56 | |
|
57 | |
|
58 | |
|
59 | 10648 | public class TrieMap<Value> implements Serializable, Map<String, Value>, Cloneable { |
60 | |
|
61 | |
|
62 | |
private static final long serialVersionUID = 1L; |
63 | |
|
64 | |
|
65 | |
private transient TrieNode<Value> rootNode; |
66 | |
|
67 | 49 | private transient ReentrantReadWriteLock lock = new ReentrantReadWriteLock(); |
68 | |
|
69 | |
|
70 | |
|
71 | |
|
72 | 49 | public TrieMap() { |
73 | 49 | rootNode = new TrieNode<Value>(' ', null, false); |
74 | 49 | } |
75 | |
|
76 | |
|
77 | |
|
78 | |
|
79 | |
|
80 | |
|
81 | |
|
82 | |
public TrieMap(final Map<String, Value> map) { |
83 | 0 | this(); |
84 | 0 | putAll(map); |
85 | 0 | } |
86 | |
|
87 | |
|
88 | |
|
89 | |
|
90 | |
|
91 | |
|
92 | |
|
93 | |
|
94 | |
|
95 | |
public boolean add(final String phrase) { |
96 | 6 | return addRecursive(rootNode, phrase, null, false); |
97 | |
} |
98 | |
|
99 | |
|
100 | |
|
101 | |
|
102 | |
|
103 | |
|
104 | |
|
105 | |
|
106 | |
|
107 | |
|
108 | |
|
109 | |
public boolean add(final String phrase, final Value object) { |
110 | 519 | return addRecursive(rootNode, phrase, object, false); |
111 | |
} |
112 | |
|
113 | |
|
114 | |
|
115 | |
|
116 | |
|
117 | |
|
118 | |
public Properties asProperties() { |
119 | 9 | return new TrieMapBackedProperties(); |
120 | |
} |
121 | |
|
122 | |
|
123 | |
|
124 | |
|
125 | |
|
126 | |
|
127 | |
|
128 | |
|
129 | |
public Properties asProperties(final Properties defaults) { |
130 | 9 | return new TrieMapBackedProperties(defaults); |
131 | |
} |
132 | |
|
133 | |
|
134 | |
|
135 | |
|
136 | |
@Override |
137 | |
public void clear() { |
138 | 10 | rootNode = new TrieNode<Value>(' ', null, false); |
139 | 10 | } |
140 | |
|
141 | |
|
142 | |
|
143 | |
|
144 | |
@SuppressWarnings("unchecked") |
145 | |
@Override |
146 | |
public TrieMap<Value> clone() { |
147 | 1 | TrieMap<Value> clone = null; |
148 | |
try { |
149 | 1 | clone = (TrieMap<Value>) super.clone(); |
150 | 1 | clone.rootNode = rootNode.clone(); |
151 | 0 | } catch (final CloneNotSupportedException e) { |
152 | 1 | } |
153 | 1 | return clone; |
154 | |
} |
155 | |
|
156 | |
|
157 | |
|
158 | |
|
159 | |
@Override |
160 | |
public boolean containsKey(final Object key) { |
161 | 17 | if (key instanceof String) { |
162 | 15 | return containsPrefix((String) key); |
163 | |
} |
164 | 2 | return false; |
165 | |
} |
166 | |
|
167 | |
|
168 | |
|
169 | |
|
170 | |
|
171 | |
|
172 | |
|
173 | |
|
174 | |
|
175 | |
public boolean containsPrefix(final String prefix) { |
176 | 18 | final TrieNode<Value> matchedNode = matchPrefixRecursive(rootNode, prefix); |
177 | 18 | return (matchedNode != null); |
178 | |
} |
179 | |
|
180 | |
|
181 | |
|
182 | |
|
183 | |
@Override |
184 | |
public boolean containsValue(final Object value) { |
185 | 31 | return getPathForValue(value) != null; |
186 | |
} |
187 | |
|
188 | |
|
189 | |
|
190 | |
|
191 | |
@Override |
192 | |
public Set<java.util.Map.Entry<String, Value>> entrySet() { |
193 | 2 | final Set<Map.Entry<String, Value>> result = new TreeSet<Map.Entry<String, Value>>(); |
194 | 2 | for (final String key : keySet()) { |
195 | 22 | result.add(new Entry(key)); |
196 | |
} |
197 | 2 | return result; |
198 | |
} |
199 | |
|
200 | |
|
201 | |
|
202 | |
|
203 | |
@SuppressWarnings("unchecked") |
204 | |
@Override |
205 | |
public boolean equals(final Object obj) { |
206 | 2 | if (this == obj) { |
207 | 0 | return true; |
208 | |
} |
209 | 2 | if (obj == null) { |
210 | 0 | return false; |
211 | |
} |
212 | 2 | if (getClass() != obj.getClass()) { |
213 | 0 | return false; |
214 | |
} |
215 | 2 | final TrieMap other = (TrieMap) obj; |
216 | 2 | if (rootNode == null) { |
217 | 0 | if (other.rootNode != null) { |
218 | 0 | return false; |
219 | |
} |
220 | 2 | } else if (!rootNode.equals(other.rootNode)) { |
221 | 0 | return false; |
222 | |
} |
223 | 2 | return true; |
224 | |
} |
225 | |
|
226 | |
|
227 | |
|
228 | |
|
229 | |
|
230 | |
|
231 | |
|
232 | |
|
233 | |
|
234 | |
|
235 | |
public boolean forceAdd(final String phrase, final Value object) { |
236 | 35 | return addRecursive(rootNode, phrase, object, true); |
237 | |
} |
238 | |
|
239 | |
|
240 | |
|
241 | |
|
242 | |
@Override |
243 | |
public Value get(final Object key) { |
244 | 91 | if (key instanceof String) { |
245 | 90 | final TrieNode<Value> matchedNode = matchPrefixRecursive(rootNode, (String) key); |
246 | 90 | if (matchedNode != null) { |
247 | 68 | final Value result = matchedNode.getObject(); |
248 | 68 | return result; |
249 | |
} |
250 | |
} |
251 | 23 | return null; |
252 | |
} |
253 | |
|
254 | |
|
255 | |
|
256 | |
|
257 | |
|
258 | |
|
259 | |
|
260 | |
|
261 | |
|
262 | |
|
263 | |
|
264 | |
public String getBestMatchingPath(final String prefix) { |
265 | 6 | if (isEmpty(prefix)) { |
266 | 1 | return null; |
267 | |
} |
268 | 5 | final TrieNode<Value> trieNode = rootNode.getChildNode(prefix.charAt(0)); |
269 | 5 | if (trieNode != null) { |
270 | 4 | final StringBuilder builder = new StringBuilder().append(prefix.charAt(0)); |
271 | 4 | final String subPrefix = prefix.substring(1); |
272 | 4 | if (StringUtils.isEmpty(subPrefix)) { |
273 | 1 | return builder.toString(); |
274 | |
} else { |
275 | 3 | return findLastMatchingRecursivly(trieNode, prefix.substring(1), builder); |
276 | |
} |
277 | |
} else { |
278 | 1 | return null; |
279 | |
} |
280 | |
} |
281 | |
|
282 | |
|
283 | |
|
284 | |
|
285 | |
|
286 | |
|
287 | |
|
288 | |
|
289 | |
public List<String> getCompletitions(final String prefix) { |
290 | 20 | final TrieNode<Value> matchedNode = matchPrefixRecursive(rootNode, prefix); |
291 | 20 | final List<String> completions = new ArrayList<String>(); |
292 | 20 | findCompletionsRecursive(matchedNode, prefix, completions); |
293 | 20 | return completions; |
294 | |
} |
295 | |
|
296 | |
|
297 | |
|
298 | |
|
299 | |
|
300 | |
|
301 | |
|
302 | |
|
303 | |
public String getPathForValue(final Object objectToFind) { |
304 | 31 | final String path = findPathForObject(rootNode, "", objectToFind); |
305 | 31 | return path; |
306 | |
} |
307 | |
|
308 | |
|
309 | |
|
310 | |
|
311 | |
|
312 | |
|
313 | |
|
314 | |
|
315 | |
public TrieMap<Value> getSubMap(final String prefix) { |
316 | 1 | final TrieNode<Value> matchedNode = matchPrefixRecursive(rootNode, prefix); |
317 | 1 | final TrieMap<Value> completitions = new TrieMap<Value>(); |
318 | 1 | findObjectMapRecursive(matchedNode, prefix, completitions); |
319 | 1 | return completitions; |
320 | |
} |
321 | |
|
322 | |
|
323 | |
|
324 | |
|
325 | |
|
326 | |
|
327 | |
|
328 | |
|
329 | |
public List<Value> getSubValues(final String prefix) { |
330 | 24 | final TrieNode<Value> matchedNode = (prefix == null) ? rootNode : matchPrefixRecursive(rootNode, prefix); |
331 | 24 | final List<Value> completions = new LinkedList<Value>(); |
332 | 24 | findObjectsRecursive(matchedNode, prefix, completions); |
333 | 24 | return completions; |
334 | |
} |
335 | |
|
336 | |
|
337 | |
|
338 | |
|
339 | |
|
340 | |
|
341 | |
|
342 | |
|
343 | |
|
344 | |
public Value getValueForBestMatchingKey(final String prefix) { |
345 | 11 | if (isEmpty(prefix)) { |
346 | 1 | return null; |
347 | |
} |
348 | 10 | final Value result = getLastMatchingObject(rootNode, prefix, null); |
349 | 10 | return result; |
350 | |
} |
351 | |
|
352 | |
|
353 | |
|
354 | |
|
355 | |
|
356 | |
|
357 | |
|
358 | |
|
359 | |
|
360 | |
|
361 | |
|
362 | |
public <T extends Value> List<Value> getValuesOnPath(final String prefix) { |
363 | 3 | if (isEmpty(prefix)) { |
364 | 1 | return Collections.emptyList(); |
365 | |
} |
366 | 2 | final List<TrieNode<Value>> matchedNodes = matchNodesOnPathRecursive(rootNode, prefix); |
367 | 2 | final List<Value> result = new ArrayList<Value>(matchedNodes.size()); |
368 | 2 | for (final TrieNode<Value> node : matchedNodes) { |
369 | 6 | if (node.containsObject()) { |
370 | 6 | final Value object = node.getObject(); |
371 | 6 | if (object != null) { |
372 | 6 | result.add(object); |
373 | |
} |
374 | 6 | } |
375 | |
} |
376 | 2 | return result; |
377 | |
} |
378 | |
|
379 | |
|
380 | |
|
381 | |
|
382 | |
@Override |
383 | |
public int hashCode() { |
384 | 2 | final int prime = 31; |
385 | 2 | int result = 1; |
386 | 2 | result = prime * result + ((rootNode == null) ? 0 : rootNode.hashCode()); |
387 | 2 | return result; |
388 | |
} |
389 | |
|
390 | |
|
391 | |
|
392 | |
|
393 | |
@Override |
394 | |
public boolean isEmpty() { |
395 | 3 | return rootNode.getChildren().isEmpty(); |
396 | |
} |
397 | |
|
398 | |
|
399 | |
|
400 | |
|
401 | |
@Override |
402 | |
public Set<String> keySet() { |
403 | 15 | final List<String> keys = getCompletitions(""); |
404 | 15 | keys.remove("" + rootNode.getNodeValue()); |
405 | 15 | return new TreeSet<String>(keys); |
406 | |
} |
407 | |
|
408 | |
|
409 | |
|
410 | |
|
411 | |
@Override |
412 | |
public Value put(final String key, final Value value) { |
413 | 20 | final Value preResult = get(key); |
414 | 20 | forceAdd(key, value); |
415 | 20 | return preResult; |
416 | |
} |
417 | |
|
418 | |
|
419 | |
|
420 | |
|
421 | |
@Override |
422 | |
public void putAll(final Map<? extends String, ? extends Value> m) { |
423 | 1 | if (m != null) { |
424 | 1 | for (final Map.Entry<? extends String, ? extends Value> entry : m.entrySet()) { |
425 | 2 | forceAdd(entry.getKey(), entry.getValue()); |
426 | |
} |
427 | |
} |
428 | 1 | } |
429 | |
|
430 | |
|
431 | |
|
432 | |
|
433 | |
@Override |
434 | |
public Value remove(final Object key) { |
435 | 4 | if (key instanceof String) { |
436 | 3 | final TrieNode<Value> matchedNode = matchPrefixRecursive(rootNode, (String) key); |
437 | 3 | if (matchedNode != null) { |
438 | 2 | final Value object = matchedNode.removeObject(); |
439 | 2 | matchedNode.setBoundary(false); |
440 | 2 | return object; |
441 | |
} |
442 | |
} |
443 | 2 | return null; |
444 | |
} |
445 | |
|
446 | |
|
447 | |
|
448 | |
|
449 | |
@Override |
450 | |
public int size() { |
451 | 11 | return keySet().size(); |
452 | |
} |
453 | |
|
454 | |
|
455 | |
|
456 | |
|
457 | |
@Override |
458 | |
public String toString() { |
459 | 2 | return rootNode.toString(); |
460 | |
} |
461 | |
|
462 | |
|
463 | |
|
464 | |
|
465 | |
@Override |
466 | |
public Collection<Value> values() { |
467 | 4 | return getSubValues(""); |
468 | |
} |
469 | |
|
470 | |
private boolean addRecursive(final TrieNode<Value> node, final String phrase, final Value object, final boolean force) { |
471 | 2904 | if (isEmpty(phrase)) { |
472 | 1 | return true; |
473 | |
} |
474 | 2903 | final char firstChar = phrase.charAt(0); |
475 | |
|
476 | 2903 | final String subString = phrase.substring(1); |
477 | 2903 | if (isEmpty(subString)) { |
478 | 559 | if (node.add(firstChar, object, force, true)) { |
479 | 552 | return true; |
480 | |
} |
481 | 7 | return false; |
482 | |
} else { |
483 | 2344 | node.add(firstChar, null, force, false); |
484 | |
} |
485 | |
|
486 | 2344 | final TrieNode<Value> childNode = node.getChildNode(firstChar); |
487 | 2344 | if (childNode != null) { |
488 | 2344 | return addRecursive(childNode, subString, object, force); |
489 | |
} |
490 | 0 | return false; |
491 | |
} |
492 | |
|
493 | |
private void findCompletionsRecursive(final TrieNode<Value> node, final String prefix, final List<String> completions) { |
494 | 275 | if (node == null) { |
495 | 1 | return; |
496 | |
} |
497 | 274 | if (node.isBoundary()) { |
498 | 125 | completions.add(prefix); |
499 | |
} |
500 | 274 | final Collection<TrieNode<Value>> childNodes = node.getChildren(); |
501 | 274 | for (final TrieNode<Value> childNode : childNodes) { |
502 | 255 | final char childChar = childNode.getNodeValue(); |
503 | 255 | findCompletionsRecursive(childNode, prefix + childChar, completions); |
504 | 255 | } |
505 | 274 | } |
506 | |
|
507 | |
private String findLastMatchingRecursivly(final TrieNode<Value> node, final String phrase, final StringBuilder completion) { |
508 | 13 | final char firstChar = phrase.charAt(0); |
509 | 13 | final String subString = phrase.substring(1); |
510 | 13 | if (isEmpty(subString)) { |
511 | 2 | completion.append(firstChar); |
512 | 2 | return completion.toString(); |
513 | |
} |
514 | |
|
515 | 11 | final TrieNode<Value> childNode = node.getChildNode(firstChar); |
516 | 11 | if (childNode != null) { |
517 | 10 | completion.append(firstChar); |
518 | 10 | return findLastMatchingRecursivly(childNode, subString, completion); |
519 | |
} else { |
520 | 1 | return completion.toString(); |
521 | |
} |
522 | |
} |
523 | |
|
524 | |
private void findObjectMapRecursive(final TrieNode<Value> node, final String prefix, final TrieMap<Value> completions) { |
525 | 5 | if (node == null) { |
526 | |
|
527 | 0 | return; |
528 | |
} |
529 | 5 | if (node.containsObject()) { |
530 | 3 | final Value object = node.getObject(); |
531 | 3 | if (object != null) { |
532 | 3 | completions.put(prefix, object); |
533 | |
} |
534 | |
} |
535 | 5 | final Collection<TrieNode<Value>> childNodes = node.getChildren(); |
536 | 5 | for (final TrieNode<Value> childNode : childNodes) { |
537 | 4 | final char childChar = childNode.getNodeValue(); |
538 | 4 | findObjectMapRecursive(childNode, prefix + childChar, completions); |
539 | 4 | } |
540 | 5 | } |
541 | |
|
542 | |
private void findObjectsRecursive(final TrieNode<Value> node, final String prefix, final List<Value> completions) { |
543 | 207 | if (node == null) { |
544 | |
|
545 | 2 | return; |
546 | |
} |
547 | 205 | if (node.containsObject()) { |
548 | 100 | final Value object = node.getObject(); |
549 | 100 | if (object != null) { |
550 | 100 | completions.add(object); |
551 | |
} |
552 | |
} |
553 | 205 | final Collection<TrieNode<Value>> childNodes = node.getChildren(); |
554 | 205 | for (final TrieNode<Value> childNode : childNodes) { |
555 | 183 | final char childChar = childNode.getNodeValue(); |
556 | 183 | findObjectsRecursive(childNode, prefix + childChar, completions); |
557 | 183 | } |
558 | 205 | } |
559 | |
|
560 | |
private String findPathForObject(final TrieNode<Value> node, final String prefix, final Object toFind) { |
561 | 565 | if (node == null) { |
562 | |
|
563 | 0 | return null; |
564 | |
} |
565 | 565 | if (node.containsObject()) { |
566 | 229 | final Value object = node.getObject(); |
567 | 229 | if (object != null && object.equals(toFind)) { |
568 | 26 | return prefix; |
569 | |
} |
570 | |
} |
571 | 539 | final Collection<TrieNode<Value>> childNodes = node.getChildren(); |
572 | 539 | for (final TrieNode<Value> childNode : childNodes) { |
573 | 534 | final char childChar = childNode.getNodeValue(); |
574 | 534 | final String path = findPathForObject(childNode, prefix + childChar, toFind); |
575 | 534 | if (path != null) { |
576 | 145 | return path; |
577 | |
} |
578 | 389 | } |
579 | 394 | return null; |
580 | |
} |
581 | |
|
582 | |
@SuppressWarnings("unchecked") |
583 | |
private Value getLastMatchingObject(final TrieNode node, final String prefix, final Value lastObject) { |
584 | 115 | if (isEmpty(prefix)) { |
585 | 5 | return lastObject; |
586 | |
} |
587 | 110 | final char firstChar = prefix.charAt(0); |
588 | 110 | final TrieNode childNode = node.getChildNode(firstChar); |
589 | 110 | if (childNode == null) { |
590 | |
|
591 | 5 | return lastObject; |
592 | |
} else { |
593 | |
|
594 | 105 | return getLastMatchingObject(childNode, prefix.substring(1), ((Value) ((childNode.containsObject()) ? childNode.getObject() : lastObject))); |
595 | |
} |
596 | |
} |
597 | |
|
598 | |
private boolean isEmpty(final String phrase) { |
599 | 6701 | return StringUtils.isEmpty(phrase); |
600 | |
} |
601 | |
|
602 | |
private List<TrieNode<Value>> matchNodesOnPathRecursive(final TrieNode<Value> node, final String prefix) { |
603 | 2 | return matchNodesOnPathRecursive(node, prefix, new LinkedList<TrieNode<Value>>()); |
604 | |
} |
605 | |
|
606 | |
private List<TrieNode<Value>> matchNodesOnPathRecursive(final TrieNode<Value> node, final String prefix, final List<TrieNode<Value>> result) { |
607 | 13 | if (isEmpty(prefix)) { |
608 | 1 | result.add(node); |
609 | 1 | return result; |
610 | |
} |
611 | 12 | final char firstChar = prefix.charAt(0); |
612 | 12 | final TrieNode<Value> childNode = node.getChildNode(firstChar); |
613 | 12 | if (childNode == null) { |
614 | |
|
615 | 1 | if (node.isBoundary()) { |
616 | 1 | result.add(node); |
617 | |
} |
618 | 1 | return result; |
619 | |
} else { |
620 | |
|
621 | 11 | if (node.isBoundary()) { |
622 | 4 | result.add(node); |
623 | |
} |
624 | 11 | return matchNodesOnPathRecursive(childNode, prefix.substring(1), result); |
625 | |
} |
626 | |
} |
627 | |
|
628 | |
private TrieNode<Value> matchPrefixRecursive(final TrieNode<Value> node, final String prefix) { |
629 | 733 | if (isEmpty(prefix)) { |
630 | 126 | return node; |
631 | |
} |
632 | 607 | final char firstChar = prefix.charAt(0); |
633 | 607 | final TrieNode<Value> childNode = node.getChildNode(firstChar); |
634 | 607 | if (childNode == null) { |
635 | |
|
636 | 30 | return null; |
637 | |
} else { |
638 | |
|
639 | 577 | return matchPrefixRecursive(childNode, prefix.substring(1)); |
640 | |
} |
641 | |
} |
642 | |
|
643 | |
@SuppressWarnings("unchecked") |
644 | |
private void readObject(final ObjectInputStream in) throws IOException, ClassNotFoundException { |
645 | 1 | lock = new ReentrantReadWriteLock(); |
646 | |
|
647 | 1 | rootNode = new TrieNode<Value>(' ', null, false); |
648 | 1 | final int size = in.readInt(); |
649 | |
String key; |
650 | |
Value value; |
651 | 12 | for (int i = 0; i < size; i++) { |
652 | 11 | key = (String) in.readObject(); |
653 | 11 | value = (Value) in.readObject(); |
654 | 11 | add(key, value); |
655 | |
} |
656 | 1 | } |
657 | |
|
658 | |
|
659 | |
|
660 | |
|
661 | |
private void writeObject(final ObjectOutputStream out) throws IOException { |
662 | |
try { |
663 | 1 | lock.readLock().lock(); |
664 | 1 | final Set<Map.Entry<String, Value>> entrySet = entrySet(); |
665 | 1 | out.writeInt(entrySet.size()); |
666 | 1 | for (final Map.Entry<String, Value> entry : entrySet) { |
667 | 11 | out.writeObject(entry.getKey()); |
668 | 11 | out.writeObject(entry.getValue()); |
669 | |
} |
670 | |
} finally { |
671 | 1 | lock.readLock().unlock(); |
672 | 1 | } |
673 | 1 | } |
674 | |
|
675 | |
|
676 | |
|
677 | |
|
678 | |
|
679 | |
|
680 | |
@SuppressWarnings("unchecked") |
681 | |
protected Set<Object> getkeySet() { |
682 | 2 | final List keys = getCompletitions(""); |
683 | 2 | keys.remove("" + rootNode.getNodeValue()); |
684 | 2 | return new TreeSet<Object>(keys); |
685 | |
} |
686 | |
|
687 | |
|
688 | |
|
689 | |
|
690 | |
|
691 | |
|
692 | |
|
693 | |
|
694 | |
@SuppressWarnings("unchecked") |
695 | |
protected List<Object> getObjectValues(final String prefix) { |
696 | 2 | final List<Object> completions = new ArrayList(getSubValues(prefix)); |
697 | 2 | return completions; |
698 | |
} |
699 | |
|
700 | |
|
701 | |
|
702 | |
|
703 | |
|
704 | |
|
705 | |
@SuppressWarnings("unchecked") |
706 | |
protected Set internalEntrySet() { |
707 | 2 | final Set result = new HashSet(); |
708 | 2 | for (final String key : keySet()) { |
709 | 12 | result.add(new Entry(key)); |
710 | |
} |
711 | 2 | return result; |
712 | |
} |
713 | |
|
714 | |
|
715 | |
|
716 | |
|
717 | |
|
718 | |
|
719 | |
|
720 | 19 | public final class TrieMapBackedProperties extends Properties implements Cloneable { |
721 | |
|
722 | |
|
723 | |
private static final long serialVersionUID = 1L; |
724 | |
|
725 | |
|
726 | 18 | private final Map<Object, Object> noneStringKeyMap = new HashMap<Object, Object>(); |
727 | |
|
728 | |
|
729 | 18 | private final ReentrantReadWriteLock lock = new ReentrantReadWriteLock(); |
730 | |
|
731 | 9 | private TrieMapBackedProperties() { |
732 | 9 | } |
733 | |
|
734 | 9 | private TrieMapBackedProperties(final Properties defaults) { |
735 | 9 | super(defaults); |
736 | 9 | } |
737 | |
|
738 | |
|
739 | |
|
740 | |
|
741 | |
@Override |
742 | |
public void clear() { |
743 | |
try { |
744 | 2 | lock.writeLock().lock(); |
745 | 2 | TrieMap.this.clear(); |
746 | 2 | noneStringKeyMap.clear(); |
747 | |
} finally { |
748 | 2 | lock.writeLock().unlock(); |
749 | 2 | } |
750 | 2 | } |
751 | |
|
752 | |
|
753 | |
|
754 | |
|
755 | |
@Override |
756 | |
public TrieMapBackedProperties clone() { |
757 | |
try { |
758 | 1 | lock.readLock().lock(); |
759 | 1 | final TrieMap<Value> clonedMap = TrieMap.this.clone(); |
760 | 1 | final TrieMapBackedProperties clone = (TrieMapBackedProperties) clonedMap.asProperties(defaults); |
761 | 1 | clone.noneStringKeyMap.putAll(noneStringKeyMap); |
762 | 1 | return clone; |
763 | |
} finally { |
764 | 1 | lock.readLock().unlock(); |
765 | |
} |
766 | |
|
767 | |
} |
768 | |
|
769 | |
|
770 | |
|
771 | |
|
772 | |
@Override |
773 | |
public boolean contains(final Object value) { |
774 | 17 | return containsValue(value); |
775 | |
} |
776 | |
|
777 | |
|
778 | |
|
779 | |
|
780 | |
@Override |
781 | |
public boolean containsKey(final Object key) { |
782 | |
try { |
783 | 3 | lock.readLock().lock(); |
784 | 3 | return TrieMap.this.containsKey(key) || noneStringKeyMap.containsKey(key); |
785 | |
} finally { |
786 | 3 | lock.readLock().unlock(); |
787 | |
} |
788 | |
} |
789 | |
|
790 | |
|
791 | |
|
792 | |
|
793 | |
@Override |
794 | |
public boolean containsValue(final Object value) { |
795 | 20 | if (value == null) { |
796 | 1 | throw new NullPointerException(); |
797 | |
} |
798 | |
try { |
799 | 19 | lock.readLock().lock(); |
800 | 19 | return TrieMap.this.containsValue(value) || noneStringKeyMap.containsValue(value); |
801 | |
} finally { |
802 | 19 | lock.readLock().unlock(); |
803 | |
} |
804 | |
} |
805 | |
|
806 | |
|
807 | |
|
808 | |
|
809 | |
@Override |
810 | |
public Enumeration<Object> elements() { |
811 | 1 | final Iterator<Object> iterator = values().iterator(); |
812 | 1 | return new Enumeration<Object>() { |
813 | |
|
814 | |
@Override |
815 | |
public boolean hasMoreElements() { |
816 | 14 | return iterator.hasNext(); |
817 | |
} |
818 | |
|
819 | |
@Override |
820 | |
public Object nextElement() { |
821 | 13 | return iterator.next(); |
822 | |
} |
823 | |
}; |
824 | |
} |
825 | |
|
826 | |
|
827 | |
|
828 | |
|
829 | |
@SuppressWarnings("unchecked") |
830 | |
@Override |
831 | |
public Set<Map.Entry<Object, Object>> entrySet() { |
832 | |
try { |
833 | 2 | lock.readLock().lock(); |
834 | 2 | final Set entrySet = TrieMap.this.internalEntrySet(); |
835 | 2 | entrySet.addAll(noneStringKeyMap.entrySet()); |
836 | 2 | return entrySet; |
837 | |
} finally { |
838 | 2 | lock.readLock().unlock(); |
839 | |
} |
840 | |
} |
841 | |
|
842 | |
|
843 | |
|
844 | |
|
845 | |
@Override |
846 | |
public boolean equals(final Object obj) { |
847 | |
try { |
848 | 1 | lock.readLock().lock(); |
849 | 1 | if (this == obj) { |
850 | 0 | return true; |
851 | |
} |
852 | 1 | if (!super.equals(obj)) { |
853 | 0 | return false; |
854 | |
} |
855 | 1 | if (getClass() != obj.getClass()) { |
856 | 0 | return false; |
857 | |
} |
858 | 1 | final TrieMapBackedProperties other = (TrieMapBackedProperties) obj; |
859 | 1 | if (!getOuterType().equals(other.getOuterType())) { |
860 | 0 | return false; |
861 | |
} |
862 | 1 | if (noneStringKeyMap == null) { |
863 | 0 | if (other.noneStringKeyMap != null) { |
864 | 0 | return false; |
865 | |
} |
866 | 1 | } else if (!noneStringKeyMap.equals(other.noneStringKeyMap)) { |
867 | 0 | return false; |
868 | |
} |
869 | 1 | return true; |
870 | |
} finally { |
871 | 1 | lock.readLock().unlock(); |
872 | |
} |
873 | |
} |
874 | |
|
875 | |
|
876 | |
|
877 | |
|
878 | |
@Override |
879 | |
public Object get(final Object key) { |
880 | |
try { |
881 | 18 | lock.readLock().lock(); |
882 | 18 | Object result = TrieMap.this.get(key); |
883 | 18 | if (result == null) { |
884 | 3 | result = noneStringKeyMap.get(key); |
885 | |
} |
886 | 18 | return result; |
887 | |
} finally { |
888 | 18 | lock.readLock().unlock(); |
889 | |
} |
890 | |
} |
891 | |
|
892 | |
|
893 | |
|
894 | |
|
895 | |
@Override |
896 | |
public String getProperty(final String key) { |
897 | 5 | final Object oval = get(key); |
898 | 5 | final String sval = (oval instanceof String) ? (String) oval : null; |
899 | 5 | return ((sval == null) && (defaults != null)) ? defaults.getProperty(key) : sval; |
900 | |
} |
901 | |
|
902 | |
|
903 | |
|
904 | |
|
905 | |
@Override |
906 | |
public int hashCode() { |
907 | 2 | final int prime = 31; |
908 | 2 | int result = 0; |
909 | 2 | result = prime * result + getOuterType().hashCode(); |
910 | 2 | result = prime * result + ((noneStringKeyMap == null) ? 0 : noneStringKeyMap.hashCode()); |
911 | 2 | return result; |
912 | |
} |
913 | |
|
914 | |
|
915 | |
|
916 | |
|
917 | |
@Override |
918 | |
public boolean isEmpty() { |
919 | |
try { |
920 | 1 | lock.readLock().lock(); |
921 | 1 | return TrieMap.this.isEmpty() && noneStringKeyMap.isEmpty(); |
922 | |
} finally { |
923 | 1 | lock.readLock().unlock(); |
924 | |
} |
925 | |
} |
926 | |
|
927 | |
|
928 | |
|
929 | |
|
930 | |
@Override |
931 | |
public Enumeration<Object> keys() { |
932 | 1 | final Iterator<Object> it = keySet().iterator(); |
933 | 1 | return new Enumeration<Object>() { |
934 | |
|
935 | |
@Override |
936 | |
public boolean hasMoreElements() { |
937 | 0 | return it.hasNext(); |
938 | |
} |
939 | |
|
940 | |
@Override |
941 | |
public Object nextElement() { |
942 | 0 | return it.next(); |
943 | |
} |
944 | |
}; |
945 | |
} |
946 | |
|
947 | |
|
948 | |
|
949 | |
|
950 | |
@Override |
951 | |
public Set<Object> keySet() { |
952 | |
try { |
953 | 2 | lock.readLock().lock(); |
954 | 2 | final Set<Object> keys = new HashSet<Object>(TrieMap.this.getkeySet()); |
955 | 2 | keys.addAll(noneStringKeyMap.keySet()); |
956 | 2 | if (defaults != null) { |
957 | 2 | keys.addAll(defaults.keySet()); |
958 | |
} |
959 | 2 | return keys; |
960 | |
} finally { |
961 | 2 | lock.readLock().unlock(); |
962 | |
} |
963 | |
} |
964 | |
|
965 | |
|
966 | |
|
967 | |
|
968 | |
@SuppressWarnings("unchecked") |
969 | |
@Override |
970 | |
public Object put(final Object key, final Object value) { |
971 | |
try { |
972 | 25 | lock.writeLock().lock(); |
973 | 25 | if (key instanceof String) { |
974 | 14 | return TrieMap.this.put((String) key, (Value) value); |
975 | |
} else { |
976 | 11 | return noneStringKeyMap.put(key, value); |
977 | |
} |
978 | |
} finally { |
979 | 25 | lock.writeLock().unlock(); |
980 | |
} |
981 | |
} |
982 | |
|
983 | |
|
984 | |
|
985 | |
|
986 | |
@SuppressWarnings("unchecked") |
987 | |
@Override |
988 | |
public void putAll(final Map<? extends Object, ? extends Object> t) { |
989 | |
try { |
990 | 1 | lock.writeLock().lock(); |
991 | 1 | for (final Map.Entry entry : t.entrySet()) { |
992 | 2 | put(entry.getKey(), entry.getValue()); |
993 | |
} |
994 | |
} finally { |
995 | 1 | lock.writeLock().unlock(); |
996 | 1 | } |
997 | 1 | } |
998 | |
|
999 | |
|
1000 | |
|
1001 | |
|
1002 | |
@Override |
1003 | |
public Object remove(final Object key) { |
1004 | |
try { |
1005 | 2 | lock.writeLock().lock(); |
1006 | 2 | Object result = TrieMap.this.remove(key); |
1007 | 2 | if (result == null) { |
1008 | 1 | result = noneStringKeyMap.remove(key); |
1009 | |
} |
1010 | 2 | return result; |
1011 | |
} finally { |
1012 | 2 | lock.writeLock().unlock(); |
1013 | |
} |
1014 | |
} |
1015 | |
|
1016 | |
|
1017 | |
|
1018 | |
|
1019 | |
@Override |
1020 | |
public Object setProperty(final String key, final String value) { |
1021 | 12 | return put(key, value); |
1022 | |
} |
1023 | |
|
1024 | |
|
1025 | |
|
1026 | |
|
1027 | |
@Override |
1028 | |
public int size() { |
1029 | 6 | return TrieMap.this.size() + noneStringKeyMap.size(); |
1030 | |
} |
1031 | |
|
1032 | |
|
1033 | |
|
1034 | |
|
1035 | |
@Override |
1036 | |
public String toString() { |
1037 | 1 | return new StringBuilder(TrieMap.this.toString()).append(",").append(noneStringKeyMap.toString()).toString(); |
1038 | |
} |
1039 | |
|
1040 | |
|
1041 | |
|
1042 | |
|
1043 | |
@Override |
1044 | |
public Collection<Object> values() { |
1045 | |
try { |
1046 | 2 | lock.readLock().lock(); |
1047 | 2 | final List<Object> result = TrieMap.this.getObjectValues(""); |
1048 | 2 | result.addAll(noneStringKeyMap.values()); |
1049 | 2 | if (defaults != null) { |
1050 | 1 | result.addAll(defaults.values()); |
1051 | |
} |
1052 | 2 | return result; |
1053 | |
} finally { |
1054 | 2 | lock.readLock().unlock(); |
1055 | |
} |
1056 | |
} |
1057 | |
|
1058 | |
|
1059 | |
|
1060 | |
|
1061 | |
|
1062 | |
|
1063 | |
@SuppressWarnings("unchecked") |
1064 | |
private TrieMap getOuterType() { |
1065 | 4 | return TrieMap.this; |
1066 | |
} |
1067 | |
} |
1068 | |
|
1069 | |
|
1070 | |
|
1071 | |
|
1072 | 132 | private final class Entry implements Map.Entry<String, Value>, Comparable<Entry> { |
1073 | |
|
1074 | |
|
1075 | |
private final String key; |
1076 | |
|
1077 | |
|
1078 | |
|
1079 | |
|
1080 | |
|
1081 | |
|
1082 | |
|
1083 | 34 | private Entry(final String keyParam) { |
1084 | 34 | this.key = keyParam; |
1085 | 34 | } |
1086 | |
|
1087 | |
|
1088 | |
|
1089 | |
|
1090 | |
@Override |
1091 | |
public int compareTo(final Entry o) { |
1092 | 64 | return key.compareTo(o.getKey()); |
1093 | |
} |
1094 | |
|
1095 | |
|
1096 | |
|
1097 | |
|
1098 | |
@Override |
1099 | |
public String getKey() { |
1100 | 98 | return key; |
1101 | |
} |
1102 | |
|
1103 | |
|
1104 | |
|
1105 | |
|
1106 | |
@Override |
1107 | |
public Value getValue() { |
1108 | 34 | return get(key); |
1109 | |
} |
1110 | |
|
1111 | |
|
1112 | |
|
1113 | |
|
1114 | |
@Override |
1115 | |
public Value setValue(final Value value) { |
1116 | 11 | final Value result = get(key); |
1117 | 11 | if (value == null) { |
1118 | 0 | remove(key); |
1119 | |
} else { |
1120 | 11 | forceAdd(key, value); |
1121 | |
} |
1122 | 11 | return result; |
1123 | |
} |
1124 | |
} |
1125 | |
|
1126 | 60 | private final class TrieNode<ValueNode> implements Cloneable { |
1127 | |
|
1128 | |
|
1129 | |
private static final long serialVersionUID = 1L; |
1130 | |
|
1131 | |
|
1132 | |
private ValueNode object; |
1133 | |
|
1134 | |
|
1135 | |
private final Character character; |
1136 | |
|
1137 | |
|
1138 | |
private Map<Character, TrieNode<ValueNode>> children; |
1139 | |
|
1140 | |
|
1141 | 1239 | private boolean boundary = false; |
1142 | |
|
1143 | 1239 | private TrieNode(final char c, final ValueNode value, final boolean boundaryParam) { |
1144 | 1239 | this.character = Character.valueOf(c); |
1145 | 1239 | this.boundary = boundaryParam; |
1146 | 1239 | children = new TreeMap<Character, TrieNode<ValueNode>>(); |
1147 | 1239 | if (value != null) { |
1148 | 493 | setValue(value); |
1149 | |
} |
1150 | 1239 | } |
1151 | |
|
1152 | |
public boolean add(final char c, final ValueNode object, final boolean force, final boolean isBoundary) { |
1153 | |
try { |
1154 | 2903 | lock.writeLock().lock(); |
1155 | 2903 | final TrieNode<ValueNode> node = children.get(Character.valueOf(c)); |
1156 | 2903 | if (node == null) { |
1157 | |
|
1158 | 1179 | children.put(Character.valueOf(c), new TrieNode<ValueNode>(c, object, isBoundary)); |
1159 | 1179 | return true; |
1160 | 1724 | } else if (object != null && (force || !node.isBoundary())) { |
1161 | 58 | node.setValue(object); |
1162 | 58 | node.setBoundary(isBoundary); |
1163 | 58 | return true; |
1164 | |
} |
1165 | |
} finally { |
1166 | 1237 | lock.writeLock().unlock(); |
1167 | 1666 | } |
1168 | 1666 | return false; |
1169 | |
} |
1170 | |
|
1171 | |
@SuppressWarnings("unchecked") |
1172 | |
@Override |
1173 | |
public TrieNode<ValueNode> clone() { |
1174 | |
try { |
1175 | 23 | lock.readLock().lock(); |
1176 | 23 | TrieNode<ValueNode> node = null; |
1177 | |
try { |
1178 | 23 | node = (TrieNode<ValueNode>) super.clone(); |
1179 | 23 | final Map<Character, TrieNode<ValueNode>> childs = new TreeMap<Character, TrieNode<ValueNode>>(); |
1180 | 23 | for (final TrieNode<ValueNode> nodeTrieNode : children.values()) { |
1181 | 22 | childs.put(nodeTrieNode.character, nodeTrieNode.clone()); |
1182 | |
} |
1183 | 23 | node.children = childs; |
1184 | 0 | } catch (final CloneNotSupportedException cnse) { |
1185 | 23 | } |
1186 | 23 | return node; |
1187 | |
} finally { |
1188 | 23 | lock.readLock().unlock(); |
1189 | |
} |
1190 | |
} |
1191 | |
|
1192 | |
|
1193 | |
|
1194 | |
|
1195 | |
|
1196 | |
|
1197 | |
public boolean containsObject() { |
1198 | |
try { |
1199 | 886 | lock.readLock().lock(); |
1200 | 886 | return isBoundary() && object != null; |
1201 | |
} finally { |
1202 | 886 | lock.readLock().unlock(); |
1203 | |
} |
1204 | |
} |
1205 | |
|
1206 | |
|
1207 | |
|
1208 | |
|
1209 | |
@SuppressWarnings("unchecked") |
1210 | |
@Override |
1211 | |
public boolean equals(final Object obj) { |
1212 | 46 | if (this == obj) { |
1213 | 0 | return true; |
1214 | |
} |
1215 | 46 | if (obj == null) { |
1216 | 0 | return false; |
1217 | |
} |
1218 | 46 | if (getClass() != obj.getClass()) { |
1219 | 0 | return false; |
1220 | |
} |
1221 | 46 | final TrieNode<ValueNode> other = (TrieNode<ValueNode>) obj; |
1222 | 46 | if (boundary != other.boundary) { |
1223 | 0 | return false; |
1224 | |
} |
1225 | 46 | if (character == null) { |
1226 | 0 | if (other.character != null) { |
1227 | 0 | return false; |
1228 | |
} |
1229 | 46 | } else if (!character.equals(other.character)) { |
1230 | 0 | return false; |
1231 | |
} |
1232 | 46 | if (children == null) { |
1233 | 0 | if (other.children != null) { |
1234 | 0 | return false; |
1235 | |
} |
1236 | 46 | } else if (!children.equals(other.children)) { |
1237 | 0 | return false; |
1238 | |
} |
1239 | 46 | if (object == null) { |
1240 | 24 | if (other.object != null) { |
1241 | 0 | return false; |
1242 | |
} |
1243 | 22 | } else if (!object.equals(other.object)) { |
1244 | 0 | return false; |
1245 | |
} |
1246 | 46 | return true; |
1247 | |
} |
1248 | |
|
1249 | |
|
1250 | |
|
1251 | |
|
1252 | |
|
1253 | |
|
1254 | |
|
1255 | |
|
1256 | |
|
1257 | |
public TrieNode<ValueNode> getChildNode(final char c) { |
1258 | 3089 | return children.get(Character.valueOf(c)); |
1259 | |
} |
1260 | |
|
1261 | |
|
1262 | |
|
1263 | |
|
1264 | |
|
1265 | |
|
1266 | |
public Collection<TrieNode<ValueNode>> getChildren() { |
1267 | |
try { |
1268 | 1026 | lock.readLock().lock(); |
1269 | 1026 | return (children == null) ? Collections.<TrieNode<ValueNode>> emptyList() : children.values(); |
1270 | |
} finally { |
1271 | 1026 | lock.readLock().unlock(); |
1272 | |
} |
1273 | |
} |
1274 | |
|
1275 | |
|
1276 | |
|
1277 | |
|
1278 | |
|
1279 | |
|
1280 | |
public char getNodeValue() { |
1281 | 993 | return character.charValue(); |
1282 | |
} |
1283 | |
|
1284 | |
|
1285 | |
|
1286 | |
|
1287 | |
|
1288 | |
|
1289 | |
public ValueNode getObject() { |
1290 | |
try { |
1291 | 424 | lock.readLock().lock(); |
1292 | 424 | return object; |
1293 | |
} finally { |
1294 | 424 | lock.readLock().unlock(); |
1295 | |
} |
1296 | |
} |
1297 | |
|
1298 | |
|
1299 | |
|
1300 | |
|
1301 | |
@Override |
1302 | |
public int hashCode() { |
1303 | 46 | final int prime = 31; |
1304 | 46 | int result = 1; |
1305 | 46 | result = prime * result + (boundary ? 1231 : 1237); |
1306 | 46 | result = prime * result + ((character == null) ? 0 : character.hashCode()); |
1307 | 46 | result = prime * result + ((children == null) ? 0 : children.hashCode()); |
1308 | 46 | result = prime * result + ((object == null) ? 0 : object.hashCode()); |
1309 | 46 | return result; |
1310 | |
} |
1311 | |
|
1312 | |
|
1313 | |
|
1314 | |
|
1315 | |
|
1316 | |
|
1317 | |
public boolean isBoundary() { |
1318 | 1263 | return boundary; |
1319 | |
} |
1320 | |
|
1321 | |
|
1322 | |
|
1323 | |
|
1324 | |
|
1325 | |
|
1326 | |
public ValueNode removeObject() { |
1327 | |
try { |
1328 | 2 | lock.writeLock().lock(); |
1329 | |
|
1330 | 2 | final ValueNode result = getObject(); |
1331 | 2 | object = null; |
1332 | 2 | return result; |
1333 | |
} finally { |
1334 | 2 | lock.writeLock().unlock(); |
1335 | |
} |
1336 | |
} |
1337 | |
|
1338 | |
|
1339 | |
|
1340 | |
|
1341 | |
|
1342 | |
|
1343 | |
|
1344 | |
public void setBoundary(final boolean boundary) { |
1345 | |
try { |
1346 | 60 | lock.writeLock().lock(); |
1347 | 60 | this.boundary = boundary; |
1348 | |
} finally { |
1349 | 60 | lock.writeLock().unlock(); |
1350 | 60 | } |
1351 | 60 | } |
1352 | |
|
1353 | |
|
1354 | |
|
1355 | |
|
1356 | |
@Override |
1357 | |
public String toString() { |
1358 | 2 | final StringBuilder sb = new StringBuilder("{"); |
1359 | 2 | for (final TrieNode<ValueNode> node : children.values()) { |
1360 | 4 | node.toString(sb, ""); |
1361 | |
} |
1362 | 2 | return sb.append("}").toString(); |
1363 | |
} |
1364 | |
|
1365 | |
|
1366 | |
|
1367 | |
|
1368 | |
|
1369 | |
|
1370 | |
|
1371 | |
|
1372 | |
|
1373 | |
|
1374 | |
|
1375 | |
|
1376 | |
|
1377 | |
|
1378 | |
|
1379 | |
|
1380 | |
|
1381 | |
|
1382 | |
|
1383 | |
private Object setValue(final ValueNode obj) { |
1384 | 551 | final Object result = this.object; |
1385 | 551 | this.object = obj; |
1386 | 551 | return result; |
1387 | |
} |
1388 | |
|
1389 | |
|
1390 | |
|
1391 | |
|
1392 | |
|
1393 | |
|
1394 | |
|
1395 | |
|
1396 | |
|
1397 | |
|
1398 | |
|
1399 | |
|
1400 | |
|
1401 | |
|
1402 | |
|
1403 | |
|
1404 | |
|
1405 | |
|
1406 | |
|
1407 | |
|
1408 | |
|
1409 | |
|
1410 | |
|
1411 | |
|
1412 | |
|
1413 | |
|
1414 | |
|
1415 | |
|
1416 | |
|
1417 | |
|
1418 | |
|
1419 | |
|
1420 | |
|
1421 | |
protected StringBuilder toString(final StringBuilder sb, final String prefix) { |
1422 | 44 | if (isBoundary() && object != null) { |
1423 | 22 | sb.append(prefix + character); |
1424 | 22 | sb.append(" : ").append(object.toString()).append(";\n"); |
1425 | |
} |
1426 | 44 | for (final TrieNode<ValueNode> node : children.values()) { |
1427 | 40 | node.toString(sb, prefix + character.charValue()); |
1428 | |
} |
1429 | 44 | return sb; |
1430 | |
} |
1431 | |
|
1432 | |
} |
1433 | |
|
1434 | |
} |