jdsl.core.ref
Class NodeBinaryTree

java.lang.Object
  |
  +--jdsl.core.ref.AbstractPositionalContainer
        |
        +--jdsl.core.ref.NodeBinaryTree

All Implemented Interfaces:

BinaryTree, Container, InspectableBinaryTree, InspectableContainer, InspectablePositionalContainer, InspectableTree, PositionalContainer

public class NodeBinaryTree

extends AbstractPositionalContainer

implements BinaryTree

A node-based Binary Tree. The Positions of the tree are the nodes.

contains() is O(1) time; so replaceSubtree, cut, and link are O(S), where S is the number of positions in that subtree. Positions() and elements() are O(N) -- where N is the number of positions in the entire tree. All other methods are O(1) time.

Elements can be stored at both internal and external (leaf) nodes.

The data structure stores a supernode which in turn stores the root. (this supernode is invisible to the end user) You are only allowed to link in and replaceSubtree with other instances of NodeBinaryTree (or subclasses thereof).

Version:

$Id: NodeBinaryTree.java,v 1.37 2001/03/21 17:16:21 lv Exp $

Author:

Ryan Baker (rsb), Mark Handy (mdh), Benoit Hudson (bh)

See Also:

AbstractPositionalContainer, BinaryTree

Inner Class Summary

protected static class	NodeBinaryTree.NBTNode This is the class for all user-visible nodes It contains links for its parent, children, and element.
protected static class	NodeBinaryTree.NBTSuperNode This is the supernode.

Field Summary

protected int

_size The size of the tree protected so that RestructurableNodeBinaryTree can access it

Constructor Summary

	NodeBinaryTree() Create a tree.
protected	NodeBinaryTree(NodeBinaryTree.NBTNode root) Create a tree from a set of nodes.

Method Summary

protected NodeBinaryTree.NBTNode	checkPosition(Accessor a) Casts the accessor passed in to the appropriate node class for this container; also checks if it is null.
Position	childAtRank(Position node, int rank) O(1) time
PositionIterator	children(Position p) O(1) time
boolean	contains(Accessor a) O(1) time
BinaryTree	cut(Position rootOfSubtree) Takes O(S) time, where S is the number of positions in the subtree to cut
ObjectIterator	elements() Takes O(N) time from the need to iterate through the tree during snapshot, where N is the number of elements in the tree
void	expandExternal(Position mustBeExternal) O(1) time
Position	firstChild(Position node) O(1) time
void	graftOnLeft(Position subtree, java.lang.Object eltOfParent, BinaryTree newSibling) Takes O(S) time, where S is the number of positions in the new subtree to graft on You are only allowed to link in and replaceSubtree with other instances of NodeBinaryTree (or subclasses thereof)
void	graftOnRight(Position subtree, java.lang.Object eltOfParent, BinaryTree newSibling) Takes O(S) time, where S is the number of positions in the new subtree to graft on You are only allowed to link in and replaceSubtree with other instances of NodeBinaryTree (or subclasses thereof)
boolean	isEmpty() Overridden from AbstractPositionalContainer to be O(1) time.
boolean	isExternal(Position p) O(1) time
boolean	isInternal(Position p) O(1) time
boolean	isRoot(Position p) O(1) time
Position	lastChild(Position node) O(1) time
Position	leftChild(Position p) O(1) time
java.lang.Object	link(Position mustBeExternal, BinaryTree newSubtree) Takes O(S) time, where S is the number of positions in this subtree You are only allowed to link in and replaceSubtree with other instances of NodeBinaryTree (or subclasses thereof)
Container	newContainer() O(1) time
int	numChildren(Position node) O(1) time Can be determined by the inherent nature of the type of node rather than by counting
Position	parent(Position p) O(1) time
PositionIterator	positions() Takes O(N) time from the need to iterate through the tree during snapshot, where N is the number of positions in the tree
int	rankOfChild(Position child) O(1) time
void	removeAboveExternal(Position mustBeExternal) O(1) time
java.lang.Object	replaceElement(Accessor p, java.lang.Object newElement) O(1) time
BinaryTree	replaceSubtree(Position subtreeRoot, BinaryTree newSubtree) Takes O(S1+S2) time, where S1 and S2 are the number of positions in each subtree You are only allowed to link in and replaceSubtree with other instances of NodeBinaryTree (or subclasses thereof)
protected void	resetToEmpty() Used for resetting the tree to an empty tree after a link or replaceSubtree operation.
Position	rightChild(Position p) O(1) time
Position	root() O(1) time
Position	sibling(Position p) O(1) time
Position	siblingAfter(Position node) O(1) time
Position	siblingBefore(Position node) O(1) time
PositionIterator	siblings(Position p) O(1) time
int	size() O(1) time
java.lang.String	toString()
protected void	updateContainer(Accessor root) Recursively changes the container of all nodes in the subtree anchored at root to this container, adding to _size for each node whose container we change Takes O(S) time -- where S is the number of elements in the subtree

