AddressTrie (IPAddress javadoc by seancfoley)

java.lang.Object
- inet.ipaddr.format.util.AddressTrie<E>

Type Parameters:

E - the type of the address keys

All Implemented Interfaces:

AddressTrieOps<E>, AddressTrieOps.AddressTrieAddOps<E>, TreeOps<E>, Serializable, Cloneable, Iterable<E>

Direct Known Subclasses:

AssociativeAddressTrie, IPv4AddressTrie, IPv6AddressTrie, MACAddressTrie
```
public abstract class AddressTrie<E extends Address>
extends Object
```
A compact binary trie (aka compact binary prefix tree, or binary radix trie), for addresses and/or CIDR prefix block subnets. The prefixes in used by the prefix trie are the CIDR prefixes, or the full address in the case of individual addresses with no prefix length. The elements of the trie are CIDR prefix blocks or addresses.
This trie data structure allows you to check an address for containment in many subnets at once, in constant time. The trie allows you to check a subnet for containment of many smaller subnets or addresses at once, in constant time. The trie allows you to check for equality of a subnet or address with a large number of subnets or addresses at once.
The trie can also be used as the backing structure for a AddressTrieSet which is a NavigableSet. Unlike TreeSet this data structure provides access to the nodes and the associated subtrie with each node, which corresponds with their associated CIDR prefix block subnets.
There is only a single possible trie for any given set of address and subnets. For one thing, this means they are automatically balanced. Also, this makes access to subtries and to the nodes themselves more useful, allowing for many of the same operations performed on the original trie.
Each node has either a prefix block or a single address as its key. Each prefix block node can have two sub-nodes, each sub-node a prefix block or address contained by the node.
There are more nodes in the trie than there are elements in the set. A node is considered "added" if it was explicitly added to the trie and is included as an element when viewed as a set. There are non-added prefix block nodes that are generated in the trie as well. When two or more added addresses share the same prefix up until they differ with the bit at index x, then a prefix block node is generated (if not already added to the trie) for the common prefix of length x, with the nodes for those addresses to be found following the lower or upper sub-nodes according to the bit at index x + 1 in each address. If that bit is 1, the node can be found by following the upper sub-node, and when it is 0, the lower sub-node.
Nodes that were generated as part of the trie structure only because of other added elements are not elements of the represented set. The set elements are the elements that were explicitly added.
You can work with parts of the trie, starting from any node in the trie, calling methods that start with any given node, such as iterating or spliterating the subtrie, finding the first or last in the subtrie, doing containment checks with the subtrie, and so on.
The binary trie structure defines a natural ordering of the trie elements. Addresses of equal prefix length are sorted by prefix value. Addresses with no prefix length are sorted by address value. Addresses of differing prefix length are sorted according to the bit that follows the shorter prefix length in the address with the longer prefix length, whether that bit is 0 or 1 determines if that address is ordered before or after the address of shorter prefix length.
The unique and pre-defined structure for a trie means that different means of traversing the trie can be more meaningful. This trie implementation provides 8 different ways of iterating through the trie:
- 1, 2: the natural sorted trie order, forward and reverse (spliterating is also an option for these two orders). Use nodeIterator(boolean), iterator() or descendingIterator(). A comparator is also provided for this order.
- 3, 4: pre-order tree traversal, in which parent node is visited before sub-nodes, with sub-nodes visited in forward or reverse order
- 5, 6: post-order tree traversal, in which sub-nodes are visited before parent nodes, with sub-nodes visited in forward or reverse order
- 7, 8: prefix-block order, in which larger prefix blocks are visited before smaller, and blocks of equal size are visited in forward or reverse sorted order
All of these orderings are useful in specific contexts.
You can do lookup and containment checks on all the subnets and addresses in the trie at once, in constant time. A generic trie data structure lookup is O(m) where m is the entry length. For this trie, which operates on address bits, entry length is capped at 128 bits for IPv6 and 32 bits for IPv4. That makes lookup a constant time operation. Subnet containment or equality checks are also constant time since they work the same way as lookup, by comparing prefix bits.
For a generic trie data structure, construction is O(m * n) where m is entry length and n is the number of addresses, but for this trie, since entry length is capped at 128 bits for IPv6 and 32 bits for IPv4, construction is O(n), in linear proportion to the number of added elements.
This trie also allows for constant time size queries (count of added elements, not node count), by storing sub-trie size in each node. It works by updating the size of every node in the path to any added or removed node. This does not change insertion or deletion operations from being constant time (because tree-depth is limited to address bit count). At the same this makes size queries constant time, rather than being O(n) time.
This class is abstract and has a subclass for each address version or type. A single trie can use just a single address type or version, since it works with bits alone, and this cannot distinguish between different versions and types in the trie structure. More specifically, using different address bit lengths would:
- break the concept of containment, for example IPv6 address 0::/8 would be considered to contain IPv4 address 0.2.3.4
- break the concept of equality, for example MAC 1:2:3:*:*:* and IPv4 1.2.3.0/24 would be considered the same since they have the same prefix bits and length
Instead, you could aggregate multiple subtries to create a collection of multiple address types or versions. You can use the method toString(boolean, AddressTrie...) for a String that represents multiple tries as a single tree.
Tries are thread-safe when not being modified (elements added or removed), but are not thread-safe when one thread is modifying the trie. For thread safety when modifying, one option is to use Collections.synchronizedNavigableSet(java.util.NavigableSet) on asSet().
See Also:

