edu.wpi.cs.dsrg.xmldb.xat.component.xatrewrite
Class ReWriteTraversal

java.lang.Object
  |
  +--edu.wpi.cs.dsrg.xmldb.xat.common.operator.XATPropertiesImp
        |
        +--edu.wpi.cs.dsrg.xmldb.xat.common.operator.XATQueryObjectImp
              |
              +--edu.wpi.cs.dsrg.xmldb.xat.component.xatrewrite.ReWriteTraversal
Direct Known Subclasses:
CancelOutTraversal

public class ReWriteTraversal
extends XATQueryObjectImp

 ReWriteTraversal is the traversal strategy used in the rewrite steps
 It is responsible for iterating over an XAT algebra tree and finding 2 nodes
 to evaluate equivalence rules on.  

 The class is instantiated by passing in an XATTree to traverse, a ReWriteRules object that
 will be used to evaluate the rules and a Vector containing names (strings) 
 of XATOperators (fully quantified) to rewrite. doPushDown is then called with a direction
 to rewrite rules.  
 
 The types of XATOperators to evaluate are determined before starting the traversal.  A Vector
  is passed into the constructor
 This reWriteOrder vector also determines the order of operators to evaluate.

 The traversal starts by iterating over the tree and finding all Source operators.  Then, starting with
 the first operator, travels up the tree until the first XATOperator (x1) whose type corresponds to the 
 first class name in the reWriteOrder Vector is found. Operators who are in their final
 position are not used.  Next,depending on the direction the user
 wishes to rewrite rules, the system will either take the parent or child of x1.  A call is then
 made to ReWriteRules.evaluateRules passing in the 2 operators.  

 Once the rule is evaluted for 2 nodes, the ReWriteResult object is interpreted and 
 If the operator is in its finalPosition (from the result object), the hashtable that keeps track
 of which operators have completed evaluation is updated and the next Operator is found.  If the
 operator is not in its final position, the new child or parent (depending on direction) is used
 to evalute another rule.

 The process continues until all operators are in their final position.  
 

Since:
1.0
See Also:
ReWriteResult, XATNode, XATOperator, XATTree, Serialized Form

Field Summary
static int DOWN
          Constant to rewrite rules downward.
protected  java.util.Hashtable reWriteList
           The HashTabe stores the list of operators in the tree and whether they are in their final position or not.
protected  java.util.Vector reWriteOrder
          List of Strings representing the order and name of XATOperators to rewrite.
protected  XATTree reWriteTree
          The XATTree to rewrite
protected  ReWriteRules rules
          Contains the equivalence rules
protected  boolean stepThrough
          Out put the tree after each rewrtie step or not.
protected  java.util.Vector stepTrees
          The tree in current rewrite step.
static int UP
          Constant to rewrite rules upward.
 
Fields inherited from class edu.wpi.cs.dsrg.xmldb.xat.common.operator.XATQueryObjectImp
stats, statsPresent
 
Constructor Summary
ReWriteTraversal(XATTree tree, ReWriteRules p1, java.util.Vector order)
          ReWriteTraversal constructor.
ReWriteTraversal(XATTree tree, ReWriteRules p1, java.util.Vector order, boolean step)
          ReWriteTraversal constructor.
 
Method Summary
 XATTree doPushdown(int direction)
           This method uses the XATtree passed into the constructor, and traverses over the tree and finds 2 nodes to try to swap.
 XATTree doRewrite(int direction)
          This method repeatly call doPushdown until there is no more changes in the Pushdown.
protected  XATNode findNextNode(XATNode paramNode, java.lang.String toMatch)
           Accepts an XATNode paramNode and an XATOperator.
protected  XATNode findNextNode(XATTree tree, XATNode paramNode, java.lang.String toMatch)
          Find next node need to be pushed down.
protected  void getAllSourceNodes(java.util.Vector sourceSet, XATNode root, XATTree tree)
          Find all of the Source operators in an XATTree.
protected  void getChildren(java.util.Vector destinationVector, XATNode root)
          getChildren accepts a destination Vector and an XATNode it then puts all of the root's children into this vector
 java.util.Vector getStepTrees()
          Get the tree in current rewrite step.
 boolean isDebug()
          Get the value of the propertity 'DEBUG_ReWriteTraversal'.
 boolean isIsChanged()
          Get the value of the propertity 'isChanged'.
