org.ardverk.collection
Class PatriciaTrie<K,V>

java.lang.Object
  java.util.AbstractMap<K,V>
      org.ardverk.collection.PatriciaTrie<K,V>

All Implemented Interfaces:

java.io.Serializable, java.util.Map<K,V>, java.util.SortedMap<K,V>, Trie<K,V>

public class PatriciaTrie<K,V>
extends java.util.AbstractMap<K,V>
implements Trie<K,V>

PATRICIA Trie

Practical Algorithm to Retrieve Information Coded in Alphanumeric

A PATRICIA Trie is a compressed Trie. Instead of storing all data at the edges of the Trie (and having empty internal nodes), PATRICIA stores data in every node. This allows for very efficient traversal, insert, delete, predecessor, successor, prefix, range, and select(Object) operations. All operations are performed at worst in O(K) time, where K is the number of bits in the largest item in the tree. In practice, operations actually take O(A(K)) time, where A(K) is the average number of bits of all items in the tree.

Most importantly, PATRICIA requires very few comparisons to keys while doing any operation. While performing a lookup, each comparison (at most K of them, described above) will perform a single bit comparison against the given key, instead of comparing the entire key to another key.

The Trie can return operations in lexicographical order using the traverse(Cursor), 'prefix', 'submap', or 'iterator' methods. The Trie can also scan for items that are 'bitwise' (using an XOR metric) by the 'select' method. Bitwise closeness is determined by the KeyAnalyzer returning true or false for a bit being set or not in a given key.

This PATRICIA Trie supports both variable length & fixed length keys. Some methods, such as getPrefixedBy(Object) are suited only to variable length keys, whereas getPrefixedByBits(Object, int) is suited to fixed-size keys.

Any methods here that take an Object argument may throw a ClassCastException if the method is expecting an instance of K and it isn't K.

Author:

Roger Kapsi, Sam Berlin

See Also:

Radix Tree, PATRICIA, Crit-Bit Tree, Serialized Form

Nested Class Summary

Nested classes/interfaces inherited from class java.util.AbstractMap

java.util.AbstractMap.SimpleEntry<K,V>, java.util.AbstractMap.SimpleImmutableEntry<K,V>

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

java.util.Map.Entry<K,V>

Field Summary

protected KeyAnalyzer<? super K>

keyAnalyzer The KeyAnalyzer that's being used to build the PATRICIA Trie

Constructor Summary

PatriciaTrie(KeyAnalyzer<? super K> keyAnalyzer)

PatriciaTrie(KeyAnalyzer<? super K> keyAnalyzer, java.util.Map<? extends K,? extends V> m)

Method Summary

void	clear()
java.util.Comparator<? super K>	comparator()
boolean	containsKey(java.lang.Object k)
java.util.Set<java.util.Map.Entry<K,V>>	entrySet()
K	firstKey()
V	get(java.lang.Object k)
KeyAnalyzer<? super K>	getKeyAnalyzer() Returns the KeyAnalyzer that constructed the Trie.
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.SortedMap<K,V>	headMap(K toKey)
java.util.Set<K>	keySet()
K	lastKey()
V	put(K key, V value)
V	remove(java.lang.Object k)
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.
int	size()
java.util.SortedMap<K,V>	subMap(K fromKey, K toKey)
java.util.SortedMap<K,V>	tailMap(K fromKey)
java.lang.String	toString()
java.util.Map.Entry<K,V>	traverse(Cursor<? super K,? super V> cursor) Traverses the Trie in lexicographical order.
java.util.Collection<V>	values()

Methods inherited from class java.util.AbstractMap

clone, containsValue, equals, hashCode, isEmpty, putAll

Methods inherited from class java.lang.Object

finalize, getClass, notify, notifyAll, wait, wait, wait

Methods inherited from interface org.ardverk.collection.Trie

select, select, selectKey, selectValue, traverse

Methods inherited from interface java.util.SortedMap

entrySet, keySet, values

Methods inherited from interface java.util.Map

clear, containsKey, containsValue, equals, get, hashCode, isEmpty, put, putAll, remove, size

Field Detail

keyAnalyzer

protected final KeyAnalyzer<? super K> keyAnalyzer

The KeyAnalyzer that's being used to build the PATRICIA Trie

Constructor Detail

PatriciaTrie