Serialized Form

Nested Class Summary

Nested Classes
Modifier and Type	Class and Description
`static class`	`AddressTrie.AddressComparator<E extends Address>` A comparator that provides the same ordering used by the trie, an ordering that works with prefix block subnets and individual addresses.
`static class`	`AddressTrie.TrieComparator<E extends Address>`
`static class`	`AddressTrie.TrieNode<E extends Address>` A node for a compact binary prefix trie whose elements are prefix block subnets or addresses,

Nested classes/interfaces inherited from interface inet.ipaddr.format.util.AddressTrieOps
AddressTrieOps.AddressTrieAddOps<E extends Address>, AddressTrieOps.AssociativeAddressTrieOps<K extends Address,V>, AddressTrieOps.AssociativeAddressTriePutOps<K extends Address,V>

Method Summary

All Methods Static Methods Instance Methods Abstract Methods Concrete Methods
Modifier and Type	Method and Description
`boolean`	`add(E addr)` Adds the given single address or prefix block subnet to the trie.
`AddressTrie.TrieNode<E>`	`addNode(E addr)` Adds the given single address or prefix block subnet to the trie, if not already there.
`AddressTrie.TrieNode<E>`	`addTrie(AddressTrie.TrieNode<E> trie)` Adds nodes matching the given sub-root node and all of its sub-nodes to the trie, if not already there.
`Iterator<? extends AddressTrie.TrieNode<E>>`	`allNodeIterator(boolean forward)` Iterates through the nodes (not just the added nodes) in forward or reverse tree order.
`Spliterator<? extends AddressTrie.TrieNode<E>>`	`allNodeSpliterator(boolean forward)` Creates a `Spliterator` over the nodes in forward or reverse natural tree order.
`AddressTrieSet<E>`	`asSet()` Returns a java.util.NavigableSet that uses this as the backing data structure.
`Iterator<? extends AddressTrie.TrieNode<E>>`	`blockSizeAllNodeIterator(boolean lowerSubNodeFirst)` Iterates all nodes in the trie, ordered by keys from largest prefix blocks to smallest, and then to individual addresses.
`<C> BinaryTreeNode.CachingIterator<? extends AddressTrie.TrieNode<E>,E,C>`	`blockSizeCachingAllNodeIterator()` Iterates all nodes, ordered by keys from largest prefix blocks to smallest, and then to individual addresses.
`Iterator<? extends AddressTrie.TrieNode<E>>`	`blockSizeNodeIterator(boolean lowerSubNodeFirst)` Iterates the added nodes in the trie, ordered by keys from largest prefix blocks to smallest, and then to individual addresses.
`E`	`ceiling(E addr)` Returns the lowest added address greater than or equal to the given address.
`AddressTrie.TrieNode<E>`	`ceilingAddedNode(E addr)` Returns the added node whose address is the lowest address greater than or equal to the given address.
`void`	`clear()` Removes all added nodes from the tree, after which `isEmpty()` will return true
`AddressTrie<E>`	`clone()` Copies the trie, but not the keys or values.
`abstract inet.ipaddr.format.util.AddedTreeBase<E,? extends inet.ipaddr.format.util.AddressTrie.SubNodesMapping<E,? extends inet.ipaddr.format.util.AddressTrie.SubNodesMapping<E,?>>>`	`constructAddedNodesTree()` Provides an associative trie in which the root and each added node are mapped to a list of their respective direct added nodes.
`Iterator<? extends AddressTrie.TrieNode<E>>`	`containedFirstAllNodeIterator(boolean forwardSubNodeOrder)` Returns an iterator that does a post-order binary tree traversal.
`Iterator<? extends AddressTrie.TrieNode<E>>`	`containedFirstIterator(boolean forwardSubNodeOrder)` Returns an iterator that does a post-order binary tree traversal of the added nodes.
`<C> BinaryTreeNode.CachingIterator<? extends AddressTrie.TrieNode<E>,E,C>`	`containingFirstAllNodeIterator(boolean forwardSubNodeOrder)` Returns an iterator that does a pre-order binary tree traversal.
`<C> BinaryTreeNode.CachingIterator<? extends AddressTrie.TrieNode<E>,E,C>`	`containingFirstIterator(boolean forwardSubNodeOrder)` Returns an iterator that does a pre-order binary tree traversal of the added nodes.
`boolean`	`contains(E addr)` Returns whether the given address or prefix block subnet is in the trie (as an added element).
`static <E extends Address> E`	`decrement(E addr)` Returns the previous address according to the trie ordering
`Iterator<E>`	`descendingIterator()` Traverses the added node keys in reverse natural tree order.
`Spliterator<E>`	`descendingSpliterator()` Creates a `Spliterator` over the keys of the added nodes in descending natural tree order.
`boolean`	`elementContains(E addr)` Checks if a prefix block subnet or address in the trie contains the given subnet or address.
`AddressTrie.TrieNode<E>`	`elementsContainedBy(E addr)` Checks if a part of this trie is contained by the given prefix block subnet or individual address.
`AddressTrie.TrieNode<E>`	`elementsContaining(E addr)` Finds the added subnets and/or addresses in the trie that contain the given individual address or prefix block subnet.
`boolean`	`equals(Object o)` Returns whether the given argument is a trie with a set of nodes that equal the set of nodes in this trie
`AddressTrie.TrieNode<E>`	`firstAddedNode()` Returns the added node with the first (lowest valued) key, or null if there are no added entries in this trie or subtrie
`AddressTrie.TrieNode<E>`	`firstNode()` Returns the node with the first (lowest valued) key, whether the node is added or not
`E`	`floor(E addr)` Returns the highest added address less than or equal to the given address.
`AddressTrie.TrieNode<E>`	`floorAddedNode(E addr)` Returns the added node whose address is the highest address less than or equal to the given address.
`Comparator<E>`	`getComparator()` Returns a comparator for the trie order
`AddressTrie.TrieNode<E>`	`getNode(E addr)` Gets the node corresponding to the given address, returns null if not such element exists.
`AddressTrie.TrieNode<E>`	`getRoot()` Returns the root of this trie
`int`	`hashCode()`
`E`	`higher(E addr)` Returns the lowest added address strictly greater than the given address.
`AddressTrie.TrieNode<E>`	`higherAddedNode(E addr)` Returns the added node whose address is the lowest address strictly greater than the given address.
`static <E extends Address> E`	`increment(E addr)` Returns the next address according to the trie ordering
`boolean`	`isEmpty()` Returns true if there are not any added nodes within this tree
`Iterator<E>`	`iterator()` Traverses the added node keys in natural tree order.
`AddressTrie.TrieNode<E>`	`lastAddedNode()` Returns the added node with the last (highest valued) key, or null if there are no added elements in this trie or subtrie
`AddressTrie.TrieNode<E>`	`lastNode()` Returns the node with the last (highest valued) key, whether the node is added or not
`E`	`longestPrefixMatch(E addr)` Of all the added subnets or address whose prefix matches the given address, returns the one with the longest prefix.
`AddressTrie.TrieNode<E>`	`longestPrefixMatchNode(E addr)` Finds the containing subnet or address in the trie with the smallest subnet size, which is equivalent to finding the subnet or address with the longest matching prefix.
`E`	`lower(E addr)` Returns the highest added address strictly less than the given address.
`AddressTrie.TrieNode<E>`	`lowerAddedNode(E addr)` Returns the added node whose address is the highest address strictly less than the given address.
`Iterator<? extends AddressTrie.TrieNode<E>>`	`nodeIterator(boolean forward)` Iterates through the added nodes in forward or reverse natural tree order.
`int`	`nodeSize()` Returns the number of nodes in the trie, which is more than the number of added elements.
`Spliterator<? extends AddressTrie.TrieNode<E>>`	`nodeSpliterator(boolean forward)` Creates a `Spliterator` over the added nodes in forward or reverse natural tree order.
`boolean`	`remove(E addr)` Removes the given single address or prefix block subnet from the trie.
`AddressTrie.TrieNode<E>`	`removeElementsContainedBy(E addr)` Removes any single address or prefix block subnet from the trie that is contained in the given individual address or prefix block subnet.
`E`	`shortestPrefixMatch(E addr)` Of all the added subnets or address whose prefix matches the given address, returns the one with the shortest prefix.
`AddressTrie.TrieNode<E>`	`shortestPrefixMatchNode(E addr)` Finds the containing subnet or address in the trie with the largest subnet size, which is equivalent to finding the subnet or address with the shortest matching prefix.
`int`	`size()` Returns the number of elements in the tree.
`Spliterator<E>`	`spliterator()` Creates a `Spliterator` over the keys of the added nodes in natural tree order.
`abstract String`	`toAddedNodesTreeString()` Provides a flattened version of the trie showing only the contained added nodes and their containment structure, which is non-binary.
`String`	`toString()` Returns a visual representation of the tree with one node per line.
`String`	`toString(boolean withNonAddedKeys)` Returns a visual representation of the tree with one node per line, with or without the non-added keys.
`static String`	`toString(boolean withNonAddedKeys, AddressTrie<?>... tries)` Produces a visual representation of the given tries joined by a single root node, with one node per line.

