Package com.vividsolutions.jump.util

Class SuggestTree

  • public class SuggestTree
extends Object
    An autocomplete data structure that enables you to quickly look up the top k terms with a given prefix in a set of weighted terms. The structure is based on a compressed trie of the terms (implemented as a randomized ternary search tree) in which each node holds a weight-ordered list of the k highest-weighted terms in its subtree.

    Note that this implementation is not synchronized. If multiple threads access a Suggest Tree concurrently, and at least one of the threads modifies the tree, it must be synchronized externally.

    • Constructor Detail

      • SuggestTree

        public SuggestTree​(int k)
        Creates a Suggest Tree with the specified k-value.
        Parameters:
        k - the maximum number of autocomplete suggestions to return for a given prefix
        Throws:
        IllegalArgumentException - if the specified k-value is less than 1

    • Method Detail

      • getAutocompleteSuggestions

        public SuggestTree.Node getAutocompleteSuggestions​(String prefix)
        Returns the k highest-weighted terms in the tree that start with the specified prefix, or null if there is no such term.
        Parameters:
        prefix - the prefix for which to return autocomplete suggestions
        Returns:
        the k highest-weighted terms in the tree that start with the specified prefix, or null if there is no such term
        Throws:
        IllegalArgumentException - if the specified prefix is an empty string
        NullPointerException - if the specified prefix is null

      • getEntry

        public SuggestTree.Entry getEntry​(String term)
        Returns the tree entry for the specified term, or null if there is no such entry.
        Parameters:
        term - the term for which to return the corresponding tree entry
        Returns:
        the tree entry for the specified term, or null if there is no such entry
        Throws:
        IllegalArgumentException - if the specified term is an empty string
        NullPointerException - if the specified term is null

      • iterator

        public SuggestTree.Iterator iterator()
        Returns an iterator over the terms in the tree.
        Returns:
        an iterator over the terms in the tree

      • size

        public int size()
        Returns the number of terms in the tree.
        Returns:
        the number of terms in the tree

      • put

        public void put​(String term,
                int weight)
        Inserts the specified term with the specified weight into the tree, or reweights the term if it is already present.
        Parameters:
        term - the term to be inserted or reweighted
        weight - the weight to be assigned to the term
        Throws:
        IllegalArgumentException - if the specified term is an empty string or much too long (longer than 32767 characters)
        NullPointerException - if the specified term is null

      • remove

        public void remove​(String term)
        Removes the specified term from the tree.
        Parameters:
        term - the term to be removed
        Throws:
        IllegalArgumentException - if the specified term is an empty string
        NullPointerException - if the specified term is null