K - the address typeV - the type of the mapped valuespublic class AddressTrieMap<K extends Address,V> extends AbstractMap<K,V> implements NavigableMap<K,V>, Cloneable, Serializable
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.
| Modifier and Type | Class and Description |
|---|---|
static class |
AddressTrieMap.EntrySet<K extends Address,V> |
AbstractMap.SimpleEntry<K,V>, AbstractMap.SimpleImmutableEntry<K,V>| Constructor and Description |
|---|
AddressTrieMap(AssociativeAddressTrie<K,V> trie) |
AddressTrieMap(AssociativeAddressTrie<K,V> trie,
Map<? extends K,? extends V> map) |
| Modifier and Type | Method and Description |
|---|---|
AssociativeAddressTrie<K,V> |
asTrie()
Return a trie representing this map.
|
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.
|
Comparator<K> |
comparator() |
V |
compute(K key,
BiFunction<? super K,? super V,? extends V> remappingFunction) |
V |
computeIfAbsent(K key,
Function<? super K,? extends V> remappingFunction) |
V |
computeIfPresent(K key,
BiFunction<? super K,? super V,? extends V> remappingFunction) |
boolean |
containsKey(Object key) |
boolean |
containsValue(Object value) |
AddressTrieSet<K> |
descendingKeySet() |
AddressTrieMap<K,V> |
descendingMap() |
AddressTrieMap.EntrySet<K,V> |
entrySet() |
boolean |
equals(Object o) |
Map.Entry<K,V> |
firstEntry() |
K |
firstKey() |
Map.Entry<K,V> |
floorEntry(K key) |
K |
floorKey(K key) |
void |
forEach(BiConsumer<? super K,? super V> action) |
V |
get(Object key) |
V |
getOrDefault(Object key,
V defaultValue) |
AddressTrieSet.Range<K> |
getRange()
Returns the range if this map has a restricted range, see
hasRestrictedRange(). |
int |
hashCode() |
boolean |
hasRestrictedRange()
Returns whether this map is the result of a call to
headMap(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) |
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() |
Map.Entry<K,V> |
lastEntry() |
K |
lastKey() |
Map.Entry<K,V> |
longestPrefixMatchEntry(K addr)
Returns the map entry corresponding to the key with the longest prefix match with the given address.
|
Map.Entry<K,V> |
lowerEntry(K key) |
K |
lowerKey(K key) |
V |
merge(K key,
V suppliedValue,
BiFunction<? super V,? super V,? extends V> remappingFunction) |
AddressTrieSet<K> |
navigableKeySet() |
Map.Entry<K,V> |
pollFirstEntry() |
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(Object key) |
boolean |
remove(Object key,
Object value) |
V |
replace(K key,
V value) |
boolean |
replace(K key,
V oldValue,
V newValue) |
void |
replaceAll(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) |
String |
toTrieString() |
putAll, toString, valuespublic AddressTrieMap(AssociativeAddressTrie<K,V> trie)
public AddressTrieMap<K,V> descendingMap()
descendingMap in interface NavigableMap<K extends Address,V>public AddressTrieSet<K> descendingKeySet()
descendingKeySet in interface NavigableMap<K extends Address,V>public AssociativeAddressTrie<K,V> asTrie()
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.
public boolean hasRestrictedRange()
headMap(Address), tailMap(Address),
subMap(Address, Address) or any of the other methods with the same names.public AddressTrieSet.Range<K> getRange()
hasRestrictedRange(). Otherwise returns null.public AddressTrieSet<K> keySet()
public AddressTrieSet<K> navigableKeySet()
navigableKeySet in interface NavigableMap<K extends Address,V>public AddressTrieMap.EntrySet<K,V> entrySet()
public V merge(K key, V suppliedValue, BiFunction<? super V,? super V,? extends V> remappingFunction)
public V computeIfAbsent(K key, Function<? super K,? extends V> remappingFunction)
computeIfAbsent in interface Map<K extends Address,V>public V putIfAbsent(K key, V value)
putIfAbsent in interface Map<K extends Address,V>public V computeIfPresent(K key, BiFunction<? super K,? super V,? extends V> remappingFunction)
computeIfPresent in interface Map<K extends Address,V>public boolean containsKey(Object key)
containsKey in interface Map<K extends Address,V>containsKey in class AbstractMap<K extends Address,V>public boolean containsValue(Object value)
containsValue in interface Map<K extends Address,V>containsValue in class AbstractMap<K extends Address,V>public V put(K key, V value)
If the given address is not a single address nor prefix block, then this method throws IllegalArgumentException.
public V getOrDefault(Object key, V defaultValue)
getOrDefault in interface Map<K extends Address,V>public void forEach(BiConsumer<? super K,? super V> action)
public void replaceAll(BiFunction<? super K,? super V,? extends V> function)
replaceAll in interface Map<K extends Address,V>public int size()
hasRestrictedRange(),
in which case it is a linear time operation proportional to the number of mappings.public boolean isEmpty()
public void clear()
public int hashCode()
public AddressTrieMap<K,V> subMap(K fromKey, K toKey)
public AddressTrieMap<K,V> subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive)
subMap in interface NavigableMap<K extends Address,V>public AddressTrieMap<K,V> headMap(K toKey)
public AddressTrieMap<K,V> headMap(K toKey, boolean inclusive)
headMap in interface NavigableMap<K extends Address,V>public AddressTrieMap<K,V> tailMap(K fromKey)
public AddressTrieMap<K,V> tailMap(K fromKey, boolean inclusive)
tailMap in interface NavigableMap<K extends Address,V>public Map.Entry<K,V> firstEntry()
firstEntry in interface NavigableMap<K extends Address,V>public Map.Entry<K,V> lastEntry()
lastEntry in interface NavigableMap<K extends Address,V>public Map.Entry<K,V> lowerEntry(K key)
lowerEntry in interface NavigableMap<K extends Address,V>public K lowerKey(K key)
lowerKey in interface NavigableMap<K extends Address,V>public Map.Entry<K,V> floorEntry(K key)
floorEntry in interface NavigableMap<K extends Address,V>public K floorKey(K key)
floorKey in interface NavigableMap<K extends Address,V>public Map.Entry<K,V> ceilingEntry(K key)
ceilingEntry in interface NavigableMap<K extends Address,V>public K ceilingKey(K key)
ceilingKey in interface NavigableMap<K extends Address,V>public Map.Entry<K,V> higherEntry(K key)
higherEntry in interface NavigableMap<K extends Address,V>public K higherKey(K key)
higherKey in interface NavigableMap<K extends Address,V>public Map.Entry<K,V> pollFirstEntry()
pollFirstEntry in interface NavigableMap<K extends Address,V>public Map.Entry<K,V> pollLastEntry()
pollLastEntry in interface NavigableMap<K extends Address,V>public boolean equals(Object o)
public AddressTrieMap<K,V> clone()
clone in class AbstractMap<K extends Address,V>public Comparator<K> comparator()
comparator in interface SortedMap<K extends Address,V>public String toTrieString()
public AddressTrieMap<K,V> subMapFromKeysContainedBy(K addr)
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.
addr - public AddressTrieMap<K,V> subMapFromKeysContaining(K addr)
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.
addr - public boolean keyContains(K addr)
addr -