Changeset 1125 for trunk/autoquest-core-tasktrees/src/main/java/de/ugoe/cs/autoquest/tasktrees/nodeequality/SelectionComparisonRule.java

Timestamp:

03/18/13 11:46:47 (11 years ago)

Author:

pharms

Message:

• refactoring of task tree node comparison to be able to optimize the comparisons for the different comparison levels lexically, syntactically, semantically

File:

• trunk/autoquest-core-tasktrees/src/main/java/de/ugoe/cs/autoquest/tasktrees/nodeequality/SelectionComparisonRule.java (modified) (3 diffs)

trunk/autoquest-core-tasktrees/src/main/java/de/ugoe/cs/autoquest/tasktrees/nodeequality/SelectionComparisonRule.java

@@ -14 +14 @@
 
 package de.ugoe.cs.autoquest.tasktrees.nodeequality;
+
+import java.util.List;
 
 import de.ugoe.cs.autoquest.tasktrees.treeifc.ISelection;
@@ -51 +53 @@
     }
 
-    /*
-     * (non-Javadoc)
+    /* (non-Javadoc)
+     * @see NodeComparisonRule#isApplicable(ITaskTreeNode, ITaskTreeNode)
+     */
+    @Override
+    public boolean isApplicable(ITaskTreeNode node1, ITaskTreeNode node2) {
+        return (node1 instanceof ISelection) && (node2 instanceof ISelection);
+    }
+
+    /* (non-Javadoc)
+     * @see NodeComparisonRule#areLexicallyEqual(ITaskTreeNode, ITaskTreeNode)
+     */
+    @Override
+    public boolean areLexicallyEqual(ITaskTreeNode node1, ITaskTreeNode node2) {
+        NodeEquality equality = getEquality(node1, node2, NodeEquality.LEXICALLY_EQUAL);
+        return (equality != null) && (equality.isAtLeast(NodeEquality.LEXICALLY_EQUAL));
+    }
+
+    /* (non-Javadoc)
+     * @see NodeComparisonRule#areSyntacticallyEqual(ITaskTreeNode, ITaskTreeNode)
+     */
+    @Override
+    public boolean areSyntacticallyEqual(ITaskTreeNode node1, ITaskTreeNode node2) {
+        NodeEquality equality = getEquality(node1, node2, NodeEquality.SYNTACTICALLY_EQUAL);
+        return (equality != null) && (equality.isAtLeast(NodeEquality.SYNTACTICALLY_EQUAL));
+    }
+
+    /* (non-Javadoc)
+     * @see NodeComparisonRule#areSemanticallyEqual(ITaskTreeNode, ITaskTreeNode)
+     */
+    @Override
+    public boolean areSemanticallyEqual(ITaskTreeNode node1, ITaskTreeNode node2) {
+        NodeEquality equality = getEquality(node1, node2, NodeEquality.SEMANTICALLY_EQUAL);
+        return (equality != null) && (equality.isAtLeast(NodeEquality.SEMANTICALLY_EQUAL));
+    }
+
+    /* (non-Javadoc)
+     * @see NodeComparisonRule#compare(ITaskTreeNode, ITaskTreeNode)
+     */
+    @Override
+    public NodeEquality compare(ITaskTreeNode node1, ITaskTreeNode node2) {
+        return getEquality(node1, node2, null);
+    }
+
+    /**
      * 
-     * @see de.ugoe.cs.tasktree.nodeequality.NodeEqualityRule#apply(TaskTreeNode, TaskTreeNode)
-     */
-    @Override
-    public NodeEquality compare(ITaskTreeNode node1, ITaskTreeNode node2) {
-        if ((!(node1 instanceof ISelection)) || (!(node2 instanceof ISelection))) {
-            return null;
-        }
-
-        if (node1 == node2) {
-            return NodeEquality.IDENTICAL;
-        }
-
-        // if both sequences do not have children, they are identical. If only one of them has
-        // children, they are unequal.
-        if ((node1.getChildren().size() == 0) && (node2.getChildren().size() == 0)) {
+     */
+    private NodeEquality getEquality(ITaskTreeNode node1,
+                                     ITaskTreeNode node2,
+                                     NodeEquality  requiredEqualityLevel)
+    {
+        List<ITaskTreeNode> children1 = node1.getChildren();
+        List<ITaskTreeNode> children2 = node2.getChildren();
+
+        // if both selections do not have children, they are lexically equal. If only one of them
+        // has children, they are unequal.
+        if ((children1.size() == 0) && (children2.size() == 0)) {
             return NodeEquality.LEXICALLY_EQUAL;
         }
-        else if ((node1.getChildren().size() == 0) || (node2.getChildren().size() == 0)) {
+        else if ((children1.size() == 0) || (children2.size() == 0)) {
             return NodeEquality.UNEQUAL;
         }
 
-        NodeEquality selectionEquality = NodeEquality.LEXICALLY_EQUAL;
-
-        // compare each child of selection one with each child of selection two
+        NodeEquality selectionEquality;
+
+        if (requiredEqualityLevel == null) {
+            // calculate the common equality level for all children of both selections.
+            // do it in both directions to ensure commutative comparison
+            selectionEquality = getCommonEqualityLevel(children1, children2);
+            if (selectionEquality != NodeEquality.UNEQUAL) {
+                return selectionEquality.getCommonDenominator
+                    (getCommonEqualityLevel(children2, children1));
+            }
+            else {
+                return NodeEquality.UNEQUAL;
+            }
+        }
+        else {
+            // we are searching for a specific equality
+            if (checkEqualityLevel(children1, children2, requiredEqualityLevel) &&
+                checkEqualityLevel(children2, children1, requiredEqualityLevel))
+            {
+                return requiredEqualityLevel;
+            }
+            else {
+                return NodeEquality.UNEQUAL;
+            }
+        }
+    }
+
+    /**
+     * <p>
+     * TODO: comment
+     * </p>
+     *
+     * @param children1
+     * @param children2
+     * @param requiredEqualityLevel
+     */
+    private NodeEquality getCommonEqualityLevel(List<ITaskTreeNode> children1,
+                                                List<ITaskTreeNode> children2)
+    {
+        NodeEquality listEquality = NodeEquality.LEXICALLY_EQUAL;
+        
         NodeEquality childEquality;
         NodeEquality currentEquality;
-        for (ITaskTreeNode child1 : node1.getChildren()) {
+        for (ITaskTreeNode child1 : children1) {
             childEquality = null;
-            for (ITaskTreeNode child2 : node2.getChildren()) {
-                currentEquality = mRuleManager.applyRules(child1, child2);
+            for (ITaskTreeNode child2 : children2) {
+                currentEquality = callRuleManager(child1, child2, null);
                 if ((currentEquality != null) && (currentEquality != NodeEquality.UNEQUAL)) {
                     if (childEquality == null) {
@@ -91 +169 @@
                         childEquality = childEquality.getCommonDenominator(currentEquality);
                     }
-                }
-            }
-            
-            if (childEquality != null) {
-                selectionEquality = selectionEquality.getCommonDenominator(childEquality);
-            }
-            else {
-                return NodeEquality.UNEQUAL;
-            }
-        }
-
-        // compare each child of selection two with each child of selection one
-        for (ITaskTreeNode child2 : node2.getChildren()) {
-            childEquality = null;
-            for (ITaskTreeNode child1 : node1.getChildren()) {
-                currentEquality = mRuleManager.applyRules(child1, child2);
-                if ((currentEquality != null) && (currentEquality != NodeEquality.UNEQUAL)) {
-                    if (childEquality == null) {
-                        childEquality = currentEquality;
-                    }
-                    else {
-                        childEquality = childEquality.getCommonDenominator(currentEquality);
+                    
+                    if (childEquality == NodeEquality.SEMANTICALLY_EQUAL) {
+                        // as we calculate only the common denominator, we can break up here for
+                        // the current child. We will not improve the denominator anymore
+                        break;
                     }
                 }
             }
             
-            if (childEquality != null) {
-                selectionEquality = selectionEquality.getCommonDenominator(childEquality);
+            if (childEquality == null) {
+                // we did not find any child in the second list, that is equal to the searched
+                // child
+                return NodeEquality.UNEQUAL;
             }
             else {
-                return NodeEquality.UNEQUAL;
-            }
-        }
-
-        return selectionEquality;
+                listEquality = listEquality.getCommonDenominator(childEquality);
+            }
+        }
+
+        return listEquality;
+    }
+
+    /**
+     * <p>
+     * TODO: comment
+     * </p>
+     *
+     * @param children1
+     * @param children2
+     * @param requiredEqualityLevel
+     */
+    private boolean checkEqualityLevel(List<ITaskTreeNode> children1,
+                                       List<ITaskTreeNode> children2,
+                                       NodeEquality        requiredEqualityLevel)
+    {
+        NodeEquality childEquality;
+        NodeEquality currentEquality;
+        for (ITaskTreeNode child1 : children1) {
+            childEquality = null;
+            for (ITaskTreeNode child2 : children2) {
+                currentEquality = callRuleManager(child1, child2, requiredEqualityLevel);
+                if ((currentEquality != null) && (currentEquality.isAtLeast(requiredEqualityLevel)))
+                {
+                    // we found at least one equal child with sufficient equality in the
+                    // second list. So be can break up for this child.
+                    childEquality = currentEquality;
+                    break;
+                }
+            }
+            
+            if (childEquality == null) {
+                // we did not find any child in the second list, that is equal to the searched
+                // child
+                return false;
+            }
+        }
+
+        // for all children, we found an equality 
+        return true;
+    }
+
+    /**
+     * <p>
+     * TODO: comment
+     * </p>
+     *
+     * @param child1
+     * @param child2
+     * @param requiredEqualityLevel
+     * @return
+     */
+    private NodeEquality callRuleManager(ITaskTreeNode child1,
+                                         ITaskTreeNode child2,
+                                         NodeEquality  requiredEqualityLevel)
+    {
+        if (requiredEqualityLevel == null) {
+            return mRuleManager.compare(child1, child2);
+        }
+        else if (mRuleManager.areAtLeastEqual(child1, child2, requiredEqualityLevel)) {
+            return requiredEqualityLevel;
+        }
+        else {
+            return NodeEquality.UNEQUAL;
+        }
     }