All Packages  Class Hierarchy  This Package  Previous  Next  Index

Class jdsl.core.ref.BTNodeBinaryTree

java.lang.Object
   |
   +----jdsl.core.ref.BTNodeBinaryTree

public class BTNodeBinaryTree

extends Object

implements BinaryTree

Version:

$Revision: 1.4 $, $Date: 1998/07/01 18:05:33 $

Author:

Mike Boilen (mgb)

See Also:

InvalidContainerException, link, replaceSubtree

BTNodeBinaryTree()

Class Constructor.

BTNodeBinaryTree(BTNode)

Constructs a new BTNodeBinaryTree with newRootas the root of the tree.

children(Position)

The returned Enumeration is guaranteed to give the children in left-to-right order.

cut(Position)

Position subtreeRoot and all its children are removed from this tree and replaced with a new external node with a null element.

elements()

Return the elements stored in this container.

expandExternal(Position)

The external position specified is transformed into an internal, and it gains two children.

head()

Returns the head node of this tree.

isEmpty()

Tests if this container is empty.

isExternal(Position)

Checks if a given Position is an external node in this tree.

isInternal(Position)

Checks if a given Position if an internal node in this tree.

isRoot(Position)

leftChild(Position)

Returns the left child of a Position

link(Position, BinaryTree)

Position mustBeExternal is removed from the tree.

newContainer()

Returns a new, empty instance of this container.

parent(Position)

Returns the parent of a Position in the tree.

positions()

Returns the Positions of this BinaryTree in preorder order.

removeAboveExternal(Position)

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.

replace(Position, Object)

Replaces the element of a Position.

replaceSubtree(Position, BinaryTree)

Swaps a subtree of the tree on which the method is called with a "subtree" passed in.

rightChild(Position)

Returns the right child of a Position

root()

Returns the root, or top node, of the tree.

sibling(Position)

Returns the sibling of a Position

siblings(Position)

The returned Enumeration is guaranteed to give the siblings in left-to-right order.

size()

Returns the size of this container.

swap(Position, Position)

Swaps the elements associated with the two Positions, leaving the Positions themselves "where" they were.

 public BTNodeBinaryTree()

Class Constructor. Contstructs a new BTNodeBinaryTree with a single leaf as the root.

 protected BTNodeBinaryTree(BTNode newRoot)

Constructs a new BTNodeBinaryTree with newRootas the root of the tree.

Parameters:

newRoot - the root of the new BTNodeBinaryTree

See Also:

setRoot

 public BTHeadNode head()

Returns the head node of this tree.

Returns:

the head node.

 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.

Throws: InvalidContainerException

if this BTNodeBinaryTree has been invalidated.

See Also:

checkTree

 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

Throws: InvalidPositionException

In addition to the usual invalid-position possibilities, this is thrown when the position specified is not external

Throws: InvalidContainerException

if this BTNodeBinaryTree has been invalidated.

See Also:

checkTree

 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: InvalidContainerException

if this BTNodeBinaryTree has been invalidated.

See Also:

checkTree

 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. It will be invalidated by link.

Throws: InvalidPositionException

Thrown, in addition to the usual circumstances, when Position mustBeExternal is internal

Throws: InvalidContainerException

if this BTNodeBinaryTree has been invalidated.

See Also:

checkTree

 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.

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

 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

Throws: InvalidContainerException

if this BTNodeBinaryTree has been invalidated.

See Also:

checkTree

 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

Throws: InvalidContainerException

if this BTNodeBinaryTree has been invalidated.

See Also:

checkTree

 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

Throws: InvalidContainerException

if this BTNodeBinaryTree has been invalidated.

See Also:

checkTree

 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

 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

 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

 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

 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

Throws: InvalidContainerException

if this BTNodeBinaryTree has been invalidated.

See Also:

checkTree

 public 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

 public 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

 public 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

 public Object replace(Position p,
                       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

 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

 public 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

 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

 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

 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

All Packages  Class Hierarchy  This Package  Previous  Next  Index