jdsl.core.api
Interface Tree

All Superinterfaces:

Container, InspectableContainer, InspectablePositionalContainer, InspectableTree, PositionalContainer

All Known Implementing Classes:

NodeTree

public interface Tree

extends InspectableTree, PositionalContainer

A positional container representing an ordered tree. The children of each internal node are ordered. A tree always has at least one node (isEmpty() always returns false). The smallest tree is a single external node.

Version:

JDSL 2.1.1

Author:

Mark Handy, Mike Boilen (mgb), Andrew Schwerin (schwerin), Luca Vismara (lv), Galina Shubina (gs)

See Also:

InspectableTree

Method Summary

Object	contract(Position node) Replaces a node with its children in the appropriate order.
Tree	cut(Position node) Cuts this tree above the given node, and replaces this position with an external node with a null element.
Position	expand(Position fromChild, Position toChild, Object elem) Replaces a set of consecutive children with a new node having those children as its children in the appropriate order.
Position	insertAfterSibling(Position node, Object elem) Inserts a new sibling after a given node
Position	insertBeforeSibling(Position node, Object elem) Inserts a new sibling before a given node.
Position	insertChildAtRank(Position node, int rank, Object elem) Inserts a new child of node at the specified rank.
Position	insertFirstChild(Position node, Object elem) Inserts a new child of node as the first child.
Position	insertLastChild(Position node, Object elem) Inserts a new child of node as the last child.
Object	link(Position extNode, Tree t) Links tree t at external node extNode by replacing ExtNode with the root of t.
Object	removeExternal(Position node) Removes an external node (a leaf).
Tree	replaceSubtree(Position node, Tree t) Replaces the subtree rooted at node with the tree t.

Methods inherited from interface jdsl.core.api.InspectableTree

childAtRank, children, firstChild, isExternal, isInternal, isRoot, lastChild, numChildren, parent, rankOfChild, root, siblingAfter, siblingBefore, siblings

Methods inherited from interface jdsl.core.api.InspectablePositionalContainer

positions

Methods inherited from interface jdsl.core.api.InspectableContainer

contains, elements, isEmpty, size

Methods inherited from interface jdsl.core.api.PositionalContainer

swapElements

Methods inherited from interface jdsl.core.api.Container

newContainer, replaceElement

Method Detail

cut

public Tree cut(Position node)
         throws InvalidAccessorException

Cuts this tree above the given node, and replaces this position with an external node with a null element. The subtree cut off at that point is returned to the user as a brand new Tree intstance.

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 Object link(Position extNode,
                   Tree t)
            throws InvalidAccessorException,
                   InvalidContainerException

Links tree t at external node extNode by replacing ExtNode with the root of t. As a result of this method, the positions of tree t become positions of this tree and tree t becomes a tree with a single node with a null element.

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:

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

Replaces the subtree rooted at node with the tree t. The positions of t become positions of this tree. The cut subtree with the node as its root is returned to the user as a new tree instance. All the positions of this subtree become positions of this new tree. Note that link(.) and cut(.) can both be implemented in terms of this method.

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

Inserts a new sibling after a given node

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

Inserts a new child of node at the specified rank.

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

Inserts a new sibling before a given node.

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

Inserts a new child of node as the first child.

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

Inserts a new child of node as the last child.

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

Removes an external node (a leaf).

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

Replaces a node with its children in the appropriate order. It removes node, and then inserts its children, maintaining their order, between siblingBefore(node) and siblingAfter(node).

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

Replaces a set of consecutive children with a new node having those children as its children in the appropriate order. It removes the children between fromChild and toChild (inclusive), inserts a new node in their place, and makes the removed children the children of the new node, maintaining their order.

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