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

//   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.TaskInstanceComparator;
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.IMarkingTemporalRelationship;
import de.ugoe.cs.autoquest.tasktrees.treeifc.ISelection;
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 {
    
    /**
     * 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,
                        ITask         task1,
                        TaskTraversal traversal1,
                        ITask         task2,
                        TaskTraversal traversal2)
    {
        this.leftHandSide = task1;
        this.leftHandSideTraversal = traversal1;
        this.rightHandSide = task2;
        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,
                                            TaskInstanceComparator 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 */);
    }

    /**
     * static convenience method to compare two tasks but ignoring a given set of subtasks when
     * creating the traversals. Furhtermore, it can be defined, if subtasks occurring in both
     * similar tasks are traversed or not.
     */
    public static SimilarTasks compareTasks(ITask                  task1,
                                            ITask                  task2,
                                            TaskInstanceComparator comparator,
                                            List<TaskPath>         pathsNotToTraverse,
                                            boolean                traverseCommonPaths)
    {
        Set<ITask> commonInvolvedTasks;

        if (traverseCommonPaths) {
            commonInvolvedTasks = new HashSet<ITask>();
        }
        else {
            commonInvolvedTasks = getCommonInvolvedTasks(task1, task2);
        }

        TaskTraversal traversal1 =
             TaskTraversal.getTraversal(task1, commonInvolvedTasks, pathsNotToTraverse);
        
        TaskTraversal traversal2 =
             TaskTraversal.getTraversal(task2, commonInvolvedTasks, pathsNotToTraverse);

        if ((traversal1.size() <= 0) || (traversal2.size() <= 0)) {
            return null;
        }

        Patch patch = new TaskTraversalMyersDiff(comparator).getDiff(traversal1, traversal2);

        SimilarTasks result = new SimilarTasks(patch, task1, traversal1, task2, 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,
                                                            TaskInstanceComparator comparator)
    {
        SimilarTasks similarTasks = source;
        
        List<TaskPath> pathsToIgnore = similarTasks.getPathsToIgnore();
        
        int prevPathsToIgnoreCount = 0;
        
        do {
            prevPathsToIgnoreCount = pathsToIgnore.size();
            
            similarTasks = compareTasks
                (similarTasks.getLeftHandSide(), similarTasks.getRightHandSide(),
                 comparator, pathsToIgnore, true);

            similarTasks.dump(System.out);
            
            List<TaskPath> furtherPathsToIgnore = similarTasks.getPathsToIgnore();
            
            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);
        
        return similarTasks;
    }

    /**
     * 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;
    }
    
    /**
     * @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>();
        Delta singleChangeDelta = null;
        
        if ((patch.getDeltas().size() == 1) &&
            (patch.getDeltas().get(0).getType() == Delta.TYPE.CHANGE))
        {
            singleChangeDelta = patch.getDeltas().get(0);
        }
        
        // if it is a full change, then the parent of either side must be fully ignored
        if (singleChangeDelta != null) {
            if ((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 selections and interleaving
            // iterations that have to be ignored if they belong to a delta
            for (Delta delta : patch.getDeltas()) {
                //getSelections(delta, result);
                getPathsToRealIntersectingIterations(delta, result);
                getNotFullyInterleavingIteration(delta, result);
                getPathsToParentTasksFullyInsideDelta(delta, 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;
            }
        }
    }*/

    /**
     *
     */
    @SuppressWarnings("unchecked")
    private void getPathsToRealIntersectingIterations(Delta delta, List<TaskPath> paths) {
        TaskPath path1 = getCommonPath((List<TaskPath>) delta.getOriginal().getLines());
        TaskPath path2 = getCommonPath((List<TaskPath>) delta.getRevised().getLines());
        
        // both paths denote those parent tasks that contain the delta.
        // But there may be parent tasks still contained in the path that are iterations and
        // that are disjoint with a parent in the other path. Those iterations need to be
        // considered, as otherwise a created selection would be against the associative law of
        // iterations. Hence, we search for the topmost iteration on both paths that is disjoint
        // with a parent node in the respective other path.
        
        for (int i = 0; i < path1.size(); i++) {
            TaskPath path1Prefix = path1.subPath(0, i + 1);
            int[] idxsPath1 = leftHandSideTraversal.getIndexesRootedBy(path1Prefix);
            
            // normalize the indexes to be 0 the index of the delta. Everything left of it
            // is smaller 0, everything right of it, larger.
            idxsPath1[0] -= delta.getOriginal().getPosition();
            idxsPath1[1] -= delta.getOriginal().getPosition() + delta.getOriginal().size() - 1;
            
            for (int j = 0; j < path2.size(); j++) {
                TaskPath path2Prefix = path2.subPath(0, j + 1);
                int[] idxsPath2 = rightHandSideTraversal.getIndexesRootedBy(path2Prefix);
                
                // normalize the indexes to be 0 the index of the delta. Everything left of it
                // is smaller 0, everything right of it, larger.
                idxsPath2[0] -= delta.getRevised().getPosition();
                idxsPath2[1] -=
                    delta.getRevised().getPosition() + delta.getRevised().size() - 1;
                
                // now compare the indexes and check, if the sublists are real subsets of each
                // other. If not, they only have a real common subset but there is at least one
                // non shared element on both sides. If so, and one is an iteration, we
                // have to use it as elements to be selected
                if (((idxsPath1[0] < idxsPath2[0]) && (idxsPath1[1] < idxsPath2[1])) ||
                    ((idxsPath1[0] > idxsPath2[0]) && (idxsPath1[1] > idxsPath2[1])))
                {
                    if ((path1.get(i).getTask() instanceof IIteration) &&
                        (path2.get(j).getTask() instanceof IIteration))
                    {
                        System.out.println("found paths to real intersecting parents");
                        int[] indexBuf = leftHandSideTraversal.getIndexesRootedBy(path1Prefix);
                        System.out.println(idxsPath1[0] + "(" + indexBuf[0] + ")  " + idxsPath1[1] +
                                           "(" + indexBuf[1] + ")  " + path1Prefix);
                        indexBuf = rightHandSideTraversal.getIndexesRootedBy(path2Prefix);
                        System.out.println(idxsPath2[0] + "(" + indexBuf[0] + ")  " + idxsPath2[1] +
                                           "(" + indexBuf[1] + ")  " + path2Prefix);
                        
                        paths.add(path1Prefix);
                        paths.add(path2Prefix);
                        return;
                    }
                }
            }
        }
    }

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

    /**
     *
     */
    @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<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++;
            }
            else {
                allCount += getDiffPenalty(path.getLast());
            }
        }
        
        for (TaskPath path : traversal2.getTraversalPaths()) {
            if (isInefficientAction(path.getLast())) {
                diffCount++;
            }
            else {
                allCount += getDiffPenalty(path.getLast());
            }
        }
        
        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);
    }
}