pqrtree
Class PQRTree

java.lang.Object
  pqrtree.PQRTree

All Implemented Interfaces:

java.lang.Runnable

public class PQRTree
extends java.lang.Object
implements java.lang.Runnable

A PQR Tree over a set U is a rooted tree with four types of nodes - P, Q, R and leaves. PQR Tree is a compact way of storing and manipulating all the permutantion of n elements that keep consecutive the elements in certaing given sets. And encapsulates subsets where the consecutive ones fails by R nodes.

Version:

0.1

Author:

Bruno Dilly

Field Summary

java.util.concurrent.locks.Lock	addSetLock
java.util.concurrent.locks.Condition	canAddSet
java.util.concurrent.locks.Condition	canBePainted
private static int	COLOR_BLACK
private static int	COLOR_GRAY
private static int	COLOR_WHITE
PQRController	controller
private boolean	doneReduction
private int	drawHeight
private int	drawWidth
private boolean	hasChanged
private Leaf[]	leaves
java.util.concurrent.locks.Condition	nextStep
private java.lang.String	operationsString
private boolean	painted
private java.lang.String	reduceString
private PQRNode	root
private int[]	s
private boolean	setToBeAdded
private boolean	stepByStep
private static int	TYPE_PNODE
private static int	TYPE_QNODE
private static int	TYPE_RNODE

Constructor Summary

PQRTree(java.lang.Object[] u)
Creates a universal PQRTree.

PQRTree(java.lang.Object[] u, int[][] c)
Creates a universal PQRTree.

PQRTree(java.lang.Object[] u, PQRController controller, java.util.concurrent.locks.Lock addSetLock, java.util.concurrent.locks.Condition canAddSet, java.util.concurrent.locks.Condition canBePainted, java.util.concurrent.locks.Condition nextStep)
Creates a universal PQRTree.

Method Summary

void	addSet() Changes the tree to keep consecutive the elements of the set previously added, if it's possible.
void	addSet(int[] s) Changes the tree to keep consecutive the elements of the set s, if it's possible.
private void	adjustLCA(PQRNode w) Adjusts the LCA according to its type.
private void	changePIntoQ(PQRNode v) Changes the type of the node from P to Q.
private void	changeQIntoR(PQRNode w) Changes a Q LCA with black children not consecutive into a R node.
private PQRNode	colorTree(int[] s) Colors black the leaves corresponding to the elements of s, colors black, gray or keeps white the internal nodes, and finds the Least Commons Ancestor.
void	drawTree(java.awt.Graphics aPen) Draws the tree to the GUI.
java.lang.String	frontier() Finds a valid permutation given the collection.
private java.lang.String	frontier(Node v) Creates a string representing a valid permutation recursively.
int	getHeight()
Node	getLeafAt(int index) Returns a leaf node with the specified index relative the the order in which they were originally added when the PQTree was built.
java.util.Vector	getLeaves() Gets the leaves of the Tree
java.lang.String	getOperationsString() Gets the operations string.
java.lang.String	getReduceString() Gets the reduce string.
int	getWidth()
boolean	isDoneReduction() Verifies if a reduction is already concluded.
private PQRNode	moveChildrenToGrayNode(PQRNode w, PQRNode v) A gray child of the LCA become the ancestor of its black and gray brother nodes.
private void	moveChildrenToLCA(PQRNode w, PQRNode v) Move the children from a gray node, child of the LCA, to the LCA.
java.lang.String	preOrder() Represents the PQR tree in pre order way.
private java.lang.String	preOrder(Node v) Creates a string representing the tree recursively.
private void	prepareLCA(PQRNode w) Groups the black children of LCA into a new P node.
private PQRNode	preparePNode(PQRNode v) Groups black children and white children into new P nodes.
void	prepareToDrawTree() Prepares the PQTree to be drawn by the GUI by calculating the width and height needed to draw the tree, and calculated the width and height required to draw each node of the tree.
private PQRNode	reduceTree(PQRNode w) Repeatedly kills, merge, or uncolors gray nodes, sometimes also creating new nodes when needed, until no gray nodes remain in the tree.
void	reset() Resets the tree to a P-universal.
private void	reverseGrayNode(PQRNode v) Reverse a Q gray node, if its children isn't in the right order.
void	run() Runs the thread.
void	setConstraints(int[] s) Sets the constraints.
void	setLocks(java.util.concurrent.locks.Lock addSetLock, java.util.concurrent.locks.Condition canAddSet, java.util.concurrent.locks.Condition canBePainted, java.util.concurrent.locks.Condition nextStep) Sets the lock and conditions to work with the controller.
void	setPainted(boolean p) Sets the tree to painted or not yet painted.
void	setReduceString(int[] s) Sets the reduce string.
void	setStep(boolean s) Sets the tree to reduct completely or by steps.
void	step() Signals the controller to paint the tree, and waits for signal to continue with the next step of the reduction.
private void	uncolorTree(int[] s) Uncolors all black nodes

