- Type Parameters:
K
- the address typeV
- the type of the mapped values
- All Implemented Interfaces:
Serializable
,Cloneable
,Map<K,
,V> NavigableMap<K,
,V> SequencedMap<K,
,V> SortedMap<K,
V>
AssociativeAddressTrie
to view it as a Java Collections Framework map,
implementing the Map
, SortedMap
, and NavigableMap
interfaces.
Like TreeMap
, this map is backed by a binary tree and implements the same interfaces that TreeMap
does.
But there are some significant differences between the two binary tree implementations.
A trie is naturally balanced and can only reach a depth corresponding to the number of bits in the keys, which is 32 for IPv4 and 128 for IPv6 tries. The TreeMap is balanced using red-black balancing.
The AssociativeAddressTrie
allows you to modify the map entries using Map.Entry.setValue(Object)
,
while TreeMap
does not. The entries provided by the TreeMap
are copies of the original nodes,
so that the original nodes can be re-purposed. The nodes are not exposed.
In the AssociativeAddressTrie
nodes are not re-purposed, and in fact they are also exposed.
This enables navigation through the nodes.
The node hierarchy has a special meaning, there is only one hierarchy for any given set of addresses,
since it is determined by prefix block subnet containment. The hierarchy enables certain address-specific containment-based operations,
such as subnet deletion or containment checks.
In the trie map, when doing lookups and some other operations, only parts of the address keys are examined at each node in the binary tree search,
rather than comparisons of the whole key, as with TreeMap
.
The trie map supports only the one comparison representing subnet containment, which is based on bit values and prefix length.
The TreeMap is a general-purpose map supporting any natural ordering or Comparator.
With the trie map, only addresses that are either individual address or prefix block subnets of the same type and version can be added to the trie,
see AddressTrie.AddressComparator
for a comparator for the ordering.
Should you wish to store, in a map, address instances that are not individual address or prefix block subnets,
you can use TreeMap
or any other Java collections framework map to store addresses of any type,
or addresses of different versions or types in the same map,
since all address items in this library are comparable with a natural ordering.
There are additional orderings provided by this library as well, see AddressComparator
.
- Author:
- scfoley
- See Also:
-
Nested Class Summary
Nested ClassesNested classes/interfaces inherited from class java.util.AbstractMap
AbstractMap.SimpleEntry<K,
V>, AbstractMap.SimpleImmutableEntry<K, V> -
Constructor Summary
ConstructorsConstructorDescriptionAddressTrieMap
(AssociativeAddressTrie<K, V> trie) AddressTrieMap
(AssociativeAddressTrie<K, V> trie, Map<? extends K, ? extends V> map) -
Method Summary
Modifier and TypeMethodDescriptionasTrie()
Return a trie representing this map.ceilingEntry
(K key) ceilingKey
(K key) void
clear()
clone()
Clones the map along with the backing trie.computeIfAbsent
(K key, Function<? super K, ? extends V> remappingFunction) computeIfPresent
(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) boolean
containsKey
(Object key) boolean
containsValue
(Object value) entrySet()
boolean
firstKey()
floorEntry
(K key) void
forEach
(BiConsumer<? super K, ? super V> action) getOrDefault
(Object key, V defaultValue) getRange()
Returns the range if this map has a restricted range, seehasRestrictedRange()
.int
hashCode()
boolean
Returns whether this map is the result of a call toheadMap(Address)
,tailMap(Address)
,subMap(Address, Address)
or any of the other methods with the same names.higherEntry
(K key) boolean
isEmpty()
boolean
keyContains
(K addr) Returns true if a subnet or address key in the map contains the given subnet or address.keySet()
lastKey()
longestPrefixMatchEntry
(K addr) Returns the map entry corresponding to the key with the longest prefix match with the given address.lowerEntry
(K key) Maps the given single address or prefix block subnet to the given value in the map.putIfAbsent
(K key, V value) boolean
boolean
void
replaceAll
(BiFunction<? super K, ? super V, ? extends V> function) int
size()
Returns the number of mappings in this map.subMapFromKeysContainedBy
(K addr) Returns a sub-map consisting of the mappings in the map with address keys contained by the given address The sub-map will have a restricted range matching the range of the given subnet or address.subMapFromKeysContaining
(K addr) Returns a sub-map consisting of the mappings in the map with address keys that contain the given address.Methods inherited from class java.util.AbstractMap
putAll, toString, values
Methods inherited from interface java.util.NavigableMap
reversed
Methods inherited from interface java.util.SequencedMap
sequencedEntrySet, sequencedKeySet, sequencedValues
-
Constructor Details
-
AddressTrieMap
-
AddressTrieMap
-
-
Method Details
-
descendingMap
- Specified by:
descendingMap
in interfaceNavigableMap<K extends Address,
V>
-
descendingKeySet
- Specified by:
descendingKeySet
in interfaceNavigableMap<K extends Address,
V>
-
asTrie
Return a trie representing this map.If this map has a restricted range, see
hasRestrictedRange()
, this generates a new trie corresponding to the map with only the nodes pertaining to the restricted range sub-map. Otherwise this returns the original backing trie for this map.When a new trie is generated, the original backing trie for this map remains the same, it is not changed to the new trie.
The returned trie will always have the same natural trie ordering, even if this map has the reverse ordering.
-
hasRestrictedRange
public boolean hasRestrictedRange()Returns whether this map is the result of a call toheadMap(Address)
,tailMap(Address)
,subMap(Address, Address)
or any of the other methods with the same names.- Returns:
-
getRange
Returns the range if this map has a restricted range, seehasRestrictedRange()
. Otherwise returns null.- Returns:
-
keySet
-
entrySet
-
merge
-
compute
-
computeIfAbsent
- Specified by:
computeIfAbsent
in interfaceMap<K extends Address,
V>
-
putIfAbsent
- Specified by:
putIfAbsent
in interfaceMap<K extends Address,
V>
-
computeIfPresent
- Specified by:
computeIfPresent
in interfaceMap<K extends Address,
V>
-
containsKey
- Specified by:
containsKey
in interfaceMap<K extends Address,
V> - Overrides:
containsKey
in classAbstractMap<K extends Address,
V>
-
containsValue
- Specified by:
containsValue
in interfaceMap<K extends Address,
V> - Overrides:
containsValue
in classAbstractMap<K extends Address,
V>
-
get
-
put
Maps the given single address or prefix block subnet to the given value in the map.If the given address is not a single address nor prefix block, then this method throws IllegalArgumentException.
-
remove
-
getOrDefault
- Specified by:
getOrDefault
in interfaceMap<K extends Address,
V>
-
forEach
-
replaceAll
- Specified by:
replaceAll
in interfaceMap<K extends Address,
V>
-
remove
-
replace
-
replace
-
size
public int size()Returns the number of mappings in this map. This is a constant time operation, unless the map has a restricted range, seehasRestrictedRange()
, in which case it is a linear time operation proportional to the number of mappings. -
isEmpty
public boolean isEmpty() -
clear
public void clear() -
hashCode
public int hashCode() -
subMap
-
subMap
- Specified by:
subMap
in interfaceNavigableMap<K extends Address,
V>
-
headMap
-
headMap
- Specified by:
headMap
in interfaceNavigableMap<K extends Address,
V>
-
tailMap
-
tailMap
- Specified by:
tailMap
in interfaceNavigableMap<K extends Address,
V>
-
firstEntry
- Specified by:
firstEntry
in interfaceNavigableMap<K extends Address,
V> - Specified by:
firstEntry
in interfaceSequencedMap<K extends Address,
V>
-
firstKey
-
lastEntry
- Specified by:
lastEntry
in interfaceNavigableMap<K extends Address,
V> - Specified by:
lastEntry
in interfaceSequencedMap<K extends Address,
V>
-
lastKey
-
lowerEntry
- Specified by:
lowerEntry
in interfaceNavigableMap<K extends Address,
V>
-
lowerKey
- Specified by:
lowerKey
in interfaceNavigableMap<K extends Address,
V>
-
floorEntry
- Specified by:
floorEntry
in interfaceNavigableMap<K extends Address,
V>
-
floorKey
- Specified by:
floorKey
in interfaceNavigableMap<K extends Address,
V>
-
ceilingEntry
- Specified by:
ceilingEntry
in interfaceNavigableMap<K extends Address,
V>
-
ceilingKey
- Specified by:
ceilingKey
in interfaceNavigableMap<K extends Address,
V>
-
higherEntry
- Specified by:
higherEntry
in interfaceNavigableMap<K extends Address,
V>
-
higherKey
- Specified by:
higherKey
in interfaceNavigableMap<K extends Address,
V>
-
pollFirstEntry
- Specified by:
pollFirstEntry
in interfaceNavigableMap<K extends Address,
V> - Specified by:
pollFirstEntry
in interfaceSequencedMap<K extends Address,
V>
-
pollLastEntry
- Specified by:
pollLastEntry
in interfaceNavigableMap<K extends Address,
V> - Specified by:
pollLastEntry
in interfaceSequencedMap<K extends Address,
V>
-
equals
-
clone
Clones the map along with the backing trie. If the map had a restricted range, the clone does not. -
comparator
- Specified by:
comparator
in interfaceSortedMap<K extends Address,
V>
-
toTrieString
-
subMapFromKeysContainedBy
Returns a sub-map consisting of the mappings in the map with address keys contained by the given address The sub-map will have a restricted range matching the range of the given subnet or address.If the sub-map would be the same size as this map, then this map is returned. The sub-map will the same backing trie as this map.
- Parameters:
addr
-- Returns:
-
subMapFromKeysContaining
Returns a sub-map consisting of the mappings in the map with address keys that contain the given address. The sub-map will have the same restricted range (if any) as this sub-map.If the sub-map would be the same size as this map, then this map is returned. Otherwise, the sub-map is backed by a new trie.
- Parameters:
addr
-- Returns:
-
keyContains
Returns true if a subnet or address key in the map contains the given subnet or address.- Parameters:
addr
-- Returns:
-
longestPrefixMatchEntry
Returns the map entry corresponding to the key with the longest prefix match with the given address.- Parameters:
addr
-- Returns:
-