Class ConcurrentInvertedRadixTree<O>
- java.lang.Object
-
- com.googlecode.concurrenttrees.radixinverted.ConcurrentInvertedRadixTree<O>
-
- All Implemented Interfaces:
PrettyPrintable
,RadixTree<O>
,InvertedRadixTree<O>
,java.io.Serializable
public class ConcurrentInvertedRadixTree<O> extends java.lang.Object implements InvertedRadixTree<O>, PrettyPrintable, java.io.Serializable
An implementation ofInvertedRadixTree
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 based onConcurrentRadixTree
.- See Also:
- Serialized Form
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description (package private) static class
ConcurrentInvertedRadixTree.ConcurrentInvertedRadixTreeImpl<O>
-
Field Summary
Fields Modifier and Type Field Description private ConcurrentInvertedRadixTree.ConcurrentInvertedRadixTreeImpl<O>
radixTree
-
Constructor Summary
Constructors Constructor Description ConcurrentInvertedRadixTree(NodeFactory nodeFactory)
Creates a newConcurrentInvertedRadixTree
which will use the givenNodeFactory
to create nodes.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description 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.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.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.KeyValuePair<O>
getKeyValuePairForLongestKeyPrefixing(java.lang.CharSequence document)
Returns theKeyValuePair
for the longest key in the tree which is a prefix of the given document.java.lang.Iterable<KeyValuePair<O>>
getKeyValuePairsForClosestKeys(java.lang.CharSequence candidate)
Returns a lazy iterable which returns the set ofKeyValuePair
s for keys and their associated values in the tree which are the closest match for the given candidate key.java.lang.Iterable<KeyValuePair<O>>
getKeyValuePairsForKeysContainedIn(java.lang.CharSequence document)
Returns a lazy iterable which returns the set ofKeyValuePair
s 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 ofKeyValuePair
s for keys in the tree which prefix the given document.java.lang.Iterable<KeyValuePair<O>>
getKeyValuePairsForKeysStartingWith(java.lang.CharSequence prefix)
Returns a lazy iterable which returns the set ofKeyValuePair
s for keys and their associated values in the tree, where the keys start with the given prefix.java.lang.CharSequence
getLongestKeyPrefixing(java.lang.CharSequence document)
Returns the longest key in the tree which is a prefix of the given document.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.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>
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>
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.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.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.
-
-
-
Field Detail
-
radixTree
private final ConcurrentInvertedRadixTree.ConcurrentInvertedRadixTreeImpl<O> radixTree
-
-
Constructor Detail
-
ConcurrentInvertedRadixTree
public ConcurrentInvertedRadixTree(NodeFactory nodeFactory)
Creates a newConcurrentInvertedRadixTree
which will use the givenNodeFactory
to create nodes.- Parameters:
nodeFactory
- An object which createsNode
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
-
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 interfaceInvertedRadixTree<O>
- Specified by:
put
in interfaceRadixTree<O>
- Parameters:
key
- The key with which the specified value should be associatedvalue
- 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 interfaceInvertedRadixTree<O>
- Specified by:
putIfAbsent
in interfaceRadixTree<O>
- Parameters:
key
- The key with which the specified value should be associatedvalue
- 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
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.
-
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 interfaceInvertedRadixTree<O>
- Specified by:
getValueForExactKey
in interfaceRadixTree<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 interfaceRadixTree<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 ofObject.equals(Object)
).- Specified by:
getValuesForKeysStartingWith
in interfaceRadixTree<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 ofKeyValuePair
s 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, theKeyValuePair
for that key is also returned.- Specified by:
getKeyValuePairsForKeysStartingWith
in interfaceRadixTree<O>
- Parameters:
prefix
- A prefix of keys in the tree for which associatedKeyValuePair
s are sought- Returns:
- The set of
KeyValuePair
s for keys in the tree which start with the given prefix, inclusive
-
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")
-> returnsFord 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 interfaceRadixTree<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 interfaceRadixTree<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 ofKeyValuePair
s 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 interfaceRadixTree<O>
- Parameters:
candidate
- A candidate key- Returns:
- The set of
KeyValuePair
s for keys and their associated values in the tree which most closely match the candidate key, inclusive
-
getKeysPrefixing
public 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.- Specified by:
getKeysPrefixing
in interfaceInvertedRadixTree<O>
- 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
public 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.- Specified by:
getValuesForKeysPrefixing
in interfaceInvertedRadixTree<O>
- 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
public java.lang.Iterable<KeyValuePair<O>> getKeyValuePairsForKeysPrefixing(java.lang.CharSequence document)
Returns a lazy iterable which returns the set ofKeyValuePair
s for keys in the tree which prefix the given document.- Specified by:
getKeyValuePairsForKeysPrefixing
in interfaceInvertedRadixTree<O>
- Parameters:
document
- A document to be scanned for keys contained in the tree which prefix the given document- Returns:
- The set of
KeyValuePair
s for keys in the tree which prefix the given document
-
getLongestKeyPrefixing
public java.lang.CharSequence getLongestKeyPrefixing(java.lang.CharSequence document)
Returns the longest key in the tree which is a prefix of the given document.- Specified by:
getLongestKeyPrefixing
in interfaceInvertedRadixTree<O>
- 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
public 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.- Specified by:
getValueForLongestKeyPrefixing
in interfaceInvertedRadixTree<O>
- 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
public KeyValuePair<O> getKeyValuePairForLongestKeyPrefixing(java.lang.CharSequence document)
Returns theKeyValuePair
for the longest key in the tree which is a prefix of the given document.- Specified by:
getKeyValuePairForLongestKeyPrefixing
in interfaceInvertedRadixTree<O>
- 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
public 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.- Specified by:
getKeysContainedIn
in interfaceInvertedRadixTree<O>
- 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
public 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.- Specified by:
getValuesForKeysContainedIn
in interfaceInvertedRadixTree<O>
- 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
public java.lang.Iterable<KeyValuePair<O>> getKeyValuePairsForKeysContainedIn(java.lang.CharSequence document)
Returns a lazy iterable which returns the set ofKeyValuePair
s for keys in the tree which are contained in the given document.- Specified by:
getKeyValuePairsForKeysContainedIn
in interfaceInvertedRadixTree<O>
- Parameters:
document
- A document to be scanned for keys contained in the tree- Returns:
- The set of
KeyValuePair
s for keys in the tree which are contained in the given document
-
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.
-
getNode
public Node getNode()
- Specified by:
getNode
in interfacePrettyPrintable
-
-