Methods inherited from class java.lang.Object
getClass, notify, notifyAll, wait, wait, wait

Methods inherited from interface inet.ipaddr.format.util.AddressTrieOps
getAddedNode

Methods inherited from interface java.lang.Iterable
forEach

- Method Detail
  - increment
```
public static <E extends Address> E increment(E addr)
```
    Returns the next address according to the trie ordering
    
    Type Parameters:
    
    E -
    
    Parameters:
    
    addr -
    
    Returns:
  - decrement
```
public static <E extends Address> E decrement(E addr)
```
    Returns the previous address according to the trie ordering
    
    Type Parameters:
    
    E -
    
    Parameters:
    
    addr -
    
    Returns:
  - isEmpty
```
public boolean isEmpty()
```
    Returns true if there are not any added nodes within this tree
  - nodeSize
```
public int nodeSize()
```
    Returns the number of nodes in the trie, which is more than the number of added elements.
    
    Returns:
  - size
```
public int size()
```
    Returns the number of elements in the tree. Only nodes for which BinaryTreeNode.isAdded() returns true are counted. When zero is returned, isEmpty() returns true.
    
    Returns:
  - add
```
public boolean add(E addr)
```
    Description copied from interface: AddressTrieOps.AddressTrieAddOps
    
    Adds the given single address or prefix block subnet to the trie.
    If the given address is not a single address nor prefix block, then this method throws IllegalArgumentException.
    If not a single address nor prefix block, the Partition class can be used to convert the address before calling this method. Given a subnet s of type E and a trie of type AddressTrie<E>, such as IPv4Address and IPv4AddressTrie, you can convert and add the spanning prefix blocks with Partition.partitionWithSpanningBlocks(s).predicateForEach(trie::add), or you can convert and add using a single max block size with Partition.partitionWithSingleBlockSize(s).predicateForEach(trie::add).
    Returns true if the prefix block or address was inserted, false if already in the trie.
    
    Returns:
  - addNode