Methods inherited from class java.lang.Object

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

Field Detail

root

private PQRNode root

leaves

private Leaf[] leaves

TYPE_PNODE

private static final int TYPE_PNODE

See Also:

Constant Field Values

TYPE_QNODE

private static final int TYPE_QNODE

See Also:

Constant Field Values

TYPE_RNODE

private static final int TYPE_RNODE

See Also:

Constant Field Values

COLOR_WHITE

private static final int COLOR_WHITE

See Also:

Constant Field Values

COLOR_GRAY

private static final int COLOR_GRAY

See Also:

Constant Field Values

COLOR_BLACK

private static final int COLOR_BLACK

See Also:

Constant Field Values

s

private int[] s

drawWidth

private int drawWidth

drawHeight

private int drawHeight

hasChanged

private boolean hasChanged

doneReduction

private boolean doneReduction

reduceString

private java.lang.String reduceString

operationsString

private java.lang.String operationsString

stepByStep

private boolean stepByStep

setToBeAdded

private boolean setToBeAdded

painted

private boolean painted

addSetLock

public java.util.concurrent.locks.Lock addSetLock

canAddSet

public java.util.concurrent.locks.Condition canAddSet

canBePainted

public java.util.concurrent.locks.Condition canBePainted

nextStep

public java.util.concurrent.locks.Condition nextStep

controller

public PQRController controller

Constructor Detail

PQRTree

public PQRTree(java.lang.Object[] u)

Creates a universal PQRTree. It's a tree with a PNode with all the elements of the universe set as it's leaves.

Parameters:

u - The universe set. Will be represented as leaves.

PQRTree

public PQRTree(java.lang.Object[] u,
               PQRController controller,
               java.util.concurrent.locks.Lock addSetLock,
               java.util.concurrent.locks.Condition canAddSet,
               java.util.concurrent.locks.Condition canBePainted,
               java.util.concurrent.locks.Condition nextStep)

Creates a universal PQRTree. It's a tree with a PNode with all the elements of the universe set as it's leaves.

Parameters:

u - The universe set. Will be represented as leaves.

controller - Graphics controller.

addSetLock - A lock to works with some conditions.

canAddSet - Condition to adds a set to the tree.

canBePainted - Condition to paints the tree.

nextStep - Condition to executes the next step.

PQRTree

public PQRTree(java.lang.Object[] u,
               int[][] c)

Creates a universal PQRTree. It's a tree with a PNode with all the elements of the universe set as it's leaves. For each set of the collection, it adds the set. It's a online algorithm.

Parameters:

u - The universe set. Will be represented as leaves.

c - The collection. A set of sets.

See Also:

PQRTree(Object[])

Method Detail

run

public void run()

Runs the thread.

Specified by:

run in interface java.lang.Runnable

setConstraints

public void setConstraints(int[] s)

Sets the constraints.

Parameters:

s - The constraints to set.

addSet

public void addSet()

Changes the tree to keep consecutive the elements of the set previously added, if it's possible.

addSet

public void addSet(int[] s)

Changes the tree to keep consecutive the elements of the set s, if it's possible.

Parameters:

s - Set of elements that must to be consecutive.

colorTree

private PQRNode colorTree(int[] s)

Colors black the leaves corresponding to the elements of s, colors black, gray or keeps white the internal nodes, and finds the Least Commons Ancestor.

Parameters:

s - Set of elements that must to be consecutive.

Returns:

The Least Common Ancestor.

reduceTree

private PQRNode reduceTree(PQRNode w)

Repeatedly kills, merge, or uncolors gray nodes, sometimes also creating new nodes when needed, until no gray nodes remain in the tree.

Parameters:

w - Least Common Ancestor

Returns:

The Least Common Ancestor, that can be another node after the reduction.

adjustLCA

private void adjustLCA(PQRNode w)

Adjusts the LCA according to its type. After reduction there are no gray nodes left in the tree. Therefore, all maximal black nodes are children of the LCA.

Parameters:

w - Least Common Ancestor

uncolorTree

private void uncolorTree(int[] s)

Uncolors all black nodes

Parameters:

s - Set of elements that must to be consecutive.

prepareLCA

private void prepareLCA(PQRNode w)

Groups the black children of LCA into a new P node. It's applied when the LCA w is a P node.

