Package com.googlecode.concurrenttrees.radixinverted

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 of InvertedRadixTree 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.

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 new ConcurrentInvertedRadixTree which will use the given NodeFactory to create nodes.

Method Summary

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 the KeyValuePair 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 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>>	getKeyValuePairsForKeysContainedIn(java.lang.CharSequence document)	Returns a lazy iterable which returns the set of KeyValuePairs 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 of KeyValuePairs 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 of KeyValuePairs 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.

Methods inherited from class java.lang.Object

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

Field Detail

radixTree

private final ConcurrentInvertedRadixTree.ConcurrentInvertedRadixTreeImpl<O> radixTree

Constructor Detail

ConcurrentInvertedRadixTree

public ConcurrentInvertedRadixTree(NodeFactory nodeFactory)

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

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 InvertedRadixTree<O>

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 InvertedRadixTree<O>

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

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 InvertedRadixTree<O>

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

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 InvertedRadixTree<O>

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

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

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 interface InvertedRadixTree<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 interface InvertedRadixTree<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 of KeyValuePairs for keys in the tree which prefix the given document.

Specified by:

getKeyValuePairsForKeysPrefixing in interface InvertedRadixTree<O>

Parameters:

document - A document to be scanned for keys contained in the tree which prefix the given document

Returns:

The set of KeyValuePairs 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 interface InvertedRadixTree<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 interface InvertedRadixTree<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 the KeyValuePair for the longest key in the tree which is a prefix of the given document.

Specified by:

getKeyValuePairForLongestKeyPrefixing in interface InvertedRadixTree<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 interface InvertedRadixTree<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 interface InvertedRadixTree<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 of KeyValuePairs for keys in the tree which are contained in the given document.

Specified by:

getKeyValuePairsForKeysContainedIn in interface InvertedRadixTree<O>

Parameters:

document - A document to be scanned for keys contained in the tree

Returns:

The set of KeyValuePairs 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.

Specified by:

size in interface InvertedRadixTree<O>

Specified by:

size in interface RadixTree<O>

Returns:

The number of keys/values stored in the tree

getNode

public Node getNode()

Specified by:

getNode in interface PrettyPrintable