|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES All Classes | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectpqrtree.PQRTree
public class PQRTree
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.
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 |
---|
private PQRNode root
private Leaf[] leaves
private static final int TYPE_PNODE
private static final int TYPE_QNODE
private static final int TYPE_RNODE
private static final int COLOR_WHITE
private static final int COLOR_GRAY
private static final int COLOR_BLACK
private int[] s
private int drawWidth
private int drawHeight
private boolean hasChanged
private boolean doneReduction
private java.lang.String reduceString
private java.lang.String operationsString
private boolean stepByStep
private boolean setToBeAdded
private boolean painted
public java.util.concurrent.locks.Lock addSetLock
public java.util.concurrent.locks.Condition canAddSet
public java.util.concurrent.locks.Condition canBePainted
public java.util.concurrent.locks.Condition nextStep
public PQRController controller
Constructor Detail |
---|
public PQRTree(java.lang.Object[] u)
u
- The universe set. Will be represented as leaves.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)
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.public PQRTree(java.lang.Object[] u, int[][] c)
u
- The universe set. Will be represented as leaves.c
- The collection. A set of sets.PQRTree(Object[])
Method Detail |
---|
public void run()
run
in interface java.lang.Runnable
public void setConstraints(int[] s)
s
- The constraints to set.public void addSet()
public void addSet(int[] s)
s
, if it's possible.
s
- Set of elements that must to be consecutive.private PQRNode colorTree(int[] s)
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 childv
- 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.
Overview
Package
Class
Use
Tree
Deprecated
Index
Help
PREV CLASS
NEXT CLASS
FRAMES
NO FRAMES
All Classes
SUMMARY: NESTED | FIELD | CONSTR | METHOD
DETAIL: FIELD | CONSTR | METHOD