Interface Trie<K,V>
-
- All Superinterfaces:
java.util.Map<K,V>
,java.util.SortedMap<K,V>
- All Known Implementing Classes:
PatriciaTrie
public interface Trie<K,V> extends java.util.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
-
-
Method Summary
All Methods Instance Methods Abstract Methods Modifier and Type Method Description java.util.SortedMap<K,V>
prefixMap(K prefix)
Returns a view of thisTrie
of all elements that are prefixed by the given key.java.util.Map.Entry<K,V>
select(K key)
Returns theMap.Entry
whose key is closest in a bitwise XOR metric to the given key.java.util.Map.Entry<K,V>
select(K key, Cursor<? super K,? super V> cursor)
Iterates through theTrie
, 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.java.util.Map.Entry<K,V>
traverse(Cursor<? super K,? super V> cursor)
Traverses theTrie
in lexicographical order.
-
-
-
Method Detail
-
select
java.util.Map.Entry<K,V> select(K key)
Returns theMap.Entry
whose key is closest in a bitwise XOR metric to the given key. This is NOT lexicographic closeness. For example, given the keys:- D = 1000100
- H = 1001000
- L = 1001100
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:- D = 1000100
- H = 1001000
- L = 1001100
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:- D = 1000100
- H = 1001000
- L = 1001100
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
java.util.Map.Entry<K,V> select(K key, Cursor<? super K,? super V> cursor)
Iterates through theTrie
, starting with the entry whose bitwise value is closest in an XOR metric to the given key. After the closest entry is found, theTrie
will call select on that entry and continue calling select for each entry (traversing in order of XOR closeness, NOT lexicographically) until the cursor returnsCursor.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
java.util.Map.Entry<K,V> traverse(Cursor<? super K,? super V> cursor)
Traverses theTrie
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 andCursor.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
java.util.SortedMap<K,V> prefixMap(K prefix)
Returns a view of thisTrie
of all elements that are prefixed by the given key.In a
Trie
with fixed size keys, this is essentially aMap.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'.
-
-