public class PatriciaTrie<E> extends AbstractBitwiseTrie<K,V> implements Trie<java.lang.String,E>
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
'prefixMap', '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 prefixMap(Object)
are suited only
to variable length keys.
Modifier and Type | Class and Description |
---|---|
protected static class |
AbstractPatriciaTrie.TrieEntry<K,V>
A
Trie is a set of AbstractPatriciaTrie.TrieEntry nodes. |
Modifier and Type | Field and Description |
---|---|
protected int |
modCount
The number of times this
Trie has been modified. |
Constructor and Description |
---|
PatriciaTrie() |
PatriciaTrie(java.util.Map<? extends java.lang.String,? extends E> 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()
Gets the first key currently in this map.
|
V |
get(java.lang.Object k) |
int |
hashCode()
Gets the standard Map hashCode.
|
java.util.SortedMap<K,V> |
headMap(K toKey) |
java.util.Set<K> |
keySet() |
K |
lastKey()
Gets the last key currently in this map.
|
OrderedMapIterator<K,V> |
mapIterator()
Obtains an
OrderedMapIterator over the map. |
K |
nextKey(K key)
Gets the next key after the one specified.
|
java.util.SortedMap<K,V> |
prefixMap(K key)
Returns a view of this
Trie of all elements that are prefixed
by the given key. |
K |
previousKey(K key)
Gets the previous key before the one specified.
|
V |
put(K key,
V value)
Note that the return type is Object, rather than V as in the Map interface.
|
V |
remove(java.lang.Object k) |
java.util.Map.Entry<K,V> |
select(K key)
Returns the
Map.Entry whose key is closest in a bitwise 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.util.Collection<V> |
values() |
getKeyAnalyzer, toString
clear, clone, containsValue, equals, isEmpty, putAll
finalize, getClass, notify, notifyAll, wait, wait, wait
comparator, entrySet, firstKey, headMap, keySet, lastKey, subMap, tailMap, values
firstKey, lastKey, mapIterator, nextKey, previousKey
clear, containsKey, containsValue, equals, get, hashCode, isEmpty, put, putAll, remove, size
containsKey, containsValue, entrySet, get, isEmpty, keySet, remove, size, values
protected transient int modCount
Trie
has been modified.
It's used to detect concurrent modifications and fail-fast the Iterator
s.public PatriciaTrie()
public PatriciaTrie(java.util.Map<? extends java.lang.String,? extends E> m)
public void clear()
public int size()
public V put(K key, V value)
Put
public V get(java.lang.Object k)
public java.util.Map.Entry<K,V> select(K key)
Map.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.key
- the key to use in the searchMap.Entry
whose key is closest in a bitwise XOR metric
to the provided keypublic 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.key
- the key to use in the searchpublic 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.key
- the key to use in the searchpublic boolean containsKey(java.lang.Object k)
containsKey
in interface java.util.Map<K,V>
containsKey
in interface Get<K,V>
containsKey
in class java.util.AbstractMap<K,V>
Map.containsKey(Object)
public java.util.Set<java.util.Map.Entry<K,V>> entrySet()
public java.util.Set<K> keySet()
public java.util.Collection<V> values()
public V remove(java.lang.Object k)
public int hashCode()
hashCode
in interface java.util.Map<K,V>
hashCode
in class java.util.AbstractMap<K,V>
public java.util.Comparator<? super K> comparator()
comparator
in interface java.util.SortedMap<K,V>
public K firstKey()
OrderedMap
firstKey
in interface java.util.SortedMap<K,V>
firstKey
in interface OrderedMap<K,V>
public K lastKey()
OrderedMap
lastKey
in interface java.util.SortedMap<K,V>
lastKey
in interface OrderedMap<K,V>
public K nextKey(K key)
OrderedMap
nextKey
in interface OrderedMap<K,V>
key
- the key to search for next frompublic K previousKey(K key)
OrderedMap
previousKey
in interface OrderedMap<K,V>
key
- the key to search for previous frompublic OrderedMapIterator<K,V> mapIterator()
OrderedMap
OrderedMapIterator
over the map.
A ordered map iterator is an efficient way of iterating over maps in both directions.
mapIterator
in interface IterableGet<K,V>
mapIterator
in interface OrderedMap<K,V>
public java.util.SortedMap<K,V> prefixMap(K key)
Trie
Trie
of all elements that are prefixed
by the given key.
In a Trie
with fixed size keys, this is essentially a
Map.get(Object)
operation.
For example, if the Trie
contains 'Anna', 'Anael',
'Analu', 'Andreas', 'Andrea', 'Andres', and 'Anatole', then
a lookup of 'And' would return 'Andreas', 'Andrea', and 'Andres'.
public java.util.SortedMap<K,V> headMap(K toKey)
headMap
in interface java.util.SortedMap<K,V>
public java.util.SortedMap<K,V> subMap(K fromKey, K toKey)
subMap
in interface java.util.SortedMap<K,V>
public java.util.SortedMap<K,V> tailMap(K fromKey)
tailMap
in interface java.util.SortedMap<K,V>
Copyright © 2001-2013. All Rights Reserved.