Class AbstractPatriciaTrie<K,V>
- All Implemented Interfaces:
Serializable
,Map<K,
,V> SortedMap<K,
,V> Get<K,
,V> IterableGet<K,
,V> IterableMap<K,
,V> IterableSortedMap<K,
,V> OrderedMap<K,
,V> Put<K,
,V> Trie<K,
V>
- Direct Known Subclasses:
PatriciaTrie
Map
interface.- Since:
- 4.0
-
Nested Class Summary
Nested ClassesModifier and TypeClassDescriptionprivate class
This is a entry set view of theinvalid reference
Trie
Map.entrySet()
.private class
This is a key set view of theinvalid reference
Trie
Map.keySet()
.private final class
A prefixAbstractPatriciaTrie<K,
view of theV>.RangeEntrySet invalid reference
Trie
private class
A submap used for prefix views over theinvalid reference
Trie
private class
AAbstractPatriciaTrie<K,
that deals withV>.RangeMap Map.Entry
s.private class
ASet
view of aAbstractPatriciaTrie<K,
.V>.RangeMap private class
A range view of theinvalid reference
Trie
private static class
AAbstractPatriciaTrie.Reference
allows us to return something through a Method's argument list.protected static class
ATrie
is a set ofAbstractPatriciaTrie.TrieEntry
nodes.(package private) class
An iterator for the entries.private class
AnOrderedMapIterator
for ainvalid reference
Trie
private class
This is a value view of theinvalid reference
Trie
Map.values()
.Nested classes/interfaces inherited from class org.apache.commons.collections4.trie.AbstractBitwiseTrie
AbstractBitwiseTrie.BasicEntry<K,
V> Nested classes/interfaces inherited from class java.util.AbstractMap
AbstractMap.SimpleEntry<K,
V>, AbstractMap.SimpleImmutableEntry<K, V> -
Field Summary
FieldsModifier and TypeFieldDescriptionEach of these fields are initialized to contain an instance of the appropriate view the first time this view is requested.protected int
The number of times thisTrie
has been modified.private AbstractPatriciaTrie.TrieEntry
<K, V> The root node of theTrie
.private static final long
private int
The current size of theTrie
.private Collection
<V> -
Constructor Summary
ConstructorsModifierConstructorDescriptionprotected
AbstractPatriciaTrie
(KeyAnalyzer<? super K> keyAnalyzer) protected
AbstractPatriciaTrie
(KeyAnalyzer<? super K> keyAnalyzer, Map<? extends K, ? extends V> map) Constructs a neworg.apache.commons.collections4.Trie Trie
using the givenKeyAnalyzer
and initializes theTrie
with the values from the providedMap
. -
Method Summary
Modifier and TypeMethodDescription(package private) AbstractPatriciaTrie.TrieEntry
<K, V> addEntry
(AbstractPatriciaTrie.TrieEntry<K, V> entry, int lengthInBits) Adds the givenAbstractPatriciaTrie.TrieEntry
to theinvalid reference
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()
Comparator
<? super K> boolean
(package private) void
A helper method to decrement theinvalid reference
Trie
entrySet()
(package private) AbstractPatriciaTrie.TrieEntry
<K, V> Returns the first entry theinvalid reference
Trie
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> Goes left through the tree until it finds a valid node.(package private) AbstractPatriciaTrie.TrieEntry
<K, V> Traverses down the right path until it finds an uplink.(package private) AbstractPatriciaTrie.TrieEntry
<K, V> 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.getPrefixMapByBits
(K key, int offsetInBits, int lengthInBits) Returns a view of thisinvalid reference
Trie
(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
A helper method to increment the modification counter.(package private) void
A helper method to increment theinvalid reference
Trie
(package private) static boolean
isValidUplink
(AbstractPatriciaTrie.TrieEntry<?, ?> next, AbstractPatriciaTrie.TrieEntry<?, ?> from) Returns true if 'next' is a valid uplink coming from 'from'.keySet()
(package private) AbstractPatriciaTrie.TrieEntry
<K, V> Returns the last entry theinvalid reference
Trie
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.Obtains anOrderedMapIterator
over the map.(package private) AbstractPatriciaTrie.TrieEntry
<K, V> 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.Gets the next key after the one specified.Returns a view of thisTrie
of all elements that are prefixed by the given key.(package private) AbstractPatriciaTrie.TrieEntry
<K, V> Returns the node lexicographically before the given node (or null if none).previousKey
(K key) Gets the previous key before the one specified.Note that the return type is Object, rather than V as in the Map interface.private void
readObject
(ObjectInputStream stream) Reads the content of the stream.(package private) V
Removes a single entry from theinvalid reference
Trie
private void
Removes an external entry from theinvalid reference
Trie
private void
Removes an internal entry from theinvalid reference
Trie
Returns theMap.Entry
whose key is closest in a bitwise XOR metric to the given 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<Map.Entry<K, V>> reference) This is equivalent to the otherinvalid reference
#selectR(TrieEntry, int, Object, int, Cursor, Reference)
invalid reference
Trie
selectValue
(K key) Returns the value whose key is closest in a bitwise XOR metric to the provided key.int
size()
(package private) AbstractPatriciaTrie.TrieEntry
<K, V> Finds the subtree that contains the prefix.values()
private void
writeObject
(ObjectOutputStream stream) Writes the content to the stream for serialization.Methods inherited from class org.apache.commons.collections4.trie.AbstractBitwiseTrie
bitIndex, bitsPerElement, castKey, compare, compareKeys, getKeyAnalyzer, isBitSet, lengthInBits, toString
Methods inherited from class java.util.AbstractMap
clone, containsValue, equals, hashCode, isEmpty, putAll
Methods inherited from class java.lang.Object
finalize, getClass, notify, notifyAll, wait, wait, wait
Methods inherited from interface org.apache.commons.collections4.Get
containsValue, isEmpty
Methods inherited from interface java.util.Map
compute, computeIfAbsent, computeIfPresent, containsValue, equals, forEach, getOrDefault, hashCode, isEmpty, merge, putAll, putIfAbsent, remove, replace, replace, replaceAll
-
Field Details
-
serialVersionUID
private static final long serialVersionUID- See Also:
-
root
The root node of theTrie
. -
keySet
Each of these fields are initialized to contain an instance of the appropriate view the first time this view is requested. The views are stateless, so there's no reason to create more than one of each. -
values
-
entrySet
-
size
private transient int sizeThe current size of theTrie
. -
modCount
protected transient int modCount
-
-
Constructor Details
-
AbstractPatriciaTrie
-
AbstractPatriciaTrie
protected AbstractPatriciaTrie(KeyAnalyzer<? super K> keyAnalyzer, Map<? extends K, ? extends V> map) Constructs a neworg.apache.commons.collections4.Trie Trie
using the givenKeyAnalyzer
and initializes theTrie
with the values from the providedMap
.
-
-
Method Details
-
clear
public void clear() -
size
public int size() -
incrementSize
void incrementSize()A helper method to increment theinvalid reference
Trie
-
decrementSize
void decrementSize()A helper method to decrement theinvalid reference
Trie
-
incrementModCount
private void incrementModCount()A helper method to increment the modification counter. -
put
Description copied from interface:Put
Note that the return type is Object, rather than V as in the Map interface. See the class Javadoc for further info.- Specified by:
put
in interfaceMap<K,
V> - Specified by:
put
in interfacePut<K,
V> - Overrides:
put
in classAbstractMap<K,
V> - Parameters:
key
- key with which the specified value is to be associatedvalue
- value to be associated with the specified key- Returns:
- the previous value associated with
key
, ornull
if there was no mapping forkey
. (Anull
return can also indicate that the map previously associatednull
withkey
, if the implementation supportsnull
values.) - See Also:
-
addEntry
AbstractPatriciaTrie.TrieEntry<K,V> addEntry(AbstractPatriciaTrie.TrieEntry<K, V> entry, int lengthInBits) Adds the givenAbstractPatriciaTrie.TrieEntry
to theinvalid reference
Trie
-
get
- Specified by:
get
in interfaceGet<K,
V> - Specified by:
get
in interfaceMap<K,
V> - Overrides:
get
in classAbstractMap<K,
V> - Parameters:
k
- the key whose associated value is to be returned- Returns:
- the value to which the specified key is mapped, or
null
if this map contains no mapping for the key - See Also:
-
getEntry
Returns the entry associated with the specified key in the PatriciaTrieBase. Returns null if the map contains no mapping for this key.This may throw ClassCastException if the object is not of type K.
-
select
Returns theMap.Entry
whose key is closest in a bitwise XOR metric to the given key. This is NOT lexicographic closeness. For example, given the keys:- D = 1000100
- H = 1001000
- L = 1001100
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.- Parameters:
key
- the key to use in the search- Returns:
- the
Map.Entry
whose key is closest in a bitwise XOR metric to the provided key
-
selectKey
Returns the key that is closest in a bitwise XOR metric to the provided key. This is NOT lexicographic closeness! For example, given the keys:- D = 1000100
- H = 1001000
- L = 1001100
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.- Parameters:
key
- the key to use in the search- Returns:
- the key that is closest in a bitwise XOR metric to the provided key
-
selectValue
Returns the value whose key is closest in a bitwise XOR metric to the provided key. This is NOT lexicographic closeness! For example, given the keys:- D = 1000100
- H = 1001000
- L = 1001100
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.- Parameters:
key
- the key to use in the search- Returns:
- the value whose key is closest in a bitwise XOR metric to the provided key
-
selectR
private boolean selectR(AbstractPatriciaTrie.TrieEntry<K, V> h, int bitIndex, K key, int lengthInBits, AbstractPatriciaTrie.Reference<Map.Entry<K, V>> reference) This is equivalent to the otherinvalid reference
#selectR(TrieEntry, int, Object, int, Cursor, Reference)
invalid reference
Trie
-
containsKey
- Specified by:
containsKey
in interfaceGet<K,
V> - Specified by:
containsKey
in interfaceMap<K,
V> - Overrides:
containsKey
in classAbstractMap<K,
V> - Parameters:
k
- key whose presence in this map is to be tested- Returns:
true
if this map contains a mapping for the specified key- See Also:
-
entrySet
-
keySet
-
values
-
remove
- Specified by:
remove
in interfaceGet<K,
V> - Specified by:
remove
in interfaceMap<K,
V> - Overrides:
remove
in classAbstractMap<K,
V> - Parameters:
k
- key whose mapping is to be removed from the map- Returns:
- the previous value associated with
key
, ornull
if there was no mapping forkey
. - Throws:
ClassCastException
- if provided key is of an incompatible type- See Also:
-
getNearestEntryForKey
Returns the nearest entry for a given key. This is useful for finding knowing if a given key exists (and finding the value for it), or for inserting the key. The actual get implementation. This is very similar to selectR but with the exception that it might return the root Entry even if it's empty. -
removeEntry
Removes a single entry from theinvalid reference
Trie
-
removeExternalEntry
Removes an external entry from theinvalid reference
Trie
-
removeInternalEntry
Removes an internal entry from theinvalid reference
Trie
-
nextEntry
Returns the entry lexicographically after the given entry. If the given entry is null, returns the first node. -
nextEntryImpl
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). If 'tree' is non-null, this will limit the search to the given tree. The basic premise is that each iteration can follow the following steps: 1) Scan all the way to the left. a) If we already started from this node last time, proceed to Step 2. b) If a valid uplink is found, use it. c) If the result is an empty node (root not set), break the scan. d) If we already returned the left node, break the scan. 2) Check the right. a) If we already returned the right node, proceed to Step 3. b) If it is a valid uplink, use it. c) Do Step 1 from the right node. 3) Back up through the parents until we encounter find a parent that we're not the right child of. 4) If there's no right child of that parent, the iteration is finished. Otherwise continue to Step 5. 5) Check to see if the right child is a valid uplink. a) If we already returned that child, proceed to Step 6. Otherwise, use it. 6) If the right child of the parent is the parent itself, we've already found invalid input: '&' returned the end of the Trie, so exit. 7) Do Step 1 on the parent's right child. -
firstEntry
AbstractPatriciaTrie.TrieEntry<K,V> firstEntry()Returns the first entry theinvalid reference
Trie
This is implemented by going always to the left until we encounter a valid uplink. That uplink is the first key.
-
followLeft
Goes left through the tree until it finds a valid node. -
comparator
-
firstKey
Description copied from interface:OrderedMap
Gets the first key currently in this map.- Returns:
- the first key currently in this map
-
lastKey
Description copied from interface:OrderedMap
Gets the last key currently in this map.- Returns:
- the last key currently in this map
-
nextKey
Description copied from interface:OrderedMap
Gets the next key after the one specified.- Parameters:
key
- the key to search for next from- Returns:
- the next key, null if no match or at end
-
previousKey
Description copied from interface:OrderedMap
Gets the previous key before the one specified.- Parameters:
key
- the key to search for previous from- Returns:
- the previous key, null if no match or at start
-
mapIterator
Description copied from interface:OrderedMap
Obtains anOrderedMapIterator
over the map.A ordered map iterator is an efficient way of iterating over maps in both directions.
- Returns:
- a map iterator
-
prefixMap
Description copied from interface:Trie
Returns a view of thisTrie
of all elements that are prefixed by the given key.In a
Trie
with fixed size keys, this is essentially aMap.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'. -
getPrefixMapByBits
Returns a view of thisinvalid reference
Trie
The view that this returns is optimized to have a very efficient
Iterator
. TheSortedMap.firstKey()
,SortedMap.lastKey()
&Map.size()
methods must iterate over all possible values in order to determine the results. This information is cached until the PATRICIAinvalid reference
Trie
Iterator
) must compare the given key to the prefix to ensure that it is within the range of the view. TheIterator
'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.- Parameters:
key
- the key to use in the searchoffsetInBits
- the prefix offsetlengthInBits
- the number of significant prefix bits- Returns:
- a
SortedMap
view of thisinvalid reference
Trie
-
headMap
-
subMap
-
tailMap
-
higherEntry
Returns an entry strictly higher than the given key, or null if no such entry exists. -
ceilingEntry
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. -
lowerEntry
Returns a key-value mapping associated with the greatest key strictly less than the given key, or null if there is no such key. -
floorEntry
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. -
subtree
Finds the subtree that contains the prefix. This is very similar to getR but with the difference that we stop the lookup if h.bitIndex > lengthInBits. -
lastEntry
AbstractPatriciaTrie.TrieEntry<K,V> lastEntry()Returns the last entry theinvalid reference
Trie
This is implemented by going always to the right until we encounter a valid uplink. That uplink is the last key.
-
followRight
Traverses down the right path until it finds an uplink. -
previousEntry
Returns the node lexicographically before the given node (or null if none). This follows four simple branches: - If the uplink that returned us was a right uplink: - If predecessor's left is a valid uplink from predecessor, return it. - Else, follow the right path from the predecessor's left. - If the uplink that returned us was a left uplink: - Loop back through parents until we encounter a node where node != node.parent.left. - If node.parent.left is uplink from node.parent: - If node.parent.left is not root, return it. - If it is root invalid input: '&' root isEmpty, return null. - If it is root invalid input: '&' root !isEmpty, return root. - If node.parent.left is not uplink from node.parent: - Follow right path for first right child from node.parent.left- Parameters:
start
- the start entry
-
nextEntryInSubtree
AbstractPatriciaTrie.TrieEntry<K,V> nextEntryInSubtree(AbstractPatriciaTrie.TrieEntry<K, V> node, AbstractPatriciaTrie.TrieEntry<K, V> parentOfSubtree) Returns the entry lexicographically after the given entry. If the given entry is null, returns the first node. This will traverse only within the subtree. If the given node is not within the subtree, this will have undefined results. -
isValidUplink
static boolean isValidUplink(AbstractPatriciaTrie.TrieEntry<?, ?> next, AbstractPatriciaTrie.TrieEntry<?, ?> from) Returns true if 'next' is a valid uplink coming from 'from'. -
readObject
Reads the content of the stream.- Throws:
IOException
ClassNotFoundException
-
writeObject
Writes the content to the stream for serialization.- Throws:
IOException
-