Interface InvertedRadixTree<O>

  • Type Parameters:
    O - The type of the values associated with keys in the tree
    All Superinterfaces:
    RadixTree<O>
    All Known Implementing Classes:
    ConcurrentInvertedRadixTree

    public interface InvertedRadixTree<O>
    extends RadixTree<O>
    API of an inverted radix tree, that is a radix tree which is set up to scan external documents for keys previously added to the tree, rather than for data contained in the tree itself.

    This method of scanning external documents for keys (or keywords) can be significantly faster than repeatedly scanning the same document for each and every keyword using String.contains(CharSequence) on the document.

    Time complexity is O(d) rather than O(dn), where d=length of document and n=number of keys/keywords.

    This is an extension of RadixTree which provides additional traversal algorithms to implement this functionality on top of the same tree structure. See documentation on each method for details.

    • Method Summary

      All Methods Instance Methods Abstract Methods 
      Modifier and Type Method Description
      java.lang.Iterable<java.lang.CharSequence> getKeysContainedIn​(java.lang.CharSequence document)
      Returns a lazy iterable which returns the set of keys in the tree which are contained in the given document.
      java.lang.Iterable<java.lang.CharSequence> getKeysPrefixing​(java.lang.CharSequence document)
      Returns a lazy iterable which returns the set of keys in the tree which prefix the given document.
      KeyValuePair<O> getKeyValuePairForLongestKeyPrefixing​(java.lang.CharSequence document)
      Returns the KeyValuePair for the longest key in the tree which is a prefix of the given document.
      java.lang.Iterable<KeyValuePair<O>> getKeyValuePairsForKeysContainedIn​(java.lang.CharSequence document)
      Returns a lazy iterable which returns the set of KeyValuePairs for keys in the tree which are contained in the given document.
      java.lang.Iterable<KeyValuePair<O>> getKeyValuePairsForKeysPrefixing​(java.lang.CharSequence document)
      Returns a lazy iterable which returns the set of KeyValuePairs for keys in the tree which prefix the given document.
      java.lang.CharSequence getLongestKeyPrefixing​(java.lang.CharSequence document)
      Returns the longest key in the tree which is a prefix of the given document.
      O getValueForExactKey​(java.lang.CharSequence key)
      Returns the value associated with the given key (exact match), or returns null if no such value is associated with the key.
      O getValueForLongestKeyPrefixing​(java.lang.CharSequence document)
      Returns the value associated with the longest key in the tree which is a prefix of the given document.
      java.lang.Iterable<O> getValuesForKeysContainedIn​(java.lang.CharSequence document)
      Returns a lazy iterable which returns the set of values associated with keys in the tree which are contained in the given document.
      java.lang.Iterable<O> getValuesForKeysPrefixing​(java.lang.CharSequence document)
      Returns a lazy iterable which returns the set of values associated with keys in the tree which prefix the given document.
      O put​(java.lang.CharSequence key, O value)
      Associates the given value with the given key; replacing any previous value associated with the key.
      O putIfAbsent​(java.lang.CharSequence key, O value)
      If a value is not already associated with the given key in the tree, associates the given value with the key; otherwise if an existing value is already associated, returns the existing value and does not overwrite it.
      boolean remove​(java.lang.CharSequence key)
      Removes the value associated with the given key (exact match).
      int size()
      Counts the number of keys/values stored in the tree.
    • Method Detail

      • put

        O put​(java.lang.CharSequence key,
              O value)
        Associates the given value with the given key; replacing any previous value associated with the key. Returns the previous value associated with the key, if any.

        This operation is performed atomically.

        Specified by:
        put in interface RadixTree<O>
        Parameters:
        key - The key with which the specified value should be associated
        value - The value to associate with the key, which cannot be null
        Returns:
        The previous value associated with the key, if there was one, otherwise null
      • putIfAbsent

        O putIfAbsent​(java.lang.CharSequence key,
                      O value)
        If a value is not already associated with the given key in the tree, associates the given value with the key; otherwise if an existing value is already associated, returns the existing value and does not overwrite it.

        This operation is performed atomically.

        Specified by:
        putIfAbsent in interface RadixTree<O>
        Parameters:
        key - The key with which the specified value should be associated
        value - The value to associate with the key, which cannot be null
        Returns:
        The existing value associated with the key, if there was one; otherwise null in which case the new value was successfully associated
      • remove

        boolean remove​(java.lang.CharSequence key)
        Removes the value associated with the given key (exact match). If no value is associated with the key, does nothing.
        Specified by:
        remove in interface RadixTree<O>
        Parameters:
        key - The key for which an associated value should be removed
        Returns:
        True if a value was removed (and therefore was associated with the key), false if no value was associated/removed
      • getValueForExactKey

        O getValueForExactKey​(java.lang.CharSequence key)
        Returns the value associated with the given key (exact match), or returns null if no such value is associated with the key.
        Specified by:
        getValueForExactKey in interface RadixTree<O>
        Parameters:
        key - The key with which a sought value might be associated
        Returns:
        The value associated with the given key (exact match), or null if no value was associated with the key
      • getKeysPrefixing

        java.lang.Iterable<java.lang.CharSequence> getKeysPrefixing​(java.lang.CharSequence document)
        Returns a lazy iterable which returns the set of keys in the tree which prefix the given document.
        Parameters:
        document - A document to be scanned for keys contained in the tree which prefix the given document
        Returns:
        The set of keys in the tree which prefix the given document
      • getValuesForKeysPrefixing

        java.lang.Iterable<O> getValuesForKeysPrefixing​(java.lang.CharSequence document)
        Returns a lazy iterable which returns the set of values associated with keys in the tree which prefix the given document.
        Parameters:
        document - A document to be scanned for keys contained in the tree which prefix the given document
        Returns:
        The set of values associated with keys in the tree which prefix the given document
      • getKeyValuePairsForKeysPrefixing

        java.lang.Iterable<KeyValuePair<O>> getKeyValuePairsForKeysPrefixing​(java.lang.CharSequence document)
        Returns a lazy iterable which returns the set of KeyValuePairs for keys in the tree which prefix the given document.
        Parameters:
        document - A document to be scanned for keys contained in the tree which prefix the given document
        Returns:
        The set of KeyValuePairs for keys in the tree which prefix the given document
      • getLongestKeyPrefixing

        java.lang.CharSequence getLongestKeyPrefixing​(java.lang.CharSequence document)
        Returns the longest key in the tree which is a prefix of the given document.
        Parameters:
        document - A document to be scanned for a key contained in the tree which prefixes the given document
        Returns:
        The longest key in the tree which is a prefix of the given document, or null if no such key is contained in the tree
      • getValueForLongestKeyPrefixing

        O getValueForLongestKeyPrefixing​(java.lang.CharSequence document)
        Returns the value associated with the longest key in the tree which is a prefix of the given document.
        Parameters:
        document - A document to be scanned for a key contained in the tree which prefixes the given document
        Returns:
        The value associated with longest key in the tree which is a prefix of the given document, or null if no such key is contained in the tree
      • getKeyValuePairForLongestKeyPrefixing

        KeyValuePair<O> getKeyValuePairForLongestKeyPrefixing​(java.lang.CharSequence document)
        Returns the KeyValuePair for the longest key in the tree which is a prefix of the given document.
        Parameters:
        document - A document to be scanned for a key contained in the tree which prefixes the given document
        Returns:
        The KeyValuePair for the longest key in the tree which is a prefix of the given document, or null if no such key is contained in the tree
      • getKeysContainedIn

        java.lang.Iterable<java.lang.CharSequence> getKeysContainedIn​(java.lang.CharSequence document)
        Returns a lazy iterable which returns the set of keys in the tree which are contained in the given document.
        Parameters:
        document - A document to be scanned for keys contained in the tree
        Returns:
        The set of keys in the tree which are contained in the given document
      • getValuesForKeysContainedIn

        java.lang.Iterable<O> getValuesForKeysContainedIn​(java.lang.CharSequence document)
        Returns a lazy iterable which returns the set of values associated with keys in the tree which are contained in the given document.
        Parameters:
        document - A document to be scanned for keys contained in the tree
        Returns:
        The set of values associated with keys in the tree which are contained in the given document
      • getKeyValuePairsForKeysContainedIn

        java.lang.Iterable<KeyValuePair<O>> getKeyValuePairsForKeysContainedIn​(java.lang.CharSequence document)
        Returns a lazy iterable which returns the set of KeyValuePairs for keys in the tree which are contained in the given document.
        Parameters:
        document - A document to be scanned for keys contained in the tree
        Returns:
        The set of KeyValuePairs for keys in the tree which are contained in the given document
      • size

        int size()
        Counts the number of keys/values stored in the tree.

        In the current implementation, this is an expensive operation, having O(n) time complexity.

        Specified by:
        size in interface RadixTree<O>
        Returns:
        The number of keys/values stored in the tree