Interface RadixTree<O>
-
- Type Parameters:
O
- The type of the values associated with keys in the tree
- All Known Subinterfaces:
InvertedRadixTree<O>
- All Known Implementing Classes:
ConcurrentInvertedRadixTree
,ConcurrentInvertedRadixTree.ConcurrentInvertedRadixTreeImpl
,ConcurrentRadixTree
,ConcurrentReversedRadixTree.ConcurrentReverseRadixTreeImpl
,ConcurrentSuffixTree.ConcurrentSuffixTreeImpl
,LCSubstringSolver.ConcurrentSuffixTreeImpl
public interface RadixTree<O>
API of a radix tree, that is a tree which allows values to be looked up based on prefixes of the keys with which they were associated, as well as based on exact matches for keys. A radix tree essentially allows "equals" and "starts with" lookup. See documentation on each method for details.
-
-
Method Summary
All Methods Instance Methods Abstract 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>
getKeysStartingWith(java.lang.CharSequence prefix)
Returns a lazy iterable which returns the set of keys in the tree which start with the given prefix.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>>
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.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>
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>
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.
-
-
-
Method Detail
-
put
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.- 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
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.- 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
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.- 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
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.- 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
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.- 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
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)
).- 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
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.- 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
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.- Parameters:
candidate
- A candidate key- Returns:
- The set of keys in the tree which most closely match the candidate key, inclusive
-
getValuesForClosestKeys
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.- 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
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.- 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
-
size
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.- Returns:
- The number of keys/values stored in the tree
-
-