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:

JDSL 2.1.1

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
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, Object elem) O(number of children of a new node) time
Position	firstChild(Position node) O(1) time
Position	insertAfterSibling(Position node, Object elem) O(1) time
Position	insertBeforeSibling(Position node, Object elem) O(1) time
Position	insertChildAtRank(Position node, int rank, Object elem) O(the number of children of the node) time
Position	insertFirstChild(Position node, Object elem) O(1) time
Position	insertLastChild(Position node, 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
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
Object	removeExternal(Position node) O(1) time
Object	replaceElement(Accessor a, 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
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

Throws:

InvalidAccessorException - if a is null

isEmpty

public boolean isEmpty()

O(1) time

Specified by:

isEmpty in interface InspectableContainer

Overrides:

isEmpty in class AbstractPositionalContainer

size

public int size()

O(1) time

Specified by:

size in interface 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

Returns:

an iterator over all the elements stored in this container

newContainer

public Container newContainer()

O(1) time

Specified by:

newContainer in interface Container

Returns:

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

replaceElement

public Object replaceElement(Accessor a,
                             Object newElement)
                      throws InvalidAccessorException

O(1) time

Specified by:

replaceElement in interface 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

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

Throws:

InvalidAccessorException

isRoot

public boolean isRoot(Position node)
               throws InvalidAccessorException

O(1) time

Specified by:

isRoot in interface 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

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

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

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

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

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

Parameters:

node - a node of the tree

Returns:

iterator over all the other children of the same parent

Throws:

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

BoundaryViolationException - if node is the root of the tree

numChildren

public int numChildren(Position node)
                throws InvalidAccessorException

O(1) time

Specified by:

numChildren in interface 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

Parameters:

node - a node

Returns:

the sibling after node

Throws:

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

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

childAtRank

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

O(1) time

Specified by:

childAtRank in interface 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

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

Parameters:

node - a node

Returns:

the first child of node

Throws:

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

BoundaryViolationException - if node is a leaf

lastChild

public Position lastChild(Position node)
                   throws BoundaryViolationException,
                          InvalidAccessorException

O(1) time

Specified by:

lastChild in interface 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

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

Parameters:

p - 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 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

Parameters:

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

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

InvalidAccessorException - if extNode is not external, is null, or does not belong 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

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,
                                   Object elem)
                            throws BoundaryViolationException,
                                   InvalidAccessorException

O(1) time

Specified by:

insertAfterSibling in interface 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,
                                  Object elem)
                           throws BoundaryViolationException,
                                  InvalidAccessorException

O(the number of children of the node) time

Specified by:

insertChildAtRank in interface 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:

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

BoundaryViolationException - if rank < 0 or rank > numChildren(node)

insertBeforeSibling

public Position insertBeforeSibling(Position node,
                                    Object elem)
                             throws BoundaryViolationException,
                                    InvalidAccessorException

O(1) time

Specified by:

insertBeforeSibling in interface 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

BoundaryViolationException - if node is the root

insertFirstChild

public Position insertFirstChild(Position node,
                                 Object elem)
                          throws InvalidAccessorException

O(1) time

Specified by:

insertFirstChild in interface 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,
                                Object elem)
                         throws InvalidAccessorException

O(1) time

Specified by:

insertLastChild in interface 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 Object removeExternal(Position node)
                      throws BoundaryViolationException,
                             InvalidAccessorException

O(1) time

Specified by:

removeExternal in interface 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 Object contract(Position node)
                throws BoundaryViolationException,
                       InvalidAccessorException

O(1) time

Specified by:

contract in interface 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,
                       Object elem)
                throws InvalidAccessorException

O(number of children of a new node) time

Specified by:

expand in interface 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 String toString()