Class ConcurrentSuffixTree<O>
- java.lang.Object
-
- com.googlecode.concurrenttrees.suffix.ConcurrentSuffixTree<O>
-
- All Implemented Interfaces:
PrettyPrintable
,SuffixTree<O>
,java.io.Serializable
public class ConcurrentSuffixTree<O> extends java.lang.Object implements SuffixTree<O>, PrettyPrintable, java.io.Serializable
An implementation ofSuffixTree
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) class
ConcurrentSuffixTree.ConcurrentSuffixTreeImpl<V>
-
Field Summary
Fields Modifier and Type Field Description private ConcurrentSuffixTree.ConcurrentSuffixTreeImpl<java.util.Set<java.lang.String>>
radixTree
private java.util.concurrent.ConcurrentMap<java.lang.String,O>
valueMap
-
Constructor Summary
Constructors Constructor Description ConcurrentSuffixTree(NodeFactory nodeFactory)
Creates a newConcurrentSuffixTree
which will use the givenNodeFactory
to create nodes.
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description (package private) void
addSuffixesToRadixTree(java.lang.String keyAsString)
protected java.util.Set<java.lang.String>
createSetForOriginalKeys()
Creates a newSet
in which original keys from which a suffix was generated can be stored.java.lang.Iterable<java.lang.CharSequence>
getKeysContaining(java.lang.CharSequence fragment)
Returns a lazy iterable which returns the set of keys in the tree which contain the given fragment.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>>
getKeyValuePairsForKeysContaining(java.lang.CharSequence fragment)
Returns a lazy iterable which returns the set ofKeyValuePair
s for keys and their associated values in the tree, where the keys contain the given fragment.java.lang.Iterable<KeyValuePair<O>>
getKeyValuePairsForKeysEndingWith(java.lang.CharSequence suffix)
Returns a lazy iterable which returns the set ofKeyValuePair
s for keys and their associated values in the tree, where the keys end with the given suffix.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>
getValuesForKeysContaining(java.lang.CharSequence fragment)
Returns a lazy iterable which returns the set of values associated with keys in the tree which contain the given fragment.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.(package private) static <T> java.util.Iterator<T>
nullSafeIterator(java.lang.Iterable<T> iterable)
Utility method to return an iterator for the given iterable, or an empty iterator if the iterable is null.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).(package private) void
removeSuffixesFromRadixTree(java.lang.String keyAsString)
int
size()
Counts the number of keys/values stored in the tree.
-
-
-
Field Detail
-
radixTree
private final ConcurrentSuffixTree.ConcurrentSuffixTreeImpl<java.util.Set<java.lang.String>> radixTree
-
valueMap
private final java.util.concurrent.ConcurrentMap<java.lang.String,O> valueMap
-
-
Constructor Detail
-
ConcurrentSuffixTree
public ConcurrentSuffixTree(NodeFactory nodeFactory)
Creates a newConcurrentSuffixTree
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 interfaceSuffixTree<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 interfaceSuffixTree<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.- Specified by:
remove
in interfaceSuffixTree<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
-
addSuffixesToRadixTree
void addSuffixesToRadixTree(java.lang.String keyAsString)
-
removeSuffixesFromRadixTree
void removeSuffixesFromRadixTree(java.lang.String keyAsString)
-
createSetForOriginalKeys
protected java.util.Set<java.lang.String> createSetForOriginalKeys()
Creates a newSet
in which original keys from which a suffix was generated can be stored. By default this method creates a new concurrent set based onConcurrentHashMap
. Subclasses could override this method to create an alternative set. Specifically it is expected that this would be useful in unit tests, where sets with consistent iteration order would be useful.- Returns:
- A new
Set
in which original keys from which a suffix was generated can be stored
-
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 interfaceSuffixTree<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
-
getKeysEndingWith
public 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.- Specified by:
getKeysEndingWith
in interfaceSuffixTree<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 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, or multiple suffixes of the same key, the set returned does not contain duplicates (as determined by the value objects' implementation ofObject.equals(Object)
).- Specified by:
getValuesForKeysEndingWith
in interfaceSuffixTree<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 java.lang.Iterable<KeyValuePair<O>> getKeyValuePairsForKeysEndingWith(java.lang.CharSequence suffix)
Returns a lazy iterable which returns the set ofKeyValuePair
s 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, theKeyValuePair
for that key is also returned.- Specified by:
getKeyValuePairsForKeysEndingWith
in interfaceSuffixTree<O>
- Parameters:
suffix
- A suffix of keys in the tree for which associatedKeyValuePair
s are sought- Returns:
- The set of
KeyValuePair
s for keys in the tree which end with the given suffix, inclusive
-
getKeysContaining
public java.lang.Iterable<java.lang.CharSequence> getKeysContaining(java.lang.CharSequence fragment)
Returns a lazy iterable which returns the set of keys in the tree which contain the given fragment. This is inclusive - if the given fragment is an exact match for a key in the tree, that key is also returned.- Specified by:
getKeysContaining
in interfaceSuffixTree<O>
- Parameters:
fragment
- A fragment of sought keys in the tree- Returns:
- The set of keys in the tree which contain the given fragment, inclusive
-
getValuesForKeysContaining
public java.lang.Iterable<O> getValuesForKeysContaining(java.lang.CharSequence fragment)
Returns a lazy iterable which returns the set of values associated with keys in the tree which contain the given fragment. This is inclusive - if the given fragment is an exact match for a key in the tree, the value associated with that key is also returned.- Specified by:
getValuesForKeysContaining
in interfaceSuffixTree<O>
- Parameters:
fragment
- A fragment of keys in the tree for which associated values are sought- Returns:
- The set of values associated with keys in the tree which contain the given fragment, inclusive
-
getKeyValuePairsForKeysContaining
public java.lang.Iterable<KeyValuePair<O>> getKeyValuePairsForKeysContaining(java.lang.CharSequence fragment)
Returns a lazy iterable which returns the set ofKeyValuePair
s for keys and their associated values in the tree, where the keys contain the given fragment. This is inclusive - if the given fragment is an exact match for a key in the tree, theKeyValuePair
for that key is also returned.- Specified by:
getKeyValuePairsForKeysContaining
in interfaceSuffixTree<O>
- Parameters:
fragment
- A fragment of keys in the tree for which associatedKeyValuePair
s are sought- Returns:
- The set of
KeyValuePair
s for keys in the tree which contain the given fragment, inclusive
-
size
public int size()
Counts the number of keys/values stored in the tree. In the current implementation, this has a time complexity similar toConcurrentHashMap.size()
.- Specified by:
size
in interfaceSuffixTree<O>
- Returns:
- The number of keys/values stored in the tree
-
nullSafeIterator
static <T> java.util.Iterator<T> nullSafeIterator(java.lang.Iterable<T> iterable)
Utility method to return an iterator for the given iterable, or an empty iterator if the iterable is null.
-
getNode
public Node getNode()
- Specified by:
getNode
in interfacePrettyPrintable
-
-