Java example source code file (Trie.java)

This example Java source code file (Trie.java) is included in the alvinalexander.com "Java Source Code Warehouse" project. The intent of this project is to help you "Learn Java by Example" ^TM.

Learn more about this Java project at its project page.

Java - Java tags/keywords

alpha_size, node, object, string, trie

The Trie.java Java example source code

/*
 * reserved comment block
 * DO NOT REMOVE OR ALTER!
 */
/*
 * Copyright 1999-2004 The Apache Software Foundation.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
/*
 * $Id: Trie.java,v 1.2.4.1 2005/09/15 08:15:59 suresh_emailid Exp $
 */
package com.sun.org.apache.xml.internal.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;
  }
}