- Type Parameters:
E
-
- All Superinterfaces:
Cloneable
,Iterable<E>
,Serializable
,TreeOps<E>
- All Known Subinterfaces:
AddressTrieOps.AddressTrieAddOps<E>
,AddressTrieOps.AssociativeAddressTrieOps<K,
,V> AddressTrieOps.AssociativeAddressTriePutOps<K,
V>
- All Known Implementing Classes:
AddressTrie
,AddressTrie.TrieNode
,AssociativeAddressTrie
,AssociativeAddressTrie.AssociativeTrieNode
,IPv4AddressAssociativeTrie
,IPv4AddressAssociativeTrie.IPv4AssociativeTrieNode
,IPv4AddressTrie
,IPv4AddressTrie.IPv4TrieNode
,IPv6AddressAssociativeTrie
,IPv6AddressAssociativeTrie.IPv6AssociativeTrieNode
,IPv6AddressTrie
,IPv6AddressTrie.IPv6TrieNode
,MACAddressAssociativeTrie
,MACAddressAssociativeTrie.MACAssociativeTrieNode
,MACAddressTrie
,MACAddressTrie.MACTrieNode
- Author:
- scfoley
-
Nested Class Summary
Nested ClassesModifier and TypeInterfaceDescriptionstatic interface
AddressTrieOps.AddressTrieAddOps<E extends Address>
Provides an interface to the trie add operations.static interface
Provides an interface to the associative trie operations.static interface
Provides an interface to the associative trie put operations. -
Method Summary
Modifier and TypeMethodDescriptionIterator
<? 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 aSpliterator
over the nodes in forward or reverse natural tree order.ceilingAddedNode
(E addr) Returns the added node whose address is the lowest address greater than or equal to the given address.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
Returns whether the given address or prefix block subnet is in the trie (as an added element).boolean
elementContains
(E addr) Checks if a prefix block subnet or address in the trie contains the given subnet or address.elementsContainedBy
(E addr) Checks if a part of this trie is contained by the given prefix block subnet or individual address.elementsContaining
(E addr) Finds the added subnets and/or addresses in the trie that contain the given individual address or prefix block subnet.Returns the added node with the first (lowest valued) key, or null if there are no added entries in this trie or subtrieReturns the node with the first (lowest valued) key, whether the node is added or notfloorAddedNode
(E addr) Returns the added node whose address is the highest address less than or equal to the given address.default AddressTrie.TrieNode
<E> getAddedNode
(E addr) Gets trie nodes representing added elements.Gets the node corresponding to the given address, returns null if not such element exists.higherAddedNode
(E addr) Returns the added node whose address is the lowest address strictly greater than the given address.Returns the added node with the last (highest valued) key, or null if there are no added elements in this trie or subtrielastNode()
Returns the node with the last (highest valued) key, whether the node is added or notlongestPrefixMatch
(E addr) Of all the added subnets or address whose prefix matches the given address, returns the one with the longest prefix.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.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.Spliterator
<? extends AddressTrie.TrieNode<E>> nodeSpliterator
(boolean forward) Creates aSpliterator
over the added nodes in forward or reverse natural tree order.boolean
Removes the given single address or prefix block subnet from the trie.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.Methods inherited from interface inet.ipaddr.format.util.TreeOps
descendingIterator, descendingSpliterator, iterator, spliterator
-
Method Details
-
getNode
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. SeeAddressTrieOps.AddressTrieAddOps.add(Address)
for more details.- Parameters:
addr
-- Returns:
- See Also:
-
getAddedNode
Gets trie nodes representing added elements.Use
contains(Address)
to check for the existence of a given address in the trie, as well asgetNode(Address)
to search for all nodes including those not-added but also auto-generated nodes for subnet blocks.- Parameters:
addr
-- Returns:
-
elementContains
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. SeeAddressTrieOps.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
elementsContaining(Address)
.- Parameters:
addr
-- Returns:
-
contains
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. SeeAddressTrieOps.AddressTrieAddOps.add(Address)
for more details.Returns true if the prefix block or address address exists already in the trie, false otherwise.
Use
getAddedNode(Address)
to get the node for the address rather than just checking for its existence.- Parameters:
addr
-- Returns:
-
remove
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. SeeAddressTrieOps.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
getAddedNode(Address)
to get the node and then callingBinaryTreeNode.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.
- Parameters:
addr
-- Returns:
- See Also:
-
removeElementsContainedBy
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
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
removeElementsContainedBy(Address)
will remove them both, whileremove(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. SeeAddressTrieOps.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.
- Parameters:
addr
-- Returns:
-
elementsContainedBy
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. SeeAddressTrieOps.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.- Parameters:
addr
-- Returns:
-
elementsContaining
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. SeeAddressTrieOps.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
elementContains(Address)
to check for the existence of a containing address.- Parameters:
addr
-- Returns:
-
longestPrefixMatchNode
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. SeeAddressTrieOps.AddressTrieAddOps.add(Address)
for more details.Returns null if no added subnet or address contains the given argument.
Use
elementContains(Address)
to check for the existence of a containing address.
To get all the containing addresses, useelementsContaining(Address)
.
UselongestPrefixMatch(Address)
to get the address corresponding to the result of this method.- Parameters:
addr
-- Returns:
-
longestPrefixMatch
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. SeeAddressTrieOps.AddressTrieAddOps.add(Address)
for more details.Returns null if no added subnet or address contains the given argument.
Use
elementContains(Address)
to check for the existence of a containing address.
To get all the containing addresses (subnets with matching prefix), useelementsContaining(Address)
.
To get the node corresponding to the result of this method, uselongestPrefixMatchNode(Address)
- Parameters:
addr
-- Returns:
-
nodeIterator
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.- Specified by:
nodeIterator
in interfaceTreeOps<E extends Address>
- Parameters:
forward
- if true, goes in ascending order, otherwise descending- Returns:
-
allNodeIterator
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 theIterator.remove()
operation.- Specified by:
allNodeIterator
in interfaceTreeOps<E extends Address>
- Parameters:
forward
- if true, goes in ascending order, otherwise descending- Returns:
-
containingFirstIterator
<C> BinaryTreeNode.CachingIterator<? extends AddressTrie.TrieNode<E>,E, containingFirstIteratorC> (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.- Specified by:
containingFirstIterator
in interfaceTreeOps<E extends Address>
- Parameters:
forwardSubNodeOrder
- if true, a left sub-node will be visited before the right sub-node of the same parent node.- Returns:
-
containingFirstAllNodeIterator
<C> BinaryTreeNode.CachingIterator<? extends AddressTrie.TrieNode<E>,E, containingFirstAllNodeIteratorC> (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:
The following iterative code provides the same functionality: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"); } }
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.- Specified by:
containingFirstAllNodeIterator
in interfaceTreeOps<E extends Address>
- Parameters:
forwardSubNodeOrder
- if true, a left sub-node will be visited before the right sub-node of the same parent node.- Returns:
-
containedFirstIterator
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.- Specified by:
containedFirstIterator
in interfaceTreeOps<E extends Address>
- Parameters:
forwardSubNodeOrder
- if true, a left sub-node will be visited before the right sub-node of the same parent node.- Returns:
-
containedFirstAllNodeIterator
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. IfIterator.remove()
is called it will throwUnsupportedOperationException
.See
TreeOps
for more details on the ordering.- Specified by:
containedFirstAllNodeIterator
in interfaceTreeOps<E extends Address>
- Parameters:
forwardSubNodeOrder
- if true, a left sub-node will be visited before the right sub-node of the same parent node.- Returns:
-
nodeSpliterator
Description copied from interface:TreeOps
Creates aSpliterator
over the added nodes in forward or reverse natural tree order.See
TreeOps
for more details on the ordering.- Specified by:
nodeSpliterator
in interfaceTreeOps<E extends Address>
- Parameters:
forward
- if true, goes in ascending order, otherwise descending- Returns:
-
allNodeSpliterator
Description copied from interface:TreeOps
Creates aSpliterator
over the nodes in forward or reverse natural tree order.See
TreeOps
for more details on the ordering.- Specified by:
allNodeSpliterator
in interfaceTreeOps<E extends Address>
- Parameters:
forward
- if true, goes in ascending order, otherwise descending- Returns:
-
firstNode
AddressTrie.TrieNode<E> firstNode()Returns the node with the first (lowest valued) key, whether the node is added or not- Returns:
-
lastNode
AddressTrie.TrieNode<E> lastNode()Returns the node with the last (highest valued) key, whether the node is added or not- Returns:
-
firstAddedNode
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- Returns:
-
lastAddedNode
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- Returns:
-
floorAddedNode
Returns the added node whose address is the highest address less than or equal to the given address.- Parameters:
addr
-- Returns:
-
lowerAddedNode
Returns the added node whose address is the highest address strictly less than the given address.- Parameters:
addr
-- Returns:
-
ceilingAddedNode
Returns the added node whose address is the lowest address greater than or equal to the given address.- Parameters:
addr
-- Returns:
-
higherAddedNode
Returns the added node whose address is the lowest address strictly greater than the given address.- Parameters:
addr
-- Returns:
-