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

Timestamp:

05/31/15 19:22:54 (9 years ago)

Author:

pharms

Message:

• fixed a bug in the detection of overlapping iterations before merging them.
• now iterations are ignored, if they cause no repetitions in a task to be merged
• the same applies for optionals making hopefully the merge more intuitive and cause less large selections

File:

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

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

@@ -27 +27 @@
 import de.ugoe.cs.autoquest.tasktrees.treeifc.IEventTaskInstance;
 import de.ugoe.cs.autoquest.tasktrees.treeifc.IIteration;
+import de.ugoe.cs.autoquest.tasktrees.treeifc.IIterationInstance;
 import de.ugoe.cs.autoquest.tasktrees.treeifc.IMarkingTemporalRelationship;
-import de.ugoe.cs.autoquest.tasktrees.treeifc.IOptional;
+import de.ugoe.cs.autoquest.tasktrees.treeifc.IOptionalInstance;
 import de.ugoe.cs.autoquest.tasktrees.treeifc.ISelection;
-import de.ugoe.cs.autoquest.tasktrees.treeifc.ISequence;
+import de.ugoe.cs.autoquest.tasktrees.treeifc.ISelectionInstance;
+import de.ugoe.cs.autoquest.tasktrees.treeifc.ISequenceInstance;
 import de.ugoe.cs.autoquest.tasktrees.treeifc.IStructuringTemporalRelationship;
 import de.ugoe.cs.autoquest.tasktrees.treeifc.ITask;