Methods inherited from class jdsl.core.ref.AbstractPositionalContainer

swapElements

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Methods inherited from interface jdsl.core.api.PositionalContainer

swapElements

Field Detail

_size

protected int _size

The size of the tree protected so that RestructurableNodeBinaryTree can access it

Constructor Detail

NodeBinaryTree

public NodeBinaryTree()

Create a tree. The tree has a single external node at its root, with element null.

NodeBinaryTree

protected NodeBinaryTree(NodeBinaryTree.NBTNode root)
                  throws InvalidAccessorException

Create a tree from a set of nodes. The tree will have as its root the given node. This constructor is protected in order to prevent it from being used except as a result of operations on one tree that create another tree It is assumed that the method calling this will take responsibility for changing the container_ of the various internal NBTNodes, as well as setting _size -- this way, we can allow O(1) time access where appropriate

Parameters:

root - Root of a tree of existing nodes.

Throws:

InvalidAccessorException - when the given root has a parent.

Method Detail

graftOnLeft

public void graftOnLeft(Position subtree,
                        java.lang.Object eltOfParent,
                        BinaryTree newSibling)

Takes O(S) time, where S is the number of positions in the new subtree to graft on You are only allowed to link in and replaceSubtree with other instances of NodeBinaryTree (or subclasses thereof)

Specified by:

graftOnLeft in interface BinaryTree

Following copied from interface: jdsl.core.api.BinaryTree

Parameters:

newSubtree - the binary tree whose root will be linked in as the left child of the new node

eltOfParent - the object to be stored in the new node

subtreeRoot - any position in this binary tree

Throws:

InvalidAccessorException - if subtreeRoot is null or does not belong to this binary tree.

InvalidContainerException - if newSubtree is null, incompatible with, or equal to this binary tree.

graftOnRight

public void graftOnRight(Position subtree,
                         java.lang.Object eltOfParent,
                         BinaryTree newSibling)

Takes O(S) time, where S is the number of positions in the new subtree to graft on You are only allowed to link in and replaceSubtree with other instances of NodeBinaryTree (or subclasses thereof)

Specified by:

graftOnRight in interface BinaryTree

Following copied from interface: jdsl.core.api.BinaryTree

Parameters:

subtreeRoot - any position in this binary tree

eltOfParent - the object to be stored in the new node

newSubtree - the binary tree whose root will be linked in as the right child of the new node

Throws:

InvalidAccessorException - if subtreeRoot is null or does not belong to this binary tree.

InvalidContainerException - if newSubtree is null, incompatible with, or equal to this binary tree.

expandExternal

public void expandExternal(Position mustBeExternal)
                    throws InvalidAccessorException

O(1) time

Specified by:

expandExternal in interface BinaryTree

Following copied from interface: jdsl.core.api.BinaryTree

Parameters:

node - any external position in this binary tree

Throws:

InvalidAccessorException - if node is not external, is null, or does not belong to this binary tree.

removeAboveExternal

public void removeAboveExternal(Position mustBeExternal)
                         throws InvalidAccessorException,
                                BoundaryViolationException

O(1) time

Specified by:

removeAboveExternal in interface BinaryTree

