- java.lang.Object
-
- inet.ipaddr.format.util.BinaryTreeNode<E>
-
- inet.ipaddr.format.util.AddressTrie.TrieNode<E>
-
- Type Parameters:
E
-
- All Implemented Interfaces:
AddressTrieOps<E>
,TreeOps<E>
,java.io.Serializable
,java.lang.Cloneable
,java.lang.Iterable<E>
- Direct Known Subclasses:
AssociativeAddressTrie.AssociativeTrieNode
,IPv4AddressTrie.IPv4TrieNode
,IPv6AddressTrie.IPv6TrieNode
,MACAddressTrie.MACTrieNode
- Enclosing class:
- AddressTrie<E extends Address>
public abstract static class AddressTrie.TrieNode<E extends Address> extends BinaryTreeNode<E> implements AddressTrieOps<E>
A node for a compact binary prefix trie whose elements are prefix block subnets or addresses,- Author:
- scfoley
- See Also:
- Serialized Form
-
-
Nested Class Summary
-
Nested classes/interfaces inherited from class inet.ipaddr.format.util.BinaryTreeNode
BinaryTreeNode.CachingIterator<N extends BinaryTreeNode<E>,E,C>
-
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 Instance Methods Concrete Methods Modifier and Type Method Description java.util.Iterator<? extends AddressTrie.TrieNode<E>>
allNodeIterator(boolean forward)
Iterates through all the nodes of the sub-tree with this node as the root, in forward or reverse tree order.java.util.Spliterator<? extends AddressTrie.TrieNode<E>>
allNodeSpliterator(boolean forward)
Creates aSpliterator
over the nodes in forward or reverse natural tree order.AddressTrie<E>
asNewTrie()
Creates a new sub-trie, copying the nodes starting with this node as root.java.util.Iterator<? extends AddressTrie.TrieNode<E>>
blockSizeAllNodeIterator(boolean lowerSubNodeFirst)
Iterates all the nodes, ordered by keys from largest prefix blocks to smallest and then to individual addresses, in the sub-trie with this node as the root.<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, in the sub-trie with this node as the root.java.util.Iterator<? extends AddressTrie.TrieNode<E>>
blockSizeNodeIterator(boolean lowerSubNodeFirst)
Iterates the added nodes, ordered by keys from largest prefix blocks to smallest and then to individual addresses, in the sub-trie with this node as the root.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.AddressTrie.TrieNode<E>
clone()
Clones the node.AddressTrie.TrieNode<E>
cloneTree()
Clones the sub-tree starting with this node as root.java.util.Iterator<? extends AddressTrie.TrieNode<E>>
containedFirstAllNodeIterator(boolean forwardSubNodeOrder)
Returns an iterator that does a post-order binary tree traversal.java.util.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.java.util.Iterator<? extends AddressTrie.TrieNode<E>>
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).java.util.Spliterator<E>
descendingSpliterator()
Creates aSpliterator
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(java.lang.Object o)
Returns whether the key values match those of the given nodeAddressTrie.TrieNode<E>
firstAddedNode()
Returns the first (lowest valued) added node in the sub-tree originating from this node, or null if there are no added entries in this tree or sub-treeAddressTrie.TrieNode<E>
firstNode()
Returns the first (lowest valued) node in the sub-tree originating from this node.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.AddressTrie.TrieNode<E>
getLowerSubNode()
Returns the sub node whose address is smallest in valueAddressTrie.TrieNode<E>
getNode(E addr)
Gets the node corresponding to the given address, returns null if not such element exists.AddressTrie.TrieNode<E>
getParent()
Returns the node for the subnet block containing this node.AddressTrie.TrieNode<E>
getUpperSubNode()
Returns the sub-node whose address is largest in valueE
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.AddressTrie.TrieNode<E>
lastAddedNode()
Returns the last (highest valued) added node in the sub-tree originating from this node, or null if there are no added entries in this tree or sub-treeAddressTrie.TrieNode<E>
lastNode()
Returns the last (highest valued) node in the sub-tree originating from this node.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.AddressTrie.TrieNode<E>
nextAddedNode()
Returns the next node in the tree that is an added node, following the tree order, or null if there is no such node.AddressTrie.TrieNode<E>
nextNode()
Returns the node that follows this node following the tree orderjava.util.Iterator<? extends AddressTrie.TrieNode<E>>
nodeIterator(boolean forward)
Iterates through the added nodes of the sub-tree with this node as the root, in forward or reverse tree order.java.util.Spliterator<? extends AddressTrie.TrieNode<E>>
nodeSpliterator(boolean forward)
Creates aSpliterator
over the added nodes in forward or reverse natural tree order.AddressTrie.TrieNode<E>
previousAddedNode()
Returns the previous node in the tree that is an added node, following the tree order in reverse, or null if there is no such node.AddressTrie.TrieNode<E>
previousNode()
Returns the node that precedes this node following the 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.java.util.Spliterator<E>
spliterator()
Creates aSpliterator
over the keys of the added nodes in natural tree order.-
Methods inherited from class inet.ipaddr.format.util.BinaryTreeNode
clear, descendingIterator, getKey, hashCode, isAdded, isEmpty, isLeaf, isRoot, iterator, nodeSize, remove, setAdded, size, toString, toTreeString, treeEquals, treeHashCode
-
Methods inherited from interface inet.ipaddr.format.util.AddressTrieOps
getAddedNode
-
Methods inherited from interface inet.ipaddr.format.util.TreeOps
descendingIterator, iterator
-
-
-
-
Method Detail
-
getParent
public AddressTrie.TrieNode<E> getParent()
Returns the node for the subnet block containing this node.- Overrides:
getParent
in classBinaryTreeNode<E extends Address>
- Returns:
-
getUpperSubNode
public AddressTrie.TrieNode<E> getUpperSubNode()
Returns the sub-node whose address is largest in value- Overrides:
getUpperSubNode
in classBinaryTreeNode<E extends Address>
- Returns:
-
getLowerSubNode
public AddressTrie.TrieNode<E> getLowerSubNode()
Returns the sub node whose address is smallest in value- Overrides:
getLowerSubNode
in classBinaryTreeNode<E extends Address>
- Returns:
-
previousAddedNode
public AddressTrie.TrieNode<E> previousAddedNode()
Description copied from class:BinaryTreeNode
Returns the previous node in the tree that is an added node, following the tree order in reverse, or null if there is no such node.- Overrides:
previousAddedNode
in classBinaryTreeNode<E extends Address>
- Returns:
-
nextAddedNode
public AddressTrie.TrieNode<E> nextAddedNode()
Description copied from class:BinaryTreeNode
Returns the next node in the tree that is an added node, following the tree order, or null if there is no such node.- Overrides:
nextAddedNode
in classBinaryTreeNode<E extends Address>
- Returns:
-
nextNode
public AddressTrie.TrieNode<E> nextNode()
Description copied from class:BinaryTreeNode
Returns the node that follows this node following the tree order- Overrides:
nextNode
in classBinaryTreeNode<E extends Address>
- Returns:
-
previousNode
public AddressTrie.TrieNode<E> previousNode()
Description copied from class:BinaryTreeNode
Returns the node that precedes this node following the tree order.- Overrides:
previousNode
in classBinaryTreeNode<E extends Address>
- Returns:
-
firstNode
public AddressTrie.TrieNode<E> firstNode()
Description copied from class:BinaryTreeNode
Returns the first (lowest valued) node in the sub-tree originating from this node.- Specified by:
firstNode
in interfaceAddressTrieOps<E extends Address>
- Overrides:
firstNode
in classBinaryTreeNode<E extends Address>
- Returns:
-
firstAddedNode
public AddressTrie.TrieNode<E> firstAddedNode()
Description copied from class:BinaryTreeNode
Returns the first (lowest valued) added node in the sub-tree originating from this node, or null if there are no added entries in this tree or sub-tree- Specified by:
firstAddedNode
in interfaceAddressTrieOps<E extends Address>
- Overrides:
firstAddedNode
in classBinaryTreeNode<E extends Address>
- Returns:
-
lastNode
public AddressTrie.TrieNode<E> lastNode()
Description copied from class:BinaryTreeNode
Returns the last (highest valued) node in the sub-tree originating from this node.- Specified by:
lastNode
in interfaceAddressTrieOps<E extends Address>
- Overrides:
lastNode
in classBinaryTreeNode<E extends Address>
- Returns:
-
lastAddedNode
public AddressTrie.TrieNode<E> lastAddedNode()
Description copied from class:BinaryTreeNode
Returns the last (highest valued) added node in the sub-tree originating from this node, or null if there are no added entries in this tree or sub-tree- Specified by:
lastAddedNode
in interfaceAddressTrieOps<E extends Address>
- Overrides:
lastAddedNode
in classBinaryTreeNode<E extends Address>
- 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.- Specified by:
lowerAddedNode
in interfaceAddressTrieOps<E extends Address>
- Returns:
-
lower
public E lower(E addr)
Description copied from interface:AddressTrieOps
Returns the highest added address strictly less than the given address.- Specified by:
lower
in interfaceAddressTrieOps<E extends 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.- Specified by:
floorAddedNode
in interfaceAddressTrieOps<E extends 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.- Specified by:
floor
in interfaceAddressTrieOps<E extends 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.- Specified by:
higherAddedNode
in interfaceAddressTrieOps<E extends Address>
- Returns:
-
higher
public E higher(E addr)
Description copied from interface:AddressTrieOps
Returns the lowest added address strictly greater than the given address.- Specified by:
higher
in interfaceAddressTrieOps<E extends 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.- Specified by:
ceilingAddedNode
in interfaceAddressTrieOps<E extends 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.- Specified by:
ceiling
in interfaceAddressTrieOps<E extends Address>
- Returns:
-
nodeIterator
public java.util.Iterator<? extends AddressTrie.TrieNode<E>> nodeIterator(boolean forward)
Description copied from class:BinaryTreeNode
Iterates through the added nodes of the sub-tree with this node as the root, in forward or reverse tree order.- Specified by:
nodeIterator
in interfaceAddressTrieOps<E extends Address>
- Specified by:
nodeIterator
in interfaceTreeOps<E extends Address>
- Overrides:
nodeIterator
in classBinaryTreeNode<E extends Address>
- Parameters:
forward
- if true, goes in ascending order, otherwise descending- Returns:
-
allNodeIterator
public java.util.Iterator<? extends AddressTrie.TrieNode<E>> allNodeIterator(boolean forward)
Description copied from class:BinaryTreeNode
Iterates through all the nodes of the sub-tree with this node as the root, in forward or reverse tree order.- Specified by:
allNodeIterator
in interfaceAddressTrieOps<E extends Address>
- Specified by:
allNodeIterator
in interfaceTreeOps<E extends Address>
- Overrides:
allNodeIterator
in classBinaryTreeNode<E extends Address>
- Parameters:
forward
- if true, goes in ascending order, otherwise descending- Returns:
-
blockSizeNodeIterator
public java.util.Iterator<? extends AddressTrie.TrieNode<E>> blockSizeNodeIterator(boolean lowerSubNodeFirst)
Iterates the added nodes, ordered by keys from largest prefix blocks to smallest and then to individual addresses, in the sub-trie with this node as the root.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 java.util.Iterator<? extends AddressTrie.TrieNode<E>> blockSizeAllNodeIterator(boolean lowerSubNodeFirst)
Iterates all the nodes, ordered by keys from largest prefix blocks to smallest and then to individual addresses, in the sub-trie with this node as the root.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, in the sub-trie with this node as the root.- Returns:
-
containingFirstIterator
public java.util.Iterator<? extends AddressTrie.TrieNode<E>> 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.See the docs for
TreeOps
for more details on the ordering.- Specified by:
containingFirstIterator
in interfaceAddressTrieOps<E extends Address>
- Specified by:
containingFirstIterator
in interfaceTreeOps<E extends Address>
- Overrides:
containingFirstIterator
in classBinaryTreeNode<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
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:
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 interfaceAddressTrieOps<E extends Address>
- Specified by:
containingFirstAllNodeIterator
in interfaceTreeOps<E extends Address>
- Overrides:
containingFirstAllNodeIterator
in classBinaryTreeNode<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
public java.util.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.- Specified by:
containedFirstIterator
in interfaceAddressTrieOps<E extends Address>
- Specified by:
containedFirstIterator
in interfaceTreeOps<E extends Address>
- Overrides:
containedFirstIterator
in classBinaryTreeNode<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
public java.util.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 interfaceAddressTrieOps<E extends Address>
- Specified by:
containedFirstAllNodeIterator
in interfaceTreeOps<E extends Address>
- Overrides:
containedFirstAllNodeIterator
in classBinaryTreeNode<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
public java.util.Spliterator<? extends AddressTrie.TrieNode<E>> nodeSpliterator(boolean forward)
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 interfaceAddressTrieOps<E extends Address>
- Specified by:
nodeSpliterator
in interfaceTreeOps<E extends Address>
- Parameters:
forward
- if true, goes in ascending order, otherwise descending- Returns:
-
allNodeSpliterator
public java.util.Spliterator<? extends AddressTrie.TrieNode<E>> allNodeSpliterator(boolean forward)
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 interfaceAddressTrieOps<E extends Address>
- Specified by:
allNodeSpliterator
in interfaceTreeOps<E extends Address>
- Parameters:
forward
- if true, goes in ascending order, otherwise descending- Returns:
-
spliterator
public java.util.Spliterator<E> spliterator()
Description copied from interface:TreeOps
Creates aSpliterator
over the keys of the added nodes in natural tree order.See
TreeOps
for more details on the ordering.
-
descendingSpliterator
public java.util.Spliterator<E> descendingSpliterator()
Description copied from interface:TreeOps
Creates aSpliterator
over the keys of the added nodes in descending natural tree order.See
TreeOps
for more details on the ordering.- Specified by:
descendingSpliterator
in interfaceTreeOps<E extends Address>
- 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. SeeAddressTrieOps.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.- Specified by:
contains
in interfaceAddressTrieOps<E extends Address>
- 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. 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
AddressTrieOps.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.
- Specified by:
remove
in interfaceAddressTrieOps<E extends Address>
- Returns:
- See Also:
AddressTrieOps.removeElementsContainedBy(Address)
-
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. SeeAddressTrieOps.AddressTrieAddOps.add(Address)
for more details.- Specified by:
getNode
in interfaceAddressTrieOps<E extends Address>
- Returns:
- See Also:
AddressTrieOps.contains(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, whileAddressTrieOps.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. 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.
- Specified by:
removeElementsContainedBy
in interfaceAddressTrieOps<E extends Address>
- 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. 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.- Specified by:
elementsContainedBy
in interfaceAddressTrieOps<E extends Address>
- 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. 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
AddressTrieOps.elementContains(Address)
to check for the existence of a containing address.- Specified by:
elementsContaining
in interfaceAddressTrieOps<E extends 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. SeeAddressTrieOps.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), useAddressTrieOps.elementsContaining(Address)
.
To get the node corresponding to the result of this method, useAddressTrieOps.longestPrefixMatchNode(Address)
- Specified by:
longestPrefixMatch
in interfaceAddressTrieOps<E extends 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. SeeAddressTrieOps.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, useAddressTrieOps.elementsContaining(Address)
.
UseAddressTrieOps.longestPrefixMatch(Address)
to get the address corresponding to the result of this method.- Specified by:
longestPrefixMatchNode
in interfaceAddressTrieOps<E extends Address>
- 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. SeeAddressTrieOps.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), useAddressTrieOps.elementsContaining(Address)
.
To get the node corresponding to the result of this method, useAddressTrieOps.shortestPrefixMatchNode(Address)
- Specified by:
shortestPrefixMatch
in interfaceAddressTrieOps<E extends 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. SeeAddressTrieOps.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, useAddressTrieOps.elementsContaining(Address)
.
UseAddressTrieOps.shortestPrefixMatch(Address)
to get the address corresponding to the result of this method.- Specified by:
shortestPrefixMatchNode
in interfaceAddressTrieOps<E extends Address>
- 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. 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
AddressTrieOps.elementsContaining(Address)
.- Specified by:
elementContains
in interfaceAddressTrieOps<E extends Address>
- Returns:
-
asNewTrie
public AddressTrie<E> asNewTrie()
Creates a new sub-trie, copying the nodes starting with this node as root. The nodes are copies of the nodes in this sub-trie, but their keys and values are not copies.
-
cloneTree
public AddressTrie.TrieNode<E> cloneTree()
Description copied from class:BinaryTreeNode
Clones the sub-tree starting with this node as root. The nodes are cloned, but their keys and values are not cloned.- Overrides:
cloneTree
in classBinaryTreeNode<E extends Address>
-
clone
public AddressTrie.TrieNode<E> clone()
Description copied from class:BinaryTreeNode
Clones the node. Keys remain the same, but the parent node and the lower and upper sub-nodes are all set to null.- Overrides:
clone
in classBinaryTreeNode<E extends Address>
-
equals
public boolean equals(java.lang.Object o)
Description copied from class:BinaryTreeNode
Returns whether the key values match those of the given node- Overrides:
equals
in classBinaryTreeNode<E extends Address>
-
-