jdsl.core.ref
Class NodeTree

java.lang.Object
  |
  +--jdsl.core.ref.AbstractPositionalContainer
        |
        +--jdsl.core.ref.NodeTree
All Implemented Interfaces:
Container, InspectableContainer, InspectablePositionalContainer, InspectableTree, PositionalContainer, Tree

public class NodeTree
extends AbstractPositionalContainer
implements Tree

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

cut(), link(), and replaceSubtree() are implemented with O(n) running times to support size() and contains() having O(1) running times. Rank related methods are O(the maximum number of children per node). The tree is implemented with a internal node data structure which keeps track of the structure of the tree (i.e. links to parents, siblings, and children).

Version:
$Id: NodeTree.java,v 1.17 2001/03/21 17:16:20 lv Exp $
Author:
Galina Shubina (gs)

Constructor Summary
NodeTree()
          The default constructor for NodeTree, which creates a tree with one node whose element is null.
 
Method Summary
 Position childAtRank(Position node, int rank)
          O(1) time
 PositionIterator children(Position node)
          O(1) time if cache exists, O(the number of children of the node) otherwise.
 boolean contains(Accessor a)
          O(1) time
 java.lang.Object contract(Position node)
          O(1) time
 Tree cut(Position p)
          O(size of the cut subtree) time
 ObjectIterator elements()
          O(1) time if cache already exists, O(size of the tree) otherwise
 Position expand(Position fromChild, Position toChild, java.lang.Object elem)
          O(number of children of a new node) time
 Position firstChild(Position node)
          O(1) time
 Position insertAfterSibling(Position node, java.lang.Object elem)
          O(1) time
 Position insertBeforeSibling(Position node, java.lang.Object elem)
          O(1) time
 Position insertChildAtRank(Position node, int rank, java.lang.Object elem)
          O(the number of children of the node) time
 Position insertFirstChild(Position node, java.lang.Object elem)
          O(1) time
 Position insertLastChild(Position node, java.lang.Object elem)
          O(1) time
 boolean isEmpty()
          O(1) time
 boolean isExternal(Position node)
          O(1) time
 boolean isInternal(Position node)
          O(1) time
 boolean isRoot(Position node)
          O(1) time
 Position lastChild(Position node)
          O(1) time
 java.lang.Object link(Position extNode, Tree t)
          O(size of the new subtree to be linked in) time
 Container newContainer()
          O(1) time
 int numChildren(Position node)
          O(1) time
 Position parent(Position node)
          O(1) time
 PositionIterator positions()
          O(1) time if cache already exists, O(size of the tree) otherwise
 int rankOfChild(Position child)
          O(the number of children of the node) time
 java.lang.Object removeExternal(Position node)
          O(1) time
 java.lang.Object replaceElement(Accessor a, java.lang.Object newElement)
          O(1) time
 Tree replaceSubtree(Position node, Tree t)
          O(size of the new subtree + size of the cut tree) time
 Position root()
          O(1) time
 Position siblingAfter(Position node)
          O(1) time
 Position siblingBefore(Position node)
          O(the number of children of the node) time
 PositionIterator siblings(Position node)
          O(the number of children of the node) time
 int size()
          O(1) time
 void swapElements(Position a, Position b)
          O(1) time
 java.lang.String toString()
           
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Constructor Detail

NodeTree

public NodeTree()
The default constructor for NodeTree, which creates a tree with one node whose element is null. This is the only public constructor.
Method Detail

contains

public boolean contains(Accessor a)
                 throws InvalidAccessorException
O(1) time
Specified by:
contains in interface InspectableContainer
Following copied from interface: jdsl.core.api.InspectableContainer
Throws:
InvalidAccessorException - if a is null

isEmpty

public boolean isEmpty()
O(1) time
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

size

public int size()
O(1) time
Specified by:
size in interface InspectableContainer
Following copied from interface: jdsl.core.api.InspectableContainer
Returns:
Number of elements stored by the container.

elements

public ObjectIterator elements()
O(1) time if cache already exists, O(size of the tree) otherwise
Specified by:
elements in interface InspectableContainer
Following copied from interface: jdsl.core.api.InspectableContainer
Returns:
an iterator over all the elements stored in 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.

replaceElement

public java.lang.Object replaceElement(Accessor a,
                                       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

positions

public PositionIterator positions()
O(1) time if cache already exists, O(size of the tree) otherwise
Specified by:
positions in interface InspectablePositionalContainer
Following copied from interface: jdsl.core.api.InspectablePositionalContainer
Returns:
A PositionIterator over all positions in the container

swapElements

public void swapElements(Position a,
                         Position b)
                  throws InvalidAccessorException
O(1) time
Specified by:
swapElements in interface PositionalContainer
Overrides:
swapElements in class AbstractPositionalContainer
Following copied from interface: jdsl.core.api.PositionalContainer
Parameters:
a - First Position to swap
b - Second Position to swap
Throws:
InvalidAccessorException - if either of a and b is null or does not belong to this positional container

isRoot

public boolean isRoot(Position node)
               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 node)
                   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 node)
                   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 node)
                throws BoundaryViolationException,
                       InvalidAccessorException
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 node)
                          throws InvalidAccessorException
O(1) time if cache exists, O(the number of children of the node) otherwise.
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 node)
                          throws BoundaryViolationException,
                                 InvalidAccessorException
O(the number of children of the node) 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
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

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

siblingBefore

public Position siblingBefore(Position node)
                       throws BoundaryViolationException,
                              InvalidAccessorException
