|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
public interface Trie<K,V>
Defines the interface for a prefix tree, an ordered tree data structure. For more information, see Tries.
Nested Class Summary |
---|
Nested classes/interfaces inherited from interface java.util.Map |
---|
java.util.Map.Entry<K,V> |
Method Summary | |
---|---|
java.util.SortedMap<K,V> |
getPrefixedBy(K key)
Returns a view of this SortedTrie of all elements that are prefixed
by the given key. |
java.util.SortedMap<K,V> |
getPrefixedBy(K key,
int length)
Returns a view of this SortedTrie of all elements that are prefixed
by the length of the key. |
java.util.SortedMap<K,V> |
getPrefixedBy(K key,
int offset,
int length)
Returns a view of this SortedTrie of all elements that are prefixed
by the key, starting at the given offset and for the given length. |
java.util.SortedMap<K,V> |
getPrefixedByBits(K key,
int lengthInBits)
Returns a view of this SortedTrie of all elements that are prefixed
by the number of bits in the given Key. |
java.util.SortedMap<K,V> |
getPrefixedByBits(K key,
int offsetInBits,
int lengthInBits)
Returns a view of this SortedTrie of all elements that are prefixed
by the number of bits in the given Key. |
java.util.Map.Entry<K,V> |
select(K key)
Returns the 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 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. |
java.util.Map.Entry<K,V> |
traverse(Cursor<? super K,? super V> cursor)
Traverses the Trie in lexicographical order. |
Methods inherited from interface java.util.SortedMap |
---|
comparator, entrySet, firstKey, headMap, keySet, lastKey, subMap, tailMap, values |
Methods inherited from interface java.util.Map |
---|
clear, containsKey, containsValue, equals, get, hashCode, isEmpty, put, putAll, remove, size |
Method Detail |
---|
java.util.Map.Entry<K,V> select(K key)
Entry
whose key is closest in a bitwise XOR
metric to the given key. This is NOT lexicographic closeness.
For example, given the keys:
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.
Entry
whose key is closest in a bitwise XOR metric
to the provided key.K selectKey(K key)
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.
V selectValue(K key)
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.
java.util.Map.Entry<K,V> select(K key, Cursor<? super K,? super V> cursor)
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.
Cursor.Decision.EXIT
on, or null
if it continued till the end.java.util.Map.Entry<K,V> traverse(Cursor<? super K,? super V> cursor)
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.
Cursor.Decision.EXIT
on, or null
if it continued till the end.java.util.SortedMap<K,V> getPrefixedBy(K key)
SortedTrie
of all elements that are prefixed
by the given key.
In a SortedTrie
with fixed size keys, this is essentially a
Map.get(Object)
operation.
For example, if the SortedTrie
contains 'Anna', 'Anael',
'Analu', 'Andreas', 'Andrea', 'Andres', and 'Anatole', then
a lookup of 'And' would return 'Andreas', 'Andrea', and 'Andres'.
java.util.SortedMap<K,V> getPrefixedBy(K key, int length)
SortedTrie
of all elements that are prefixed
by the length of the key.
SortedTrie
s with fixed size keys will not support this operation
(because all keys are the same length).
For example, if the SortedTrie
contains 'Anna', 'Anael', 'Analu',
'Andreas', 'Andrea', 'Andres', and 'Anatole', then a lookup for 'Andrey'
and a length of 4 would return 'Andreas', 'Andrea', and 'Andres'.
java.util.SortedMap<K,V> getPrefixedBy(K key, int offset, int length)
SortedTrie
of all elements that are prefixed
by the key, starting at the given offset and for the given length.
SortedTrie
s with fixed size keys will not support this operation
(because all keys are the same length).
For example, if the SortedTrie
contains 'Anna', 'Anael', 'Analu',
'Andreas', 'Andrea', 'Andres', and 'Anatole', then a lookup for
'Hello Andrey Smith', an offset of 6 and a length of 4 would return
'Andreas', 'Andrea', and 'Andres'.
java.util.SortedMap<K,V> getPrefixedByBits(K key, int lengthInBits)
SortedTrie
of all elements that are prefixed
by the number of bits in the given Key.
In SortedTrie
s with fixed size keys like IP addresses this method
can be used to lookup partial keys. That is you can lookup all addresses
that begin with '192.168' by providing the key '192.168.X.X' and a
length of 16.
java.util.SortedMap<K,V> getPrefixedByBits(K key, int offsetInBits, int lengthInBits)
SortedTrie
of all elements that are prefixed
by the number of bits in the given Key.
|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |