Changeset 1850 for trunk

Timestamp:

12/23/14 11:24:24 (10 years ago)

Author:

pharms

Message:

• performance improvements
• rename of task instance comparator to task comparator
• prevention of traversing optional in calculating the mergable level of similarity
• checking if similar task at a mergable level of similarity are still well aligned

File:

• trunk/autoquest-core-tasktrees/src/main/java/de/ugoe/cs/autoquest/tasktrees/temporalrelation/utils/SimilarTasks.java (modified) (14 diffs)

trunk/autoquest-core-tasktrees/src/main/java/de/ugoe/cs/autoquest/tasktrees/temporalrelation/utils/SimilarTasks.java

@@ -22 +22 @@
 
 import de.ugoe.cs.autoquest.eventcore.gui.Scroll;
-import de.ugoe.cs.autoquest.tasktrees.temporalrelation.TaskInstanceComparator;
+import de.ugoe.cs.autoquest.tasktrees.temporalrelation.TaskComparator;
 import de.ugoe.cs.autoquest.tasktrees.treeifc.DefaultTaskTraversingVisitor;
 import de.ugoe.cs.autoquest.tasktrees.treeifc.IEventTask;
@@ -28 +28 @@
 import de.ugoe.cs.autoquest.tasktrees.treeifc.IIteration;
 import de.ugoe.cs.autoquest.tasktrees.treeifc.IMarkingTemporalRelationship;
+import de.ugoe.cs.autoquest.tasktrees.treeifc.IOptional;
 import de.ugoe.cs.autoquest.tasktrees.treeifc.ISelection;
+import de.ugoe.cs.autoquest.tasktrees.treeifc.ISequence;
 import de.ugoe.cs.autoquest.tasktrees.treeifc.IStructuringTemporalRelationship;
 import de.ugoe.cs.autoquest.tasktrees.treeifc.ITask;
@@ -52 +54 @@
     
     /**
+     * default indicator for unequal tasks
+     */
+    public static final SimilarTasks UNEQUAL_TASKS = new SimilarTasks(null, null, null);
+    
+    /**
      * result of the string like comparison of both task traversals
      */
