Changeset 1982

Timestamp:

06/30/15 10:26:24 (9 years ago)

Author:

pharms

Message:

• no merging if mergable level of similarity is 100 --> a selection of both tasks to be merged would be created
• reuse of intermediary tasks also for merge results if identical
• selections having themselves as direct of indirect child will not be created --> merging aborted
• harmonizations of marking temporal relationships for merged sequences
• integration of single iterations if a merged sequence is iterated somewhere
• detection of repetitions of identical tasks that became identical due to merging
• removal or sequences that have only one child

File:

• trunk/autoquest-core-tasktrees/src/main/java/de/ugoe/cs/autoquest/tasktrees/temporalrelation/CondenseSimilarTasksRule.java (modified) (16 diffs)

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

@@ -28 +28 @@
 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;
@@ -45 +46 @@
 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;
@@ -194 +196 @@
             
             /*mergecount++;
-            if ((mergecount > 140) && ((mergecount % 20) == 0)) {
+            System.out.println(mergecount);
+            if ((mergecount % 20) == 0) {
                 System.out.println("performing validation " + mergecount);
-                new TaskTreeValidator().validate(appData.getTaskModel().getUserSessions(), true);
+                new de.ugoe.cs.autoquest.tasktrees.temporalrelation.utils.TaskTreeValidator()
+                    .validate(appData.getTaskModel().getUserSessions(), true);
             }*/
-            
             
             appData.setMostSimilarTasks(null);
@@ -235 +238 @@
             }
             
-            harmonizeMarkingTemporalRelationships(sessions);
+            harmonizeModel(sessions, appData.getTaskModel());
         }
         while (appData.getMostSimilarTasks() != null);
@@ -284 +287 @@
      *
      */
-    private void harmonizeMarkingTemporalRelationships(List<IUserSession> sessions) {
-        final Map<ITask, IIteration> harmonizedIterations = new HashMap<>();
-        final Map<ITask, IOptional> harmonizedOptionals = new HashMap<>();
-        
-        for (IUserSession session : sessions) {
-            for (ITaskInstance instance : session) {
-                instance.accept(new DefaultTaskInstanceTraversingVisitor() {
-                    
-                    @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);
-                        }
-                        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);
-                        }
-                        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();
-                            
-                            boolean foundOtherInstanceWithOldChild = false;
-                            
-                            for (ITaskInstance instance : selection.getInstances()) {
-                                ITask child = ((ISelectionInstance) instance).getChild().getTask();
-                                
-                                if (child == childTaskBeforeUpdate) {
-                                    foundOtherInstanceWithOldChild = true;
-                                    break;
-                                }
-                            }
-                            
-                            if (!foundOtherInstanceWithOldChild) {
-                                taskBuilder.removeChild(selection, childTaskBeforeUpdate);
-                            }
-                            
-                            // remove and add the child to ensure to have it only once
-                            taskBuilder.removeChild(selection, childTaskAfterUpdate);
-                            taskBuilder.addChild(selection, childTaskAfterUpdate);
-                        }
-                    }
-
-                    @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);
-                            }
-                            
-                            childIndex++;
-                        }
-                    }
-                    
-                });
-
-            }
-            
-            // several subsequent instances, which had formerly different tasks, may now have
-            // the same. Hence, they need to be merged. But as everything else would be way too
-            // complex, we only perform the merge, if they occur next to each other on the
-            // same level
-            mergeSubsequentIdenticalMarkingTemporalRelationships(session);
-        }
+    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);
     }
 
@@ -477 +386 @@
             (similarTasks, identTaskHandlStrat.getTaskComparator());
         
-        if (similarTasks == null) {
+        if ((similarTasks == null) || (similarTasks.getDiffLevel() == 100)) {
             // this may happen, if no mergable level of similarity can be found
             return;
@@ -486 +395 @@
         List<FlattenInstruction> flattenInstructions =
             getFlattenInstructions(similarTasks, appData);
+        
+        if (flattenInstructions == null) {
+            // we cannot merge this
+            return;
+        }
         
         // for (FlattenInstruction instruction : flattenInstructions) {
@@ -572 +486 @@
         }
         
-        /*if (replacements.size() > 0) {
+        /*if (replacementTask != null) {
             System.out.println("replacement task is calculated to be: ");
-            new TaskTreeEncoder().encode(replacements.values().iterator().next().getTask(),
-                                         System.out);
+            new de.ugoe.cs.autoquest.tasktrees.temporalrelation.utils.TaskTreeEncoder().encode
+                (replacementTask, System.out);
         }*/
         
@@ -581 +495 @@
         // <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< 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()) {
@@ -760 +682 @@
                                 else if (selection.getChildren().contains(child2)) {
                                     existingChildTask = child2;
-                               }
+                                }
                                 
                                 if (existingChildTask != null) {
@@ -812 +734 @@
                         }
                     }