```
public AddressTrie.TrieNode<E> addNode(E addr)
```
    Description copied from interface: AddressTrieOps.AddressTrieAddOps
    
    Adds the given single address or prefix block subnet to the trie, if not already there.
    If the given address is not a single address nor prefix block, then this method throws IllegalArgumentException.
    If not a single address nor prefix block, the Partition class can be used to convert the address before calling this method. See AddressTrieOps.AddressTrieAddOps.add(Address) for more details.
    Returns the node for the added address, whether it was already in the trie or not.
    If you wish to know whether the node was already there when adding, use AddressTrieOps.AddressTrieAddOps.add(Address), or before adding you can use AddressTrieOps.getAddedNode(Address)
    
    Returns:
  - constructAddedNodesTree
```
public abstract inet.ipaddr.format.util.AddedTreeBase<E,? extends inet.ipaddr.format.util.AddressTrie.SubNodesMapping<E,? extends inet.ipaddr.format.util.AddressTrie.SubNodesMapping<E,?>>> constructAddedNodesTree()
```
    Provides an associative trie in which the root and each added node are mapped to a list of their respective direct added nodes. This trie provides an alternative non-binary tree structure of the added nodes. It is used by toAddedNodesTreeString() to produce a string showing the alternative structure. If there are no non-added nodes in this trie, then the alternative tree structure provided by this method is the same as the original trie.
    
    Returns:
  - toAddedNodesTreeString
```
public abstract String toAddedNodesTreeString()
```
    Provides a flattened version of the trie showing only the contained added nodes and their containment structure, which is non-binary. The root node is included, which may or may not be added.
    See constructAddedNodesTree()
    
    Returns:
  - addTrie
```
public AddressTrie.TrieNode<E> addTrie(AddressTrie.TrieNode<E> trie)
```
    Description copied from interface: AddressTrieOps.AddressTrieAddOps
    
    Adds nodes matching the given sub-root node and all of its sub-nodes to the trie, if not already there.
    For each added in the given node that does not exist in the trie, a copy of each node will be made that matches the trie type (associative or not), and the copy will be inserted into the trie.
    The node type need not match the node type of the trie, although the address type/version E must match. You can add associative nodes to tries with this method but associated values will all be null. If you want to preserve the values, use AssociativeAddressTriePutOps#putTrie(AssociativeTrieNode) instead.
    When adding one trie to another, this method is more efficient than adding each node of the first trie individually. When using this method, searching for the location to add sub-nodes starts from the inserted parent node.
    Returns the node corresponding to the given sub-root node, whether it was already in the trie or not.
    
    Returns:
  - contains
```
public boolean contains(E addr)
```
    Description copied from interface: AddressTrieOps
    
    Returns whether the given address or prefix block subnet is in the trie (as an added element).
    If the given address is not a single address nor prefix block, then this method throws IllegalArgumentException.
    If not a single address nor prefix block, the Partition class can be used to convert the address before calling this method. See AddressTrieOps.AddressTrieAddOps.add(Address) for more details.
    Returns true if the prefix block or address address exists already in the trie, false otherwise.
    Use AddressTrieOps.getAddedNode(Address) to get the node for the address rather than just checking for its existence.
    
    Returns:
  - remove
```
public boolean remove(E addr)
```
    Description copied from interface: AddressTrieOps
    
    Removes the given single address or prefix block subnet from the trie.
    Removing an element will not remove contained elements (nodes for contained blocks and addresses).
    If the given address is not a single address nor prefix block, then this method throws IllegalArgumentException.
    If not a single address nor prefix block, the Partition class can be used to convert the address before calling this method. See AddressTrieOps.AddressTrieAddOps.add(Address) for more details.
    Returns true if the prefix block or address was removed, false if not already in the trie.
    You can also remove by calling AddressTrieOps.getAddedNode(Address) to get the node and then calling BinaryTreeNode.remove() on the node.
    When an address is removed, the corresponding node may remain in the trie if it remains a subnet block for two sub-nodes. If the corresponding node can be removed from the trie, it will be.
    
    Returns:
    
    See Also:
    
    AddressTrieOps.removeElementsContainedBy(Address)
  - removeElementsContainedBy
```
public AddressTrie.TrieNode<E> removeElementsContainedBy(E addr)
```
    Description copied from interface: AddressTrieOps
    
    Removes any single address or prefix block subnet from the trie that is contained in the given individual address or prefix block subnet.
    Goes further than AddressTrieOps.remove(Address), not requiring a match to an inserted node, and also removing all the sub-nodes of any removed node or sub-node.
    For example, after inserting 1.2.3.0 and 1.2.3.1, passing 1.2.3.0/31 to AddressTrieOps.removeElementsContainedBy(Address) will remove them both, while AddressTrieOps.remove(Address) will remove nothing. After inserting 1.2.3.0/31, then #remove(Address) will remove 1.2.3.0/31, but will leave 1.2.3.0 and 1.2.3.1 in the trie.
    It cannot partially delete a node, such as deleting a single address from a prefix block represented by a node. It can only delete the whole node if the whole address or block represented by that node is contained in the given address or block.
    If the given address is not a single address nor prefix block, then this method throws IllegalArgumentException.
    If not a single address nor prefix block, the Partition class can be used to convert the address before calling this method. See AddressTrieOps.AddressTrieAddOps.add(Address) for more details.
    Returns the root node of the subtrie that was removed from the trie, or null if nothing was removed.
    
    Returns:
  - elementsContainedBy
