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 com.sun.org.apache.xml.internal.utils;
  20. /**
  21. * A digital search trie for 7-bit ASCII text
  22. * The API is a subset of java.util.Hashtable
  23. * The key must be a 7-bit ASCII string
  24. * The value may be any Java Object
  25. * @xsl.usage internal
  26. */
  27. public class Trie
  28. {
  29. /** Size of the m_nextChar array. */
  30. public static final int ALPHA_SIZE = 128;
  31. /** The root node of the tree. */
  32. Node m_Root;
  33. /** helper buffer to convert Strings to char arrays */
  34. private char[] m_charBuffer = new char[0];
  35. /**
  36. * Construct the trie.
  37. */
  38. public Trie()
  39. {
  40. m_Root = new Node();
  41. }
  42. /**
  43. * Put an object into the trie for lookup.
  44. *
  45. * @param key must be a 7-bit ASCII string
  46. * @param value any java object.
  47. *
  48. * @return The old object that matched key, or null.
  49. */
  50. public Object put(String key, Object value)
  51. {
  52. final int len = key.length();
  53. if (len > m_charBuffer.length)
  54. {
  55. // make the biggest buffer ever needed in get(String)
  56. m_charBuffer = new char[len];
  57. }
  58. Node node = m_Root;
  59. for (int i = 0; i < len; i++)
  60. {
  61. Node nextNode = node.m_nextChar[Character.toUpperCase(key.charAt(i))];
  62. if (nextNode != null)
  63. {
  64. node = nextNode;
  65. }
  66. else
  67. {
  68. for (; i < len; i++)
  69. {
  70. Node newNode = new Node();
  71. // put this value into the tree with a case insensitive key
  72. node.m_nextChar[Character.toUpperCase(key.charAt(i))] = newNode;
  73. node.m_nextChar[Character.toLowerCase(key.charAt(i))] = newNode;
  74. node = newNode;
  75. }
  76. break;
  77. }
  78. }
  79. Object ret = node.m_Value;
  80. node.m_Value = value;
  81. return ret;
  82. }
  83. /**
  84. * Get an object that matches the key.
  85. *
  86. * @param key must be a 7-bit ASCII string
  87. *
  88. * @return The object that matches the key, or null.
  89. */
  90. public Object get(final String key)
  91. {
  92. final int len = key.length();
  93. /* If the name is too long, we won't find it, this also keeps us
  94. * from overflowing m_charBuffer
  95. */
  96. if (m_charBuffer.length < len)
  97. return null;
  98. Node node = m_Root;
  99. switch (len) // optimize the look up based on the number of chars
  100. {
  101. // case 0 looks silly, but the generated bytecode runs
  102. // faster for lookup of elements of length 2 with this in
  103. // and a fair bit faster. Don't know why.
  104. case 0 :
  105. {
  106. return null;
  107. }
  108. case 1 :
  109. {
  110. final char ch = key.charAt(0);
  111. if (ch < ALPHA_SIZE)
  112. {
  113. node = node.m_nextChar[ch];
  114. if (node != null)
  115. return node.m_Value;
  116. }
  117. return null;
  118. }
  119. // comment out case 2 because the default is faster
  120. // case 2 :
  121. // {
  122. // final char ch0 = key.charAt(0);
  123. // final char ch1 = key.charAt(1);
  124. // if (ch0 < ALPHA_SIZE && ch1 < ALPHA_SIZE)
  125. // {
  126. // node = node.m_nextChar[ch0];
  127. // if (node != null)
  128. // {
  129. //
  130. // if (ch1 < ALPHA_SIZE)
  131. // {
  132. // node = node.m_nextChar[ch1];
  133. // if (node != null)
  134. // return node.m_Value;
  135. // }
  136. // }
  137. // }
  138. // return null;
  139. // }
  140. default :
  141. {
  142. key.getChars(0, len, m_charBuffer, 0);
  143. // copy string into array
  144. for (int i = 0; i < len; i++)
  145. {
  146. final char ch = m_charBuffer[i];
  147. if (ALPHA_SIZE <= ch)
  148. {
  149. // the key is not 7-bit ASCII so we won't find it here
  150. return null;
  151. }
  152. node = node.m_nextChar[ch];
  153. if (node == null)
  154. return null;
  155. }
  156. return node.m_Value;
  157. }
  158. }
  159. }
  160. /**
  161. * The node representation for the trie.
  162. * @xsl.usage internal
  163. */
  164. class Node
  165. {
  166. /**
  167. * Constructor, creates a Node[ALPHA_SIZE].
  168. */
  169. Node()
  170. {
  171. m_nextChar = new Node[ALPHA_SIZE];
  172. m_Value = null;
  173. }
  174. /** The next nodes. */
  175. Node m_nextChar[];
  176. /** The value. */
  177. Object m_Value;
  178. }
  179. }