-
+                    
+                    // 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);
@@ -907 +853 @@
      */
     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)) {
@@ -1098 +1049 @@
                             // first check, if the instance was already created, if not create it
                             ISequenceInstance sequenceInstance = ensureSequenceChildInstanceFor
-                                (selection, (ISequence) instruction.getSelectedChild(),  session);
+                                (selection, (ISequence) instruction.getSelectedChild(), session);
 
                             taskBuilder.addChild(sequenceInstance, instance);
@@ -1469 +1420 @@
         }
     }
-    
-    /**
-     *
-     */
-    private void mergeSubsequentIdenticalMarkingTemporalRelationships(ITaskInstanceList list) {
-        int index = 0;
-        TaskComparator comparator = identTaskHandlStrat.getTaskComparator();
-        
-        while (index < (list.size() - 1)) {
-            ITaskInstance instance1 = list.get(index);
-            ITaskInstance instance2 = list.get(index + 1);
-            
-            if (comparator.equals(instance1.getTask(), instance2.getTask())) {
-                if (instance1 instanceof IIterationInstance) {
-                    // add the children of the second to the first iteration instance and discard
-                    // the second
-                    for (ITaskInstance child : (IIterationInstance) instance2) {
-                        taskBuilder.addChild((IIterationInstance) instance1, child); 
-                    }
-                    
-                    taskBuilder.removeTaskInstance(list, index + 1);
-                    taskBuilder.discardTaskInstance(instance2);
-                }
-                else if (instance1 instanceof IOptionalInstance) {
-                    ITaskInstance optionalChildInstance1 =
-                        ((IOptionalInstance) instance1).getChild();
-                    ITaskInstance optionalChildInstance2 =
-                            ((IOptionalInstance) instance2).getChild();
-                        
-                    if (optionalChildInstance1 == null) {
-                        // independent of the second, just remove the first. The second will be the
-                        // unique representation
-                        taskBuilder.removeTaskInstance(list, index);
-                    }
-                    else if (optionalChildInstance2 == null) {
-                        // remove the second. The first will be the unique representation
-                        taskBuilder.removeTaskInstance(list, index + 1);
-                    }
-                    else if (optionalChildInstance1 instanceof IIterationInstance) {
-                        // add all children of the second optional iteration instance to the
-                        // first and discard the second
-                        for (ITaskInstance child : (IIterationInstance) optionalChildInstance2) {
-                            taskBuilder.addChild
-                                ((IIterationInstance) optionalChildInstance1, child); 
-                        }
-                        
-                        taskBuilder.removeTaskInstance(list, index + 1);
-                        taskBuilder.discardTaskInstance(instance2);
-                    }
-                    else {
-                        // both optional children are no iterations --> create an iteration
-                        // for them and add them both as children.
-                        throw new java.lang.UnsupportedOperationException("not implemented yet");
-                    }
-                }
-                else {
-                    index++;
-                }
-            }
-            else {
-                index++;
-            }
-        }
-        
-        for (ITaskInstance child : list) {
-            if (child instanceof ITaskInstanceList) {
-                mergeSubsequentIdenticalMarkingTemporalRelationships((ITaskInstanceList) child);
-            }
-        }
-    }
-    
+
     /**
      *
@@ -1559 +1440 @@
         }
     }
-
-    /**
-     *
-     */
-    /*private boolean containsNewTask(ITask task, RuleApplicationData appData) {
-        if (appData.isSelfCreatedTask(task)) {
-            return true;
-        }
-        else if (task instanceof IStructuringTemporalRelationship) {
-            for (ITask child : ((IStructuringTemporalRelationship) task).getChildren()) {
-                if (containsNewTask(child, appData)) {
-                    return true;
-                }
-            }
-        }
-        else if (task instanceof IMarkingTemporalRelationship) {
-            return containsNewTask(((IMarkingTemporalRelationship) task).getMarkedTask(), appData);
-        }
-        
-        return false;
-    }*/
+    
+    /**
+     * 
+     */
+    private 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);
+        }
+
+    }
 
     /**
@@ -1983 +1864 @@
     }
 
+    /**
+     * 
+     */
+    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);
+        }
+    }
 }