Parameters:

w - Least Common Ancestor

preparePNode

private PQRNode preparePNode(PQRNode v)

Groups black children and white children into new P nodes. It's applied to a gray P node child of the LCA.

Parameters:

v - A gray P node, child of the LCA.

Returns:

Updates v node.

changeQIntoR

private void changeQIntoR(PQRNode w)

Changes a Q LCA with black children not consecutive into a R node.

Parameters:

w - Least Common Ancestor of type Q.

changePIntoQ

private void changePIntoQ(PQRNode v)

Changes the type of the node from P to Q. The P node is a gray child of the LCA, with at most one black child and one white child.

Parameters:

v - A gray P node, child of the LCA.

reverseGrayNode

private void reverseGrayNode(PQRNode v)

Reverse a Q gray node, if its children isn't in the right order.

Parameters:

v - Q gray node.

moveChildrenToGrayNode

private PQRNode moveChildrenToGrayNode(PQRNode w,
                                       PQRNode v)

A gray child of the LCA become the ancestor of its black and gray brother nodes.

Parameters:

w - Least Common Ancestor type P with at most one black child

v - A Q node in right order or a R node, gray child of the LCA.

moveChildrenToLCA

private void moveChildrenToLCA(PQRNode w,
                               PQRNode v)

Move the children from a gray node, child of the LCA, to the LCA.

Parameters:

w - Least Common Ancestor type Q, in right order relative to the child v, or type R.

v - Gray node type Q in right order or type R.

frontier

public java.lang.String frontier()

Finds a valid permutation given the collection.

Returns:

A valid permutation.

frontier

private java.lang.String frontier(Node v)

Creates a string representing a valid permutation recursively.

Parameters:

v - Node to be evaluated.

Returns:

The leaves data converted to string.

preOrder

public java.lang.String preOrder()

Represents the PQR tree in pre order way. Displays intern nodes type and leaves data.

Returns:

Representation of the PQR tree.

preOrder

private java.lang.String preOrder(Node v)

Creates a string representing the tree recursively.

Parameters:

v - Node to be evaluated.

Returns:

The nodes hierarchy converted to string.

getLeaves

public java.util.Vector getLeaves()

Gets the leaves of the Tree

Returns:

Leaves

getWidth

public int getWidth()

getHeight

public int getHeight()

prepareToDrawTree

public void prepareToDrawTree()
                       throws java.lang.Exception

Prepares the PQTree to be drawn by the GUI by calculating the width and height needed to draw the tree, and calculated the width and height required to draw each node of the tree.

Throws:

java.lang.Exception

drawTree

public void drawTree(java.awt.Graphics aPen)
              throws java.lang.Exception

Draws the tree to the GUI.

Parameters:

aPen - The pen, graphics object.

Throws:

java.lang.Exception

getLeafAt

public Node getLeafAt(int index)

Returns a leaf node with the specified index relative the the order in which they were originally added when the PQTree was built.

Parameters:

index - The index of leaves vector.

Returns:

The leaf.

getReduceString

public java.lang.String getReduceString()

Gets the reduce string. The leaves that compose the constraint.

Returns:

Reduce string.

getOperationsString

public java.lang.String getOperationsString()

Gets the operations string. All the operantions executed by the tree.

Returns:

Operations string.

setReduceString

public void setReduceString(int[] s)

Sets the reduce string. The leaves that compose the set s.

Parameters:

s - Set to be added to the tree.

isDoneReduction

public boolean isDoneReduction()

Verifies if a reduction is already concluded.

Returns:

true, if the reduction is concluded, or false, if it isn't.

step

public void step()

Signals the controller to paint the tree, and waits for signal to continue with the next step of the reduction.

setLocks

public void setLocks(java.util.concurrent.locks.Lock addSetLock,
                     java.util.concurrent.locks.Condition canAddSet,
                     java.util.concurrent.locks.Condition canBePainted,
                     java.util.concurrent.locks.Condition nextStep)

Sets the lock and conditions to work with the controller.

Parameters:

addSetLock - A lock to works with some conditions.

canAddSet - Condition to adds a set to the tree.

canBePainted - Condition to paints the tree.

nextStep - Condition to executes the next step.

setStep

public void setStep(boolean s)

Sets the tree to reduct completely or by steps.

Parameters:

s - true if reduction should be make step by step, drawing the tree, or false if should do the reduction completely.

setPainted

public void setPainted(boolean p)

Sets the tree to painted or not yet painted.

Parameters:

p - true if the tree was already painted, or false if it wasn't.

reset

public void reset()

Resets the tree to a P-universal.