View Javadoc

1   /*
2    * $Id: PrefixTrie.java 651946 2008-04-27 13:41:38Z apetrelli $
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  
22  package org.apache.struts2.util;
23  
24  /***
25   * Quickly matches a prefix to an object.
26   *
27   */
28  public class PrefixTrie {
29  
30      // supports 7-bit chars.
31      private static final int SIZE = 128;
32  
33      Node root = new Node();
34  
35      public void put(String prefix, Object value) {
36          Node current = root;
37          for (int i = 0; i < prefix.length(); i++) {
38              char c = prefix.charAt(i);
39              if (c > SIZE)
40                  throw new IllegalArgumentException("'" + c + "' 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  }