public PatriciaTrie(KeyAnalyzer<? super K> keyAnalyzer)

PatriciaTrie

public PatriciaTrie(KeyAnalyzer<? super K> keyAnalyzer,
                    java.util.Map<? extends K,? extends V> m)

Method Detail

comparator

public java.util.Comparator<? super K> comparator()

Specified by:

comparator in interface java.util.SortedMap<K,V>

getPrefixedBy

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

Specified by:

getPrefixedBy in interface Trie<K,V>

getPrefixedBy

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

Specified by:

getPrefixedBy in interface Trie<K,V>

getPrefixedBy

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

Specified by:

getPrefixedBy in interface Trie<K,V>

getPrefixedByBits

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

Specified by:

getPrefixedByBits in interface Trie<K,V>

firstKey

public K firstKey()

Specified by:

firstKey in interface java.util.SortedMap<K,V>

lastKey

public K lastKey()

Specified by:

lastKey in interface java.util.SortedMap<K,V>

getPrefixedByBits

public 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. The view that this returns is optimized to have a very efficient Iterator. The SortedMap#firstEntry(), SortedMap.lastKey() & Map.size() methods must iterate over all possible values in order to determine the results. This information is cached until the PATRICIA Trie changes. All other methods (except Iterator) must compare the given key to the prefix to ensure that it is within the range of the view. The Iterator's remove method must also relocate the subtree that contains the prefixes if the entry holding the subtree is removed or changes. Changing the subtree takes O(K) time.

Specified by:

getPrefixedByBits in interface Trie<K,V>

headMap

public java.util.SortedMap<K,V> headMap(K toKey)

Specified by:

headMap in interface java.util.SortedMap<K,V>

subMap

public java.util.SortedMap<K,V> subMap(K fromKey,
                                       K toKey)

Specified by:

subMap in interface java.util.SortedMap<K,V>

tailMap

public java.util.SortedMap<K,V> tailMap(K fromKey)

Specified by:

tailMap in interface java.util.SortedMap<K,V>

clear

public void clear()

Specified by:

clear in interface java.util.Map<K,V>

Overrides:

clear in class java.util.AbstractMap<K,V>

size

public int size()

Specified by:

size in interface java.util.Map<K,V>

Overrides:

size in class java.util.AbstractMap<K,V>

put

public V put(K key,
             V value)

Specified by:

put in interface java.util.Map<K,V>

Overrides:

put in class java.util.AbstractMap<K,V>

get

public V get(java.lang.Object k)

Specified by:

get in interface java.util.Map<K,V>

Overrides:

get in class java.util.AbstractMap<K,V>

select

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

select

public 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

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

containsKey

public boolean containsKey(java.lang.Object k)

Specified by:

containsKey in interface java.util.Map<K,V>

Overrides:

containsKey in class java.util.AbstractMap<K,V>

entrySet

public java.util.Set<java.util.Map.Entry<K,V>> entrySet()

Specified by:

entrySet in interface java.util.Map<K,V>

Specified by:

entrySet in interface java.util.SortedMap<K,V>

Specified by:

entrySet in class java.util.AbstractMap<K,V>

keySet

public java.util.Set<K> keySet()

Specified by:

keySet in interface java.util.Map<K,V>

Specified by:

keySet in interface java.util.SortedMap<K,V>

Overrides:

keySet in class java.util.AbstractMap<K,V>

values

public java.util.Collection<V> values()

Specified by:

values in interface java.util.Map<K,V>

Specified by:

values in interface java.util.SortedMap<K,V>

Overrides:

values in class java.util.AbstractMap<K,V>

remove

public V remove(java.lang.Object k)

Specified by:

remove in interface java.util.Map<K,V>

Overrides:

remove in class java.util.AbstractMap<K,V>

Throws:

java.lang.ClassCastException - if provided key is of an incompatible type

getKeyAnalyzer

public KeyAnalyzer<? super K> getKeyAnalyzer()

Returns the KeyAnalyzer that constructed the Trie.

selectKey

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

Specified by:

selectKey in interface Trie<K,V>

Returns:

The key that is closest in a bitwise XOR metric to the provided key.

selectValue

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

Specified by:

selectValue in interface Trie<K,V>

Returns:

The value whose key is closest in a bitwise XOR metric to the provided key.

toString

public java.lang.String toString()

Overrides:

toString in class java.util.AbstractMap<K,V>