```
public AddressTrie.TrieNode<E> elementsContainedBy(E addr)
```
    Description copied from interface: AddressTrieOps
    
    Checks if a part of this trie is contained by the given prefix block subnet or individual address.
    If the given address is not a single address nor prefix block, then this method throws IllegalArgumentException.
    If not a single address nor prefix block, the Partition class can be used to convert the address before calling this method. See AddressTrieOps.AddressTrieAddOps.add(Address) for more details.
    Returns the root node of the contained subtrie, or null if no subtrie is contained. The node returned need not be an "added" node, see BinaryTreeNode.isAdded() for more details on added nodes. The returned subtrie is backed by this trie, so changes in this trie are reflected in those nodes and vice-versa.
    
    Returns:
  - elementsContaining
```
public AddressTrie.TrieNode<E> elementsContaining(E addr)
```
    Description copied from interface: AddressTrieOps
    
    Finds the added subnets and/or addresses in the trie that contain the given individual address or prefix block subnet.
    If the given address is not a single address nor prefix block, then this method throws IllegalArgumentException.
    If not a single address nor prefix block, the Partition class can be used to convert the address before calling this method. See AddressTrieOps.AddressTrieAddOps.add(Address) for more details.
    Returns a list of the nodes for prefix block subnets and addresses from the trie that contain the address or block. The list consists only of added nodes, see BinaryTreeNode.isAdded() for more details on added nodes. The list is constructed as a trie in which each parent node has only one sub-node.
    Use AddressTrieOps.elementContains(Address) to check for the existence of a containing address.
    
    Returns:
  - longestPrefixMatch
```
public E longestPrefixMatch(E addr)
```
    Description copied from interface: AddressTrieOps
    
    Of all the added subnets or address whose prefix matches the given address, returns the one with the longest prefix. This is equivalent to finding the containing subnet or address with the smallest subnet size.
    If the given address is not a single address nor prefix block, then this method throws IllegalArgumentException.
    If not a single address nor prefix block, the Partition class can be used to convert the address before calling this method. See AddressTrieOps.AddressTrieAddOps.add(Address) for more details.
    Returns null if no added subnet or address contains the given argument.
    Use AddressTrieOps.elementContains(Address) to check for the existence of a containing address.
    To get all the containing addresses (subnets with matching prefix), use AddressTrieOps.elementsContaining(Address).
    To get the node corresponding to the result of this method, use AddressTrieOps.longestPrefixMatchNode(Address)
    
    Returns:
  - longestPrefixMatchNode
```
public AddressTrie.TrieNode<E> longestPrefixMatchNode(E addr)
```
    Description copied from interface: AddressTrieOps
    
    Finds the containing subnet or address in the trie with the smallest subnet size, which is equivalent to finding the subnet or address with the longest matching prefix. Returns the node corresponding to that subnet.
    If the given address is not a single address nor prefix block, then this method throws IllegalArgumentException.
    If not a single address nor prefix block, the Partition class can be used to convert the address before calling this method. See AddressTrieOps.AddressTrieAddOps.add(Address) for more details.
    Returns null if no added subnet or address contains the given argument.
    Use AddressTrieOps.elementContains(Address) to check for the existence of a containing address.
    To get all the containing addresses, use AddressTrieOps.elementsContaining(Address).
    Use AddressTrieOps.longestPrefixMatch(Address) to get the address corresponding to the result of this method.
    
    Returns:
  - shortestPrefixMatch
```
public E shortestPrefixMatch(E addr)
```
    Description copied from interface: AddressTrieOps
    
    Of all the added subnets or address whose prefix matches the given address, returns the one with the shortest prefix. This is equivalent to finding the containing subnet or address with the largest subnet size.
    If the given address is not a single address nor prefix block, then this method throws IllegalArgumentException.
    If not a single address nor prefix block, the Partition class can be used to convert the address before calling this method. See AddressTrieOps.AddressTrieAddOps.add(Address) for more details.
    Returns null if no added subnet or address contains the given argument.
    Use AddressTrieOps.elementContains(Address) to check for the existence of a containing address.
    To get all the containing addresses (subnets with matching prefix), use AddressTrieOps.elementsContaining(Address).
    To get the node corresponding to the result of this method, use AddressTrieOps.shortestPrefixMatchNode(Address)
    
    Returns:
  - shortestPrefixMatchNode
```
public AddressTrie.TrieNode<E> shortestPrefixMatchNode(E addr)
```
    Description copied from interface: AddressTrieOps
    
    Finds the containing subnet or address in the trie with the largest subnet size, which is equivalent to finding the subnet or address with the shortest matching prefix. Returns the node corresponding to that subnet.
    If the given address is not a single address nor prefix block, then this method throws IllegalArgumentException.
    If not a single address nor prefix block, the Partition class can be used to convert the address before calling this method. See AddressTrieOps.AddressTrieAddOps.add(Address) for more details.
    Returns null if no added subnet or address contains the given argument.
    Use AddressTrieOps.elementContains(Address) to check for the existence of a containing address.
    To get all the containing addresses, use AddressTrieOps.elementsContaining(Address).
    Use AddressTrieOps.shortestPrefixMatch(Address) to get the address corresponding to the result of this method.
    
    Returns:
  - elementContains
