textmaven.tst
Class TernarySearchTree

java.lang.Object
  extended bytextmaven.tst.TernarySearchTree

public class TernarySearchTree
extends java.lang.Object

Implementation of ternary search tree. A Ternary Search Tree is a data structure that behaves in a manner that is very similar to a HashMap.

Author:
Wally Flint (the original implementation), Peter Kolloch (minor improvements and additions)

Constructor Summary
TernarySearchTree()
           
 
Method Summary
 java.lang.Object get(java.lang.String key)
          Retrieve the object indexed by key.
protected  java.lang.String getKey(textmaven.tst.TSTNode node)
          Returns the key that indexes the node argument.
 int getLastNumReturnValues()
          Returns the number of values returned by the last call to matchAlmostString or matchPrefixString methods.
 textmaven.tst.TSTNode getNode(java.lang.String key)
          Returns the Node indexed by key, or null if that node doesn't exist.
protected  textmaven.tst.TSTNode getNode(java.lang.String key, textmaven.tst.TSTNode startNode)
          Returns the Node indexed by key, or null if that node doesn't exist.
protected  textmaven.tst.TSTNode getOrCreateNode(java.lang.String key)
          Returns the Node indexed by key, creating that node if it doesn't exist, and creating any required.
 TSTIterator iterator()
          Returns an iterator over all entries in this tree.
static void main(java.lang.String[] args)
           
 DoublyLinkedList matchAlmost(java.lang.String key)
          Returns a list of keys that almost match argument key.
protected  DoublyLinkedList matchAlmost(java.lang.String key, int numReturnValues)
          Returns a list of keys that almost match argument key.
 java.lang.String matchAlmostString(java.lang.String key)
          Returns a String representation of keys that almost match argument key.
protected  java.lang.String matchAlmostString(java.lang.String key, int numReturnValues)
          Returns a String representation of keys that almost match argument key.
 DoublyLinkedList matchPrefix(java.lang.String prefix)
          Returns alphabetical list of all keys in the tree that begin with prefix.
 DoublyLinkedList matchPrefix(java.lang.String prefix, int numReturnValues)
          Returns alphabetical list of all keys in the tree that begin with prefix.
 java.lang.String[] matchPrefixArray(java.lang.String prefix, int numReturnValues)
           
 java.lang.String[] matchPrefixAsArray(java.lang.String prefix)
           
 java.lang.String matchPrefixString(java.lang.String prefix)
          Returns alphabetical list of all keys in the tree that begin with prefix.
 java.lang.String matchPrefixString(java.lang.String prefix, int numReturnValues)
          Returns alphabetical list of all keys in the tree that begin with prefix.
 int numDataNodes()
          Returns the number of nodes in the tree that have non-null data.
protected  int numDataNodes(textmaven.tst.TSTNode startingNode)
          Returns the number of nodes in the subtree below and including startingNode.
 int numNodes()
          Returns the total number of nodes in the tree.
protected  int numNodes(textmaven.tst.TSTNode startingNode)
          Returns the total number of nodes in the subtree below and including startingNode.
protected  void printTree()
          Prints entire tree structure to standard output, beginning with the root node and workind down.
protected  void printTree(textmaven.tst.TSTNode startingNode)
          Prints subtree structure to standard output, beginning with startingNode and workind down.
 void put(java.lang.String key, java.lang.Object value)
          Stores value in the TernarySearchTree.
 void remove(java.lang.String key)
          Removes value indexed by key.
 void setMatchAlmostDiff(int diff)
          Sets the number of characters by which words can differ from target word when calling matchAlmost or matchAlmostString methods.
 void setNumReturnValues(int num)
          Sets default maximum number of values returned from matchPrefix, matchPrefixString, matchAlmost, and matchAlmostString methods.
protected  DoublyLinkedList sortKeys(textmaven.tst.TSTNode startNode, int numReturnValues)
          Returns keys sorted in alphabetical order.
 java.lang.String sortKeysString()
           
 java.lang.String sortKeysString(int numReturnValues)
           
 java.lang.String sortKeysString(textmaven.tst.TSTNode startNode, int numReturnValues)
          Returns keys sorted in alphabetical order, returning a result of type String.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

TernarySearchTree

public TernarySearchTree()
Method Detail

put

public void put(java.lang.String key,
                java.lang.Object value)
Stores value in the TernarySearchTree. The value may be retrieved using key.

Parameters:
key - A string that indexes the object to be stored.
value - The object to be stored in the tree.

get

public java.lang.Object get(java.lang.String key)
Retrieve the object indexed by key.

Parameters:
key - A String index.
Returns:
Object The object retrieved from the TernarySearchTree.