O(the number of children of the node) 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(the number of children of the node) 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

cut

public Tree cut(Position p)
         throws InvalidAccessorException
O(size of the cut subtree) time
Specified by:
cut in interface Tree
Following copied from interface: jdsl.core.api.Tree
Parameters:
node - The position above which to make the cut; will be the root of the returned tree
Returns:
the subtree cut off of the tree.
Throws:
InvalidAccessorException - if node is null or does not belong to this tree.

link

public java.lang.Object link(Position extNode,
                             Tree t)
                      throws InvalidAccessorException,
                             InvalidContainerException
O(size of the new subtree to be linked in) time
Specified by:
link in interface Tree
Following copied from interface: jdsl.core.api.Tree
Parameters:
nextNode - The position to insert the tree t at.
t - The subtree to insert at the position.
Returns:
The object contained in the eliminated extNode
Throws:
InvalidAccessorException - if extNode is not external, is null, or does not belong to this tree.
InvalidContainerException - if t is null, incompatible with, or equal to this tree.

replaceSubtree

public Tree replaceSubtree(Position node,
                           Tree t)
                    throws InvalidAccessorException,
                           InvalidContainerException
O(size of the new subtree + size of the cut tree) time
Specified by:
replaceSubtree in interface Tree
Following copied from interface: jdsl.core.api.Tree
Parameters:
node - a node
t - the tree that will replace the tree rooted at node
Returns:
A new tree, with node as its root
Throws:
InvalidAccessorException - if node is null or does not belong to this tree.
InvalidContainerException - if t is null, incompatible with, or equal to this tree.

insertAfterSibling

public Position insertAfterSibling(Position node,
                                   java.lang.Object elem)
                            throws BoundaryViolationException,
                                   InvalidAccessorException
O(1) time
Specified by:
insertAfterSibling in interface Tree
Following copied from interface: jdsl.core.api.Tree
Parameters:
node - a node different from the root
elem - the object to be stored in the new node
Returns:
the new node
Throws:
BoundaryViolationException - if node is the root
InvalidAccessorException - if node is null or does not belong to this tree

insertChildAtRank

public Position insertChildAtRank(Position node,
                                  int rank,
                                  java.lang.Object elem)
                           throws BoundaryViolationException,
                                  InvalidAccessorException
O(the number of children of the node) time
Specified by:
insertChildAtRank in interface Tree
Following copied from interface: jdsl.core.api.Tree
Parameters:
node - a node
rank - an integer index of the children of node from 0 to numChildren(node) (inclusive)
elem - the object to be stored in the new node
Returns:
the new node
Throws:
BoundaryViolationException - if rank < 0 or rank > numChildren(node)
InvalidAccessorException - if node is null or does not belong to this tree

insertBeforeSibling

public Position insertBeforeSibling(Position node,
                                    java.lang.Object elem)
                             throws BoundaryViolationException,
                                    InvalidAccessorException
O(1) time
Specified by:
insertBeforeSibling in interface Tree
Following copied from interface: jdsl.core.api.Tree
Parameters:
node - a node
elem - the object to be stored in the new node
Returns:
the new node
Throws:
BoundaryViolationException - if node is the root
InvalidAccessorException - if node is null or does not belong to this tree

insertFirstChild

public Position insertFirstChild(Position node,
                                 java.lang.Object elem)
                          throws InvalidAccessorException
O(1) time
Specified by:
insertFirstChild in interface Tree
Following copied from interface: jdsl.core.api.Tree
Parameters:
node - a node
elem - the object to be stored in the new node
Returns:
the new node
Throws:
InvalidAccessorException - if node is null or does not belong to this tree

insertLastChild

public Position insertLastChild(Position node,
                                java.lang.Object elem)
                         throws InvalidAccessorException
O(1) time
Specified by:
insertLastChild in interface Tree
Following copied from interface: jdsl.core.api.Tree
Parameters:
node - a node
elem - the object to be stored in the new node
Returns:
the new node
Throws:
InvalidAccessorException - if node is null or does not belong to this tree

removeExternal

public java.lang.Object removeExternal(Position node)
                                throws BoundaryViolationException,
                                       InvalidAccessorException
O(1) time
Specified by:
removeExternal in interface Tree
Following copied from interface: jdsl.core.api.Tree
Parameters:
node - a leaf node different from the root
Returns:
the object stored in node
Throws:
BoundaryViolationException - if node is not external or is the root
InvalidAccessorException - if node is null or does not belong to this tree

contract

public java.lang.Object contract(Position node)
                          throws BoundaryViolationException,
                                 InvalidAccessorException
O(1) time
Specified by:
contract in interface Tree
Following copied from interface: jdsl.core.api.Tree
Parameters:
node - a node
Returns:
the object stored in node
Throws:
BoundaryViolationException - if node is the root or an external node
InvalidAccessorException - if node is null or does not belong to this tree

expand

public Position expand(Position fromChild,
                       Position toChild,
                       java.lang.Object elem)
                throws InvalidAccessorException
O(number of children of a new node) time
Specified by:
expand in interface Tree
Following copied from interface: jdsl.core.api.Tree
Parameters:
fromChild - a node
toChild - any higher-ranked sibling of fromChild or fromChild itself
elem - the object to be stored in the new node
Returns:
the new node
Throws:
InvalidAccessorException - if fromChild and toChild are not siblings, or if toChild is a lower-ranked sibling of fromChild, or if either of them is null or does not belong to this tree

toString

public java.lang.String toString()
Overrides:
toString in class java.lang.Object