Package org.apache.jena.atlas.lib

Class Trie<T>

  • Type Parameters:
    T - Type of the value stored.
    public final class Trie<T>
extends java.lang.Object
    An implementation of a classic Trie, this is a mapping from strings to some value type optimized for fast prefix search and match. If you do not need prefix search then you should typically use a standard Map instead.

    The empty or null string may be used as a special key to refer to the root node of the trie.

    A Trie cannot store null values since null is used as an internal marker to indicate that there is no value associated with a key. This is necessary because the nature of the data structure means that adding a key potentially adds multiple keys many of which will not be associated with a value.

    • Constructor Summary

      Constructors 
      Constructor Description
      Trie()  

    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      void add​(java.lang.String key, T value)
      Adds a value to the trie overwriting any existing value
      void clear()
      Clear the Trie completely.
      boolean contains​(java.lang.String key)
      Gets whether a key exists in the trie and has a non-null value mapped to it
      boolean contains​(java.lang.String key, boolean requireValue)
      Gets whether a key exists in the trie and meets the given value criteria
      boolean contains​(java.lang.String key, T value)
      Gets whether a key value pair are present in the trie
      T get​(java.lang.String key)
      Gets the value associated with a key
      boolean isEmpty()
      Test whether the Trie is empty.
      T longestMatch​(java.lang.String key)
      Finds the longest match for a given key i.e.
      java.util.List<T> partialSearch​(java.lang.String key)
      Performs a search and returns any value associated with any partial or whole prefix of the key
      java.util.List<T> prefixSearch​(java.lang.String prefix)
      Performs a prefix search and returns all values mapped under the given prefix.
      void remove​(java.lang.String key)
      Removes a value from the trie
      T shortestMatch​(java.lang.String key)
      Finds the shortest match for a given key i.e.

      • Methods inherited from class java.lang.Object

        equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

    • Constructor Detail

      • Trie

        public Trie()

    • Method Detail

      • add

        public void add​(java.lang.String key,
                T value)
        Adds a value to the trie overwriting any existing value

        Note that a null value is treated as if the key does not actually exist in the tree so trying to add a null is a no-op. If you want to remove a key use the remove(String) method instead.

        Parameters:
        key - Key
        value - Value

      • remove

        public void remove​(java.lang.String key)
        Removes a value from the trie

        This doesn't actually remove the key per-se rather sets the value associated with the key to null.

        Parameters:
        key - Key

      • clear

        public void clear()
        Clear the Trie completely.

      • isEmpty

        public boolean isEmpty()
        Test whether the Trie is empty.

      • contains

        public boolean contains​(java.lang.String key)
        Gets whether a key exists in the trie and has a non-null value mapped to it
        Parameters:
        key - Key
        Returns:
        True if the key exists and has a non-null value mapped to it

      • contains

        public boolean contains​(java.lang.String key,
                        boolean requireValue)
        Gets whether a key exists in the trie and meets the given value criteria
        Parameters:
        key - Key
        requireValue - If true a key must have a non-null value associated with it to be considered to be contained in the tree, if false then the key must merely map to a node in the trie
        Returns:
        True if the key exists and the value criteria is met, false otherwise

      • contains

        public boolean contains​(java.lang.String key,
                        T value)
        Gets whether a key value pair are present in the trie
        Parameters:
        key - Key
        value - Value
        Returns:
        True if the key value pair exists in the trie, false otherwise

      • get

        public T get​(java.lang.String key)
        Gets the value associated with a key
        Parameters:
        key - Key
        Returns:
        Value

      • prefixSearch

        public java.util.List<T> prefixSearch​(java.lang.String prefix)
        Performs a prefix search and returns all values mapped under the given prefix. The entirety of the prefix must be matched, if you only want part of the prefix to be matched use the partialSearch(String) method instead.
        Parameters:
        prefix - Prefix
        Returns:
        List of values associated with the given key

      • partialSearch

        public java.util.List<T> partialSearch​(java.lang.String key)
        Performs a search and returns any value associated with any partial or whole prefix of the key
        Parameters:
        key - Key
        Returns:
        List of values associated with any partial prefix of the key

      • shortestMatch

        public T shortestMatch​(java.lang.String key)
        Finds the shortest match for a given key i.e. returns the value associated with the shortest prefix of the key that has a value
        Parameters:
        key - Key
        Returns:
        Shortest Match or null if no possible matches

      • longestMatch

        public T longestMatch​(java.lang.String key)
        Finds the longest match for a given key i.e. returns the value associated with the longest prefix of the key that has a value
        Parameters:
        key - Key
        Returns:
        Longest Match or null if no possible matches