Class 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 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.
    • 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