E - the type of the values in this mappublic class PatriciaTrie<E> extends AbstractBitwiseTrie<K,V>
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.
| 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) |
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 a
MapIterator 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() |
toStringcompute, computeIfAbsent, computeIfPresent, containsValue, equals, forEach, getOrDefault, hashCode, isEmpty, merge, putAll, putIfAbsent, remove, replace, replace, replaceAllcontainsValue, isEmptypublic 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)
Putput in interface java.util.Map<K,V>put in interface Put<K,V>put in class java.util.AbstractMap<K,V>key - key with which the specified value is to be associatedvalue - value to be associated with the specified keykey, or
null if there was no mapping for key.
(A null return can also indicate that the map
previously associated null with key,
if the implementation supports null values.)Map.put(Object, Object)public V get(java.lang.Object k)
get in interface java.util.Map<K,V>get in interface Get<K,V>get in class java.util.AbstractMap<K,V>k - the key whose associated value is to be returnednull if this map contains no mapping for the keyMap.get(Object)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>k - key whose presence in this map is to be testedtrue if this map contains a mapping for the specified
keyMap.containsKey(Object)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 interface Get<K,V>entrySet in class java.util.AbstractMap<K,V>Map.entrySet()public java.util.Set<K> keySet()
public java.util.Collection<V> values()
public V remove(java.lang.Object k)
remove in interface java.util.Map<K,V>remove in interface Get<K,V>remove in class java.util.AbstractMap<K,V>k - key whose mapping is to be removed from the mapkey, or
null if there was no mapping for key.java.lang.ClassCastException - if provided key is of an incompatible typeMap.remove(Object)public java.util.Comparator<? super K> comparator()
public K firstKey()
OrderedMappublic K lastKey()
OrderedMappublic K nextKey(K key)
OrderedMapkey - the key to search for next frompublic K previousKey(K key)
OrderedMapkey - the key to search for previous frompublic OrderedMapIterator<K,V> mapIterator()
IterableGetMapIterator over the map.
A map iterator is an efficient way of iterating over maps. There is no need to access the entry set or use Map Entry objects.
IterableMap<String,Integer> map = new HashedMap<String,Integer>();
MapIterator<String,Integer> it = map.mapIterator();
while (it.hasNext()) {
String key = it.next();
Integer value = it.getValue();
it.setValue(value + 1);
}
public java.util.SortedMap<K,V> prefixMap(K key)
TrieTrie 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'.
key - the key used in the searchSortedMap view of this Trie with all elements whose
key is prefixed by the search keypublic java.util.SortedMap<K,V> headMap(K toKey)
public java.util.SortedMap<K,V> subMap(K fromKey,
K toKey)
public java.util.SortedMap<K,V> tailMap(K fromKey)
Copyright © 2010 - 2020 Adobe. All Rights Reserved