| /* |
| * The Apache Software License, Version 1.1 |
| * |
| * |
| * Copyright (c) 1999-2003 The Apache Software Foundation. All rights |
| * reserved. |
| * |
| * Redistribution and use in source and binary forms, with or without |
| * modification, are permitted provided that the following conditions |
| * are met: |
| * |
| * 1. Redistributions of source code must retain the above copyright |
| * notice, this list of conditions and the following disclaimer. |
| * |
| * 2. Redistributions in binary form must reproduce the above copyright |
| * notice, this list of conditions and the following disclaimer in |
| * the documentation and/or other materials provided with the |
| * distribution. |
| * |
| * 3. The end-user documentation included with the redistribution, |
| * if any, must include the following acknowledgment: |
| * "This product includes software developed by the |
| * Apache Software Foundation (http://www.apache.org/)." |
| * Alternately, this acknowledgment may appear in the software itself, |
| * if and wherever such third-party acknowledgments normally appear. |
| * |
| * 4. The names "Xalan" and "Apache Software Foundation" must |
| * not be used to endorse or promote products derived from this |
| * software without prior written permission. For written |
| * permission, please contact apache@apache.org. |
| * |
| * 5. Products derived from this software may not be called "Apache", |
| * nor may "Apache" appear in their name, without prior written |
| * permission of the Apache Software Foundation. |
| * |
| * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED |
| * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES |
| * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE |
| * DISCLAIMED. IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR |
| * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, |
| * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT |
| * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF |
| * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND |
| * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, |
| * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT |
| * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF |
| * SUCH DAMAGE. |
| * ==================================================================== |
| * |
| * This software consists of voluntary contributions made by many |
| * individuals on behalf of the Apache Software Foundation and was |
| * originally based on software copyright (c) 1999, Lotus |
| * Development Corporation., http://www.lotus.com. For more |
| * information on the Apache Software Foundation, please see |
| * <http://www.apache.org/>. |
| */ |
| package org.apache.xml.utils; |
| |
| /** |
| * A digital search trie for 7-bit ASCII text |
| * The API is a subset of java.util.Hashtable |
| * The key must be a 7-bit ASCII string |
| * The value may be any Java Object |
| * @xsl.usage internal |
| */ |
| public class Trie |
| { |
| |
| /** Size of the m_nextChar array. */ |
| public static final int ALPHA_SIZE = 128; |
| |
| /** The root node of the tree. */ |
| Node m_Root; |
| |
| /** helper buffer to convert Strings to char arrays */ |
| private char[] m_charBuffer = new char[0]; |
| |
| /** |
| * Construct the trie. |
| */ |
| public Trie() |
| { |
| m_Root = new Node(); |
| } |
| |
| /** |
| * Put an object into the trie for lookup. |
| * |
| * @param key must be a 7-bit ASCII string |
| * @param value any java object. |
| * |
| * @return The old object that matched key, or null. |
| */ |
| public Object put(String key, Object value) |
| { |
| |
| final int len = key.length(); |
| if (len > m_charBuffer.length) |
| { |
| // make the biggest buffer ever needed in get(String) |
| m_charBuffer = new char[len]; |
| } |
| |
| Node node = m_Root; |
| |
| for (int i = 0; i < len; i++) |
| { |
| Node nextNode = node.m_nextChar[Character.toUpperCase(key.charAt(i))]; |
| |
| if (nextNode != null) |
| { |
| node = nextNode; |
| } |
| else |
| { |
| for (; i < len; i++) |
| { |
| Node newNode = new Node(); |
| // put this value into the tree with a case insensitive key |
| node.m_nextChar[Character.toUpperCase(key.charAt(i))] = newNode; |
| node.m_nextChar[Character.toLowerCase(key.charAt(i))] = newNode; |
| node = newNode; |
| } |
| break; |
| } |
| } |
| |
| Object ret = node.m_Value; |
| |
| node.m_Value = value; |
| |
| return ret; |
| } |
| |
| /** |
| * Get an object that matches the key. |
| * |
| * @param key must be a 7-bit ASCII string |
| * |
| * @return The object that matches the key, or null. |
| */ |
| public Object get(final String key) |
| { |
| |
| final int len = key.length(); |
| |
| /* If the name is too long, we won't find it, this also keeps us |
| * from overflowing m_charBuffer |
| */ |
| if (m_charBuffer.length < len) |
| return null; |
| |
| Node node = m_Root; |
| switch (len) // optimize the look up based on the number of chars |
| { |
| // case 0 looks silly, but the generated bytecode runs |
| // faster for lookup of elements of length 2 with this in |
| // and a fair bit faster. Don't know why. |
| case 0 : |
| { |
| return null; |
| } |
| |
| case 1 : |
| { |
| final char ch = key.charAt(0); |
| if (ch < ALPHA_SIZE) |
| { |
| node = node.m_nextChar[ch]; |
| if (node != null) |
| return node.m_Value; |
| } |
| return null; |
| } |
| // comment out case 2 because the default is faster |
| // case 2 : |
| // { |
| // final char ch0 = key.charAt(0); |
| // final char ch1 = key.charAt(1); |
| // if (ch0 < ALPHA_SIZE && ch1 < ALPHA_SIZE) |
| // { |
| // node = node.m_nextChar[ch0]; |
| // if (node != null) |
| // { |
| // |
| // if (ch1 < ALPHA_SIZE) |
| // { |
| // node = node.m_nextChar[ch1]; |
| // if (node != null) |
| // return node.m_Value; |
| // } |
| // } |
| // } |
| // return null; |
| // } |
| default : |
| { |
| key.getChars(0, len, m_charBuffer, 0); |
| // copy string into array |
| for (int i = 0; i < len; i++) |
| { |
| final char ch = m_charBuffer[i]; |
| if (ALPHA_SIZE <= ch) |
| { |
| // the key is not 7-bit ASCII so we won't find it here |
| return null; |
| } |
| |
| node = node.m_nextChar[ch]; |
| if (node == null) |
| return null; |
| } |
| |
| return node.m_Value; |
| } |
| } |
| } |
| |
| /** |
| * The node representation for the trie. |
| * @xsl.usage internal |
| */ |
| class Node |
| { |
| |
| /** |
| * Constructor, creates a Node[ALPHA_SIZE]. |
| */ |
| Node() |
| { |
| m_nextChar = new Node[ALPHA_SIZE]; |
| m_Value = null; |
| } |
| |
| /** The next nodes. */ |
| Node m_nextChar[]; |
| |
| /** The value. */ |
| Object m_Value; |
| } |
| } |
