Changeset 1146 for trunk/autoquest-core-tasktrees/src/main/java/de/ugoe/cs/autoquest/tasktrees/temporalrelation/SequenceForTaskDetectionRule.java

Timestamp:

04/04/13 16:06:07 (11 years ago)

Author:

pharms

Message:

• complete refactoring of task tree model with a separation of task models and task instances
• appropriate adaptation of task tree generation process
• appropriate adaptation of commands and task tree visualization

File:

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

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

@@ -15 +15 @@
 package de.ugoe.cs.autoquest.tasktrees.temporalrelation;
 
+import java.util.HashMap;
 import java.util.Iterator;
 import java.util.LinkedList;
 import java.util.List;
 
-import de.ugoe.cs.autoquest.tasktrees.nodeequality.NodeEquality;
-import de.ugoe.cs.autoquest.tasktrees.nodeequality.NodeEqualityRuleManager;
+import de.ugoe.cs.autoquest.tasktrees.taskequality.TaskEquality;
+import de.ugoe.cs.autoquest.tasktrees.taskequality.TaskEqualityRuleManager;
+import de.ugoe.cs.autoquest.tasktrees.treeifc.IEventTask;
 import de.ugoe.cs.autoquest.tasktrees.treeifc.IIteration;
 import de.ugoe.cs.autoquest.tasktrees.treeifc.ISelection;
 import de.ugoe.cs.autoquest.tasktrees.treeifc.ISequence;
-import de.ugoe.cs.autoquest.tasktrees.treeifc.ITaskTreeBuilder;
-import de.ugoe.cs.autoquest.tasktrees.treeifc.ITaskTreeNode;
-import de.ugoe.cs.autoquest.tasktrees.treeifc.ITaskTreeNodeFactory;
+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.IUserSession;
+import de.ugoe.cs.autoquest.usageprofiles.SymbolComparator;
 import de.ugoe.cs.autoquest.usageprofiles.Trie;
 import de.ugoe.cs.autoquest.usageprofiles.TrieProcessor;
 import de.ugoe.cs.util.StopWatch;
-import de.ugoe.cs.util.console.Console;
 
 /**
@@ -39 +44 @@
  * @author Patrick Harms
  */
