jdsl.core.ref
Class BTNodeBinaryTree

java.lang.Object
  |
  +--jdsl.core.ref.BTNodeBinaryTree
Direct Known Subclasses:
RestructurableNodeBinaryTree

public class BTNodeBinaryTree
extends java.lang.Object
implements BinaryTree

A linked implementation of a BinaryTree. This container may become invalid if it is used as the parameter to a link or replaceSubtree call. An invalidated BTNodeBinaryTree will throw a InvalidContainerException in response to any method call.

Author:
Mike Boilen (mgb)
See Also:
InvalidContainerException, link, replaceSubtree

Constructor Summary
BTNodeBinaryTree()
          Class Constructor.
 
Method Summary
 java.util.Enumeration children(Position p)
          The returned Enumeration is guaranteed to give the children in left-to-right order.
 BinaryTree cut(Position subtreeRoot)
          Position subtreeRoot and all its children are removed from this tree and replaced with a new external node with a null element.
 java.util.Enumeration elements()
          Return the elements stored in this container.
 void expandExternal(Position mustBeExternal)
          The external position specified is transformed into an internal, and it gains two children.
 jdsl.core.ref.BTHeadNode head()
          Returns the head node of this tree.
 boolean isEmpty()
          Tests if this container is empty.
 boolean isExternal(Position p)
          Checks if a given Position is an external node in this tree.
 boolean isInternal(Position p)
          Checks if a given Position if an internal node in this tree.
 boolean isRoot(Position p)
           
 Position leftChild(Position p)
          Returns the left child of a Position
 void link(Position mustBeExternal, BinaryTree newSubtree)
          Position mustBeExternal is removed from the tree.
 Container newContainer()
          Returns a new, empty instance of this container.
 Position parent(Position p)
          Returns the parent of a Position in the tree.
 java.util.Enumeration positions()
          Returns the Positions of this BinaryTree in preorder order.
 void removeAboveExternal(Position mustBeExternal)
          The parent of Position mustBeExternal is deleted, and the sibling subtree of mustBeExternal takes the parent's place as the left/right child of the parent's parent.
 java.lang.Object replace(Position p, java.lang.Object newElement)
          Replaces the element of a Position.
 BinaryTree replaceSubtree(Position subtreeRoot, BinaryTree newSubtree)
          Swaps a subtree of the tree on which the method is called with a "subtree" passed in.
 Position rightChild(Position p)
          Returns the right child of a Position
 Position root()
          Returns the root, or top node, of the tree.
 Position sibling(Position p)
          Returns the sibling of a Position
 java.util.Enumeration siblings(Position p)
          The returned Enumeration is guaranteed to give the siblings in left-to-right order.
 int size()
          Returns the size of this container.
 void swap(Position a, Position b)
          Swaps the elements associated with the two Positions, leaving the Positions themselves "where" they were.
 
Methods inherited from class java.lang.Object
equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

BTNodeBinaryTree

public BTNodeBinaryTree()
Class Constructor. Contstructs a new BTNodeBinaryTree with a single leaf as the root.
Method Detail

head

public jdsl.core.ref.BTHeadNode head()
Returns the head node of this tree.
Returns:
the head node.

expandExternal

public void expandExternal(Position mustBeExternal)
                    throws InvalidPositionException,
                           InvalidContainerException
The external position specified is transformed into an internal, and it gains two children. The position reference itself doesn't change, and its element also doesn't change. The elements of its two new, external children are both null objects.
Specified by:
expandExternal in interface BinaryTree
Parameters:
mustBeExternal - A position which must be an external position in the BinaryTree
Throws:
InvalidPositionException - Thrown, in addition to the usual circumstances, when mustBeExternal is internal.
InvalidContainerException - if this BTNodeBinaryTree has been invalidated.
See Also:
checkTree

removeAboveExternal

public void removeAboveExternal(Position mustBeExternal)
                         throws InvalidPositionException,
                                BoundaryViolationException,
                                InvalidContainerException
The parent of Position mustBeExternal is deleted, and the sibling subtree of mustBeExternal takes the parent's place as the left/right child of the parent's parent. The external position specified is also deleted.
Specified by:
removeAboveExternal in interface BinaryTree
Parameters:
mustBeExternal - A position which must be an external position in the BinaryTree
Throws:
BoundaryViolationException - When the position specified is an external position, as required, but also the root
InvalidPositionException - In addition to the usual invalid-position possibilities, this is thrown when the position specified is not external
InvalidContainerException - if this BTNodeBinaryTree has been invalidated.
See Also:
checkTree

