com.googlecode.concurrenttrees.suffix
Class ConcurrentSuffixTree<O>

java.lang.Object
  com.googlecode.concurrenttrees.suffix.ConcurrentSuffixTree<O>

All Implemented Interfaces:

PrettyPrintable, SuffixTree<O>

public class ConcurrentSuffixTree<O>
extends Object
implements SuffixTree<O>, PrettyPrintable

An implementation of 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.

Author:

Niall Gallagher

Constructor Summary

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.

Method Summary

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 KeyValuePairs 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 KeyValuePairs 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.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

ConcurrentSuffixTree

public ConcurrentSuffixTree(NodeFactory nodeFactory)

Creates a new ConcurrentSuffixTree 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

ConcurrentSuffixTree

public ConcurrentSuffixTree(NodeFactory nodeFactory,
                            boolean restrictConcurrency)

Creates a new ConcurrentSuffixTree 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

restrictConcurrency - 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 threads

Method Detail

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 SuffixTree<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 SuffixTree<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

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 SuffixTree<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

createSetForOriginalKeys

protected Set<String> createSetForOriginalKeys()

Creates a new 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.

Returns:

A new Set in which original keys from which a suffix was generated can be stored

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 SuffixTree<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 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 SuffixTree<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, or multiple suffixes of the same key, the set returned does not contain duplicates (as determined by the value objects' implementation of #equals(Object)).

Specified by:

getValuesForKeysEndingWith in interface SuffixTree<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 SuffixTree<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

getKeysContaining

public Iterable<CharSequence> getKeysContaining(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 interface SuffixTree<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 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.

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 interface SuffixTree<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 Iterable<KeyValuePair<O>> getKeyValuePairsForKeysContaining(CharSequence fragment)

Returns a lazy iterable which returns the set of KeyValuePairs 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.

Specified by:

getKeyValuePairsForKeysContaining in interface SuffixTree<O>

Parameters:

fragment - A fragment of keys in the tree for which associated KeyValuePairs are sought

Returns:

The set of KeyValuePairs 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 to ConcurrentHashMap.size().

Specified by:

size in interface SuffixTree<O>

Returns:

The number of keys/values stored in the tree

getNode

public Node getNode()

Specified by:

getNode in interface PrettyPrintable