edu.northwestern.at.utils

## Class TernaryTrie

- java.lang.Object
- - edu.northwestern.at.utils.TernaryTrie

- All Implemented Interfaces:
    TaggedStrings

      public class TernaryTrie
      extends java.lang.Object
      implements TaggedStrings

  `TernaryTrie` is an 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.

  Version:
    $Revision: 2134 $ $Date: 2005-03-28 14:48:04 -0500 (Mon, 28 Mar 2005) $
  Author:
    Daniel Fisher

- - ### Field Summary

    Fields
    Modifier and Type | Field and Description
    --- | ---
    `protected int` | `maxKeyLength` Maximum key length.
    `protected int` | `nodeCount` Count of nodes in tree.
    `protected TernaryTrieNode` | `root` root node of the ternary tree

  - ### Constructor Summary

    Constructors
    Constructor and Description
    `TernaryTrie()` Construct empty ternary trie.
    `TernaryTrie(java.util.List<java.lang.String> stringsList)` Construct a ternary trie from values in a list.
    `TernaryTrie(java.util.Map<java.lang.String,java.lang.String> stringsMap, boolean addValuesAsKeys)` Construct a ternary trie from keys and values in a map.
    `TernaryTrie(java.util.Set<java.lang.String> stringsSet)` Construct a ternary trie from values in a set.
    `TernaryTrie(TaggedStrings stringsList, boolean addValuesAsKeys)` Construct a ternary trie from values in a tagged strings list.

  - ### Method Summary

    Methods
    Modifier and Type | Method and Description
    --- | ---
    `void` | `addCollection(java.util.Collection<java.lang.String> collection)` Add words from a collection.
    `boolean` | `containsKey(java.lang.String word)` Check if trie contains a specified key.
    `boolean` | `containsString(java.lang.String string)` See if specified string exists.
    `protected TernaryTrieNode` | `findNode(TernaryTrieNode node, java.lang.String word, int index)`
    `java.lang.Object` | `get(java.lang.String word)` Get associated value for word.
    `java.util.Set<java.lang.String>` | `getAllStrings()` Get set of all unique string values.
    `java.util.Set<java.lang.String>` | `getAllTags()` Get set of all unique tag values as strings.
    `int` | `getStringCount()` Get number of strings.
    `java.lang.String` | `getTag(java.lang.String string)` Get the tag value associated with a string.
    `java.util.List<java.lang.String>` | `getWords()` This will return an array of all the words in this `TernaryTrie`.
    `protected TernaryTrieNode` | `insertNode(TernaryTrieNode node, java.lang.String word, int index, java.lang.Object value)` This will recursively insert a word into the `TernaryTrie` one node at a time beginning at the supplied node.
    `java.util.List<java.lang.String>` | `nearSearch(java.lang.String word, int distance)` This will return an array of strings which are near to the supplied word by the supplied distance.
    `protected java.util.List<java.lang.String>` | `nearSearchNode(TernaryTrieNode node, int distance, java.util.List<java.lang.String> matches, java.lang.String match, java.lang.String word, int index)` This will recursively search for a near match word in the `TernaryTrie` one node at a time beginning at the supplied node.
    `java.util.List<java.lang.String>` | `partialSearch(java.lang.String word)` This will return an array of strings which partially match the supplied word.
    `protected java.util.List<java.lang.String>` | `partialSearchNode(TernaryTrieNode node, java.util.List<java.lang.String> matches, java.lang.String match, java.lang.String word, int index)` This will recursively search for a partial word in the `TernaryTrie` one node at a time beginning at the supplied node.
    `java.util.List<java.lang.String>` | `prefixSearch(java.lang.String prefix)`
    `protected java.util.List<java.lang.String>` | `prefixSearchNode(TernaryTrieNode node, java.util.List<java.lang.String> matches, java.lang.String match, java.lang.String prefix, java.lang.String prefixPattern, int index)`
    `java.lang.Object` | `put(java.lang.String word, java.lang.Object value)` Add word and associated value to trie.
    `void` | `putTag(java.lang.String string, java.lang.String tag)` Set the tag value associated with a string.
    `protected boolean` | `searchNode(TernaryTrieNode node, java.lang.String word, int index)` This will recursively search for a word in the `TernaryTrie` one node at a time beginning at the supplied node.
    `int` | `size()` Return size of trie (# of terminal nodes)
    `protected java.util.List<java.lang.String>` | `traverseNode(TernaryTrieNode node, java.lang.String s, java.util.List<java.lang.String> words)` This will recursively traverse every node in the `TernaryTrie` one node at a time beginning at the supplied node.

    - ### Methods inherited from class java.lang.Object

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

- - ### Field Detail

    - #### root

          protected TernaryTrieNode root

      root node of the ternary tree

    - #### nodeCount

          protected int nodeCount

      Count of nodes in tree.

    - #### maxKeyLength

          protected int maxKeyLength

      Maximum key length.

  - ### Constructor Detail

    - #### TernaryTrie

          public TernaryTrie()

      Construct empty ternary trie.

    - #### TernaryTrie

          public TernaryTrie(java.util.Map<java.lang.String,java.lang.String> stringsMap,
                     boolean addValuesAsKeys)

      Construct a ternary trie from keys and values in a map.
      Parameters:
        `stringsMap` - The map whose keys and values are to be added to the trie.
        `addValuesAsKeys` - True to add each value as a key as well.

    - #### TernaryTrie

          public TernaryTrie(java.util.Set<java.lang.String> stringsSet)

      Construct a ternary trie from values in a set.
      Parameters:
        `stringsSet` - The set whose values are to be added to the trie.

    - #### TernaryTrie

          public TernaryTrie(java.util.List<java.lang.String> stringsList)

      Construct a ternary trie from values in a list.
      Parameters:
        `stringsList` - The list whose values are to be added to the trie.

    - #### TernaryTrie

          public TernaryTrie(TaggedStrings stringsList,
                     boolean addValuesAsKeys)

      Construct a ternary trie from values in a tagged strings list.
      Parameters:
        `stringsList` - The tagged strings list whose values are to be added to the trie.
        `addValuesAsKeys` - True to add each value as a key as well.

  - ### Method Detail

    - #### addCollection

          public void addCollection(java.util.Collection<java.lang.String> collection)

      Add words from a collection.
      Parameters:
        `collection` - Collection whose values are to be inserted into trie.

    - #### put

          public java.lang.Object put(java.lang.String word,
                             java.lang.Object value)

      Add word and associated value to trie.
      Parameters:
        `word` - String to insert.
        `value` - Object value.
      Returns:
        Previous value, if any, for word.

    - #### get

          public java.lang.Object get(java.lang.String word)

      Get associated value for word.
      Parameters:
        `word` - String whose associated value we want.
      Returns:
        Associated value.

    - #### containsKey

          public boolean containsKey(java.lang.String word)

      Check if trie contains a specified key.
      Parameters:
        `word` - The key to look up.
      Returns:
        true if trie contains specified key.

    - #### partialSearch

          public java.util.List<java.lang.String> partialSearch(java.lang.String word)

      This will return 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 preformed.

      Parameters:
        `word` - `String` to search for
      Returns:
        `String[]` - of matching words

    - #### prefixSearch

          public java.util.List<java.lang.String> prefixSearch(java.lang.String prefix)

    - #### prefixSearchNode

          protected java.util.List<java.lang.String> prefixSearchNode(TernaryTrieNode node,
                                                          java.util.List<java.lang.String> matches,
                                                          java.lang.String match,
                                                          java.lang.String prefix,
                                                          java.lang.String prefixPattern,
                                                          int index)

    - #### nearSearch

          public java.util.List<java.lang.String> nearSearch(java.lang.String word,
                                                    int distance)

      This will 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 preformed.

      Parameters:
        `word` - `String` to search for
        `distance` - `int` for valid match
      Returns:
        `String[]` - of matching words

    - #### getWords

          public java.util.List<java.lang.String> getWords()

      This will return an array of all the words in this `TernaryTrie`. This is a very expensive operation, every node in the tree is traversed.

      Returns:
        `String[]` - of words

    - #### insertNode

          protected TernaryTrieNode insertNode(TernaryTrieNode node,
                                   java.lang.String word,
                                   int index,
                                   java.lang.Object value)

      This will recursively insert a word into the `TernaryTrie` one node at a time beginning at the supplied node.

      Parameters:
        `node` - `TernaryTrieNode` to put character in
        `word` - `String` to be inserted
        `index` - `int` of character in word
      Returns:
        `TernaryTrieNode` - to insert

    - #### searchNode

          protected boolean searchNode(TernaryTrieNode node,
                           java.lang.String word,
                           int index)

      This will recursively search for a word in the `TernaryTrie` one node at a time beginning at the supplied node.

      Parameters:
        `node` - `TernaryTrieNode` to search in
        `word` - `String` to search for
        `index` - `int` of character in word
      Returns:
        `boolean` - whether or not word was found

    - #### findNode

          protected TernaryTrieNode findNode(TernaryTrieNode node,
                                 java.lang.String word,
                                 int index)

    - #### partialSearchNode

          protected java.util.List<java.lang.String> partialSearchNode(TernaryTrieNode node,
                                                           java.util.List<java.lang.String> matches,
                                                           java.lang.String match,
                                                           java.lang.String word,
                                                           int index)

      This will recursively search for a partial word in the `TernaryTrie` one node at a time beginning at the supplied node.

      Parameters:
        `node` - `TernaryTrieNode` to search in
        `matches` - `ArrayList` of partial matches
        `match` - `String` the current word being examined
        `word` - `String` to search for
        `index` - `int` of character in word
      Returns:
        `ArrayList` - of matches

    - #### nearSearchNode

          protected java.util.List<java.lang.String> nearSearchNode(TernaryTrieNode node,
                                                        int distance,
                                                        java.util.List<java.lang.String> matches,
                                                        java.lang.String match,
                                                        java.lang.String word,
                                                        int index)

      This will recursively search for a near match word in the `TernaryTrie` one node at a time beginning at the supplied node.

      Parameters:
        `node` - `TernaryTrieNode` to search in
        `distance` - `int` of a valid match, must be > 0
        `matches` - `ArrayList` of near matches
        `match` - `String` the current word being examined
        `word` - `String` to search for
        `index` - `int` of character in word
      Returns:
        `ArrayList` - of matches

    - #### traverseNode

          protected java.util.List<java.lang.String> traverseNode(TernaryTrieNode node,
                                                      java.lang.String s,
                                                      java.util.List<java.lang.String> words)

      This will recursively traverse every node in the `TernaryTrie` one node at a time beginning at the supplied node. The result is a string representing every word, which is delimited by the LINE_SEPARATOR character.

      Parameters:
        `node` - `TernaryTrieNode` to begin traversing
        `s` - `String` of words found at the supplied node
        `words` - `ArrayList` which will be returned (recursive function)
      Returns:
        `String` - containing all words from the supplied node

    - #### size

          public int size()

      Return size of trie (# of terminal nodes)
      Returns:
        Number of terminal nodes (nodes with data values).

    - #### containsString

          public boolean containsString(java.lang.String string)

      See if specified string exists.
      Specified by:
        `containsString` in interface `TaggedStrings`
      Parameters:
        `string` - The string.
      Returns:
        True if specified string exists.

    - #### getTag

          public java.lang.String getTag(java.lang.String string)

      Get the tag value associated with a string.
      Specified by:
        `getTag` in interface `TaggedStrings`
      Parameters:
        `string` - The string.
      Returns:
        The tag value associated with the string. May be null.

    - #### putTag

          public void putTag(java.lang.String string,
                    java.lang.String tag)

      Set the tag value associated with a string.
      Specified by:
        `putTag` in interface `TaggedStrings`
      Parameters:
        `string` - The string.
        `tag` - The tag.

    - #### getStringCount

          public int getStringCount()

      Get number of strings.
      Specified by:
        `getStringCount` in interface `TaggedStrings`
      Returns:
        Number of strings.

    - #### getAllStrings

          public java.util.Set<java.lang.String> getAllStrings()

      Get set of all unique string values.
      Specified by:
        `getAllStrings` in interface `TaggedStrings`
      Returns:
        Set of all unique string values.

    - #### getAllTags

          public java.util.Set<java.lang.String> getAllTags()

      Get set of all unique tag values as strings.
      Specified by:
        `getAllTags` in interface `TaggedStrings`
      Returns:
        Set of all unique string tag values.