KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > apache > xml > utils > Trie


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