cut

public BinaryTree cut(Position subtreeRoot)
               throws InvalidPositionException,
                      InvalidContainerException
Position subtreeRoot and all its children are removed from this tree and replaced with a new external node with a null element. They are packaged in a new binary tree and returned; all positions and elements are still valid, although some of them have a different container after the operation.
Specified by:
cut in interface BinaryTree
Parameters:
subtreeRoot - The position above which to make the cut
Returns:
The subtree removed, packaged as a new BT, with subtreeRoot as its root
Throws:
InvalidContainerException - if this BTNodeBinaryTree has been invalidated.
See Also:
checkTree

link

public void link(Position mustBeExternal,
                 BinaryTree newSubtree)
          throws InvalidPositionException,
                 InvalidContainerException,
                 InvalidArgumentException
Position mustBeExternal is removed from the tree. The root of newSubtree, with all its children, is installed in its place, with all their positions and elements unchanged.
Specified by:
link in interface BinaryTree
Parameters:
mustBeExternal - The external node to replace with the new subtree
newSubtree - The subtree to link in. It will be invalidated by link.
Throws:
InvalidPositionException - Thrown, in addition to the usual circumstances, when Position mustBeExternal is internal
InvalidContainerException - if this BTNodeBinaryTree has been invalidated.
See Also:
checkTree

replaceSubtree

public BinaryTree replaceSubtree(Position subtreeRoot,
                                 BinaryTree newSubtree)
                          throws InvalidPositionException,
                                 InvalidContainerException,
                                 InvalidArgumentException
Swaps a subtree of the tree on which the method is called with a "subtree" passed in. In the extreme, the subtree of the tree on which the method is called might be the entire tree, or might be just a leaf. Position subtreeRoot specifies a subtree of the tree on which this method is called. That subtree is removed from the tree, and newSubtree is linked in in its place. A new tree, whose root is the position subtreeRoot, is returned to the user (this tree corresponds exactly to the removed subtree). Note that link(.) and cut(.) can both be implemented in terms of this method.
Specified by:
replaceSubtree in interface BinaryTree
Parameters:
subtreeRoot - Any position in the BinaryTree on which the method is called
newSubtree - The tree that will replace the tree rooted at subtreeRoot
Returns:
A new BT, with subtreeRoot as its root
Throws:
InvalidContainerException - if this BTNodeBinaryTree has been invalidated.
See Also:
checkTree

leftChild

public Position leftChild(Position p)
                   throws InvalidPositionException,
                          BoundaryViolationException,
                          InvalidContainerException
Returns the left child of a Position
Parameters:
p - Any node of the tree
Returns:
left child of the given node
Throws:
BoundaryViolationException - If Position p is external
InvalidContainerException - if this BTNodeBinaryTree has been invalidated.
See Also:
checkTree

rightChild

public Position rightChild(Position p)
                    throws InvalidPositionException,
                           BoundaryViolationException,
                           InvalidContainerException
Returns the right child of a Position
Parameters:
p - Any node of the tree
Returns:
right child of the given node
Throws:
BoundaryViolationException - If Position p is external
InvalidContainerException - if this BTNodeBinaryTree has been invalidated.
See Also:
checkTree

sibling

public Position sibling(Position p)
                 throws InvalidPositionException,
                        BoundaryViolationException,
                        InvalidContainerException
