pqrtree
Class PQRNode

java.lang.Object
  pqrtree.Node
      pqrtree.PQRNode

public class PQRNode
extends Node

A PQRNode object is an intern node of PQRTree. It can be type P, Q or R. Every P Node has at least 2 children, that can be arbitrary permutated. Every Q Node has at least 3 children, that can be reversed. Every R Node has at least 3 children, that can be arbitrary permutated. The R nodes encapsulate subsets where the consecutive ones proprety fails.

Version:

0.1

Author:

Bruno Dilly

See Also:

Node

Field Summary

private ColoredDoublyLinkedList	blackChildren
private ChildrenDoublyLinkedList	children
private boolean	deleted
private ColoredDoublyLinkedList	grayChildren
private int	pertinentLeaves
private int	pertinentPaths
private int	type

Fields inherited from class pqrtree.Node

ancestor, ancestorListPosition, ancestorReference, COLOR_BLACK, COLOR_GRAY, COLOR_WHITE, DRAW_BLACK_COLOR, DRAW_BOUNDARY_SIZE, DRAW_CONNECTOR_SIZE, DRAW_GRAY_COLOR, DRAW_NORMAL_COLOR, DRAW_SIZE, DRAW_WHITE_COLOR, leaf, TYPE_PNODE, TYPE_QNODE, TYPE_RNODE

Constructor Summary

PQRNode(int type, PQRNode ancestor)
Creates a new internal node of the PQRTree, type P, Q or R, linked to it's ancestor.

Method Summary

void	addBlackChild(Node child) Adds a child node to the end of the black children's list.
void	addChild(Node child) Adds a node to the end of the children's list.
void	addGrayChild(Node child) Adds a child node to the end of the gray children's list.
boolean	areAllChildrenBlack() Verifies if all children are black.
boolean	areBlackChildrenConsecutive() Verifies if all black children are consecutive.
void	clearBlackChildren() Empties the black children's list.
void	clearChildren() Empties the children's list.
void	clearGrayChildren() Empties the gray children's list.
void	decPertinentPaths() Decrements the pertinent paths counter by one.
ColoredDoublyLinkedList	getBlackChildren() Gets the black children's list and returns it.
ChildrenDoublyLinkedList	getChildren() Gets the children's list and returns it.
ListNode	getFirstChild() Gets the first child, and returns it.
PQRNode	getGrayChild() Gets a gray child node, and returns it.
ColoredDoublyLinkedList	getGrayChildren() Gets the gray children's list and returns it.
ListNode	getLastChild() Gets the last child, and returns it.
int	getPertinentLeaves() Gets the pertinent leaves counter value.
int	getPertinentPaths() Gets the pertinent paths counter value.
int	getType() Returns the type of the node.
boolean	hasGrayChildren() Verifies if the node has at least one gray child.
void	incPertinentLeaves(int i) Increments the pertinent leaves counter by a integer value.
void	incPertinentPaths() Increments the pertinent paths counter by one.
void	setBlackChildren(ColoredDoublyLinkedList newList) Changes the black children's list by another one.
void	setChildren(ChildrenDoublyLinkedList newList) Changes the children's list by another one.
void	setDeleted() Sets the node as deleted.
void	setGrayChildren(ColoredDoublyLinkedList newList) Changes the gray children's list by another one.
void	setPertinentLeaves(int newValue) Sets the pertinent leaves counter to a new value.
void	setPertinentPaths(int newValue) Sets the pertinent paths counter to a new value.
void	setType(int type) Sets the type of the node.
void	substitutedBy(PQRNode v) Substitutes the node by another one.
boolean	wasDeleted() Verifies if the node was deleted
void	zeroPertinentLeaves() Sets the pertinent leaves counter to zero.
void	zeroPertinentPaths() Sets the pertinent paths counter to zero.

Methods inherited from class pqrtree.Node

countSubLeaves, drawNode, findLeader, getAncestor, getAncestorListPosition, getAncestorReference, getColor, getDepth, getParent, isLeaf, setAncestor, setAncestorListPosition, setAncestorReference, setColor, setParent, union, visited, wasVisited

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

type

private int type

pertinentPaths

private int pertinentPaths

pertinentLeaves

private int pertinentLeaves

deleted

private boolean deleted

children

private ChildrenDoublyLinkedList children

blackChildren

private ColoredDoublyLinkedList blackChildren

grayChildren

private ColoredDoublyLinkedList grayChildren

Constructor Detail

PQRNode

public PQRNode(int type,
               PQRNode ancestor)

Creates a new internal node of the PQRTree, type P, Q or R, linked to it's ancestor.

Parameters:

