Module inet.ipaddr

Class AddressTrieMap<K extends Address,V>

java.lang.Object
java.util.AbstractMap<K,V>
inet.ipaddr.format.util.AddressTrieMap<K,V>
Type Parameters:
K - the address type
V - the type of the mapped values
All Implemented Interfaces:
Serializable, Cloneable, Map<K,V>, NavigableMap<K,V>, SequencedMap<K,V>, SortedMap<K,V>

public class AddressTrieMap<K extends Address,V> extends AbstractMap<K,V> implements NavigableMap<K,V>, Cloneable, Serializable
Wraps a 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: