|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Object nz.ac.waikato.jdsl.core.ref.AbstractPositionalContainer nz.ac.waikato.jdsl.core.ref.NodeTree
public class NodeTree
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).
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 |
---|
public NodeTree()
Method Detail |
---|
public boolean contains(Accessor a) throws InvalidAccessorException
contains
in interface InspectableContainer
InvalidAccessorException
- if a is nullpublic boolean isEmpty()
isEmpty
in interface InspectableContainer
isEmpty
in class AbstractPositionalContainer
true
if and only if the container is empty (holds
no elements)InspectableBinaryTree
public int size()
size
in interface InspectableContainer
public ObjectIterator elements()
elements
in interface InspectableContainer
public Container newContainer()
newContainer
in interface Container
public java.lang.Object replaceElement(Accessor a, java.lang.Object newElement) throws InvalidAccessorException
replaceElement
in interface Container
a
- Accessor in this containernewElement
- to be stored at a
InvalidAccessorException
- if a is null or does not
belong to this containerpublic PositionIterator positions()
positions
in interface InspectablePositionalContainer
public void swapElements(Position a, Position b) throws InvalidAccessorException
swapElements
in interface PositionalContainer
swapElements
in class AbstractPositionalContainer
a
- First Position to swapb
- Second Position to swap
InvalidAccessorException
- if either of a
and b
is null or does not belong to this positional
containerpublic boolean isRoot(Position node) throws InvalidAccessorException
isRoot
in interface InspectableTree
node
- a node
true
if node
is the root of this tree
InvalidAccessorException
- if node
is null or
does not belong to this treepublic boolean isInternal(Position node) throws InvalidAccessorException
isInternal
in interface InspectableTree
node
- a node
true
if node
has at least one child
InvalidAccessorException
- if node
is null or
does not belong to this treepublic boolean isExternal(Position node) throws InvalidAccessorException
isExternal
in interface InspectableTree
node
- Any node of the tree
true
if node
has no children
InvalidAccessorException
- if node
is null or
does not belong to this treepublic Position root()
root
in interface InspectableTree
public Position parent(Position node) throws BoundaryViolationException, InvalidAccessorException
parent
in interface InspectableTree
node
- a node
BoundaryViolationException
- if node
is the
root of the tree
InvalidAccessorException
- if node
is null or
does not belong to this treepublic PositionIterator children(Position node) throws InvalidAccessorException
children
in interface InspectableTree
node
- a node of the tree
InvalidAccessorException
- if node
is null or
does not belong to this treepublic PositionIterator siblings(Position node) throws BoundaryViolationException, InvalidAccessorException
siblings
in interface InspectableTree
node
- a node of the tree
BoundaryViolationException
- if node
is the
root of the tree
InvalidAccessorException
- if node
is null or
does not belong to this treepublic int numChildren(Position node) throws InvalidAccessorException
numChildren
in interface InspectableTree
node
- a node of the tree
node
InvalidAccessorException
- if node
is null or
does not belong to this treepublic Position siblingAfter(Position node) throws BoundaryViolationException, InvalidAccessorException
siblingAfter
in interface InspectableTree
node
- a node
node
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 treepublic Position childAtRank(Position node, int rank) throws BoundaryViolationException, InvalidAccessorException
childAtRank
in interface InspectableTree
node
- a noderank
- an integer index of the children of
node
; childAtRank(0) is the first child,
childAtRank(numChildren(node)-1) is the last child
node
at the specified rank
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 treepublic Position siblingBefore(Position node) throws BoundaryViolationException, InvalidAccessorException
siblingBefore
in interface InspectableTree
node
- a node
node
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 treepublic Position firstChild(Position node) throws BoundaryViolationException, InvalidAccessorException
firstChild
in interface InspectableTree
node
- a node
node
BoundaryViolationException
- if node
is
a leaf
InvalidAccessorException
- if node
is null
or does not belong to this treepublic Position lastChild(Position node) throws BoundaryViolationException, InvalidAccessorException
lastChild
in interface InspectableTree
node
- a node
node
BoundaryViolationException
- if node
is
a leaf
InvalidAccessorException
- if node
is null
or does not belong to this treepublic int rankOfChild(Position child) throws BoundaryViolationException, InvalidAccessorException
rankOfChild
in interface InspectableTree
child
- a node
child
BoundaryViolationException
- if child
is
the root
InvalidAccessorException
- if child
is null
or does not belong to this treepublic Tree cut(Position p) throws InvalidAccessorException
cut
in interface Tree
p
- The position above which to make the cut;
will be the root of the returned tree
InvalidAccessorException
- if node
is null
or does not belong to this tree.public java.lang.Object link(Position extNode, Tree t) throws InvalidAccessorException, InvalidContainerException
link
in interface Tree
extNode
- The position to insert the tree
t
at.t
- The subtree to insert at the position.
extNode
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.public Tree replaceSubtree(Position node, Tree t) throws InvalidAccessorException, InvalidContainerException
replaceSubtree
in interface Tree
node
- a nodet
- the tree that will replace the tree rooted
at node
node
as its root
InvalidAccessorException
- if node
is null
or does not belong to this tree.
InvalidContainerException
- if t
is null,
incompatible with, or equal to this tree.public Position insertAfterSibling(Position node, java.lang.Object elem) throws BoundaryViolationException, InvalidAccessorException
insertAfterSibling
in interface Tree
node
- a node different from the rootelem
- the object to be stored in the new node
BoundaryViolationException
- if node
is the root
InvalidAccessorException
- if node
is null
or does not belong to this treepublic Position insertChildAtRank(Position node, int rank, java.lang.Object elem) throws BoundaryViolationException, InvalidAccessorException
insertChildAtRank
in interface Tree
node
- a noderank
- an integer index of the children of node
from 0 to numChildren(node) (inclusive)elem
- the object to be stored in the new node
BoundaryViolationException
- if rank
< 0 or
rank
> numChildren(node
)
InvalidAccessorException
- if node
is null
or does not belong to this treepublic Position insertBeforeSibling(Position node, java.lang.Object elem) throws BoundaryViolationException, InvalidAccessorException
insertBeforeSibling
in interface Tree
node
- a nodeelem
- the object to be stored in the new node
BoundaryViolationException
- if node
is the root
InvalidAccessorException
- if node
is null
or does not belong to this treepublic Position insertFirstChild(Position node, java.lang.Object elem) throws InvalidAccessorException
insertFirstChild
in interface Tree
node
- a nodeelem
- the object to be stored in the new node
InvalidAccessorException
- if node
is null
or does not belong to this treepublic Position insertLastChild(Position node, java.lang.Object elem) throws InvalidAccessorException
insertLastChild
in interface Tree
node
- a nodeelem
- the object to be stored in the new node
InvalidAccessorException
- if node
is null
or does not belong to this treepublic java.lang.Object removeExternal(Position node) throws BoundaryViolationException, InvalidAccessorException
removeExternal
in interface Tree
node
- a leaf node different from the root
node
BoundaryViolationException
- if node
is not
external or is the root
InvalidAccessorException
- if node
is null
or does not belong to this treepublic java.lang.Object contract(Position node) throws BoundaryViolationException, InvalidAccessorException
contract
in interface Tree
node
- a node
node
BoundaryViolationException
- if node
is the
root or an external node
InvalidAccessorException
- if node
is null
or does not belong to this treepublic Position expand(Position fromChild, Position toChild, java.lang.Object elem) throws InvalidAccessorException
expand
in interface Tree
fromChild
- a nodetoChild
- any higher-ranked sibling of
fromChild
or fromChild
itselfelem
- the object to be stored in the new node
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 treepublic java.lang.String toString()
toString
in class java.lang.Object
|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |