Class TernarySearchTree

java.lang.Object
  |
  +--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.

Inner Class Summary

protected class

TernarySearchTree.TSTNode An inner class of TernarySearchTree that represents a node in the tree.

Constructor Summary

TernarySearchTree()

Method Summary

java.lang.Object	get(java.lang.String key) Retrieve the object indexed by key.
protected java.lang.String	getKey(TernarySearchTree.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.
TernarySearchTree.TSTNode	getNode(java.lang.String key) Returns the Node indexed by key, or null if that node doesn't exist.
protected TernarySearchTree.TSTNode	getNode(java.lang.String key, TernarySearchTree.TSTNode startNode) Returns the Node indexed by key, or null if that node doesn't exist.
protected TernarySearchTree.TSTNode	getOrCreateNode(java.lang.String key) Returns the Node indexed by key, creating that node if it doesn't exist, and creating any required.
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	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(TernarySearchTree.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(TernarySearchTree.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(TernarySearchTree.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(TernarySearchTree.TSTNode startNode, int numReturnValues) Returns keys sorted in alphabetical order.
java.lang.String	sortKeysString()
java.lang.String	sortKeysString(int numReturnValues)
java.lang.String	sortKeysString(TernarySearchTree.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 TernarySearchTree.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 TernarySearchTree.TSTNode getNode(java.lang.String key,
                                            TernarySearchTree.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.

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(TernarySearchTree.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(TernarySearchTree.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 TernarySearchTree.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.

getKey

protected java.lang.String getKey(TernarySearchTree.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(TernarySearchTree.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(TernarySearchTree.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(TernarySearchTree.TSTNode startingNode)

Prints subtree structure to standard output, beginning with startingNode and workind down.