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:
$Id: Tree.java,v 1.10 2000/01/12 03:21:34 mdh Exp $
Author:
Mark Handy, Mike Boilen (mgb), Andrew Schwerin (schwerin), Luca Vismara (lv), Galina Shubina (gs)
See Also:
InspectableTree

Method Summary
 java.lang.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, java.lang.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, java.lang.Object elem)
          Inserts a new sibling after a given node
 Position insertBeforeSibling(Position node, java.lang.Object elem)
          Inserts a new sibling before a given node.
 Position insertChildAtRank(Position node, int rank, java.lang.Object elem)
          Inserts a new child of node at the specified rank.
 Position insertFirstChild(Position node, java.lang.Object elem)
          Inserts a new child of node as the first child.
 Position insertLastChild(Position node, java.lang.Object elem)
          Inserts a new child of node as the last child.
 java.lang.Object link(Position extNode, Tree t)
          Links tree t at external node extNode by replacing ExtNode with the root of t.
 java.lang.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 java.lang.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:
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
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,
                                   java.lang.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,
                                  java.lang.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,
                                    java.lang.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,
                                 java.lang.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,
                                java.lang.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 java.lang.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 java.lang.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,
                       java.lang.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