source: trunk/autoquest-core-tasktrees/src/main/java/de/ugoe/cs/autoquest/tasktrees/temporalrelation/CondenseSimilarTasksRule.java @ 1854

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

import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

import de.ugoe.cs.autoquest.tasktrees.taskequality.TaskEquality;
import de.ugoe.cs.autoquest.tasktrees.temporalrelation.utils.MostSimilarTaskDeterminer;
import de.ugoe.cs.autoquest.tasktrees.temporalrelation.utils.SimilarTasks;
import de.ugoe.cs.autoquest.tasktrees.temporalrelation.utils.TaskTraversal;
import de.ugoe.cs.autoquest.tasktrees.treeifc.IIteration;
import de.ugoe.cs.autoquest.tasktrees.treeifc.IIterationInstance;
import de.ugoe.cs.autoquest.tasktrees.treeifc.IMarkingTemporalRelationship;
import de.ugoe.cs.autoquest.tasktrees.treeifc.IOptional;
import de.ugoe.cs.autoquest.tasktrees.treeifc.IOptionalInstance;
import de.ugoe.cs.autoquest.tasktrees.treeifc.ISelection;
import de.ugoe.cs.autoquest.tasktrees.treeifc.ISelectionInstance;
import de.ugoe.cs.autoquest.tasktrees.treeifc.ISequence;
import de.ugoe.cs.autoquest.tasktrees.treeifc.ISequenceInstance;
import de.ugoe.cs.autoquest.tasktrees.treeifc.ITask;
import de.ugoe.cs.autoquest.tasktrees.treeifc.ITaskBuilder;
import de.ugoe.cs.autoquest.tasktrees.treeifc.ITaskFactory;
import de.ugoe.cs.autoquest.tasktrees.treeifc.ITaskInstance;
import de.ugoe.cs.autoquest.tasktrees.treeifc.ITaskInstanceList;
import de.ugoe.cs.autoquest.tasktrees.treeifc.ITaskModel;
import de.ugoe.cs.autoquest.tasktrees.treeifc.IUserSession;
import de.ugoe.cs.autoquest.tasktrees.treeifc.TaskPath;
import de.ugoe.cs.util.console.Console;
import difflib.Chunk;
import difflib.Delta;

/**
 * <p>
 * This rule performs a condensing of a task tree. It searches for similar tasks and merges them
 * if possible in to one task with different execution variants. Hence, this rule detects selections
 * and optionals.
 * </p>
 * <p>
 * The similarity of tasks is determined by comparing task traversals. A task traversal is an
 * ordered list of the leaf nodes of a task. This is similar to performing a minimal execution of
 * the task. The task traversals of two tasks are compared using string comparison algorithms. The
 * less differences the lists have, the more similar they are.
 * </p>
 * <p>
 * If two tasks are similar, they are merged. Merging is done based on the differences between
 * the task traversals. Two tasks are merged based on their instances. First, all instances of both
 * tasks are flattened. Instances of selections or commonalities of both tasks stay unflattened.
 * Then the lists resulting from this flattening are extended with instances of optionals and
 * selections which are introduced where required. Finally, the instances are put together to a
 * single task again by applying the {@link SequenceForTaskDetectionRule} on them.
 * </p>
 * <p>
 * Merging has to consider several specific situations. E.g., tasks may look similar but due to
 * iterations, they can not be merged correctly. Here, the rule ensures, that these so called
 * interleaving iterations are detected, not traversed when traversing a task and its instances,
 * and, therefore, preserved.
 * </p>
 * <p>
 * All details about this rule are described in the extended ACHI2014 paper of Harms "Trace-based
 * task tree generation". The extended paper was submitted to the IntSys IARIA Journal.
 * </p>
 * 
 * @author Patrick Harms
 */
class CondenseSimilarTasksRule implements ISessionScopeRule {

    /**
     * <p>
     * the task factory to be used for creating substructures for the temporal
     * relationships identified during rule application
     * </p>
     */
    private ITaskFactory taskFactory;
    /**
     * <p>
     * the task builder to be used for creating substructures for the temporal relationships
     * identified during rule application
     * </p>
     */
    private ITaskBuilder taskBuilder;

    /**
     * <p>
     * the task handling strategy to be used for comparing tasks during iteration detection an trie
     * generation, i.e., after the tasks are harmonized 
     * </p>
     */
    private TaskHandlingStrategy identTaskHandlStrat;
    
    /**
     * <p>
     * instantiates the rule and initializes it with a task equality to be considered when
     * comparing tasks as well as a task factory and builder to be used for creating task
     * structures.
     * </p>
     * 
     * @param minimalTaskEquality the task equality to be considered when comparing tasks
     * @param taskFactory         the task factory to be used for creating substructures
     * @param taskBuilder         the task builder to be used for creating substructures
     */
    CondenseSimilarTasksRule(TaskEquality minimalTaskEquality,
                             ITaskFactory taskFactory,
                             ITaskBuilder taskBuilder)
    {
        this.taskFactory = taskFactory;
        this.taskBuilder = taskBuilder;
        
        this.identTaskHandlStrat = new TaskHandlingStrategy(TaskEquality.IDENTICAL);
    }

    /* (non-Javadoc)
     * @see java.lang.Object#toString()
     */
    @Override
    public String toString() {
        return "CondenseSimilarTasksRule";
    }

    /* (non-Javadoc)
     * @see de.ugoe.cs.autoquest.tasktrees.temporalrelation.ISessionScopeRule#apply(java.util.List)
     */
    @Override
    public RuleApplicationResult apply(List<IUserSession> sessions) {
        
        // >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
        // >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> TEST IMPLEMENTATION >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
        /*final List<IEventTaskInstance> formerInstances = new ArrayList<>();
        final List<IEventTaskInstance> newInstances = new ArrayList<>();
        
        try {
            ITaskInstanceVisitor visitor = new DefaultTaskInstanceTraversingVisitor() {
                @Override
                public void visit(IEventTaskInstance eventTaskInstance) {
                    formerInstances.add(eventTaskInstance);
                }
            };
            
            PrintStream out = new PrintStream(new FileOutputStream(new File("01.out")));
            
            for (IUserSession session : sessions) {
                new TaskTreeEncoder().encode(session, out, null);
                
                for (ITaskInstance instance : session) {
                    instance.accept(visitor);
                }
            }
            out.close();
        }
        catch (FileNotFoundException e) {
            e.printStackTrace();
        }
        
        PrintStream fileout = null;
        try {
            fileout = new PrintStream("sysout.txt");
        }
        catch (FileNotFoundException e1) {
            e1.printStackTrace();
        }
        
        PrintStream origOut = System.out;
        if (fileout != null) {
            System.setOut(fileout);
        }*/
        
        // <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
        // <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< TEST IMPLEMENTATION <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
        
        
        RuleApplicationData appData = new RuleApplicationData(sessions);
        
        do {
            appData.setTaskModel(taskFactory.createTaskModel(sessions));
            appData.setMostSimilarTasks(null);
            
            // >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
            // >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> TEST IMPLEMENTATION >>>>>>>>>>>>>>>>>>>>>
            // for (ITask task : appData.getTaskModel().getTasks()) {
            //     if (task.getInstances().size() <= 0) {
            //         throw new RuntimeException("task " + task + " has no instances anymore");
            //     }
            //     
            //     try {
            //         new TaskTreeValidator().validate(task);
            //     }
            //     catch (Exception e) {
            //         new TaskTreeEncoder().encode(task, System.err);
            //     }
            // }
            // 
            // new TaskTreeValidator().validate(sessions);
            
            // <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
            // <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< TEST IMPLEMENTATION <<<<<<<<<<<<<<<<<<<<<<


            Console.println("condensing " + appData.getTaskModel().getTasks().size() + " tasks");

            getMostSimilarTasks(appData);

            if (appData.getMostSimilarTasks() != null) {
                for (SimilarTasks mostSimilarTask : appData.getMostSimilarTasks()) {
                    handleSimilarTasks(mostSimilarTask, appData);
                    appData.markAsAlreadyCondensed
                        (mostSimilarTask.getLeftHandSide(), mostSimilarTask.getRightHandSide());
                }
            }
            
        }
        while (appData.getMostSimilarTasks() != null);
        
        
        // >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
        // >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> TEST IMPLEMENTATION >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
        /*try {
            ITaskInstanceVisitor visitor = new DefaultTaskInstanceTraversingVisitor() {
                @Override
                public void visit(IEventTaskInstance eventTaskInstance) {
                    newInstances.add(eventTaskInstance);
                }
            };
            
            PrintStream out = new PrintStream(new FileOutputStream(new File("02.out")));
            
            for (IUserSession session : sessions) {
                new TaskTreeEncoder().encode(session, out, null);
                
                for (ITaskInstance instance : session) {
                    instance.accept(visitor);
                }
            }
            out.close();
        }
        catch (FileNotFoundException e) {
            e.printStackTrace();
        }
        
        System.out.println("sizes  " + formerInstances.size() + "  " + newInstances.size());
        for (int i = 0; i < newInstances.size(); i++) {
            if (formerInstances.get(i) != newInstances.get(i)) {
                System.out.println(i + "  " + formerInstances.get(i) + "  " + newInstances.get(i));
            }
        }
        
        System.setOut(origOut);
        fileout.close();*/
        // <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
        // <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< TEST IMPLEMENTATION <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<

        
        return appData.finalizeRuleApplicationResult();
    }

