javatools.datatypes
Class PQRTree.Node

java.lang.Object
  javatools.datatypes.PQRTree.Node

Direct Known Subclasses:

PQRTree.Leaf

Enclosing class:

PQRTree<E>

public class PQRTree.Node
extends java.lang.Object

Represents a PQR Tree node

Constructor Summary

PQRTree.Node(PQRTree.NodeType t)
Constructs a node of type t

Method Summary

void	addBlackLeaves(int num) Adds a number of black leaves
void	addChild(PQRTree.Node n) Adds a new child
void	addChild(PQRTree.Node n, int pos) Adds a new child at a given position
void	allocChildren(int n) Allocates space for a certain number of children
PQRTree.Node	child(int pos) Returns the child at a position
PQRTree.Color	color() Returns the color of this node
PQRTree.Node	colorAndGetLCA(int numS) Colors the current node and all ancestors, returns the LCA.
void	debug(java.lang.Object... args) Debugging method
void	dropChild(int pos) Eliminates a child
PQRTree.Node	firstChild() Returns the first child
int	grayChild() Returns the index of the first gray child
boolean	is(PQRTree.Color t) True if the node is of color c
boolean	is(PQRTree.NodeType t) True if the node is of type t
boolean	isBlack() True if the node is black
boolean	isGray() True if the node is gray
boolean	isLeaf() True if the node is of type LEAF
boolean	isP() True if the node is of type P
boolean	isQ() True if the node is of type Q
boolean	isR() True if the node is of type R
boolean	isWhite() True if the node is white
PQRTree.Node	lastChild() Returns the last child
void	makeChildGrandchild(int pos, PQRTree.Node father) Makes the child at pos a child of father
void	makeChildGrandchild(int pos, PQRTree.Node father, int newPos) Makes the child at pos a child of father at newPos
void	makeGrandchildChild(PQRTree.Node father, int oldPos, int newPos) Makes the child of father at oldPos a child of this at newPos
void	mergeIntoLCA(int childPos) Merges the child into the LCA, if the LCA is a Q node or an R node
PQRTree.Node	moveChildrenAway(int childPos) MOves children away from the current node, returns new LCA
int	numChildren() Returns the number of children
void	prepareLCA(int[] childPos) Prepares the LCA, updates the position of a given child
void	reverseLCA(int[] childPos) Reverses the current node (must be LCA of type Q) if this is necessary
void	reverseQNode() Reverses the current node (must be Q) if this is necessary
java.lang.String	toString()
void	transformPintoQ() Transforms a gray P node into a Q node

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, wait, wait, wait

Constructor Detail

PQRTree.Node

public PQRTree.Node(PQRTree.NodeType t)

Constructs a node of type t

Method Detail

dropChild

public void dropChild(int pos)

Eliminates a child

makeChildGrandchild

public void makeChildGrandchild(int pos,
                                PQRTree.Node father,
                                int newPos)

Makes the child at pos a child of father at newPos

makeChildGrandchild

public void makeChildGrandchild(int pos,
                                PQRTree.Node father)

Makes the child at pos a child of father

makeGrandchildChild

public void makeGrandchildChild(PQRTree.Node father,
                                int oldPos,
                                int newPos)

Makes the child of father at oldPos a child of this at newPos

addChild

public void addChild(PQRTree.Node n)

Adds a new child

addChild

public void addChild(PQRTree.Node n,
                     int pos)

Adds a new child at a given position

addBlackLeaves

public void addBlackLeaves(int num)

Adds a number of black leaves

allocChildren

public void allocChildren(int n)

Allocates space for a certain number of children

colorAndGetLCA

public PQRTree.Node colorAndGetLCA(int numS)

Colors the current node and all ancestors, returns the LCA. Call with nodes from the constraint set

color

public PQRTree.Color color()

Returns the color of this node

is

public boolean is(PQRTree.NodeType t)

True if the node is of type t

isP

public boolean isP()

True if the node is of type P

isQ

public boolean isQ()

True if the node is of type Q

isR

public boolean isR()

True if the node is of type R

isLeaf

public boolean isLeaf()

True if the node is of type LEAF

is

public boolean is(PQRTree.Color t)

True if the node is of color c

isWhite

public boolean isWhite()

True if the node is white

isBlack

public boolean isBlack()

True if the node is black

isGray

public boolean isGray()

True if the node is gray

numChildren

public int numChildren()

Returns the number of children

lastChild

public PQRTree.Node lastChild()

Returns the last child

firstChild

public PQRTree.Node firstChild()

Returns the first child

child

public PQRTree.Node child(int pos)

Returns the child at a position

grayChild

public int grayChild()

Returns the index of the first gray child

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object

debug

public void debug(java.lang.Object... args)

Debugging method

transformPintoQ

public void transformPintoQ()

Transforms a gray P node into a Q node

prepareLCA

public void prepareLCA(int[] childPos)

Prepares the LCA, updates the position of a given child

mergeIntoLCA

public void mergeIntoLCA(int childPos)

Merges the child into the LCA, if the LCA is a Q node or an R node

reverseQNode

public void reverseQNode()

Reverses the current node (must be Q) if this is necessary

reverseLCA

public void reverseLCA(int[] childPos)

Reverses the current node (must be LCA of type Q) if this is necessary

moveChildrenAway

public PQRTree.Node moveChildrenAway(int childPos)

MOves children away from the current node, returns new LCA