// Copyright 2012 Georg-August-Universität Göttingen, Germany
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
package de.ugoe.cs.autoquest.tasktrees.temporalrelation.utils;
import java.io.PrintStream;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;
import de.ugoe.cs.autoquest.eventcore.gui.Scroll;
import de.ugoe.cs.autoquest.tasktrees.temporalrelation.TaskComparator;
import de.ugoe.cs.autoquest.tasktrees.treeifc.DefaultTaskTraversingVisitor;
import de.ugoe.cs.autoquest.tasktrees.treeifc.IEventTask;
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.IOptionalInstance;
import de.ugoe.cs.autoquest.tasktrees.treeifc.ISelection;
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;
import de.ugoe.cs.autoquest.tasktrees.treeifc.ITaskInstance;
import de.ugoe.cs.autoquest.tasktrees.treeifc.ITemporalRelationship;
import de.ugoe.cs.autoquest.tasktrees.treeifc.TaskPath;
import difflib.Chunk;
import difflib.Delta;
import difflib.Patch;
/**
*
* This class represents a pair of tasks and their corresponding similarity level, respectively,
* their diff level. In addition, it contains the task traversal, i.e., the flattened variants
* of the compared tasks. It provides static methods to compare two tasks and get an object of this
* class as result. Furthermore, it allows to adapt the contained traversals so that unmergable
* subtasks are not traversed.
*
*
* @author Patrick Harms
*/
public class SimilarTasks {
/**
* 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
*/
private Patch patch;
/**
* the diff level resulting from the comparison
*/
private int diffLevel;
/**
* the first compared task
*/
private ITask leftHandSide;
/**
* the second compare task
*/
private ITask rightHandSide;
/**
* the traversal of the first task
*/
private TaskTraversal leftHandSideTraversal;
/**
* the traversal of the second task
*/
private TaskTraversal rightHandSideTraversal;
/**
* initialized a pair of tasks and calculates its diff level
*/
public SimilarTasks(Patch patch,
TaskTraversal traversal1,
TaskTraversal traversal2)
{
if (traversal1 != null) {
this.leftHandSide = traversal1.getTask();
}
this.leftHandSideTraversal = traversal1;
if (traversal2 != null) {
this.rightHandSide = traversal2.getTask();
}
this.rightHandSideTraversal = traversal2;
if (patch != null) {
this.patch = patch;
this.diffLevel = getDiffLevel(patch, traversal1, traversal2);
}
else {
this.diffLevel = 100;
}
}
/**
* static convenience method to compare two tasks
*/
public static SimilarTasks compareTasks(ITask task1,
ITask task2,
TaskComparator comparator)
{
return compareTasks(task1, task2, comparator, null);
}
/**
* static convenience method to compare two tasks but ignoring a given set of subtasks when
* creating the traversals.
*/
public static SimilarTasks compareTasks(ITask task1,
ITask task2,
TaskComparator comparator,
List 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, traversal1, traversal2);
return result;
}
/**
* This method checks for mergability of the provided similar tasks and if this is not given,
* it reduces the traversals by ignoring interleaving iterations and other situations until
* the remaining traversals can be the basis of a merge.
*/
public static SimilarTasks getMergableLevelOfSimilarity(SimilarTasks source,
TaskComparator comparator)
{
SimilarTasks similarTasks = source;
List pathsToIgnore = similarTasks.getPathsToIgnore();
int prevPathsToIgnoreCount = 0;
do {
prevPathsToIgnoreCount = pathsToIgnore.size();
similarTasks = compareTasks
(similarTasks.getLeftHandSide(), similarTasks.getRightHandSide(),
comparator, pathsToIgnore);
// similarTasks.dump(System.out);
List furtherPathsToIgnore = similarTasks.getPathsToIgnore();
// System.out.println("further paths to ignore:");
// for (TaskPath path : furtherPathsToIgnore) {
// System.out.println(" " + path);
// }
for (TaskPath pathToAdd : furtherPathsToIgnore) {
boolean found = false;
for (TaskPath pathToIgnore : pathsToIgnore) {
if (pathToAdd.equals(pathToIgnore)) {
found = true;
break;
}
}
if (!found) {
pathsToIgnore.add(pathToAdd);
}
}
}
while (pathsToIgnore.size() > prevPathsToIgnoreCount);
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;
}
}
/**
* checks if the delta between the two traversals is at their border or not
*/
public boolean isInBetweenDifference() {
List deltas = patch.getDeltas();
for (Delta delta : deltas) {
int origPos = delta.getOriginal().getPosition();
int origSize = delta.getOriginal().size();
int revPos = delta.getRevised().getPosition();
int revSize = delta.getRevised().size();
if ((origPos <= 0) || (revPos <= 0)) {
// optional must not be the beginning of the task
return false;
}
else if ((delta.getType() == Delta.TYPE.INSERT) &&
((revPos + revSize) >= rightHandSideTraversal.size()))
{
// optional must not be the end of the right hand side task
return false;
}
else if ((delta.getType() == Delta.TYPE.DELETE) &&
((origPos + origSize) >= leftHandSideTraversal.size()))
{
// optional must not be the end of the left hand side task
return false;
}
else if ((delta.getType() == Delta.TYPE.CHANGE) &&
(((revPos + revSize) >= rightHandSideTraversal.size()) ||
((origPos + origSize) >= leftHandSideTraversal.size())))
{
// selection must not be the end of the left hand or right hand side task
return false;
}
}
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;
}
/**
* @return the patch
*/
public Patch getPatch() {
return patch;
}
/**
* @return the diff level
*/
public int getDiffLevel() {
return diffLevel;
}
/**
* @return the first task of the comparison
*/
public ITask getLeftHandSide() {
return leftHandSide;
}
/**
* @return the second task of the comparison
*/
public ITask getRightHandSide() {
return rightHandSide;
}
/**
* @return the traversal of the first task of the comparison
*/
public TaskTraversal getLeftHandSideTraversal() {
return leftHandSideTraversal;
}
/**
* @return the traversal of the second task of the comparison
*/
public TaskTraversal getRightHandSideTraversal() {
return rightHandSideTraversal;
}
/**
* returns paths to subtasks, that can not be merged.
*/
public List getPathsToIgnore() {
List result = new LinkedList();
if ((patch.getDeltas().size() == 1) &&
(patch.getDeltas().get(0).getType() == Delta.TYPE.CHANGE))
{
// 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()))
{
TaskPath path = new TaskPath();
path.add(leftHandSide, 0);
result.add(path);
}
if ((singleChangeDelta.getRevised().getPosition() == 0) &&
(singleChangeDelta.getRevised().size() == rightHandSideTraversal.size()))
{
TaskPath path = new TaskPath();
path.add(rightHandSide, 0);
result.add(path);
}
}
if (result.size() < 2) {
// 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()) {
getNotFullyInterleavingIteration(delta, result);
getPathsToParentTasksFullyInsideDelta(delta, 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
// that hence should be ignored (especially when performing flattening of task
// instances later with the goal to preserve as many subtasks and respective instances)
int deltaIndex = 0;
int leftTraversalIndex = 0;
int rightTraversalIndex = 0;
Set commonInvolvedTasks = getCommonInvolvedTasks(leftHandSide, rightHandSide);
do {
Delta delta = deltaIndex < patch.getDeltas().size()
? patch.getDeltas().get(deltaIndex++) : null;
int nextLeftTraversalIndex = leftHandSideTraversal.size();
int nextRightTraversalIndex = rightHandSideTraversal.size();
if (delta != null) {
nextLeftTraversalIndex = delta.getOriginal().getPosition() + 1;
nextRightTraversalIndex = delta.getRevised().getPosition() + 1;
if (delta.getType() == Delta.TYPE.INSERT) {
nextLeftTraversalIndex--;
}
else if (delta.getType() == Delta.TYPE.DELETE) {
nextRightTraversalIndex--;
}
}
TaskPath[] leftSubTraversal =
leftHandSideTraversal.subList(leftTraversalIndex, nextLeftTraversalIndex);
for (TaskPath path : leftSubTraversal) {
for (int i = 0; i < path.size(); i++) {
if (commonInvolvedTasks.contains(path.getTask(i))) {
// found a candidate. Check if the candidate does not span more than
// the sub traversal
TaskPath parentPath = path.subPath(0, i + 1);
int[] indexes = leftHandSideTraversal.getIndexesRootedBy(parentPath);
if ((indexes[0] >= leftTraversalIndex) &&
(indexes[1] < nextLeftTraversalIndex))
{
result.add(parentPath);
break; // breaks only the path but the rest of the traversal is
// checked too
}
}
}
}
TaskPath[] rightSubTraversal =
rightHandSideTraversal.subList(rightTraversalIndex, nextRightTraversalIndex);
for (TaskPath path : rightSubTraversal) {
for (int i = 0; i < path.size(); i++) {
if (commonInvolvedTasks.contains(path.getTask(i))) {
// found a candidate. Check if the candidate does not span more than
// the sub traversal
TaskPath parentPath = path.subPath(0, i + 1);
int[] indexes = rightHandSideTraversal.getIndexesRootedBy(parentPath);
if ((indexes[0] >= rightTraversalIndex) &&
(indexes[1] < nextRightTraversalIndex))
{
result.add(parentPath);
break; // breaks only the path but the rest of the traversal is
// checked too
}
}
}
}
leftTraversalIndex = nextLeftTraversalIndex;
rightTraversalIndex = nextRightTraversalIndex;
}
while (leftTraversalIndex < leftHandSideTraversal.size());
}
return result;
}
/**
*
*/
public void dump(PrintStream out) {
out.println();
out.print("similar tasks: left ");
out.print(leftHandSide);
out.print(" (");
out.print(leftHandSide.getInstances().size());
out.print(" instances), right ");
out.print(rightHandSide);
out.print(" (");
out.print(rightHandSide.getInstances().size());
out.print(" instances), diff level ");
out.println(diffLevel);
out.println("left traversal");
for (TaskPath path : leftHandSideTraversal.getTraversalPaths()) {
out.println(path);
}
out.println("right traversal");
for (TaskPath path : rightHandSideTraversal.getTraversalPaths()) {
out.println(path);
}
if (patch != null) {
out.println("deltas:");
for (Delta delta : patch.getDeltas()) {
out.println(delta);
}
}
List linesLeft = new LinkedList();
TaskPath path = new TaskPath();
path.add(leftHandSide, 0);
dumpToLineList(path, leftHandSideTraversal, linesLeft);
path.removeLast();
List linesRight = new LinkedList();
path.add(rightHandSide, 0);
dumpToLineList(path, rightHandSideTraversal, linesRight);
/*System.out.println("\n#################################################");
for (int j = 0; ((j < linesLeft.size()) || (j < linesRight.size())); j++) {
String left = j < linesLeft.size() ? linesLeft.get(j) : "";
String right = j < linesRight.size() ? linesRight.get(j) : "";
StringBuffer line = new StringBuffer();
line.append(j);
line.append(":\t");
line.append(left);
for (int k = line.length(); k < 60; k++) {
line.append(' ');
}
line.append(right);
System.out.println(line);
}*/
// change lists to have the same length depending on the changes
int lineIndexLeft = 0;
int lineIndexRight = 0;
int leftHandTraversalIndex = 0;
while (leftHandTraversalIndex < leftHandSideTraversal.size()) {
//System.out.println("\n" + lineIndexLeft + " " + lineIndexRight);
Delta delta = null;
for (Delta candidate : patch.getDeltas()) {
if (candidate.getOriginal().getPosition() == leftHandTraversalIndex) {
delta = candidate;
break;
}
}
if ((delta != null) && (delta.getType() == Delta.TYPE.DELETE)) {
for (int j = 0; j < delta.getOriginal().size(); j++) {
while (linesLeft.get(lineIndexLeft) != null) {
lineIndexLeft++;
}
linesLeft.remove(lineIndexLeft);
while (lineIndexRight < lineIndexLeft) {
linesRight.add(lineIndexRight++, null);
}
leftHandTraversalIndex++;
}
linesLeft.add(lineIndexLeft++, "-------------------------------------");
linesRight.add(lineIndexRight++, "-------------------------------------");
}
else if ((delta != null) && (delta.getType() == Delta.TYPE.INSERT)) {
for (int j = 0; j < delta.getRevised().size(); j++) {
while (linesRight.get(lineIndexRight) != null) {
lineIndexRight++;
}
linesRight.remove(lineIndexRight);
while (lineIndexLeft < lineIndexRight) {
linesLeft.add(lineIndexLeft++, null);
}
}
// ensure that what is equal is harmonized too (because after an insert always
// comes something equal). The traversal index will be updated automatically,
// too.
delta = null;
linesLeft.add(lineIndexLeft++, "-------------------------------------");
linesRight.add(lineIndexRight++, "-------------------------------------");
}
if ((delta == null) || (delta.getType() == Delta.TYPE.CHANGE)) {
int chunkSizeLeft = delta != null ? delta.getOriginal().size() : 1;
int chunkSizeRight = delta != null ? delta.getRevised().size() : 1;
int chunksHandledLeft = 0;
int chunksHandledRight = 0;
for (int j = 0; j < Math.max(chunkSizeLeft, chunkSizeRight); j++) {
if (chunksHandledLeft < chunkSizeLeft) {
while (linesLeft.get(lineIndexLeft) != null) {
lineIndexLeft++;
}
linesLeft.remove(lineIndexLeft);
chunksHandledLeft++;
}
if (chunksHandledRight < chunkSizeRight) {
while (linesRight.get(lineIndexRight) != null) {
lineIndexRight++;
}
linesRight.remove(lineIndexRight);
chunksHandledRight++;
}
while (lineIndexLeft < lineIndexRight) {
linesLeft.add(lineIndexLeft++, null);
}
while (lineIndexRight < lineIndexLeft) {
linesRight.add(lineIndexRight++, null);
}
}
linesLeft.add(lineIndexLeft++, "-------------------------------------");
linesRight.add(lineIndexRight++, "-------------------------------------");
leftHandTraversalIndex += delta != null ? delta.getOriginal().size() : 1;
}
/*System.out.println(delta + " " + leftHandTraversalIndex);
System.out.println("\n#################################################");
for (int j = 0; ((j < linesLeft.size()) || (j < linesRight.size())); j++) {
String left = j < linesLeft.size() ? linesLeft.get(j) : "";
String right = j < linesRight.size() ? linesRight.get(j) : "";
StringBuffer line = new StringBuffer();
line.append(j);
line.append(":\t");
line.append(left);
for (int k = line.length(); k < 60; k++) {
line.append(' ');
}
line.append(right);
System.out.println(line);
}*/
}
int indentLeft = 0;
int indentRight = 0;
for (int i = 0; i < linesLeft.size(); i++) {
StringBuffer line = new StringBuffer();
String left = linesLeft.get(i);
String right = linesRight.get(i);
if (left != null) {
if (left.indexOf('}') >= 0) {
indentLeft -= 2;
}
for (int j = 0; j < indentLeft; j++) {
line.append(' ');
}
if (left.indexOf('{') >= 0) {
indentLeft += 2;
}
line.append(left);
}
if (right != null) {
for (int j = line.length(); j < 100; j++) {
line.append(' ');
}
if (right.indexOf('}') >= 0) {
indentRight -= 2;
}
for (int j = 0; j < indentRight; j++) {
line.append(' ');
}
if (right.indexOf('{') >= 0) {
indentRight += 2;
}
line.append(right);
}
out.println(line);
}
}
/**
*
*/
private static Set getCommonInvolvedTasks(ITask task1, ITask task2) {
Set result = getAllInvolvedTasks(task1);
result.retainAll(getAllInvolvedTasks(task2));
return result;
}
/**
*
*/
private static Set getAllInvolvedTasks(ITask task) {
final Set result = new HashSet();
task.accept(new DefaultTaskTraversingVisitor() {
@Override
public void visit(IEventTask eventTask) {
result.add(eventTask);
}
@Override
public void visit(IStructuringTemporalRelationship relationship) {
result.add(relationship);
super.visit(relationship);
}
@Override
public void visit(IMarkingTemporalRelationship relationship) {
result.add(relationship);
super.visit(relationship);
}
});
return result;
}
/**
*
*/
private void dumpToLineList(TaskPath path,
TaskTraversal traversal,
List lines)
{
boolean isTraversalElement = false;
for (TaskPath candidate : traversal.getTraversalPaths()) {
if (path.equals(candidate)) {
isTraversalElement = true;
break;
}
}
if (isTraversalElement) {
lines.add(path.getLast().toString());
lines.add(null);
/*ByteArrayOutputStream byteStream = new ByteArrayOutputStream();
PrintStream out = new PrintStream(byteStream);
new TaskTreeEncoder().encode(path.getLast(), out);
out.close();
BufferedReader reader = new BufferedReader
(new InputStreamReader(new ByteArrayInputStream(byteStream.toByteArray())));
String line = null;
do {
try {
line = reader.readLine();
}
catch (IOException e) {
// should not happen so dump hard
e.printStackTrace();
}
lines.add(line != null ? line.trim() : null);
}
while (line != null);*/
}
else {
ITask task = path.getLast();
if (task instanceof ITemporalRelationship) {
lines.add(task + " {");
if (task instanceof IStructuringTemporalRelationship) {
List children =
((IStructuringTemporalRelationship) task).getChildren();
for (int i = 0; i < children.size(); i++) {
path.add(children.get(i), i);
dumpToLineList(path, traversal, lines);
path.removeLast();
}
}
else if (task instanceof IMarkingTemporalRelationship) {
IMarkingTemporalRelationship relationship =
(IMarkingTemporalRelationship) task;
path.add(relationship.getMarkedTask(), 0);
dumpToLineList(path, traversal, lines);
path.removeLast();
}
if (lines.get(lines.size() - 1) != null) {
lines.add("}");
}
else {
lines.add(lines.size() - 1, "}");
}
}
else {
lines.add(task + " {}");
}
}
}
/**
*
*/
/*@SuppressWarnings("unchecked")
private void getSelections(Delta delta, List result) {
TaskPath path1 = getCommonPath((List) delta.getOriginal().getLines());
TaskPath path2 = getCommonPath((List) delta.getRevised().getLines());
for (int i = 0; i < path1.size(); i++) {
if (path1.getTask(i) instanceof ISelection) {
System.out.println("found selection to ignore");
System.out.println(path1.subPath(0, i + 1));
result.add(path1.subPath(0, i + 1));
break;
}
}
for (int i = 0; i < path2.size(); i++) {
if (path2.getTask(i) instanceof ISelection) {
System.out.println("found selection to ignore");
System.out.println(path2.subPath(0, i + 1));
result.add(path2.subPath(0, i + 1));
break;
}
}
}*/
/**
* 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 getConflictingIterations() {
List 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 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 result)
{
if (instance instanceof IIterationInstance) {
ITask markedTask = instance.getTask();
while (markedTask instanceof IMarkingTemporalRelationship) {
markedTask = ((IMarkingTemporalRelationship) markedTask).getMarkedTask();
}
if ((!(markedTask instanceof IEventTask)) &&
((IIterationInstance) instance).size() > 1)
{
// iteration repeates multiple event tasks and is 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 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 overlappingIterations = new LinkedList();
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);
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 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;
}
/**
*
*/
private TaskPath getCommonPath(List paths) {
TaskPath commonPath;
if (paths.size() > 0) {
commonPath = new TaskPath(paths.get(0));
for (int i = 1; i < paths.size(); i++) {
TaskPath comparePath = paths.get(i);
for (int j = 0; (j < commonPath.size()) && (j < comparePath.size()); j++) {
if (!commonPath.get(j).equals(comparePath.get(j))) {
while (commonPath.size() > j) {
commonPath.removeLast();
}
break;
}
}
}
}
else {
commonPath = new TaskPath();
}
return commonPath;
}
/**
*
*/
private void getNotFullyInterleavingIteration(Delta delta, List result) {
getNotFullyInterleavingIterations(delta.getOriginal(), leftHandSideTraversal, result);
getNotFullyInterleavingIterations(delta.getRevised(), rightHandSideTraversal, result);
}
/**
* If a chunk has a minimum number of 2 entries and at least one of them belongs to an iteration
* 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,
TaskTraversal traversal,
List result)
{
@SuppressWarnings("unchecked")
List paths = (List) chunk.getLines();
TaskPath commonPath = getCommonPath(paths);
if (paths.size() > 1) {
TaskPath firstPath = paths.get(0);
TaskPath lastPath = paths.get(paths.size() - 1);
for (int i = commonPath.size(); i < firstPath.size(); i++) {
if (firstPath.get(i).getTask() instanceof IIteration) {
// check, if the iteration covers things preceding the delta but not the whole
// delta
int[] indexes = traversal.getIndexesRootedBy(firstPath.subPath(0, i + 1));
if ((indexes[0] < chunk.getPosition()) && // starts before the delta
(indexes[1] < (chunk.getPosition() + chunk.size() - 1))) // does not cover delta
{
result.add(firstPath.subPath(0, i + 1));
break;
}
}
}
for (int i = commonPath.size(); i < lastPath.size(); i++) {
if (lastPath.get(i).getTask() instanceof IIteration) {
// check, if the iteration covers things preceding the delta but not the whole
// delta
int[] indexes = traversal.getIndexesRootedBy(lastPath.subPath(0, i + 1));
if ((indexes[0] > chunk.getPosition()) && // starts in between the delta
(indexes[1] >= (chunk.getPosition() + chunk.size()))) // ends after the delta
{
result.add(lastPath.subPath(0, i + 1));
break;
}
}
}
}
}
/**
*
*/
private void getPathsToParentTasksFullyInsideDelta(Delta delta, List result) {
getPathsToParentTasksFullyInsideChunk(delta.getOriginal(), leftHandSideTraversal, result);
getPathsToParentTasksFullyInsideChunk(delta.getRevised(), rightHandSideTraversal, result);
}
/**
* 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.
*/
private void getPathsToParentTasksFullyInsideChunk(Chunk chunk,
TaskTraversal traversal,
List result)
{
@SuppressWarnings("unchecked")
List paths = (List) chunk.getLines();
TaskPath commonPath = getCommonPath(paths);
for (TaskPath path : paths) {
for (int i = commonPath.size(); i < path.size(); i++) {
if (!(path.getLast() instanceof IEventTask)) {
// check, if the parent task covers things fully inside the delta
int[] indexes = traversal.getIndexesRootedBy(path.subPath(0, i + 1));
if ((chunk.getPosition() <= indexes[0]) && // starts in the delta
(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));
result.add(path.subPath(0, i + 1));
break;
}
}
}
}
}
/**
*
*/
private void getUnexecutedParentOptionals(ITask task,
List 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 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();
}
}
/**
*
*/
@SuppressWarnings("unchecked")
private int getDiffLevel(Patch patch,
TaskTraversal traversal1,
TaskTraversal traversal2)
{
int diffCount = 0;
int allCount = 0;
for (Delta delta : patch.getDeltas()) {
for (TaskPath path : (List) delta.getOriginal().getLines()) {
// inefficient actions are counted later.
if (!isInefficientAction(path.getLast())) {
diffCount += getDiffPenalty(path.getLast());
}
}
for (TaskPath path : (List) delta.getRevised().getLines()) {
// inefficient actions are counted later.
if (!isInefficientAction(path.getLast())) {
diffCount += getDiffPenalty(path.getLast());
}
}
}
//if (getPathsToRealIntersectingIterations().size() > 0) {
// add a penalty if intersecting iterations are present
//count += 10;
//}
// add a penalty for inefficient actions which are equal as they have to be treated
// unequal, too. Otherwise, many scrolls, e.g., would pretend a high equality of tasks
// which contain only some non inefficient actions
for (TaskPath path : traversal1.getTraversalPaths()) {
if (isInefficientAction(path.getLast())) {
diffCount++;
allCount++;
}
else {
allCount += getDiffPenalty(path.getLast());
}
}
for (TaskPath path : traversal2.getTraversalPaths()) {
if (isInefficientAction(path.getLast())) {
diffCount++;
allCount++;
}
else {
allCount += getDiffPenalty(path.getLast());
}
}
if (allCount == 0) {
// this happens, if all actions are inefficient. Return the highest diff level
return 100;
}
else {
return (100 * diffCount) / allCount;
}
}
/**
*
*/
private boolean isInefficientAction(ITask task) {
ITaskInstance inst = task.getInstances().iterator().next();
if ((inst instanceof IEventTaskInstance) &&
(((IEventTaskInstance) inst).getEvent().getType() instanceof Scroll))
{
return true;
}
else if (task instanceof IMarkingTemporalRelationship) {
return isInefficientAction(((IMarkingTemporalRelationship) task).getMarkedTask());
}
else {
return false;
}
}
/**
*
*/
private int getDiffPenalty(ITask task) {
if (task instanceof IEventTask) {
return 1;
}
else if (task instanceof IMarkingTemporalRelationship) {
return getDiffPenalty(((IMarkingTemporalRelationship) task).getMarkedTask());
}
else if (task instanceof IStructuringTemporalRelationship) {
int result = 0;
for (ITask child : ((IStructuringTemporalRelationship) task).getChildren()) {
result += getDiffPenalty(child);
}
if (task instanceof ISelection) {
result /= ((IStructuringTemporalRelationship) task).getChildren().size();
}
return result;
}
throw new IllegalArgumentException("unknown type of task: " + task);
}
}