@@ -85 +92 @@
      */
     public SimilarTasks(Patch         patch,
-                        ITask         task1,
                         TaskTraversal traversal1,
-                        ITask         task2,
                         TaskTraversal traversal2)
     {
-        this.leftHandSide = task1;
+        if (traversal1 != null) {
+            this.leftHandSide = traversal1.getTask();
+        }
+        
         this.leftHandSideTraversal = traversal1;
-        this.rightHandSide = task2;
+        
+        if (traversal2 != null) {
+            this.rightHandSide = traversal2.getTask();
+        }
+        
         this.rightHandSideTraversal = traversal2;
         
@@ -107 +119 @@
      * static convenience method to compare two tasks
      */
-    public static SimilarTasks compareTasks(ITask                  task1,
-                                            ITask                  task2,
-                                            TaskInstanceComparator comparator)
+    public static SimilarTasks compareTasks(ITask          task1,
+                                            ITask          task2,
+                                            TaskComparator comparator)
     {
-        return compareTasks(task1, task2, comparator, null, true /* never set to false as a common
-                                                                 path may occur several times
-                                                                 at distinct places in a traversal
-                                                                 and once it may be part of a delta
-                                                                 and once not */);
+        return compareTasks(task1, task2, comparator, null);
     }
 
     /**
      * static convenience method to compare two tasks but ignoring a given set of subtasks when
-     * creating the traversals. Furhtermore, it can be defined, if subtasks occurring in both
-     * similar tasks are traversed or not.
-     */
-    public static SimilarTasks compareTasks(ITask                  task1,
-                                            ITask                  task2,
-                                            TaskInstanceComparator comparator,
-                                            List<TaskPath>         pathsNotToTraverse,
-                                            boolean                traverseCommonPaths)
+     * creating the traversals.
+     */
+    public static SimilarTasks compareTasks(ITask          task1,
+                                            ITask          task2,
+                                            TaskComparator comparator,
+                                            List<TaskPath> pathsNotToTraverse)
     {
-        Set<ITask> commonInvolvedTasks;
-
-        if (traverseCommonPaths) {
-            commonInvolvedTasks = new HashSet<ITask>();
-        }
-        else {
-            commonInvolvedTasks = getCommonInvolvedTasks(task1, task2);
-        }
-
-        TaskTraversal traversal1 =
-             TaskTraversal.getTraversal(task1, commonInvolvedTasks, pathsNotToTraverse);
-        
-        TaskTraversal traversal2 =
-             TaskTraversal.getTraversal(task2, commonInvolvedTasks, pathsNotToTraverse);
+        TaskTraversal traversal1 = TaskTraversal.getTraversal(task1, pathsNotToTraverse);
+        TaskTraversal traversal2 = TaskTraversal.getTraversal(task2, pathsNotToTraverse);
 
         if ((traversal1.size() <= 0) || (traversal2.size() <= 0)) {
             return null;
         }
-
+        
+        return compareTraversals(traversal1, traversal2, comparator);
+    }
+
+    /**
+     * <p>
+     * TODO: comment
+     * </p>
+     *
+     * @param traversal1
+     * @param traversal2
+     * @param comparator
+     * @return
+     */
+    public static SimilarTasks compareTraversals(TaskTraversal  traversal1,
+                                                 TaskTraversal  traversal2,
+                                                 TaskComparator comparator)
+    {
         Patch patch = new TaskTraversalMyersDiff(comparator).getDiff(traversal1, traversal2);
 
-        SimilarTasks result = new SimilarTasks(patch, task1, traversal1, task2, traversal2);
+        SimilarTasks result = new SimilarTasks(patch, traversal1, traversal2);
 
         return result;
@@ -161 +172 @@
      * the remaining traversals can be the basis of a merge.
      */
-    public static SimilarTasks getMergableLevelOfSimilarity(SimilarTasks           source,
-                                                            TaskInstanceComparator comparator)
+    public static SimilarTasks getMergableLevelOfSimilarity(SimilarTasks   source,
+                                                            TaskComparator comparator)
     {
         SimilarTasks similarTasks = source;
@@ -175 +186 @@
             similarTasks = compareTasks
                 (similarTasks.getLeftHandSide(), similarTasks.getRightHandSide(),
-                 comparator, pathsToIgnore, true);
-
-            similarTasks.dump(System.out);
+                 comparator, pathsToIgnore);
+
+            // similarTasks.dump(System.out);
             
             List<TaskPath> furtherPathsToIgnore = similarTasks.getPathsToIgnore();
             
-            for (TaskPath path : furtherPathsToIgnore) {
-                System.out.println(path);
-            }
+            // System.out.println("further paths to ignore:");
+            // for (TaskPath path : furtherPathsToIgnore) {
+            //     System.out.println("  " + path);
+            // }
             
             for (TaskPath pathToAdd : furtherPathsToIgnore) {
@@ -201 +213 @@
         while (pathsToIgnore.size() > prevPathsToIgnoreCount);
         
-        return similarTasks;
+        if (similarTasks.isStillWellAligned()) {
+            return similarTasks;
+        }
+        else {
+            // this may happen, if due to interleaving iterations the similarities of the task
+            // move and the diff algorithm does not align them anymore as optimal as possible
+            // because some similarities were lost due to not comparing all paths anymore. 
+            return null;
+        }
     }
 
@@ -242 +262 @@
         
         return deltas.size() > 0;
+    }
+
+    /**
+     * <p>
+     * TODO: comment
+     * </p>
+     *
+     * @return
+     */
+    public boolean isStillWellAligned() {
+        if (isInBetweenDifference()) {
+            return true;
+        }
+        else {
+            for (Delta delta : patch.getDeltas()) {
+                if (delta.getType() == Delta.TYPE.INSERT) {
+                    if ((delta.getOriginal().getPosition() == 0) ||
+                        (delta.getOriginal().getPosition() == leftHandSideTraversal.size()))
+                    {
+                        return false;
+                    }
+                }
+                else if (delta.getType() == Delta.TYPE.DELETE) {
+                    if ((delta.getRevised().getPosition() == 0) ||
+                        (delta.getRevised().getPosition() == rightHandSideTraversal.size()))
+                    {
+                        return false;
+                    }
+                }
+            }
+        }
+        
+        return true;
     }
     
@@ -328 +381 @@
             }
             