    /**
     *
     */
    private void getMostSimilarTasks(RuleApplicationData appData) {
        // determine the list of interesting tasks
        Collection<ITask> allTasks = appData.getTaskModel().getTasks();
        Iterator<ITask> taskIterator = allTasks.iterator();
        List<ITask> taskList = new ArrayList<ITask>(allTasks.size());
        
        while (taskIterator.hasNext()) {
            ITask task = taskIterator.next();
            
            // only Sequences need to be compared with each other. Iterations differ only in their
            // child, i.e., in the child sequences.
            if (task instanceof ISequence) {
                taskList.add(task);
            }
        }
        
        if (taskList.size() > 1) {
            List<SimilarTasks> mostSimilarTasks =
                appData.getMostSimilarTasksDeterminer().getMostSimilarTasks
                    (taskList, appData.getTaskModel());
            
            if (mostSimilarTasks.size() > 0) {
                appData.setMostSimilarTasks(mostSimilarTasks);
            }
        }
    }

    /**
     *
     */
    private void handleSimilarTasks(SimilarTasks similarTasks, RuleApplicationData appData) {
        // we need at least one instance per similar task. If not, it will not work and also
        // does not make sense. No instances anymore can be caused by merging and hence
        // discarding tasks in preceding merges.
        
        // similarTasks.dump(System.out);
        
        if ((similarTasks.getLeftHandSide().getInstances().size() <= 0) ||
            (similarTasks.getRightHandSide().getInstances().size() <= 0))
        {
            /*System.out.println("a task exists that has no instances");
            System.out.println(similarTasks.getLeftHandSide() + "  " +
                               similarTasks.getLeftHandSide().getInstances().size());
            System.out.println(similarTasks.getRightHandSide() + "  " +
                               similarTasks.getRightHandSide().getInstances().size());*/
            
            throw new RuntimeException
                ("one and the same task seems to belong to several similar tasks");
        }
        
        similarTasks = SimilarTasks.getMergableLevelOfSimilarity
            (similarTasks, identTaskHandlStrat.getTaskComparator());
        
        if (similarTasks == null) {
            // this may happen, if no mergable level of similarity can be found
            return;
        }
        
        // similarTasks.dump(System.out);

        List<FlattenInstruction> flattenInstructions =
            getFlattenInstructions(similarTasks, appData);
        
        // for (FlattenInstruction instruction : flattenInstructions) {
        //     instruction.dump(System.out);
        // }
        
        int noOfFlattenedInstances = similarTasks.getLeftHandSide().getInstances().size() +
            similarTasks.getRightHandSide().getInstances().size();
        
        // >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
        // >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> TEST IMPLEMENTATION >>>>>>>>>>>>>>>>>>>>>>>>>>>>>
        List<TaskPath> excludes = new ArrayList<TaskPath>();
        
        for (FlattenInstruction instruction : flattenInstructions) {
            //System.out.println("exclude " + instruction.path);
            excludes.add(instruction.path);
        }
        // <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
        // <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< TEST IMPLEMENTATION <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<

        Map<ITaskInstance, IUserSession> flattenedSessions =
            new HashMap<ITaskInstance, IUserSession>(noOfFlattenedInstances);
        flattenInstances
            (similarTasks.getLeftHandSide(), flattenInstructions, flattenedSessions, excludes);
        flattenInstances
            (similarTasks.getRightHandSide(), flattenInstructions, flattenedSessions, excludes);

        // >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
        // >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> TEST IMPLEMENTATION >>>>>>>>>>>>>>>>>>>>>>>>>>>>>
        /*for (IUserSession session : flattenedSessions.values()) {
            System.out.println("user session {");
            
            for (ITaskInstance instance : session) {
                System.out.println(instance);
            }
            
            System.out.println("}");
        }*/
        // <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
        // <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< TEST IMPLEMENTATION <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
        
        List<IUserSession> flattenedSessionList =
            new LinkedList<IUserSession>(flattenedSessions.values());
        
        new SequenceForTaskDetectionRule
            (TaskEquality.IDENTICAL, taskFactory, taskBuilder).apply(flattenedSessionList);
        
        Map<ITaskInstance, ITaskInstance> replacements = new HashMap<ITaskInstance, ITaskInstance>();
        ITask replacementTask = null;
        
        for (Map.Entry<ITaskInstance, IUserSession> entry : flattenedSessions.entrySet()) {
            // >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
            // >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> TEST IMPLEMENTATION >>>>>>>>>>>>>>>>>>>>>>>>>>>>>
            // the user sessions were sufficiently equal to have now only one common task as child
            
            if (entry.getValue().size() != 1) {
                //new TaskTreeEncoder().encode(entry.getValue(), System.out, excludes);
                throw new RuntimeException("flattened sessions were not combined as expected");
            }
            
            if (replacementTask == null) {
                replacementTask = entry.getValue().get(0).getTask();
            }
            else if (replacementTask != entry.getValue().get(0).getTask()) {
                throw new RuntimeException("two separate replacement tasks were calculated as " +
                                           "replacement, one for both tasks to be merged");
            }
            
            // <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
            // <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< TEST IMPLEMENTATION <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
            
            replacements.put(entry.getKey(), entry.getValue().get(0));
        }
        
        // >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
        // >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> TEST IMPLEMENTATION >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
        // ((Task) replacementTask).setDescription
        //     (replacementTask + " calculated as full replacement for " +
        //      similarTasks.getLeftHandSide() + " and " + similarTasks.getRightHandSide());
    
        int allInstances = similarTasks.getLeftHandSide().getInstances().size() +
            similarTasks.getRightHandSide().getInstances().size();
        
        if (replacements.size() != allInstances) {
            throw new RuntimeException("number of replacements does not match number of instances");
        }
        
        /*if (replacements.size() > 0) {
            System.out.println("replacement task is calculated to be: ");
            new TaskTreeEncoder().encode(replacements.values().iterator().next().getTask(),
                                         System.out);
        }*/
        
        // <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
        // <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< TEST IMPLEMENTATION <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<

        // create also replacements for potential parent iterations or optionals
        IIteration harmonizedIteration = taskFactory.createNewIteration();
        taskBuilder.setMarkedTask(harmonizedIteration, replacementTask);
        
        IOptional harmonizedOptional = taskFactory.createNewOptional();
        taskBuilder.setMarkedTask(harmonizedOptional, replacementTask);
        
        for (IUserSession session : appData.getSessions()) {
            replaceTaskInstances(session, replacements, similarTasks,
                                 harmonizedIteration, harmonizedOptional);
            
            // several subsequent instances, which had formerly different tasks, may now have the
            // same. Hence, they need to be merged. But as everything else would be way too complex,
            // we only perform the merge, if they occur next to each other on the same level
            mergeSubsequentIdenticalMarkingTemporalRelationships(session);
        }
        
        
        // >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
        // >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> TEST IMPLEMENTATION >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
        if (replacements.size() != 0) {
            for (Map.Entry<ITaskInstance, ITaskInstance> entry : replacements.entrySet()) {
                System.out.println
                    ("did not replace instance " + entry.getKey() + " with " + entry.getValue());
            }
            
            throw new RuntimeException();
        }
        // <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
        // <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< TEST IMPLEMENTATION <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
    }

    /**
     * 
     */
    private List<FlattenInstruction> getFlattenInstructions(SimilarTasks        similarTasks,
                                                            RuleApplicationData appData)
    {
        TaskTraversal leftHandSideTraversal = similarTasks.getLeftHandSideTraversal();
        TaskTraversal rightHandSideTraversal = similarTasks.getRightHandSideTraversal();
        
        List<FlattenInstruction> result = new LinkedList<FlattenInstruction>();
        TaskComparator comp = identTaskHandlStrat.getTaskComparator();
        
        // first create instructions for the deltas
        for (Delta delta : similarTasks.getPatch().getDeltas()) {
            if ((delta.getType() == Delta.TYPE.INSERT) ||
                (delta.getType() == Delta.TYPE.DELETE))
            {
                // System.out.println("handling " + delta.getType());
                Chunk chunk;
                TaskPath insertAfterPath = null;
                TaskPath insertBeforePath;
                
                if (delta.getType() == Delta.TYPE.INSERT) {
                    chunk = delta.getRevised();
                    int pos = delta.getOriginal().getPosition();
                    // System.out.println(" position " + pos);
                    
                    if (pos > 0) {
                        insertAfterPath = leftHandSideTraversal.getTraversalPaths()[pos - 1];
                    }
                    insertBeforePath = leftHandSideTraversal.getTraversalPaths()[pos];
                }
                else {
                    chunk = delta.getOriginal();
                    int pos = delta.getRevised().getPosition();
                    if (pos > 0) {
                        insertAfterPath = rightHandSideTraversal.getTraversalPaths()[pos - 1];
                    }
                    insertBeforePath = rightHandSideTraversal.getTraversalPaths()[pos];
                }
                
                ITask child = getTaskForChunk(chunk, appData);
                IOptional optional;
                
                if (child instanceof IOptional) {
                    optional = (IOptional) child;
                }
                else {
                    optional = taskFactory.createNewOptional();
                    taskBuilder.setMarkedTask(optional, child);
                    // ((Task) optional).setDescription(optional.getDescription() +
                    //                                  " created for " + delta.getType());
                    optional = (IOptional) appData.ensureUnique(optional);
                    createReplacementInstructions(chunk, optional, null, result);
                }

                // create a flatten instruction for the non-occurrence of the optional
                result.add(new FlattenInstruction(insertAfterPath, insertBeforePath, optional));
                
            }
            else if (delta.getType() == Delta.TYPE.CHANGE) {
                ITask child1;
                ITask child2;
                
                // check, if the change covers the whole traversal. If so reuse the root task.
                // Otherwise, create intermediate tasks if required representing both sides
                // of changes
                if ((delta.getOriginal().getPosition() == 0) &&
                    (delta.getOriginal().size() == similarTasks.getLeftHandSideTraversal().size()))
                {
                    child1 = similarTasks.getLeftHandSide();
                }
                else {
                    child1 = getTaskForChunk(delta.getOriginal(), appData);
                }
                
                if ((delta.getRevised().getPosition() == 0) &&
                    (delta.getRevised().size() == similarTasks.getRightHandSideTraversal().size()))
                {
                    child2 = similarTasks.getRightHandSide();
                }
                else {
                    child2 = getTaskForChunk(delta.getRevised(), appData);
                }
                
                // check if either of the variants is an iteration or optional of the respective
                // other variant. If so, ensure, that the iteration or optional are preserved
                ITask markedTask1 = (child1 instanceof IMarkingTemporalRelationship) ?
                    ((IMarkingTemporalRelationship) child1).getMarkedTask() : null;
                
                ITask markedTask2 = (child2 instanceof IMarkingTemporalRelationship) ?
                    ((IMarkingTemporalRelationship) child2).getMarkedTask() : null;
                
                if (comp.equals(markedTask1, child2)) {
                    if (child1 instanceof IOptional) {
                        createReplacementInstructions
                            (delta.getRevised(), (IOptional) child1, null, result);
                    }
                    else {
                        throw new java.lang.UnsupportedOperationException("not implemented yet");
                    }
                }
                else if (comp.equals(markedTask2, child1)) {
                    if (child2 instanceof IOptional) {
                        createReplacementInstructions
                            (delta.getOriginal(), (IOptional) child2, null, result);
                    }
                    else {
                        throw new java.lang.UnsupportedOperationException("not implemented yet");
                    }
                }
                else if ((markedTask1 != null) && (comp.equals(markedTask1, markedTask2))) {
                    throw new java.lang.UnsupportedOperationException("not implemented yet");
                }
                else {
                    // its time to create a selection of both variants. If one is already
                    // a selection, it is reused and extended, if required
                    ITask expectedChild1 = null;
                    ITask expectedChild2 = null;
                    
                    ISelection selection = null;
                    if (child1 instanceof ISelection) {
                        selection = (ISelection) child1;
                    }
                
                    if (child2 instanceof ISelection) {
                        if (selection == null) {
                            // only child 2 is a selection --> extend it with child 1
                            selection = (ISelection) child2;
                            addSelectionChildIfRequired(selection, child1);
                            expectedChild1 = child1;
                        }
                        else {
                            // both are selections --> extend child 1 with variants of child2
                            for (ITask child : ((ISelection) child2).getChildren()) {
                                addSelectionChildIfRequired(selection, child);
                            }
                        }
                    }
                    else if (selection != null) {
                        // only child 1 is a selection --> extend it with child 2
                        addSelectionChildIfRequired(selection, child2);
                        expectedChild2 = child2;
                    }
                    else if (selection == null) {
                        // none of both is already a selection, so create a new one with both
                        // of the children as variants
                        selection = taskFactory.createNewSelection();
                        // ((Task) selection).setDescription(selection.getDescription() +
                        //                                   " created for " + delta.getType());
                        taskBuilder.addChild(selection, child1);
                        taskBuilder.addChild(selection, child2);
                        expectedChild1 = child1;
                        expectedChild2 = child2;
                    }

                    selection = (ISelection) appData.ensureUnique(selection);
                
                    createReplacementInstructions
                        (delta.getOriginal(), selection, expectedChild1, result);
                    createReplacementInstructions
                        (delta.getRevised(), selection, expectedChild2, result);
                }
            }
        }
        
        // create instructions to harmonize marking temporal relationships for untraversed tasks
        int leftHandSideIndex = 0;
        int rightHandSideIndex = 0;
        
        OUTER:
        while (leftHandSideIndex < leftHandSideTraversal.getTraversalPaths().length) {
            for (Delta delta : similarTasks.getPatch().getDeltas()) {
                if (delta.getOriginal().getPosition() == leftHandSideIndex) {
                    if (delta.getType() == Delta.TYPE.INSERT) {
                        rightHandSideIndex += delta.getRevised().size();
                        // do not continue OUTER to ensure, that the left hand side and the 
                        // right hand side coming directly after the insert are handled
                    }
                    else if (delta.getType() == Delta.TYPE.DELETE) {
                        leftHandSideIndex += delta.getOriginal().size();
                        continue OUTER;
                    }
                    else if (delta.getType() == Delta.TYPE.CHANGE) {
                        leftHandSideIndex += delta.getOriginal().size();
                        rightHandSideIndex += delta.getRevised().size();
                        continue OUTER;
                    }
                }
            }
            
            TaskPath leftPath = leftHandSideTraversal.getTraversalPaths()[leftHandSideIndex];
            TaskPath rightPath = rightHandSideTraversal.getTraversalPaths()[rightHandSideIndex];
            
            if (comp.equals(leftPath.getLast(), rightPath.getLast())) {
                if (leftPath.getTask(leftPath.size() - 2) instanceof IOptional) {
                    IOptional optional = (IOptional) leftPath.getTask(leftPath.size() - 2);
                    result.add
                        (new FlattenInstruction(leftPath.subPath(0, leftPath.size()), optional));

                    result.add(new FlattenInstruction(rightPath, optional));
                }
                else if (rightPath.getTask(rightPath.size() - 2) instanceof IOptional) {
                    IOptional optional = (IOptional) rightPath.getTask(rightPath.size() - 2);
                    result.add
                        (new FlattenInstruction(rightPath.subPath(0, rightPath.size()), optional));

                    result.add(new FlattenInstruction(leftPath, optional));
                }
            }
            
            leftHandSideIndex++;
            rightHandSideIndex++;
        }
        
        
        // then create instructions for what stays the same
        OUTER:
        for (TaskPath path : leftHandSideTraversal.getTraversalPaths()) {
            for (FlattenInstruction instruction : result) {
                if (instruction.matches(path)) {
                    continue OUTER;
                }
            }
            
            result.add(new FlattenInstruction(path));
        }

        OUTER:
        for (TaskPath path : rightHandSideTraversal.getTraversalPaths()) {
            for (FlattenInstruction instruction : result) {
                if (instruction.matches(path)) {
                    continue OUTER;
                }
            }
            
            result.add(new FlattenInstruction(path));
        }

        return result;
    }

