inet.ipaddr.format.util

Interface TreeOps<E>

Type Parameters:

E -

All Superinterfaces:

Cloneable, Iterable<E>, Serializable

All Known Subinterfaces:

AddressTrieOps<E>, AddressTrieOps.AddressTrieAddOps<E>, AddressTrieOps.AssociativeAddressTrieOps<K,V>, AddressTrieOps.AssociativeAddressTriePutOps<K,V>

All Known Implementing Classes:

AddressTrie, AddressTrie.TrieNode, AssociativeAddressTrie, AssociativeAddressTrie.AssociativeTrieNode, BinaryTreeNode, IPv4AddressAssociativeTrie, IPv4AddressAssociativeTrie.IPv4AssociativeTrieNode, IPv4AddressTrie, IPv4AddressTrie.IPv4TrieNode, IPv6AddressAssociativeTrie, IPv6AddressAssociativeTrie.IPv6AssociativeTrieNode, IPv6AddressTrie, IPv6AddressTrie.IPv6TrieNode, MACAddressAssociativeTrie, MACAddressAssociativeTrie.MACAssociativeTrieNode, MACAddressTrie, MACAddressTrie.MACTrieNode

public interface TreeOps<E>
extends Iterable<E>, Serializable, Cloneable

TreeOps is an interface to the operations supported by both trees and tree nodes: traversals, cloning, and serialization.

The traversal orders are demonstrated by the following code:

static class Node extends BinaryTreeNode<Integer> {

        private static final long serialVersionUID = 1L;

        Node(int i) {
                super(i);
                setAdded(true);
        }
        
        protected void setUpper(int upper) {
                super.setUpper(new Node(upper));
        }

        protected void setLower(int lower) {
                super.setLower(new Node(lower));
        }
        
        @Override
        public Node getUpperSubNode() {
                return (Node) super.getUpperSubNode();
        }

        @Override
        public Node getLowerSubNode() {
                return (Node) super.getLowerSubNode();
        }
}

static void trieOrders() {
        Node root = new Node(1);
        root.setLower(2);
        root.setUpper(3);
        root.getLowerSubNode().setLower(4);
        root.getLowerSubNode().setUpper(5);
        root.getUpperSubNode().setLower(6);
        root.getUpperSubNode().setUpper(7);
        root.getLowerSubNode().getLowerSubNode().setLower(8);
        root.getLowerSubNode().getLowerSubNode().setUpper(9);
        root.getLowerSubNode().getUpperSubNode().setLower(10);
        root.getLowerSubNode().getUpperSubNode().setUpper(11);
        root.getUpperSubNode().getLowerSubNode().setLower(12);
        root.getUpperSubNode().getLowerSubNode().setUpper(13);
        root.getUpperSubNode().getUpperSubNode().setLower(14);
        root.getUpperSubNode().getUpperSubNode().setUpper(15);
        
        PrintStream out = System.out;
        out.println(root.toTreeString(true, false));
        
        out.println("natural tree order:");
        print(root.nodeIterator(true));
        out.println("reverse natural tree order:");
        print(root.nodeIterator(false));
        out.println("pre-order traversal, lower node first:");
        print(root.containingFirstIterator(true));
        out.println("pre-order traversal, upper node first:");
        print(root.containingFirstIterator(false));
        out.println("post-order traversal, lower node first:");
        print(root.containedFirstIterator(true));
        out.println("post-order traversal, upper node first:");
        print(root.containedFirstIterator(false));
}

static void print(Iterator<? extends BinaryTreeNode<Integer>> iterator) {
        PrintStream out = System.out;
        while(iterator.hasNext()) {
                Integer i = iterator.next().getKey();
                out.print(i);
                out.print(' ');
        }
        out.println();
        out.println();
}

The code gives the following output (the tree is printed with lower nodes before upper nodes):

● 1
├─● 2
│ ├─● 4
│ │ ├─● 8
│ │ └─● 9
│ └─● 5
│   ├─● 10
│   └─● 11
└─● 3
  ├─● 6
  │ ├─● 12
  │ └─● 13
  └─● 7
    ├─● 14
    └─● 15

