org.passay.dictionary

Class TernaryTree

java.lang.Object

org.passay.dictionary.TernaryTree

public class TernaryTree
extends Object

Implementation of a ternary tree. Methods are provided for inserting strings and searching for strings. The algorithms in this class are all recursive, and have not been optimized for any particular purpose. Data which is inserted is not sorted before insertion, however data can be inserted beginning with the median of the supplied data.

Author:

Middleware Services

Field Summary

Fields

Modifier and Type	Field and Description
protected static Comparator<Character>	CASE_INSENSITIVE_COMPARATOR Case insensitive comparator.
protected static Comparator<Character>	CASE_SENSITIVE_COMPARATOR Case sensitive comparator.
protected Comparator<Character>	comparator Character comparator.

Constructor Summary

Constructors

Constructor and Description
TernaryTree() Creates an empty case sensitive ternary tree.
TernaryTree(boolean caseSensitive) Creates an empty ternary tree with the given case sensitivity.

Method Summary

Modifier and Type	Method and Description
protected Map<Integer,Integer>	getNodeStats() Returns a histogram of how many words end at each depth.
List<String>	getWords() Returns a list of all the words in this ternary tree.
void	insert(String word) Inserts the supplied word into this tree.
void	insert(String[] words) Inserts the supplied array of words into this tree.
String[]	nearSearch(String word, int distance) Return an array of strings which are near to the supplied word by the supplied distance.
String[]	partialSearch(String word) Returns an array of strings which partially match the supplied word. word should be of the format '.e.e.e' Where the '.' character represents any valid character.
void	print(Writer out) Prints an ASCII representation of this ternary tree to the supplied writer.
void	print(Writer out, boolean fullPath) Prints an ASCII representation of this ternary tree to the supplied writer.
boolean	search(String word) Returns whether the supplied word has been inserted into this ternary tree.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

CASE_SENSITIVE_COMPARATOR

protected static final Comparator<Character> CASE_SENSITIVE_COMPARATOR

Case sensitive comparator.

CASE_INSENSITIVE_COMPARATOR

protected static final Comparator<Character> CASE_INSENSITIVE_COMPARATOR

Case insensitive comparator.

comparator

protected final Comparator<Character> comparator

Character comparator.

Constructor Detail

TernaryTree

public TernaryTree()

Creates an empty case sensitive ternary tree.

TernaryTree

public TernaryTree(boolean caseSensitive)

Creates an empty ternary tree with the given case sensitivity.

Parameters:

caseSensitive - whether this ternary tree should be case sensitive.

Method Detail

insert

public void insert(String word)

Inserts the supplied word into this tree.

Parameters:

word - to insert

insert

public void insert(String[] words)

Inserts the supplied array of words into this tree.

Parameters:

words - to insert

search

public boolean search(String word)

Returns whether the supplied word has been inserted into this ternary tree.

Parameters:

word - to search for

Returns:

whether the word was found

partialSearch

public String[] partialSearch(String word)

Returns an array of strings which partially match the supplied word. word should be of the format '.e.e.e' Where the '.' character represents any valid character. Possible results from this query include: Helene, delete, or severe Note that no substring matching occurs, results only include strings of the same length. If the supplied word does not contain the '.' character, then a regular search is performed.

NOTE This method is not supported for case insensitive ternary trees. Since the tree is built without regard to case any words returned from the tree may or may not match the case of the supplied word.

Parameters:

word - to search for

Returns:

array of matching words

Throws:

UnsupportedOperationException - if this is a case insensitive ternary tree

nearSearch

public String[] nearSearch(String word,
                           int distance)

Return an array of strings which are near to the supplied word by the supplied distance. For the query nearSearch("fisher", 2): Possible results include: cipher, either, fishery, kosher, sister. If the supplied distance is not > 0, then a regular search is performed.

NOTE This method is not supported for case insensitive ternary trees. Since the tree is built without regard to case any words returned from the tree may or may not match the case of the supplied word.

Parameters:

word - to search for

distance - for valid match

Returns:

array of matching words

Throws:

UnsupportedOperationException - if this is a case insensitive ternary tree

getWords

public List<String> getWords()

Returns a list of all the words in this ternary tree. This is a very expensive operation, every node in the tree is traversed. The returned list cannot be modified.

Returns:

unmodifiable list of words

print

public void print(Writer out,
                  boolean fullPath)
           throws IOException

Prints an ASCII representation of this ternary tree to the supplied writer. This is a very expensive operation, every node in the tree is traversed. The output produced is hard to read, but it should give an indication of whether or not your tree is balanced.

Parameters:

out - to print to

fullPath - specifies whether each line should show the full path from root or only the suffix

Throws:

IOException - if an error occurs

print

public void print(Writer out)
           throws IOException

Prints an ASCII representation of this ternary tree to the supplied writer. This is a very expensive operation, every node in the tree is traversed. The output produced is hard to read, but it should give an indication of whether or not your tree is balanced.

Parameters:

out - to print to

Throws:

IOException - if an error occurs

getNodeStats

protected Map<Integer,Integer> getNodeStats()

Returns a histogram of how many words end at each depth.

Returns:

a histogram of how many words end at each depth