- Type Parameters:
E
- the type of the address keys
- All Implemented Interfaces:
AddressTrieOps<E>
,AddressTrieOps.AddressTrieAddOps<E>
,TreeOps<E>
,Serializable
,Cloneable
,Iterable<E>
- Direct Known Subclasses:
AssociativeAddressTrie
,IPv4AddressTrie
,IPv6AddressTrie
,MACAddressTrie
This trie data structure allows you to check an address for containment in many subnets at once, in constant time. The trie allows you to check a subnet for containment of many smaller subnets or addresses at once, in constant time. The trie allows you to check for equality of a subnet or address with a large number of subnets or addresses at once.
The trie can also be used as the backing structure for a AddressTrieSet
which is a NavigableSet
.
Unlike TreeSet
this data structure provides access to the nodes and the associated subtrie with each node,
which corresponds with their associated CIDR prefix block subnets.
There is only a single possible trie for any given set of address and subnets. For one thing, this means they are automatically balanced. Also, this makes access to subtries and to the nodes themselves more useful, allowing for many of the same operations performed on the original trie.
Each node has either a prefix block or a single address as its key. Each prefix block node can have two sub-nodes, each sub-node a prefix block or address contained by the node.
There are more nodes in the trie than there are elements in the set. A node is considered "added" if it was explicitly added to the trie and is included as an element when viewed as a set. There are non-added prefix block nodes that are generated in the trie as well. When two or more added addresses share the same prefix up until they differ with the bit at index x, then a prefix block node is generated (if not already added to the trie) for the common prefix of length x, with the nodes for those addresses to be found following the lower or upper sub-nodes according to the bit at index x + 1 in each address. If that bit is 1, the node can be found by following the upper sub-node, and when it is 0, the lower sub-node.
Nodes that were generated as part of the trie structure only because of other added elements are not elements of the represented set. The set elements are the elements that were explicitly added.
You can work with parts of the trie, starting from any node in the trie, calling methods that start with any given node, such as iterating or spliterating the subtrie, finding the first or last in the subtrie, doing containment checks with the subtrie, and so on.
The binary trie structure defines a natural ordering of the trie elements. Addresses of equal prefix length are sorted by prefix value. Addresses with no prefix length are sorted by address value. Addresses of differing prefix length are sorted according to the bit that follows the shorter prefix length in the address with the longer prefix length, whether that bit is 0 or 1 determines if that address is ordered before or after the address of shorter prefix length.
The unique and pre-defined structure for a trie means that different means of traversing the trie can be more meaningful. This trie implementation provides 8 different ways of iterating through the trie:
- 1, 2: the natural sorted trie order, forward and reverse (spliterating is also an option for these two orders). Use
nodeIterator(boolean)
,TreeOps.iterator()
orTreeOps.descendingIterator()
. A comparator is also provided for this order. - 3, 4: pre-order tree traversal, in which parent node is visited before sub-nodes, with sub-nodes visited in forward or reverse order
- 5, 6: post-order tree traversal, in which sub-nodes are visited before parent nodes, with sub-nodes visited in forward or reverse order
- 7, 8: prefix-block order, in which larger prefix blocks are visited before smaller, and blocks of equal size are visited in forward or reverse sorted order
All of these orderings are useful in specific contexts.
You can do lookup and containment checks on all the subnets and addresses in the trie at once, in constant time. A generic trie data structure lookup is O(m) where m is the entry length. For this trie, which operates on address bits, entry length is capped at 128 bits for IPv6 and 32 bits for IPv4. That makes lookup a constant time operation. Subnet containment or equality checks are also constant time since they work the same way as lookup, by comparing prefix bits.
For a generic trie data structure, construction is O(m * n) where m is entry length and n is the number of addresses, but for this trie, since entry length is capped at 128 bits for IPv6 and 32 bits for IPv4, construction is O(n), in linear proportion to the number of added elements.
This trie also allows for constant time size queries (count of added elements, not node count), by storing sub-trie size in each node. It works by updating the size of every node in the path to any added or removed node. This does not change insertion or deletion operations from being constant time (because tree-depth is limited to address bit count). At the same this makes size queries constant time, rather than being O(n) time.
This class is abstract and has a subclass for each address version or type. A single trie can use just a single address type or version, since it works with bits alone, and this cannot distinguish between different versions and types in the trie structure. More specifically, using different address bit lengths would:
- break the concept of containment, for example IPv6 address 0::/8 would be considered to contain IPv4 address 0.2.3.4
- break the concept of equality, for example MAC 1:2:3:*:*:* and IPv4 1.2.3.0/24 would be considered the same since they have the same prefix bits and length
Instead, you could aggregate multiple subtries to create a collection of multiple address types or versions.
You can use the method toString(boolean, AddressTrie...)
for a String that represents multiple tries as a single tree.
Tries are thread-safe when not being modified (elements added or removed), but are not thread-safe when one thread is modifying the trie.
For thread safety when modifying, one option is to use Collections.synchronizedNavigableSet(java.util.NavigableSet)
on asSet()
.
- Author:
- scfoley
- See Also:
-
Nested Class Summary
Nested ClassesModifier and TypeClassDescriptionstatic class
AddressTrie.AddressComparator<E extends Address>
A comparator that provides the same ordering used by the trie, an ordering that works with prefix block subnets and individual addresses.static class
AddressTrie.TrieComparator<E extends Address>
static class
AddressTrie.TrieNode<E extends Address>
A node for a compact binary prefix trie whose elements are prefix block subnets or addresses,Nested classes/interfaces inherited from interface inet.ipaddr.format.util.AddressTrieOps
AddressTrieOps.AddressTrieAddOps<E extends Address>, AddressTrieOps.AssociativeAddressTrieOps<K extends Address,
V>, AddressTrieOps.AssociativeAddressTriePutOps<K extends Address, V> -
Method Summary
Modifier and TypeMethodDescriptionboolean
Adds the given single address or prefix block subnet to the trie.Adds the given single address or prefix block subnet to the trie, if not already there.addTrie
(AddressTrie.TrieNode<E> trie) Adds nodes matching the given sub-root node and all of its sub-nodes to the trie, if not already there.Iterator
<? extends AddressTrie.TrieNode<E>> allNodeIterator
(boolean forward) Iterates through the nodes (not just the added nodes) in forward or reverse tree order.Spliterator
<? extends AddressTrie.TrieNode<E>> allNodeSpliterator
(boolean forward) Creates aSpliterator
over the nodes in forward or reverse natural tree order.asSet()
Returns a java.util.NavigableSet that uses this as the backing data structure.Iterator
<? extends AddressTrie.TrieNode<E>> blockSizeAllNodeIterator
(boolean lowerSubNodeFirst) Iterates all nodes in the trie, ordered by keys from largest prefix blocks to smallest, and then to individual addresses.<C> BinaryTreeNode.CachingIterator
<? extends AddressTrie.TrieNode<E>, E, C> Iterates all nodes, ordered by keys from largest prefix blocks to smallest, and then to individual addresses.Iterator
<? extends AddressTrie.TrieNode<E>> blockSizeNodeIterator
(boolean lowerSubNodeFirst) Iterates the added nodes in the trie, ordered by keys from largest prefix blocks to smallest, and then to individual addresses.ceilingAddedNode
(E addr) Returns the added node whose address is the lowest address greater than or equal to the given address.void
clear()
Removes all added nodes from the tree, after whichisEmpty()
will return trueclone()
Copies the trie, but not the keys or values.abstract AssociativeAddressTrie
<E, ? extends List<? extends AssociativeAddressTrie.AssociativeTrieNode<E, ?>>> Provides an associative trie in which the root and each added node are mapped to a list of their respective direct added nodes.Iterator
<? extends AddressTrie.TrieNode<E>> containedFirstAllNodeIterator
(boolean forwardSubNodeOrder) Returns an iterator that does a post-order binary tree traversal.Iterator
<? extends AddressTrie.TrieNode<E>> containedFirstIterator
(boolean forwardSubNodeOrder) Returns an iterator that does a post-order binary tree traversal of the added nodes.<C> BinaryTreeNode.CachingIterator
<? extends AddressTrie.TrieNode<E>, E, C> containingFirstAllNodeIterator
(boolean forwardSubNodeOrder) Returns an iterator that does a pre-order binary tree traversal.<C> BinaryTreeNode.CachingIterator
<? extends AddressTrie.TrieNode<E>, E, C> containingFirstIterator
(boolean forwardSubNodeOrder) Returns an iterator that does a pre-order binary tree traversal of the added nodes.boolean
Returns whether the given address or prefix block subnet is in the trie (as an added element).static <E extends Address>
Edecrement
(E addr) Returns the previous address according to the trie orderingTraverses the added node keys in reverse natural tree order.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.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.boolean
Returns whether the given argument is a trie with a set of nodes that equal the set of nodes in this trieReturns 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.Returns a comparator for the trie orderGets the node corresponding to the given address, returns null if not such element exists.getRoot()
Returns the root of this trieint
hashCode()
higherAddedNode
(E addr) Returns the added node whose address is the lowest address strictly greater than the given address.static <E extends Address>
Eincrement
(E addr) Returns the next address according to the trie orderingboolean
isEmpty()
Returns true if there are not any added nodes within this treeiterator()
Traverses the added node keys in natural tree order.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.int
nodeSize()
Returns the number of nodes in the trie, which is more than the number of elements.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.int
size()
Returns the number of elements in the tree.Creates aSpliterator
over the keys of the added nodes in natural tree order.Provides a flattened version of the trie showing only the contained added nodes and their containment structure, which is non-binary.toString()
Returns a visual representation of the tree with one node per line.toString
(boolean withNonAddedKeys) Returns a visual representation of the tree with one node per line, with or without the non-added keys.static String
toString
(boolean withNonAddedKeys, AddressTrie<?>... tries) Produces a visual representation of the given tries joined by a single root node, with one node per line.Methods inherited from interface inet.ipaddr.format.util.AddressTrieOps
getAddedNode
-
Method Details
-
increment
Returns the next address according to the trie ordering- Type Parameters:
E
-- Parameters:
addr
-- Returns:
-
decrement
Returns the previous address according to the trie ordering- Type Parameters:
E
-- Parameters:
addr
-- Returns:
-
isEmpty
public boolean isEmpty()Returns true if there are not any added nodes within this tree -
nodeSize
public int nodeSize()Returns the number of nodes in the trie, which is more than the number of elements.- Returns:
-
size
public int size()Returns the number of elements in the tree. Only nodes for whichBinaryTreeNode.isAdded()
returns true are counted. When zero is returned,isEmpty()
returns true.- Returns:
-
add
Description copied from interface:AddressTrieOps.AddressTrieAddOps
Adds the given single address or prefix block subnet to the trie.If the given address is not a single address nor prefix block, then this method throws IllegalArgumentException.
If not a single address nor prefix block, the
Partition
class can be used to convert the address before calling this method. Given a subnet s of type E and a trie of type AddressTrie<E>, such asIPv4Address
andIPv4AddressTrie
, you can convert and add the spanning prefix blocks withPartition.partitionWithSpanningBlocks(s).predicateForEach(trie::add)
, or you can convert and add using a single max block size withPartition.partitionWithSingleBlockSize(s).predicateForEach(trie::add)
.Returns true if the prefix block or address was inserted, false if already in the trie.
- Parameters:
addr
-- Returns:
-
addNode
Description copied from interface:AddressTrieOps.AddressTrieAddOps
Adds the given single address or prefix block subnet to the trie, if not already there.If the given address is not a single address nor prefix block, then this method throws IllegalArgumentException.
If not a single address nor prefix block, the
Partition
class can be used to convert the address before calling this method. SeeAddressTrieOps.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 useAddressTrieOps.getAddedNode(Address)
- Parameters:
addr
-- Returns:
-
constructAddedNodesTree
public abstract AssociativeAddressTrie<E,? extends List<? extends AssociativeAddressTrie.AssociativeTrieNode<E, constructAddedNodesTree()?>>> Provides an associative trie in which the root and each added node are mapped to a list of their respective direct added nodes. This trie provides an alternative non-binary tree structure of the added nodes. It is used bytoAddedNodesTreeString()
to produce a string showing the alternative structure. If there are no non-added nodes in this trie, then the alternative tree structure provided by this method is the same as the original trie.- Returns:
-
toAddedNodesTreeString
Provides a flattened version of the trie showing only the contained added nodes and their containment structure, which is non-binary. The root node is included, which may or may not be added.- Returns:
-
addTrie
Description copied from interface:AddressTrieOps.AddressTrieAddOps
Adds nodes matching the given sub-root node and all of its sub-nodes to the trie, if not already there.For each added in the given node that does not exist in the trie, a copy of each node will be made that matches the trie type (associative or not), and the copy will be inserted into the trie.
The node type need not match the node type of the trie, although the address type/version E must match. You can add associative nodes to tries with this method but associated values will all be null. If you want to preserve the values, use
AddressTrieOps.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.
- Parameters:
trie
-- Returns:
-
contains
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.- Parameters:
addr
-- Returns:
-
remove
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.
- Parameters:
addr
-- Returns:
- See Also:
-
removeElementsContainedBy
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.
- Parameters:
addr
-- Returns:
-
elementsContainedBy
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.- Parameters:
addr
-- Returns:
-
elementsContaining
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.- Parameters:
addr
-- Returns:
-
longestPrefixMatch
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)
- Parameters:
addr
-- Returns:
-
longestPrefixMatchNode
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.- Parameters:
addr
-- Returns:
-
elementContains
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)
.- Parameters:
addr
-- Returns:
-
getNode
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.- Parameters:
addr
-- Returns:
- See Also:
-
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.- Parameters:
forward
- if true, goes in ascending order, otherwise descending- Returns:
-
blockSizeNodeIterator
Iterates the added nodes in the trie, ordered by keys from largest prefix blocks to smallest, and then to individual addresses.This iterator supports the
Iterator.remove()
operation.- Parameters:
lowerSubNodeFirst
- if true, for blocks of equal size the lower is first, otherwise the reverse order- Returns:
-
blockSizeAllNodeIterator
public Iterator<? extends AddressTrie.TrieNode<E>> blockSizeAllNodeIterator(boolean lowerSubNodeFirst) Iterates all nodes in the trie, ordered by keys from largest prefix blocks to smallest, and then to individual addresses.This iterator supports the
Iterator.remove()
operation.- Parameters:
lowerSubNodeFirst
- if true, for blocks of equal size the lower is first, otherwise the reverse order- Returns:
-
blockSizeCachingAllNodeIterator
public <C> BinaryTreeNode.CachingIterator<? extends AddressTrie.TrieNode<E>,E, blockSizeCachingAllNodeIterator()C> Iterates all nodes, ordered by keys from largest prefix blocks to smallest, and then to individual addresses.This iterator supports the
Iterator.remove()
operation.- Returns:
-
containingFirstIterator
public <C> BinaryTreeNode.CachingIterator<? extends AddressTrie.TrieNode<E>,E, 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.- 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, 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.- Parameters:
forwardSubNodeOrder
- if true, a left sub-node will be visited before the right sub-node of the same parent node.- Returns:
-
containedFirstIterator
public Iterator<? extends AddressTrie.TrieNode<E>> containedFirstIterator(boolean forwardSubNodeOrder) Description copied from interface:TreeOps
Returns an iterator that does a post-order binary tree traversal of the added nodes. All added sub-nodes will be visited before their parent nodes. For an address trie this means contained addresses and subnets will be visited before their containing subnet blocks.This iterator supports the
Iterator.remove()
operation.See
TreeOps
for more details on the ordering.- Parameters:
forwardSubNodeOrder
- if true, a left sub-node will be visited before the right sub-node of the same parent node.- Returns:
-
containedFirstAllNodeIterator
public Iterator<? extends AddressTrie.TrieNode<E>> containedFirstAllNodeIterator(boolean forwardSubNodeOrder) Description copied from interface:TreeOps
Returns an iterator that does a post-order binary tree traversal. All sub-nodes will be visited before their parent nodes. For an address trie this means contained addresses and subnets will be visited before their containing subnet blocks.This iterator does not support the
Iterator.remove()
operation. IfIterator.remove()
is called it will throwUnsupportedOperationException
.See
TreeOps
for more details on the ordering.- Parameters:
forwardSubNodeOrder
- if true, a left sub-node will be visited before the right sub-node of the same parent node.- Returns:
-
spliterator
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.- Returns:
-
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.- 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.- 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.- Parameters:
forward
- if true, goes in ascending order, otherwise descending- 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.- Parameters:
forward
- if true, goes in ascending order, otherwise descending- Returns:
-
firstNode
Description copied from interface:AddressTrieOps
Returns the node with the first (lowest valued) key, whether the node is added or not- Returns:
-
firstAddedNode
Description copied from interface:AddressTrieOps
Returns the added node with the first (lowest valued) key, or null if there are no added entries in this trie or subtrie- Returns:
-
lastNode
Description copied from interface:AddressTrieOps
Returns the node with the last (highest valued) key, whether the node is added or not- Returns:
-
lastAddedNode
Description copied from interface:AddressTrieOps
Returns the added node with the last (highest valued) key, or null if there are no added elements in this trie or subtrie- Returns:
-
getComparator
Returns a comparator for the trie order- Returns:
-
asSet
Returns a java.util.NavigableSet that uses this as the backing data structure. Added elements of this trie are the elements in the set.- Returns:
-
getRoot
Returns the root of this trie- Returns:
-
lowerAddedNode
Description copied from interface:AddressTrieOps
Returns the added node whose address is the highest address strictly less than the given address.- Parameters:
addr
-- Returns:
-
floorAddedNode
Description copied from interface:AddressTrieOps
Returns the added node whose address is the highest address less than or equal to the given address.- Parameters:
addr
-- Returns:
-
higherAddedNode
Description copied from interface:AddressTrieOps
Returns the added node whose address is the lowest address strictly greater than the given address.- Parameters:
addr
-- Returns:
-
ceilingAddedNode
Description copied from interface:AddressTrieOps
Returns the added node whose address is the lowest address greater than or equal to the given address.- Parameters:
addr
-- Returns:
-
clear
public void clear()Removes all added nodes from the tree, after whichisEmpty()
will return true -
clone
Copies the trie, but not the keys or values. -
equals
Returns whether the given argument is a trie with a set of nodes that equal the set of nodes in this trie -
toString
Returns a visual representation of the tree with one node per line. -
toString
Returns a visual representation of the tree with one node per line, with or without the non-added keys. -
toString
Produces a visual representation of the given tries joined by a single root node, with one node per line.- Parameters:
withNonAddedKeys
-tries
-- Returns:
-
iterator
Description copied from interface:TreeOps
Traverses the added node keys in natural tree order.See
TreeOps
for more details on the ordering. -
descendingIterator
Description copied from interface:TreeOps
Traverses the added node keys in reverse natural tree order.See
TreeOps
for more details on the ordering.- Specified by:
descendingIterator
in interfaceTreeOps<E extends Address>
- Returns:
-
hashCode
public int hashCode()
-