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