Following copied from interface: jdsl.core.api.BinaryTree

Parameters:

node - any external position in this binary tree

Throws:

BoundaryViolationException - if node is an external position, as required, but also the root of this binary tree.

InvalidAccessorException - if node is not external, is null, or does not belong to this binary tree.

cut

public BinaryTree cut(Position rootOfSubtree)
               throws InvalidAccessorException

Takes O(S) time, where S is the number of positions in the subtree to cut

Specified by:

cut in interface BinaryTree

Following copied from interface: jdsl.core.api.BinaryTree

Parameters:

node - the position above which to make the cut

Returns:

the subtree removed, packaged as a new BinaryTree, with node as its root

Throws:

InvalidAccessorException - if node is null or does not belong to this binary tree.

link

public java.lang.Object link(Position mustBeExternal,
                             BinaryTree newSubtree)
                      throws InvalidAccessorException,
                             InvalidContainerException

Takes O(S) time, where S is the number of positions in this subtree You are only allowed to link in and replaceSubtree with other instances of NodeBinaryTree (or subclasses thereof)

Specified by:

link in interface BinaryTree

Following copied from interface: jdsl.core.api.BinaryTree

Parameters:

node - the external node to replace with the new subtree

newSubtree - the subtree to link in

Returns:

the element of the external position that was removed

Throws:

InvalidAccessorException - if node is not external, is null, or does not belong to this binary tree.

InvalidContainerException - if newSubtree is null, incompatible with, or equal to this binary tree.

replaceSubtree

public BinaryTree replaceSubtree(Position subtreeRoot,
                                 BinaryTree newSubtree)
                          throws InvalidAccessorException,
                                 InvalidContainerException

Takes O(S1+S2) time, where S1 and S2 are the number of positions in each subtree You are only allowed to link in and replaceSubtree with other instances of NodeBinaryTree (or subclasses thereof)

Specified by:

replaceSubtree in interface BinaryTree

Following copied from interface: jdsl.core.api.BinaryTree

Parameters:

subtreeRoot - any position in this binary tree

newSubtree - the binary tree that will replace the binary tree rooted at subtreeRoot

Returns:

a new binary tree, with subtreeRoot as its root

Throws:

InvalidAccessorException - if subtreeRoot is null or does not belong to this binary tree.

InvalidContainerException - if newSubtree is null, incompatible with, or equal to this binary tree.

updateContainer

protected void updateContainer(Accessor root)
                        throws InvalidAccessorException

Recursively changes the container of all nodes in the subtree anchored at root to this container, adding to _size for each node whose container we change Takes O(S) time -- where S is the number of elements in the subtree

Parameters:

root - The node to begin with

leftChild

public Position leftChild(Position p)
                   throws InvalidAccessorException,
                          BoundaryViolationException

O(1) time

Specified by:

leftChild in interface InspectableBinaryTree

Following copied from interface: jdsl.core.api.InspectableBinaryTree

Parameters:

node - Any internal node of the tree

Returns:

left child of node

Throws:

BoundaryViolationException - if node is external

InvalidAccessorException - if node is null or does not belong to this binary tree.

rightChild

public Position rightChild(Position p)
                    throws InvalidAccessorException,
                           BoundaryViolationException

O(1) time

Specified by:

rightChild in interface InspectableBinaryTree

Following copied from interface: jdsl.core.api.InspectableBinaryTree

Parameters:

node - Any internal node of the tree

Returns:

right child of node

Throws:

BoundaryViolationException - if node is external

InvalidAccessorException - if node is null or does not belong to this binary tree.

sibling

public Position sibling(Position p)
                 throws InvalidAccessorException,
                        BoundaryViolationException

O(1) time

Specified by:

sibling in interface InspectableBinaryTree

Following copied from interface: jdsl.core.api.InspectableBinaryTree

Parameters:

node - a node of the binary tree.

Returns:

sibling of node.

Throws:

BoundaryViolationException - if node is the root

InvalidAccessorException - if node is null or does not belong to this binary tree.

isRoot

