|
|||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Object textmaven.tst.TernarySearchTree
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.
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 |
public TernarySearchTree()
Method Detail |
public void put(java.lang.String key, java.lang.Object value)
key
- A string that indexes the object to be stored.value
- The object to be stored in the tree.public java.lang.Object get(java.lang.String key)
key
- A String index.
public void remove(java.lang.String key)
key
- A string that indexes the object to be removed from the tree.public void setNumReturnValues(int num)
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.public int getLastNumReturnValues()
public textmaven.tst.TSTNode getNode(java.lang.String key)
key
- An index that points to the desired node.
protected textmaven.tst.TSTNode getNode(java.lang.String key, textmaven.tst.TSTNode startNode)
key
- An index that points to the desired node.startNode
- The top node defining the subtree to be searched.
public DoublyLinkedList matchPrefix(java.lang.String prefix)
prefix
- Each key returned from this method will begin with the characters in prefix.
public DoublyLinkedList matchPrefix(java.lang.String prefix, int numReturnValues)
prefix
- Each key returned from this method will begin with the characters in prefix.numReturnValues
- The maximum number of values returned from this method.
public java.lang.String[] matchPrefixAsArray(java.lang.String prefix)
public java.lang.String[] matchPrefixArray(java.lang.String prefix, int numReturnValues)
public java.lang.String matchPrefixString(java.lang.String prefix)
prefix
- Each key returned from this method will begin with the characters in prefix.
public java.lang.String matchPrefixString(java.lang.String prefix, int numReturnValues)
prefix
- Each key returned from this method will begin with the characters in prefix.numReturnValues
- The maximum number of values returned from this method.
protected DoublyLinkedList sortKeys(textmaven.tst.TSTNode startNode, int numReturnValues)
startNode
- The top node defining the subtree to be searched.numReturnValues
- The maximum number of values returned from this method.
public java.lang.String sortKeysString(int numReturnValues)
public java.lang.String sortKeysString()
public java.lang.String sortKeysString(textmaven.tst.TSTNode startNode, int numReturnValues)
startNode
- The top node defining the subtree to be searched.numReturnValues
- The maximum number of values returned from this method.
public DoublyLinkedList matchAlmost(java.lang.String key)
key
- The target key.
protected DoublyLinkedList matchAlmost(java.lang.String key, int numReturnValues)
key
- The target key.numReturnValues
- The maximum number of values returned by this method.
public java.lang.String matchAlmostString(java.lang.String key)
key
- The target key.
protected java.lang.String matchAlmostString(java.lang.String key, int numReturnValues)
key
- The target key.numReturnValues
- The maximum number of values returned by this method.
public void setMatchAlmostDiff(int diff)
diff
- The number of characters by which words can differ from target word.protected textmaven.tst.TSTNode getOrCreateNode(java.lang.String key) throws java.lang.NullPointerException, java.lang.IllegalArgumentException
key
- A string that indexes the node that is returned.
java.lang.NullPointerException
java.lang.IllegalArgumentException
public TSTIterator iterator()
protected java.lang.String getKey(textmaven.tst.TSTNode node)
node
- The node whose index is to be calculated.
public int numNodes()
protected int numNodes(textmaven.tst.TSTNode startingNode)
startingNode
- The top node of the subtree. The node that defines the subtree.
public int numDataNodes()
protected int numDataNodes(textmaven.tst.TSTNode startingNode)
startingNode
- The top node of the subtree. The node that defines the subtree.
protected void printTree()
protected void printTree(textmaven.tst.TSTNode startingNode)
public static void main(java.lang.String[] args)
|
|||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |