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

//   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;

/**
 * <p>
 * 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.
 * </p>
 * 
 * @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<TaskPath> 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>
     * static convenience method to compare two task traversals using a given comparator to compare
     * the individual tasks in the traversals.
     * </p>
     */
    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<TaskPath> pathsToIgnore = similarTasks.getPathsToIgnore();
        
        int prevPathsToIgnoreCount = 0;
        
        do {
            prevPathsToIgnoreCount = pathsToIgnore.size();
            
            similarTasks = compareTasks
                (similarTasks.getLeftHandSide(), similarTasks.getRightHandSide(),
                 comparator, pathsToIgnore);

            // similarTasks.dump(System.out);
            
            List<TaskPath> 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<Delta> 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;
    }

    /**
     * <p>
     * returns true, if the differences between the traversals are between the beginning and the
     * end of both traversals.
     * </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;
    }
    
    /**
     * @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<TaskPath> getPathsToIgnore() {
        List<TaskPath> result = new LinkedList<TaskPath>();
        
        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<ITask> 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<String> linesLeft = new LinkedList<String>();
        TaskPath path = new TaskPath();
        path.add(leftHandSide, 0);
        dumpToLineList(path, leftHandSideTraversal, linesLeft);
        path.removeLast();
        
        List<String> linesRight = new LinkedList<String>();
        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<ITask> getCommonInvolvedTasks(ITask task1, ITask task2) {
        Set<ITask> result = getAllInvolvedTasks(task1);
        result.retainAll(getAllInvolvedTasks(task2));
        return result;
    }

    /**
     *
     */
    private static Set<ITask> getAllInvolvedTasks(ITask task) {
        final Set<ITask> result = new HashSet<ITask>();

        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<String>  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<ITask> 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<TaskPath> result) {
        TaskPath path1 = getCommonPath((List<TaskPath>) delta.getOriginal().getLines());
        TaskPath path2 = getCommonPath((List<TaskPath>) 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<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) {
            ITask markedTask = instance.getTask();
            
            while (markedTask instanceof IMarkingTemporalRelationship) {
                markedTask = ((IMarkingTemporalRelationship) markedTask).getMarkedTask();
            }
            
            if ((!(markedTask instanceof IEventTask)) &&
                ((IIterationInstance) instance).size() > 1)
            {
                // iteration repeats 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<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)) {
                for (TaskPath rightPath : iterationsWithMultipleExecutions) {
                    if (rightPath.getTask(0).equals(rightHandSide)) {
                        int[] leftIdxs = leftHandSideTraversal.getIndexesRootedBy(leftPath);
                        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<Delta> deltas)
    {
        int originalStartUpdate = 0;
        int originalEndUpdate = 0;
        int revisedStartUpdate = 0;
        int revisedEndUpdate = 0;
        
        for (Delta delta : deltas) {
            if (delta.getType() == Delta.TYPE.INSERT) {
                // for insert deltas only the original indexes must be adapted
                if (delta.getOriginal().getPosition() <= originalIndexes[0]) {
                    originalStartUpdate += delta.getRevised().size();
                }
                if (delta.getOriginal().getPosition() <= originalIndexes[1]) {
                    originalEndUpdate += delta.getRevised().size();
                }
            }
            else if (delta.getType() == Delta.TYPE.DELETE) {
                // for delete deltas only the revised indexes must be adapted
                if (delta.getRevised().getPosition() <= revisedIndexes[0]) {
                    revisedStartUpdate += delta.getOriginal().size();
                }
                if (delta.getRevised().getPosition() <= revisedIndexes[1]) {
                    revisedEndUpdate += delta.getOriginal().size();
                }
            }
            else if (delta.getType() == Delta.TYPE.CHANGE) {
                // for change deltas we adapt only the revision indexes.
                // If the revised variant is longer than the original, the indexes become smaller.
                // else, the other way around
                int lengthDiff = delta.getOriginal().size() - delta.getRevised().size();
                
                if (lengthDiff < 0) {
                    // the revised variant is longer --> adapt indexes of original
                    lengthDiff = 0 - lengthDiff;
                    int start = delta.getOriginal().getPosition();
                    int end = start + delta.getOriginal().size() - 1;
                    
                    if (end < originalIndexes[0]) {
                        // delta is before indexes
                        originalStartUpdate += lengthDiff;
                    }
                    if ((end <= originalIndexes[1]) || (start <= originalIndexes[1])) {
                        // delta and indexes overlap
                        originalEndUpdate += lengthDiff;
                    }
                }
                else if (lengthDiff > 0) {
                    // the original variant is longer --> adapt indexes of revised
                    int start = delta.getRevised().getPosition();
                    int end = start + delta.getRevised().size() - 1;
                    
                    if (end < revisedIndexes[0]) {
                        // delta is before indexes
                        revisedStartUpdate += lengthDiff;
                    }
                    if ((end <= revisedIndexes[1]) || (start <= revisedIndexes[1])) {
                        // delta and indexes overlap
                        revisedEndUpdate += lengthDiff;
                    }
                }
            }
        }
        
        originalIndexes[0] += originalStartUpdate;
        originalIndexes[1] += originalEndUpdate;
        revisedIndexes[0] += revisedStartUpdate;
        revisedIndexes[1] += revisedEndUpdate;
    }

    /**
     *
     */
    private TaskPath getCommonPath(List<TaskPath> 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<TaskPath> 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<TaskPath> result)
    {
        @SuppressWarnings("unchecked")
        List<TaskPath> paths = (List<TaskPath>) 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<TaskPath> 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<TaskPath> result)
    {
        @SuppressWarnings("unchecked")
        List<TaskPath> paths = (List<TaskPath>) chunk.getLines();
        
        for (TaskPath path : paths) {
            for (int i = path.size() - 1; i >= 0; i--) {
                // check, if the parent task covers things fully inside the delta
                TaskPath parentPath = path.subPath(0, i);
                
                //System.out.println("checking parent path " + parentPath);
                int[] indexes = traversal.getIndexesRootedBy(parentPath);
                //System.out.println("indexes are " + indexes[0] + "  " + indexes[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 lying completely in the " +
                    //                   "delta: " + parentPath);
                    result.add(parentPath);
                }
                else {
                    // further parents can not be inside the delta
                    break;
                }
            }
        }
    }

    /**
     *
     */
    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();
        }
    }

    /**
     *
     */
    @SuppressWarnings("unchecked")
    private int getDiffLevel(Patch         patch,
                             TaskTraversal traversal1,
                             TaskTraversal traversal2)
    {
        if (patch.getDeltas().size() == 0) {
            return 0;
        }
        
        int diffCount = 0;
        int allCount = 0;
        
        for (Delta delta : patch.getDeltas()) {
            for (TaskPath path : (List<TaskPath>) delta.getOriginal().getLines()) {
                // inefficient actions are counted later.
                if (!isInefficientAction(path.getLast())) {
                    diffCount += getDiffPenalty(path.getLast());
                }
            }
            for (TaskPath path : (List<TaskPath>) 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) {
        if (task instanceof IEventTask) {
            IEventTaskInstance inst = (IEventTaskInstance) task.getInstances().iterator().next();
            if (inst.getEvent().getType() instanceof Scroll) {
                return true;
            }
            else {
                return false;
            }
        }
        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);
    }
}