protected  boolean isPushedDown(XATOperator toCheck)
          Check if an operator need any push down or not.
 boolean isStepThrough()
          Get the value of the propertity 'StepThrough'.
 void setDebug(boolean newDebug)
          I temporarily keep this method.
protected  void setDefaultProperties()
          This method will be called by the constructor.
 void setIsChanged(boolean newIsChanged)
          Get the value of the propertity 'isChanged'.
protected  void setPushedDown(XATOperator toSet, boolean val)
          Modifies this operators value in the reWriteList according to the val parameter.
 void setStepTrees(java.util.Vector newStepTrees)
          Get the tree in current rewrite step.
 
Methods inherited from class edu.wpi.cs.dsrg.xmldb.xat.common.operator.XATQueryObjectImp
addStatistic, compareTo, getStatistics, isValidStatistic, setDefaultStatistics
 
Methods inherited from class edu.wpi.cs.dsrg.xmldb.xat.common.operator.XATPropertiesImp
addProperty, getProperties, getProperty, isValidPropertyName, setNewPropertyValue, setProperty
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

reWriteTree

protected XATTree reWriteTree
The XATTree to rewrite
Since:
1.0

reWriteList

protected java.util.Hashtable reWriteList
 The HashTabe stores the list of operators in the tree and whether they
 are in their final position or not. 
 The key is the operator, the value is a Boolean that represents whether the operator
 is in its final position.  
 
Since:
1.0

rules

protected ReWriteRules rules
Contains the equivalence rules
Since:
1.0

reWriteOrder

protected java.util.Vector reWriteOrder
List of Strings representing the order and name of XATOperators to rewrite.
Since:
1.0

DOWN

public static final int DOWN
Constant to rewrite rules downward.
Since:
1.0

UP

public static final int UP
Constant to rewrite rules upward.
Since:
1.0

stepThrough

protected boolean stepThrough
Out put the tree after each rewrtie step or not.
Since:
1.0

stepTrees

protected java.util.Vector stepTrees
The tree in current rewrite step.
Since:
1.0
Constructor Detail

ReWriteTraversal

public ReWriteTraversal(XATTree tree,
                        ReWriteRules p1,
                        java.util.Vector order)
ReWriteTraversal constructor.
Parameters:
tree - The tree to rewrite.
p1 - The class contains equivalance rules.
order - The vector contains strings of the types of operators to optimize.
Since:
1.0
See Also:
ReWriteRules, XATTree

ReWriteTraversal

public ReWriteTraversal(XATTree tree,
                        ReWriteRules p1,
                        java.util.Vector order,
                        boolean step)
ReWriteTraversal constructor. This method is specificly used in GUI.
Parameters:
tree - The tree to rewrite.
p1 - The class contains equivalance rules.
order - The vector contains strings of the types of operators to optimize.
step - Identify if the ShowTreeCheckBox is selected or not.
Since:
1.0
See Also:
ReWriteRules, XATTree
Method Detail

doPushdown

public XATTree doPushdown(int direction)
 This method uses the XATtree passed into the constructor, and 
 traverses over the tree and finds 2 nodes to try to swap.  
 The types and order of operators to pushDown are defined in the 
 constructor. 
 
Parameters:
direction - The direction to push nodes.
Returns:
XATTree The result XAT tree after pushDown.
Since:
1.0
See Also:
XATTree, ReWriteResult, XATOperator

doRewrite

public XATTree doRewrite(int direction)
This method repeatly call doPushdown until there is no more changes in the Pushdown. Assume the this.rewriteTree never used again.
Parameters:
direction - The direction of rewrite.
Returns:
The XATTree after rewrite.
Since:
1.0
See Also:
XATTree

findNextNode

protected XATNode findNextNode(XATTree tree,
                               XATNode paramNode,
                               java.lang.String toMatch)
Find next node need to be pushed down.
 This method will traverse the tree, starting from paramNode and 
 ending as it finds a node of type that has not been pushedDown. 
 This node is then returned. If no such node is found, it returns null.
 
