Class ConcurrentReversedRadixTree<O>

java.lang.Object
com.googlecode.concurrenttrees.radixreversed.ConcurrentReversedRadixTree<O>
All Implemented Interfaces:
PrettyPrintable, ReversedRadixTree<O>, Serializable

public class ConcurrentReversedRadixTree<O> extends Object implements ReversedRadixTree<O>, PrettyPrintable, Serializable
An implementation of ReversedRadixTree which supports lock-free concurrent reads, and allows items to be added to and to be removed from the tree atomically by background thread(s), without blocking reads.

This implementation is a lightweight wrapper around ConcurrentRadixTree, see that class for implementation details.

See Also:
  • Field Details

  • Constructor Details

    • ConcurrentReversedRadixTree

      public ConcurrentReversedRadixTree(NodeFactory nodeFactory)
      Creates a new ConcurrentReversedRadixTree which will use the given NodeFactory to create nodes.
      Parameters:
      nodeFactory - An object which creates Node objects on-demand, and which might return node implementations optimized for storing the values supplied to it for the creation of each node
  • Method Details

    • getValueForExactKey

      public O getValueForExactKey(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 ReversedRadixTree<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
    • put

      public O put(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 ReversedRadixTree<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

      public O putIfAbsent(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 ReversedRadixTree<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
    • getKeysEndingWith

      public Iterable<CharSequence> getKeysEndingWith(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.

      Specified by:
      getKeysEndingWith in interface ReversedRadixTree<O>
      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

      public Iterable<O> getValuesForKeysEndingWith(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)).

      Specified by:
      getValuesForKeysEndingWith in interface ReversedRadixTree<O>
      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

      public Iterable<KeyValuePair<O>> getKeyValuePairsForKeysEndingWith(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.

      Specified by:
      getKeyValuePairsForKeysEndingWith in interface ReversedRadixTree<O>
      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
    • remove

      public boolean remove(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 ReversedRadixTree<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
    • size

      public 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 ReversedRadixTree<O>
      Returns:
      The number of keys/values stored in the tree
    • getNode

      public Node getNode()
      Specified by:
      getNode in interface PrettyPrintable