View Javadoc

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