Index: /trunk/autoquest-core-tasktrees/src/main/java/de/ugoe/cs/autoquest/tasktrees/temporalrelation/utils/SimilarTasks.java =================================================================== --- /trunk/autoquest-core-tasktrees/src/main/java/de/ugoe/cs/autoquest/tasktrees/temporalrelation/utils/SimilarTasks.java (revision 1849) +++ /trunk/autoquest-core-tasktrees/src/main/java/de/ugoe/cs/autoquest/tasktrees/temporalrelation/utils/SimilarTasks.java (revision 1850) @@ -22,5 +22,5 @@ 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,5 +28,7 @@ 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,4 +54,9 @@ /** + * 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,12 +92,17 @@ */ 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,48 +119,47 @@ * 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 pathsNotToTraverse, - boolean traverseCommonPaths) + * creating the traversals. + */ + public static SimilarTasks compareTasks(ITask task1, + ITask task2, + TaskComparator comparator, + List pathsNotToTraverse) { - Set commonInvolvedTasks; - - if (traverseCommonPaths) { - commonInvolvedTasks = new HashSet(); - } - 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); + } + + /** + *

+ * TODO: comment + *

+ * + * @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,6 +172,6 @@ * 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,13 +186,14 @@ similarTasks = compareTasks (similarTasks.getLeftHandSide(), similarTasks.getRightHandSide(), - comparator, pathsToIgnore, true); - - similarTasks.dump(System.out); + comparator, pathsToIgnore); + + // similarTasks.dump(System.out); List 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,5 +213,13 @@ 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,4 +262,37 @@ return deltas.size() > 0; + } + + /** + *

+ * TODO: comment + *

+ * + * @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,7 +381,15 @@ } + // 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,11 +884,11 @@ (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,5 +915,5 @@ if (!commonPath.get(j).equals(comparePath.get(j))) { while (commonPath.size() > j) { - commonPath.remove(j); + commonPath.removeLast(); } break; @@ -957,6 +1018,6 @@ (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,4 +1025,34 @@ } } + } + } + + /** + * + */ + private void getParentOptionals(TaskPath taskPath, List 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(); } }