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  }