    /**
     *
     */
    private void addSelectionChildIfRequired(ISelection selection, ITask child) {
        for (ITask candidate : selection.getChildren()) {
            if (identTaskHandlStrat.getTaskComparator().equals(candidate, child)) {
                return;
            }
        }
        
        taskBuilder.addChild(selection, child);
    }

    /**
     *
     */
    private ITask getTaskForChunk(Chunk chunk, RuleApplicationData appData) {
        if (chunk.size() == 1) {
            TaskPath path = (TaskPath) chunk.getLines().get(0);
            return path.getTask(path.size() - 1);
        }
        else {
            ISequence task = taskFactory.createNewSequence();
            // ((Task) task).setDescription(task.getDescription() +
            //                              " created to represent a chunk");

            for (Object pathObj : chunk.getLines()) {
                TaskPath path = (TaskPath) pathObj;
                taskBuilder.addChild(task, path.getLast());
            }
            
            return appData.ensureUnique(task);
        }
    }

    /**
     *
     */
    private void createReplacementInstructions(Chunk                    chunk,
                                               ITask                    replacement,
                                               ITask                    selectedChild,
                                               List<FlattenInstruction> result)
    {
        // create a flatten instruction for the occurrence of the replacement
        for (Object pathObj : chunk.getLines()) {
            TaskPath path = (TaskPath) pathObj;
            
            if (replacement instanceof IOptional) {
                result.add(new FlattenInstruction(path, (IOptional) replacement));
            }
            else if (replacement instanceof ISelection) {
                result.add
                    (new FlattenInstruction(path, (ISelection) replacement, selectedChild));
            }
        }
    }

    /**
     *
     */
    private void flattenInstances(ITask                            task,
                                  List<FlattenInstruction>         flattenInstructions,
                                  Map<ITaskInstance, IUserSession> flattenedSessions,
                                  List<TaskPath>                   excludes)
    {
        //int i = 0;
        for (ITaskInstance instance : task.getInstances()) {
            /*System.out.println("flattening instance " + i++ + " of task " + task);
            new TaskTreeEncoder().encode(instance, System.out, excludes);*/
            
            TaskPath taskPath = new TaskPath();
            taskPath.add(instance.getTask(), 0);
            IUserSession session = taskFactory.createUserSession();
            flattenInstance(instance, taskPath, flattenInstructions, session,
                            new LinkedList<TaskPath>());
            
            //new TaskTreeEncoder().encode(session, System.out, excludes);
            
            flattenedSessions.put(instance, session);
        }
    }

