src/main/java/au/com/miskinhill/search/analysis/Trie.java (1558B) - raw
1 package au.com.miskinhill.search.analysis;
2
3 import java.util.HashMap;
4 import java.util.Map;
5
6 // TODO move this into its own/a common utilities module?
7 public class Trie<T> {
8
9 private TrieNode root;
10
11 /**
12 * Creates a new trie with the given value associated with the empty string
13 * (i.e. it will be returned by default, if no longer matching prefix is
14 * found).
15 */
16 public Trie(T rootValue) {
17 root = new TrieNode(rootValue);
18 }
19
20 /**
21 * Associates the given value with the given key.
22 */
23 public void put(CharSequence key, T value) {
24 if (value == null)
25 throw new IllegalArgumentException("null values cannot be stored");
26 int i = 0;
27 TrieNode curr = root;
28 while (i < key.length()) {
29 TrieNode child = curr.children.get(key.charAt(i));
30 if (child == null) {
31 TrieNode new_ = new TrieNode(null);
32 curr.children.put(key.charAt(i), new_);
33 curr = new_;
34 } else {
35 curr = child;
36 }
37 i ++;
38 }
39 curr.value = value;
40 }
41
42 /**
43 * Returns the value associated with the longest prefix match for the given
44 * key.
45 */
46 public T get(CharSequence key) {
47 int i = 0;
48 TrieNode curr = root;
49 T retval = root.value;
50 while (i < key.length()) {
51 curr = curr.children.get(key.charAt(i));
52 if (curr == null) {
53 return retval;
54 } else if (curr.value != null) {
55 retval = curr.value;
56 }
57 i ++;
58 }
59 return retval;
60 }
61
62 private class TrieNode {
63 public T value;
64 public Map<Character, TrieNode> children = new HashMap<Character, TrieNode>();
65 public TrieNode(T value) {
66 this.value = value;
67 }
68 }
69
70 }