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

java.lang.Object
  extended by java.util.AbstractMap<K,V>
      extended by 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>


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