edu.wisc.ssec.mcidasv.util.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

Modifier and Type	Interface and Description
static interface	Trie.Cursor<K,V> An interface used by a Trie.

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

Map.Entry<K,V>

Method Summary

Modifier and Type	Method and Description
SortedMap<K,V>	getPrefixedBy(K key) Returns a view of this Trie of all elements that are prefixed by the given key.
SortedMap<K,V>	getPrefixedBy(K key, int length) Returns a view of this Trie of all elements that are prefixed by the length of the key.
SortedMap<K,V>	getPrefixedBy(K key, int offset, int length) Returns a view of this Trie of all elements that are prefixed by the key, starting at the given offset and for the given length.
SortedMap<K,V>	getPrefixedByBits(K key, int bitLength) Returns a view of this Trie of all elements that are prefixed by the number of bits in the given Key.
V	select(K key) Returns the value for the entry whose key is closest in a bitwise XOR metric to the given key.
Map.Entry<K,V>	select(K key, Trie.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.
Map.Entry<K,V>	traverse(Trie.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, compute, computeIfAbsent, computeIfPresent, containsKey, containsValue, equals, forEach, get, getOrDefault, hashCode, isEmpty, merge, put, putAll, putIfAbsent, remove, remove, replace, replace, replaceAll, size

Method Detail

getPrefixedBy

SortedMap<K,V> getPrefixedBy(K key)

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

In a fixed-keysize Trie, this is essentially a 'get' operation.

For example, if the Trie contains 'Lime', 'LimeWire', 'LimeRadio', 'Lax', 'Later', 'Lake', and 'Lovely', then a lookup of 'Lime' would return 'Lime', 'LimeRadio', and 'LimeWire'.

Parameters:

key - Key to search for within the trie.

Returns:

Map containing keys matching the given prefix and their values.

getPrefixedBy

SortedMap<K,V> getPrefixedBy(K key,
                             int length)

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

Fixed-keysize Tries will not support this operation (because all keys will be the same length).

For example, if the Trie contains 'Lime', 'LimeWire', 'LimeRadio', 'Lax', 'Later', 'Lake', and 'Lovely', then a lookup of 'LimePlastics' with a length of 4 would return 'Lime', 'LimeRadio', and 'LimeWire'.

Parameters:

key - Key to search for within the trie.

length - Length of key. Ignored for tries with a fixed key size.

Returns:

Map containing keys matching the given prefix and their values.

getPrefixedBy

SortedMap<K,V> getPrefixedBy(K key,
                             int offset,
                             int length)

Returns a view of this Trie of all elements that are prefixed by the key, starting at the given offset and for the given length.

Fixed-keysize Tries will not support this operation (because all keys are the same length).

For example, if the Trie contains 'Lime', 'LimeWire', 'LimeRadio', 'Lax', 'Later', 'Lake', and 'Lovely', then a lookup of 'The Lime Plastics' with an offset of 4 and a length of 4 would return 'Lime', 'LimeRadio', and 'LimeWire'.

Parameters:

key - Key to search for within the trie.

offset - Offset to begin search at.

length - Length of key. Ignored for tries with a fixed key size.

Returns:

Map containing keys matching the given prefix and their values.

getPrefixedByBits

SortedMap<K,V> getPrefixedByBits(K key,
                                 int bitLength)

Returns a view of this Trie of all elements that are prefixed by the number of bits in the given Key.

Fixed-keysize Tries can support this operation as a way to do lookups of partial keys. That is, if the Trie is storing IP addresses, you can lookup all addresses that begin with '192.168' by providing the key '192.168.X.X' and a length of 16 would return all addresses that begin with '192.168'.

Parameters:

key - Key to search for within the trie.

bitLength - Length of key in bits.

Returns:

Map containing keys matching the given prefix and their values.

select

V select(K key)

Returns the value for the 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

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

Parameters:

key - Key to search for within the trie.

Returns:

Value associated with key.

select

Map.Entry<K,V> select(K key,
                      Trie.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.SelectStatus.EXIT.
The cursor can return Cursor.SelectStatus.CONTINUE to continue traversing.
Cursor.SelectStatus.REMOVE_AND_EXIT is used to remove the current element and stop traversing.

Note: The Trie.Cursor.SelectStatus.REMOVE operation is not supported.

Parameters:

key - Key to match.

cursor - Cursor being used to traverse the trie.

Returns:

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

traverse

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

Traverses the Trie in lexicographical order. Cursor.select will be called on each entry.

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

Parameters:

cursor - Cursor being used to traverse the trie.

Returns:

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