remove

public void remove(java.lang.String key)
Removes value indexed by key. Also removes all nodes that are rendered unnecessary by the removal of this data.

Parameters:
key - A string that indexes the object to be removed from the tree.

setNumReturnValues

public void setNumReturnValues(int num)
Sets default maximum number of values returned from matchPrefix, matchPrefixString, matchAlmost, and matchAlmostString methods.

Parameters:
num - The number of values that will be returned when calling the methods above. Set this to -1 to get an unlimited number of return values. Note that the methods mentioned above provide overloaded versions that allow you to specify the maximum number of return values, in which case this value is temporarily overridden.

getLastNumReturnValues

public int getLastNumReturnValues()
Returns the number of values returned by the last call to matchAlmostString or matchPrefixString methods. (This is really just for the purposes of the demo applet.)


getNode

public textmaven.tst.TSTNode getNode(java.lang.String key)
Returns the Node indexed by key, or null if that node doesn't exist. Search begins at root node.

Parameters:
key - An index that points to the desired node.
Returns:
TSTNode The node object indexed by key. This object is an instance of an inner class named TernarySearchTree.TSTNode.

getNode

protected textmaven.tst.TSTNode getNode(java.lang.String key,
                                        textmaven.tst.TSTNode startNode)
Returns the Node indexed by key, or null if that node doesn't exist. Search begins at root node.

Parameters:
key - An index that points to the desired node.
startNode - The top node defining the subtree to be searched.
Returns:
TSTNode The node object indexed by key. This object is an instance of an inner class named TernarySearchTree.TSTNode.

matchPrefix

public DoublyLinkedList matchPrefix(java.lang.String prefix)
Returns alphabetical list of all keys in the tree that begin with prefix. Only keys for nodes having non-null data are included in the list.

Parameters:
prefix - Each key returned from this method will begin with the characters in prefix.
Returns:
DoublyLinkedList An implementation of a LinkedList that is java 1.1 compatible.

matchPrefix

public DoublyLinkedList matchPrefix(java.lang.String prefix,
                                    int numReturnValues)
Returns alphabetical list of all keys in the tree that begin with prefix. Only keys for nodes having non-null data are included in the list.

Parameters:
prefix - Each key returned from this method will begin with the characters in prefix.
numReturnValues - The maximum number of values returned from this method.
Returns:
DoublyLinkedList An implementation of a LinkedList that is java 1.1 compatible.

matchPrefixAsArray

public java.lang.String[] matchPrefixAsArray(java.lang.String prefix)

matchPrefixArray

public java.lang.String[] matchPrefixArray(java.lang.String prefix,
                                           int numReturnValues)

matchPrefixString

public java.lang.String matchPrefixString(java.lang.String prefix)
Returns alphabetical list of all keys in the tree that begin with prefix. Only keys for nodes having non-null data are included in the list.

Parameters:
prefix - Each key returned from this method will begin with the characters in prefix.
Returns:
String A string representation of all keys matching the argument prefix. Keys are delimited with the newline char ('\n').

matchPrefixString

public java.lang.String matchPrefixString(java.lang.String prefix,
                                          int numReturnValues)
Returns alphabetical list of all keys in the tree that begin with prefix. Only keys for nodes having non-null data are included in the list.

Parameters:
prefix - Each key returned from this method will begin with the characters in prefix.
numReturnValues - The maximum number of values returned from this method.
Returns:
String A string representation of all keys matching the argument prefix. Keys are delimited with the newline char ('\n').

sortKeys

protected DoublyLinkedList sortKeys(textmaven.tst.TSTNode startNode,
                                    int numReturnValues)
Returns keys sorted in alphabetical order. Includes startNode and all nodes connected to startNode. Number of keys returned is limited to numReturnValues. To get a list that isn't limited in size, set numReturnValues to -1.

Parameters:
startNode - The top node defining the subtree to be searched.
numReturnValues - The maximum number of values returned from this method.
Returns:
DoublyLinkedList An implementation of a LinkedList that is java 1.1 compatible.

sortKeysString

public java.lang.String sortKeysString(int numReturnValues)

sortKeysString

public java.lang.String sortKeysString()

sortKeysString

public java.lang.String sortKeysString(textmaven.tst.TSTNode startNode,
                                       int numReturnValues)
Returns keys sorted in alphabetical order, returning a result of type String. Includes startNode and all nodes connected to startNode. Number of keys returned is limited to numReturnValues. To get a list that isn't limited in size, set numReturnValues to -1.

Parameters:
startNode - The top node defining the subtree to be searched.
numReturnValues - The maximum number of values returned from this method.
Returns:
String A string representation of keys in alphabetical order.

