public class PatriciaTrie<K,V> extends java.util.AbstractMap<K,V> implements Trie<K,V>
Trie
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.
Modifier and Type | Field and Description |
---|---|
protected KeyAnalyzer<? super K> |
keyAnalyzer
The
KeyAnalyzer that's being used to build the
PATRICIA Trie |
Constructor and Description |
---|
PatriciaTrie(KeyAnalyzer<? super K> keyAnalyzer) |
PatriciaTrie(KeyAnalyzer<? super K> keyAnalyzer,
java.util.Map<? extends K,? extends V> m) |
Modifier and Type | Method and Description |
---|---|
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() |
clone, containsValue, equals, hashCode, isEmpty, putAll
finalize, getClass, notify, notifyAll, wait, wait, wait
protected final KeyAnalyzer<? super K> keyAnalyzer
KeyAnalyzer
that's being used to build the
PATRICIA Trie
public PatriciaTrie(KeyAnalyzer<? super K> keyAnalyzer)
public PatriciaTrie(KeyAnalyzer<? super K> keyAnalyzer, java.util.Map<? extends K,? extends V> m)
public java.util.Comparator<? super K> comparator()
public java.util.SortedMap<K,V> getPrefixedBy(K key)
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
in interface Trie<K,V>
public java.util.SortedMap<K,V> getPrefixedBy(K key, int length)
SortedTrie
of all elements that are prefixed
by the length of the key.
SortedTrie
s 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
in interface Trie<K,V>
public java.util.SortedMap<K,V> getPrefixedBy(K key, int offset, int length)
SortedTrie
of all elements that are prefixed
by the key, starting at the given offset and for the given length.
SortedTrie
s 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'.
getPrefixedBy
in interface Trie<K,V>
public java.util.SortedMap<K,V> getPrefixedByBits(K key, int lengthInBits)
SortedTrie
of all elements that are prefixed
by the number of bits in the given Key.
In SortedTrie
s 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
in interface Trie<K,V>
public java.util.SortedMap<K,V> getPrefixedByBits(K key, int offsetInBits, int lengthInBits)
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.getPrefixedByBits
in interface Trie<K,V>
public void clear()
clear
in interface java.util.Map<K,V>
clear
in class java.util.AbstractMap<K,V>
public int size()
size
in interface java.util.Map<K,V>
size
in class java.util.AbstractMap<K,V>
public V put(K key, V value)
put
in interface java.util.Map<K,V>
put
in class java.util.AbstractMap<K,V>
public V get(java.lang.Object k)
get
in interface java.util.Map<K,V>
get
in class java.util.AbstractMap<K,V>
public java.util.Map.Entry<K,V> select(K key)
Entry
whose key is closest in a bitwise XOR
metric to the given key. This is NOT lexicographic closeness.
For example, given the keys:
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.Entry
whose key is closest in a bitwise XOR metric
to the provided key.public java.util.Map.Entry<K,V> select(K key, Cursor<? super K,? super V> cursor)
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.
Cursor.Decision.EXIT
on, or null
if it continued till the end.public java.util.Map.Entry<K,V> traverse(Cursor<? super K,? super V> cursor)
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.
Cursor.Decision.EXIT
on, or null
if it continued till the end.public boolean containsKey(java.lang.Object k)
containsKey
in interface java.util.Map<K,V>
containsKey
in class java.util.AbstractMap<K,V>
public java.util.Set<java.util.Map.Entry<K,V>> entrySet()
entrySet
in interface java.util.Map<K,V>
entrySet
in interface java.util.SortedMap<K,V>
entrySet
in class java.util.AbstractMap<K,V>
public java.util.Set<K> keySet()
keySet
in interface java.util.Map<K,V>
keySet
in interface java.util.SortedMap<K,V>
keySet
in class java.util.AbstractMap<K,V>
public java.util.Collection<V> values()
values
in interface java.util.Map<K,V>
values
in interface java.util.SortedMap<K,V>
values
in class java.util.AbstractMap<K,V>
public V remove(java.lang.Object k)
remove
in interface java.util.Map<K,V>
remove
in class java.util.AbstractMap<K,V>
java.lang.ClassCastException
- if provided key is of an incompatible typepublic KeyAnalyzer<? super K> getKeyAnalyzer()
KeyAnalyzer
that constructed the Trie
.public K selectKey(K key)
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.public V selectValue(K key)
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.selectValue
in interface Trie<K,V>
public java.lang.String toString()
toString
in class java.util.AbstractMap<K,V>
Copyright © 2005-2009 Roger Kapsi, Sam Berlin. All Rights Reserved.