    /**
     *
     */
    private void flattenInstance(ITaskInstance            instance,
                                 TaskPath                 taskPath,
                                 List<FlattenInstruction> flattenInstructions,
                                 IUserSession             session,
                                 List<TaskPath>           previousPaths)
    {
        boolean instructionApplied = false;
        
        TaskComparator comp = identTaskHandlStrat.getTaskComparator();
        
        //System.out.println("applying instructions on " + taskPath);
        
        for (FlattenInstruction instruction : flattenInstructions) {
            if (instruction.matches(taskPath)) {
                //System.out.print("found instruction ");
                //instruction.dump(System.out);
                
                switch (instruction.getInstruction()) {
                    case DONT_TRAVERSE: {
                        if (instance != null) {
                            taskBuilder.addTaskInstance(session, instance);
                        }
                        instructionApplied = true;
                        break;
                    }
                    case MAKE_OPTIONAL: {
                        instructionApplied = true;

                        if (instance == null) {
                            break;
                        }
                        
                        IOptional optional = instruction.getOptional();

                        if (comp.equals(optional, instance.getTask())) {
                            // the instance is already an instance of the correct optional --> reuse 
                            taskBuilder.addTaskInstance(session, instance);
                        }
                        else if (comp.equals(optional.getMarkedTask(), instance.getTask())) {
                            IOptionalInstance optionalInstance =
                                taskFactory.createNewTaskInstance(optional);
                            taskBuilder.setChild(optionalInstance, instance);
                            taskBuilder.addTaskInstance(session, optionalInstance);
                        }
                        else if (optional.getMarkedTask() instanceof ISequence) {
                            // first check, if the instance was already created, if not create it
                            ISequenceInstance sequenceInstance = ensureSequenceChildInstanceFor
                                (optional, (ISequence) optional.getMarkedTask(), session);

                            taskBuilder.addChild(sequenceInstance, instance);
                        }
                        break;
                    }
                    case MAKE_SELECTION: {
                        instructionApplied = true;

                        if (instance == null) {
                            break;
                        }
                        
                        ISelection selection = instruction.getSelection();

                        if (comp.equals(instruction.getSelectedChild(), instance.getTask())) {
                            ISelectionInstance selectionInstance =
                                taskFactory.createNewTaskInstance(selection);
                            taskBuilder.setChild(selectionInstance, instance);
                            taskBuilder.addTaskInstance(session, selectionInstance);
                        }
                        else if (instruction.getSelectedChild() == null) {
                            // both variants were already selections. They will have been merged.
                            // Hence we can reuse the child instances of the existing selection
                            // instances.
                            if (comp.equals(instance.getTask(), selection)) {
                                taskBuilder.addTaskInstance(session, instance);
                            }
                            else {
                                ISelectionInstance selectionInstance =
                                    taskFactory.createNewTaskInstance(selection);
                                taskBuilder.setChild(selectionInstance,
                                                     ((ISelectionInstance) instance).getChild());
                                taskBuilder.addTaskInstance(session, selectionInstance);
                                
                                taskBuilder.discardTaskInstance(instance);
                            }
                        }
                        else if (instruction.getSelectedChild() instanceof ISequence) {
                            // first check, if the instance was already created, if not create it
                            ISequenceInstance sequenceInstance = ensureSequenceChildInstanceFor
                                (selection, (ISequence) instruction.getSelectedChild(),  session);

                            taskBuilder.addChild(sequenceInstance, instance);
                        }

                        break;
                    }
                    case INTEGRATE_OPTIONAL: {
                        TaskPath previousPath = previousPaths.size() > 0 ?
                            previousPaths.get(previousPaths.size() - 1) : null;
                        
                        if (pathsMatch(instruction.getPrecedingPath(), previousPath)) {
                            IOptional optional = instruction.getOptional();
                            IOptionalInstance optionalInstance =
                                    taskFactory.createNewTaskInstance(optional);
                            taskBuilder.addTaskInstance(session, optionalInstance);
                        }
                        
                        if (instance != null) {
                            taskBuilder.addTaskInstance(session, instance);
                        }
                        
                        instructionApplied = true;
                        break;
                    }
                    default : {
                        throw new RuntimeException("unknown instruction type");
                    }
                }
            }
            
            if (instructionApplied) {
                break;
            }
        }
        
        if (!instructionApplied) {
            ITask task = taskPath.getLast();
            if (task instanceof IIteration) {
                taskPath.add(((IIteration) task).getMarkedTask(), 0);
                
                if (instance != null) {
                    for (ITaskInstance child : (IIterationInstance) instance) {
                        flattenInstance
                            (child, taskPath, flattenInstructions, session, previousPaths);
                    }
                }
                else {
                    flattenInstance(null, taskPath, flattenInstructions, session, previousPaths);
                }
                
                taskPath.removeLast();
            }
            else if (task instanceof ISequence) {
                List<ITask> children = ((ISequence) task).getChildren();
                for (int i = 0; i < children.size(); i++) {
                    ITaskInstance child = null;
                    if (instance != null) {
                        child = ((ISequenceInstance) instance).get(i);
                    }
                    taskPath.add(children.get(i), i);
                    flattenInstance
                        (child, taskPath, flattenInstructions, session, previousPaths);
                    taskPath.removeLast();
                }
            }
            else if (task instanceof ISelection) {
                if (instance != null) {
                    taskPath.add(((ISelectionInstance) instance).getChild().getTask(), 0);
                    flattenInstance(((ISelectionInstance) instance).getChild(), taskPath,
                                    flattenInstructions, session, previousPaths);
                    taskPath.removeLast();
                }
                else {
                    // check if the selection has any child for which a rule must be considered
                    List<ITask> children = ((ISelection) task).getChildren();
                    for (int i = 0; i < children.size(); i++) {
                        taskPath.add(children.get(i), i);
                        flattenInstance
                            (null, taskPath, flattenInstructions, session, previousPaths);
                        taskPath.removeLast();
                    }
                }
            }
            else if (task instanceof IOptional) {
                taskPath.add(((IOptional) task).getMarkedTask(), 0);
                ITaskInstance child = null;
                if (instance != null) {
                    child = ((IOptionalInstance) instance).getChild();
                }
                flattenInstance(child, taskPath, flattenInstructions, session, previousPaths);
                taskPath.removeLast();
                
                if ((instance != null) && (child == null)) {
                    // add the empty optional instance
                    taskBuilder.addTaskInstance(session, instance);
                    previousPaths.add(new TaskPath(taskPath));
                }
            }
            else if (instance != null) {
                taskBuilder.addTaskInstance(session, instance);
                previousPaths.add(new TaskPath(taskPath));
            }
        }
        else {
            previousPaths.add(new TaskPath(taskPath));
        }
    }

    /**
     *
     */
    private ISequenceInstance ensureSequenceChildInstanceFor(ITask        replacement,
                                                             ISequence    expectedChildSequence,
                                                             IUserSession session)
    {
        // first check, if there is already an instance of the expected sequence. If so, check if
        // its child is a sequence instance. If not create a new task instance with an appropriate
        // sequence instance
        ITaskInstance prevInstance =
            session.size() > 0 ? session.get(session.size() - 1) : null;
        
        ISequenceInstance sequenceInstance = null;
        
        if ((prevInstance != null) &&
            (identTaskHandlStrat.getTaskComparator().equals(prevInstance.getTask(), replacement)))
        {
            if ((prevInstance instanceof IOptionalInstance) &&
                (((IOptionalInstance) prevInstance).getChild() instanceof ISequenceInstance))
            {
                sequenceInstance =
                    (ISequenceInstance) ((IOptionalInstance) prevInstance).getChild();
            }
            else if ((prevInstance instanceof ISelectionInstance) &&
                    (((ISelectionInstance) prevInstance).getChild() instanceof ISequenceInstance))
            {
                sequenceInstance =
                    (ISequenceInstance) ((ISelectionInstance) prevInstance).getChild();
            }
        }
        
        // although we found a sequence instance as expected, this instance might already be fully
        // created and a new (iterated) one must be created. Check for it and handle correctly
        if ((sequenceInstance != null) &&
            (sequenceInstance.size() == expectedChildSequence.getChildren().size()))
        {
            sequenceInstance = null;
        }
        
        if (sequenceInstance == null) {
            //System.out.println("creating new sequence instance of selected child");
            sequenceInstance = taskFactory.createNewTaskInstance(expectedChildSequence);
                
            ITaskInstance replacementInstance = null;
            
            if (replacement instanceof IOptional) {
                replacementInstance = taskFactory.createNewTaskInstance((IOptional) replacement);
                taskBuilder.setChild((IOptionalInstance) replacementInstance, sequenceInstance);
            }
            else if (replacement instanceof ISelection) {
                
                /*System.out.println("replacement: ");
                new TaskTreeEncoder().encode(replacement, System.out);
                
                System.out.println("expectedChild: ");
                new TaskTreeEncoder().encode(expectedChildSequence, System.out);*/
                
                replacementInstance = taskFactory.createNewTaskInstance((ISelection) replacement);
                taskBuilder.setChild((ISelectionInstance) replacementInstance, sequenceInstance);
            }
            
            taskBuilder.addTaskInstance(session, replacementInstance);
        }
        
        return sequenceInstance;
    }

