01: package com.opensymphony.webwork.util;
02:
03: /**
04: * Quickly matches a prefix to an object.
05: *
06: * @author crazybob@google.com (Bob Lee)
07: */
08: public class PrefixTrie {
09:
10: // supports 7-bit chars.
11: private static final int SIZE = 128;
12:
13: Node root = new Node();
14:
15: public void put(String prefix, Object value) {
16: Node current = root;
17: for (int i = 0; i < prefix.length(); i++) {
18: char c = prefix.charAt(i);
19: if (c > SIZE)
20: throw new IllegalArgumentException("'" + c
21: + "' is too big.");
22: if (current.next[c] == null)
23: current.next[c] = new Node();
24: current = current.next[c];
25: }
26: current.value = value;
27: }
28:
29: public Object get(String key) {
30: Node current = root;
31: for (int i = 0; i < key.length(); i++) {
32: char c = key.charAt(i);
33: if (c > SIZE)
34: return null;
35: current = current.next[c];
36: if (current == null)
37: return null;
38: if (current.value != null)
39: return current.value;
40: }
41: return null;
42: }
43:
44: static class Node {
45: Object value;
46: Node[] next = new Node[SIZE];
47: }
48: }
|