type - The type of the internal node. Could be a P, Q or R node.

ancestor - The internal node from which the new node descend.

See Also:

Node.Node(PQRNode)

Method Detail

getType

public int getType()

Returns the type of the node.

Returns:

The type of the node: P, Q or R node.

setType

public void setType(int type)

Sets the type of the node. It's necessary when a explicit change is required.

Parameters:

type - The type of the node: P, Q or R node.

incPertinentPaths

public void incPertinentPaths()

Increments the pertinent paths counter by one.

decPertinentPaths

public void decPertinentPaths()

Decrements the pertinent paths counter by one.

zeroPertinentPaths

public void zeroPertinentPaths()

Sets the pertinent paths counter to zero.

setPertinentPaths

public void setPertinentPaths(int newValue)

Sets the pertinent paths counter to a new value.

Parameters:

newValue - The new pertinent paths value.

getPertinentPaths

public int getPertinentPaths()

Gets the pertinent paths counter value.

Returns:

The pertinent paths counter value.

incPertinentLeaves

public void incPertinentLeaves(int i)

Increments the pertinent leaves counter by a integer value.

Parameters:

i - The value of pertinent leaves to be added to the pertinent leaves counter.

zeroPertinentLeaves

public void zeroPertinentLeaves()

Sets the pertinent leaves counter to zero.

setPertinentLeaves

public void setPertinentLeaves(int newValue)

Sets the pertinent leaves counter to a new value.

Parameters:

newValue - The new pertinent leaves value.

getPertinentLeaves

public int getPertinentLeaves()

Gets the pertinent leaves counter value.

Returns:

The pertinent leaves counter value.

getChildren

public ChildrenDoublyLinkedList getChildren()

Gets the children's list and returns it.

Returns:

The children's list.

getBlackChildren

public ColoredDoublyLinkedList getBlackChildren()

Gets the black children's list and returns it.

Returns:

The black children's list.

getGrayChildren

public ColoredDoublyLinkedList getGrayChildren()

Gets the gray children's list and returns it.

Returns:

The gray children's list.

setChildren

public void setChildren(ChildrenDoublyLinkedList newList)

Changes the children's list by another one.

Parameters:

newList - A new children's list.

setBlackChildren

public void setBlackChildren(ColoredDoublyLinkedList newList)

Changes the black children's list by another one.

Parameters:

newList - A new black children's list.

setGrayChildren

public void setGrayChildren(ColoredDoublyLinkedList newList)

Changes the gray children's list by another one.

Parameters:

newList - A new gray children's list.

areBlackChildrenConsecutive

public boolean areBlackChildrenConsecutive()

Verifies if all black children are consecutive.

Returns:

true, if all black children are consecutive, or false, if they aren't.

areAllChildrenBlack

public boolean areAllChildrenBlack()

Verifies if all children are black.

Returns:

true, if all children are black, or false, if they aren't.

addChild

public void addChild(Node child)

Adds a node to the end of the children's list.

Parameters:

child - Node to be added to the children's list.

addBlackChild

public void addBlackChild(Node child)

Adds a child node to the end of the black children's list. It means that this child will be considered black by the ancestor.

Parameters:

child - Node to be considered black by the ancestor.

addGrayChild

public void addGrayChild(Node child)

Adds a child node to the end of the gray children's list. It means that this child will be considered gray by the ancestor.

Parameters:

child - Node to be considered gray by the ancestor.

clearBlackChildren

public void clearBlackChildren()

Empties the black children's list.

clearGrayChildren

public void clearGrayChildren()

Empties the gray children's list.

clearChildren

public void clearChildren()

Empties the children's list.

hasGrayChildren

public boolean hasGrayChildren()

Verifies if the node has at least one gray child.

Returns:

true, if it has at least onde gray child, or false, if it doesn't.

getGrayChild

public PQRNode getGrayChild()

Gets a gray child node, and returns it. It isn't removed.

Returns:

A gray child.

getFirstChild

public ListNode getFirstChild()

Gets the first child, and returns it. It isn't removed.

Returns:

The first child.

getLastChild

public ListNode getLastChild()

Gets the last child, and returns it. It isn't removed.

Returns:

The last child.

substitutedBy

public void substitutedBy(PQRNode v)

Substitutes the node by another one. So, the ancestor, the ancestor list position, and the reference ancestor is hold. All the other attributes are changed by the other node ones.

Parameters:

v - The node that will substitutes this one. v must be a Q or R node.

wasDeleted

public boolean wasDeleted()

Verifies if the node was deleted

Returns:

true, if the was deleted, or false, if it wasn't.

setDeleted

public void setDeleted()

Sets the node as deleted.