@@ -344 +346 @@
     public List<TaskPath> getPathsToIgnore() {
         List<TaskPath> result = new LinkedList<TaskPath>();
-        Delta singleChangeDelta = null;
         
         if ((patch.getDeltas().size() == 1) &&
             (patch.getDeltas().get(0).getType() == Delta.TYPE.CHANGE))
         {
-            singleChangeDelta = patch.getDeltas().get(0);
-        }
-        
-        // if it is a full change, then the parent of either side must be fully ignored
-        if (singleChangeDelta != null) {
+            // if it is a full change, then the parent of either side must be fully ignored
+            Delta singleChangeDelta = patch.getDeltas().get(0);
+
             if ((singleChangeDelta.getOriginal().getPosition() == 0) &&
                 (singleChangeDelta.getOriginal().size() == leftHandSideTraversal.size()))
@@ -372 +371 @@
         
         if (result.size() < 2) {
-            // if we do not already ignore both root tasks, check for selections and interleaving
-            // iterations that have to be ignored if they belong to a delta
+            // if we do not already ignore both root tasks, check for overlapping
+            // iterations that are executed multiple times for the tasks to be merged as they have
+            // to be ignored
+            result.addAll(getConflictingIterations());
+            
+            // then check for tasks fully inside delta, which can be preserved
             for (Delta delta : patch.getDeltas()) {
-                //getSelections(delta, result);
-                getPathsToRealIntersectingIterations(delta, result);
                 getNotFullyInterleavingIteration(delta, result);
                 getPathsToParentTasksFullyInsideDelta(delta, result);
             }
             
-            // 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 for any parent optional that are at least once empty in instances of the
+            // tasks to be merged and that can, hence, not be flattened
+            getUnexecutedParentOptionals(leftHandSide, result);
+            getUnexecutedParentOptionals(rightHandSide, result);
             
             // check if there are common subtasks on both sides that lie outside any delta and
@@ -839 +837 @@
         }
     }*/
-
-    /**
-     *
-     */
-    @SuppressWarnings("unchecked")
-    private void getPathsToRealIntersectingIterations(Delta delta, List<TaskPath> paths) {
-        TaskPath path1 = getCommonPath((List<TaskPath>) delta.getOriginal().getLines());
-        TaskPath path2 = getCommonPath((List<TaskPath>) delta.getRevised().getLines());
-        
-        // both paths denote those parent tasks that contain the delta.
-        // But there may be parent tasks still contained in the path that are iterations and
-        // that are disjoint with a parent in the other path. Those iterations need to be
-        // considered, as otherwise a created selection would be against the associative law of
-        // iterations. Hence, we search for the topmost iteration on both paths that is disjoint
-        // with a parent node in the respective other path.
-        
-        for (int i = 0; i < path1.size(); i++) {
-            TaskPath path1Prefix = path1.subPath(0, i + 1);
-            int[] idxsPath1 = leftHandSideTraversal.getIndexesRootedBy(path1Prefix);
-            
-            // normalize the indexes to be 0 the index of the delta. Everything left of it
-            // is smaller 0, everything right of it, larger.
-            idxsPath1[0] -= delta.getOriginal().getPosition();
-            idxsPath1[1] -= delta.getOriginal().getPosition() + delta.getOriginal().size() - 1;
-            
-            for (int j = 0; j < path2.size(); j++) {
-                TaskPath path2Prefix = path2.subPath(0, j + 1);
-                int[] idxsPath2 = rightHandSideTraversal.getIndexesRootedBy(path2Prefix);
-                
-                // normalize the indexes to be 0 the index of the delta. Everything left of it
-                // is smaller 0, everything right of it, larger.
-                idxsPath2[0] -= delta.getRevised().getPosition();
-                idxsPath2[1] -=
-                    delta.getRevised().getPosition() + delta.getRevised().size() - 1;
-                
-                // now compare the indexes and check, if the sublists are real subsets of each
-                // other. If not, they only have a real common subset but there is at least one
-                // non shared element on both sides. If so, and one is an iteration, we
-                // have to use it as elements to be selected
-                if (((idxsPath1[0] < idxsPath2[0]) && (idxsPath1[1] < idxsPath2[1])) ||
-                    ((idxsPath1[0] > idxsPath2[0]) && (idxsPath1[1] > idxsPath2[1])))
-                {
-                    if ((path1.get(i).getTask() instanceof IIteration) &&
-                        (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);
+    
+    /**
+     * conflicting iterations are those that belong to either side of the sequence pair, that cover
+     * at least two actions, and that were executed multiple times in the context of the tasks
+     * to be merged. Iterations do only conflict, if there are at least two, one belonging to the
+     * left hand side, and the other to the right hand side. They conflict only, if they cover the
+     * same terminal nodes in the task traversals.
+     */
+    private List<TaskPath> getConflictingIterations() {
+        List<TaskPath> iterationsWithMultipleExecutions = new LinkedList<>();
+        getIterationsWithMultipleExecutions(leftHandSide, iterationsWithMultipleExecutions);
+        
+        if (iterationsWithMultipleExecutions.size() > 0) {
+            // only, if iterations are executed in both side, they are of interest. Hence,
+            // check right hand side only, if left hand side contains repeated iterations.
+            int noOfLeftHandSideRepeatedIterations = iterationsWithMultipleExecutions.size();
+            getIterationsWithMultipleExecutions(rightHandSide, iterationsWithMultipleExecutions);
+            
+            if (iterationsWithMultipleExecutions.size() > noOfLeftHandSideRepeatedIterations) {
+                // also the right hand side contains problematic iterations. Check if they are
+                // overlapping and drop all which are not.
+                dropNonOverlappingIterations(iterationsWithMultipleExecutions);
+            }
+            else {
+                // no conflict, clear the list
+                iterationsWithMultipleExecutions.clear();
+            }
+        }
+        
+        return iterationsWithMultipleExecutions;
+    }
+
+    /**
+     *
+     */
+    private void getIterationsWithMultipleExecutions(ITask          task,
+                                                     List<TaskPath> result)
+    {
+        for (ITaskInstance instance : task.getInstances()) {
+            TaskPath taskPath = new TaskPath();
+            taskPath.add(task, 0);
+            getIterationsWithMultipleExecutions(instance, taskPath, result);
+        }
+    }
+
+    /**
+     *
+     */
+    private void getIterationsWithMultipleExecutions(ITaskInstance  instance,
+                                                     TaskPath       currentPath,
+                                                     List<TaskPath> result)
+    {
+        if (instance instanceof IIterationInstance) {
+            if (((IIterationInstance) instance).size() > 1) {
+                // iteration executed multiple times --> store path
+                result.add(currentPath.subPath(0, currentPath.size())); // ensure to create a copy
+            }
+            
+            currentPath.add(((IIteration) instance.getTask()).getMarkedTask(), 0);
+            
+            for (ITaskInstance child : (IIterationInstance) instance) {
+                getIterationsWithMultipleExecutions(child, currentPath, result);
+            }
+            
+            currentPath.removeLast();
+        }
+        else if (instance instanceof ISequenceInstance) {
+            int index = 0;
+            for (ITaskInstance child : (ISequenceInstance) instance) {
+                currentPath.add(child.getTask(), index++);
+                getIterationsWithMultipleExecutions(child, currentPath, result);
+                currentPath.removeLast();
+            }
+        }
+        else if (instance instanceof ISelectionInstance) {
+            ITaskInstance child = ((ISelectionInstance) instance).getChild();
+            currentPath.add(child.getTask(), 0);
+            getIterationsWithMultipleExecutions(child, currentPath, result);
+            currentPath.removeLast();
+        }
+        else if (instance instanceof IOptionalInstance) {
+            ITaskInstance child = ((IOptionalInstance) instance).getChild();
+            if (child != null) {
+                currentPath.add(child.getTask(), 0);
+                getIterationsWithMultipleExecutions(child, currentPath, result);
+                currentPath.removeLast();
+            }
+        }
+    }
+
+    /**
+     *
+     */
+    private void dropNonOverlappingIterations(List<TaskPath> iterationsWithMultipleExecutions) {
+        // to check overlappings, iterate the iterations. Then check for each the indexes it covers
+        // in its respective traversal. Adapt the indexes depending on deltas that an iteration
+        // covers. Then check all other iterations. Consider also here the indexes in the traversal.
+        // also here, the indexes must be adapted in case of covered deltas.
+        List<TaskPath> overlappingIterations = new LinkedList<TaskPath>();
+        
+        for (TaskPath leftPath : iterationsWithMultipleExecutions) {
+            if (leftPath.getTask(0).equals(leftHandSide)) {
+                int[] leftIdxs = leftHandSideTraversal.getIndexesRootedBy(leftPath);
+                
+                for (TaskPath rightPath : iterationsWithMultipleExecutions) {
+                    if (rightPath.getTask(0).equals(rightHandSide)) {
+                        int[] rightIdxs = rightHandSideTraversal.getIndexesRootedBy(rightPath);
                         
-                        paths.add(path1Prefix);
-                        paths.add(path2Prefix);
-                        return;
-                    }
-                }
-            }
-        }
+                        adaptIndexesBasedOnDeltas(leftIdxs, rightIdxs, patch.getDeltas());
+                        
+                        if (((leftIdxs[0] < rightIdxs[0]) && (rightIdxs[0] <= leftIdxs[1])) ||
+                            ((rightIdxs[0] < leftIdxs[0]) && (leftIdxs[0] <= rightIdxs[1])))
+                        {
+                            overlappingIterations.add(leftPath);
+                            overlappingIterations.add(rightPath);
+                        }
+                    }
+                }
+            }
+        }
+        
+        iterationsWithMultipleExecutions.retainAll(overlappingIterations);
+    }
+
+    /**
+     *
+     */
+    private void adaptIndexesBasedOnDeltas(int[]       originalIndexes,
+                                           int[]       revisedIndexes,
+                                           List<Delta> deltas)
+    {
+        int originalStartUpdate = 0;
+        int originalEndUpdate = 0;
+        int revisedStartUpdate = 0;
+        int revisedEndUpdate = 0;
+        
+        for (Delta delta : deltas) {
+            if (delta.getOriginal().getPosition() < originalIndexes[0]) {
+                originalStartUpdate += delta.getRevised().size();
+            }
+            if (delta.getOriginal().getPosition() < originalIndexes[1]) {
+                originalEndUpdate += delta.getRevised().size();
+            }
+            if (delta.getRevised().getPosition() < revisedIndexes[0]) {
+                revisedStartUpdate += delta.getOriginal().size();
+            }
+            if (delta.getRevised().getPosition() < revisedIndexes[1]) {
+                revisedEndUpdate += delta.getOriginal().size();
+            }
+        }
+        
+        originalIndexes[0] += originalStartUpdate;
+        originalIndexes[1] += originalEndUpdate;
+        revisedIndexes[0] += revisedStartUpdate;
+        revisedIndexes[1] += revisedEndUpdate;
     }
 
@@ -939 +1032 @@
     /**
      * If a chunk has a minimum number of 2 entries and at least one of them belongs to an iteration
-     * the does not cover the other and also expands to preceding or succeeding paths in the
-     * traversal, we can no merge the situation.
+     * that does not cover the other and also expands to preceding or succeeding paths in the
+     * traversal, we can not merge the situation.
      */
     private void getNotFullyInterleavingIterations(Chunk          chunk,
@@ -1031 +1124 @@
      *
      */
-    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();
+    private void getUnexecutedParentOptionals(ITask          task,
+                                              List<TaskPath> result)
+    {
+        for (ITaskInstance instance : task.getInstances()) {
+            TaskPath taskPath = new TaskPath();
+            taskPath.add(task, 0);
+            getUnexecutedParentOptionals(instance, taskPath, result);
+        }
+    }
+    
+    /**
+     *
+     */
+    private void getUnexecutedParentOptionals(ITaskInstance  instance,
+                                              TaskPath       currentPath,
+                                              List<TaskPath> result)
+    {
+        if (instance instanceof IOptionalInstance) {
+            ITaskInstance child = ((IOptionalInstance) instance).getChild();
+            if (child != null) {
+                currentPath.add(child.getTask(), 0);
+                getUnexecutedParentOptionals(child, currentPath, result);
+                currentPath.removeLast();
+            }
+            else {
+                result.add(currentPath.subPath(0, currentPath.size())); // ensure to create a copy
+            }
+        }
+        else if (instance instanceof IIterationInstance) {
+            currentPath.add(((IIteration) instance.getTask()).getMarkedTask(), 0);
+            
+            for (ITaskInstance child : (IIterationInstance) instance) {
+                getUnexecutedParentOptionals(child, currentPath, result);
+            }
+            
+            currentPath.removeLast();
+        }
+        else if (instance instanceof ISequenceInstance) {
+            int index = 0;
+            for (ITaskInstance child : (ISequenceInstance) instance) {
+                currentPath.add(child.getTask(), index++);
+                getUnexecutedParentOptionals(child, currentPath, result);
+                currentPath.removeLast();
+            }
+        }
+        else if (instance instanceof ISelectionInstance) {
+            ITaskInstance child = ((ISelectionInstance) instance).getChild();
+            currentPath.add(child.getTask(), 0);
+            getUnexecutedParentOptionals(child, currentPath, result);
+            currentPath.removeLast();
         }
     }