Package com.google.mu.collect

Class PrefixSearchTable<K,V>

java.lang.Object
com.google.mu.collect.PrefixSearchTable<K,V>
public final class PrefixSearchTable<K,V> extends Object
A lookup table that stores prefix (a list of keys of type K) -> value mappings.

For example, if the table maps [a, b] prefix to a value "foo", when you search by [a, b, c], it will find the [a, b] -> foo mapping.

Conceptually it's a "Trie" except it searches by a list of key prefixes instead of string prefixes.

Since:
7.1

  • Method Details

    • get

      public Optional<V> get(List<? extends K> compoundKey)
      Searches the table for the longest prefix match of compoundKey.
      Returns:
      the value mapped to the longest (non-empty) prefix of compoundKey if present
      Throws:
      IllegalArgumentException - if compoundKey is empty
      NullPointerException - if compoundKey is null or any key element is null

    • getAll

      public BiStream<List<K>,V> getAll(List<? extends K> compoundKey)
      Searches the table for prefixes of compoundKey and returns a lazy BiStream of all mappings in ascending order of prefix length.

      If no non-empty prefix exists in the table, an empty BiStream is returned.

      To get the longest matched prefix, use get(java.util.List<? extends K>) instead.

      Returns:
      BiStream of the matched prefixes of compoundKey and the mapped values
      Throws:
      IllegalArgumentException - if compoundKey is empty
      NullPointerException - if compoundKey is null or any key element is null

    • toBuilder

      public PrefixSearchTable.Builder<K,V> toBuilder()
      Returns a new builder initialized with the same prefix mappings in this table.
      Since:
      7.2

    • builder

      public static <K, V> PrefixSearchTable.Builder<K,V> builder()
      Returns a new builder.