Class ConcurrentRadixTree<O>

    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      protected void acquireWriteLock()  
      java.lang.Iterable<java.lang.CharSequence> getClosestKeys​(java.lang.CharSequence candidate)
      Returns a lazy iterable which returns the set of keys in the tree which are the closest match for the given candidate key.
      (package private) java.lang.Iterable<java.lang.CharSequence> getDescendantKeys​(java.lang.CharSequence startKey, Node startNode)
      Returns a lazy iterable which will return CharSequence keys for which the given key is a prefix.
      (package private) <O> java.lang.Iterable<KeyValuePair<O>> getDescendantKeyValuePairs​(java.lang.CharSequence startKey, Node startNode)
      Returns a lazy iterable which will return KeyValuePair objects each containing a key and a value, for which the given key is a prefix of the key in the KeyValuePair.
      (package private) <O> java.lang.Iterable<O> getDescendantValues​(java.lang.CharSequence startKey, Node startNode)
      Returns a lazy iterable which will return values which are associated with keys in the tree for which the given key is a prefix.
      java.lang.Iterable<java.lang.CharSequence> getKeysStartingWith​(java.lang.CharSequence prefix)
      Returns a lazy iterable which returns the set of keys in the tree which start with the given prefix.
      java.lang.Iterable<KeyValuePair<O>> getKeyValuePairsForClosestKeys​(java.lang.CharSequence candidate)
      Returns a lazy iterable which returns the set of KeyValuePairs for keys and their associated values in the tree which are the closest match for the given candidate key.
      java.lang.Iterable<KeyValuePair<O>> getKeyValuePairsForKeysStartingWith​(java.lang.CharSequence prefix)
      Returns a lazy iterable which returns the set of KeyValuePairs for keys and their associated values in the tree, where the keys start with the given prefix.
      Node getNode()  
      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> getValuesForClosestKeys​(java.lang.CharSequence candidate)
      Returns a lazy iterable which returns the set of values associated with keys in the tree which are the closest match for the given candidate key.
      java.lang.Iterable<O> getValuesForKeysStartingWith​(java.lang.CharSequence prefix)
      Returns a lazy iterable which returns the set of values associated with keys in the tree which start with the given prefix.
      protected java.lang.Iterable<ConcurrentRadixTree.NodeKeyPair> lazyTraverseDescendants​(java.lang.CharSequence startKey, Node startNode)
      Traverses the tree using depth-first, preordered traversal, starting at the given node, using lazy evaluation such that the next node is only determined when next() is called on the iterator returned.
      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.
      (package private) java.lang.Object putInternal​(java.lang.CharSequence key, java.lang.Object value, boolean overwrite)
      Atomically adds the given value to the tree, creating a node for the value as necessary.
      protected void releaseWriteLock()  
      boolean remove​(java.lang.CharSequence key)
      Removes the value associated with the given key (exact match).
      (package private) ConcurrentRadixTree.SearchResult searchTree​(java.lang.CharSequence key)
      Traverses the tree and finds the node which matches the longest prefix of the given key.
      int size()
      Counts the number of keys/values stored in the tree.
      protected java.lang.CharSequence transformKeyForResult​(java.lang.CharSequence rawKey)
      A hook method which may be overridden by subclasses, to transform a key just before it is returned to the application, for example by the getKeysStartingWith(CharSequence) or the getKeyValuePairsForKeysStartingWith(CharSequence) methods.
      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
    • Field Detail

      • root

        protected volatile Node root
      • writeLock

        private final java.util.concurrent.locks.Lock writeLock
    • Constructor Detail

      • ConcurrentRadixTree

        public ConcurrentRadixTree​(NodeFactory nodeFactory)
        Creates a new ConcurrentRadixTree 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 Detail

      • acquireWriteLock

        protected void acquireWriteLock()
      • releaseWriteLock

        protected void releaseWriteLock()
      • put

        public 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

        public 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
      • getValueForExactKey

        public 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
      • getKeysStartingWith

        public java.lang.Iterable<java.lang.CharSequence> getKeysStartingWith​(java.lang.CharSequence prefix)
        Returns a lazy iterable which returns the set of keys in the tree which start with the given prefix.

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

        Specified by:
        getKeysStartingWith in interface RadixTree<O>
        Parameters:
        prefix - A prefix of sought keys in the tree
        Returns:
        The set of keys in the tree which start with the given prefix, inclusive
      • getValuesForKeysStartingWith

        public java.lang.Iterable<O> getValuesForKeysStartingWith​(java.lang.CharSequence prefix)
        Returns a lazy iterable which returns the set of values associated with keys in the tree which start with the given prefix.

        This is inclusive - if the given prefix 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:
        getValuesForKeysStartingWith in interface RadixTree<O>
        Parameters:
        prefix - A prefix of keys in the tree for which associated values are sought
        Returns:
        The set of values associated with keys in the tree which start with the given prefix, inclusive
      • getKeyValuePairsForKeysStartingWith

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

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

        Specified by:
        getKeyValuePairsForKeysStartingWith in interface RadixTree<O>
        Parameters:
        prefix - A prefix of keys in the tree for which associated KeyValuePairs are sought
        Returns:
        The set of KeyValuePairs for keys in the tree which start with the given prefix, inclusive
      • remove

        public 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
      • getClosestKeys

        public java.lang.Iterable<java.lang.CharSequence> getClosestKeys​(java.lang.CharSequence candidate)
        Returns a lazy iterable which returns the set of keys in the tree which are the closest match for the given candidate key.

        Example:
        Tree contains: Ford Focus, Ford Mondeo, BMW M3
        getClosestKeys("Ford F150") -> returns Ford Focus, Ford Mondeo

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

        Specified by:
        getClosestKeys in interface RadixTree<O>
        Parameters:
        candidate - A candidate key
        Returns:
        The set of keys in the tree which most closely match the candidate key, inclusive
      • getValuesForClosestKeys

        public java.lang.Iterable<O> getValuesForClosestKeys​(java.lang.CharSequence candidate)
        Returns a lazy iterable which returns the set of values associated with keys in the tree which are the closest match for the given candidate key.

        See {#getClosestKeys} for more details.

        Specified by:
        getValuesForClosestKeys in interface RadixTree<O>
        Parameters:
        candidate - A candidate key
        Returns:
        The set of values associated with keys in the tree which most closely match the candidate key, inclusive
      • getKeyValuePairsForClosestKeys

        public java.lang.Iterable<KeyValuePair<O>> getKeyValuePairsForClosestKeys​(java.lang.CharSequence candidate)
        Returns a lazy iterable which returns the set of KeyValuePairs for keys and their associated values in the tree which are the closest match for the given candidate key.

        See {#getClosestKeys} for more details.

        Specified by:
        getKeyValuePairsForClosestKeys in interface RadixTree<O>
        Parameters:
        candidate - A candidate key
        Returns:
        The set of KeyValuePairs for keys and their associated values in the tree which most closely match the candidate key, inclusive
      • 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 RadixTree<O>
        Returns:
        The number of keys/values stored in the tree
      • putInternal

        java.lang.Object putInternal​(java.lang.CharSequence key,
                                     java.lang.Object value,
                                     boolean overwrite)
        Atomically adds the given value to the tree, creating a node for the value as necessary. If the value is already stored for the same key, either overwrites the existing value, or simply returns the existing value, depending on the given value of the overwrite flag.
        Parameters:
        key - The key against which the value should be stored
        value - The value to store against the key
        overwrite - If true, should replace any existing value, if false should not replace any existing value
        Returns:
        The existing value for this key, if there was one, otherwise null
      • getDescendantKeys

        java.lang.Iterable<java.lang.CharSequence> getDescendantKeys​(java.lang.CharSequence startKey,
                                                                     Node startNode)
        Returns a lazy iterable which will return CharSequence keys for which the given key is a prefix. The results inherently will not contain duplicates (duplicate keys cannot exist in the tree).

        Note that this method internally converts CharSequences to Strings, to avoid set equality issues, because equals() and hashCode() are not specified by the CharSequence API contract.

      • getDescendantValues

        <O> java.lang.Iterable<O> getDescendantValues​(java.lang.CharSequence startKey,
                                                      Node startNode)
        Returns a lazy iterable which will return values which are associated with keys in the tree for which the given key is a prefix.
      • getDescendantKeyValuePairs

        <O> java.lang.Iterable<KeyValuePair<O>> getDescendantKeyValuePairs​(java.lang.CharSequence startKey,
                                                                           Node startNode)
        Returns a lazy iterable which will return KeyValuePair objects each containing a key and a value, for which the given key is a prefix of the key in the KeyValuePair. These results inherently will not contain duplicates (duplicate keys cannot exist in the tree).

        Note that this method internally converts CharSequences to Strings, to avoid set equality issues, because equals() and hashCode() are not specified by the CharSequence API contract.

      • lazyTraverseDescendants

        protected java.lang.Iterable<ConcurrentRadixTree.NodeKeyPair> lazyTraverseDescendants​(java.lang.CharSequence startKey,
                                                                                              Node startNode)
        Traverses the tree using depth-first, preordered traversal, starting at the given node, using lazy evaluation such that the next node is only determined when next() is called on the iterator returned. The traversal algorithm uses iteration instead of recursion to allow deep trees to be traversed without requiring large JVM stack sizes.

        Each node that is encountered is returned from the iterator along with a key associated with that node, in a NodeKeyPair object. The key will be prefixed by the given start key, and will be generated by appending to the start key the edges traversed along the path to that node from the start node.

        Parameters:
        startKey - The key which matches the given start node
        startNode - The start node
        Returns:
        An iterator which when iterated traverses the tree using depth-first, preordered traversal, starting at the given start node
      • transformKeyForResult

        protected java.lang.CharSequence transformKeyForResult​(java.lang.CharSequence rawKey)
        A hook method which may be overridden by subclasses, to transform a key just before it is returned to the application, for example by the getKeysStartingWith(CharSequence) or the getKeyValuePairsForKeysStartingWith(CharSequence) methods.

        This hook is expected to be used by ReversedRadixTree implementations, where keys are stored in the tree in reverse order but results should be returned in normal order.

        This default implementation simply returns the given key unmodified.

        Parameters:
        rawKey - The raw key as stored in the tree
        Returns:
        A transformed version of the key
      • searchTree

        ConcurrentRadixTree.SearchResult searchTree​(java.lang.CharSequence key)
        Traverses the tree and finds the node which matches the longest prefix of the given key.

        The node returned might be an exact match for the key, in which case ConcurrentRadixTree.SearchResult.charsMatched will equal the length of the key.

        The node returned might be an inexact match for the key, in which case ConcurrentRadixTree.SearchResult.charsMatched will be less than the length of the key.

        There are two types of inexact match:

        • An inexact match which ends evenly at the boundary between a node and its children (the rest of the key not matching any children at all). In this case if we we wanted to add nodes to the tree to represent the rest of the key, we could simply add child nodes to the node found.
        • An inexact match which ends in the middle of a the characters for an edge stored in a node (the key matching only the first few characters of the edge). In this case if we we wanted to add nodes to the tree to represent the rest of the key, we would have to split the node (let's call this node found: NF):
          1. Create a new node (N1) which will be the split node, containing the matched characters from the start of the edge in NF
          2. Create a new node (N2) which will contain the unmatched characters from the rest of the edge in NF, and copy the original edges from NF unmodified into N2
          3. Create a new node (N3) which will be the new branch, containing the unmatched characters from the rest of the key
          4. Add N2 as a child of N1
          5. Add N3 as a child of N1
          6. In the parent node of NF, replace the edge pointing to NF with an edge pointing instead to N1. If we do this step atomically, reading threads are guaranteed to never see "invalid" data, only either the old data or the new data
        The ConcurrentRadixTree.SearchResult.classification is an enum value based on its classification of the match according to the descriptions above.
        Parameters:
        key - a key for which the node matching the longest prefix of the key is required
        Returns:
        A ConcurrentRadixTree.SearchResult object which contains the node matching the longest prefix of the key, its parent node, the number of characters of the key which were matched in total and within the edge of the matched node, and a ConcurrentRadixTree.SearchResult.classification of the match as described above