+            // check for any parent optional that may be empty and can hence not be flattened
+            TaskPath tmppath = new TaskPath();
+            tmppath.add(leftHandSide, 0);
+            getParentOptionals(tmppath, result);
+            tmppath = new TaskPath();
+            tmppath.add(rightHandSide, 0);
+            getParentOptionals(tmppath, result);
+            
             // check if there are common subtasks on both sides that lie outside any delta and
             // that hence should be ignored (especially when performing flattening of task
-            // instances later with the goal to preserve as many subtasks and respective instances
+            // instances later with the goal to preserve as many subtasks and respective instances)
             int deltaIndex = 0;
             int leftTraversalIndex = 0;
@@ -823 +884 @@
                         (path2.get(j).getTask() instanceof IIteration))
                     {
-                        System.out.println("found paths to real intersecting parents");
-                        int[] indexBuf = leftHandSideTraversal.getIndexesRootedBy(path1Prefix);
-                        System.out.println(idxsPath1[0] + "(" + indexBuf[0] + ")  " + idxsPath1[1] +
-                                           "(" + indexBuf[1] + ")  " + path1Prefix);
-                        indexBuf = rightHandSideTraversal.getIndexesRootedBy(path2Prefix);
-                        System.out.println(idxsPath2[0] + "(" + indexBuf[0] + ")  " + idxsPath2[1] +
-                                           "(" + indexBuf[1] + ")  " + path2Prefix);
+                        // System.out.println("found paths to real intersecting parents");
+                        // int[] indexBuf = leftHandSideTraversal.getIndexesRootedBy(path1Prefix);
+                        // System.out.println(idxsPath1[0] + "(" + indexBuf[0] + ")  " + idxsPath1[1] +
+                        //                    "(" + indexBuf[1] + ")  " + path1Prefix);
+                        // indexBuf = rightHandSideTraversal.getIndexesRootedBy(path2Prefix);
+                        // System.out.println(idxsPath2[0] + "(" + indexBuf[0] + ")  " + idxsPath2[1] +
+                        //                    "(" + indexBuf[1] + ")  " + path2Prefix);
                         
                         paths.add(path1Prefix);
@@ -854 +915 @@
                     if (!commonPath.get(j).equals(comparePath.get(j))) {
                         while (commonPath.size() > j) {
-                            commonPath.remove(j);
+                            commonPath.removeLast();
                         }
                         break;
@@ -957 +1018 @@
                         (indexes[1] < (chunk.getPosition() + chunk.size()))) // ends in the delta
                     {
-                        System.out.println("found path to parent task lieing completely in the " +
-                                           "delta: " + path.subPath(0, i + 1));
+                        // System.out.println("found path to parent task lieing completely in the " +
+                        //                    "delta: " + path.subPath(0, i + 1));
                         result.add(path.subPath(0, i + 1));
                         break;
@@ -964 +1025 @@
                 }
             }
+        }
+    }
+
+    /**
+     *
+     */
+    private void getParentOptionals(TaskPath taskPath, List<TaskPath> result) {
+        ITask task = taskPath.getLast();
+        
+        if (task instanceof IOptional) {
+            result.add(new TaskPath(taskPath));
+        }
+        else if (task instanceof ISequence) {
+            for (int i = 0; i < ((ISequence) task).getChildren().size(); i++) {
+                taskPath.add(((ISequence) task).getChildren().get(i), i);
+                getParentOptionals(taskPath, result);
+                taskPath.removeLast();
+            }
+        }
+        else if (task instanceof ISelection) {
+            for (int i = 0; i < ((ISelection) task).getChildren().size(); i++) {
+                taskPath.add(((ISelection) task).getChildren().get(i), 0);
+                getParentOptionals(taskPath, result);
+                taskPath.removeLast();
+            }
+        }
+        else if (task instanceof IIteration) {
+            taskPath.add(((IIteration) task).getMarkedTask(), 0);
+            getParentOptionals(taskPath, result);
+            taskPath.removeLast();
         }
     }