abstract class AbstractPatriciaTrie<K,V> extends AbstractBitwiseTrie<K,V>
Map
interface.Modifier and Type | Class and Description |
---|---|
private class |
AbstractPatriciaTrie.EntrySet
This is a entry set view of the
Trie as returned by Map.entrySet() . |
private class |
AbstractPatriciaTrie.KeySet
This is a key set view of the
Trie as returned by Map.keySet() . |
private class |
AbstractPatriciaTrie.PrefixRangeEntrySet
A prefix
AbstractPatriciaTrie.RangeEntrySet view of the Trie . |
private class |
AbstractPatriciaTrie.PrefixRangeMap
A submap used for prefix views over the
Trie . |
private class |
AbstractPatriciaTrie.RangeEntryMap
A
AbstractPatriciaTrie.RangeMap that deals with Entry s. |
private class |
AbstractPatriciaTrie.RangeEntrySet
A
Set view of a AbstractPatriciaTrie.RangeMap . |
private class |
AbstractPatriciaTrie.RangeMap
A range view of the
Trie . |
private static class |
AbstractPatriciaTrie.Reference<E>
A
AbstractPatriciaTrie.Reference allows us to return something through a Method's
argument list. |
protected static class |
AbstractPatriciaTrie.TrieEntry<K,V>
A
Trie is a set of AbstractPatriciaTrie.TrieEntry nodes. |
(package private) class |
AbstractPatriciaTrie.TrieIterator<E>
An iterator for the entries.
|
private class |
AbstractPatriciaTrie.TrieMapIterator
An
OrderedMapIterator for a Trie . |
private class |
AbstractPatriciaTrie.Values
This is a value view of the
Trie as returned by Map.values() . |
AbstractBitwiseTrie.BasicEntry<K,V>
Modifier and Type | Field and Description |
---|---|
private java.util.Set<java.util.Map.Entry<K,V>> |
entrySet |
private java.util.Set<K> |
keySet
Each of these fields are initialized to contain an instance of the
appropriate view the first time this view is requested.
|
protected int |
modCount
The number of times this
Trie has been modified. |
private AbstractPatriciaTrie.TrieEntry<K,V> |
root
The root node of the
Trie . |
private static long |
serialVersionUID |
private int |
size
The current size of the
Trie . |
private java.util.Collection<V> |
values |
Modifier | Constructor and Description |
---|---|
protected |
AbstractPatriciaTrie(KeyAnalyzer<? super K> keyAnalyzer) |
protected |
AbstractPatriciaTrie(KeyAnalyzer<? super K> keyAnalyzer,
java.util.Map<? extends K,? extends V> map)
Constructs a new
org.apache.commons.collections4.Trie Trie
using the given KeyAnalyzer and initializes the Trie
with the values from the provided Map . |
Modifier and Type | Method and Description |
---|---|
(package private) AbstractPatriciaTrie.TrieEntry<K,V> |
addEntry(AbstractPatriciaTrie.TrieEntry<K,V> entry,
int lengthInBits)
Adds the given
AbstractPatriciaTrie.TrieEntry to the Trie . |
(package private) AbstractPatriciaTrie.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() |
java.util.Comparator<? super K> |
comparator() |
boolean |
containsKey(java.lang.Object k) |
(package private) void |
decrementSize()
A helper method to decrement the
Trie size and increment the modification counter. |
java.util.Set<java.util.Map.Entry<K,V>> |
entrySet() |
(package private) AbstractPatriciaTrie.TrieEntry<K,V> |
firstEntry()
Returns the first entry the
Trie is storing. |
K |
firstKey()
Gets the first key currently in this map.
|
(package private) AbstractPatriciaTrie.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.
|
(package private) AbstractPatriciaTrie.TrieEntry<K,V> |
followLeft(AbstractPatriciaTrie.TrieEntry<K,V> node)
Goes left through the tree until it finds a valid node.
|
(package private) AbstractPatriciaTrie.TrieEntry<K,V> |
followRight(AbstractPatriciaTrie.TrieEntry<K,V> node)
Traverses down the right path until it finds an uplink.
|
V |
get(java.lang.Object k) |
(package private) AbstractPatriciaTrie.TrieEntry<K,V> |
getEntry(java.lang.Object k)
Returns the entry associated with the specified key in the
PatriciaTrieBase.
|
(package private) AbstractPatriciaTrie.TrieEntry<K,V> |
getNearestEntryForKey(K key,
int lengthInBits)
Returns the nearest entry for a given key.
|
private java.util.SortedMap<K,V> |
getPrefixMapByBits(K key,
int offsetInBits,
int lengthInBits)
Returns a view of this
Trie of all elements that are prefixed
by the number of bits in the given Key. |
java.util.SortedMap<K,V> |
headMap(K toKey) |
(package private) AbstractPatriciaTrie.TrieEntry<K,V> |
higherEntry(K key)
Returns an entry strictly higher than the given key,
or null if no such entry exists.
|
private void |
incrementModCount()
A helper method to increment the modification counter.
|
(package private) void |
incrementSize()
A helper method to increment the
Trie size and the modification counter. |
(package private) static boolean |
isValidUplink(AbstractPatriciaTrie.TrieEntry<?,?> next,
AbstractPatriciaTrie.TrieEntry<?,?> from)
Returns true if 'next' is a valid uplink coming from 'from'.
|
java.util.Set<K> |
keySet() |
(package private) AbstractPatriciaTrie.TrieEntry<K,V> |
lastEntry()
Returns the last entry the
Trie is storing. |
K |
lastKey()
Gets the last key currently in this map.
|
(package private) AbstractPatriciaTrie.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.
|
OrderedMapIterator<K,V> |
mapIterator()
Obtains a
MapIterator over the map. |
(package private) AbstractPatriciaTrie.TrieEntry<K,V> |
nextEntry(AbstractPatriciaTrie.TrieEntry<K,V> node)
Returns the entry lexicographically after the given entry.
|
(package private) AbstractPatriciaTrie.TrieEntry<K,V> |
nextEntryImpl(AbstractPatriciaTrie.TrieEntry<K,V> start,
AbstractPatriciaTrie.TrieEntry<K,V> previous,
AbstractPatriciaTrie.TrieEntry<K,V> tree)
Scans for the next node, starting at the specified point, and using 'previous'
as a hint that the last node we returned was 'previous' (so we know not to return
it again).
|
(package private) AbstractPatriciaTrie.TrieEntry<K,V> |
nextEntryInSubtree(AbstractPatriciaTrie.TrieEntry<K,V> node,
AbstractPatriciaTrie.TrieEntry<K,V> parentOfSubtree)
Returns the entry lexicographically after the given entry.
|
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. |
(package private) AbstractPatriciaTrie.TrieEntry<K,V> |
previousEntry(AbstractPatriciaTrie.TrieEntry<K,V> start)
Returns the node lexicographically before the given node (or null if none).
|
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.
|
private void |
readObject(java.io.ObjectInputStream stream)
Reads the content of the stream.
|
V |
remove(java.lang.Object k) |
(package private) V |
removeEntry(AbstractPatriciaTrie.TrieEntry<K,V> h)
Removes a single entry from the
Trie . |
private void |
removeExternalEntry(AbstractPatriciaTrie.TrieEntry<K,V> h)
Removes an external entry from the
Trie . |
private void |
removeInternalEntry(AbstractPatriciaTrie.TrieEntry<K,V> h)
Removes an internal entry from the
Trie . |
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.
|
private boolean |
selectR(AbstractPatriciaTrie.TrieEntry<K,V> h,
int bitIndex,
K key,
int lengthInBits,
AbstractPatriciaTrie.Reference<java.util.Map.Entry<K,V>> reference)
This is equivalent to the other
#selectR(TrieEntry, int, Object, int, Cursor, Reference)
method but without its overhead because we're selecting only one best matching Entry from the Trie . |
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) |
(package private) AbstractPatriciaTrie.TrieEntry<K,V> |
subtree(K prefix,
int offsetInBits,
int lengthInBits)
Finds the subtree that contains the prefix.
|
java.util.SortedMap<K,V> |
tailMap(K fromKey) |
java.util.Collection<V> |
values() |
private void |
writeObject(java.io.ObjectOutputStream stream)
Writes the content to the stream for serialization.
|
bitIndex, bitsPerElement, castKey, compare, compareKeys, getKeyAnalyzer, isBitSet, lengthInBits, toString
clone, containsValue, equals, hashCode, isEmpty, putAll
finalize, getClass, notify, notifyAll, wait, wait, wait
compute, computeIfAbsent, computeIfPresent, containsValue, equals, forEach, getOrDefault, hashCode, isEmpty, merge, putAll, putIfAbsent, remove, replace, replace, replaceAll
containsValue, isEmpty
private static final long serialVersionUID
private transient AbstractPatriciaTrie.TrieEntry<K,V> root
Trie
.private transient volatile java.util.Set<K> keySet
private transient volatile java.util.Collection<V> values
private transient int size
Trie
.protected transient int modCount
Trie
has been modified.
It's used to detect concurrent modifications and fail-fast the Iterator
s.protected AbstractPatriciaTrie(KeyAnalyzer<? super K> keyAnalyzer)
protected AbstractPatriciaTrie(KeyAnalyzer<? super K> keyAnalyzer, java.util.Map<? extends K,? extends V> map)
org.apache.commons.collections4.Trie Trie
using the given KeyAnalyzer
and initializes the Trie
with the values from the provided Map
.public void clear()
public int size()
void incrementSize()
Trie
size and the modification counter.void decrementSize()
Trie
size and increment the modification counter.private void incrementModCount()
public V put(K key, V value)
Put
put
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)
AbstractPatriciaTrie.TrieEntry<K,V> addEntry(AbstractPatriciaTrie.TrieEntry<K,V> entry, int lengthInBits)
AbstractPatriciaTrie.TrieEntry
to the Trie
.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)
AbstractPatriciaTrie.TrieEntry<K,V> getEntry(java.lang.Object k)
This may throw ClassCastException if the object is not of type 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 searchprivate boolean selectR(AbstractPatriciaTrie.TrieEntry<K,V> h, int bitIndex, K key, int lengthInBits, AbstractPatriciaTrie.Reference<java.util.Map.Entry<K,V>> reference)
#selectR(TrieEntry, int, Object, int, Cursor, Reference)
method but without its overhead because we're selecting only one best matching Entry from the Trie
.public 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)
AbstractPatriciaTrie.TrieEntry<K,V> getNearestEntryForKey(K key, int lengthInBits)
V removeEntry(AbstractPatriciaTrie.TrieEntry<K,V> h)
Trie
.
If we found a Key (Entry h) then figure out if it's
an internal (hard to remove) or external Entry (easy
to remove)private void removeExternalEntry(AbstractPatriciaTrie.TrieEntry<K,V> h)
Trie
.
If it's an external Entry then just remove it.
This is very easy and straight forward.private void removeInternalEntry(AbstractPatriciaTrie.TrieEntry<K,V> h)
Trie
.
If it's an internal Entry then "good luck" with understanding
this code. The Idea is essentially that Entry p takes Entry h's
place in the trie which requires some re-wiring.AbstractPatriciaTrie.TrieEntry<K,V> nextEntry(AbstractPatriciaTrie.TrieEntry<K,V> node)
AbstractPatriciaTrie.TrieEntry<K,V> nextEntryImpl(AbstractPatriciaTrie.TrieEntry<K,V> start, AbstractPatriciaTrie.TrieEntry<K,V> previous, AbstractPatriciaTrie.TrieEntry<K,V> tree)
AbstractPatriciaTrie.TrieEntry<K,V> firstEntry()
Trie
is storing.
This is implemented by going always to the left until we encounter a valid uplink. That uplink is the first key.
AbstractPatriciaTrie.TrieEntry<K,V> followLeft(AbstractPatriciaTrie.TrieEntry<K,V> node)
public java.util.Comparator<? super K> comparator()
public K firstKey()
OrderedMap
public K lastKey()
OrderedMap
public K nextKey(K key)
OrderedMap
key
- the key to search for next frompublic K previousKey(K key)
OrderedMap
key
- the key to search for previous frompublic 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.
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)
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'.
key
- the key used in the searchSortedMap
view of this Trie
with all elements whose
key is prefixed by the search keyprivate java.util.SortedMap<K,V> getPrefixMapByBits(K key, int offsetInBits, int lengthInBits)
Trie
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.firstKey()
,
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.
key
- the key to use in the searchoffsetInBits
- the prefix offsetlengthInBits
- the number of significant prefix bitsSortedMap
view of this Trie
with all elements whose
key is prefixed by the search keyAbstractPatriciaTrie.TrieEntry<K,V> higherEntry(K key)
AbstractPatriciaTrie.TrieEntry<K,V> ceilingEntry(K key)
AbstractPatriciaTrie.TrieEntry<K,V> lowerEntry(K key)
AbstractPatriciaTrie.TrieEntry<K,V> floorEntry(K key)
AbstractPatriciaTrie.TrieEntry<K,V> subtree(K prefix, int offsetInBits, int lengthInBits)
AbstractPatriciaTrie.TrieEntry<K,V> lastEntry()
Trie
is storing.
This is implemented by going always to the right until we encounter a valid uplink. That uplink is the last key.
AbstractPatriciaTrie.TrieEntry<K,V> followRight(AbstractPatriciaTrie.TrieEntry<K,V> node)
AbstractPatriciaTrie.TrieEntry<K,V> previousEntry(AbstractPatriciaTrie.TrieEntry<K,V> start)
start
- the start entryAbstractPatriciaTrie.TrieEntry<K,V> nextEntryInSubtree(AbstractPatriciaTrie.TrieEntry<K,V> node, AbstractPatriciaTrie.TrieEntry<K,V> parentOfSubtree)
static boolean isValidUplink(AbstractPatriciaTrie.TrieEntry<?,?> next, AbstractPatriciaTrie.TrieEntry<?,?> from)
private void readObject(java.io.ObjectInputStream stream) throws java.io.IOException, java.lang.ClassNotFoundException
java.io.IOException
java.lang.ClassNotFoundException
private void writeObject(java.io.ObjectOutputStream stream) throws java.io.IOException
java.io.IOException