Parameters:
paramNode - The node to start looking from.
toMatch - The type of operator to match.
Returns:
XATNode The first match that has not been pushed down.
Since:
1.0
See Also:
XATNode

findNextNode

protected XATNode findNextNode(XATNode paramNode,
                               java.lang.String toMatch)
 Accepts an XATNode paramNode and an XATOperator. 
 The tree is traversed starting at paramNode and ends when it finds 
 a node of type type that has not been pushedDown.  This node is then returned
 If no such node is found, it returns null
 
Parameters:
paramNode - The node to start looking from.
toMatch - The type of operator to match.
Returns:
XATNode The first match that has not been pushed down.
Since:
1.0
See Also:
XATNode

getAllSourceNodes

protected void getAllSourceNodes(java.util.Vector sourceSet,
                                 XATNode root,
                                 XATTree tree)
Find all of the Source operators in an XATTree.
 This method first look at all of the root's children and adds them to the vector
 if that nodes' operator is an XML source .  The function is then
 recurvsively called on each of root's children until there are no more nodes to look at.  
 
Parameters:
sourceSet - stores all of the Source operators found
root - The root of a tree to iterate over
Returns:
void
Since:
1.0
See Also:
XATTree, XATNode

getChildren

protected void getChildren(java.util.Vector destinationVector,
                           XATNode root)
getChildren accepts a destination Vector and an XATNode it then puts all of the root's children into this vector
Parameters:
destinationVector -  
root -  
Returns:
void
Since:
1.0
See Also:
XATNode

getStepTrees

public java.util.Vector getStepTrees()
Get the tree in current rewrite step.
Returns:
java.util.Vector
Since:
1.0

isDebug

public boolean isDebug()
Get the value of the propertity 'DEBUG_ReWriteTraversal'.
Returns:
boolean True: With debug information. False: No debug information.
Since:
1.0

isIsChanged

public boolean isIsChanged()
Get the value of the propertity 'isChanged'.
Returns:
boolean True: The tree has been changed. False: No change at all.
Since:
1.0

isPushedDown

protected boolean isPushedDown(XATOperator toCheck)
Check if an operator need any push down or not. This method will look at the reWriteList and return whether the operator is in its final position of not.
 If the operator does not appear in the list, the operator is added
 and the value is set to false
 
Parameters:
toCheck - The XATOperator to look up in the reWriteList.
Returns:
boolean True: if the operator is in its final position. False: otherwise.
Since:
1.0
See Also:
XATOperator

isStepThrough

public boolean isStepThrough()
Get the value of the propertity 'StepThrough'.
Returns:
boolean True: Out put the tree after each rewrtie step. False: No debug information.
Since:
1.0

setDebug

public void setDebug(boolean newDebug)
I temporarily keep this method. But it should be deprecated! Using System.getProperty("DEBUG_ReWriteTraversal") instead. Creation date: (8/23/2002 4:56:17 PM)
Parameters:
newDebug - boolean

setDefaultProperties

protected void setDefaultProperties()
This method will be called by the constructor. It will set the default properties that the ALL query objects will support. Each subclass should override this method and add their own unique properties, but should also call super.setDefaultProperties() so that the common properties may be set.
Overrides:
setDefaultProperties in class XATQueryObjectImp
Returns:
void
Since:
1.0

setIsChanged

public void setIsChanged(boolean newIsChanged)
Get the value of the propertity 'isChanged'.
Parameters:
newIsChanged - True: The tree is changed. False: otherwise.
Returns:
boolean True: The tree has been changed. False: No change at all.
Since:
1.0

setPushedDown

protected void setPushedDown(XATOperator toSet,
                             boolean val)
Modifies this operators value in the reWriteList according to the val parameter. This is used after a rule has been evaluated and the result specifies that the operator is now in its final position
Parameters:
toSet - The XATOperator to set final position.
val - True: if the operator is now in its final position. False: otherwise.
Returns:
void
Since:
1.0

setStepTrees

public void setStepTrees(java.util.Vector newStepTrees)
Get the tree in current rewrite step.
Parameters:
newStepTrees - java.util.Vector
Returns:
void
Since:
1.0