natural tree order:
8 4 9 2 10 5 11 1 12 6 13 3 14 7 15 

reverse natural tree order:
15 7 14 3 13 6 12 1 11 5 10 2 9 4 8 

pre-order traversal, lower node first:
1 2 4 8 9 5 10 11 3 6 12 13 7 14 15 

pre-order traversal, upper node first:
1 3 7 15 14 6 13 12 2 5 11 10 4 9 8 

post-order traversal, lower node first:
8 9 4 10 11 5 2 12 13 6 14 15 7 3 1 

post-order traversal, upper node first:
15 14 7 13 12 6 3 11 10 5 9 8 4 2 1 

Method Summary

Modifier and Type	Method and Description
Iterator<? extends BinaryTreeNode<E>>	allNodeIterator(boolean forward) Iterates through the nodes (not just the added nodes) in forward or reverse tree order.
default Spliterator<? extends BinaryTreeNode<E>>	allNodeSpliterator(boolean forward) Creates a Spliterator over the nodes in forward or reverse natural tree order.
Iterator<? extends BinaryTreeNode<E>>	containedFirstAllNodeIterator(boolean forwardSubNodeOrder) Returns an iterator that does a post-order binary tree traversal.
Iterator<? extends BinaryTreeNode<E>>	containedFirstIterator(boolean forwardSubNodeOrder) Returns an iterator that does a post-order binary tree traversal of the added nodes.
<C> BinaryTreeNode.CachingIterator<? extends BinaryTreeNode<E>,E,C>	containingFirstAllNodeIterator(boolean forwardSubNodeOrder) Returns an iterator that does a pre-order binary tree traversal.
<C> BinaryTreeNode.CachingIterator<? extends BinaryTreeNode<E>,E,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.
default Spliterator<E>	descendingSpliterator() Creates a Spliterator over the keys of the added nodes in descending natural tree order.
Iterator<E>	iterator() Traverses the added node keys in natural tree order.
Iterator<? extends BinaryTreeNode<E>>	nodeIterator(boolean forward) Iterates through the added nodes in forward or reverse natural tree order.
default Spliterator<? extends BinaryTreeNode<E>>	nodeSpliterator(boolean forward) Creates a Spliterator over the added nodes in forward or reverse natural tree order.
default Spliterator<E>	spliterator() Creates a Spliterator over the keys of the added nodes in natural tree order.

Methods inherited from interface java.lang.Iterable

forEach

Method Detail

iterator

Iterator<E> iterator()

Traverses the added node keys in natural tree order.

See TreeOps for more details on the ordering.

Specified by:

iterator in interface Iterable<E>

Returns:

descendingIterator

Iterator<E> descendingIterator()

Traverses the added node keys in reverse natural tree order.

See TreeOps for more details on the ordering.

Returns:

spliterator

default Spliterator<E> spliterator()

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 Iterable<E>

Returns:

descendingSpliterator

default Spliterator<E> descendingSpliterator()

Creates a Spliterator over the keys of the added nodes in descending natural tree order.

See TreeOps for more details on the ordering.

Returns:

nodeIterator

Iterator<? extends BinaryTreeNode<E>> nodeIterator(boolean forward)

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:

allNodeIterator

Iterator<? extends BinaryTreeNode<E>> allNodeIterator(boolean forward)

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:

containingFirstIterator

<C> BinaryTreeNode.CachingIterator<? extends BinaryTreeNode<E>,E,C> containingFirstIterator(boolean forwardSubNodeOrder)

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

<C> BinaryTreeNode.CachingIterator<? extends BinaryTreeNode<E>,E,C> containingFirstAllNodeIterator(boolean forwardSubNodeOrder)

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

Iterator<? extends BinaryTreeNode<E>> containedFirstIterator(boolean forwardSubNodeOrder)

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

Iterator<? extends BinaryTreeNode<E>> containedFirstAllNodeIterator(boolean forwardSubNodeOrder)

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:

nodeSpliterator

default Spliterator<? extends BinaryTreeNode<E>> nodeSpliterator(boolean forward)

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

default Spliterator<? extends BinaryTreeNode<E>> allNodeSpliterator(boolean forward)

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: