trie.java

矩阵的QR分解算法

    /** the current leaf node */
    protected TrieNode m_CurrentLeaf;
    
    /**
     * initializes the iterator
     * 
     * @param node		the node to use as root
     */
    public TrieIterator(TrieNode node) {
      super();
      
      m_Root        = node;
      m_CurrentLeaf = (TrieNode) m_Root.getFirstLeaf();
      m_LastLeaf    = (TrieNode) m_Root.getLastLeaf();
    }
    
    /**
     * Returns true if the iteration has more elements.
     * 
     * @return		true if there is at least one more element
     */
    public boolean hasNext() {
      return (m_CurrentLeaf != null);
    }
    
    /**
     * Returns the next element in the iteration.
     * 
     * @return		the next element
     */
    public String next() {
      String	result;
      
      result        = m_CurrentLeaf.getString();
      result        = result.substring(0, result.length() - 1);  // remove STOP
      if (m_CurrentLeaf != m_LastLeaf)
	m_CurrentLeaf = (TrieNode) m_CurrentLeaf.getNextLeaf();
      else
	m_CurrentLeaf = null;
      
      return result;
    }
    
    /**
     * ignored
     */
    public void remove() {
    }
  }
  
  /** the root node */
  protected TrieNode m_Root;

  /** the hash code */
  protected int m_HashCode;
  
  /** whether the structure got modified and the hash code needs to be 
   * re-calculated */
  protected boolean m_RecalcHashCode;
  
  /**
   * initializes the data structure
   */
  public Trie() {
    super();
    
    m_Root           = new TrieNode(null);
    m_RecalcHashCode = true;
  }
  
  /**
   * Ensures that this collection contains the specified element.
   * 
   * @param o		the string to add
   * @return		true if the structure changed
   */
  public boolean add(String o) {
    return m_Root.add(o + TrieNode.STOP);
  }
  
  /**
   * Adds all of the elements in the specified collection to this collection 
   * 
   * @param c		the collection to add
   */
  public boolean addAll(Collection<? extends String> c) {
    boolean		result;
    Iterator<String>	iter;
    
    result = false;
    
    iter = (Iterator<String>) c.iterator();
    while (iter.hasNext())
      result = add(iter.next()) || result;
    
    return result;
  }
  
  /**
   * Removes all of the elements from this collection
   */
  public void clear() {
    m_Root.removeAllChildren();
    m_RecalcHashCode = true;
  }

  /**
   * returns a deep copy of itself
   * 
   * @return		a copy of itself
   */
  public Object clone() {
    Trie	result;
    
    result = new Trie();
    result.m_Root = (TrieNode) m_Root.clone();
    
    return result;
  }
  
  /**
   * Returns true if this collection contains the specified element.
   * 
   * @param o		the object to check for in trie
   * @return		true if found
   */
  public boolean contains(Object o) {
    return m_Root.contains(((String) o) + TrieNode.STOP);
  }
  
  /**
   * Returns true if this collection contains all of the elements in the 
   * specified collection.
   * 
   * @param c		the collection to look for in the trie
   * @return		true if all elements were found
   */
  public boolean containsAll(Collection<?> c) {
    boolean	result;
    Iterator	iter;
    
    result = true;
    
    iter = c.iterator();
    while (iter.hasNext()) {
      if (!contains(iter.next())) {
	result = false;
	break;
      }
    }
    
    return result;
  }
  
  /**
   * checks whether the given prefix is stored in the trie
   * 
   * @param prefix	the prefix to check
   * @return		true if the prefix is part of the trie
   */
  public boolean containsPrefix(String prefix) {
    return m_Root.contains(prefix);
  }
  
  /**
   * Compares the specified object with this collection for equality.
   * 
   * @param o		the object to check for equality
   */
  public boolean equals(Object o) {
    return m_Root.equals(((Trie) o).getRoot());
  }

  /**
   * returns the common prefix for all the nodes
   * 
   * @return		the result of the search
   */
  public String getCommonPrefix() {
    return m_Root.getCommonPrefix();
  }

  /**
   * returns the root node of the trie
   * 
   * @return		the root node
   */
  public TrieNode getRoot() {
    return m_Root;
  }

  /**
   * returns all stored strings that match the given prefix
   * 
   * @param prefix	the prefix that all strings must have
   * @return		all strings that match the prefix
   */
  public Vector<String> getWithPrefix(String prefix) {
    Vector<String>	result;
    TrieNode		node;
    TrieIterator	iter;
    
    result = new Vector<String>();
    
    if (containsPrefix(prefix)) {
      node = m_Root.find(prefix);
      iter = new TrieIterator(node);
      while (iter.hasNext())
	result.add(iter.next());
    }
    
    return result;
  }
  
  /**
   * Returns the hash code value for this collection.
   * 
   * @return		the hash code
   */
  public int hashCode() {
    if (m_RecalcHashCode) {
      m_HashCode       = toString().hashCode();
      m_RecalcHashCode = false;
    }
    
    return m_HashCode;
  }
  
  /**
   * Returns true if this collection contains no elements.
   * 
   * @return		true if empty
   */
  public boolean isEmpty() {
    return (m_Root.getChildCount() == 0);
  }

  /**
   * Returns an iterator over the elements in this collection.
   * 
   * @return		returns an iterator over all the stored strings
   */
  public Iterator<String> iterator() {
    return new TrieIterator(m_Root);
  }
  
  /**
   * Removes a single instance of the specified element from this collection, 
   * if it is present.
   * 
   * @param o		the object to remove
   * @return		true if this collection changed as a result of the call
   */
  public boolean remove(Object o) {
    boolean	result;
    
    result = m_Root.remove(((String) o) + TrieNode.STOP);
    
    m_RecalcHashCode = result;
    
    return result;
  }
  
  /**
   * Removes all this collection's elements that are also contained in the 
   * specified collection
   * 
   * @param c		the collection to remove
   * @return		true if the collection changed
   */
  public boolean removeAll(Collection<?> c) {
    boolean	result;
    Iterator	iter;
    
    result = false;
    
    iter = c.iterator();
    while (iter.hasNext()) {
      result = remove(iter.next()) || result;
    }
    
    m_RecalcHashCode = result;
    
    return result;
  }
  
  /**
   * Retains only the elements in this collection that are contained in 
   * the specified collection
   * 
   * @param c		the collection to use as reference
   * @return		true if this collection changed as a result of the call
   */
  public boolean retainAll(Collection<?> c) {
    boolean	result;
    Iterator	iter;
    Object	o;
    
    result = false;
    iter   = iterator();
    while (iter.hasNext()) {
      o = iter.next();
      if (!c.contains(o))
	result = remove(o) || result;
    }
    
    m_RecalcHashCode = result;

    return result;
  }
  
  /**
   * Returns the number of elements in this collection.
   * 
   * @return		the number of nodes in the tree
   */
  public int size() {
    return m_Root.size();
  }
  
  /**
   * Returns an array containing all of the elements in this collection.
   * 
   * @return		the stored strings as array
   */
  public Object[] toArray() {
    return toArray(new String[0]);
  }
  
  /**
   * Returns an array containing all of the elements in this collection; the 
   * runtime type of the returned array is that of the specified array.
   * 
   * @param a		the array into which the elements of this collection 
   * 			are to be stored
   * @return		an array containing the elements of this collection
   */
  public <T> T[] toArray(T[] a) {
    Object[]	result;
    Iterator	iter;
    Vector	list;
    int		i;
    
    list = new Vector();
    iter = iterator();
    while (iter.hasNext())
      list.add(iter.next());
    
    if (Array.getLength(a) != list.size())
      result = (Object[]) Array.newInstance(a.getClass().getComponentType(), list.size());
    else
      result = a;
    
    for (i = 0; i < list.size(); i++)
      result[i] = list.get(i);
    
    return (T[]) result;
  }

  /**
   * returns the node as String
   * 
   * @param node	the node to turn into a string
   * @return		the node as string
   */
  protected String toString(TrieNode node) {
    StringBuffer	result;
    int			i;
    StringBuffer	indentation;
    
    result = new StringBuffer();
    
    // indent the node
    indentation = new StringBuffer();
    for (i = 0; i < node.getLevel(); i++)
      indentation.append(" | ");
    result.append(indentation.toString());
    
    // add the node label
    if (node.getChar() == null)
      result.append("<root>");
    else if (node.getChar() == TrieNode.STOP)
      result.append("STOP");
    else
      result.append("'" + node.getChar() + "'");
    result.append("\n");

    // add the children
    for (i = 0; i < node.getChildCount(); i++)
      result.append(toString((TrieNode) node.getChildAt(i)));
    
    return result.toString();
  }
  
  /**
   * returns the trie in string representation
   * 
   * @return		the trie as string
   */
  public String toString() {
    return toString(m_Root);
  }
  
  /**
   * Only for testing (prints the built Trie). Arguments are added to the Trie. 
   * If not arguments provided then a few default strings are uses for building.
   * 
   * @param args	commandline arguments
   */
  public static void main(String[] args) {
    String[] data;
    
    if (args.length == 0) {
      data = new String[3];
      data[0] = "this is a test";
      data[1] = "this is another test";
      data[2] = "and something else";
    }
    else {
      data = args.clone();
    }

    // build trie
    Trie t = new Trie();
    for (int i = 0; i < data.length; i++)
      t.add(data[i]);
    System.out.println(t);
  }
}