pqrtree
Class PQRTree

java.lang.Object
  extended by 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.