E - public abstract static class AddressTrie.TrieNode<E extends Address> extends BinaryTreeNode<E> implements AddressTrieOps<E>
BinaryTreeNode.CachingIterator<N extends BinaryTreeNode<E>,E,C>AddressTrieOps.AddressTrieAddOps<E extends Address>, AddressTrieOps.AssociativeAddressTrieOps<K extends Address,V>, AddressTrieOps.AssociativeAddressTriePutOps<K extends Address,V>| Modifier and Type | Method and Description |
|---|---|
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.
|
Spliterator<? extends AddressTrie.TrieNode<E>> |
allNodeSpliterator(boolean forward)
Creates a
Spliterator 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.
|
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.
|
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.
|
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.
|
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).
|
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 key values match those of the given node
|
AddressTrie.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-tree
|
AddressTrie.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 value
|
AddressTrie.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 value
|
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.
|
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-tree
|
AddressTrie.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 order
|
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.
|
Spliterator<? extends AddressTrie.TrieNode<E>> |
nodeSpliterator(boolean forward)
Creates a
Spliterator 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.
|
Spliterator<E> |
spliterator()
Creates a
Spliterator over the keys of the added nodes in natural tree order. |
clear, descendingIterator, getKey, hashCode, isAdded, isEmpty, isLeaf, isRoot, iterator, nodeSize, remove, setAdded, size, toString, toTreeString, treeEquals, treeHashCodegetAddedNodedescendingIterator, iteratorpublic AddressTrie.TrieNode<E> getParent()
getParent in class BinaryTreeNode<E extends Address>public AddressTrie.TrieNode<E> getUpperSubNode()
getUpperSubNode in class BinaryTreeNode<E extends Address>public AddressTrie.TrieNode<E> getLowerSubNode()
getLowerSubNode in class BinaryTreeNode<E extends Address>public AddressTrie.TrieNode<E> previousAddedNode()
BinaryTreeNodepreviousAddedNode in class BinaryTreeNode<E extends Address>public AddressTrie.TrieNode<E> nextAddedNode()
BinaryTreeNodenextAddedNode in class BinaryTreeNode<E extends Address>public AddressTrie.TrieNode<E> nextNode()
BinaryTreeNodenextNode in class BinaryTreeNode<E extends Address>public AddressTrie.TrieNode<E> previousNode()
BinaryTreeNodepreviousNode in class BinaryTreeNode<E extends Address>public AddressTrie.TrieNode<E> firstNode()
BinaryTreeNodefirstNode in interface AddressTrieOps<E extends Address>firstNode in class BinaryTreeNode<E extends Address>public AddressTrie.TrieNode<E> firstAddedNode()
BinaryTreeNodefirstAddedNode in interface AddressTrieOps<E extends Address>firstAddedNode in class BinaryTreeNode<E extends Address>public AddressTrie.TrieNode<E> lastNode()
BinaryTreeNodelastNode in interface AddressTrieOps<E extends Address>lastNode in class BinaryTreeNode<E extends Address>public AddressTrie.TrieNode<E> lastAddedNode()
BinaryTreeNodelastAddedNode in interface AddressTrieOps<E extends Address>lastAddedNode in class BinaryTreeNode<E extends Address>public AddressTrie.TrieNode<E> lowerAddedNode(E addr)
AddressTrieOpslowerAddedNode in interface AddressTrieOps<E extends Address>public E lower(E addr)
AddressTrieOpslower in interface AddressTrieOps<E extends Address>public AddressTrie.TrieNode<E> floorAddedNode(E addr)
AddressTrieOpsfloorAddedNode in interface AddressTrieOps<E extends Address>public E floor(E addr)
AddressTrieOpsfloor in interface AddressTrieOps<E extends Address>public AddressTrie.TrieNode<E> higherAddedNode(E addr)
AddressTrieOpshigherAddedNode in interface AddressTrieOps<E extends Address>public E higher(E addr)
AddressTrieOpshigher in interface AddressTrieOps<E extends Address>public AddressTrie.TrieNode<E> ceilingAddedNode(E addr)
AddressTrieOpsceilingAddedNode in interface AddressTrieOps<E extends Address>public E ceiling(E addr)
AddressTrieOpsceiling in interface AddressTrieOps<E extends Address>public Iterator<? extends AddressTrie.TrieNode<E>> nodeIterator(boolean forward)
BinaryTreeNodenodeIterator in interface AddressTrieOps<E extends Address>nodeIterator in interface TreeOps<E extends Address>nodeIterator in class BinaryTreeNode<E extends Address>forward - if true, goes in ascending order, otherwise descendingpublic Iterator<? extends AddressTrie.TrieNode<E>> allNodeIterator(boolean forward)
BinaryTreeNodeallNodeIterator in interface AddressTrieOps<E extends Address>allNodeIterator in interface TreeOps<E extends Address>allNodeIterator in class BinaryTreeNode<E extends Address>forward - if true, goes in ascending order, otherwise descendingpublic Iterator<? extends AddressTrie.TrieNode<E>> blockSizeNodeIterator(boolean lowerSubNodeFirst)
This iterator supports the Iterator.remove() operation.
lowerSubNodeFirst - if true, for blocks of equal size the lower is first, otherwise the reverse orderpublic Iterator<? extends AddressTrie.TrieNode<E>> blockSizeAllNodeIterator(boolean lowerSubNodeFirst)
This iterator supports the Iterator.remove() operation.
lowerSubNodeFirst - if true, for blocks of equal size the lower is first, otherwise the reverse orderpublic <C> BinaryTreeNode.CachingIterator<? extends AddressTrie.TrieNode<E>,E,C> blockSizeCachingAllNodeIterator()
public Iterator<? extends AddressTrie.TrieNode<E>> containingFirstIterator(boolean forwardSubNodeOrder)
TreeOps
This iterator supports the Iterator.remove() operation.
See the docs for TreeOps for more details on the ordering.
containingFirstIterator in interface AddressTrieOps<E extends Address>containingFirstIterator in interface TreeOps<E extends Address>containingFirstIterator in class BinaryTreeNode<E extends Address>forwardSubNodeOrder - if true, a left sub-node will be visited before the right sub-node of the same parent node.public <C> BinaryTreeNode.CachingIterator<? extends AddressTrie.TrieNode<E>,E,C> containingFirstAllNodeIterator(boolean forwardSubNodeOrder)
TreeOps
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");
}
}
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.
containingFirstAllNodeIterator in interface AddressTrieOps<E extends Address>containingFirstAllNodeIterator in interface TreeOps<E extends Address>containingFirstAllNodeIterator in class BinaryTreeNode<E extends Address>forwardSubNodeOrder - if true, a left sub-node will be visited before the right sub-node of the same parent node.public Iterator<? extends AddressTrie.TrieNode<E>> containedFirstIterator(boolean forwardSubNodeOrder)
TreeOps
This iterator supports the Iterator.remove() operation.
See TreeOps for more details on the ordering.
containedFirstIterator in interface AddressTrieOps<E extends Address>containedFirstIterator in interface TreeOps<E extends Address>containedFirstIterator in class BinaryTreeNode<E extends Address>forwardSubNodeOrder - if true, a left sub-node will be visited before the right sub-node of the same parent node.public Iterator<? extends AddressTrie.TrieNode<E>> containedFirstAllNodeIterator(boolean forwardSubNodeOrder)
TreeOps
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.
containedFirstAllNodeIterator in interface AddressTrieOps<E extends Address>containedFirstAllNodeIterator in interface TreeOps<E extends Address>containedFirstAllNodeIterator in class BinaryTreeNode<E extends Address>forwardSubNodeOrder - if true, a left sub-node will be visited before the right sub-node of the same parent node.public Spliterator<? extends AddressTrie.TrieNode<E>> nodeSpliterator(boolean forward)
TreeOpsSpliterator over the added nodes in forward or reverse natural tree order.
See TreeOps for more details on the ordering.
nodeSpliterator in interface AddressTrieOps<E extends Address>nodeSpliterator in interface TreeOps<E extends Address>forward - if true, goes in ascending order, otherwise descendingpublic Spliterator<? extends AddressTrie.TrieNode<E>> allNodeSpliterator(boolean forward)
TreeOpsSpliterator over the nodes in forward or reverse natural tree order.
See TreeOps for more details on the ordering.
allNodeSpliterator in interface AddressTrieOps<E extends Address>allNodeSpliterator in interface TreeOps<E extends Address>forward - if true, goes in ascending order, otherwise descendingpublic Spliterator<E> spliterator()
TreeOpsSpliterator over the keys of the added nodes in natural tree order.
See TreeOps for more details on the ordering.
spliterator in interface TreeOps<E extends Address>spliterator in interface Iterable<E extends Address>public Spliterator<E> descendingSpliterator()
TreeOpsSpliterator over the keys of the added nodes in descending natural tree order.
See TreeOps for more details on the ordering.
descendingSpliterator in interface TreeOps<E extends Address>public boolean contains(E addr)
AddressTrieOpsIf 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.
contains in interface AddressTrieOps<E extends Address>public boolean remove(E addr)
AddressTrieOpsRemoving 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.
remove in interface AddressTrieOps<E extends Address>AddressTrieOps.removeElementsContainedBy(Address)public AddressTrie.TrieNode<E> getNode(E addr)
AddressTrieOpsIf 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.
getNode in interface AddressTrieOps<E extends Address>AddressTrieOps.contains(Address)public AddressTrie.TrieNode<E> removeElementsContainedBy(E addr)
AddressTrieOps
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.
removeElementsContainedBy in interface AddressTrieOps<E extends Address>public AddressTrie.TrieNode<E> elementsContainedBy(E addr)
AddressTrieOpsIf 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.
elementsContainedBy in interface AddressTrieOps<E extends Address>public AddressTrie.TrieNode<E> elementsContaining(E addr)
AddressTrieOpsIf 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.
elementsContaining in interface AddressTrieOps<E extends Address>public E longestPrefixMatch(E addr)
AddressTrieOpsIf 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)
longestPrefixMatch in interface AddressTrieOps<E extends Address>public AddressTrie.TrieNode<E> longestPrefixMatchNode(E addr)
AddressTrieOpsIf 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.
longestPrefixMatchNode in interface AddressTrieOps<E extends Address>public E shortestPrefixMatch(E addr)
AddressTrieOpsIf 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)
shortestPrefixMatch in interface AddressTrieOps<E extends Address>public AddressTrie.TrieNode<E> shortestPrefixMatchNode(E addr)
AddressTrieOpsIf 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.
shortestPrefixMatchNode in interface AddressTrieOps<E extends Address>public boolean elementContains(E addr)
AddressTrieOpsIf 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).
elementContains in interface AddressTrieOps<E extends Address>public AddressTrie<E> asNewTrie()
public AddressTrie.TrieNode<E> cloneTree()
BinaryTreeNodecloneTree in class BinaryTreeNode<E extends Address>public AddressTrie.TrieNode<E> clone()
BinaryTreeNodeclone in class BinaryTreeNode<E extends Address>public boolean equals(Object o)
BinaryTreeNodeequals in class BinaryTreeNode<E extends Address>