+ *
1. D = 1000100 + *
2. H = 1001000 + *
3. L = 1001100 + *
+ * + * If the {@link 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. + * + * @return The {@link Entry} whose key is closest in a bitwise XOR metric + * to the provided key. + */ + public Map.Entry select(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 {@link 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. + * + * @return The key that is closest in a bitwise XOR metric to the provided key. + */ + public K selectKey(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 {@link 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. + * + * @return The value whose key is closest in a bitwise XOR metric + * to the provided key. + */ + public V selectValue(K key); + + /** + * Iterates through the {@link 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 {@link 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 {@link Decision#EXIT}. + * + *

The cursor can return {@link Decision#CONTINUE} to continue traversing. + * + *

{@link Decision#REMOVE_AND_EXIT} is used to remove the current element + * and stop traversing. + * + *

Note: The {@link Decision#REMOVE} operation is not supported. + * + * @return The entry the cursor returned {@link Decision#EXIT} on, or null + * if it continued till the end. + */ + public Map.Entry select(K key, Cursor cursor); + + /** + * Traverses the {@link Trie} in lexicographical order. + * {@link Cursor#select(java.util.Map.Entry)} will be called on each entry. + * + *

The traversal will stop when the cursor returns {@link Decision#EXIT}, + * {@link Decision#CONTINUE} is used to continue traversing and + * {@link Decision#REMOVE} is used to remove the element that was selected + * and continue traversing. + * + *

{@link Decision#REMOVE_AND_EXIT} is used to remove the current element + * and stop traversing. + * + * @return The entry the cursor returned {@link Decision#EXIT} on, or null + * if it continued till the end. + */ + public Map.Entry traverse(Cursor cursor); + + /** + * Returns a view of this {@link SortedTrie} of all elements that are prefixed + * by the given key. + * + *

In a {@link SortedTrie} with fixed size keys, this is essentially a + * {@link #get(Object)} operation. + * + *

For example, if the {@link SortedTrie} contains 'Anna', 'Anael', + * 'Analu', 'Andreas', 'Andrea', 'Andres', and 'Anatole', then + * a lookup of 'And' would return 'Andreas', 'Andrea', and 'Andres'. + */ + public SortedMap getPrefixedBy(K key); + + /** + * Returns a view of this {@link SortedTrie} of all elements that are prefixed + * by the length of the key. + * + *

{@link SortedTrie}s with fixed size keys will not support this operation + * (because all keys are the same length). + * + *

For example, if the {@link 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'. + */ + public SortedMap getPrefixedBy(K key, int length); + + /** + * Returns a view of this {@link SortedTrie} of all elements that are prefixed + * by the key, starting at the given offset and for the given length. + * + *

{@link SortedTrie}s with fixed size keys will not support this operation + * (because all keys are the same length). + * + *

For example, if the {@link 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'. + */ + public SortedMap getPrefixedBy(K key, int offset, int length); + + /** + * Returns a view of this {@link SortedTrie} of all elements that are prefixed + * by the number of bits in the given Key. + * + *