|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectjava.util.AbstractMap<K,V>
org.apache.commons.collections4.trie.AbstractBitwiseTrie<K,V>
org.apache.commons.collections4.trie.PatriciaTrie<E>
public class PatriciaTrie<E>
Implementation of a 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
'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.
Nested Class Summary | |
---|---|
protected static class |
AbstractPatriciaTrie.TrieEntry<K,V>
A Trie is a set of AbstractPatriciaTrie.TrieEntry nodes. |
Field Summary | |
---|---|
protected int |
modCount
The number of times this Trie has been modified. |
Constructor Summary | |
---|---|
PatriciaTrie()
|
|
PatriciaTrie(Map<? extends String,? extends E> m)
|
Method Summary | |
---|---|
void |
clear()
|
Comparator<? super K> |
comparator()
|
boolean |
containsKey(Object k)
|
Set<Map.Entry<K,V>> |
entrySet()
|
K |
firstKey()
Gets the first key currently in this map. |
V |
get(Object k)
|
int |
hashCode()
Gets the standard Map hashCode. |
SortedMap<K,V> |
headMap(K toKey)
|
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. |
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(Object k)
|
Map.Entry<K,V> |
select(K key)
Returns the AbstractPatriciaTrie.TrieEntry 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()
|
SortedMap<K,V> |
subMap(K fromKey,
K toKey)
|
SortedMap<K,V> |
tailMap(K fromKey)
|
Collection<V> |
values()
|
Methods inherited from class org.apache.commons.collections4.trie.AbstractBitwiseTrie |
---|
getKeyAnalyzer, toString |
Methods inherited from class java.util.AbstractMap |
---|
clone, containsValue, equals, isEmpty, putAll, size |
Methods inherited from class java.lang.Object |
---|
finalize, getClass, notify, notifyAll, wait, wait, wait |
Methods inherited from interface org.apache.commons.collections4.Trie |
---|
prefixMap |
Methods inherited from interface java.util.SortedMap |
---|
comparator, firstKey, headMap, lastKey, subMap, tailMap |
Methods inherited from interface org.apache.commons.collections4.OrderedMap |
---|
firstKey, lastKey, mapIterator, nextKey, previousKey |
Methods inherited from interface org.apache.commons.collections4.Put |
---|
clear, put, putAll |
Methods inherited from interface org.apache.commons.collections4.Get |
---|
containsKey, containsValue, entrySet, get, isEmpty, keySet, remove, size, values |
Field Detail |
---|
protected transient int modCount
Trie
has been modified.
It's used to detect concurrent modifications and fail-fast the Iterator
s.
Constructor Detail |
---|
public PatriciaTrie()
public PatriciaTrie(Map<? extends String,? extends E> m)
Method Detail |
---|
public void clear()
clear
in interface Map<K,V>
clear
in interface Put<K,V>
clear
in class AbstractMap<K,V>
Map.clear()
public int size()
size
in interface Map<K,V>
size
in interface Get<K,V>
size
in class AbstractMap<K,V>
Map.size()
public V put(K key, V value)
Put
put
in interface Map<K,V>
put
in interface Put<K,V>
put
in class AbstractMap<K,V>
Map.put(Object, Object)
public V get(Object k)
get
in interface Map<K,V>
get
in interface Get<K,V>
get
in class AbstractMap<K,V>
Map.get(Object)
public Map.Entry<K,V> select(K key)
AbstractPatriciaTrie.TrieEntry
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 search
AbstractPatriciaTrie.TrieEntry
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 search
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.
key
- the key to use in the search
public boolean containsKey(Object k)
containsKey
in interface Map<K,V>
containsKey
in interface Get<K,V>
containsKey
in class AbstractMap<K,V>
Map.containsKey(Object)
public Set<Map.Entry<K,V>> entrySet()
entrySet
in interface Map<K,V>
entrySet
in interface Get<K,V>
entrySet
in class AbstractMap<K,V>
Map.entrySet()
public Set<K> keySet()
keySet
in interface Map<K,V>
keySet
in interface Get<K,V>
keySet
in class AbstractMap<K,V>
Map.keySet()
public Collection<V> values()
values
in interface Map<K,V>
values
in interface Get<K,V>
values
in class AbstractMap<K,V>
Map.values()
public V remove(Object k)
remove
in interface Map<K,V>
remove
in interface Get<K,V>
remove
in class AbstractMap<K,V>
ClassCastException
- if provided key is of an incompatible typeMap.remove(Object)
public int hashCode()
hashCode
in interface Map<K,V>
hashCode
in class AbstractMap<K,V>
public Comparator<? super K> comparator()
comparator
in interface SortedMap<K,V>
public K firstKey()
OrderedMap
firstKey
in interface SortedMap<K,V>
firstKey
in interface OrderedMap<K,V>
public K lastKey()
OrderedMap
lastKey
in interface 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 from
public K previousKey(K key)
OrderedMap
previousKey
in interface OrderedMap<K,V>
key
- the key to search for previous from
public OrderedMapIterator<K,V> mapIterator()
IterableGet
MapIterator
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.
IterableMapmap = new HashedMap (); MapIterator it = map.mapIterator(); while (it.hasNext()) { String key = it.next(); Integer value = it.getValue(); it.setValue(value + 1); }
mapIterator
in interface IterableGet<K,V>
mapIterator
in interface OrderedMap<K,V>
public 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'.
prefixMap
in interface Trie<K,V>
key
- the key used in the search
SortedMap
view of this Trie
with all elements whose
key is prefixed by the search keypublic SortedMap<K,V> headMap(K toKey)
headMap
in interface SortedMap<K,V>
public SortedMap<K,V> subMap(K fromKey, K toKey)
subMap
in interface SortedMap<K,V>
public SortedMap<K,V> tailMap(K fromKey)
tailMap
in interface SortedMap<K,V>
|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |