View Javadoc
1   /*
2    * reserved comment block
3    * DO NOT REMOVE OR ALTER!
4    */
5   /*
6    * Copyright 1999-2004 The Apache Software Foundation.
7    *
8    * Licensed under the Apache License, Version 2.0 (the "License");
9    * you may not use this file except in compliance with the License.
10   * 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, software
15   * distributed under the License is distributed on an "AS IS" BASIS,
16   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
17   * See the License for the specific language governing permissions and
18   * limitations under the License.
19   */
20  /*
21   * $Id: Trie.java,v 1.2.4.1 2005/09/15 08:15:59 suresh_emailid Exp $
22   */
23  package com.sun.org.apache.xml.internal.utils;
24  
25  /**
26   * A digital search trie for 7-bit ASCII text
27   * The API is a subset of java.util.Hashtable
28   * The key must be a 7-bit ASCII string
29   * The value may be any Java Object
30   * @xsl.usage internal
31   */
32  public class Trie
33  {
34  
35    /** Size of the m_nextChar array.  */
36    public static final int ALPHA_SIZE = 128;
37  
38    /** The root node of the tree.    */
39    Node m_Root;
40  
41    /** helper buffer to convert Strings to char arrays */
42    private char[] m_charBuffer = new char[0];
43  
44    /**
45     * Construct the trie.
46     */
47    public Trie()
48    {
49      m_Root = new Node();
50    }
51  
52    /**
53     * Put an object into the trie for lookup.
54     *
55     * @param key must be a 7-bit ASCII string
56     * @param value any java object.
57     *
58     * @return The old object that matched key, or null.
59     */
60    public Object put(String key, Object value)
61    {
62  
63      final int len = key.length();
64      if (len > m_charBuffer.length)
65      {
66          // make the biggest buffer ever needed in get(String)
67          m_charBuffer = new char[len];
68      }
69  
70      Node node = m_Root;
71  
72      for (int i = 0; i < len; i++)
73      {
74        Node nextNode = node.m_nextChar[Character.toUpperCase(key.charAt(i))];
75  
76        if (nextNode != null)
77        {
78          node = nextNode;
79        }
80        else
81        {
82          for (; i < len; i++)
83          {
84            Node newNode = new Node();
85            // put this value into the tree with a case insensitive key
86            node.m_nextChar[Character.toUpperCase(key.charAt(i))] = newNode;
87            node.m_nextChar[Character.toLowerCase(key.charAt(i))] = newNode;
88            node = newNode;
89          }
90          break;
91        }
92      }
93  
94      Object ret = node.m_Value;
95  
96      node.m_Value = value;
97  
98      return ret;
99    }
100 
101   /**
102    * Get an object that matches the key.
103    *
104    * @param key must be a 7-bit ASCII string
105    *
106    * @return The object that matches the key, or null.
107    */
108 public Object get(final String key)
109 {
110 
111     final int len = key.length();
112 
113     /* If the name is too long, we won't find it, this also keeps us
114      * from overflowing m_charBuffer
115      */
116     if (m_charBuffer.length < len)
117         return null;
118 
119     Node node = m_Root;
120     switch (len) // optimize the look up based on the number of chars
121     {
122         // case 0 looks silly, but the generated bytecode runs
123         // faster for lookup of elements of length 2 with this in
124         // and a fair bit faster.  Don't know why.
125         case 0 :
126             {
127                 return null;
128             }
129 
130         case 1 :
131             {
132                 final char ch = key.charAt(0);
133                 if (ch < ALPHA_SIZE)
134                 {
135                     node = node.m_nextChar[ch];
136                     if (node != null)
137                         return node.m_Value;
138                 }
139                 return null;
140             }
141 //        comment out case 2 because the default is faster
142 //        case 2 :
143 //            {
144 //                final char ch0 = key.charAt(0);
145 //                final char ch1 = key.charAt(1);
146 //                if (ch0 < ALPHA_SIZE && ch1 < ALPHA_SIZE)
147 //                {
148 //                    node = node.m_nextChar[ch0];
149 //                    if (node != null)
150 //                    {
151 //
152 //                        if (ch1 < ALPHA_SIZE)
153 //                        {
154 //                            node = node.m_nextChar[ch1];
155 //                            if (node != null)
156 //                                return node.m_Value;
157 //                        }
158 //                    }
159 //                }
160 //                return null;
161 //           }
162         default :
163             {
164                 key.getChars(0, len, m_charBuffer, 0);
165                 // copy string into array
166                 for (int i = 0; i < len; i++)
167                 {
168                     final char ch = m_charBuffer[i];
169                     if (ALPHA_SIZE <= ch)
170                     {
171                         // the key is not 7-bit ASCII so we won't find it here
172                         return null;
173                     }
174 
175                     node = node.m_nextChar[ch];
176                     if (node == null)
177                         return null;
178                 }
179 
180                 return node.m_Value;
181             }
182     }
183 }
184 
185   /**
186    * The node representation for the trie.
187    * @xsl.usage internal
188    */
189   class Node
190   {
191 
192     /**
193      * Constructor, creates a Node[ALPHA_SIZE].
194      */
195     Node()
196     {
197       m_nextChar = new Node[ALPHA_SIZE];
198       m_Value = null;
199     }
200 
201     /** The next nodes.   */
202     Node m_nextChar[];
203 
204     /** The value.   */
205     Object m_Value;
206   }
207 }