org.ardverk.collection
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

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

select

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. 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 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

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. 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

java.util.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.

getPrefixedBy

java.util.SortedMap<K,V> getPrefixedBy(K key)
Returns a view of this 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'.


getPrefixedBy

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.

SortedTries 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'.


getPrefixedBy

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.

SortedTries 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'.


getPrefixedByBits

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.

In SortedTries 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.


getPrefixedByBits

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.



Copyright © 2005-2009 Roger Kapsi, Sam Berlin. All Rights Reserved.