    /**
     *
     */
    private void replaceTaskInstances(ITaskInstanceList                 taskInstanceList,
                                      Map<ITaskInstance, ITaskInstance> replacements,
                                      SimilarTasks                      similarTasks,
                                      IIteration                        harmonizedIteration,
                                      IOptional                         harmonizedOptional)
    {
        for (int i = 0; i < taskInstanceList.size(); i++) {
            ITaskInstance childInstance = taskInstanceList.get(i);
            ITaskInstance replacement = replacements.remove(childInstance);
            
            if (replacement != null) {
                
                // update the model for sequences (others are updated in the calling method)
                if (taskInstanceList instanceof ISequenceInstance) {
                    ISequence task = ((ISequenceInstance) taskInstanceList).getSequence();
                    taskBuilder.setChild(task, i, replacement.getTask());
                }
                
                // perform the actual replacement and throw away the instance
                taskBuilder.setTaskInstance(taskInstanceList, i, replacement);
                TaskPath path = new TaskPath();
                path.add(childInstance.getTask(), 0);
                discardTaskInstancesNotBelongingToTraversals(childInstance, path, similarTasks);
            }
            else {
                ITask modelUpdate = replaceTaskInstances(childInstance, replacements, similarTasks,
                                                         harmonizedIteration, harmonizedOptional);
                
                if (modelUpdate != null) {
                    if (taskInstanceList instanceof ISequenceInstance) {
                        taskBuilder.setChild
                            (((ISequenceInstance) taskInstanceList).getSequence(), i, modelUpdate);
                    }
                }
            }
        }
    }

    /**
     *
     */
    private void replaceTaskInstances(IOptionalInstance                 optionalInstance,
                                      Map<ITaskInstance, ITaskInstance> replacements,
                                      SimilarTasks                      similarTasks,
                                      IIteration                        harmonizedIteration,
                                      IOptional                         harmonizedOptional)
    {
        ITaskInstance childInstance = optionalInstance.getChild();
        
        if (childInstance != null) {
            ITaskInstance replacement = replacements.remove(childInstance);
            
            if (replacement != null) {
                // do not update the model --> is updated in the calling method
                
                // perform the actual replacement and throw away the instance
                taskBuilder.setChild(optionalInstance, replacement);
                TaskPath path = new TaskPath();
                path.add(childInstance.getTask(), 0);
                discardTaskInstancesNotBelongingToTraversals(childInstance, path, similarTasks);
            }
            else {
                ITask modelUpdate = replaceTaskInstances(childInstance, replacements, similarTasks,
                                                         harmonizedIteration, harmonizedOptional);
                
                if (modelUpdate != null) {
                    taskBuilder.setMarkedTask(optionalInstance.getOptional(), modelUpdate);
                }
            }
        }
    }

    /**
     *
     */
    private void replaceTaskInstances(ISelectionInstance                selectionInstance,
                                      Map<ITaskInstance, ITaskInstance> replacements,
                                      SimilarTasks                      similarTasks,
                                      IIteration                        harmonizedIteration,
                                      IOptional                         harmonizedOptional)
    {
        TaskComparator comparator = identTaskHandlStrat.getTaskComparator();
        
        ITaskInstance childInstance = selectionInstance.getChild();
        
        if (childInstance != null) {
            ITaskInstance replacement = replacements.remove(childInstance);
            
            if (replacement != null) {
                
                if (replacement instanceof ISelectionInstance) {
                    taskBuilder.discardTaskInstance(replacement);
                    replacement = ((ISelectionInstance) replacement).getChild();
                }
                
                // update the model
                // we replace all instances of the merged tasks with instances of a new task.
                // hence, we also have to remove the task of the replaced children from the
                // available variants of the selection
                taskBuilder.removeChild(selectionInstance.getSelection(), childInstance.getTask());

                boolean found = false;
                for (ITask child : selectionInstance.getSelection().getChildren()) {
                    if (comparator.equals(child, replacement.getTask())) {
                        found = true;
                        break;
                    }
                }
                
                if (!found) {
                    taskBuilder.addChild(selectionInstance.getSelection(), replacement.getTask());
                }
                
                // perform the actual replacement and throw away the instance
                taskBuilder.setChild(selectionInstance, replacement);
                TaskPath path = new TaskPath();
                path.add(childInstance.getTask(), 0);
                discardTaskInstancesNotBelongingToTraversals(childInstance, path, similarTasks);
            }
            else {
                ITask modelUpdate = replaceTaskInstances(childInstance, replacements, similarTasks,
                                                         harmonizedIteration, harmonizedOptional);
                
                if (modelUpdate != null) {
                    taskBuilder.removeChild
                        (selectionInstance.getSelection(), childInstance.getTask());

                    boolean found = false;
                    for (ITask child : selectionInstance.getSelection().getChildren()) {
                        if (comparator.equals(child, modelUpdate)) {
                            found = true;
                            break;
                        }
                    }
                    
                    if (!found) {
                        taskBuilder.addChild(selectionInstance.getSelection(), modelUpdate);
                    }
                }
            }
        }
    }

    /**
     *
     */
    private ITask replaceTaskInstances(ITaskInstance                     childInstance,
                                       Map<ITaskInstance, ITaskInstance> replacements,
                                       SimilarTasks                      similarTasks,
                                       IIteration                        harmonizedIteration,
                                       IOptional                         harmonizedOptional)
    {
        ITask modelUpdate = null;
        
        if (childInstance instanceof IIterationInstance) {
            ITask markedTask = ((IIterationInstance) childInstance).getIteration().getMarkedTask();
            
            if ((markedTask == similarTasks.getLeftHandSide()) ||
                (markedTask == similarTasks.getRightHandSide()))
            {
                taskBuilder.setTask(childInstance, harmonizedIteration);
                modelUpdate = harmonizedIteration;
            }

            replaceTaskInstances((ITaskInstanceList) childInstance, replacements, similarTasks,
                                 harmonizedIteration, harmonizedOptional);
        }
        else if (childInstance instanceof IOptionalInstance) {
            ITask markedTask = ((IOptionalInstance) childInstance).getOptional().getMarkedTask();
            
            if ((markedTask == similarTasks.getLeftHandSide()) ||
                (markedTask == similarTasks.getRightHandSide()))
            {
                taskBuilder.setTask(childInstance, harmonizedOptional);
                modelUpdate = harmonizedOptional;
            }
            
            replaceTaskInstances((IOptionalInstance) childInstance, replacements, similarTasks,
                                 harmonizedIteration, harmonizedOptional);
        }
        else if (childInstance instanceof ISelectionInstance) {
            replaceTaskInstances((ISelectionInstance) childInstance, replacements, similarTasks,
                                 harmonizedIteration, harmonizedOptional);
        }
        else if (childInstance instanceof ISequenceInstance) {
            replaceTaskInstances((ITaskInstanceList) childInstance, replacements, similarTasks,
                                 harmonizedIteration, harmonizedOptional);
        }
        
        return modelUpdate;
    }

