public class ConcurrentSuffixTree<O> extends Object implements SuffixTree<O>, PrettyPrintable, Serializable
SuffixTree
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 on ConcurrentRadixTree
.Constructor and Description |
---|
ConcurrentSuffixTree(NodeFactory nodeFactory)
Creates a new
ConcurrentSuffixTree which will use the given NodeFactory to create nodes. |
ConcurrentSuffixTree(NodeFactory nodeFactory,
boolean restrictConcurrency)
Creates a new
ConcurrentSuffixTree which will use the given NodeFactory to create nodes. |
Modifier and Type | Method and Description |
---|---|
protected Set<String> |
createSetForOriginalKeys()
Creates a new
Set in which original keys from which a suffix was generated can be stored. |
Iterable<CharSequence> |
getKeysContaining(CharSequence fragment)
Returns a lazy iterable which returns the set of keys in the tree which contain the given fragment.
|
Iterable<CharSequence> |
getKeysEndingWith(CharSequence suffix)
Returns a lazy iterable which returns the set of keys in the tree which end with the given suffix.
|
Iterable<KeyValuePair<O>> |
getKeyValuePairsForKeysContaining(CharSequence fragment)
Returns a lazy iterable which returns the set of
KeyValuePair s for keys and their associated values in
the tree, where the keys contain the given fragment. |
Iterable<KeyValuePair<O>> |
getKeyValuePairsForKeysEndingWith(CharSequence suffix)
Returns a lazy iterable which returns the set of
KeyValuePair s for keys and their associated values in
the tree, where the keys end with the given suffix. |
Node |
getNode() |
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.
|
Iterable<O> |
getValuesForKeysContaining(CharSequence fragment)
Returns a lazy iterable which returns the set of values associated with keys in the tree which contain the given
fragment.
|
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.
|
O |
put(CharSequence key,
O value)
Associates the given value with the given key; replacing any previous value associated with the key.
|
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.
|
boolean |
remove(CharSequence key)
Removes the value associated with the given key (exact match).
|
int |
size()
Counts the number of keys/values stored in the tree.
|
public ConcurrentSuffixTree(NodeFactory nodeFactory)
ConcurrentSuffixTree
which will use the given NodeFactory
to create nodes.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 nodepublic ConcurrentSuffixTree(NodeFactory nodeFactory, boolean restrictConcurrency)
ConcurrentSuffixTree
which will use the given NodeFactory
to create nodes.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 noderestrictConcurrency
- If true, configures use of a ReadWriteLock
allowing
concurrent reads, except when writes are being performed by other threads, in which case writes block all reads;
if false, configures lock-free reads; allows concurrent non-blocking reads, even if writes are being performed
by other threadspublic O put(CharSequence key, O value)
put
in interface SuffixTree<O>
key
- The key with which the specified value should be associatedvalue
- The value to associate with the key, which cannot be nullpublic O putIfAbsent(CharSequence key, O value)
putIfAbsent
in interface SuffixTree<O>
key
- The key with which the specified value should be associatedvalue
- The value to associate with the key, which cannot be nullpublic boolean remove(CharSequence key)
remove
in interface SuffixTree<O>
key
- The key for which an associated value should be removedprotected Set<String> createSetForOriginalKeys()
Set
in which original keys from which a suffix was generated can be stored.
By default this method creates a new concurrent set based on ConcurrentHashMap
.
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.Set
in which original keys from which a suffix was generated can be storedpublic O getValueForExactKey(CharSequence key)
getValueForExactKey
in interface SuffixTree<O>
key
- The key with which a sought value might be associatedpublic Iterable<CharSequence> getKeysEndingWith(CharSequence suffix)
getKeysEndingWith
in interface SuffixTree<O>
suffix
- A suffix of sought keys in the treepublic Iterable<O> getValuesForKeysEndingWith(CharSequence suffix)
#equals(Object)
).getValuesForKeysEndingWith
in interface SuffixTree<O>
suffix
- A suffix of keys in the tree for which associated values are soughtpublic Iterable<KeyValuePair<O>> getKeyValuePairsForKeysEndingWith(CharSequence suffix)
KeyValuePair
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, the KeyValuePair
for that key is also returned.getKeyValuePairsForKeysEndingWith
in interface SuffixTree<O>
suffix
- A suffix of keys in the tree for which associated KeyValuePair
s are soughtKeyValuePair
s for keys in the tree which end with the given suffix, inclusivepublic Iterable<CharSequence> getKeysContaining(CharSequence fragment)
getKeysContaining
in interface SuffixTree<O>
fragment
- A fragment of sought keys in the treepublic Iterable<O> getValuesForKeysContaining(CharSequence fragment)
getValuesForKeysContaining
in interface SuffixTree<O>
fragment
- A fragment of keys in the tree for which associated values are soughtpublic Iterable<KeyValuePair<O>> getKeyValuePairsForKeysContaining(CharSequence fragment)
KeyValuePair
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, the
KeyValuePair
for that key is also returned.getKeyValuePairsForKeysContaining
in interface SuffixTree<O>
fragment
- A fragment of keys in the tree for which associated KeyValuePair
s are soughtKeyValuePair
s for keys in the tree which contain the given fragment, inclusivepublic int size()
ConcurrentHashMap.size()
.size
in interface SuffixTree<O>
public Node getNode()
getNode
in interface PrettyPrintable
Copyright © 2016. All rights reserved.