View Javadoc

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  }