```
public boolean elementContains(E addr)
```
    Description copied from interface: AddressTrieOps
    
    Checks if a prefix block subnet or address in the trie contains the given subnet or address.
    If the given address is not a single address nor prefix block, then this method throws IllegalArgumentException.
    If not a single address nor prefix block, the Partition class can be used to convert the address before calling this method. See AddressTrieOps.AddressTrieAddOps.add(Address) for more details.
    Returns true if the subnet or address is contained by a trie element, false otherwise.
    To get all the containing addresses, use AddressTrieOps.elementsContaining(Address).
    
    Returns:
  - getNode
```
public AddressTrie.TrieNode<E> getNode(E addr)
```
    Description copied from interface: AddressTrieOps
    
    Gets the node corresponding to the given address, returns null if not such element exists.
    If added is true, returns only nodes representing added elements, otherwise returns any node, including a prefix block that was not added.
    If the given address is not a single address nor prefix block, then this method throws IllegalArgumentException.
    If not a single address nor prefix block, the Partition class can be used to convert the address before calling this method. See AddressTrieOps.AddressTrieAddOps.add(Address) for more details.
    
    Returns:
    
    See Also:
    
    AddressTrieOps.contains(Address)
  - allNodeIterator
```
public Iterator<? extends AddressTrie.TrieNode<E>> allNodeIterator(boolean forward)
```
    Description copied from interface: TreeOps
    
    Iterates through the nodes (not just the added nodes) in forward or reverse tree order.
    
    See TreeOps for more details on the ordering. This iterator supports the Iterator.remove() operation.
    
    Parameters:
    
    forward - if true, goes in ascending order, otherwise descending
    
    Returns:
  - blockSizeNodeIterator
```
public Iterator<? extends AddressTrie.TrieNode<E>> blockSizeNodeIterator(boolean lowerSubNodeFirst)
```
    Iterates the added nodes in the trie, ordered by keys from largest prefix blocks to smallest, and then to individual addresses.
    This iterator supports the Iterator.remove() operation.
    
    Parameters:
    
    lowerSubNodeFirst - if true, for blocks of equal size the lower is first, otherwise the reverse order
    
    Returns:
  - blockSizeAllNodeIterator
```
public Iterator<? extends AddressTrie.TrieNode<E>> blockSizeAllNodeIterator(boolean lowerSubNodeFirst)
```
    Iterates all nodes in the trie, ordered by keys from largest prefix blocks to smallest, and then to individual addresses.
    This iterator supports the Iterator.remove() operation.
    
    Parameters:
    
    lowerSubNodeFirst - if true, for blocks of equal size the lower is first, otherwise the reverse order
    
    Returns:
  - blockSizeCachingAllNodeIterator
```
public <C> BinaryTreeNode.CachingIterator<? extends AddressTrie.TrieNode<E>,E,C> blockSizeCachingAllNodeIterator()
```
    Iterates all nodes, ordered by keys from largest prefix blocks to smallest, and then to individual addresses.
    This iterator supports the Iterator.remove() operation.
    
    Returns:
  - containingFirstIterator
```
public <C> BinaryTreeNode.CachingIterator<? extends AddressTrie.TrieNode<E>,E,C> containingFirstIterator(boolean forwardSubNodeOrder)
```
    Description copied from interface: TreeOps
    
    Returns an iterator that does a pre-order binary tree traversal of the added nodes. All added nodes will be visited before their added sub-nodes. For an address trie this means added containing subnet blocks will be visited before their added contained addresses and subnet blocks.
    This iterator supports the Iterator.remove() operation.
    Once a given node is visited, the iterator allows you to cache an object corresponding to the lower or upper sub-node that can be retrieved when you later visit that sub-node.
    Objects are cached only with nodes to be visited. So for this iterator that means an object will be cached with the first added lower or upper sub-node, the next lower or upper sub-node to be visited, which is not necessarily the direct lower or upper sub-node of a given node.
    The caching allows you to provide iteration context from a parent to its sub-nodes when iterating. The caching and retrieval is done in constant-time and linear space (proportional to tree size).
    See TreeOps for more details on the ordering.
    
    Parameters:
    
    forwardSubNodeOrder - if true, a left sub-node will be visited before the right sub-node of the same parent node.
    
    Returns:
  - containingFirstAllNodeIterator
```
public <C> BinaryTreeNode.CachingIterator<? extends AddressTrie.TrieNode<E>,E,C> containingFirstAllNodeIterator(boolean forwardSubNodeOrder)
```
    Description copied from interface: TreeOps
    Returns an iterator that does a pre-order binary tree traversal. All nodes will be visited before their sub-nodes. For an address trie this means containing subnet blocks will be visited before their contained addresses and subnet blocks.
    This iterator supports the Iterator.remove() operation.
    Once a given node is visited, the iterator allows you to cache an object corresponding to the lower or upper sub-node that can be retrieved when you later visit that sub-node. That allows you to provide iteration context from a parent to its sub-nodes when iterating. The caching and retrieval is done in constant-time and linear space (proportional to tree size).
    Here is an example showing usage of the caching. Consider this recursive code doing a pre-order traversal:
