net.sf.eos.trie
Class PatriciaTrie<K,V>

java.lang.Object
  java.util.AbstractMap<K,V>
      net.sf.eos.trie.PatriciaTrie<K,V>

All Implemented Interfaces:

Serializable, Map<K,V>, SortedMap<K,V>, Trie<K,V>

public class PatriciaTrie<K,V>
extends AbstractMap<K,V>
implements Trie<K,V>, Serializable

A PATRICIA Trie.

PATRICIA = 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' 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', '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 PatriciaTrie.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(...) are suited only to variable length keys, whereas getPrefixedByBits(...) is suited to fixed-size keys.

Additionally see PATRICIA for more information.

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

    PatriciaTrie<String, String> trie = new PatriciaTrie<String, String>
    (new CharSequenceKeyAnalyzer());

    trie.put("Lime", "Lime");
    trie.put("LimeWire", "LimeWire");
    trie.put("LimeRadio", "LimeRadio");
    trie.put("Lax", "Lax");
    trie.put("Lake", "Lake");
    trie.put("Lovely", "Lovely");

    System.out.println(trie.select("Lo"));
    System.out.println(trie.select("Lime"));

    System.out.println(trie.getPrefixedBy("La").toString());

    Output:
        Lovely
        Lime
        {Lake=Lake, Lax=Lax}

 

Note: Taken from Limewire sourcecode and repackaged by Sascha Kohlmann.

Author:

Roger Kapsi, Sam Berlin

See Also:

Serialized Form

Nested Class Summary

static interface

PatriciaTrie.KeyAnalyzer<K> Defines the interface to analyze Trie keys on a bit level.

Nested classes/interfaces inherited from interface net.sf.eos.trie.Trie

Trie.Cursor<K,V>

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

Map.Entry<K,V>

Constructor Summary

PatriciaTrie(PatriciaTrie.KeyAnalyzer<? super K> keyAnalyzer)
Constructs a new PatriciaTrie using the given keyAnalyzer.

Method Summary

protected K	asKey(Object key) Gets the key as a 'K'.
protected net.sf.eos.trie.PatriciaTrie.TrieEntry<K,V>	ceilingEntry(K key) Returns a key-value mapping associated with the least key greater than or equal to the given key, or null if there is no such key.
void	clear() Clears the Trie (i.e. removes all elements).
Comparator<? super K>	comparator() Returns the KeyAnalyzer as a comparator.
boolean	containsKey(Object k) Returns true if this trie contains the specified Key This may throw ClassCastException if the object is not of type K.
boolean	containsValue(Object o) Returns true if this Trie contains the specified value.
Set<Map.Entry<K,V>>	entrySet()
K	firstKey()
protected net.sf.eos.trie.PatriciaTrie.TrieEntry<K,V>	floorEntry(K key) Returns a key-value mapping associated with the greatest key less than or equal to the given key, or null if there is no such key.
protected net.sf.eos.trie.PatriciaTrie.TrieEntry<K,V>	followRight(net.sf.eos.trie.PatriciaTrie.TrieEntry<K,V> node) Traverses down the right path until it finds an uplink.
V	get(Object k) Returns the Value whose Key equals our lookup Key or null if no such key exists.
PatriciaTrie.KeyAnalyzer<? super K>	getKeyAnalyzer() Returns the KeyAnalyzer that constructed the trie.
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.
SortedMap<K,V>	headMap(K toKey)
protected net.sf.eos.trie.PatriciaTrie.TrieEntry<K,V>	higherEntry(K key) Returns an entry strictly higher than the given key, or null if no such entry exists.
boolean	isEmpty() Returns true if the Trie is empty
Set<K>	keySet() Returns a set view of the keys contained in this map.
K	lastKey()
protected net.sf.eos.trie.PatriciaTrie.TrieEntry<K,V>	lowerEntry(K key) Returns a key-value mapping associated with the greatest key strictly less than the given key, or null if there is no such key.
V	put(K key, V value) Adds a new pair to the Trie and if a pair already exists it will be replaced.
V	remove(Object k) Removes a Key from the Trie if one exists This may throw ClassCastException if the object is not of type K.
V	select(K key) Returns the Value whose Key has the longest prefix in common with our lookup 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.
int	size() Returns the number items in the Trie
SortedMap<K,V>	subMap(K fromKey, K toKey)
SortedMap<K,V>	tailMap(K fromKey)
String	toString() Returns each entry as a string.
Map.Entry<K,V>	traverse(Trie.Cursor<? super K,? super V> cursor) Traverses the Trie in lexicographical order.
Collection<V>	values() Returns a collection view of the values contained in this map.

Methods inherited from class java.util.AbstractMap

clone, equals, hashCode, putAll

Methods inherited from class java.lang.Object

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

Methods inherited from interface java.util.Map

equals, hashCode, putAll

Constructor Detail

PatriciaTrie

public PatriciaTrie(PatriciaTrie.KeyAnalyzer<? super K> keyAnalyzer)

Constructs a new PatriciaTrie using the given keyAnalyzer.

Method Detail

getKeyAnalyzer

public PatriciaTrie.KeyAnalyzer<? super K> getKeyAnalyzer()

Returns the KeyAnalyzer that constructed the trie.

comparator

public Comparator<? super K> comparator()

Returns the KeyAnalyzer as a comparator.

Specified by:

comparator in interface SortedMap<K,V>

clear

public void clear()

Clears the Trie (i.e. removes all elements).

Specified by:

clear in interface Map<K,V>

Overrides:

clear in class AbstractMap<K,V>

isEmpty

public boolean isEmpty()

Returns true if the Trie is empty

Specified by:

isEmpty in interface Map<K,V>

Overrides:

isEmpty in class AbstractMap<K,V>

size

public int size()

