Module inet.ipaddr

Class AddressTrie.TrieNode<E extends Address>

    • Method Detail

      • blockSizeNodeIterator

        public java.util.Iterator<? extends AddressTrie.TrieNode<E>> blockSizeNodeIterator​(boolean lowerSubNodeFirst)
        Iterates the added nodes, ordered by keys from largest prefix blocks to smallest and then to individual addresses, in the sub-trie with this node as the root.

        This iterator supports the Iterator.remove() operation.

        Parameters:
        lowerSubNodeFirst - if true, for blocks of equal size the lower is first, otherwise the reverse order
        Returns:
      • blockSizeAllNodeIterator

        public java.util.Iterator<? extends AddressTrie.TrieNode<E>> blockSizeAllNodeIterator​(boolean lowerSubNodeFirst)
        Iterates all the nodes, ordered by keys from largest prefix blocks to smallest and then to individual addresses, in the sub-trie with this node as the root.

        This iterator supports the Iterator.remove() operation.

        Parameters:
        lowerSubNodeFirst - if true, for blocks of equal size the lower is first, otherwise the reverse order
        Returns:
      • blockSizeCachingAllNodeIterator

        public <C> BinaryTreeNode.CachingIterator<? extends AddressTrie.TrieNode<E>,​E,​C> blockSizeCachingAllNodeIterator()
        Iterates all nodes, ordered by keys from largest prefix blocks to smallest and then to individual addresses, in the sub-trie with this node as the root.
        Returns:
      • containingFirstIterator

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

        Specified by:
        containingFirstIterator in interface AddressTrieOps<E extends Address>
        Specified by:
        containingFirstIterator in interface TreeOps<E extends Address>
        Overrides:
        containingFirstIterator in class BinaryTreeNode<E extends Address>
        Parameters:
        forwardSubNodeOrder - if true, a left sub-node will be visited before the right sub-node of the same parent node.
        Returns:
      • containingFirstAllNodeIterator

        public <C> BinaryTreeNode.CachingIterator<? extends AddressTrie.TrieNode<E>,​E,​C> containingFirstAllNodeIterator​(boolean forwardSubNodeOrder)
        Description copied from interface: TreeOps
        Returns an iterator that does a pre-order binary tree traversal. All nodes will be visited before their sub-nodes. For an address trie this means containing subnet blocks will be visited before their contained addresses and subnet blocks.

        This iterator supports the Iterator.remove() operation.

        Once a given node is visited, the iterator allows you to cache an object corresponding to the lower or upper sub-node that can be retrieved when you later visit that sub-node. That allows you to provide iteration context from a parent to its sub-nodes when iterating. The caching and retrieval is done in constant-time and linear space (proportional to tree size).

        Here is an example showing usage of the caching. Consider this recursive code doing a pre-order traversal:

        
        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.

        Specified by:
        containingFirstAllNodeIterator in interface AddressTrieOps<E extends Address>
        Specified by:
        containingFirstAllNodeIterator in interface TreeOps<E extends Address>
        Overrides:
        containingFirstAllNodeIterator in class BinaryTreeNode<E extends Address>
        Parameters:
        forwardSubNodeOrder - if true, a left sub-node will be visited before the right sub-node of the same parent node.
        Returns:
      • containedFirstIterator

        public java.util.Iterator<? extends AddressTrie.TrieNode<E>> containedFirstIterator​(boolean forwardSubNodeOrder)
        Description copied from interface: TreeOps
        Returns an iterator that does a post-order binary tree traversal of the added nodes. All added sub-nodes will be visited before their parent nodes. For an address trie this means contained addresses and subnets will be visited before their containing subnet blocks.

        This iterator supports the Iterator.remove() operation.

        See TreeOps for more details on the ordering.

        Specified by:
        containedFirstIterator in interface AddressTrieOps<E extends Address>
        Specified by:
        containedFirstIterator in interface TreeOps<E extends Address>
        Overrides:
        containedFirstIterator in class BinaryTreeNode<E extends Address>
        Parameters:
        forwardSubNodeOrder - if true, a left sub-node will be visited before the right sub-node of the same parent node.
        Returns:
      • containedFirstAllNodeIterator

        public java.util.Iterator<? extends AddressTrie.TrieNode<E>> containedFirstAllNodeIterator​(boolean forwardSubNodeOrder)
        Description copied from interface: TreeOps
        Returns an iterator that does a post-order binary tree traversal. All sub-nodes will be visited before their parent nodes. For an address trie this means contained addresses and subnets will be visited before their containing subnet blocks.

        This iterator does not support the Iterator.remove() operation. If Iterator.remove() is called it will throw UnsupportedOperationException.

        See TreeOps for more details on the ordering.

        Specified by:
        containedFirstAllNodeIterator in interface AddressTrieOps<E extends Address>
        Specified by:
        containedFirstAllNodeIterator in interface TreeOps<E extends Address>
        Overrides:
        containedFirstAllNodeIterator in class BinaryTreeNode<E extends Address>
        Parameters:
        forwardSubNodeOrder - if true, a left sub-node will be visited before the right sub-node of the same parent node.
        Returns:
      • nodeSpliterator

        public java.util.Spliterator<? extends AddressTrie.TrieNode<E>> nodeSpliterator​(boolean forward)
        Description copied from interface: TreeOps
        Creates a Spliterator over the added nodes in forward or reverse natural tree order.

        See TreeOps for more details on the ordering.

        Specified by:
        nodeSpliterator in interface AddressTrieOps<E extends Address>
        Specified by:
        nodeSpliterator in interface TreeOps<E extends Address>
        Parameters:
        forward - if true, goes in ascending order, otherwise descending
        Returns:
      • spliterator

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

        See TreeOps for more details on the ordering.

        Specified by:
        spliterator in interface java.lang.Iterable<E extends Address>
        Specified by:
        spliterator in interface TreeOps<E extends Address>
      • descendingSpliterator

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

        Specified by:
        descendingSpliterator in interface TreeOps<E extends Address>
        Returns:
      • contains

        public boolean contains​(E addr)
        Description copied from interface: AddressTrieOps
        Returns whether the given address or prefix block subnet is in the trie (as an added element).

        If the given address is not a single address nor prefix block, then this method throws IllegalArgumentException.

        If not a single address nor prefix block, the Partition class can be used to convert the address before calling this method. 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.

        Specified by:
        contains in interface AddressTrieOps<E extends Address>
        Returns:
      • remove

        public boolean remove​(E addr)
        Description copied from interface: AddressTrieOps
        Removes the given single address or prefix block subnet from the trie.

        Removing an element will not remove contained elements (nodes for contained blocks and addresses).

        If the given address is not a single address nor prefix block, then this method throws IllegalArgumentException.

        If not a single address nor prefix block, the Partition class can be used to convert the address before calling this method. 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.

        Specified by:
        remove in interface AddressTrieOps<E extends Address>
        Returns:
        See Also:
        AddressTrieOps.removeElementsContainedBy(Address)
      • getNode

        public AddressTrie.TrieNode<E> getNode​(E addr)
        Description copied from interface: AddressTrieOps
        Gets the node corresponding to the given address, returns null if not such element exists.

        If added is true, returns only nodes representing added elements, otherwise returns any node, including a prefix block that was not added.

        If the given address is not a single address nor prefix block, then this method throws IllegalArgumentException.

        If not a single address nor prefix block, the Partition class can be used to convert the address before calling this method. See AddressTrieOps.AddressTrieAddOps.add(Address) for more details.

        Specified by:
        getNode in interface AddressTrieOps<E extends Address>
        Returns:
        See Also:
        AddressTrieOps.contains(Address)
      • removeElementsContainedBy

        public AddressTrie.TrieNode<E> removeElementsContainedBy​(E addr)
        Description copied from interface: AddressTrieOps
        Removes any single address or prefix block subnet from the trie that is contained in the given individual address or prefix block subnet.

        Goes further than AddressTrieOps.remove(Address), not requiring a match to an inserted node, and also removing all the sub-nodes of any removed node or sub-node.

        For example, after inserting 1.2.3.0 and 1.2.3.1, passing 1.2.3.0/31 to AddressTrieOps.removeElementsContainedBy(Address) will remove them both, 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.

        Specified by:
        removeElementsContainedBy in interface AddressTrieOps<E extends Address>
        Returns:
      • elementsContainedBy

        public AddressTrie.TrieNode<E> elementsContainedBy​(E addr)
        Description copied from interface: AddressTrieOps
        Checks if a part of this trie is contained by the given prefix block subnet or individual address.

        If the given address is not a single address nor prefix block, then this method throws IllegalArgumentException.

        If not a single address nor prefix block, the Partition class can be used to convert the address before calling this method. 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.

        Specified by:
        elementsContainedBy in interface AddressTrieOps<E extends Address>
        Returns:
      • elementsContaining

        public AddressTrie.TrieNode<E> elementsContaining​(E addr)
        Description copied from interface: AddressTrieOps
        Finds the added subnets and/or addresses in the trie that contain the given individual address or prefix block subnet.

        If the given address is not a single address nor prefix block, then this method throws IllegalArgumentException.

        If not a single address nor prefix block, the Partition class can be used to convert the address before calling this method. 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.

        Specified by:
        elementsContaining in interface AddressTrieOps<E extends Address>
        Returns:
      • elementContains

        public boolean elementContains​(E addr)
        Description copied from interface: AddressTrieOps
        Checks if a prefix block subnet or address in the trie contains the given subnet or address.

        If the given address is not a single address nor prefix block, then this method throws IllegalArgumentException.

        If not a single address nor prefix block, the Partition class can be used to convert the address before calling this method. 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).

        Specified by:
        elementContains in interface AddressTrieOps<E extends Address>
        Returns:
      • asNewTrie

        public AddressTrie<E> asNewTrie()
        Creates a new sub-trie, copying the nodes starting with this node as root. The nodes are copies of the nodes in this sub-trie, but their keys and values are not copies.
      • equals

        public boolean equals​(java.lang.Object o)
        Description copied from class: BinaryTreeNode
        Returns whether the key values match those of the given node
        Overrides:
        equals in class BinaryTreeNode<E extends Address>