- java.lang.Object
-
- java.util.AbstractMap<K,V>
-
- inet.ipaddr.format.util.AddressTrieMap<K,V>
-
- Type Parameters:
K
- the address typeV
- the type of the mapped values
- All Implemented Interfaces:
java.io.Serializable
,java.lang.Cloneable
,java.util.Map<K,V>
,java.util.NavigableMap<K,V>
,java.util.SortedMap<K,V>
public class AddressTrieMap<K extends Address,V> extends java.util.AbstractMap<K,V> implements java.util.NavigableMap<K,V>, java.lang.Cloneable, java.io.Serializable
Wraps aAssociativeAddressTrie
to view it as a Java Collections Framework map, implementing theMap
,SortedMap
, andNavigableMap
interfaces.Like
TreeMap
, this map is backed by a binary tree and implements the same interfaces thatTreeMap
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 usingMap.Entry.setValue(Object)
, whileTreeMap
does not. The entries provided by theTreeMap
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, seeAddressComparator
.- Author:
- scfoley
- See Also:
- Serialized Form
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description static class
AddressTrieMap.EntrySet<K extends Address,V>
-
Constructor Summary
Constructors Constructor Description AddressTrieMap(AssociativeAddressTrie<K,V> trie)
AddressTrieMap(AssociativeAddressTrie<K,V> trie, java.util.Map<? extends K,? extends V> map)
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description AssociativeAddressTrie<K,V>
asTrie()
Return a trie representing this map.java.util.Map.Entry<K,V>
ceilingEntry(K key)
K
ceilingKey(K key)
void
clear()
AddressTrieMap<K,V>
clone()
Clones the map along with the backing trie.java.util.Comparator<K>
comparator()
V
compute(K key, java.util.function.BiFunction<? super K,? super V,? extends V> remappingFunction)
V
computeIfAbsent(K key, java.util.function.Function<? super K,? extends V> remappingFunction)
V
computeIfPresent(K key, java.util.function.BiFunction<? super K,? super V,? extends V> remappingFunction)
boolean
containsKey(java.lang.Object key)
boolean
containsValue(java.lang.Object value)
AddressTrieSet<K>
descendingKeySet()
AddressTrieMap<K,V>
descendingMap()
AddressTrieMap.EntrySet<K,V>
entrySet()
boolean
equals(java.lang.Object o)
java.util.Map.Entry<K,V>
firstEntry()
K
firstKey()
java.util.Map.Entry<K,V>
floorEntry(K key)
K
floorKey(K key)
void
forEach(java.util.function.BiConsumer<? super K,? super V> action)
V
get(java.lang.Object key)
V
getOrDefault(java.lang.Object key, V defaultValue)
AddressTrieSet.Range<K>
getRange()
Returns the range if this map has a restricted range, seehasRestrictedRange()
.int
hashCode()
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.AddressTrieMap<K,V>
headMap(K toKey)
AddressTrieMap<K,V>
headMap(K toKey, boolean inclusive)
java.util.Map.Entry<K,V>
higherEntry(K key)
K
higherKey(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.AddressTrieSet<K>
keySet()
java.util.Map.Entry<K,V>
lastEntry()
K
lastKey()
java.util.Map.Entry<K,V>
longestPrefixMatchEntry(K addr)
Returns the map entry corresponding to the key with the longest prefix match with the given address.java.util.Map.Entry<K,V>
lowerEntry(K key)
K
lowerKey(K key)
V
merge(K key, V suppliedValue, java.util.function.BiFunction<? super V,? super V,? extends V> remappingFunction)
AddressTrieSet<K>
navigableKeySet()
java.util.Map.Entry<K,V>
pollFirstEntry()
java.util.Map.Entry<K,V>
pollLastEntry()
V
put(K key, V value)
Maps the given single address or prefix block subnet to the given value in the map.V
putIfAbsent(K key, V value)
V
remove(java.lang.Object key)
boolean
remove(java.lang.Object key, java.lang.Object value)
V
replace(K key, V value)
boolean
replace(K key, V oldValue, V newValue)
void
replaceAll(java.util.function.BiFunction<? super K,? super V,? extends V> function)
int
size()
Returns the number of mappings in this map.AddressTrieMap<K,V>
subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive)
AddressTrieMap<K,V>
subMap(K fromKey, K toKey)
AddressTrieMap<K,V>
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.AddressTrieMap<K,V>
subMapFromKeysContaining(K addr)
Returns a sub-map consisting of the mappings in the map with address keys that contain the given address.AddressTrieMap<K,V>
tailMap(K fromKey)
AddressTrieMap<K,V>
tailMap(K fromKey, boolean inclusive)
java.lang.String
toTrieString()
-
-
-
Constructor Detail
-
AddressTrieMap
public AddressTrieMap(AssociativeAddressTrie<K,V> trie)
-
AddressTrieMap
public AddressTrieMap(AssociativeAddressTrie<K,V> trie, java.util.Map<? extends K,? extends V> map)
-
-
Method Detail
-
descendingMap
public AddressTrieMap<K,V> descendingMap()
-
descendingKeySet
public AddressTrieSet<K> descendingKeySet()
-
asTrie
public AssociativeAddressTrie<K,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
public AddressTrieSet.Range<K> getRange()
Returns the range if this map has a restricted range, seehasRestrictedRange()
. Otherwise returns null.- Returns:
-
keySet
public AddressTrieSet<K> keySet()
-
navigableKeySet
public AddressTrieSet<K> navigableKeySet()
-
entrySet
public AddressTrieMap.EntrySet<K,V> entrySet()
-
merge
public V merge(K key, V suppliedValue, java.util.function.BiFunction<? super V,? super V,? extends V> remappingFunction)
-
compute
public V compute(K key, java.util.function.BiFunction<? super K,? super V,? extends V> remappingFunction)
-
computeIfAbsent
public V computeIfAbsent(K key, java.util.function.Function<? super K,? extends V> remappingFunction)
-
computeIfPresent
public V computeIfPresent(K key, java.util.function.BiFunction<? super K,? super V,? extends V> remappingFunction)
-
containsKey
public boolean containsKey(java.lang.Object key)
-
containsValue
public boolean containsValue(java.lang.Object value)
-
get
public V get(java.lang.Object key)
-
put
public V put(K key, V value)
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
public V remove(java.lang.Object key)
-
replaceAll
public void replaceAll(java.util.function.BiFunction<? super K,? super V,? extends V> function)
-
remove
public boolean remove(java.lang.Object key, java.lang.Object value)
-
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
public AddressTrieMap<K,V> subMap(K fromKey, K toKey)
-
subMap
public AddressTrieMap<K,V> subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive)
-
headMap
public AddressTrieMap<K,V> headMap(K toKey)
-
headMap
public AddressTrieMap<K,V> headMap(K toKey, boolean inclusive)
-
tailMap
public AddressTrieMap<K,V> tailMap(K fromKey)
-
tailMap
public AddressTrieMap<K,V> tailMap(K fromKey, boolean inclusive)
-
firstKey
public K firstKey()
-
lastKey
public K lastKey()
-
equals
public boolean equals(java.lang.Object o)
-
clone
public AddressTrieMap<K,V> clone()
Clones the map along with the backing trie. If the map had a restricted range, the clone does not.
-
comparator
public java.util.Comparator<K> comparator()
-
toTrieString
public java.lang.String toTrieString()
-
subMapFromKeysContainedBy
public AddressTrieMap<K,V> 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.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
public AddressTrieMap<K,V> subMapFromKeysContaining(K addr)
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
public boolean keyContains(K addr)
Returns true if a subnet or address key in the map contains the given subnet or address.- Parameters:
addr
-- Returns:
-
-