Returns the sibling of a Position
Parameters:
otherChild - Any node of the tree
Returns:
sibling of the given node (the other child of this node's parent)
Throws:
BoundaryViolationException - If Position p is the root
InvalidContainerException - if this BTNodeBinaryTree has been invalidated.
See Also:
checkTree

isRoot

public boolean isRoot(Position p)
               throws InvalidPositionException,
                      InvalidContainerException
Parameters:
p - Any node of the tree
Returns:
Whether the given node is the root of the tree
Throws:
InvalidContainerException - if this BTNodeBinaryTree has been invalidated.
See Also:
checkTree

isInternal

public boolean isInternal(Position p)
                   throws InvalidPositionException,
                          InvalidContainerException
Checks if a given Position if an internal node in this tree.
Parameters:
p - Any node of the tree
Returns:
Whether the given node has at least one child
Throws:
InvalidContainerException - if this BTNodeBinaryTree has been invalidated.
See Also:
checkTree

isExternal

public boolean isExternal(Position p)
                   throws InvalidPositionException,
                          InvalidContainerException
Checks if a given Position is an external node in this tree.
Parameters:
p - Any node of the tree
Returns:
Whether the given node has zero children
Throws:
InvalidContainerException - if this BTNodeBinaryTree has been invalidated.
See Also:
checkTree

root

public Position root()
              throws InvalidContainerException
Returns the root, or top node, of the tree. Note that trees always have at least one external node, so they always have a root.
Returns:
The top node of the tree
Throws:
InvalidContainerException - if this BTNodeBinaryTree has been invalidated.
See Also:
checkTree

parent

public Position parent(Position p)
                throws InvalidPositionException,
                       BoundaryViolationException,
                       InvalidContainerException
Returns the parent of a Position in the tree.
Parameters:
p - Any node of the tree
Returns:
Parent Position of the given node
Throws:
BoundaryViolationException - If p is the root of the tree
InvalidContainerException - if this BTNodeBinaryTree has been invalidated.
See Also:
checkTree

children

public java.util.Enumeration children(Position p)
                               throws InvalidPositionException,
                                      InvalidContainerException
The returned Enumeration is guaranteed to give the children in left-to-right order.
Parameters:
p - Any node of the tree
Returns:
Enumeration of all the children of that node
Throws:
InvalidContainerException - if this BTNodeBinaryTree has been invalidated.
See Also:
checkTree

siblings

public java.util.Enumeration siblings(Position p)
                               throws InvalidPositionException,
                                      InvalidContainerException
The returned Enumeration is guaranteed to give the siblings in left-to-right order.
Parameters:
p - Any node of the tree
Returns:
Enumeration of all the other children of the same parent
Throws:
InvalidContainerException - if this BTNodeBinaryTree has been invalidated.
See Also:
checkTree

positions

public java.util.Enumeration positions()
Returns the Positions of this BinaryTree in preorder order.
Returns:
Enumeration of all Positions in the container
Throws:
InvalidContainerException - if this BTNodeBinaryTree has been invalidated.
See Also:
checkTree

replace

public java.lang.Object replace(Position p,
                                java.lang.Object newElement)
                         throws InvalidPositionException
Replaces the element of a Position. Guaranteed to be a constant-time operation.
Parameters:
p - Position at which replacement is to occur
newElement - Element now to be stored at Position p
Returns:
Old element, formerly stored at Position p
Throws:
InvalidContainerException - if this BTNodeBinaryTree has been invalidated.
See Also:
checkTree

swap

public void swap(Position a,
                 Position b)
          throws InvalidPositionException
Swaps the elements associated with the two Positions, leaving the Positions themselves "where" they were. One of the Positions can be from another container, and the swap will be across containers.
Parameters:
a - A Position.
b - A Position.
Throws:
InvalidContainerException - if this BTNodeBinaryTree has been invalidated.
See Also:
checkTree

elements

public java.util.Enumeration elements()
Return the elements stored in this container. Duplicated elements are represented in the enumeration as many times as they are held in the container. For some containers, the order of elements in the enumeration is arbitrary, but for some it is defined.
Returns:
A java.util.Enumeration of all elements in the container
Throws:
InvalidContainerException - if this BTNodeBinaryTree has been invalidated.
See Also:
checkTree, Enumeration

newContainer

public Container newContainer()
Returns a new, empty instance of this container.
Returns:
A new instance of the class of the container on which the method is called.
Throws:
InvalidContainerException - if this BTNodeBinaryTree has been invalidated.
See Also:
checkTree

size

public int size()
Returns the size of this container. The size is equal to the number of nodes in this tree. Runs on order N time. operations.

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

Throws:
InvalidContainerException - if this BTNodeBinaryTree has been invalidated.
See Also:
checkTree

isEmpty

public boolean isEmpty()
                throws InvalidContainerException
Tests if this container is empty. Unlike size, runs in constant time. Since a container always has at least one external node, it can never be empty, so this method always returns true.
Returns:
Always returns false since a BinaryTree can never be empty.
Throws:
InvalidContainerException - if this BTNodeBinaryTree has been invalidated.
See Also:
checkTree, size