public boolean isRoot(Position p)
               throws InvalidAccessorException

O(1) time

Specified by:

isRoot in interface InspectableTree

Following copied from interface: jdsl.core.api.InspectableTree

Parameters:

node - a node

Returns:

true if node is the root of this tree

Throws:

InvalidAccessorException - if node is null or does not belong to this tree

isInternal

public boolean isInternal(Position p)
                   throws InvalidAccessorException

O(1) time

Specified by:

isInternal in interface InspectableTree

Following copied from interface: jdsl.core.api.InspectableTree

Parameters:

node - a node

Returns:

true if node has at least one child

Throws:

InvalidAccessorException - if node is null or does not belong to this tree

isExternal

public boolean isExternal(Position p)
                   throws InvalidAccessorException

O(1) time

Specified by:

isExternal in interface InspectableTree

Following copied from interface: jdsl.core.api.InspectableTree

Parameters:

node - Any node of the tree

Returns:

true if node has no children

Throws:

InvalidAccessorException - if node is null or does not belong to this tree

root

public Position root()

O(1) time

Specified by:

root in interface InspectableTree

Following copied from interface: jdsl.core.api.InspectableTree

Returns:

The top node of the tree (may also be a leaf if the tree has exactly one node)

parent

public Position parent(Position p)
                throws InvalidAccessorException,
                       BoundaryViolationException

O(1) time

Specified by:

parent in interface InspectableTree

Following copied from interface: jdsl.core.api.InspectableTree

Parameters:

node - a node

Returns:

parent position of the given node

Throws:

BoundaryViolationException - if node is the root of the tree

InvalidAccessorException - if node is null or does not belong to this tree

children

public PositionIterator children(Position p)
                          throws InvalidAccessorException

O(1) time

Specified by:

children in interface InspectableTree

Following copied from interface: jdsl.core.api.InspectableTree

Parameters:

node - a node of the tree

Returns:

iterator over all the children of node

Throws:

InvalidAccessorException - if node is null or does not belong to this tree

siblings

public PositionIterator siblings(Position p)
                          throws InvalidAccessorException

O(1) time

Specified by:

siblings in interface InspectableTree

Following copied from interface: jdsl.core.api.InspectableTree

Parameters:

node - a node of the tree

Returns:

iterator over all the other children of the same parent

Throws:

BoundaryViolationException - if node is the root of the tree

InvalidAccessorException - if node is null or does not belong to this tree

numChildren

public int numChildren(Position node)
                throws InvalidAccessorException

O(1) time Can be determined by the inherent nature of the type of node rather than by counting

Specified by:

numChildren in interface InspectableTree

Following copied from interface: jdsl.core.api.InspectableTree

Parameters:

node - a node of the tree

Returns:

the number of children of node

Throws:

InvalidAccessorException - if node is null or does not belong to this tree

siblingAfter

public Position siblingAfter(Position node)
                      throws BoundaryViolationException,
                             InvalidAccessorException

O(1) time

Specified by:

siblingAfter in interface InspectableTree

Following copied from interface: jdsl.core.api.InspectableTree

Parameters:

node - a node

Returns:

the sibling after node

Throws:

BoundaryViolationException - if node is either the last child of a node or the root

InvalidAccessorException - if node is null or does not belong to this tree

siblingBefore

public Position siblingBefore(Position node)
                       throws BoundaryViolationException,
                              InvalidAccessorException

O(1) time

Specified by:

siblingBefore in interface InspectableTree

Following copied from interface: jdsl.core.api.InspectableTree

Parameters:

node - a node

Returns:

the sibling before node

Throws:

BoundaryViolationException - if node is either the first child of a node or the root

InvalidAccessorException - if node is null or does not belong to this tree

firstChild

public Position firstChild(Position node)
                    throws BoundaryViolationException,
                           InvalidAccessorException

O(1) time

Specified by:

firstChild in interface InspectableTree

Following copied from interface: jdsl.core.api.InspectableTree

Parameters:

node - a node

Returns:

the first child of node

Throws:

BoundaryViolationException - if node is a leaf

