public class MACAddressTrie extends AddressTrie<MACAddress>
AddressTrie
for more details.Modifier and Type | Class and Description |
---|---|
static class |
MACAddressTrie.MACTrieNode |
AddressTrie.AddressComparator<E extends Address>, AddressTrie.TrieComparator<E extends Address>, AddressTrie.TrieNode<E extends Address>
AddressTrieOps.AddressTrieAddOps<E extends Address>, AddressTrieOps.AssociativeAddressTrieOps<K extends Address,V>, AddressTrieOps.AssociativeAddressTriePutOps<K extends Address,V>
Constructor and Description |
---|
MACAddressTrie() |
Modifier and Type | Method and Description |
---|---|
MACAddressTrie.MACTrieNode |
addNode(MACAddress addr)
Adds the given single address or prefix block subnet to the trie, if not already there.
|
MACAddressTrie.MACTrieNode |
addTrie(AddressTrie.TrieNode<MACAddress> trie)
Adds nodes matching the given sub-root node and all of its sub-nodes to the trie, if not already there.
|
Iterator<MACAddressTrie.MACTrieNode> |
allNodeIterator(boolean forward)
Iterates through the nodes (not just the added nodes) in forward or reverse tree order.
|
Spliterator<MACAddressTrie.MACTrieNode> |
allNodeSpliterator(boolean forward)
Creates a
Spliterator over the nodes in forward or reverse natural tree order. |
Iterator<MACAddressTrie.MACTrieNode> |
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<MACAddressTrie.MACTrieNode,MACAddress,C> |
blockSizeCachingAllNodeIterator()
Iterates all nodes, ordered by keys from largest prefix blocks to smallest, and then to individual addresses.
|
Iterator<MACAddressTrie.MACTrieNode> |
blockSizeNodeIterator(boolean lowerSubNodeFirst)
Iterates the added nodes in the trie, ordered by keys from largest prefix blocks to smallest, and then to individual addresses.
|
MACAddressTrie.MACTrieNode |
ceilingAddedNode(MACAddress addr)
Returns the added node whose address is the lowest address greater than or equal to the given address.
|
MACAddressTrie |
clone()
Copies the trie, but not the keys or values.
|
AddedTree<MACAddress> |
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<MACAddressTrie.MACTrieNode> |
containedFirstAllNodeIterator(boolean forwardSubNodeOrder)
Returns an iterator that does a post-order binary tree traversal.
|
Iterator<MACAddressTrie.MACTrieNode> |
containedFirstIterator(boolean forwardSubNodeOrder)
Returns an iterator that does a post-order binary tree traversal of the added nodes.
|
<C> BinaryTreeNode.CachingIterator<MACAddressTrie.MACTrieNode,MACAddress,C> |
containingFirstAllNodeIterator(boolean forwardSubNodeOrder)
Returns an iterator that does a pre-order binary tree traversal.
|
<C> BinaryTreeNode.CachingIterator<MACAddressTrie.MACTrieNode,MACAddress,C> |
containingFirstIterator(boolean forwardSubNodeOrder)
Returns an iterator that does a pre-order binary tree traversal of the added nodes.
|
Iterator<E> |
descendingIterator()
Traverses the added node keys in reverse natural tree order.
|
MACAddressTrie.MACTrieNode |
elementsContainedBy(MACAddress addr)
Checks if a part of this trie is contained by the given prefix block subnet or individual address.
|
MACAddressTrie.MACTrieNode |
elementsContaining(MACAddress 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
|
MACAddressTrie.MACTrieNode |
firstAddedNode()
Returns the added node with the first (lowest valued) key,
or null if there are no added entries in this trie or subtrie
|
MACAddressTrie.MACTrieNode |
firstNode()
Returns the node with the first (lowest valued) key, whether the node is added or not
|
MACAddressTrie.MACTrieNode |
floorAddedNode(MACAddress addr)
Returns the added node whose address is the highest address less than or equal to the given address.
|
MACAddressTrie.MACTrieNode |
getAddedNode(MACAddress addr)
Gets trie nodes representing added elements.
|
MACAddressTrie.MACTrieNode |
getNode(MACAddress addr)
Gets the node corresponding to the given address, returns null if not such element exists.
|
MACAddressTrie.MACTrieNode |
getRoot()
Returns the root of this trie
|
int |
hashCode() |
MACAddressTrie.MACTrieNode |
higherAddedNode(MACAddress addr)
Returns the added node whose address is the lowest address strictly greater than the given address.
|
Iterator<E> |
iterator()
Traverses the added node keys in natural tree order.
|
MACAddressTrie.MACTrieNode |
lastAddedNode()
Returns the added node with the last (highest valued) key,
or null if there are no added elements in this trie or subtrie
|
MACAddressTrie.MACTrieNode |
lastNode()
Returns the node with the last (highest valued) key, whether the node is added or not
|
MACAddressTrie.MACTrieNode |
longestPrefixMatchNode(MACAddress 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.
|
MACAddressTrie.MACTrieNode |
lowerAddedNode(MACAddress addr)
Returns the added node whose address is the highest address strictly less than the given address.
|
Iterator<MACAddressTrie.MACTrieNode> |
nodeIterator(boolean forward)
Iterates through the added nodes in forward or reverse natural tree order.
|
Spliterator<MACAddressTrie.MACTrieNode> |
nodeSpliterator(boolean forward)
Creates a
Spliterator over the added nodes in forward or reverse natural tree order. |
MACAddressTrie.MACTrieNode |
removeElementsContainedBy(MACAddress addr)
Removes any single address or prefix block subnet from the trie that is contained in the given individual address or prefix block subnet.
|
String |
toAddedNodesTreeString()
Provides a flattened version of the trie showing only the contained added nodes and their containment structure, which is non-binary.
|
add, asSet, ceiling, clear, contains, decrement, descendingSpliterator, elementContains, floor, getComparator, higher, increment, isEmpty, longestPrefixMatch, lower, nodeSize, remove, shortestPrefixMatch, shortestPrefixMatchNode, size, spliterator, toString, toString, toString
public MACAddressTrie.MACTrieNode getRoot()
getRoot
in class AddressTrie<MACAddress>
public MACAddressTrie.MACTrieNode removeElementsContainedBy(MACAddress 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<MACAddress>
removeElementsContainedBy
in class AddressTrie<MACAddress>
public MACAddressTrie.MACTrieNode elementsContainedBy(MACAddress addr)
AddressTrieOps
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.
elementsContainedBy
in interface AddressTrieOps<MACAddress>
elementsContainedBy
in class AddressTrie<MACAddress>
public MACAddressTrie.MACTrieNode elementsContaining(MACAddress addr)
AddressTrieOps
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.
elementsContaining
in interface AddressTrieOps<MACAddress>
elementsContaining
in class AddressTrie<MACAddress>
public MACAddressTrie.MACTrieNode longestPrefixMatchNode(MACAddress addr)
AddressTrieOps
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.
longestPrefixMatchNode
in interface AddressTrieOps<MACAddress>
longestPrefixMatchNode
in class AddressTrie<MACAddress>
public MACAddressTrie.MACTrieNode getAddedNode(MACAddress addr)
AddressTrieOps
Use AddressTrieOps.contains(Address)
to check for the existence of a given address in the trie,
as well as AddressTrieOps.getNode(Address)
to search for all nodes including those not-added but also auto-generated nodes for subnet blocks.
public MACAddressTrie.MACTrieNode getNode(MACAddress addr)
AddressTrieOps
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.
getNode
in interface AddressTrieOps<MACAddress>
getNode
in class AddressTrie<MACAddress>
AddressTrieOps.contains(Address)
public MACAddressTrie.MACTrieNode addNode(MACAddress addr)
AddressTrieOps.AddressTrieAddOps
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)
addNode
in interface AddressTrieOps.AddressTrieAddOps<MACAddress>
addNode
in class AddressTrie<MACAddress>
public MACAddressTrie.MACTrieNode addTrie(AddressTrie.TrieNode<MACAddress> trie)
AddressTrieOps.AddressTrieAddOps
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.
addTrie
in interface AddressTrieOps.AddressTrieAddOps<MACAddress>
addTrie
in class AddressTrie<MACAddress>
public Iterator<MACAddressTrie.MACTrieNode> nodeIterator(boolean forward)
TreeOps
This iterator supports the Iterator.remove()
operation.
See TreeOps
for more details on the ordering.
nodeIterator
in interface AddressTrieOps<MACAddress>
nodeIterator
in interface TreeOps<MACAddress>
nodeIterator
in class AddressTrie<MACAddress>
forward
- if true, goes in ascending order, otherwise descendingpublic Iterator<MACAddressTrie.MACTrieNode> allNodeIterator(boolean forward)
TreeOps
See TreeOps
for more details on the ordering.
This iterator supports the Iterator.remove()
operation.
allNodeIterator
in interface AddressTrieOps<MACAddress>
allNodeIterator
in interface TreeOps<MACAddress>
allNodeIterator
in class AddressTrie<MACAddress>
forward
- if true, goes in ascending order, otherwise descendingpublic Iterator<MACAddressTrie.MACTrieNode> blockSizeNodeIterator(boolean lowerSubNodeFirst)
AddressTrie
This iterator supports the Iterator.remove()
operation.
blockSizeNodeIterator
in class AddressTrie<MACAddress>
lowerSubNodeFirst
- if true, for blocks of equal size the lower is first, otherwise the reverse orderpublic Iterator<MACAddressTrie.MACTrieNode> blockSizeAllNodeIterator(boolean lowerSubNodeFirst)
AddressTrie
This iterator supports the Iterator.remove()
operation.
blockSizeAllNodeIterator
in class AddressTrie<MACAddress>
lowerSubNodeFirst
- if true, for blocks of equal size the lower is first, otherwise the reverse orderpublic <C> BinaryTreeNode.CachingIterator<MACAddressTrie.MACTrieNode,MACAddress,C> blockSizeCachingAllNodeIterator()
AddressTrie
This iterator supports the Iterator.remove()
operation.
blockSizeCachingAllNodeIterator
in class AddressTrie<MACAddress>
public <C> BinaryTreeNode.CachingIterator<MACAddressTrie.MACTrieNode,MACAddress,C> containingFirstIterator(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.
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.
containingFirstIterator
in interface AddressTrieOps<MACAddress>
containingFirstIterator
in interface TreeOps<MACAddress>
containingFirstIterator
in class AddressTrie<MACAddress>
forwardSubNodeOrder
- if true, a left sub-node will be visited before the right sub-node of the same parent node.public <C> BinaryTreeNode.CachingIterator<MACAddressTrie.MACTrieNode,MACAddress,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");
}
}
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.
containingFirstAllNodeIterator
in interface AddressTrieOps<MACAddress>
containingFirstAllNodeIterator
in interface TreeOps<MACAddress>
containingFirstAllNodeIterator
in class AddressTrie<MACAddress>
forwardSubNodeOrder
- if true, a left sub-node will be visited before the right sub-node of the same parent node.public Iterator<MACAddressTrie.MACTrieNode> containedFirstIterator(boolean forwardSubNodeOrder)
TreeOps
This iterator supports the Iterator.remove()
operation.
See TreeOps
for more details on the ordering.
containedFirstIterator
in interface AddressTrieOps<MACAddress>
containedFirstIterator
in interface TreeOps<MACAddress>
containedFirstIterator
in class AddressTrie<MACAddress>
forwardSubNodeOrder
- if true, a left sub-node will be visited before the right sub-node of the same parent node.public Iterator<MACAddressTrie.MACTrieNode> 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<MACAddress>
containedFirstAllNodeIterator
in interface TreeOps<MACAddress>
containedFirstAllNodeIterator
in class AddressTrie<MACAddress>
forwardSubNodeOrder
- if true, a left sub-node will be visited before the right sub-node of the same parent node.public Spliterator<MACAddressTrie.MACTrieNode> nodeSpliterator(boolean forward)
TreeOps
Spliterator
over the added nodes in forward or reverse natural tree order.
See TreeOps
for more details on the ordering.
nodeSpliterator
in interface AddressTrieOps<MACAddress>
nodeSpliterator
in interface TreeOps<MACAddress>
nodeSpliterator
in class AddressTrie<MACAddress>
forward
- if true, goes in ascending order, otherwise descendingpublic Spliterator<MACAddressTrie.MACTrieNode> allNodeSpliterator(boolean forward)
TreeOps
Spliterator
over the nodes in forward or reverse natural tree order.
See TreeOps
for more details on the ordering.
allNodeSpliterator
in interface AddressTrieOps<MACAddress>
allNodeSpliterator
in interface TreeOps<MACAddress>
allNodeSpliterator
in class AddressTrie<MACAddress>
forward
- if true, goes in ascending order, otherwise descendingpublic MACAddressTrie.MACTrieNode lowerAddedNode(MACAddress addr)
AddressTrieOps
lowerAddedNode
in interface AddressTrieOps<MACAddress>
lowerAddedNode
in class AddressTrie<MACAddress>
public MACAddressTrie.MACTrieNode floorAddedNode(MACAddress addr)
AddressTrieOps
floorAddedNode
in interface AddressTrieOps<MACAddress>
floorAddedNode
in class AddressTrie<MACAddress>
public MACAddressTrie.MACTrieNode higherAddedNode(MACAddress addr)
AddressTrieOps
higherAddedNode
in interface AddressTrieOps<MACAddress>
higherAddedNode
in class AddressTrie<MACAddress>
public MACAddressTrie.MACTrieNode ceilingAddedNode(MACAddress addr)
AddressTrieOps
ceilingAddedNode
in interface AddressTrieOps<MACAddress>
ceilingAddedNode
in class AddressTrie<MACAddress>
public MACAddressTrie.MACTrieNode firstNode()
AddressTrieOps
firstNode
in interface AddressTrieOps<MACAddress>
firstNode
in class AddressTrie<MACAddress>
public MACAddressTrie.MACTrieNode lastNode()
AddressTrieOps
lastNode
in interface AddressTrieOps<MACAddress>
lastNode
in class AddressTrie<MACAddress>
public MACAddressTrie.MACTrieNode firstAddedNode()
AddressTrieOps
firstAddedNode
in interface AddressTrieOps<MACAddress>
firstAddedNode
in class AddressTrie<MACAddress>
public MACAddressTrie.MACTrieNode lastAddedNode()
AddressTrieOps
lastAddedNode
in interface AddressTrieOps<MACAddress>
lastAddedNode
in class AddressTrie<MACAddress>
public boolean equals(Object o)
AddressTrie
equals
in class AddressTrie<MACAddress>
public MACAddressTrie clone()
clone
in class AddressTrie<MACAddress>
public AddedTree<MACAddress> constructAddedNodesTree()
AddressTrie
AddressTrie.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.constructAddedNodesTree
in class AddressTrie<MACAddress>
public String toAddedNodesTreeString()
AddressTrie
toAddedNodesTreeString
in class AddressTrie<MACAddress>
public Iterator<E> iterator()
TreeOps
See TreeOps
for more details on the ordering.
public Iterator<E> descendingIterator()
TreeOps
See TreeOps
for more details on the ordering.
descendingIterator
in interface TreeOps<E extends Address>