```
IPv6AddressTrie ipv6Tree = ...;
visitRecursive(ipv6Tree.getRoot(), null);

static <E> void visitRecursive(BinaryTreeNode<E> node, String direction) {
        if(direction == null) {
                direction = "root";
        }
        System.out.println("visited " + direction + " " + node);
        BinaryTreeNode<E> sub = node.getLowerSubNode();
        if(sub != null) {
                visitRecursive(sub, direction + " left");
        }
        sub = node.getUpperSubNode();
        if(sub != null) {
                visitRecursive(sub, direction + " right");
        }
}
```
    The following iterative code provides the same functionality:
```
visitIterative(ipv6Tree.getRoot());

static <E> void visitIterative(BinaryTreeNode<E> node) {    
        CachingIterator<? extends BinaryTreeNode<E>, E, String>iterator = node.containingFirstAllNodeIterator(true);
        while(iterator.hasNext()) {
                BinaryTreeNode<E> next = iterator.next();
                String direction = iterator.getCached();
                if(direction == null) {
                        direction = "root";
                }
                System.out.println("visited " + direction + " " + next);
                iterator.cacheWithLowerSubNode(direction + " left");
                iterator.cacheWithUpperSubNode(direction + " right");
        }
}
 
```
    See TreeOps for more details on the ordering.
    Parameters:
    
    forwardSubNodeOrder - if true, a left sub-node will be visited before the right sub-node of the same parent node.
    
    Returns:
  - containedFirstIterator
```
public Iterator<? extends AddressTrie.TrieNode<E>> containedFirstIterator(boolean forwardSubNodeOrder)
```
    Description copied from interface: TreeOps
    
    Returns an iterator that does a post-order binary tree traversal of the added nodes. All added sub-nodes will be visited before their parent nodes. For an address trie this means contained addresses and subnets will be visited before their containing subnet blocks.
    This iterator supports the Iterator.remove() operation.
    See TreeOps for more details on the ordering.
    
    Parameters:
    
    forwardSubNodeOrder - if true, a left sub-node will be visited before the right sub-node of the same parent node.
    
    Returns:
  - containedFirstAllNodeIterator
```
public Iterator<? extends AddressTrie.TrieNode<E>> containedFirstAllNodeIterator(boolean forwardSubNodeOrder)
```
    Description copied from interface: TreeOps
    
    Returns an iterator that does a post-order binary tree traversal. All sub-nodes will be visited before their parent nodes. For an address trie this means contained addresses and subnets will be visited before their containing subnet blocks.
    This iterator does not support the Iterator.remove() operation. If Iterator.remove() is called it will throw UnsupportedOperationException.
    See TreeOps for more details on the ordering.
    
    Parameters:
    
    forwardSubNodeOrder - if true, a left sub-node will be visited before the right sub-node of the same parent node.
    
    Returns:
  - spliterator
```
public Spliterator<E> spliterator()
```
    Description copied from interface: TreeOps
    
    Creates a Spliterator over the keys of the added nodes in natural tree order.
    See TreeOps for more details on the ordering.
  - descendingSpliterator
```
public Spliterator<E> descendingSpliterator()
```
    Description copied from interface: TreeOps
    
    Creates a Spliterator over the keys of the added nodes in descending natural tree order.
    See TreeOps for more details on the ordering.
    
    Returns:
  - nodeSpliterator
```
public Spliterator<? extends AddressTrie.TrieNode<E>> nodeSpliterator(boolean forward)
```
    Description copied from interface: TreeOps
    
    Creates a Spliterator over the added nodes in forward or reverse natural tree order.
    See TreeOps for more details on the ordering.
    
    Parameters:
    
    forward - if true, goes in ascending order, otherwise descending
    
    Returns:
  - allNodeSpliterator
```
public Spliterator<? extends AddressTrie.TrieNode<E>> allNodeSpliterator(boolean forward)
```
    Description copied from interface: TreeOps
    
    Creates a Spliterator over the nodes in forward or reverse natural tree order.
    See TreeOps for more details on the ordering.
    
    Parameters:
    
    forward - if true, goes in ascending order, otherwise descending
    
    Returns:
  - nodeIterator
```
public Iterator<? extends AddressTrie.TrieNode<E>> nodeIterator(boolean forward)
```
    Description copied from interface: TreeOps
    
    Iterates through the added nodes in forward or reverse natural tree order.
    This iterator supports the Iterator.remove() operation.
    See TreeOps for more details on the ordering.
    
    Parameters:
    
    forward - if true, goes in ascending order, otherwise descending
    
    Returns:
  - firstNode
```
public AddressTrie.TrieNode<E> firstNode()
```
    Description copied from interface: AddressTrieOps
    
    Returns the node with the first (lowest valued) key, whether the node is added or not
    
    Returns:
  - firstAddedNode
```
public AddressTrie.TrieNode<E> firstAddedNode()
```
    Description copied from interface: AddressTrieOps
    
    Returns the added node with the first (lowest valued) key, or null if there are no added entries in this trie or subtrie
    
    Returns:
  - lastNode
```
public AddressTrie.TrieNode<E> lastNode()
```
    Description copied from interface: AddressTrieOps
    
    Returns the node with the last (highest valued) key, whether the node is added or not
    
    Returns:
  - lastAddedNode
