Class Trie<V>

  • Type Parameters:
    V - the value type of the trie.
    All Implemented Interfaces:
    Serializable, Map<String,​V>

    public class Trie<V>
    extends Object
    implements Serializable, Map<String,​V>

    A basic Trie implementation that uses hashmaps to store its child nodes. The find(String, CharMatcher) method provides functionality to find all elements of the trie in the specified string in longest-first style using the specified CharPredicate to accept or reject matches based on the character after the match, e.g. only match if the next character is whitespace.

    Note that views of the trie, i.e. keySet(), values(), entrySet(), and the resulting map from prefix(), are unmodifiable.

    Author:
    David B. Bracewell
    See Also:
    Serialized Form
    • Constructor Detail

      • Trie

        public Trie()
        Instantiates a new Trie.
      • Trie

        public Trie​(Map<String,​V> map)
        Instantiates a new Trie initializing the values to those in the given map.
        Parameters:
        map - A map of string to value used to populate the trie.
    • Method Detail

      • clear

        public void clear()
        Specified by:
        clear in interface Map<String,​V>
      • find

        public List<TrieMatch<V>> find​(String text,
                                       CharMatcher delimiter)
        Matches the strings in the trie against a specified text. Matching is doing using a greedy longest match wins way. The give CharPredicate is used to determine if matches are accepted, e.g. only accept a match followed by a whitespace character.
        Parameters:
        text - the text to find the trie elements in
        delimiter - the predicate that specifies acceptable delimiters
        Returns:
        the list of matched elements
      • isEmpty

        public boolean isEmpty()
        Specified by:
        isEmpty in interface Map<String,​V>
      • prefix

        public Map<String,​V> prefix​(String prefix)

        Returns an unmodifiable map view of this Trie containing only those elements with the given prefix.

        Parameters:
        prefix - the prefix to match
        Returns:
        A unmodifiable map view of the trie whose elements have the given prefix
      • size

        public int size()
        Specified by:
        size in interface Map<String,​V>
      • suggest

        public Map<String,​Integer> suggest​(String string)
        Suggest map.
        Parameters:
        string - the string
        Returns:
        the map
      • suggest

        public Map<String,​Integer> suggest​(String string,
                                                 int maxCost)
        Suggest map.
        Parameters:
        string - the string
        maxCost - the max cost
        Returns:
        the map
      • suggest

        public Map<String,​Integer> suggest​(String string,
                                                 int maxCost,
                                                 int substitutionCost)
        Suggest map.
        Parameters:
        string - the string
        maxCost - the max cost
        substitutionCost - the substitution cost
        Returns:
        the map
      • trimToSize

        public Trie<V> trimToSize()
        Compresses the memory of the individual trie nodes.
        Returns:
        this trie