Module inet.ipaddr

Class AddressTrie<E extends Address>

java.lang.Object
inet.ipaddr.format.util.AddressTrie<E>
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

public abstract class AddressTrie<E extends Address> extends Object
A compact binary trie (aka compact binary prefix tree, or binary radix trie), for addresses and/or CIDR prefix block subnets. The prefixes in used by the prefix trie are the CIDR prefixes, or the full address in the case of individual addresses with no prefix length. The elements of the trie are CIDR prefix blocks or addresses.

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() or TreeOps.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:
  • Method Details

    • increment

      public static <E extends Address> E increment(E addr)
      Returns the next address according to the trie ordering
      Type Parameters:
      E -
      Parameters:
      addr -
      Returns:
    • decrement

      public static <E extends Address> E decrement(E addr)
      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 which BinaryTreeNode.isAdded() returns true are counted. When zero is returned, isEmpty() returns true.
      Returns:
    • add

      public boolean add(E addr)
      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 as IPv4Address and IPv4AddressTrie, you can convert and add the spanning prefix blocks with Partition.partitionWithSpanningBlocks(s).predicateForEach(trie::add), or you can convert and add using a single max block size with Partition.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

      public AddressTrie.TrieNode<E> addNode(E addr)
      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. 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)

      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 by 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.
      Returns:
    • toAddedNodesTreeString

      public String 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.

      See constructAddedNodesTree()

      Returns:
    • addTrie

      public AddressTrie.TrieNode<E> addTrie(AddressTrie.TrieNode<E> trie)
      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

      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. 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.

      Parameters:
      addr -
      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. 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.

      Parameters:
      addr -
      Returns:
      See Also:
    • 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, 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.

      Parameters:
      addr -
      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. 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.

      Parameters:
      addr -
      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. 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.

      Parameters:
      addr -
      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. 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)

      Parameters:
      addr -
      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. 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.

      Parameters:
      addr -
      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. 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).

      Parameters:
      addr -
      Returns:
    • 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. See AddressTrieOps.AddressTrieAddOps.add(Address) for more details.

      Parameters:
      addr -
      Returns:
      See Also:
    • allNodeIterator

      public Iterator<? extends AddressTrie.TrieNode<E>> allNodeIterator(boolean forward)
      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 the Iterator.remove() operation.

      Parameters:
      forward - if true, goes in ascending order, otherwise descending
      Returns:
    • blockSizeNodeIterator

      public 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.

      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,C> blockSizeCachingAllNodeIterator()
      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,C> 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.

      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,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:

      
      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.

      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. If Iterator.remove() is called it will throw UnsupportedOperationException.

      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

      public Spliterator<E> spliterator()
      Description copied from interface: TreeOps
      Creates a Spliterator over the keys of the added nodes in natural tree order.

      See TreeOps for more details on the ordering.

      Returns:
    • descendingSpliterator

      public Spliterator<E> descendingSpliterator()
      Description copied from interface: TreeOps
      Creates a Spliterator over the keys of the added nodes in descending natural tree order.

      See TreeOps for more details on the ordering.

      Returns:
    • nodeSpliterator

      public Spliterator<? extends AddressTrie.TrieNode<E>> nodeSpliterator(boolean forward)
      Description copied from interface: TreeOps
      Creates a Spliterator 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

      public Spliterator<? extends AddressTrie.TrieNode<E>> allNodeSpliterator(boolean forward)
      Description copied from interface: TreeOps
      Creates a Spliterator 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

      public Iterator<? extends AddressTrie.TrieNode<E>> nodeIterator(boolean forward)
      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

      public AddressTrie.TrieNode<E> firstNode()
      Description copied from interface: AddressTrieOps
      Returns the node with the first (lowest valued) key, whether the node is added or not
      Returns:
    • firstAddedNode

      public AddressTrie.TrieNode<E> 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

      public AddressTrie.TrieNode<E> lastNode()
      Description copied from interface: AddressTrieOps
      Returns the node with the last (highest valued) key, whether the node is added or not
      Returns:
    • lastAddedNode

      public AddressTrie.TrieNode<E> 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

      public Comparator<E> getComparator()
      Returns a comparator for the trie order
      Returns:
    • asSet

      public AddressTrieSet<E> 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

      public AddressTrie.TrieNode<E> getRoot()
      Returns the root of this trie
      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.
      Parameters:
      addr -
      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.
      Parameters:
      addr -
      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.
      Parameters:
      addr -
      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.
      Parameters:
      addr -
      Returns:
    • clear

      public void clear()
      Removes all added nodes from the tree, after which isEmpty() will return true
    • clone

      public AddressTrie<E> clone()
      Copies the trie, but not the keys or values.
    • equals

      public 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
    • toString

      public String toString()
      Returns a visual representation of the tree with one node per line.
    • toString

      public String toString(boolean withNonAddedKeys)
      Returns a visual representation of the tree with one node per line, with or without the non-added keys.
    • toString

      public 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.
      Parameters:
      withNonAddedKeys -
      tries -
      Returns:
    • iterator

      public Iterator<E> iterator()
      Description copied from interface: TreeOps
      Traverses the added node keys in natural tree order.

      See TreeOps for more details on the ordering.

      Specified by:
      iterator in interface Iterable<E extends Address>
      Specified by:
      iterator in interface TreeOps<E extends Address>
      Returns:
    • descendingIterator

      public Iterator<E> 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 interface TreeOps<E extends Address>
      Returns:
    • hashCode

      public int hashCode()
      Overrides:
      hashCode in class Object