|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: INNER | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Object | +--jdsl.core.ref.AbstractPositionalContainer | +--jdsl.core.ref.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
jdsl.core.api.InspectableContainer
InvalidAccessorException
- if a is nullpublic boolean isEmpty()
isEmpty
in interface InspectableContainer
isEmpty
in class AbstractPositionalContainer
jdsl.core.api.InspectableContainer
true
if and only if the container is empty (holds
no elements)InspectableBinaryTree
public int size()
size
in interface InspectableContainer
jdsl.core.api.InspectableContainer
public ObjectIterator elements()
elements
in interface InspectableContainer
jdsl.core.api.InspectableContainer
public Container newContainer()
newContainer
in interface Container
jdsl.core.api.Container
public java.lang.Object replaceElement(Accessor a, java.lang.Object newElement) throws InvalidAccessorException
replaceElement
in interface Container
jdsl.core.api.Container
a
- Accessor in this containernewElement
- to be stored at aInvalidAccessorException
- if a is null or does not
belong to this containerpublic PositionIterator positions()
positions
in interface InspectablePositionalContainer
jdsl.core.api.InspectablePositionalContainer
public void swapElements(Position a, Position b) throws InvalidAccessorException
swapElements
in interface PositionalContainer
swapElements
in class AbstractPositionalContainer
jdsl.core.api.PositionalContainer
a
- First Position to swapb
- Second Position to swapInvalidAccessorException
- 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
jdsl.core.api.InspectableTree
node
- a nodetrue
if node
is the root of this treeInvalidAccessorException
- if node
is null or
does not belong to this treepublic boolean isInternal(Position node) throws InvalidAccessorException
isInternal
in interface InspectableTree
jdsl.core.api.InspectableTree
node
- a nodetrue
if node
has at least one childInvalidAccessorException
- if node
is null or
does not belong to this treepublic boolean isExternal(Position node) throws InvalidAccessorException
isExternal
in interface InspectableTree
jdsl.core.api.InspectableTree
node
- Any node of the treetrue
if node
has no childrenInvalidAccessorException
- if node
is null or
does not belong to this treepublic Position root()
root
in interface InspectableTree
jdsl.core.api.InspectableTree
public Position parent(Position node) throws BoundaryViolationException, InvalidAccessorException
parent
in interface InspectableTree
jdsl.core.api.InspectableTree
node
- a nodeBoundaryViolationException
- if node
is the
root of the treeInvalidAccessorException
- if node
is null or
does not belong to this treepublic PositionIterator children(Position node) throws InvalidAccessorException
children
in interface InspectableTree
jdsl.core.api.InspectableTree
node
- a node of the treeInvalidAccessorException
- if node
is null or
does not belong to this treepublic PositionIterator siblings(Position node) throws BoundaryViolationException, InvalidAccessorException
siblings
in interface InspectableTree
jdsl.core.api.InspectableTree
node
- a node of the treeBoundaryViolationException
- if node
is the
root of the treeInvalidAccessorException
- if node
is null or
does not belong to this treepublic int numChildren(Position node) throws InvalidAccessorException
numChildren
in interface InspectableTree
jdsl.core.api.InspectableTree
node
- a node of the treenode
InvalidAccessorException
- if node
is null or
does not belong to this treepublic Position siblingAfter(Position node) throws BoundaryViolationException, InvalidAccessorException
siblingAfter
in interface InspectableTree
jdsl.core.api.InspectableTree
node
- a nodenode
BoundaryViolationException
- if node
is
either the last child of a node or the rootInvalidAccessorException
- if node
is null
or does not belong to this treepublic Position childAtRank(Position node, int rank) throws BoundaryViolationException, InvalidAccessorException
childAtRank
in interface InspectableTree
jdsl.core.api.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 childnode
at the specified rankBoundaryViolationException
- if rank < 0 or rank >
numChildren(node)-1 or node is a leafInvalidAccessorException
- if node
is null
or does not belong to this treepublic Position siblingBefore(Position node) throws BoundaryViolationException, InvalidAccessorException
siblingBefore
in interface InspectableTree
jdsl.core.api.InspectableTree
node
- a nodenode
BoundaryViolationException
- if node
is
either the first child of a node or the rootInvalidAccessorException
- if node
is null
or does not belong to this treepublic Position firstChild(Position node) throws BoundaryViolationException, InvalidAccessorException
firstChild
in interface InspectableTree
jdsl.core.api.InspectableTree
node
- a nodenode
BoundaryViolationException
- if node
is
a leafInvalidAccessorException
- if node
is null
or does not belong to this treepublic Position lastChild(Position node) throws BoundaryViolationException, InvalidAccessorException
lastChild
in interface InspectableTree
jdsl.core.api.InspectableTree
node
- a nodenode
BoundaryViolationException
- if node
is
a leafInvalidAccessorException
- if node
is null
or does not belong to this treepublic int rankOfChild(Position child) throws BoundaryViolationException, InvalidAccessorException
rankOfChild
in interface InspectableTree
jdsl.core.api.InspectableTree
child
- a nodechild
BoundaryViolationException
- if child
is
the rootInvalidAccessorException
- if child
is null
or does not belong to this treepublic Tree cut(Position p) throws InvalidAccessorException
cut
in interface Tree
jdsl.core.api.Tree
node
- The position above which to make the cut;
will be the root of the returned treeInvalidAccessorException
- 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
jdsl.core.api.Tree
nextNode
- 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
jdsl.core.api.Tree
node
- a nodet
- the tree that will replace the tree rooted
at node
node
as its rootInvalidAccessorException
- 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
jdsl.core.api.Tree
node
- a node different from the rootelem
- the object to be stored in the new nodeBoundaryViolationException
- if node
is the rootInvalidAccessorException
- 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
jdsl.core.api.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 nodeBoundaryViolationException
- 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
jdsl.core.api.Tree
node
- a nodeelem
- the object to be stored in the new nodeBoundaryViolationException
- if node
is the rootInvalidAccessorException
- 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
jdsl.core.api.Tree
node
- a nodeelem
- the object to be stored in the new nodeInvalidAccessorException
- 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
jdsl.core.api.Tree
node
- a nodeelem
- the object to be stored in the new nodeInvalidAccessorException
- if node
is null
or does not belong to this treepublic java.lang.Object removeExternal(Position node) throws BoundaryViolationException, InvalidAccessorException
removeExternal
in interface Tree
jdsl.core.api.Tree
node
- a leaf node different from the rootnode
BoundaryViolationException
- if node
is not
external or is the rootInvalidAccessorException
- if node
is null
or does not belong to this treepublic java.lang.Object contract(Position node) throws BoundaryViolationException, InvalidAccessorException
contract
in interface Tree
jdsl.core.api.Tree
node
- a nodenode
BoundaryViolationException
- if node
is the
root or an external nodeInvalidAccessorException
- 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
jdsl.core.api.Tree
fromChild
- a nodetoChild
- any higher-ranked sibling of
fromChild
or fromChild
itselfelem
- the object to be stored in the new nodeInvalidAccessorException
- 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: INNER | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |