BinaryTreeNode (IPAddress javadoc by seancfoley)

java.lang.Object
- inet.ipaddr.format.util.BinaryTreeNode<E>

Type Parameters:

E -

All Implemented Interfaces:

TreeOps<E>, Serializable, Cloneable, Iterable<E>

Direct Known Subclasses:

AddressTrie.TrieNode
```
public class BinaryTreeNode<E>
extends Object
implements TreeOps<E>
```
A binary tree node.
Some binary tree nodes are considered "added" and others are not. Those nodes created for key elements added to the tree are "added" nodes. Those that are not added are those nodes created to serve as junctions for the added nodes. Only added elements contribute to the size of a tree. When removing nodes, non-added nodes are removed automatically whenever they are no longer needed, which is when an added node has less than two added sub-nodes.
BinaryTreeNode objects have a read-only API, in the sense that they cannot be constructed directly. Instead they are created indirectly by tree operations or by cloning existing nodes.
The API does allow you to remove them from trees, or to clone them. They can also be used to traverse a tree.
Nodes have various properties: the key, parent node, lower sub-node, upper sub-node, "added" property, and size. The "added" property can change if the node changes status following tree operations. If removed from a tree the parent property can change, and the sub-nodes can change when sub-nodes are removed from the tree, or other nodes are inserted into the tree, changing sub-nodes. However, none of these can be explicitly changed directly, they can only be changed indirectly by tree operations. The key of a node never changes.

See Also:

Serialized Form

Nested Class Summary

Nested Classes
Modifier and Type Class and Description

static interface BinaryTreeNode.CachingIterator<N extends BinaryTreeNode<E>,E,C>

Nested Classes
Modifier and Type	Class and Description
`static interface`	`BinaryTreeNode.CachingIterator<N extends BinaryTreeNode<E>,E,C>`

Method Summary

All Methods Instance Methods Concrete Methods
Modifier and Type	Method and Description
`Iterator<? extends BinaryTreeNode<E>>`	`allNodeIterator(boolean forward)` Iterates through all the nodes of the sub-tree with this node as the root, in forward or reverse tree order.
`void`	`clear()` Removes this node and all sub-nodes from the tree, after which isEmpty() will return true.
`BinaryTreeNode<E>`	`clone()` Clones the node.
`BinaryTreeNode<E>`	`cloneTree()` Clones the sub-tree starting with this node as root.
`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()` Returns an iterator that iterates through the elements of the subtrie with this node as the root.
`boolean`	`equals(Object o)` Returns whether the key values match those of the given node
`BinaryTreeNode<E>`	`firstAddedNode()` Returns the first (lowest valued) added node in the sub-tree originating from this node, or null if there are no added entries in this tree or sub-tree
`BinaryTreeNode<E>`	`firstNode()` Returns the first (lowest valued) node in the sub-tree originating from this node.
`E`	`getKey()` Gets the key used for placing the node in the tree.
`BinaryTreeNode<E>`	`getLowerSubNode()` Gets the direct child node whose key is smallest in value
`BinaryTreeNode<E>`	`getParent()` Gets the node from which this node is a direct child node, or null if this is the root.
`BinaryTreeNode<E>`	`getUpperSubNode()` Gets the direct child node whose key is largest in value
`int`	`hashCode()` The hash code is the hash code of the key value
`boolean`	`isAdded()` Some binary tree nodes are considered "added" and others are not.
`boolean`	`isEmpty()` Returns where there are not any elements in the sub-tree with this node as the root.
`boolean`	`isLeaf()` Returns whether this node is in the tree (is a node for which `isAdded()` is true) and additional there are other elements in the sub-tree with this node as the root.
`boolean`	`isRoot()` Returns whether this is the root of the backing tree.
`Iterator<E>`	`iterator()` Returns an iterator that iterates through the elements of the sub-tree with this node as the root.
`BinaryTreeNode<E>`	`lastAddedNode()` Returns the last (highest valued) added node in the sub-tree originating from this node, or null if there are no added entries in this tree or sub-tree
`BinaryTreeNode<E>`	`lastNode()` Returns the last (highest valued) node in the sub-tree originating from this node.
`BinaryTreeNode<E>`	`nextAddedNode()` Returns the next node in the tree that is an added node, following the tree order, or null if there is no such node.
`BinaryTreeNode<E>`	`nextNode()` Returns the node that follows this node following the tree order
`Iterator<? extends BinaryTreeNode<E>>`	`nodeIterator(boolean forward)` Iterates through the added nodes of the sub-tree with this node as the root, in forward or reverse tree order.
`int`	`nodeSize()` Returns the count of all nodes in the tree starting from this node and extending to all sub-nodes.
`BinaryTreeNode<E>`	`previousAddedNode()` Returns the previous node in the tree that is an added node, following the tree order in reverse, or null if there is no such node.
`BinaryTreeNode<E>`	`previousNode()` Returns the node that precedes this node following the tree order.
`void`	`remove()` Removes this node from the list of added nodes, and also removes from the tree if possible.
`void`	`setAdded()` Make this node an added node, which is equivalent to adding the corresponding address to the tree.
`int`	`size()` Returns the count of nodes added to the sub-tree starting from this node as root and moving downwards to sub-nodes.
`String`	`toString()` Returns a visual representation of this node including the key, with an open circle indicating this node is not an added node, a closed circle indicating this node is an added node.
`String`	`toTreeString(boolean withNonAddedKeys, boolean withSizes)` Returns a visual representation of the sub-tree with this node as root, with one node per line.
`boolean`	`treeEquals(BinaryTreeNode<?> other)` Returns whether the sub-tree represented by this node as the root node matches the given sub-tree
`int`	`treeHashCode()` The hash code is the sum of the hash codes of all the added elements in the sub-tree with this node as the root