matchAlmost

public DoublyLinkedList matchAlmost(java.lang.String key)
Returns a list of keys that almost match argument key. Keys returned will have exactly diff characters that do not match the target key, where diff is equal to the last value passed in as an argument to the setMatchAlmostDiff method. If the matchAlmost method is called before the setMatchAlmostDiff method has been called for the first time, then diff = 0.

Parameters:
key - The target key.
Returns:
DoublyLinkedList An implementation of a LinkedList that is java 1.1 compatible.

matchAlmost

protected DoublyLinkedList matchAlmost(java.lang.String key,
                                       int numReturnValues)
Returns a list of keys that almost match argument key. Keys returned will have exactly diff characters that do not match the target key, where diff is equal to the last value passed in as an argument to the setMatchAlmostDiff method. If the matchAlmost method is called before the setMatchAlmostDiff method has been called for the first time, then diff = 0.

Parameters:
key - The target key.
numReturnValues - The maximum number of values returned by this method.
Returns:
DoublyLinkedList An implementation of a LinkedList that is java 1.1 compatible.

matchAlmostString

public java.lang.String matchAlmostString(java.lang.String key)
Returns a String representation of keys that almost match argument key. Keys returned will have exactly diff characters that do not match the target key, where diff is equal to the last value passed in as an argument to the setMatchAlmostDiff method. If the matchAlmost method is called before the setMatchAlmostDiff method has been called for the first time, then diff = 0.

Parameters:
key - The target key.
Returns:
String A String representation of keys that almost match the target key. Keys are delimited by the newline char ('\n').

matchAlmostString

protected java.lang.String matchAlmostString(java.lang.String key,
                                             int numReturnValues)
Returns a String representation of keys that almost match argument key. Keys returned will have exactly diff characters that do not match the target key, where diff is equal to the last value passed in as an argument to the setMatchAlmostDiff method. If the matchAlmost method is called before the setMatchAlmostDiff method has been called for the first time, then diff = 0.

Parameters:
key - The target key.
numReturnValues - The maximum number of values returned by this method.
Returns:
String A String representation of keys that almost match the target key. Keys are delimited by the newline char ('\n').

setMatchAlmostDiff

public void setMatchAlmostDiff(int diff)
Sets the number of characters by which words can differ from target word when calling matchAlmost or matchAlmostString methods. Arguments less than 1 will set the char difference to 1, and arguments greater than 4 will set the char difference to 4.

Parameters:
diff - The number of characters by which words can differ from target word.

getOrCreateNode

protected textmaven.tst.TSTNode getOrCreateNode(java.lang.String key)
                                         throws java.lang.NullPointerException,
                                                java.lang.IllegalArgumentException
Returns the Node indexed by key, creating that node if it doesn't exist, and creating any required. intermediate nodes if they don't exist.

Parameters:
key - A string that indexes the node that is returned.
Returns:
TSTNode The node object indexed by key. This object is an instance of an inner class named TernarySearchTree.TSTNode.
Throws:
java.lang.NullPointerException
java.lang.IllegalArgumentException

iterator

public TSTIterator iterator()
Returns an iterator over all entries in this tree.


getKey

protected java.lang.String getKey(textmaven.tst.TSTNode node)
Returns the key that indexes the node argument.

Parameters:
node - The node whose index is to be calculated.
Returns:
String The string that indexes the node argument.

numNodes

public int numNodes()
Returns the total number of nodes in the tree. Counts nodes whether or not they have data.

Returns:
int The total number of nodes in the tree.

numNodes

protected int numNodes(textmaven.tst.TSTNode startingNode)
Returns the total number of nodes in the subtree below and including startingNode. Counts nodes whether or not they have data.

Parameters:
startingNode - The top node of the subtree. The node that defines the subtree.
Returns:
int The total number of nodes in the subtree.

numDataNodes

public int numDataNodes()
Returns the number of nodes in the tree that have non-null data.

Returns:
int The number of nodes in the tree that have non-null data.

numDataNodes

protected int numDataNodes(textmaven.tst.TSTNode startingNode)
Returns the number of nodes in the subtree below and including startingNode. Counts only nodes that have non-null data.

Parameters:
startingNode - The top node of the subtree. The node that defines the subtree.
Returns:
int The total number of nodes in the subtree.

printTree

protected void printTree()
Prints entire tree structure to standard output, beginning with the root node and workind down.


printTree

protected void printTree(textmaven.tst.TSTNode startingNode)
Prints subtree structure to standard output, beginning with startingNode and workind down.


main

public static void main(java.lang.String[] args)


Copyright © 2002-2005 Sourceforge. All Rights Reserved.