Returns the number items in the Trie

Specified by:

size in interface Map<K,V>

Overrides:

size in class AbstractMap<K,V>

put

public V put(K key,
             V value)

Adds a new pair to the Trie and if a pair already exists it will be replaced. In the latter case it will return the old value.

Specified by:

put in interface Map<K,V>

Overrides:

put in class AbstractMap<K,V>

entrySet

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

Specified by:

entrySet in interface Map<K,V>

Specified by:

entrySet in class AbstractMap<K,V>

get

public V get(Object k)

Returns the Value whose Key equals our lookup Key or null if no such key exists.

Specified by:

get in interface Map<K,V>

Overrides:

get in class AbstractMap<K,V>

asKey

protected final K asKey(Object key)

Gets the key as a 'K'.

select

public V select(K key)

Returns the Value whose Key has the longest prefix in common with our lookup key.

Specified by:

select in interface Trie<K,V>

select

public Map.Entry<K,V> select(K key,
                             Trie.Cursor<? super K,? super V> cursor)

Description copied from interface: Trie

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.

Specified by:

select in interface Trie<K,V>

Returns:

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

getPrefixedBy

public 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'. The view that this returns is optimized to have a very efficient Iterator. The firstKey, lastKey & size methods must iterate over all possible values in order to determine the results. This information is cached until the Patricia tree 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:

getPrefixedBy in interface Trie<K,V>

Parameters:

key -

getPrefixedBy

public 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'. The view that this returns is optimized to have a very efficient Iterator. The firstKey, lastKey & size methods must iterate over all possible values in order to determine the results. This information is cached until the Patricia tree 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:

getPrefixedBy in interface Trie<K,V>

Parameters:

key -

length -

getPrefixedBy

public 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'. The view that this returns is optimized to have a very efficient Iterator. The firstKey, lastKey & size methods must iterate over all possible values in order to determine the results. This information is cached until the Patricia tree 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:

getPrefixedBy in interface Trie<K,V>

Parameters:

key -

offset -

length -

getPrefixedByBits

public 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'. The view that this returns is optimized to have a very efficient Iterator. The firstKey, lastKey & size methods must iterate over all possible values in order to determine the results. This information is cached until the Patricia tree 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>

Parameters:

key -

bitLength -

containsKey

public boolean containsKey(Object k)

Returns true if this trie contains the specified Key This may throw ClassCastException if the object is not of type K.

Specified by:

containsKey in interface Map<K,V>

Overrides:

containsKey in class AbstractMap<K,V>

containsValue

public boolean containsValue(Object o)

Returns true if this Trie contains the specified value.

Specified by:

containsValue in interface Map<K,V>

Overrides:

containsValue in class AbstractMap<K,V>

remove

public V remove(Object k)

Removes a Key from the Trie if one exists This may throw ClassCastException if the object is not of type K.

Specified by:

remove in interface Map<K,V>

Overrides:

remove in class AbstractMap<K,V>

Parameters:

k - the Key to delete

Returns:

Returns the deleted Value

toString

public String toString()

Returns each entry as a string.

Overrides:

toString in class AbstractMap<K,V>

traverse

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

Description copied from interface: Trie

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.

Specified by:

traverse in interface Trie<K,V>

Returns:

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

keySet

public Set<K> keySet()

Returns a set view of the keys contained in this map. The set is backed by the map, so changes to the map are reflected in the set, and vice-versa. The set supports element removal, which removes the corresponding mapping from this map, via the Iterator.remove, Set.remove, removeAll, retainAll, and clear operations. It does not support the add or addAll operations.

Specified by:

keySet in interface Map<K,V>

Overrides:

keySet in class AbstractMap<K,V>

Returns:

a set view of the keys contained in this map.

values

public Collection<V> values()

Returns a collection view of the values contained in this map. The collection is backed by the map, so changes to the map are reflected in the collection, and vice-versa. The collection supports element removal, which removes the corresponding mapping from this map, via the Iterator.remove, Collection.remove, removeAll, retainAll, and clear operations. It does not support the add or addAll operations.

Specified by:

values in interface Map<K,V>

Overrides:

values in class AbstractMap<K,V>

Returns:

a collection view of the values contained in this map.

followRight

protected net.sf.eos.trie.PatriciaTrie.TrieEntry<K,V> followRight(net.sf.eos.trie.PatriciaTrie.TrieEntry<K,V> node)

Traverses down the right path until it finds an uplink.

firstKey

public K firstKey()

Specified by:

firstKey in interface SortedMap<K,V>

headMap

public SortedMap<K,V> headMap(K toKey)

Specified by:

headMap in interface SortedMap<K,V>

lastKey

public K lastKey()

Specified by:

lastKey in interface SortedMap<K,V>

subMap

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

Specified by:

subMap in interface SortedMap<K,V>

tailMap

public SortedMap<K,V> tailMap(K fromKey)

Specified by:

tailMap in interface SortedMap<K,V>

higherEntry

protected net.sf.eos.trie.PatriciaTrie.TrieEntry<K,V> higherEntry(K key)

Returns an entry strictly higher than the given key, or null if no such entry exists.

ceilingEntry

protected net.sf.eos.trie.PatriciaTrie.TrieEntry<K,V> ceilingEntry(K key)

Returns a key-value mapping associated with the least key greater than or equal to the given key, or null if there is no such key.

lowerEntry

protected net.sf.eos.trie.PatriciaTrie.TrieEntry<K,V> lowerEntry(K key)

Returns a key-value mapping associated with the greatest key strictly less than the given key, or null if there is no such key.

floorEntry

protected net.sf.eos.trie.PatriciaTrie.TrieEntry<K,V> floorEntry(K key)

Returns a key-value mapping associated with the greatest key less than or equal to the given key, or null if there is no such key.