-class SequenceForTaskDetectionRule implements TemporalRelationshipRule {
+class SequenceForTaskDetectionRule implements ISessionScopeRule {
     
     /**
      * <p>
-     * the task tree node factory to be used for creating substructures for the temporal
+     * the task factory to be used for creating substructures for the temporal
      * relationships identified during rule
      * </p>
      */
-    private ITaskTreeNodeFactory taskTreeNodeFactory;
+    private ITaskFactory taskFactory;
     /**
      * <p>
-     * the task tree builder to be used for creating substructures for the temporal relationships
+     * the task builder to be used for creating substructures for the temporal relationships
      * identified during rule application
      * </p>
      */
-    private ITaskTreeBuilder taskTreeBuilder;
+    private ITaskBuilder taskBuilder;
 
     /**
      * <p>
-     * the node comparator to be used for comparing task tree nodes
+     * the task comparator to be used for comparing tasks
      * </p>
      */
-    private TaskTreeNodeComparator nodeComparator;
+    private TaskComparator taskComparator;
 
     /**
      * <p>
-     * instantiates the rule and initializes it with a node equality rule manager and the minimal
-     * node equality identified sublist must have to consider them as iterated.
+     * instantiates the rule and initializes it with a task equality rule manager and the minimal
+     * task equality identified sublist must have to consider them as iterated.
      * </p>
      */
-    SequenceForTaskDetectionRule(NodeEqualityRuleManager nodeEqualityRuleManager,
-                                 NodeEquality            minimalNodeEquality,
-                                 ITaskTreeNodeFactory    taskTreeNodeFactory,
-                                 ITaskTreeBuilder        taskTreeBuilder)
+    SequenceForTaskDetectionRule(TaskEqualityRuleManager taskEqualityRuleManager,
+                                 TaskEquality            minimalTaskEquality,
+                                 ITaskFactory            taskFactory,
+                                 ITaskBuilder            taskBuilder)
     {
-        this.taskTreeNodeFactory = taskTreeNodeFactory;
-        this.taskTreeBuilder = taskTreeBuilder;
-        
-        this.nodeComparator =
-            new TaskTreeNodeComparator(nodeEqualityRuleManager, minimalNodeEquality);
+        this.taskFactory = taskFactory;
+        this.taskBuilder = taskBuilder;
+        
+        this.taskComparator = new TaskComparator(taskEqualityRuleManager, minimalTaskEquality);
     }
 
@@ -89 +93 @@
     }
 
-    /*
-     * (non-Javadoc)
-     * 
-     * @see de.ugoe.cs.tasktree.temporalrelation.TemporalRelationshipRule#apply(TaskTreeNode,
-     * boolean)
+    /* (non-Javadoc)
+     * @see de.ugoe.cs.autoquest.tasktrees.temporalrelation.ISessionScopeRule#apply(java.util.List)
      */
     @Override
-    public RuleApplicationResult apply(ITaskTreeNode parent, boolean finalize) {
-        if (!(parent instanceof ISequence)) {
-            return null;
-        }
-
-        if (!finalize) {
-            // the rule is always feasible as tasks may occur at any time
-            RuleApplicationResult result = new RuleApplicationResult();
-            result.setRuleApplicationStatus(RuleApplicationStatus.FEASIBLE);
-            return result;
-        }
-
-        List<ITaskTreeNode> children = parent.getChildren();
-        List<ISequence> sessions = new LinkedList<ISequence>();
-        
-        for (ITaskTreeNode child : children) {
-            if (child instanceof ISequence) {
-                sessions.add((ISequence) child);
-            }
-            else {
-                Console.println("provided parent is no parent of sessions");
-                return null;
-            }
-        }
-        
+    public RuleApplicationResult apply(List<IUserSession> sessions) {
         RuleApplicationData appData = new RuleApplicationData(sessions);
 
-        boolean finished = false;
-        
         // this is the real rule application. Loop while something is replaced.
         do {
@@ -137 +112 @@
             appData.getStopWatch().stop("whole loop");
             
-            //((TaskTreeNodeComparator) nodeComparator).getStopWatch().dumpStatistics(System.out);
-            //((TaskTreeNodeComparator) nodeComparator).getStopWatch().reset();
+            //((TaskTreeNodeComparator) taskComparator).getStopWatch().dumpStatistics(System.out);
+            //((TaskTreeNodeComparator) taskComparator).getStopWatch().reset();
             
             appData.getStopWatch().dumpStatistics(System.out);
             appData.getStopWatch().reset();
             
-            finished = (appData.getReplacementCounter() == 0);
-        }
-        while (!finished);
-        
-        System.out.println("created " + appData.getResult().getNewlyCreatedParentNodes().size() +
-                           " new parent nodes\n");
-        
-        if (appData.getResult().getNewlyCreatedParentNodes().size() > 0) {
+        }
+        while (appData.detectedAndReplacedTasks());
+        
+        System.out.println
+            ("created " + appData.getResult().getNewlyCreatedTasks().size() +
+             " new tasks and " + appData.getResult().getNewlyCreatedTaskInstances().size() +
+             " appropriate instances\n");
+        
+        if ((appData.getResult().getNewlyCreatedTasks().size() > 0) ||
+            (appData.getResult().getNewlyCreatedTaskInstances().size() > 0))
+        {
             appData.getResult().setRuleApplicationStatus(RuleApplicationStatus.FINISHED);
         }
@@ -164 +142 @@
         appData.getStopWatch().start("detecting iterations");
         
-        List<ISequence> sessions = appData.getSessions();
-        int foundIterations = 0;
-        
-        for (ISequence session : sessions) {
-            foundIterations += detectAndReplaceIterations(session, appData);
-        }
+        List<IUserSession> sessions = appData.getSessions();
+        int iteratedTasks = 0;
+        
+        ITask iteratedTask = null;
+        
+        do {
+            iteratedTask = searchIteratedTask(sessions);
+            
+            if (iteratedTask != null) {
+                replaceIterationsOf(iteratedTask, sessions, appData);
+                iteratedTasks++;
+            }
+        }
+        while (iteratedTask != null);
         
         appData.getStopWatch().stop("detecting iterations");
-        System.out.println(" --> found " + foundIterations);
-    }
-
-    /**
-     * @param appData
-     */
-    private int detectAndReplaceIterations(ISequence           session,
-                                           RuleApplicationData appData)
+        System.out.println(" --> found " + iteratedTasks + " iterated tasks");
+    }
+
+    /**
+     *
+     */
+    private ITask searchIteratedTask(List<IUserSession> sessions) {
+        for (IUserSession session : sessions) {
+            for (int i = 0; i < (session.size() - 1); i++) {
+                if (taskComparator.equals(session.get(i).getTask(), session.get(i + 1).getTask())) {
+                    return session.get(i).getTask();
+                }
+            }
+        }
+        
+        return null;
+    }
+
+    /**
+     *
+     */
+    private void replaceIterationsOf(ITask               iteratedTask,
+                                     List<IUserSession>  sessions,
+                                     RuleApplicationData appData)
     {
-        int count = 0;
-        
-        TemporalRelationshipRule rule = new SimpleIterationDetectionRule
-            (nodeComparator, taskTreeNodeFactory, taskTreeBuilder);
-
-        RuleApplicationResult result = rule.apply(session, true);
-            
-        if ((result != null) && (result.getNewlyCreatedParentNodes() != null)) {
-            for (ITaskTreeNode newParent : result.getNewlyCreatedParentNodes()) {
-                appData.getResult().addNewlyCreatedParentNode(newParent);
-                if (newParent instanceof IIteration) {
-                    count++;
-                }
-            }
-        }
-        
-        return count;
+        IIteration iteration = taskFactory.createNewIteration();
+        ITaskInstance iterationInstance = null;
+        
+        List<ITaskInstance> iterationInstances = new LinkedList<ITaskInstance>();
+        
+        for (IUserSession session : sessions) {
+            int index = 0;
+            while (index < session.size()) {
+                if (taskComparator.equals(iteratedTask, session.get(index).getTask())) {
+                    if (iterationInstance == null) {
+                        iterationInstance = taskFactory.createNewTaskInstance(iteration);
+                        iterationInstances.add(iterationInstance);
+                        taskBuilder.addTaskInstance(session, index, iterationInstance);
+                        index++;
+                    }
+                    
+                    taskBuilder.addChild(iterationInstance, session.get(index));
+                    taskBuilder.removeTaskInstance(session, index);
+                }
+                else {
+                    if (iterationInstance != null) {
+                        iterationInstance = null;
+                    }
+                    index++;
+                }
+            }
+        }
+        
+        harmonizeIterationInstancesModel(iteration, iterationInstances);
+    }
+
+    /**
+     * <p>
+     * TODO: comment
+     * </p>
+     *
+     * @param iteratedTaskVariants
+     */
+    private void harmonizeIterationInstancesModel(IIteration          iteration,
+                                                  List<ITaskInstance> iterationInstances)
+    {
+        List<ITask> iteratedTaskVariants = new LinkedList<ITask>();
+        
+        // merge the lexically different variants of iterated task to a unique list 
+        for (ITaskInstance iterationInstance : iterationInstances) {
+            for (ITaskInstance executionVariant : iterationInstance) {
+                ITask candidate = executionVariant.getTask();
+            
+                boolean found = false;
+                for (ITask taskVariant : iteratedTaskVariants) {
+                    if (taskComparator.areLexicallyEqual(taskVariant, candidate)) {
+                        taskBuilder.setTask(executionVariant, taskVariant);
+                        found = true;
+                        break;
+                    }
+                }
+                
+                if (!found) {
+                    iteratedTaskVariants.add(candidate);
+                }
+            }
+        }
+        
+        // if there are more than one lexically different variant of iterated tasks, adapt the
+        // iteration model to be a selection of different variants. In this case also adapt
+        // the generated iteration instances to correctly contain selection instances. If there
+        // is only one variant of an iterated task, simply set this as the marked task of the
+        // iteration. In this case, the instances can be preserved as is
+        if (iteratedTaskVariants.size() > 1) {
+            ISelection selection = taskFactory.createNewSelection();
+            
+            for (ITask variant : iteratedTaskVariants) {
+                taskBuilder.addChild(selection, variant);
+            }
+            
+            taskBuilder.setMarkedTask(iteration, selection);
+            
+            for (ITaskInstance instance : iterationInstances) {
+                for (int i = 0; i < instance.size(); i++) {
+                    ITaskInstance selectionInstance = taskFactory.createNewTaskInstance(selection);
+                    taskBuilder.addChild(selectionInstance, instance.get(i));
+                    taskBuilder.setTaskInstance(instance, i, selectionInstance);
+                }
+            }
+        }
+        else {
+            taskBuilder.setMarkedTask(iteration, iteratedTaskVariants.get(0));
+        }
     }
 
@@ -226 +299 @@
         Tasks tasks;
         boolean createNewTrie = (appData.getLastTrie() == null) ||
-            appData.getReplacementCounter() > 0; // tree has changed
+            appData.detectedAndReplacedTasks(); // tree has changed
         
         do {
@@ -240 +313 @@
             createNewTrie = false;
             
-            for (List<ITaskTreeNode> task : tasks) {
+            for (List<ITaskInstance> task : tasks) {
                 if (task.size() >= appData.getTrainedSequenceLength()) {
                     // Trie must be recreated with a longer sequence length to be sure that
@@ -267 +340 @@
 
         appData.getStopWatch().start("training trie");
-        appData.setLastTrie(new Trie<ITaskTreeNode>(nodeComparator));
+        appData.setLastTrie(new Trie<ITaskInstance>(taskComparator));
     
-        List<ISequence> sessions = appData.getSessions();
-        
-        for (ISequence session : sessions) {
+        List<IUserSession> sessions = appData.getSessions();
+        
+        for (IUserSession session : sessions) {
             trainTrie(session, appData);
         }
@@ -282 +355 @@
      * @param parent
      */
-    private void trainTrie(ISequence session, RuleApplicationData appData) {
-        List<ITaskTreeNode> children = session.getChildren();
+    private void trainTrie(IUserSession session, RuleApplicationData appData) {
+        List<ITaskInstance> children = session.getExecutedTasks();
         
         if ((children != null) && (children.size() > 0)) {
@@ -294 +367 @@
      */
     private void replaceSequencesOccurringMostOften(RuleApplicationData appData) {
-        appData.resetReplacementCounter();
+        appData.detectedAndReplacedTasks(false);
 
         if ((appData.getLastFoundTasks().size() > 0) &&
             (appData.getLastFoundTasks().getOccurrenceCount() > 1))
         {
-            System.out.println("replacing tasks occurrences with merged variants of all versions");
-
-            for (List<ITaskTreeNode> task : appData.getLastFoundTasks()) {
-                String taskId = "task " + RuleUtils.getNewId();
-                System.out.println("replacing " + taskId + ": " + task);
-
-                appData.clearTaskOccurrences();
-                determineVariantsOfTaskOccurrences(task, appData.getSessions(), appData);
-                
-                appData.getStopWatch().start("merging task nodes");
-                ITaskTreeNode taskReplacement = mergeVariantsOfTaskOccurrence(taskId, appData);
-                appData.getStopWatch().stop("merging task nodes");
-
-                appData.resetReplacementCounter();
-                replaceTaskOccurrences(task, taskReplacement, appData.getSessions(), appData);
-
-                if (appData.getReplacementCounter() > 0) {
-                    appData.getResult().addNewlyCreatedParentNode(taskReplacement);
-                }
-
-                if (appData.getReplacementCounter() <
-                    appData.getLastFoundTasks().getOccurrenceCount())
-                {
-                    System.out.println(taskId + ": replaced task only " +
-                                       appData.getReplacementCounter() +
-                                       " times instead of expected " +
+            System.out.println("replacing tasks occurrences");
+
+            for (List<ITaskInstance> task : appData.getLastFoundTasks()) {
+                ISequence sequence = taskFactory.createNewSequence();
+                
+                System.out.println("replacing " + sequence.getId() + ": " + task);
+
+                List<ITaskInstance> sequenceInstances =
+                    replaceTaskOccurrences(task, appData.getSessions(), sequence);
+                
+                harmonizeSequenceInstancesModel(sequence, sequenceInstances,task.size());
+                appData.detectedAndReplacedTasks(sequenceInstances.size() > 0);
+
+                if (sequenceInstances.size() < appData.getLastFoundTasks().getOccurrenceCount()) {
+                    System.out.println(sequence.getId() + ": replaced task only " +
+                                       sequenceInstances.size() + " times instead of expected " +
                                        appData.getLastFoundTasks().getOccurrenceCount());
                 }
@@ -333 +396 @@
 
     /**
-     * @param tree
-     */
-    private void determineVariantsOfTaskOccurrences(List<ITaskTreeNode> task,
-                                                    List<ISequence>     sessions,
-                                                    RuleApplicationData appData)
+     *
+     */
+    private void harmonizeSequenceInstancesModel(ISequence           sequence,
+                                                 List<ITaskInstance> sequenceInstances,
+                                                 int                 sequenceLength)
     {
-        for (ISequence session : sessions) {
-            int index = -1;
-                
-            List<ITaskTreeNode> children = session.getChildren();
-
-            do {
-                index = getSubListIndex(children, task, ++index);
-
-                if (index > -1) {
-                    ISequence taskOccurrence = RuleUtils.getSubSequenceInRange
-                            (session, index, index + task.size() - 1, null,
-                             taskTreeNodeFactory, taskTreeBuilder);
-
-                    appData.addTaskOccurrence(taskOccurrence);
-
-                    // let the index point to the last element the belongs the identified occurrence
-                    index += task.size() - 1;
-                }
-            }
-            while (index > -1);
-        }
-    }
-
-    /**
-     * @param appData
-     * @return
-     */
-    private ITaskTreeNode mergeVariantsOfTaskOccurrence(String              taskId,
-                                                        RuleApplicationData appData)
-    {
-        return mergeVariantsOfTasks(taskId, appData.getTaskOccurrences());
-    }
-
-    /**
-     * @param appData
-     * @return
-     */
-    private ITaskTreeNode mergeVariantsOfTasks(String description, List<ITaskTreeNode> variants) {
-        // merge but preserve lexically distinct variants
-        TaskTreeNodeMerger merger = new TaskTreeNodeMerger
-            (taskTreeNodeFactory, taskTreeBuilder, nodeComparator);
-        
-        merger.mergeTaskNodes(variants);
-        
-        if (variants.size() == 1) {
-            ITaskTreeNode replacement = variants.get(0);
-            taskTreeBuilder.setDescription(replacement, description);
-            return replacement;
-        }
-        else {
-            ISelection selection = taskTreeNodeFactory.createNewSelection();
-            taskTreeBuilder.setDescription(selection, "variants of task " + description);
-            
-            for (ITaskTreeNode variant : variants) {
-                taskTreeBuilder.addChild(selection, variant);
-            }
-            
-            return selection;
-        }
-    }
-
-    /**
-     * @param task
-     * @param parent
-     * @param treeBuilder
-     * @param nodeFactory
-     * @param result
-     */
-    private void replaceTaskOccurrences(List<ITaskTreeNode> task,
-                                        ITaskTreeNode       replacement,
-                                        List<ISequence>     sessions,
-                                        RuleApplicationData appData)
-    {
-        // now check the children themselves for an occurrence of the task
-        for (int i = 0; i < sessions.size(); i++) {
-            ISequence session = sessions.get(i);
-            
-            int index = -1;
-        
-            List<ITaskTreeNode> children = session.getChildren();
-
-            do {
-                index = getSubListIndex(children, task, ++index);
-
-                if (index > -1) {
-                    if ((!(replacement instanceof ISequence)) ||
-                        (task.size() < children.size()))
-                    {
-                        for (int j = index; j < index + task.size(); j++) {
-                            taskTreeBuilder.removeChild(session, index);
-                        }
-
-                        taskTreeBuilder.addChild(session, index, replacement);
-                        appData.incrementReplacementCounter();
-
-                        children = session.getChildren();
-                    }
-                    else {
-                        // the whole list of children is an occurrence of this task. So ask the
-                        // caller of the method to replace the whole node
-                        sessions.set(i, (ISequence) replacement);
-                        appData.incrementReplacementCounter();
+        
+        // ensure for each subtask that lexically different variants are preserved
+        for (int subTaskIndex = 0; subTaskIndex < sequenceLength; subTaskIndex++) {
+            List<ITask> subTaskVariants = new LinkedList<ITask>();
+            
+            for (ITaskInstance sequenceInstance : sequenceInstances) {
+                ITask candidate = sequenceInstance.get(subTaskIndex).getTask();
+                
+                boolean found = false;
+                
+                for (int i = 0; i < subTaskVariants.size(); i++) {
+                    if (taskComparator.areLexicallyEqual(subTaskVariants.get(i), candidate)) {
+                        taskBuilder.setTask
+                            (sequenceInstance.get(subTaskIndex), subTaskVariants.get(i));
+                        
+                        found = true;
                         break;
                     }
                 }
+                
+                if (!found) {
+                    subTaskVariants.add(candidate);
+                }
+            }
+            
+            // if there are more than one lexically different variant of the sub task at
+            // the considered position, adapt the sequence model at that position to have
+            // a selection of the different variants. In this case also adapt the
+            // generated sequence instances to correctly contain selection instances. If
+            // there is only one variant of sub tasks at the given position, simply set
+            // this variant as the sub task of the selection. In this case, the instances
+            // can be preserved as is
+            if (subTaskVariants.size() > 1) {
+                ISelection selection = taskFactory.createNewSelection();
+                
+                for (ITask variant : subTaskVariants) {
+                    taskBuilder.addChild(selection, variant);
+                }
+                
+                taskBuilder.addChild(sequence, selection);
+                
+                for (ITaskInstance instance : sequenceInstances) {
+                    ITaskInstance selectionInstance =
+                        taskFactory.createNewTaskInstance(selection);
+                    taskBuilder.addChild(selectionInstance, instance.get(subTaskIndex));
+                    taskBuilder.setTaskInstance(instance, subTaskIndex, selectionInstance);
+                }
+            }
+            else if (subTaskVariants.size() == 1) {
+                taskBuilder.addChild(sequence, subTaskVariants.get(0));
+            }
+        }
+    }
+
+    /**
+     * @param tree
+     */
+    private List<ITaskInstance> replaceTaskOccurrences(List<ITaskInstance> task,
+                                                       List<IUserSession>  sessions,
+                                                       ISequence           temporalTaskModel)
+    {
+        List<ITaskInstance> sequenceInstances = new LinkedList<ITaskInstance>();
+        
+        for (IUserSession session : sessions) {
+            int index = -1;
+                
+            do {
+                index = getSubListIndex(session, task, ++index);
+
+                if (index > -1) {
+                    sequenceInstances.add
+                        (RuleUtils.createNewSubSequenceInRange
+                             (session, index, index + task.size() - 1, temporalTaskModel,
+                              taskFactory, taskBuilder));
+                }
             }
             while (index > -1);
         }
+        
+        return sequenceInstances;
     }
 
@@ -454 +489 @@
      * @return
      */
-    private int getSubListIndex(List<ITaskTreeNode> list,
-                                List<ITaskTreeNode> subList,
+    private int getSubListIndex(ITaskInstanceList   list,
+                                List<ITaskInstance> subList,
                                 int                 startIndex)
     {
@@ -465 +500 @@
             
             for (int j = 0; j < subList.size(); j++) {
-                if (!nodeComparator.equals(list.get(i + j), subList.get(j))) {
+                if (!taskComparator.equals(list.get(i + j), subList.get(j))) {
                     matchFound = false;
                     break;
@@ -479 +514 @@
         return result;
     }
+
+    /**
+     * @param trie
+     * @param object
+     * @return
+     */
+    private int getSubListIndex(List<ITaskInstance> list,
+                                List<ITaskInstance> subList,
+                                int                 startIndex)
+    {
+        boolean matchFound;
+        int result = -1;
+        
+        for (int i = startIndex; i <= list.size() - subList.size(); i++) {
+            matchFound = true;
+            
+            for (int j = 0; j < subList.size(); j++) {
+                if (!taskComparator.equals(list.get(i + j), subList.get(j))) {
+                    matchFound = false;
+                    break;
+                }
+            }
+            
+            if (matchFound) {
+                result = i;
+                break;
+            }
+        }
+        
+        return result;
+    }
     
     /**
      * @author Patrick Harms
      */
-    private class MaxCountAndLongestTasksFinder implements TrieProcessor<ITaskTreeNode> {
+    private class MaxCountAndLongestTasksFinder implements TrieProcessor<ITaskInstance> {
         
         /**
@@ -493 +559 @@
          * 
          */
-        private List<List<ITaskTreeNode>> foundTasks = new LinkedList<List<ITaskTreeNode>>();
+        private List<List<ITaskInstance>> foundTasks = new LinkedList<List<ITaskInstance>>();
 
         /**
@@ -507 +573 @@
          */
         @Override
-        public TrieProcessor.Result process(List<ITaskTreeNode> task, int count) {
-            if (task.size() < 2) {
-                // ignore single nodes
+        public TrieProcessor.Result process(List<ITaskInstance> foundTask, int count) {
+            if (foundTask.size() < 2) {
+                // ignore single tasks
                 return TrieProcessor.Result.CONTINUE;
             }
@@ -519 +585 @@
 
             if (this.currentCount > count) {
-                // ignore this children of this node, as they may have only smaller counts than
+                // ignore this children of this task, as they may have only smaller counts than
                 // the already found tasks
                 return TrieProcessor.Result.SKIP_NODE;
@@ -536 +602 @@
                 boolean added = false;
                 for (int i = 0; i < foundTasks.size(); i++) {
-                    if (foundTasks.get(i).size() < task.size()) {
+                    if (foundTasks.get(i).size() < foundTask.size()) {
                         // defensive copy
-                        foundTasks.add(i, new LinkedList<ITaskTreeNode>(task)); // defensive copy
+                        foundTasks.add(i, new LinkedList<ITaskInstance>(foundTask)); // defensive copy
                         added = true;
                         break;
@@ -545 +611 @@
                 
                 if (!added) {
-                    foundTasks.add(new LinkedList<ITaskTreeNode>(task)); // defensive copy
+                    foundTasks.add(new LinkedList<ITaskInstance>(foundTask)); // defensive copy
                 }
             }
@@ -571 +637 @@
                         // found a task that is a potential subtask. Check for this and remove the
                         // subtask if needed
-                        List<ITaskTreeNode> longTask = foundTasks.get(i);
-                        List<ITaskTreeNode> shortTask = foundTasks.get(j);
+                        List<ITaskInstance> longTask = foundTasks.get(i);
+                        List<ITaskInstance> shortTask = foundTasks.get(j);
                         
                         if (getSubListIndex(longTask, shortTask, 0) > -1) {
@@ -598 +664 @@
          * 
          */
-        private List<ISequence> sessions;
-        
-        /**
-         * 
-         */
-        private Trie<ITaskTreeNode> lastTrie;
+        private List<IUserSession> sessions;
+        
+        /**
+         * 
+         */
+        private Trie<ITaskInstance> lastTrie;
         
         /**
@@ -618 +684 @@
          * 
          */
-        private List<ITaskTreeNode> taskOccurrences = new LinkedList<ITaskTreeNode>();
-        
-        /**
-         * 
-         */
-        private int replacementCounter;
+        private boolean detectedAndReplacedTasks;
         
         /**
@@ -638 +699 @@
          * 
          */
-        private RuleApplicationData(List<ISequence> sessions) {
+        private RuleApplicationData(List<IUserSession> sessions) {
             this.sessions = sessions;
         }
@@ -645 +706 @@
          * @return the tree
          */
-        private List<ISequence> getSessions() {
+        private List<IUserSession> getSessions() {
             return sessions;
         }
@@ -652 +713 @@
          * @param lastTrie the lastTrie to set
          */
-        private void setLastTrie(Trie<ITaskTreeNode> lastTrie) {
+        private void setLastTrie(Trie<ITaskInstance> lastTrie) {
             this.lastTrie = lastTrie;
         }
@@ -659 +720 @@
          * @return the lastTrie
          */
-        private Trie<ITaskTreeNode> getLastTrie() {
+        private Trie<ITaskInstance> getLastTrie() {
             return lastTrie;
         }
@@ -692 +753 @@
 
         /**
-         * @return the taskOccurrences
-         */
-        private void clearTaskOccurrences() {
-            taskOccurrences.clear();
-        }
-
-        /**
-         * @return the taskOccurrences
-         */
-        private void addTaskOccurrence(ITaskTreeNode taskOccurrence) {
-            taskOccurrences.add(taskOccurrence);
-        }
-
-        /**
-         * @return the taskOccurrences
-         */
-        private List<ITaskTreeNode> getTaskOccurrences() {
-            return taskOccurrences;
-        }
-
-        /**
          *
          */
-        private void resetReplacementCounter() {
-            replacementCounter = 0;
+        private void detectedAndReplacedTasks(boolean detectedAndReplacedTasks) {
+            this.detectedAndReplacedTasks = detectedAndReplacedTasks;
         }
 
@@ -722 +762 @@
          *
          */
-        private void incrementReplacementCounter() {
-            replacementCounter++;
-        }
-
-        /**
-         *
-         */
-        private int getReplacementCounter() {
-            return replacementCounter;
+        private boolean detectedAndReplacedTasks() {
+            return detectedAndReplacedTasks;
         }
         
@@ -753 +786 @@
      * @author Patrick Harms
      */
-    private static class Tasks implements Iterable<List<ITaskTreeNode>> {
+    private static class Tasks implements Iterable<List<ITaskInstance>> {
         
         /**
@@ -763 +796 @@
          * 
          */
-        private List<List<ITaskTreeNode>> sequences;
+        private List<List<ITaskInstance>> sequences;
 
         /**
@@ -769 +802 @@
          * @param sequences
          */
-        private Tasks(int occurrenceCount, List<List<ITaskTreeNode>> sequences) {
+        private Tasks(int occurrenceCount, List<List<ITaskInstance>> sequences) {
             super();
             this.occurrenceCount = occurrenceCount;
@@ -797 +830 @@
          */
         @Override
-        public Iterator<List<ITaskTreeNode>> iterator() {
+        public Iterator<List<ITaskInstance>> iterator() {
             return this.sequences.iterator();
         }
@@ -803 +836 @@
     }
 
+    /**
+     *
+     */
+    private class TaskComparator implements SymbolComparator<ITaskInstance> {
+
+        /** */
+        private Comparer comparer;
+
+        /** */
+        private Comparer lexicalComparer;
+
+        /** */
+        private HashMap<Long, Boolean> equalityBuffer = new HashMap<Long, Boolean>();
+
+        /** */
+        private HashMap<Long, Boolean> lexicalEqualityBuffer;
+
+        /**
+         *
+         */
+        public TaskComparator(TaskEqualityRuleManager taskEqualityRuleManager,
+                              TaskEquality            minimalNodeEquality)
+        {
+            super();
+            
+            if (minimalNodeEquality == TaskEquality.LEXICALLY_EQUAL) {
+                comparer = new LexicalComparer(taskEqualityRuleManager);
+            }
+            else if (minimalNodeEquality == TaskEquality.SYNTACTICALLY_EQUAL) {
+                comparer = new SyntacticalComparer(taskEqualityRuleManager);
+            }
+            else if (minimalNodeEquality == TaskEquality.SEMANTICALLY_EQUAL) {
+                comparer = new SemanticalComparer(taskEqualityRuleManager);
+            }
+            else {
+                comparer = new DefaultComparer(taskEqualityRuleManager, minimalNodeEquality);
+            }
+            
+            if (minimalNodeEquality == TaskEquality.LEXICALLY_EQUAL) {
+                lexicalComparer = comparer;
+                lexicalEqualityBuffer = equalityBuffer;
+            }
+            else {
+                lexicalComparer = new LexicalComparer(taskEqualityRuleManager);
+                lexicalEqualityBuffer = new HashMap<Long, Boolean>();
+            }
+        }
+
+        /* (non-Javadoc)
+         * @see de.ugoe.cs.autoquest.tasktrees.temporalrelation.SymbolComparator#equals(java.lang.Object, java.lang.Object)
+         */
+        @Override
+        public boolean equals(ITaskInstance taskInstance1, ITaskInstance taskInstance2) {
+            return equals(taskInstance1.getTask(), taskInstance2.getTask());
+        }        
+
+        /**
+         * 
+         */
+        public boolean equals(ITask task1, ITask task2) {
+            Boolean result;
+            
+            if (task1 != task2) {
+                if ((task1 instanceof IEventTask) && (task2 instanceof IEventTask)) {
+                    long key = ((long) System.identityHashCode(task1)) << 32;
+                    key += System.identityHashCode(task2);
+                
+                    result = equalityBuffer.get(key);
+                
+                    if (result == null) {
+                        result = comparer.compare(task1, task2);
+                        equalityBuffer.put(key, result);
+                    }
+                }
+                else {
+                    result = false;
+                }
+            }
+            else {
+                result = true;
+            }
+            
+            return result;
+        }
+
+        /**
+         *
+         */
+        public boolean areLexicallyEqual(ITask task1, ITask task2) {
+            Boolean result;
+            
+            if (task1 != task2) {
+                long key = ((long) System.identityHashCode(task1)) << 32;
+                key += System.identityHashCode(task2);
+                
+                result = lexicalEqualityBuffer.get(key);
+                
+                if (result == null) {
+                    result = lexicalComparer.compare(task1, task2);
+                    lexicalEqualityBuffer.put(key, result);
+                }
+            }
+            else {
+                result = true;
+            }
+            
+            return result;
+        }
+    }
+
+    /**
+     * 
+     */
+    private interface Comparer {
+        
+        /**
+         * 
+         */
+        boolean compare(ITask task1, ITask task2);
+    }
+
+    /**
+     * 
+     */
+    private class LexicalComparer implements Comparer {
+        
+        /**
+         * <p>
+         * the task equality manager needed for comparing tasks with each other
+         * </p>
+         */
+        private TaskEqualityRuleManager taskEqualityRuleManager;
+        
+        /**
+         *
+         */
+        public LexicalComparer(TaskEqualityRuleManager taskEqualityRuleManager) {
+           this.taskEqualityRuleManager = taskEqualityRuleManager;
+        }
+        
+        /**
+         * 
+         */
+        public boolean compare(ITask task1, ITask task2) {
+            return taskEqualityRuleManager.areLexicallyEqual(task1, task2);
+        }
+    }
+
+    /**
+     * 
+     */
+    private class SyntacticalComparer implements Comparer {
+        
+        /**
+         * <p>
+         * the task equality manager needed for comparing tasks with each other
+         * </p>
+         */
+        private TaskEqualityRuleManager taskEqualityRuleManager;
+        
+        /**
+         *
+         */
+        public SyntacticalComparer(TaskEqualityRuleManager taskEqualityRuleManager) {
+           this.taskEqualityRuleManager = taskEqualityRuleManager;
+        }
+        
+        /**
+         * 
+         */
+        public boolean compare(ITask task1, ITask task2) {
+            return taskEqualityRuleManager.areSyntacticallyEqual(task1, task2);
+        }
+    }
+
+    /**
+     * 
+     */
+    private class SemanticalComparer implements Comparer {
+        
+        /**
+         * <p>
+         * the task equality manager needed for comparing tasks with each other
+         * </p>
+         */
+        private TaskEqualityRuleManager taskEqualityRuleManager;
+        
+        /**
+         *
+         */
+        public SemanticalComparer(TaskEqualityRuleManager taskEqualityRuleManager) {
+           this.taskEqualityRuleManager = taskEqualityRuleManager;
+        }
+        
+        /**
+         * 
+         */
+        public boolean compare(ITask task1, ITask task2) {
+            return taskEqualityRuleManager.areSemanticallyEqual(task1, task2);
+        }
+    }
+
+    /**
+     * 
+     */
+    private class DefaultComparer implements Comparer {
+        
+        /**
+         * <p>
+         * the task equality manager needed for comparing tasks with each other
+         * </p>
+         */
+        private TaskEqualityRuleManager taskEqualityRuleManager;
+
+        /**
+         * <p>
+         * the minimal task equality two identified sublists need to have to consider them as equal
+         * </p>
+         */
+        private TaskEquality minimalNodeEquality;
+        
+        /**
+         *
+         */
+        public DefaultComparer(TaskEqualityRuleManager taskEqualityRuleManager,
+                               TaskEquality            minimalNodeEquality)
+        {
+           this.taskEqualityRuleManager = taskEqualityRuleManager;
+           this.minimalNodeEquality = minimalNodeEquality;
+        }
+        
+        /**
+         * 
+         */
+        public boolean compare(ITask task1, ITask task2) {
+            return taskEqualityRuleManager.areAtLeastEqual(task1, task2, minimalNodeEquality);
+        }
+    }
 }