Methods inherited from class java.lang.Object
getClass, notify, notifyAll, wait, wait, wait

Methods inherited from interface inet.ipaddr.format.util.TreeOps
allNodeSpliterator, descendingSpliterator, nodeSpliterator, spliterator

Methods inherited from interface java.lang.Iterable
forEach

- Method Detail
  - getKey
```
public E getKey()
```
    Gets the key used for placing the node in the tree.
    
    Returns:
    
    the key used for placing the node in the tree.
  - isRoot
```
public boolean isRoot()
```
    Returns whether this is the root of the backing tree.
    
    Returns:
  - getParent
```
public BinaryTreeNode<E> getParent()
```
    Gets the node from which this node is a direct child node, or null if this is the root.
    
    Returns:
  - getUpperSubNode
```
public BinaryTreeNode<E> getUpperSubNode()
```
    Gets the direct child node whose key is largest in value
    
    Returns:
  - getLowerSubNode
```
public BinaryTreeNode<E> getLowerSubNode()
```
    Gets the direct child node whose key is smallest in value
    
    Returns:
  - isAdded
```
public boolean isAdded()
```
    Some binary tree nodes are considered "added" and others are not. Those nodes created for key elements added to the tree are "added" nodes. Those that are not added are those nodes created to serve as junctions for the added nodes. Only added elements contribute to the size of a tree. When removing nodes, non-added nodes are removed automatically whenever they are no longer needed, which is when an added node has less than two added sub-nodes.
    
    Returns:
    
    whether this node represents an element added to the tree
  - setAdded
```
public void setAdded()
```
    Make this node an added node, which is equivalent to adding the corresponding address to the tree. If already added, this method has no effect.
    You cannot set an added node to non-added, for that you should remove the node from the tree by calling remove(). A non-added node will only remain in the tree if it needs to in the tree.
  - size
```
public int size()
```
    Returns the count of nodes added to the sub-tree starting from this node as root and moving downwards to sub-nodes. This is a constant-time operation since the size is maintained in each node and adjusted with each add and remove operation in the sub-tree.
    
    Returns:
  - nodeSize
```
public int nodeSize()
```
    Returns the count of all nodes in the tree starting from this node and extending to all sub-nodes. Unlike size(), this is not a constant-time operation and must visit all sub-nodes of this node.
    
    Returns:
  - remove
```
public void remove()
```
    Removes this node from the list of added nodes, and also removes from the tree if possible. If it has two sub-nodes, it cannot be removed from the tree, in which case it is marked as not "added", nor is it counted in the tree size. Only added nodes can be removed from the tree. If this node is not added, this method does nothing.
  - clear
```
public void clear()
```
    Removes this node and all sub-nodes from the tree, after which isEmpty() will return true.
  - isEmpty
```
public boolean isEmpty()
```
    Returns where there are not any elements in the sub-tree with this node as the root.
  - isLeaf
```
public boolean isLeaf()
```
    Returns whether this node is in the tree (is a node for which isAdded() is true) and additional there are other elements in the sub-tree with this node as the root.
  - firstNode
```
public BinaryTreeNode<E> firstNode()
```
    Returns the first (lowest valued) node in the sub-tree originating from this node.
    
    Returns:
  - firstAddedNode
```
public BinaryTreeNode<E> firstAddedNode()
```
    Returns the first (lowest valued) added node in the sub-tree originating from this node, or null if there are no added entries in this tree or sub-tree
    
    Returns:
  - lastNode
```
public BinaryTreeNode<E> lastNode()
```
    Returns the last (highest valued) node in the sub-tree originating from this node.
    
    Returns:
  - lastAddedNode
```
public BinaryTreeNode<E> lastAddedNode()
```
    Returns the last (highest valued) added node in the sub-tree originating from this node, or null if there are no added entries in this tree or sub-tree
    
    Returns:
  - nextNode
```
public BinaryTreeNode<E> nextNode()
```
    Returns the node that follows this node following the tree order
    
    Returns:
  - previousNode
