pqrtree
Class PQRTree

java.lang.Object
  pqrtree.PQRTree

public class PQRTree
extends java.lang.Object

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

private static int	COLOR_BLACK
private static int	COLOR_GRAY
private static int	COLOR_WHITE
private Leaf[]	leaves
private PQRNode	root
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.

Method Summary

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.
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.
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.
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.
private void	reverseGrayNode(PQRNode v) Reverse a Q gray node, if its children isn't in the right order.
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

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,
               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

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.