Class AbstractPatriciaTrie<K,V>
java.lang.Object
java.util.AbstractMap<K,V>
org.apache.commons.collections4.trie.AbstractBitwiseTrie<K,V>
org.apache.commons.collections4.trie.AbstractPatriciaTrie<K,V>
- Type Parameters:
K- the type of the keys in this mapV- the type of the values in this map
- 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
This class implements the base PATRICIA algorithm and everything that
is related to the
Map interface.- Since:
- 4.0
- See Also:
-
Nested Class Summary
Nested ClassesModifier and TypeClassDescriptionprotected static classATrieis a set ofAbstractPatriciaTrie.TrieEntrynodes.Nested classes/interfaces inherited from class java.util.AbstractMap
AbstractMap.SimpleEntry<K,V>, AbstractMap.SimpleImmutableEntry<K, V> -
Field Summary
Fields -
Constructor Summary
ConstructorsModifierConstructorDescriptionprotectedAbstractPatriciaTrie(KeyAnalyzer<? super K> keyAnalyzer) Constructs a newTrieusing the givenKeyAnalyzer.protectedAbstractPatriciaTrie(KeyAnalyzer<? super K> keyAnalyzer, Map<? extends K, ? extends V> map) Constructs a newTrieusing the givenKeyAnalyzerand initializes theTriewith the values from the providedMap. -
Method Summary
Modifier and TypeMethodDescriptionvoidclear()Removes all of the mappings from this map.Comparator<? super K> booleanTests for presence of a given key.entrySet()Gets a set view of the mappings contained in this map.firstKey()Gets the first key currently in this map.Gets a value at a given key.keySet()Gets a view of the keys contained in this map.lastKey()Gets the last key currently in this map.Obtains anOrderedMapIteratorover the map.Gets the next key after the one specified.Returns a view of thisTrieof all elements that are prefixed by the given key.previousKey(K key) Gets the previous key before the one specified.Associates the specified value with the specified key in this map.Remove a key-value mappings.Returns theMap.Entrywhose 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.selectValue(K key) Returns the value whose key is closest in a bitwise XOR metric to the provided key.intsize()Gets the number of key-value mappings in this map.values()Gets a a collection view of the values contained in this map.Methods inherited from class org.apache.commons.collections4.trie.AbstractBitwiseTrie
getKeyAnalyzer, toStringMethods inherited from class java.util.AbstractMap
clone, containsValue, equals, hashCode, isEmpty, putAllMethods inherited from class java.lang.Object
finalize, getClass, notify, notifyAll, wait, wait, waitMethods inherited from interface org.apache.commons.collections4.Get
containsValue, isEmptyMethods inherited from interface java.util.Map
compute, computeIfAbsent, computeIfPresent, containsValue, equals, forEach, getOrDefault, hashCode, isEmpty, merge, putAll, putIfAbsent, remove, replace, replace, replaceAll
-
Field Details
-
modCount
-
-
Constructor Details
-
AbstractPatriciaTrie
Constructs a newTrieusing the givenKeyAnalyzer.- Parameters:
keyAnalyzer- theKeyAnalyzer.
-
AbstractPatriciaTrie
protected AbstractPatriciaTrie(KeyAnalyzer<? super K> keyAnalyzer, Map<? extends K, ? extends V> map) Constructs a newTrieusing the givenKeyAnalyzerand initializes theTriewith the values from the providedMap.- Parameters:
keyAnalyzer- theKeyAnalyzer.map- The source map.
-
-
Method Details
-
clear
-
comparator
-
containsKey
Description copied from interface:GetTests for presence of a given key.- Specified by:
containsKeyin interfaceGet<K,V> - Specified by:
containsKeyin interfaceMap<K,V> - Overrides:
containsKeyin classAbstractMap<K,V> - Parameters:
k- key whose presence in this map is to be tested- Returns:
trueif this map contains a mapping for the specified key- See Also:
-
entrySet
Description copied from interface:GetGets a set view of the mappings contained in this map. -
firstKey
Description copied from interface:OrderedMapGets the first key currently in this map.- Returns:
- the first key currently in this map
-
get
Description copied from interface:GetGets a value at a given key.- Specified by:
getin interfaceGet<K,V> - Specified by:
getin interfaceMap<K,V> - Overrides:
getin 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
nullif this map contains no mapping for the key - See Also:
-
headMap
-
keySet
Description copied from interface:GetGets a view of the keys contained in this map. -
lastKey
Description copied from interface:OrderedMapGets the last key currently in this map.- Returns:
- the last key currently in this map
-
mapIterator
Description copied from interface:OrderedMapObtains anOrderedMapIteratorover the map.An ordered map iterator is an efficient way of iterating over maps in both directions.
- Returns:
- a map iterator
-
nextKey
Description copied from interface:OrderedMapGets 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
-
prefixMap
Description copied from interface:TrieReturns a view of thisTrieof all elements that are prefixed by the given key.In a
Triewith fixed size keys, this is essentially aMap.get(Object)operation.For example, if the
Triecontains 'Anna', 'Anael', 'Analu', 'Andreas', 'Andrea', 'Andres', and 'Anatole', then a lookup of 'And' would return 'Andreas', 'Andrea', and 'Andres'. -
previousKey
Description copied from interface:OrderedMapGets 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
-
put
Description copied from interface:PutAssociates the specified value with the specified key in this map.Note that the return type is Object, rather than V as in the Map interface. See the class Javadoc for further info.
- Specified by:
putin interfaceMap<K,V> - Specified by:
putin interfacePut<K,V> - Overrides:
putin 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, ornullif there was no mapping forkey. (Anullreturn can also indicate that the map previously associatednullwithkey, if the implementation supportsnullvalues.) - See Also:
-
remove
Remove a key-value mappings.- Specified by:
removein interfaceGet<K,V> - Specified by:
removein interfaceMap<K,V> - Overrides:
removein classAbstractMap<K,V> - Parameters:
k- key whose mapping is to be removed from the map- Returns:
- the previous value associated with
key, ornullif there was no mapping forkey. - Throws:
ClassCastException- if provided key is of an incompatible type- See Also:
-
select
Returns theMap.Entrywhose 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
Triecontained '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.Entrywhose 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
Triecontained '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
Triecontained '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
-
size
-
subMap
-
tailMap
-
values
Description copied from interface:GetGets a a collection view of the values contained in this map.
-