Interface ReversedRadixTree<O>

  • Type Parameters:
    O - The type of the values associated with keys in the tree
    All Known Implementing Classes:
    ConcurrentReversedRadixTree

    public interface ReversedRadixTree<O>
    API of a reversed radix tree, that is a tree which allows values to be looked up based on suffixes of the keys with which they were associated, as well as based on exact matches for keys. A reverse radix tree essentially allows "equals" and "ends with" lookup.

    This has the same structure as a radix tree, but this tree transparently reverses characters in the keys added to the tree, and reverses characters supplied for queries. This is not the same as a suffix tree - a suffix tree stores all possible suffix substrings of keys (supporting "contains" lookup); this tree only stores the original key in reverse character order.

    See documentation on each method for details.

    See Also:
    RadixTree
    • Method Summary

      All Methods Instance Methods Abstract Methods 
      Modifier and Type Method Description
      java.lang.Iterable<java.lang.CharSequence> getKeysEndingWith​(java.lang.CharSequence suffix)
      Returns a lazy iterable which returns the set of keys in the tree which end with the given suffix.
      java.lang.Iterable<KeyValuePair<O>> getKeyValuePairsForKeysEndingWith​(java.lang.CharSequence suffix)
      Returns a lazy iterable which returns the set of KeyValuePairs for keys and their associated values in the tree, where the keys end with the given suffix.
      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.
      java.lang.Iterable<O> getValuesForKeysEndingWith​(java.lang.CharSequence suffix)
      Returns a lazy iterable which returns the set of values associated with keys in the tree which end with the given suffix.
      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.

        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.

        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.
        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.
        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
      • getKeysEndingWith

        java.lang.Iterable<java.lang.CharSequence> getKeysEndingWith​(java.lang.CharSequence suffix)
        Returns a lazy iterable which returns the set of keys in the tree which end with the given suffix.

        This is inclusive - if the given suffix is an exact match for a key in the tree, that key is also returned.

        Parameters:
        suffix - A suffix of sought keys in the tree
        Returns:
        The set of keys in the tree which end with the given suffix, inclusive
      • getValuesForKeysEndingWith

        java.lang.Iterable<O> getValuesForKeysEndingWith​(java.lang.CharSequence suffix)
        Returns a lazy iterable which returns the set of values associated with keys in the tree which end with the given suffix.

        This is inclusive - if the given suffix is an exact match for a key in the tree, the value associated with that key is also returned.

        Note that although the same value might originally have been associated with multiple keys, the set returned does not contain duplicates (as determined by the value objects' implementation of Object.equals(Object)).

        Parameters:
        suffix - A suffix of keys in the tree for which associated values are sought
        Returns:
        The set of values associated with keys in the tree which end with the given suffix, inclusive
      • getKeyValuePairsForKeysEndingWith

        java.lang.Iterable<KeyValuePair<O>> getKeyValuePairsForKeysEndingWith​(java.lang.CharSequence suffix)
        Returns a lazy iterable which returns the set of KeyValuePairs for keys and their associated values in the tree, where the keys end with the given suffix.

        This is inclusive - if the given suffix is an exact match for a key in the tree, the KeyValuePair for that key is also returned.

        Parameters:
        suffix - A suffix of keys in the tree for which associated KeyValuePairs are sought
        Returns:
        The set of KeyValuePairs for keys in the tree which end with the given suffix, inclusive
      • 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.

        Returns:
        The number of keys/values stored in the tree