    /**
     * 
     */
    private void discardTaskInstancesNotBelongingToTraversals(ITaskInstance instance,
                                                              TaskPath      pathToInstance,
                                                              SimilarTasks  similarTasks)
    {
        boolean discarded = false;
        for (TaskPath candidate : similarTasks.getLeftHandSideTraversal().getTraversalPaths()) {
            if (candidate.size() > pathToInstance.size()) {
                TaskPath potentialEqualSubPath = candidate.subPath(0, pathToInstance.size());
                if (pathsMatch(potentialEqualSubPath, pathToInstance)) {
                    taskBuilder.discardTaskInstance(instance);
                    discarded = true;
                    break;
                }
            }
        }
        
        if (!discarded) {
            for (TaskPath candidate : similarTasks.getRightHandSideTraversal().getTraversalPaths()) {
                if (candidate.size() > pathToInstance.size()) {
                    TaskPath potentialEqualSubPath = candidate.subPath(0, pathToInstance.size());
                    if (pathsMatch(potentialEqualSubPath, pathToInstance)) {
                        taskBuilder.discardTaskInstance(instance);
                        discarded = true;
                        break;
                    }
                }
            }
        }
        
        if (discarded) {
            // now also discard the children
            if (instance instanceof ISequenceInstance) {
                int index = 0;
                for (ITaskInstance childInstance : (ITaskInstanceList) instance) {
                    pathToInstance.add(childInstance.getTask(), index++);
                    discardTaskInstancesNotBelongingToTraversals
                        (childInstance, pathToInstance, similarTasks);
                    pathToInstance.removeLast();
                }
            }
            else if (instance instanceof IIterationInstance) {
                for (ITaskInstance childInstance : (ITaskInstanceList) instance) {
                    pathToInstance.add(childInstance.getTask(), 0);
                    discardTaskInstancesNotBelongingToTraversals
                        (childInstance, pathToInstance, similarTasks);
                    pathToInstance.removeLast();
                }
            }
            else if (instance instanceof IOptionalInstance) {
                ITaskInstance childInstance = ((IOptionalInstance) instance).getChild();
                if (childInstance != null) {
                    pathToInstance.add(childInstance.getTask(), 0);
                    discardTaskInstancesNotBelongingToTraversals
                        (childInstance, pathToInstance, similarTasks);
                    pathToInstance.removeLast();
                }
            }
            else if (instance instanceof ISelectionInstance) {
                ITaskInstance childInstance = ((ISelectionInstance) instance).getChild();
                pathToInstance.add(childInstance.getTask(), 0);
                discardTaskInstancesNotBelongingToTraversals
                    (childInstance, pathToInstance, similarTasks);
                pathToInstance.removeLast();
            }
        }
    }
    
    /**
     *
     */
    private void mergeSubsequentIdenticalMarkingTemporalRelationships(ITaskInstanceList list) {
        int index = 0;
        TaskComparator comparator = identTaskHandlStrat.getTaskComparator();
        
        while (index < (list.size() - 1)) {
            ITaskInstance instance1 = list.get(index);
            ITaskInstance instance2 = list.get(index + 1);
            
            if (comparator.equals(instance1.getTask(), instance2.getTask())) {
                if (instance1 instanceof IIterationInstance) {
                    // add the children of the second to the first iteration instance and discard
                    // the second
                    for (ITaskInstance child : (IIterationInstance) instance2) {
                        taskBuilder.addChild((IIterationInstance) instance1, child); 
                    }
                    
                    taskBuilder.removeTaskInstance(list, index + 1);
                    taskBuilder.discardTaskInstance(instance2);
                }
                else if (instance1 instanceof IOptionalInstance) {
                    ITaskInstance optionalChildInstance1 =
                        ((IOptionalInstance) instance1).getChild();
                    ITaskInstance optionalChildInstance2 =
                            ((IOptionalInstance) instance2).getChild();
                        
                    if (optionalChildInstance1 == null) {
                        // independent of the second, just remove the first. The second will be the
                        // unique representation
                        taskBuilder.removeTaskInstance(list, index);
                    }
                    else if (optionalChildInstance2 == null) {
                        // remove the second. The first will be the unique representation
                        taskBuilder.removeTaskInstance(list, index + 1);
                    }
                    else if (optionalChildInstance1 instanceof IIterationInstance) {
                        // add all children of the second optional iteration instance to the
                        // first and discard the second
                        for (ITaskInstance child : (IIterationInstance) optionalChildInstance2) {
                            taskBuilder.addChild
                                ((IIterationInstance) optionalChildInstance1, child); 
                        }
                        
                        taskBuilder.removeTaskInstance(list, index + 1);
                        taskBuilder.discardTaskInstance(instance2);
                    }
                    else {
                        // both optional children are no iterations --> create an iteration
                        // for them and add them both as children.
                        throw new java.lang.UnsupportedOperationException("not implemented yet");
                    }
                }
                else {
                    index++;
                }
            }
            else {
                index++;
            }
        }
        
        for (ITaskInstance child : list) {
            if (child instanceof ITaskInstanceList) {
                mergeSubsequentIdenticalMarkingTemporalRelationships((ITaskInstanceList) child);
            }
        }
    }
    
    /**
     *
     */
    private static boolean pathsMatch(TaskPath path1, TaskPath path2) {
        if (path1 == null) {
            return path2 == null;
        }
        else if ((path2 != null) && (path1.size() == path2.size())) {
            for (int i = 0; i < path1.size(); i++) {
                if (!path1.get(i).equals(path2.get(i))) {
                    return false;
                }
            }
            return true;
        }
        else {
            return false;
        }
    }

    /**
     *
     */
    /*private boolean containsNewTask(ITask task, RuleApplicationData appData) {
        if (appData.isSelfCreatedTask(task)) {
            return true;
        }
        else if (task instanceof IStructuringTemporalRelationship) {
            for (ITask child : ((IStructuringTemporalRelationship) task).getChildren()) {
                if (containsNewTask(child, appData)) {
                    return true;
                }
            }
        }
        else if (task instanceof IMarkingTemporalRelationship) {
            return containsNewTask(((IMarkingTemporalRelationship) task).getMarkedTask(), appData);
        }
        
        return false;
    }*/

    /**
     * 
     */
    private class RuleApplicationData {

        /**
         * 
         */
        private List<IUserSession> sessions;
        
        /**
         * 
         */
        private ITaskModel taskModel;

        /**
         * 
         */
        private MostSimilarTaskDeterminer mostSimilarTasksDeterminer =
            new MostSimilarTaskDeterminer(identTaskHandlStrat.getTaskComparator());
        
        /**
         * 
         */
        private List<SimilarTasks> mostSimilarTasks;
        
        /**
         * 
         */
        private List<ITask> newTasks = new LinkedList<ITask>();
        
        /**
         * 
         */
        private RuleApplicationResult ruleApplicationResult = new RuleApplicationResult();
        
        /**
         * 
         */
        private RuleApplicationData(List<IUserSession> sessions) {
            this.sessions = sessions;
        }

        /**
         *
         */
        boolean isSelfCreatedTask(ITask task) {
            for (ITask candidate : newTasks) {
                if (candidate == task) {
                    return true;
                }
            }
            
            return false;
        }

        /**
         * @return the mostSimilarTasksDeterminer
         */
        private MostSimilarTaskDeterminer getMostSimilarTasksDeterminer() {
            return mostSimilarTasksDeterminer;
        }

        /**
         *
         */
        private void markAsAlreadyCondensed(ITask task1, ITask task2) {
            mostSimilarTasksDeterminer.addComparisonToSkip(task1, task2);
        }