InvalidAccessorException - if node is null or does not belong to this tree

lastChild

public Position lastChild(Position node)
                   throws BoundaryViolationException,
                          InvalidAccessorException

O(1) time

Specified by:

lastChild in interface InspectableTree

Following copied from interface: jdsl.core.api.InspectableTree

Parameters:

node - a node

Returns:

the last child of node

Throws:

BoundaryViolationException - if node is a leaf

InvalidAccessorException - if node is null or does not belong to this tree

rankOfChild

public int rankOfChild(Position child)
                throws BoundaryViolationException,
                       InvalidAccessorException

O(1) time

Specified by:

rankOfChild in interface InspectableTree

Following copied from interface: jdsl.core.api.InspectableTree

Parameters:

child - a node

Returns:

rank of child

Throws:

BoundaryViolationException - if child is the root

InvalidAccessorException - if child is null or does not belong to this tree

childAtRank

public Position childAtRank(Position node,
                            int rank)
                     throws BoundaryViolationException,
                            InvalidAccessorException

O(1) time

Specified by:

childAtRank in interface InspectableTree

Following copied from interface: jdsl.core.api.InspectableTree

Parameters:

node - a node

rank - an integer index of the children of node; childAtRank(0) is the first child, childAtRank(numChildren(node)-1) is the last child

Returns:

the child of node at the specified rank

Throws:

BoundaryViolationException - if rank < 0 or rank > numChildren(node)-1 or node is a leaf

InvalidAccessorException - if node is null or does not belong to this tree

positions

public PositionIterator positions()

Takes O(N) time from the need to iterate through the tree during snapshot, where N is the number of positions in the tree

Specified by:

positions in interface InspectablePositionalContainer

Returns:

PositionIterator of the container in preorder

elements

public ObjectIterator elements()

Takes O(N) time from the need to iterate through the tree during snapshot, where N is the number of elements in the tree

Specified by:

elements in interface InspectableContainer

Returns:

an iterator over the container's elements in preorder

replaceElement

public java.lang.Object replaceElement(Accessor p,
                                       java.lang.Object newElement)
                                throws InvalidAccessorException

O(1) time

Specified by:

replaceElement in interface Container

Following copied from interface: jdsl.core.api.Container

Parameters:

a - Accessor in this container

newElement - to be stored at a

Returns:

old element, previously stored at a

Throws:

InvalidAccessorException - if a is null or does not belong to this container

newContainer

public Container newContainer()

O(1) time

Specified by:

newContainer in interface Container

Following copied from interface: jdsl.core.api.Container

Returns:

A new, empty Container of the same class as this one.

size

public int size()

O(1) time

Specified by:

size in interface InspectableContainer

Returns:

Number of elements in the container, where each occurrence of a duplicated element adds 1 to the size() of the container.

isEmpty

public boolean isEmpty()

Overridden from AbstractPositionalContainer to be O(1) time. Will always be false under the current definition of the BinaryTree, since a BT is initialized with one external element.

Specified by:

isEmpty in interface InspectableContainer

Overrides:

isEmpty in class AbstractPositionalContainer

Following copied from interface: jdsl.core.api.InspectableContainer

Returns:

true if and only if the container is empty (holds no elements)

See Also:

InspectableBinaryTree

contains

public boolean contains(Accessor a)

O(1) time

Specified by:

contains in interface InspectableContainer

Following copied from interface: jdsl.core.api.InspectableContainer

Throws:

InvalidAccessorException - if a is null

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object

resetToEmpty

protected void resetToEmpty()

Used for resetting the tree to an empty tree after a link or replaceSubtree operation. This method is protected, so other trees can instruct this tree to do so after a link or replaceSubtree operation O(1) time

checkPosition

protected NodeBinaryTree.NBTNode checkPosition(Accessor a)
                                        throws InvalidAccessorException

Casts the accessor passed in to the appropriate node class for this container; also checks if it is null. Also checks if it belongs to this container. This method is protected to allow it to be overridden to check for container in a different fashion

Parameters:

a - The accessor to cast

Returns:

The casted node