pqrtree
Class Node

java.lang.Object
  pqrtree.Node

Direct Known Subclasses:

Leaf, PQRNode

public class Node
extends java.lang.Object

A node object can be of four types: P, Q, R - represented by the PQRNode class - or leaves - represented by the Leaf class.

Version:

0.1

Author:

Bruno Dilly

See Also:

PQRNode, Leaf

Field Summary

protected PQRNode	ancestor
protected ListNode	ancestorListPosition
protected Node	ancestorReference
private int	color
protected static int	COLOR_BLACK
protected static int	COLOR_GRAY
protected static int	COLOR_WHITE
protected boolean	leaf
protected static int	TYPE_PNODE
protected static int	TYPE_QNODE
protected static int	TYPE_RNODE
private boolean	visited

Constructor Summary

Node(PQRNode ancestor)
Creates a new PQRTree's node, linked to it's ancestor

Method Summary

Node	findLeader() Finds the representative of the disjoint set, implementing the shrink path heuristics
PQRNode	getAncestor() Gets the ancestor direct link, if it exists.
ListNode	getAncestorListPosition() Gets the node of the children list of the parent that points to the node.
Node	getAncestorReference() Gets the ancestor reference link, if it exists.
int	getColor() Returns the color of the node.
PQRNode	getParent() Finds the imediate ancestor of the node.
boolean	isLeaf() Verifies if the node is a leaf.
void	setAncestor(PQRNode ancestor) Sets the ancestor direct link.
void	setAncestorListPosition(ListNode n) Sets the node of the children list of the parent that points to the node.
void	setAncestorReference(Node n) Sets the ancestor direct link.
void	setColor(int color) Sets the color of the node.
void	setParent(PQRNode p) Sets ancestor direct link and ancestor reference to make possible finding the parent.
Node	union(Node v, int sizeV, Node p, int sizeP) Join two node children of the same node.
void	visited(boolean visited) Sets the visited state of the node.
boolean	wasVisited() Verifies if the node was already visited.

Methods inherited from class java.lang.Object

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

Field Detail

visited

private boolean visited

color

private int color

leaf

protected boolean leaf

ancestorListPosition

protected ListNode ancestorListPosition

ancestor

protected PQRNode ancestor

ancestorReference

protected Node ancestorReference

TYPE_PNODE

protected static final int TYPE_PNODE

See Also:

Constant Field Values

TYPE_QNODE

protected static final int TYPE_QNODE

See Also:

Constant Field Values

TYPE_RNODE

protected static final int TYPE_RNODE

See Also:

Constant Field Values

COLOR_WHITE

protected static final int COLOR_WHITE

See Also:

Constant Field Values

COLOR_GRAY

protected static final int COLOR_GRAY

See Also:

Constant Field Values

COLOR_BLACK

protected static final int COLOR_BLACK

See Also:

Constant Field Values

Constructor Detail

Node

public Node(PQRNode ancestor)

Creates a new PQRTree's node, linked to it's ancestor

Parameters:

ancestor - The internal node from which the new node descend

Method Detail

wasVisited

public boolean wasVisited()

Verifies if the node was already visited.

Returns:

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

visited

public void visited(boolean visited)

Sets the visited state of the node.

Parameters:

visited - Reports if the node was visited.

getAncestor

public PQRNode getAncestor()

Gets the ancestor direct link, if it exists. It just exists if the node is child of a P node.

Returns:

The ancestor, if it's a P node, or null.

setAncestor

public void setAncestor(PQRNode ancestor)

Sets the ancestor direct link.

Parameters:

ancestor - The ancestor, if it's a P node, or null.

getAncestorReference

public Node getAncestorReference()

Gets the ancestor reference link, if it exists. It just exists if the node is child of a Q or R node. It's the attribute necessary to implements disjoint sets.

Returns:

The ancestor reference, that should be a brother node or maybe itself.

setAncestorReference

public void setAncestorReference(Node n)

Sets the ancestor direct link.

Parameters:

n - The ancestor reference. Must be a brother, itself, or null.

getParent

public PQRNode getParent()

Finds the imediate ancestor of the node. It can be child of P, Q or R node. The parent will be find.

Returns:

The imediate ancestor.

See Also:

getAncestor(), getAncestorReference()

setParent

public void setParent(PQRNode p)

Sets ancestor direct link and ancestor reference to make possible finding the parent.

Parameters:

p - The parent.

See Also:

setAncestor(PQRNode), setAncestorReference(Node)

getColor

public int getColor()

Returns the color of the node. It can be, black, gray or white.

Returns:

Color of the node

setColor

public void setColor(int color)

Sets the color of the node. It can be, black, gray or white.

Parameters:

color - Color black, gray or white.

isLeaf

public boolean isLeaf()

Verifies if the node is a leaf.

Returns:

true, if the node is a leaf, or false, if it isn't.

getAncestorListPosition

public ListNode getAncestorListPosition()

Gets the node of the children list of the parent that points to the node.

Returns:

The list node that points to the node.

setAncestorListPosition

public void setAncestorListPosition(ListNode n)

Sets the node of the children list of the parent that points to the node.

Parameters:

n - The list node.

findLeader

public Node findLeader()

Finds the representative of the disjoint set, implementing the shrink path heuristics

Returns:

The representative of the disjoint set

union

public Node union(Node v,
                  int sizeV,
                  Node p,
                  int sizeP)

Join two node children of the same node. It implements the balancing disjoint sets heuristic.

Parameters:

v - One node

sizeV - Weight of the first node

p - Another node

sizeP - Weight of the second node

Returns:

The node choosen to be the representative.