        /**
         *
         */
        private RuleApplicationResult finalizeRuleApplicationResult() {
            for (ITask newTask : newTasks) {
                ruleApplicationResult.addNewlyCreatedTask(newTask);
                
                if (newTask instanceof IOptional) {
                    if (isSelfCreatedTask(((IOptional) newTask).getMarkedTask()) &&
                        (((IOptional) newTask).getMarkedTask() instanceof ISequence))
                    {
                        ruleApplicationResult.addNewlyCreatedTask
                            (((IOptional) newTask).getMarkedTask());
                    }
                }
                else if (newTask instanceof ISelection) {
                    for (ITask child : ((ISelection) newTask).getChildren()) {
                        if (isSelfCreatedTask(child) && (child instanceof ISequence)) {
                            ruleApplicationResult.addNewlyCreatedTask(child);
                        }
                    }
                }
            }
            
            
            return ruleApplicationResult;
        }

        /**
         * @return the tree
         */
        private List<IUserSession> getSessions() {
            return sessions;
        }

        /**
         * @return the taskModel
         */
        private ITaskModel getTaskModel() {
            return taskModel;
        }

        /**
         * @param taskModel the taskModel to set
         */
        private void setTaskModel(ITaskModel taskModel) {
            this.taskModel = taskModel;
        }

        /**
         * @return the orderedDiffLevels
         */
        private List<SimilarTasks> getMostSimilarTasks() {
            return mostSimilarTasks;
        }

        /**
         * @param orderedDiffLevels the orderedDiffLevels to set
         */
        private void setMostSimilarTasks(List<SimilarTasks> mostSimilarTasks) {
            this.mostSimilarTasks = mostSimilarTasks;
        }
        
        /**
         * 
         */
        private ITask ensureUnique(ITask task) {
            // replacements done in this rule are either optionals or selections. So focus on them
            if (task instanceof IOptional) {
                for (ITask newTask : newTasks) {
                    if (newTask instanceof IOptional) {
                        ITask child1 = ((IOptional) task).getMarkedTask();
                        ITask child2 = ((IOptional) newTask).getMarkedTask();
                        if (createdChildEquals(child1, child2)) {
                            // System.out.println("reusing optional " + newTask + " for " + task);
                            return newTask;
                        }
                    }
                }
            }
            else if (task instanceof ISelection) {
                for (ITask newTask : newTasks) {
                    if (newTask instanceof ISelection) {
                        List<ITask> children1 = ((ISelection) task).getChildren();
                        List<ITask> children2 = ((ISelection) newTask).getChildren();
                        if (createdSelectionChildrenEqual(children1, children2)) {
                            /*System.out.println("reusing selection " + newTask + " for " + task);
                            
                            System.out.println("---------------------------- existing task");
                            new TaskTreeEncoder().encode(newTask, System.out);
                            
                            System.out.println("---------------------------- completely new task");
                            new TaskTreeEncoder().encode(task, System.out);*/
                            
                            return newTask;
                        }
                    }
                }
            }
            else if (task instanceof ISequence) {
                List<ISequence> allRelevant = new ArrayList<>();
                
                for (ITask candidate : newTasks) {
                    if (candidate instanceof ISequence) {
                        allRelevant.add((ISequence) candidate);
                    }
                }
                
                for (ITask candidate : taskModel.getTasks()) {
                    if (candidate instanceof ISequence) {
                        allRelevant.add((ISequence) candidate);
                    }
                }
                
                for (ISequence candidate : allRelevant) {
                    List<ITask> children1 = ((ISequence) task).getChildren();
                    List<ITask> children2 = ((ISequence) candidate).getChildren();

                    boolean equal = false;
                    if (children1.size() == children2.size()) {
                        equal = true;
                        for (int i = 0; i < children1.size(); i++) {
                            if (children1.get(i) != children2.get(i)) {
                                equal = false;
                                break;
                            }
                        }
                    }

                    if (equal) {
                        // System.out.println("reusing sequence " + candidate + " for " + task);
                        return candidate;
                    }
                }
            }
            
            newTasks.add(task);
            
            return task;
        }

        /**
         *
         */
        private boolean createdSelectionChildrenEqual(List<ITask> children1, List<ITask> children2) {
            if (children1.size() != children2.size()) {
                return false;
            }
            
            for (ITask child1 : children1) {
                boolean found = false;
                
                for (ITask child2 : children2) {
                    if (createdChildEquals(child1, child2)) {
                        found = true;
                        break;
                    }
                }
                
                if (!found) {
                    return false;
                }
            }
            
            return true;
        }

        /**
         *
         */
        private boolean createdChildEquals(ITask child1, ITask child2) {
            if (child1 == child2) {
                return true;
            }
            else if (!isSelfCreatedTask(child1) && !isSelfCreatedTask(child2)) {
                // the simple comparison can not work if the tasks are not self created
                return false;
            }
            else if ((child1 instanceof ISequence) && (child2 instanceof ISequence)) {
                ISequence sequence1 = (ISequence) child1;
                ISequence sequence2 = (ISequence) child2;
                
                if (sequence1.getChildren().size() != sequence2.getChildren().size()) {
                    return false;
                }
                
                for (int i = 0; i < sequence1.getChildren().size(); i++) {
                    if (sequence1.getChildren().get(i) != sequence2.getChildren().get(i)) {
                        return false;
                    }
                }
                
                return true;
            }
            else {
                return false;
            }
        }
    }
    
    /**
     * 
     */
    private static class FlattenInstruction {
        
        /**
         * 
         */
        private enum Instruction { DONT_TRAVERSE, MAKE_OPTIONAL, MAKE_SELECTION, INTEGRATE_OPTIONAL };

        /** */
        private TaskPath path;

        /** */
        private TaskPath precedingPath;

        /** */
        private Instruction instruction;

        /** */
        private IOptional optional = null;

        /** */
        private ISelection selection = null;

        /** */
        private ITask selectedChild = null;

        /**
         * 
         */
        private FlattenInstruction(TaskPath path) {
            this.path = path;
            this.instruction = Instruction.DONT_TRAVERSE;
        }

        /**
         * 
         */
        private FlattenInstruction(TaskPath path, IOptional optional) {
            this.path = path;
            this.instruction = Instruction.MAKE_OPTIONAL;
            this.optional = optional;
        }

        /**
         * 
         */
        private FlattenInstruction(TaskPath path, ISelection selection, ITask selectedChild) {
            this.path = path;
            this.instruction = Instruction.MAKE_SELECTION;
            this.selection = selection;
            this.selectedChild = selectedChild;
        }

        /**
         * 
         */
        private FlattenInstruction(TaskPath  precedingPath,
                                   TaskPath  path,
                                   IOptional optional)
        {
            this.path = path;
            this.precedingPath = precedingPath;
            this.instruction = Instruction.INTEGRATE_OPTIONAL;
            this.optional = optional;
        }
        
        /**
         * 
         */
        IOptional getOptional() {
            return optional;
        }


        /**
         * @return the selection
         */
        ISelection getSelection() {
            return selection;
        }

        /**
         * @return the selectedChild
         */
        ITask getSelectedChild() {
            return selectedChild;
        }

        /**
         * @return the instruction
         */
        Instruction getInstruction() {
            return instruction;
        }

        /**
         * @return the precedingPath
         */
        TaskPath getPrecedingPath() {
            return precedingPath;
        }

        /**
         *
         */
        boolean matches(TaskPath path) {
            return pathsMatch(this.path, path);
        }
        

//        /**
//         *
//         */
//        void dump(PrintStream out) {
//            for (int i = 0; i < path.size(); i++) {
//                out.print("-->");
//                out.print(path.getTask(i).getId());
//                out.print('(');
//                out.print(path.get(i).getIndex());
//                out.print(')');
//            }
//            
//            out.print("  ");
//            out.print(instruction);
//           
//            out.println();
//        }
        
    }

}