```
public BinaryTreeNode<E> previousNode()
```
    Returns the node that precedes this node following the tree order.
    
    Returns:
  - nextAddedNode
```
public BinaryTreeNode<E> nextAddedNode()
```
    Returns the next node in the tree that is an added node, following the tree order, or null if there is no such node.
    
    Returns:
  - previousAddedNode
```
public BinaryTreeNode<E> previousAddedNode()
```
    Returns the previous node in the tree that is an added node, following the tree order in reverse, or null if there is no such node.
    
    Returns:
  - iterator
```
public Iterator<E> iterator()
```
    Returns an iterator that iterates through the elements of the sub-tree with this node as the root. The iteration is in sorted element order.
    
    Specified by:
    
    iterator in interface TreeOps<E>
    
    Specified by:
    
    iterator in interface Iterable<E>
    
    Returns:
  - descendingIterator
```
public Iterator<E> descendingIterator()
```
    Returns an iterator that iterates through the elements of the subtrie with this node as the root. The iteration is in reverse sorted element order.
    
    Specified by:
    
    descendingIterator in interface TreeOps<E>
    
    Returns:
  - nodeIterator
```
public Iterator<? extends BinaryTreeNode<E>> nodeIterator(boolean forward)
```
    Iterates through the added nodes of the sub-tree with this node as the root, in forward or reverse tree order.
    
    Specified by:
    
    nodeIterator in interface TreeOps<E>
    
    Parameters:
    
    forward - if true, goes in ascending order, otherwise descending
    
    Returns:
  - allNodeIterator
```
public Iterator<? extends BinaryTreeNode<E>> allNodeIterator(boolean forward)
```
    Iterates through all the nodes of the sub-tree with this node as the root, in forward or reverse tree order.
    
    Specified by:
    
    allNodeIterator in interface TreeOps<E>
    
    Parameters:
    
    forward - if true, goes in ascending order, otherwise descending
    
    Returns:
  - containingFirstIterator
```
public <C> BinaryTreeNode.CachingIterator<? extends BinaryTreeNode<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 TreeOps<E>
    
    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 BinaryTreeNode<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 TreeOps<E>
    
    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 BinaryTreeNode<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 TreeOps<E>
    
    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 BinaryTreeNode<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 TreeOps<E>
    
    Parameters:
    
    forwardSubNodeOrder - if true, a left sub-node will be visited before the right sub-node of the same parent node.
    
    Returns:
  - toTreeString
```
public String toTreeString(boolean withNonAddedKeys,
                           boolean withSizes)
```
    Returns a visual representation of the sub-tree with this node as root, with one node per line.
    
    Parameters:
    
    withNonAddedKeys - whether to show nodes that are not added nodes
    
    withSizes - whether to include the counts of added nodes in each sub-tree
    
    Returns:
  - toString
```
public String toString()
```
    Returns a visual representation of this node including the key, with an open circle indicating this node is not an added node, a closed circle indicating this node is an added node.
    
    Overrides:
    
    toString in class Object
  - clone
```
public BinaryTreeNode<E> clone()
```
    Clones the node. Keys remain the same, but the parent node and the lower and upper sub-nodes are all set to null.
    
    Overrides:
    
    clone in class Object
  - cloneTree
```
public BinaryTreeNode<E> cloneTree()
```
    Clones the sub-tree starting with this node as root. The nodes are cloned, but their keys and values are not cloned.
  - hashCode
```
public int hashCode()
```
    The hash code is the hash code of the key value
    
    Overrides:
    
    hashCode in class Object
  - treeHashCode
```
public int treeHashCode()
```
    The hash code is the sum of the hash codes of all the added elements in the sub-tree with this node as the root
  - equals
```
public boolean equals(Object o)
```
    Returns whether the key values match those of the given node
    
    Overrides:
    
    equals in class Object
  - treeEquals
```
public boolean treeEquals(BinaryTreeNode<?> other)
```
    Returns whether the sub-tree represented by this node as the root node matches the given sub-tree

Class BinaryTreeNode<E>

Nested Class Summary

Method Summary

Methods inherited from class java.lang.Object

Methods inherited from interface inet.ipaddr.format.util.TreeOps

Methods inherited from interface java.lang.Iterable

Method Detail

getKey

isRoot

getParent

getUpperSubNode

getLowerSubNode

isAdded

setAdded

size

nodeSize

remove

clear

isEmpty

isLeaf

firstNode

firstAddedNode

lastNode

lastAddedNode

nextNode

previousNode

nextAddedNode

previousAddedNode

iterator

descendingIterator

nodeIterator

allNodeIterator

containingFirstIterator

containingFirstAllNodeIterator

containedFirstIterator

containedFirstAllNodeIterator

toTreeString

toString

clone

cloneTree

hashCode

treeHashCode

equals

treeEquals