org.apache.lucene.search.suggest.tst

## Class TSTAutocomplete

- java.lang.Object
- - org.apache.lucene.search.suggest.tst.TSTAutocomplete

-     public class TSTAutocomplete
      extends Object

  Ternary Search Trie implementation.
  See Also:
    `TernaryTreeNode`

- - ### Method Summary

    Methods
    Modifier and Type | Method and Description
    --- | ---
    `void` | `balancedTree(Object[] tokens, Object[] vals, int lo, int hi, TernaryTreeNode root)` Inserting keys in TST in the order middle,small,big (lexicographic measure) recursively creates a balanced tree which reduces insertion and search times significantly.
    `TernaryTreeNode` | `insert(TernaryTreeNode currentNode, CharSequence s, Object val, int x)` Inserts a key in TST creating a series of Binary Search Trees at each node.
    `ArrayList<TernaryTreeNode>` | `prefixCompletion(TernaryTreeNode root, CharSequence s, int x)` Auto-completes a given prefix query using Depth-First Search with the end of prefix as source node each time finding a new leaf to get a complete key to be added in the suggest list.

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

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

- - ### Method Detail

    - #### balancedTree

          public void balancedTree(Object[] tokens,
                          Object[] vals,
                          int lo,
                          int hi,
                          TernaryTreeNode root)

      Inserting keys in TST in the order middle,small,big (lexicographic measure) recursively creates a balanced tree which reduces insertion and search times significantly.
      Parameters:
        `tokens` - Sorted list of keys to be inserted in TST.
        `lo` - stores the lower index of current list.
        `hi` - stores the higher index of current list.
        `root` - a reference object to root of TST.

    - #### insert

          public TernaryTreeNode insert(TernaryTreeNode currentNode,
                               CharSequence s,
                               Object val,
                               int x)

      Inserts a key in TST creating a series of Binary Search Trees at each node. The key is actually stored across the eqKid of each node in a successive manner.
      Parameters:
        `currentNode` - a reference node where the insertion will take currently.
        `s` - key to be inserted in TST.
        `x` - index of character in key to be inserted currently.
      Returns:
        currentNode The new reference to root node of TST

    - #### prefixCompletion

          public ArrayList<TernaryTreeNode> prefixCompletion(TernaryTreeNode root,
                                                    CharSequence s,
                                                    int x)

      Auto-completes a given prefix query using Depth-First Search with the end of prefix as source node each time finding a new leaf to get a complete key to be added in the suggest list.
      Parameters:
        `root` - a reference to root node of TST.
        `s` - prefix query to be auto-completed.
        `x` - index of current character to be searched while traversing through the prefix in TST.
      Returns:
        suggest list of auto-completed keys for the given prefix query.

Copyright © 2000-2013 Apache Software Foundation. All Rights Reserved.