jdsl.core.api
Interface BinaryTree

All Known Subinterfaces:
RestructurableBinaryTree
All Known Implementing Classes:
LinkedBinaryTree, BTNodeBinaryTree

public abstract interface BinaryTree
extends InspectableBinaryTree

Interface for a binary tree that can be modified. Note that binary trees are specified to start with a single external node with a null element, so no generic insert(.) method is needed here; every conceivable binary tree (except one with no nodes at all) can be built up from the methods of this interface. In addition, because the splice methods (link and replaceSubtree) invalidate containers. Any class implementing BinaryTree must throw an InvalidContainerException from all methods if the container has been invalidated.

Author:
Mark Handy, Mike Boilen (mgb)

Method Summary
 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.
 void expandExternal(Position mustBeExternal)
          The external position specified is transformed into an internal, and it gains two children.
 void link(Position mustBeExternal, BinaryTree newSubtree)
          Position mustBeExternal is removed from the tree.
 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.
 BinaryTree replaceSubtree(Position subtreeRoot, BinaryTree newSubtree)
          Swaps a subtree of the tree on which the method is called with a "subtree" passed in.
 
Methods inherited from interface jdsl.core.api.InspectableBinaryTree
leftChild, rightChild, sibling
 
Methods inherited from interface jdsl.core.api.InspectableTree
children, isExternal, isInternal, isRoot, parent, root, siblings
 
Methods inherited from interface jdsl.core.api.PositionalContainer
positions, replace, swap
 
Methods inherited from interface jdsl.core.api.Container
elements, newContainer
 
Methods inherited from interface jdsl.simple.api.SimpleContainer
isEmpty, size
 

Method Detail

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.
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 container has been invalidated.

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.
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 container has been invalidated.

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.
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:
InvalidPositionException - if subtreeRoot is of a type not accepted by this container or null.
InvalidContainerException - if this container has been invalidated.

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.
Parameters:
mustBeExternal - The external node to replace with the new subtree
newSubtree - The subtree to link in
Throws:
InvalidPositionException - if subtreeRoot is of a type not accepted by this container or null.
InvalidContainerException - if this container has been invalidated.
InvalidArgumentException - if newSubtree is the same tree that link is called on.

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 a new BinaryTree is created to hold this removed subtree. Note that link(.) and cut(.) can both be implemented in terms of this method.
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 BinaryTree, with subtreeRoot as its root
Throws:
InvalidPositionException - if subtreeRoot is of a type not accepted by this container or null.
InvalidContainerException - if this container has been invalidated.
InvalidArgumentException - if newSubtree is the same