trie.java

矩阵的QR分解算法

/*
 *    This program is free software; you can redistribute it and/or modify
 *    it under the terms of the GNU General Public License as published by
 *    the Free Software Foundation; either version 2 of the License, or
 *    (at your option) any later version.
 *
 *    This program is distributed in the hope that it will be useful,
 *    but WITHOUT ANY WARRANTY; without even the implied warranty of
 *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *    GNU General Public License for more details.
 *
 *    You should have received a copy of the GNU General Public License
 *    along with this program; if not, write to the Free Software
 *    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 */

/*
 * Trie.java
 * Copyright (C) 2007 University of Waikato, Hamilton, New Zealand
 */

package weka.core;

import java.io.Serializable;
import java.lang.reflect.Array;
import java.util.Collection;
import java.util.Enumeration;
import java.util.Hashtable;
import java.util.Iterator;
import java.util.Vector;

import javax.swing.tree.DefaultMutableTreeNode;

/**
 * A class representing a Trie data structure for strings.
 * See also <a href="http://en.wikipedia.org/wiki/Trie" target="_blank">Trie</a> 
 * on WikiPedia.
 * 
 * @author  fracpete (fracpete at waikato dot ac dot nz)
 * @version $Revision: 1.1 $
 */
public class Trie
  implements Serializable, Cloneable, Collection<String> {

  /** for serialization */
  private static final long serialVersionUID = -5897980928817779048L;

  /**
   * Represents a node in the trie.
   * 
   * @author  fracpete (fracpete at waikato dot ac dot nz)
   * @version $Revision: 1.1 $
   */
  public static class TrieNode
    extends DefaultMutableTreeNode {
    
    /** for serialization */
    private static final long serialVersionUID = -2252907099391881148L;
    
    /** the stop character */
    public final static Character STOP = '\0';

    /** for fast access to the children */
    protected Hashtable<Character,TrieNode> m_Children;
    
    /**
     * initializes the node
     * 
     * @param c		the value of this node
     */
    public TrieNode(char c) {
      this(new Character(c));
    }
    
    /**
     * initializes the node
     * 
     * @param c		the value of this node
     */
    public TrieNode(Character c) {
      super(c);
      
      m_Children = new Hashtable<Character,TrieNode>(100);
    }
    
    /**
     * returns the stored character
     * 
     * @return		the stored character
     */
    public Character getChar() {
      return (Character) getUserObject();
    }
    
    /**
     * sets the character this node represents
     * 
     * @param value	the character to store
     */
    public void setChar(Character value) {
      setUserObject(value);
    }

    /**
     * adds the given string to its children (creates children if necessary)
     * 
     * @param suffix	the suffix to add to its children
     * @return		true if the add operation changed the structure
     */
    public boolean add(String suffix) {
      boolean		result;
      Character 	c;
      String		newSuffix;
      TrieNode		child;
      
      result    = false;
      c         = suffix.charAt(0);
      newSuffix = suffix.substring(1);
      
      // find child and add if necessary
      child = m_Children.get(c);
      if (child == null) {
	result = true;
	child = add(c);
      }
      
      // propagate remaining suffix
      if (newSuffix.length() > 0)
	result = child.add(newSuffix) || result;
      
      return result;
    }
    
    /**
     * adds the given charater to its children
     * 
     * @param c		the character to add
     * @return		the generated child node
     */
    protected TrieNode add(Character c) {
      TrieNode	child;
      
      child = new TrieNode(c);
      add(child);
      m_Children.put(c, child);
      
      return child;
    }
    
    /**
     * removes the given characted from its children
     * 
     * @param c		the character to remove
     */
    protected void remove(Character c) {
      TrieNode	child;
      
      child = m_Children.get(c);
      remove(child);
      m_Children.remove(c);
    }
    
    /**
     * Removes a suffix from the trie.
     * 
     * @param suffix	the suffix to remove
     * @return		true if this trie changed as a result of the call
     */
    public boolean remove(String suffix) {
      boolean		result;
      Character		c;
      String		newSuffix;
      TrieNode		child;
      
      c         = suffix.charAt(0);
      newSuffix = suffix.substring(1);
      child     = m_Children.get(c);
      
      if (child == null) {
	result = false;
      }
      else if (newSuffix.length() == 0) {
	remove(c);
	result = true;
      }
      else {
	result = child.remove(newSuffix);
	if (child.getChildCount() == 0)
	  remove(child.getChar());
      }
      
      return result;
    }

    /**
     * checks whether a suffix can be found in its children
     * 
     * @param suffix	the suffix to look for
     * @return		true if suffix was found
     */
    public boolean contains(String suffix) {
      boolean		result;
      Character 	c;
      String		newSuffix;
      TrieNode		child;
      
      c         = suffix.charAt(0);
      newSuffix = suffix.substring(1);
      child     = m_Children.get(c);
      
      if (child == null)
	result = false;
      else if (newSuffix.length() == 0)
	result = true;
      else
	result = child.contains(newSuffix);

      return result;
    }
    
    /**
     * creates a deep copy of itself
     * 
     * @return		a deep copy of itself
     */
    public Object clone() {
      TrieNode			result;
      Enumeration<Character>	keys;
      Character			key;
      TrieNode			child;
      
      result = new TrieNode(getChar());
      keys   = m_Children.keys();
      while (keys.hasMoreElements()) {
	key   = keys.nextElement();
	child = (TrieNode) m_Children.get(key).clone();
	result.add(child);
	result.m_Children.put(key, child);
      }
      
      return result;
    }
    
    /**
     * Indicates whether some other object is "equal to" this one.
     * 
     * @param obj	the object to check for equality
     * @return		true if equal
     */
    public boolean equals(Object obj) {
      boolean			result;
      TrieNode 			node;
      Enumeration<Character>	keys;
      Character			key;
      
      node   = (TrieNode) obj;
      
      // is payload the same?
      if (getChar() == null)
	result = (node.getChar() == null);
      else
	result = getChar().equals(node.getChar());
      
      // check children
      if (result) {
	keys = m_Children.keys();
	while (keys.hasMoreElements()) {
	  key    = keys.nextElement();
	  result = m_Children.get(key).equals(node.m_Children.get(key));
	  if (!result)
	    break;
	}
      }
      
      return result;
    }

    /**
     * returns the node with the given suffix
     * 
     * @param suffix	the suffix to look for
     * @return		null if unsuccessful otherwise the corresponding node
     */
    public TrieNode find(String suffix) {
      TrieNode		result;
      Character 	c;
      String		newSuffix;
      TrieNode		child;
      
      c         = suffix.charAt(0);
      newSuffix = suffix.substring(1);
      child     = m_Children.get(c);
      
      if (child == null)
	result = null;
      else if (newSuffix.length() == 0)
	result = child;
      else
	result = child.find(newSuffix);

      return result;
    }

    /**
     * returns the common prefix for all the nodes starting with this node.
     * The result includes this node, unless it's the root node or a STOP node.
     * 
     * @return			the result of the search
     */
    public String getCommonPrefix() {
      return getCommonPrefix("");
    }

    /**
     * returns the common prefix for all the nodes starting with the node
     * for the specified prefix. Can be null if initial prefix is not found.
     * The result includes this node, unless it's the root node or a STOP node.
     * Using the empty string means starting with this node.
     * 
     * @param startPrefix	the prefix of the node to start the search from
     * @return			the result of the search, null if startPrefix
     * 				cannot be found
     */
    public String getCommonPrefix(String startPrefix) {
      String	result;
      TrieNode	startNode;

      if (startPrefix.length() == 0)
	startNode = this;
      else
	startNode = find(startPrefix);
      
      if (startNode == null)
	result = null;
      else
	result = startPrefix + startNode.determineCommonPrefix("");
	
      return result;
    }

    /**
     * determines the common prefix of the nodes.
     * 
     * @param currentPrefix	the common prefix found so far
     * @return			the result of the search
     */
    protected String determineCommonPrefix(String currentPrefix) {
      String	result;
      String	newPrefix;
      
      if (!isRoot() && (getChar() != STOP))
	newPrefix = currentPrefix + getChar();
      else
	newPrefix = currentPrefix;
      
      if (m_Children.size() == 1)
	result = ((TrieNode) getChildAt(0)).determineCommonPrefix(newPrefix);
      else
	result = newPrefix;
      
      return result;
    }
    
    /**
     * returns the number of stored strings, i.e., leaves
     * 
     * @return		the number of stored strings
     */
    public int size() {
      int	result;
      TrieNode	leaf;
      
      result = 0;
      leaf   = (TrieNode) getFirstLeaf();
      while (leaf != null) {
	if (leaf != getRoot())
	  result++;
	leaf = (TrieNode) leaf.getNextLeaf();
      }
      
      return result;
    }
    
    /**
     * returns the full string up to the root
     * 
     * @return		the full string to the root
     */
    public String getString() {
      char[]	result;
      TrieNode	node;
      
      result = new char[this.getLevel()];
      node   = this;
      while (node.getParent() != null) {
	if (node.isRoot())
	  break;
	else
	  result[node.getLevel() - 1] = node.getChar();
	node = (TrieNode) node.getParent();
      }
      
      return new String(result);
    }
    
    /**
     * returns the node in a string representation
     * 
     * @return		the node as string
     */
    public String toString() {
      return "" + getChar();
    }
  }
  
  /**
   * Represents an iterator over a trie
   * 
   * @author  fracpete (fracpete at waikato dot ac dot nz)
   * @version $Revision: 1.1 $
   */
  public static class TrieIterator 
    implements Iterator<String> {
    
    /** the node to use as root */
    protected TrieNode m_Root;
    
    /** the last leaf for this root node */
    protected TrieNode m_LastLeaf;