1 /*
2 * $Id: PrefixTrie.java 471756 2006-11-06 15:01:43Z husted $
3 *
4 * Licensed to the Apache Software Foundation (ASF) under one
5 * or more contributor license agreements. See the NOTICE file
6 * distributed with this work for additional information
7 * regarding copyright ownership. The ASF licenses this file
8 * to you under the Apache License, Version 2.0 (the
9 * "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 + "' is too big.");
40 if (current.next[c] == null)
41 current.next[c] = new Node();
42 current = current.next[c];
43 }
44 current.value = value;
45 }
46
47 public Object get(String key) {
48 Node current = root;
49 for (int i = 0; i < key.length(); i++) {
50 char c = key.charAt(i);
51 if (c > SIZE)
52 return null;
53 current = current.next[c];
54 if (current == null)
55 return null;
56 if (current.value != null)
57 return current.value;
58 }
59 return null;
60 }
61
62 static class Node {
63 Object value;
64 Node[] next = new Node[SIZE];
65 }
66 }