```
public AddressTrie.TrieNode<E> lastAddedNode()
```
    Description copied from interface: AddressTrieOps
    
    Returns the added node with the last (highest valued) key, or null if there are no added elements in this trie or subtrie
    
    Returns:
  - getComparator
```
public Comparator<E> getComparator()
```
    Returns a comparator for the trie order
    
    Returns:
  - asSet
```
public AddressTrieSet<E> asSet()
```
    Returns a java.util.NavigableSet that uses this as the backing data structure. Added elements of this trie are the elements in the set.
    
    Returns:
  - getRoot
```
public AddressTrie.TrieNode<E> getRoot()
```
    Returns the root of this trie
    
    Returns:
  - lowerAddedNode
```
public AddressTrie.TrieNode<E> lowerAddedNode(E addr)
```
    Description copied from interface: AddressTrieOps
    
    Returns the added node whose address is the highest address strictly less than the given address.
    
    Returns:
  - lower
```
public E lower(E addr)
```
    Description copied from interface: AddressTrieOps
    
    Returns the highest added address strictly less than the given address.
    
    Returns:
  - floorAddedNode
```
public AddressTrie.TrieNode<E> floorAddedNode(E addr)
```
    Description copied from interface: AddressTrieOps
    
    Returns the added node whose address is the highest address less than or equal to the given address.
    
    Returns:
  - floor
```
public E floor(E addr)
```
    Description copied from interface: AddressTrieOps
    
    Returns the highest added address less than or equal to the given address.
    
    Returns:
  - higherAddedNode
```
public AddressTrie.TrieNode<E> higherAddedNode(E addr)
```
    Description copied from interface: AddressTrieOps
    
    Returns the added node whose address is the lowest address strictly greater than the given address.
    
    Returns:
  - higher
```
public E higher(E addr)
```
    Description copied from interface: AddressTrieOps
    
    Returns the lowest added address strictly greater than the given address.
    
    Returns:
  - ceilingAddedNode
```
public AddressTrie.TrieNode<E> ceilingAddedNode(E addr)
```
    Description copied from interface: AddressTrieOps
    
    Returns the added node whose address is the lowest address greater than or equal to the given address.
    
    Returns:
  - ceiling
```
public E ceiling(E addr)
```
    Description copied from interface: AddressTrieOps
    
    Returns the lowest added address greater than or equal to the given address.
    
    Returns:
  - clear
```
public void clear()
```
    Removes all added nodes from the tree, after which isEmpty() will return true
  - clone
```
public AddressTrie<E> clone()
```
    Copies the trie, but not the keys or values.
  - equals
```
public boolean equals(Object o)
```
    Returns whether the given argument is a trie with a set of nodes that equal the set of nodes in this trie
  - toString
```
public String toString()
```
    Returns a visual representation of the tree with one node per line.
  - toString
```
public String toString(boolean withNonAddedKeys)
```
    Returns a visual representation of the tree with one node per line, with or without the non-added keys.
  - toString
```
public static String toString(boolean withNonAddedKeys,
                              AddressTrie<?>... tries)
```
    Produces a visual representation of the given tries joined by a single root node, with one node per line.
    
    Parameters:
    
    withNonAddedKeys -
    
    tries -
    
    Returns:
  - iterator
```
public Iterator<E> iterator()
```
    Description copied from interface: TreeOps
    
    Traverses the added node keys in natural tree order.
    See TreeOps for more details on the ordering.
    
    Specified by:
    
    iterator in interface TreeOps<E extends Address>
    
    Specified by:
    
    iterator in interface Iterable<E extends Address>
  - descendingIterator
```
public Iterator<E> descendingIterator()
```
    Description copied from interface: TreeOps
    
    Traverses the added node keys in reverse natural tree order.
    See TreeOps for more details on the ordering.
    
    Specified by:
    
    descendingIterator in interface TreeOps<E extends Address>
    
    Returns:
  - hashCode
```
public int hashCode()
```
    Overrides:
    
    hashCode in class Object

Class AddressTrie<E extends Address>

Nested Class Summary

Nested classes/interfaces inherited from interface inet.ipaddr.format.util.AddressTrieOps

Method Summary

Methods inherited from class java.lang.Object

Methods inherited from interface inet.ipaddr.format.util.AddressTrieOps

Methods inherited from interface java.lang.Iterable

Method Detail

increment

decrement

isEmpty

nodeSize

size

add

addNode

constructAddedNodesTree

toAddedNodesTreeString

addTrie

contains

remove

removeElementsContainedBy

elementsContainedBy

elementsContaining

longestPrefixMatch

longestPrefixMatchNode

shortestPrefixMatch

shortestPrefixMatchNode

elementContains

getNode

allNodeIterator

blockSizeNodeIterator

blockSizeAllNodeIterator

blockSizeCachingAllNodeIterator

containingFirstIterator

containingFirstAllNodeIterator

containedFirstIterator

containedFirstAllNodeIterator

spliterator

descendingSpliterator

nodeSpliterator

allNodeSpliterator

nodeIterator

firstNode

firstAddedNode

lastNode

lastAddedNode

getComparator

asSet

getRoot

lowerAddedNode

lower

floorAddedNode

floor

higherAddedNode

higher

ceilingAddedNode

ceiling

clear

clone

equals

toString

toString

toString

iterator

descendingIterator

hashCode