01: /*
02: * $Id: PrefixTrie.java 471756 2006-11-06 15:01:43Z husted $
03: *
04: * Licensed to the Apache Software Foundation (ASF) under one
05: * or more contributor license agreements. See the NOTICE file
06: * distributed with this work for additional information
07: * regarding copyright ownership. The ASF licenses this file
08: * to you under the Apache License, Version 2.0 (the
09: * "License"); you may not use this file except in compliance
10: * with the License. You may obtain a copy of the License at
11: *
12: * http://www.apache.org/licenses/LICENSE-2.0
13: *
14: * Unless required by applicable law or agreed to in writing,
15: * software distributed under the License is distributed on an
16: * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
17: * KIND, either express or implied. See the License for the
18: * specific language governing permissions and limitations
19: * under the License.
20: */
21: package org.apache.struts2.util;
22:
23: /**
24: * Quickly matches a prefix to an object.
25: *
26: */
27: public class PrefixTrie {
28:
29: // supports 7-bit chars.
30: private static final int SIZE = 128;
31:
32: Node root = new Node();
33:
34: public void put(String prefix, Object value) {
35: Node current = root;
36: for (int i = 0; i < prefix.length(); i++) {
37: char c = prefix.charAt(i);
38: if (c > SIZE)
39: throw new IllegalArgumentException("'" + c
40: + "' is too big.");
41: if (current.next[c] == null)
42: current.next[c] = new Node();
43: current = current.next[c];
44: }
45: current.value = value;
46: }
47:
48: public Object get(String key) {
49: Node current = root;
50: for (int i = 0; i < key.length(); i++) {
51: char c = key.charAt(i);
52: if (c > SIZE)
53: return null;
54: current = current.next[c];
55: if (current == null)
56: return null;
57: if (current.value != null)
58: return current.value;
59: }
60: return null;
61: }
62:
63: static class Node {
64: Object value;
65: Node[] next = new Node[SIZE];
66: }
67: }
|