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

//   Copyright 2012 Georg-August-Universität Göttingen, Germany
//
//   Licensed under the Apache License, Version 2.0 (the "License");
//   you may not use this file except in compliance with the License.
//   You may obtain a copy of the License at
//
//       http://www.apache.org/licenses/LICENSE-2.0
//
//   Unless required by applicable law or agreed to in writing, software
//   distributed under the License is distributed on an "AS IS" BASIS,
//   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
//   See the License for the specific language governing permissions and
//   limitations under the License.

package de.ugoe.cs.autoquest.tasktrees.temporalrelation;

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.DefaultTaskInstanceTraversingVisitor;
import de.ugoe.cs.autoquest.tasktrees.treeifc.IEventTask;
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.autoquest.tasktrees.treeifc.TaskTreeUtils;
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);
        //int mergecount = 0;
        
        do {
            appData.setTaskModel(taskFactory.createTaskModel(sessions));
            
            /*mergecount++;
            System.out.println(mergecount);
            if ((mergecount % 20) == 0) {
                System.out.println("performing validation " + mergecount);
                new de.ugoe.cs.autoquest.tasktrees.temporalrelation.utils.TaskTreeValidator()
                    .validate(appData.getTaskModel().getUserSessions(), true);
            }*/
            
            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());
                }
            }
            
            harmonizeModel(sessions, appData.getTaskModel());
        }
        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 harmonizeModel(List<IUserSession> sessions, ITaskModel model) {
        boolean somethingChanged;
        
        do {
            // harmonize marking temporal relationships
            MarkingTemporalRelationshipHarmonizer harmonizer =
                new MarkingTemporalRelationshipHarmonizer();
        
            for (IUserSession session : sessions) {
                for (ITaskInstance instance : session) {
                    instance.accept(harmonizer);
                }
            }
            
            // integrate iterations performed once for children that were somewhere iterated more
            // than once
            SingleIterationExecutionsIntegrator integrator =
                new SingleIterationExecutionsIntegrator(harmonizer.harmonizedIterations);

            for (IUserSession session : sessions) {
                for (ITaskInstance instance : session) {
                    instance.accept(integrator);
                }
            }
            
            // search for sequences having subsequent identical children (may be the result
            // of merging two subsequent children)
            SubsequentIdenticalChildrenMerger merger = new SubsequentIdenticalChildrenMerger();
            for (ITask task : model.getTasks()) {
                merger.mergeSubsequentIdenticalTasks(task);
            }
            
            for (IUserSession session : sessions) {
                merger.mergeSubsequentIdenticalInstances(session);
            }
            
            somethingChanged = harmonizer.somethingChanged || integrator.somethingChanged ||
                merger.somethingChanged;
                    
        }
        while(somethingChanged);
    }

    /**
     *
     */
    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) || (similarTasks.getDiffLevel() == 100)) {
            // this may happen, if no mergable level of similarity can be found
            return;
        }
        
        // similarTasks.dump(System.out);

        List<FlattenInstruction> flattenInstructions =
            getFlattenInstructions(similarTasks, appData);
        
        if (flattenInstructions == null) {
            // we cannot merge this
            return;
        }
        
        // 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, 0).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 (replacementTask != null) {
            System.out.println("replacement task is calculated to be: ");
            new de.ugoe.cs.autoquest.tasktrees.temporalrelation.utils.TaskTreeEncoder().encode
                (replacementTask, System.out);
        }*/
        
        // <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
        // <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< TEST IMPLEMENTATION <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<

        ITask uniqueReplacement = appData.ensureUnique(replacementTask);
        
        if (uniqueReplacement != replacementTask) {
            System.out.println("updating task instances with a unified replacement task");
            for (ITaskInstance replacement : replacements.values()) {
                taskBuilder.setTask(replacement, uniqueReplacement);
            }
        }

        for (IUserSession session : appData.getSessions()) {
            replaceTaskInstances(session, replacements, similarTasks);
        }
        
        
        // >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
        // >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> 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) {
                        // it may also be the case, that one is a child of a selection and occurs
                        // only as such and nowhere else. Then the parent selection is reused and
                        // extended.
                        for (ITask candidate : appData.taskModel.getTasks()) {
                            if (candidate instanceof ISelection) {
                                selection = (ISelection) candidate;
                                ITask existingChildTask = null;
                                
                                if (selection.getChildren().contains(child1)) {
                                    existingChildTask = child1;
                                }
                                else if (selection.getChildren().contains(child2)) {
                                    existingChildTask = child2;
                                }
                                
                                if (existingChildTask != null) {
                                    int noOfInstances = 0;
                                    
                                    for (ITaskInstance instance : selection.getInstances()) {
                                        ITaskInstance childInstance =
                                            ((ISelectionInstance) instance).getChild();
                                            
                                        if (childInstance.getTask() == existingChildTask) {
                                            noOfInstances++;
                                        }
                                    }
                                    
                                    if (noOfInstances < existingChildTask.getInstances().size()) {
                                        // not all instances of the existing child task are covered
                                        // by the parent selection. Hence, throw selection away and
                                        // search for another one
                                        selection = null;
                                    }
                                    else {
                                        // found a parent selection --> reuse it but add the new
                                        // variant
                                        if (child1 == existingChildTask) {
                                            addSelectionChildIfRequired(selection, child2);
                                        }
                                        else {
                                            addSelectionChildIfRequired(selection, child1);
                                        }
                                        expectedChild1 = child1;
                                        expectedChild2 = child2;
                                        break;
                                    }
                                }
                                else {
                                    selection = null;
                                }
                            }
                        }
                        
                        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;
                        }
                    }
                    
                    // tasks that refer to themselves are not valid. But due to the creation of
                    // selections, this may happen. This must be prevented
                    /*final Set<ITask> tasks = new HashSet<ITask>();
                    
                    try {
                        selection.accept(new DefaultTaskTraversingVisitor() {
                            @Override
                            public void visit(ITask task) {
                                if (!tasks.contains(task)) {
                                    tasks.add(task);
                                    super.visit(task);
                                }
                                else {
                                    throw new RuntimeException("tasks refers to itself");
                                }
                            }
                        });
                    }
                    catch (RuntimeException e) {
                        // a task refers to itself
                        return null;
                    }*/
                    
                    // the new selection does not refer to itself, no apply it
                    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.getInstruction() != FlattenInstruction.Instruction.INTEGRATE_OPTIONAL) &&
                    (instruction.matches(path)))
                {
                    continue OUTER;
                }
            }
            
            result.add(new FlattenInstruction(path));
        }

        OUTER:
        for (TaskPath path : rightHandSideTraversal.getTraversalPaths()) {
            for (FlattenInstruction instruction : result) {
                if ((instruction.getInstruction() != FlattenInstruction.Instruction.INTEGRATE_OPTIONAL) &&
                    (instruction.matches(path)))
                {
                    continue OUTER;
                }
            }
            
            result.add(new FlattenInstruction(path));
        }

        return result;
    }

    /**
     *
     */
    private void addSelectionChildIfRequired(ISelection selection, ITask child) {
        if (TaskTreeUtils.isChild(selection, child)) {
            System.out.println(selection);
            System.out.println(child);
            throw new RuntimeException("child of selection has selection itself as 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)
    {
        
        TaskComparator comp = identTaskHandlStrat.getTaskComparator();
        
        // System.out.println("applying integrate optional instructions on " + taskPath);
        
        for (FlattenInstruction instruction : flattenInstructions) {
            if ((instruction.getInstruction() == FlattenInstruction.Instruction.INTEGRATE_OPTIONAL) &&
                (instruction.matches(taskPath)))
            {
                // System.out.print("found instruction ");
                // instruction.dump(System.out);
                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);
                }
                
                break;
            }
        }
        
        boolean instanceHandled = false;
        // System.out.println("applying other 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);
                        }
                        instanceHandled = true;
                        break;
                    }
                    case MAKE_OPTIONAL: {
                        instanceHandled = 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: {
                        instanceHandled = 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: {
                        // have been applied beforehand
                        break;
                    }
                    default : {
                        throw new RuntimeException("unknown instruction type");
                    }
                }
            }
            
            if (instanceHandled) {
                break;
            }
        }
        
        if (!instanceHandled) {
            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)
    {
        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());
                }
                else if (taskInstanceList instanceof IIterationInstance) {
                    IIteration task = ((IIterationInstance) taskInstanceList).getIteration();
                    taskBuilder.setMarkedTask(task, 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 {
                replaceTaskInstances(childInstance, replacements, similarTasks);
            }
        }
    }

    /**
     *
     */
    private void replaceTaskInstances(IOptionalInstance                 optionalInstance,
                                      Map<ITaskInstance, ITaskInstance> replacements,
                                      SimilarTasks                      similarTasks)
    {
        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.setMarkedTask(optionalInstance.getOptional(), replacement.getTask());
                taskBuilder.setChild(optionalInstance, replacement);
                TaskPath path = new TaskPath();
                path.add(childInstance.getTask(), 0);
                discardTaskInstancesNotBelongingToTraversals(childInstance, path, similarTasks);
            }
            else {
                replaceTaskInstances(childInstance, replacements, similarTasks);
            }
        }
    }

    /**
     *
     */
    private void replaceTaskInstances(ISelectionInstance                selectionInstance,
                                      Map<ITaskInstance, ITaskInstance> replacements,
                                      SimilarTasks                      similarTasks)
    {
        TaskComparator comparator = identTaskHandlStrat.getTaskComparator();
        
        ITaskInstance childInstance = selectionInstance.getChild();
        
        if (childInstance != null) {
            ITaskInstance replacement = replacements.remove(childInstance);
            
            if (replacement != null) {
                
                if (replacement instanceof ISelectionInstance) {
                    // if the replacement itself is a selection instance, we cannot add
                    // a selection instance as the child of the parent selection instance.
                    // therefore, we just use the child of the replacement as new child of the
                    // existing selection instance
                    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 {
                replaceTaskInstances(childInstance, replacements, similarTasks);
            }
        }
    }

    /**
     *
     */
    private void replaceTaskInstances(ITaskInstance                     childInstance,
                                      Map<ITaskInstance, ITaskInstance> replacements,
                                      SimilarTasks                      similarTasks)
    {
        if (childInstance instanceof IIterationInstance) {
            replaceTaskInstances((ITaskInstanceList) childInstance, replacements, similarTasks);
        }
        else if (childInstance instanceof IOptionalInstance) {
            replaceTaskInstances((IOptionalInstance) childInstance, replacements, similarTasks);
        }
        else if (childInstance instanceof ISelectionInstance) {
            replaceTaskInstances((ISelectionInstance) childInstance, replacements, similarTasks);
        }
        else if (childInstance instanceof ISequenceInstance) {
            replaceTaskInstances((ITaskInstanceList) childInstance, replacements, similarTasks);
        }
    }

    /**
     * 
     */
    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 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 void removeSelectionChildIfNotUsedAnymoreInInstances(ISelection selection, ITask child) {
        boolean foundOtherInstanceWithChild = false;
        
        for (ITaskInstance instance : selection.getInstances()) {
            ITask candidate = ((ISelectionInstance) instance).getChild().getTask();
            
            if (candidate == child) {
                foundOtherInstanceWithChild = true;
                break;
            }
        }
        
        if (!foundOtherInstanceWithChild) {
            taskBuilder.removeChild(selection, child);
        }

    }

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

    /**
     * 
     */
    private class MarkingTemporalRelationshipHarmonizer
        extends DefaultTaskInstanceTraversingVisitor
    {
        /** */
        final Map<ITask, IIteration> harmonizedIterations = new HashMap<>();
        
        /** */
        final Map<ITask, IOptional> harmonizedOptionals = new HashMap<>();
        
        /** */
        private boolean somethingChanged = false;
        
        /**
         * 
         */
        @Override
        public void visit(IIterationInstance iterationInstance) {
            // visit the children
            super.visit(iterationInstance);
            
            // there may have been a model update at the children. If so, set the
            // new marked task
            IIteration iteration = iterationInstance.getIteration();
            ITask newChildTask = iterationInstance.get(0).getTask();
            
            if (newChildTask != iteration.getMarkedTask()) {
                taskBuilder.setMarkedTask(iteration, newChildTask);
            }
            
            // check, if there is a harmonized iteration
            IIteration harmonizedIteration =
                harmonizedIterations.get(iteration.getMarkedTask());
            
            if ((harmonizedIteration != null) && (iteration != harmonizedIteration)) {
                // there is a harmonized iteration --> set it as new task
                /*System.out.println("harmonizing iteration of " +
                                   iteration.getMarkedTask() + " from " + iteration +
                                   " to " + harmonizedIteration);*/
                taskBuilder.setTask(iterationInstance, harmonizedIteration);
                somethingChanged = true;
            }
            else if (harmonizedIteration == null) {
                // remember this iteration as the harmonized one
                harmonizedIterations.put(iteration.getMarkedTask(), iteration);
            }
        }
        
        /**
         * 
         */
        @Override
        public void visit(IOptionalInstance optionalInstance) {
            // visit the children
            super.visit(optionalInstance);
            
            IOptional optional = optionalInstance.getOptional();

            if (optionalInstance.getChild() != null) {
                // there may have been a model update at the child. If so, set the
                // new marked task
                ITask newChildTask = optionalInstance.getChild().getTask();
                
                if (newChildTask != optional.getMarkedTask()) {
                    taskBuilder.setMarkedTask(optional, newChildTask);
                }
            }

            // check, if there is a harmonized optional
            IOptional harmonizedOptional =
                harmonizedOptionals.get(optional.getMarkedTask());

            if ((harmonizedOptional != null) && (optional != harmonizedOptional)) {
                // there is a harmonized optional --> set it as new task
                /*System.out.println("harmonizing optional of " +
                                   optional.getMarkedTask() + " from " + optional +
                                   " to " + harmonizedOptional);*/
                taskBuilder.setTask(optionalInstance, harmonizedOptional);
                somethingChanged = true;
            }
            else if (harmonizedOptional == null) {
                // remember this optional as the harmonized one
                harmonizedOptionals.put(optional.getMarkedTask(), optional);
            }
        }

        /**
         * 
         */
        @Override
        public void visit(ISelectionInstance selectionInstance) {
            ITask childTaskBeforeUpdate = selectionInstance.getChild().getTask();
            
            super.visit(selectionInstance);
            
            ITask childTaskAfterUpdate = selectionInstance.getChild().getTask();
            
            if (childTaskBeforeUpdate != childTaskAfterUpdate) {
                // update the selection model if required.
                ISelection selection = selectionInstance.getSelection();
                removeSelectionChildIfNotUsedAnymoreInInstances(selection, childTaskBeforeUpdate);
                
                // remove and add the child to ensure to have it only once
                taskBuilder.removeChild(selection, childTaskAfterUpdate);
                taskBuilder.addChild(selection, childTaskAfterUpdate);
                somethingChanged = true;
            }
        }

        /**
         * 
         */
        @Override
        public void visit(ISequenceInstance sequenceInstance) {
            ISequence sequence = sequenceInstance.getSequence();
            int childIndex = 0;
            
            for (ITaskInstance child : sequenceInstance) {
                child.accept(this);
                
                ITask newChildTask = child.getTask();
                
                if (sequence.getChildren().get(childIndex) != newChildTask) {
                    taskBuilder.setChild(sequenceInstance.getSequence(), childIndex,
                                         newChildTask);
                    somethingChanged = true;
                }
                
                childIndex++;
            }
        }
        
    }
    

    /**
     * 
     */
    private class SingleIterationExecutionsIntegrator
        extends DefaultTaskInstanceTraversingVisitor
    {

        /** */
        private Map<ITask, IIteration> iterations;
        
        /** */
        private boolean somethingChanged = false;

        /**
         *
         */
        public SingleIterationExecutionsIntegrator(Map<ITask, IIteration> iterations) {
            this.iterations = iterations;
        }

        /* (non-Javadoc)
         * @see DefaultTaskInstanceTraversingVisitor#visit(IOptionalInstance)
         */
        @Override
        public void visit(IOptionalInstance optionalInstance) {
            super.visit(optionalInstance);

            if (optionalInstance.getChild() != null) {
                IIteration iteration = iterations.get(optionalInstance.getChild().getTask());

                if (iteration != null) {
                    taskBuilder.setMarkedTask(optionalInstance.getOptional(), iteration);
                    IIterationInstance replacement = taskFactory.createNewTaskInstance(iteration);
                    taskBuilder.addChild(replacement, optionalInstance.getChild());
                    taskBuilder.setChild(optionalInstance, replacement);
                    somethingChanged = true;
                }
            }
        }

        /* (non-Javadoc)
         * @see DefaultTaskInstanceTraversingVisitor#visit(ISelectionInstance)
         */
        @Override
        public void visit(ISelectionInstance selectionInstance) {
            super.visit(selectionInstance);
            
            ITask usedChildTask = selectionInstance.getChild().getTask();
            IIteration iteration = iterations.get(usedChildTask);
            
            if (iteration != null) {
                // extend the selection model
                // remove and add the child to ensure to have it only once
                ISelection selection = selectionInstance.getSelection();
                taskBuilder.removeChild(selection, iteration);
                taskBuilder.addChild(selection, iteration);
                
                // update the instance
                IIterationInstance replacement = taskFactory.createNewTaskInstance(iteration);
                taskBuilder.addChild(replacement, selectionInstance.getChild());
                taskBuilder.setChild(selectionInstance, replacement);
                
                // update the selection model if required.
                removeSelectionChildIfNotUsedAnymoreInInstances(selection, usedChildTask);
                
                somethingChanged = true;
            }

        }

        /* (non-Javadoc)
         * @see DefaultTaskInstanceTraversingVisitor#visit(ISequenceInstance)
         */
        @Override
        public void visit(ISequenceInstance sequenceInstance) {
            int index = 0;
            while (index < sequenceInstance.size()) {
                ITaskInstance child = sequenceInstance.get(index);
                child.accept(this);
                
                IIteration iteration = iterations.get(child.getTask());
                
                if (iteration != null) {
                    taskBuilder.setChild(sequenceInstance.getSequence(), index, iteration);
                    IIterationInstance replacement = taskFactory.createNewTaskInstance(iteration);
                    taskBuilder.addChild(replacement, child);
                    taskBuilder.setTaskInstance(sequenceInstance, index, replacement);
                    somethingChanged = true;
                }
                
                index++;
            }
        }

    }

    /**
     * 
     */
    private class SubsequentIdenticalChildrenMerger {
        
        /** */
        private boolean somethingChanged = false;

        /**
         *
         */
        private void mergeSubsequentIdenticalTasks(ITask task) {
            TaskComparator comparator = identTaskHandlStrat.getTaskComparator();

            if (task instanceof ISequence) {
                // merge the children
                mergeSubsequentIdenticalTasks((ISequence) task);
                
                int index = 0;
                
                while (index < ((ISequence) task).getChildren().size()) {
                    ITask child = ((ISequence) task).getChildren().get(index);

                    List<ITaskInstance> childInstances = new LinkedList<>();
                    
                    for (ITaskInstance instance : task.getInstances()) {
                        ITaskInstance childInstance = ((ISequenceInstance) instance).get(index);
                        if (comparator.equals(childInstance.getTask(), child)) {
                            childInstances.add(childInstance);
                        }
                    }
                    
                    Map<ITaskInstance, ITaskInstance> childInstanceReplacements = new HashMap<>();
                    
                    ITask replacementTask =
                        getReplacements(child, childInstances, childInstanceReplacements);
                        
                    if (replacementTask != null) {
                        taskBuilder.setChild((ISequence) task, index, replacementTask);

                        for (ITaskInstance instance : task.getInstances()) {
                            ITaskInstance childInstance = ((ISequenceInstance) instance).get(index);
                            ITaskInstance replacement = childInstanceReplacements.get(childInstance);

                            if (replacement != null) {
                                taskBuilder.setTaskInstance
                                    ((ISequenceInstance) instance, index, replacement);
                            }
                        }
                        
                        somethingChanged = true;
                    }
                    
                    index++;
                }
            }
            else if (task instanceof ISelection) {
                // it could have children being marking temporal relationship of a sequence of
                // interest. If so, adapt the model and the instances
                int index = 0;
                
                while (index < ((ISelection) task).getChildren().size()) {
                    ITask child = ((ISelection) task).getChildren().get(index);
                    List<ITaskInstance> childInstances = new LinkedList<>();
                    
                    for (ITaskInstance instance : task.getInstances()) {
                        ITaskInstance childInstance = ((ISelectionInstance) instance).getChild();
                        if (comparator.equals(childInstance.getTask(), child)) {
                            childInstances.add(childInstance);
                        }
                    }
                    
                    Map<ITaskInstance, ITaskInstance> childInstanceReplacements = new HashMap<>();
                    
                    ITask replacementTask =
                        getReplacements(child, childInstances, childInstanceReplacements);
                    
                    if (replacementTask != null) {
                        taskBuilder.removeChild((ISelection) task, child);
                        taskBuilder.addChild((ISelection) task, replacementTask);

                        for (ITaskInstance instance : task.getInstances()) {
                            ITaskInstance childInstance = ((ISelectionInstance) instance).getChild();
                            ITaskInstance replacement = childInstanceReplacements.get(childInstance);

                            if (replacement != null) {
                                taskBuilder.setChild(((ISelectionInstance) instance), replacement);
                            }
                        }
                        
                        // start from the beginning as the children order may have changed
                        index = 0;
                        somethingChanged = true;
                    }
                    else {
                        index++;
                    }
                }
            }
        }

        /**
         *
         */
        private ITask getReplacements(ITask                             child,
                                      List<ITaskInstance>               childInstances,
                                      Map<ITaskInstance, ITaskInstance> childInstanceReplacements)
        {
            final TaskComparator comparator = identTaskHandlStrat.getTaskComparator();
            ITask candidate = child;
            boolean isOptional = false;
            
            while (candidate instanceof IMarkingTemporalRelationship) {
                if (candidate instanceof IOptional) {
                    isOptional = true;
                }
                candidate = ((IMarkingTemporalRelationship) candidate).getMarkedTask();
            }
            
            if ((candidate instanceof IEventTask) || (candidate instanceof ISelection) ||
                (((ISequence) candidate).getChildren().size() != 1))
            {
                // no sequence of interest as it has more than one children
                return null;
            }
            
            // found a sequence to be handled. The sequence has a single child and this will
            // be either an optional of an iteration of the single child, or an iteration of
            // the single child.
            final ISequence sequenceWithSingleChild = (ISequence) candidate;
            
            // determine all instances of the sequence rooted by the provided parent instance
            ITask singleChild = sequenceWithSingleChild.getChildren().get(0);
            IOptional optional = null;

            if (singleChild instanceof IOptional) {
                isOptional = true;
                optional = (IOptional) singleChild;
                singleChild = optional.getMarkedTask();
            }

            IIteration iteration = (IIteration) singleChild;

            if (isOptional && (optional == null)) {
                optional = taskFactory.createNewOptional();
                taskBuilder.setMarkedTask(optional, iteration);
            }

            for (ITaskInstance childInstance : childInstances) {
                // get all instances of the single child of the sequence of interest which belong to
                // the a child instance to be replaced and calculate a replacement
                final List<ITaskInstance> singleChildInstances = new LinkedList<>();
                final ITask taskToSearchFor = singleChild;
                
                childInstance.accept(new DefaultTaskInstanceTraversingVisitor() {
                    @Override
                    public void visit(ISelectionInstance selectionInstance) {
                        if (comparator.equals(selectionInstance.getTask(), taskToSearchFor)) {
                            singleChildInstances.add(selectionInstance);
                        }
                    }

                    @Override
                    public void visit(ISequenceInstance sequenceInstance) {
                        if (comparator.equals(sequenceInstance.getTask(), taskToSearchFor)) {
                            singleChildInstances.add(sequenceInstance);
                        }
                        else if (comparator.equals(sequenceInstance.getTask(),
                                                   sequenceWithSingleChild))
                        {
                            super.visit(sequenceInstance);
                        }
                    }
                    
                });
                
                IIterationInstance iterationInstance = taskFactory.createNewTaskInstance(iteration);
                for (ITaskInstance singleChildInstance : singleChildInstances) {
                    taskBuilder.addTaskInstance(iterationInstance, singleChildInstance);
                }
                
                ITaskInstance replacement = iterationInstance;
                
                if (isOptional) {
                    IOptionalInstance optionalInstance = taskFactory.createNewTaskInstance(optional);
                    taskBuilder.setChild(optionalInstance, replacement);
                    replacement = optionalInstance;
                }
                
                childInstanceReplacements.put(childInstance, replacement);
            }
            
            if (isOptional) {
                return optional;
            }
            else {
                return iteration;
            }
        }

        /**
         *
         */
        private void mergeSubsequentIdenticalTasks(ISequence sequence) {
            int index = 0;
            TaskComparator comparator = identTaskHandlStrat.getTaskComparator();
            
            while (index < (sequence.getChildren().size() - 1)) {
                ITask child1 = sequence.getChildren().get(index);
                ITask child2 = sequence.getChildren().get(index + 1);
                
                // get the actual first task
                ITask task1 = child1;
                
                while (task1 instanceof IMarkingTemporalRelationship) {
                    task1 = ((IMarkingTemporalRelationship) task1).getMarkedTask();
                }
                
                // get the actual second task
                ITask task2 = child2;
                
                while (task2 instanceof IMarkingTemporalRelationship) {
                    task2 = ((IMarkingTemporalRelationship) task2).getMarkedTask();
                }
                
                if (comparator.equals(task1, task2)) {
                    // determine if the task is optional
                    boolean isOptional = false;
                    
                    if (child1 instanceof IOptional) {
                        child1 = ((IOptional) child1).getMarkedTask();
                        isOptional = true;
                    }
                    
                    if (child2 instanceof IOptional) {
                        child2 = ((IOptional) child2).getMarkedTask();
                        isOptional = true;
                    }
                    
                    if (child1 instanceof IIteration) {
                        child1 = ((IIteration) child1).getMarkedTask();
                    }
                    
                    if (child2 instanceof IIteration) {
                        child2 = ((IIteration) child2).getMarkedTask();
                    }
                    
                    IIteration iteration = taskFactory.createNewIteration();
                    taskBuilder.setMarkedTask(iteration, task1);
                    
                    IOptional optional = null;
                    
                    if (isOptional) {
                        optional = taskFactory.createNewOptional();
                        taskBuilder.setMarkedTask(optional, iteration);
                        taskBuilder.setChild(sequence, index, optional);
                    }
                    else {
                        taskBuilder.setChild(sequence, index, iteration);
                    }
                    
                    taskBuilder.removeChild(sequence, index + 1);
                    
                    for (ITaskInstance instance : sequence.getInstances()) {
                        mergeSubsequentIdenticalInstances((ISequenceInstance) instance, index,
                                                          iteration, optional);
                    }
                    
                    somethingChanged = true;
                }
                else {
                    index++;
                }
            }
        }

        /**
         *
         */
        private void mergeSubsequentIdenticalInstances(ITaskInstanceList list) {
            int index = 0;
            TaskComparator comparator = identTaskHandlStrat.getTaskComparator();
            
            while (index < (list.size() - 1)) {
                boolean isOptional = false;
                ITaskInstance instance1 = list.get(index);
                ITaskInstance instance2 = list.get(index + 1);
                
                // get the actual first task
                ITask task1 = instance1.getTask();
                
                while (task1 instanceof IMarkingTemporalRelationship) {
                    if (task1 instanceof IOptional) {
                        isOptional = true;
                    }
                    
                    task1 = ((IMarkingTemporalRelationship) task1).getMarkedTask();
                }
                
                // get the actual second task
                ITask task2 = instance2.getTask();
                
                while (task2 instanceof IMarkingTemporalRelationship) {
                    if (task2 instanceof IOptional) {
                        isOptional = true;
                    }
                    
                    task2 = ((IMarkingTemporalRelationship) task2).getMarkedTask();
                }
                
                if (comparator.equals(task1, task2)) {
                    IIteration iteration = taskFactory.createNewIteration();
                    IOptional optional = null;
                    
                    if (isOptional) {
                        optional = taskFactory.createNewOptional();
                        taskBuilder.setMarkedTask(optional, iteration);
                    }
                    
                    mergeSubsequentIdenticalInstances(list, index, iteration, optional);
                }
                
                index++;
            }
        }
        
        /**
         *
         */
        private void mergeSubsequentIdenticalInstances(ITaskInstanceList list,
                                                       int               index,
                                                       IIteration        iteration,
                                                       IOptional         optional)
        {
            ITaskInstance instance1 = list.get(index);
            ITaskInstance instance2 = list.get(index + 1);
            List<ITaskInstance> equalInstances = new LinkedList<>();
            
            if (instance1 instanceof IOptionalInstance) {
                taskBuilder.discardTaskInstance(instance1);
                instance1 = ((IOptionalInstance) instance1).getChild();
            }
            
            if (instance2 instanceof IOptionalInstance) {
                taskBuilder.discardTaskInstance(instance2);
                instance2 = ((IOptionalInstance) instance2).getChild();
            }
            
            if (instance1 instanceof IIterationInstance) {
                for (ITaskInstance child : (IIterationInstance) instance1) {
                    equalInstances.add(child);
                }
                
                taskBuilder.discardTaskInstance(instance1);
            }
            else if (instance1 != null) {
                equalInstances.add(instance1);
            }
            
            if (instance2 instanceof IIterationInstance) {
                for (ITaskInstance child : (IIterationInstance) instance2) {
                    equalInstances.add(child);
                }
                
                taskBuilder.discardTaskInstance(instance2);
            }
            else if (instance2 != null) {
                equalInstances.add(instance2);
            }
            
            ITaskInstance replacement = taskFactory.createNewTaskInstance(iteration);
            
            for (ITaskInstance equalInstance : equalInstances) {
                taskBuilder.addChild((IIterationInstance) replacement, equalInstance);
            }
            
            if (optional != null) {
                IOptionalInstance optionalInstance = taskFactory.createNewTaskInstance(optional);
                
                taskBuilder.setChild(optionalInstance, replacement);
                replacement = optionalInstance;
            }
            
            taskBuilder.setTaskInstance(list, index, replacement);
            taskBuilder.removeTaskInstance(list, index + 1);
        }
    }
}