Package org.apache.cassandra.index.sasi.utils.trie

Interface Trie<K,V>

All Superinterfaces:

Map<K,V>, SortedMap<K,V>

All Known Implementing Classes:

PatriciaTrie

public interface Trie<K,V>
extends SortedMap<K,V>

Defines the interface for a prefix tree, an ordered tree data structure. For more information, see Tries.

Author:

Roger Kapsi, Sam Berlin

Nested Class Summary

Nested classes/interfaces inherited from interface java.util.Map

Map.Entry<K extends Object,V extends Object>

Method Summary

Modifier and Type	Method	Description
SortedMap<K,V>	prefixMap(K prefix)	Returns a view of this Trie of all elements that are prefixed by the given key.
Map.Entry<K,V>	select(K key)	Returns the Map.Entry whose key is closest in a bitwise XOR metric to the given key.
Map.Entry<K,V>	select(K key, Cursor<? super K,? super V> cursor)	Iterates through the Trie, starting with the entry whose bitwise value is closest in an XOR metric to the given key.
K	selectKey(K key)	Returns the key that is closest in a bitwise XOR metric to the provided key.
V	selectValue(K key)	Returns the value whose key is closest in a bitwise XOR metric to the provided key.
Map.Entry<K,V>	traverse(Cursor<? super K,? super V> cursor)	Traverses the Trie in lexicographical order.

Methods inherited from interface java.util.Map

clear, compute, computeIfAbsent, computeIfPresent, containsKey, containsValue, equals, forEach, get, getOrDefault, hashCode, isEmpty, merge, put, putAll, putIfAbsent, remove, remove, replace, replace, replaceAll, size

Methods inherited from interface java.util.SortedMap

comparator, entrySet, firstKey, headMap, keySet, lastKey, subMap, tailMap, values

Method Details

select

Map.Entry<K,V> select(K key)

Returns the Map.Entry whose key is closest in a bitwise XOR metric to the given key. This is NOT lexicographic closeness. For example, given the keys:

1. D = 1000100
2. H = 1001000
3. L = 1001100

If the Trie contained 'H' and 'L', a lookup of 'D' would return 'L', because the XOR distance between D & L is smaller than the XOR distance between D & H.

Returns:

The Map.Entry whose key is closest in a bitwise XOR metric to the provided key.

selectKey

K selectKey(K key)

Returns the key that is closest in a bitwise XOR metric to the provided key. This is NOT lexicographic closeness! For example, given the keys:

1. D = 1000100
2. H = 1001000
3. L = 1001100

If the Trie contained 'H' and 'L', a lookup of 'D' would return 'L', because the XOR distance between D & L is smaller than the XOR distance between D & H.

Returns:

The key that is closest in a bitwise XOR metric to the provided key.

selectValue

V selectValue(K key)

Returns the value whose key is closest in a bitwise XOR metric to the provided key. This is NOT lexicographic closeness! For example, given the keys:

1. D = 1000100
2. H = 1001000
3. L = 1001100

If the Trie contained 'H' and 'L', a lookup of 'D' would return 'L', because the XOR distance between D & L is smaller than the XOR distance between D & H.

Returns:

The value whose key is closest in a bitwise XOR metric to the provided key.

select

Map.Entry<K,V> select(K key,
 Cursor<? super K,? super V> cursor)

Iterates through the Trie, starting with the entry whose bitwise value is closest in an XOR metric to the given key. After the closest entry is found, the Trie will call select on that entry and continue calling select for each entry (traversing in order of XOR closeness, NOT lexicographically) until the cursor returns Cursor.Decision.EXIT.

The cursor can return Cursor.Decision.CONTINUE to continue traversing.

Cursor.Decision.REMOVE_AND_EXIT is used to remove the current element and stop traversing.

Note: The Cursor.Decision.REMOVE operation is not supported.

Returns:

The entry the cursor returned Cursor.Decision.EXIT on, or null if it continued till the end.

traverse

Map.Entry<K,V> traverse(Cursor<? super K,? super V> cursor)

Traverses the Trie in lexicographical order. Cursor.select(java.util.Map.Entry) will be called on each entry.

The traversal will stop when the cursor returns Cursor.Decision.EXIT, Cursor.Decision.CONTINUE is used to continue traversing and Cursor.Decision.REMOVE is used to remove the element that was selected and continue traversing.

Cursor.Decision.REMOVE_AND_EXIT is used to remove the current element and stop traversing.

Returns:

The entry the cursor returned Cursor.Decision.EXIT on, or null if it continued till the end.

prefixMap

SortedMap<K,V> prefixMap(K prefix)

Returns a view of this Trie of all elements that are prefixed by the given key.

In a Trie with fixed size keys, this is essentially a Map.get(Object) operation.

For example, if the Trie contains 'Anna', 'Anael', 'Analu', 'Andreas', 'Andrea', 'Andres', and 'Anatole', then a lookup of 'And' would return 'Andreas', 'Andrea', and 'Andres'.