Module inet.ipaddr

Class AddressTrieMap<K extends Address,​V>

  • Type Parameters:
    K - the address type
    V - 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 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:
    Serialized Form
    • Method Detail

      • descendingMap

        public AddressTrieMap<K,​V> descendingMap()
        Specified by:
        descendingMap in interface java.util.NavigableMap<K extends Address,​V>
      • descendingKeySet

        public AddressTrieSet<K> descendingKeySet()
        Specified by:
        descendingKeySet in interface java.util.NavigableMap<K extends Address,​V>
      • 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.

      • keySet

        public AddressTrieSet<K> keySet()
        Specified by:
        keySet in interface java.util.Map<K extends Address,​V>
        Specified by:
        keySet in interface java.util.SortedMap<K extends Address,​V>
        Overrides:
        keySet in class java.util.AbstractMap<K extends Address,​V>
      • navigableKeySet

        public AddressTrieSet<K> navigableKeySet()
        Specified by:
        navigableKeySet in interface java.util.NavigableMap<K extends Address,​V>
      • entrySet

        public AddressTrieMap.EntrySet<K,​V> entrySet()
        Specified by:
        entrySet in interface java.util.Map<K extends Address,​V>
        Specified by:
        entrySet in interface java.util.SortedMap<K extends Address,​V>
        Specified by:
        entrySet in class java.util.AbstractMap<K extends Address,​V>
      • merge

        public V merge​(K key,
                       V suppliedValue,
                       java.util.function.BiFunction<? super V,​? super V,​? extends V> remappingFunction)
        Specified by:
        merge in interface java.util.Map<K extends Address,​V>
      • compute

        public V compute​(K key,
                         java.util.function.BiFunction<? super K,​? super V,​? extends V> remappingFunction)
        Specified by:
        compute in interface java.util.Map<K extends Address,​V>
      • computeIfAbsent

        public V computeIfAbsent​(K key,
                                 java.util.function.Function<? super K,​? extends V> remappingFunction)
        Specified by:
        computeIfAbsent in interface java.util.Map<K extends Address,​V>
      • putIfAbsent

        public V putIfAbsent​(K key,
                             V value)
        Specified by:
        putIfAbsent in interface java.util.Map<K extends Address,​V>
      • computeIfPresent

        public V computeIfPresent​(K key,
                                  java.util.function.BiFunction<? super K,​? super V,​? extends V> remappingFunction)
        Specified by:
        computeIfPresent in interface java.util.Map<K extends Address,​V>
      • containsKey

        public boolean containsKey​(java.lang.Object key)
        Specified by:
        containsKey in interface java.util.Map<K extends Address,​V>
        Overrides:
        containsKey in class java.util.AbstractMap<K extends Address,​V>
      • containsValue

        public boolean containsValue​(java.lang.Object value)
        Specified by:
        containsValue in interface java.util.Map<K extends Address,​V>
        Overrides:
        containsValue in class java.util.AbstractMap<K extends Address,​V>
      • get

        public V get​(java.lang.Object key)
        Specified by:
        get in interface java.util.Map<K extends Address,​V>
        Overrides:
        get in class java.util.AbstractMap<K extends Address,​V>
      • 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.

        See AssociativeAddressTrie

        Specified by:
        put in interface java.util.Map<K extends Address,​V>
        Overrides:
        put in class java.util.AbstractMap<K extends Address,​V>
      • remove

        public V remove​(java.lang.Object key)
        Specified by:
        remove in interface java.util.Map<K extends Address,​V>
        Overrides:
        remove in class java.util.AbstractMap<K extends Address,​V>
      • getOrDefault

        public V getOrDefault​(java.lang.Object key,
                              V defaultValue)
        Specified by:
        getOrDefault in interface java.util.Map<K extends Address,​V>
      • forEach

        public void forEach​(java.util.function.BiConsumer<? super K,​? super V> action)
        Specified by:
        forEach in interface java.util.Map<K extends Address,​V>
      • replaceAll

        public void replaceAll​(java.util.function.BiFunction<? super K,​? super V,​? extends V> function)
        Specified by:
        replaceAll in interface java.util.Map<K extends Address,​V>
      • remove

        public boolean remove​(java.lang.Object key,
                              java.lang.Object value)
        Specified by:
        remove in interface java.util.Map<K extends Address,​V>
      • replace

        public boolean replace​(K key,
                               V oldValue,
                               V newValue)
        Specified by:
        replace in interface java.util.Map<K extends Address,​V>
      • replace

        public V replace​(K key,
                         V value)
        Specified by:
        replace in interface java.util.Map<K extends Address,​V>
      • 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, see hasRestrictedRange(), in which case it is a linear time operation proportional to the number of mappings.
        Specified by:
        size in interface java.util.Map<K extends Address,​V>
        Overrides:
        size in class java.util.AbstractMap<K extends Address,​V>
        Returns:
        the number of elements in this map
      • isEmpty

        public boolean isEmpty()
        Specified by:
        isEmpty in interface java.util.Map<K extends Address,​V>
        Overrides:
        isEmpty in class java.util.AbstractMap<K extends Address,​V>
      • clear

        public void clear()
        Specified by:
        clear in interface java.util.Map<K extends Address,​V>
        Overrides:
        clear in class java.util.AbstractMap<K extends Address,​V>
      • hashCode

        public int hashCode()
        Specified by:
        hashCode in interface java.util.Map<K extends Address,​V>
        Overrides:
        hashCode in class java.util.AbstractMap<K extends Address,​V>
      • subMap

        public AddressTrieMap<K,​V> subMap​(K fromKey,
                                                K toKey)
        Specified by:
        subMap in interface java.util.NavigableMap<K extends Address,​V>
        Specified by:
        subMap in interface java.util.SortedMap<K extends Address,​V>
      • subMap

        public AddressTrieMap<K,​V> subMap​(K fromKey,
                                                boolean fromInclusive,
                                                K toKey,
                                                boolean toInclusive)
        Specified by:
        subMap in interface java.util.NavigableMap<K extends Address,​V>
      • headMap

        public AddressTrieMap<K,​V> headMap​(K toKey)
        Specified by:
        headMap in interface java.util.NavigableMap<K extends Address,​V>
        Specified by:
        headMap in interface java.util.SortedMap<K extends Address,​V>
      • headMap

        public AddressTrieMap<K,​V> headMap​(K toKey,
                                                 boolean inclusive)
        Specified by:
        headMap in interface java.util.NavigableMap<K extends Address,​V>
      • tailMap

        public AddressTrieMap<K,​V> tailMap​(K fromKey)
        Specified by:
        tailMap in interface java.util.NavigableMap<K extends Address,​V>
        Specified by:
        tailMap in interface java.util.SortedMap<K extends Address,​V>
      • tailMap

        public AddressTrieMap<K,​V> tailMap​(K fromKey,
                                                 boolean inclusive)
        Specified by:
        tailMap in interface java.util.NavigableMap<K extends Address,​V>
      • firstEntry

        public java.util.Map.Entry<K,​V> firstEntry()
        Specified by:
        firstEntry in interface java.util.NavigableMap<K extends Address,​V>
      • firstKey

        public K firstKey()
        Specified by:
        firstKey in interface java.util.SortedMap<K extends Address,​V>
      • lastEntry

        public java.util.Map.Entry<K,​V> lastEntry()
        Specified by:
        lastEntry in interface java.util.NavigableMap<K extends Address,​V>
      • lastKey

        public K lastKey()
        Specified by:
        lastKey in interface java.util.SortedMap<K extends Address,​V>
      • lowerEntry

        public java.util.Map.Entry<K,​V> lowerEntry​(K key)
        Specified by:
        lowerEntry in interface java.util.NavigableMap<K extends Address,​V>
      • lowerKey

        public K lowerKey​(K key)
        Specified by:
        lowerKey in interface java.util.NavigableMap<K extends Address,​V>
      • floorEntry

        public java.util.Map.Entry<K,​V> floorEntry​(K key)
        Specified by:
        floorEntry in interface java.util.NavigableMap<K extends Address,​V>
      • floorKey

        public K floorKey​(K key)
        Specified by:
        floorKey in interface java.util.NavigableMap<K extends Address,​V>
      • ceilingEntry

        public java.util.Map.Entry<K,​V> ceilingEntry​(K key)
        Specified by:
        ceilingEntry in interface java.util.NavigableMap<K extends Address,​V>
      • ceilingKey

        public K ceilingKey​(K key)
        Specified by:
        ceilingKey in interface java.util.NavigableMap<K extends Address,​V>
      • higherEntry

        public java.util.Map.Entry<K,​V> higherEntry​(K key)
        Specified by:
        higherEntry in interface java.util.NavigableMap<K extends Address,​V>
      • higherKey

        public K higherKey​(K key)
        Specified by:
        higherKey in interface java.util.NavigableMap<K extends Address,​V>
      • pollFirstEntry

        public java.util.Map.Entry<K,​V> pollFirstEntry()
        Specified by:
        pollFirstEntry in interface java.util.NavigableMap<K extends Address,​V>
      • pollLastEntry

        public java.util.Map.Entry<K,​V> pollLastEntry()
        Specified by:
        pollLastEntry in interface java.util.NavigableMap<K extends Address,​V>
      • equals

        public boolean equals​(java.lang.Object o)
        Specified by:
        equals in interface java.util.Map<K extends Address,​V>
        Overrides:
        equals in class java.util.AbstractMap<K extends Address,​V>
      • 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()
        Specified by:
        comparator in interface java.util.SortedMap<K extends Address,​V>
      • 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:
      • longestPrefixMatchEntry

        public 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.
        Parameters:
        addr -
        Returns: