Index: trunk/autoquest-core-tasktrees/src/main/java/de/ugoe/cs/autoquest/tasktrees/temporalrelation/SequenceForTaskDetectionRule.java
===================================================================
--- trunk/autoquest-core-tasktrees/src/main/java/de/ugoe/cs/autoquest/tasktrees/temporalrelation/SequenceForTaskDetectionRule.java	(revision 1255)
+++ trunk/autoquest-core-tasktrees/src/main/java/de/ugoe/cs/autoquest/tasktrees/temporalrelation/SequenceForTaskDetectionRule.java	(revision 1256)
@@ -15,7 +15,4 @@
 package de.ugoe.cs.autoquest.tasktrees.temporalrelation;
 
-import java.io.IOException;
-import java.io.ObjectInputStream;
-import java.util.HashMap;
 import java.util.Iterator;
 import java.util.LinkedList;
@@ -23,6 +20,4 @@
 
 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;
@@ -34,6 +29,5 @@
 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.SymbolMap;
 import de.ugoe.cs.autoquest.usageprofiles.TrieProcessor;
 import de.ugoe.cs.util.StopWatch;
@@ -102,4 +96,5 @@
 
         // this is the real rule application. Loop while something is replaced.
+        harmonizeEventTaskInstancesModel(appData);
         do {
             System.out.println();
@@ -134,4 +129,43 @@
         
         return appData.getResult();
+    }
+
+    /**
+     * <p>
+     * TODO: comment
+     * </p>
+     *
+     * @param appData
+     */
+    private void harmonizeEventTaskInstancesModel(RuleApplicationData appData) {
+        System.out.print("harmonizing task model of event task instances");
+        appData.getStopWatch().start("harmonizing event tasks");
+        
+        SymbolMap<ITaskInstance, ITask> unifiedTaskMap =
+            new SymbolMap<ITaskInstance, ITask>(taskComparator);
+        
+        int unifiedTasks = 0;
+        
+        List<IUserSession> sessions = appData.getSessions();
+        for (IUserSession session : sessions) {
+            for (ITaskInstance taskInstance : session) {
+                ITask task = unifiedTaskMap.getValue(taskInstance);
+                
+                if (task == null) {
+                    unifiedTaskMap.addSymbol(taskInstance, taskInstance.getTask());
+                }
+                else {
+                    taskBuilder.setTask(taskInstance, task);
+                    unifiedTasks++;
+                }
+            }
+        }
+        
+        
+        appData.getStopWatch().stop("harmonizing event tasks");
+        System.out.println(" --> harmonized " + unifiedTasks + " task occurrences (still " +
+                           unifiedTaskMap.size() + " different tasks)");
+        
+        appData.getStopWatch().dumpStatistics(System.out);
     }
 
@@ -373,4 +407,61 @@
         while (createNewTrie);
         
+        // create a normal trie for comparison
+        /*System.out.println("creating test trie for comparison");
+        
+        appData.getStopWatch().start("testtrie");
+        Trie<ITaskInstance> trie = new Trie<ITaskInstance>(taskComparator);
+        
+        for (IUserSession session : appData.getSessions()) {
+            trie.train(session.getExecutedTasks(), appData.getTrainedSequenceLength());
+        }
+        
+        appData.getStopWatch().stop("testtrie");
+        
+        MaxCountAndLongestTasksFinder finder = new MaxCountAndLongestTasksFinder();
+        trie.process(finder);
+
+        boolean allTasksEqual = finder.getFoundTasks().size() == tasks.size();
+        
+        allTasksEqual &= finder.getFoundTasks().occurrenceCount == tasks.occurrenceCount;
+        
+        for (List<ITaskInstance> task1 : finder.getFoundTasks()) {
+            boolean foundTask = false;
+            for (List<ITaskInstance> task2 : tasks) {
+                boolean tasksEqual = false;
+                if (task1.size() == task2.size()) {
+                    tasksEqual = true;
+                    for (int i = 0; i < task1.size(); i++) {
+                        if (!taskComparator.equals(task1.get(i).getTask(), task2.get(i).getTask()))
+                        {
+                            tasksEqual = false;
+                        }
+                    }
+                }
+                
+                if (tasksEqual) {
+                    foundTask = true;
+                    break;
+                }
+            }
+            
+            if (!foundTask) {
+                System.out.println("different is " + task1);
+                allTasksEqual = false;
+                break;
+            }
+        }
+        
+        if (!allTasksEqual) {
+            System.out.println(finder.getFoundTasks());
+            System.out.println(tasks);
+            
+            throw new IllegalArgumentException("both tries calculated different subsequences");
+        }*/
+        
+        /*TrieStatisticsDumper dumper = new TrieStatisticsDumper();
+        appData.getLastTrie().process(dumper);
+        dumper.dumpCounters();*/
+        
         appData.setLastFoundTasks(tasks);
 
@@ -388,25 +479,10 @@
 
         appData.getStopWatch().start("training trie");
-        appData.setLastTrie(new Trie<ITaskInstance>(taskComparator));
+        appData.setLastTrie(new TaskInstanceTrie(taskComparator));
     
-        List<IUserSession> sessions = appData.getSessions();
-        
-        for (IUserSession session : sessions) {
-            trainTrie(session, appData);
-        }
+        appData.getLastTrie().trainSessions
+            (appData.getSessions(), appData.getTrainedSequenceLength());
         
         appData.getStopWatch().stop("training trie");
-    }
-
-    /**
-     * @param trie
-     * @param parent
-     */
-    private void trainTrie(IUserSession session, RuleApplicationData appData) {
-        List<ITaskInstance> children = session.getExecutedTasks();
-        
-        if ((children != null) && (children.size() > 0)) {
-            appData.getLastTrie().train(children, appData.getTrainedSequenceLength());
-        }
     }
 
@@ -704,4 +780,54 @@
     }
     
+//    /**
+//     * @author Patrick Harms
+//     */
+//    private class TrieStatisticsDumper implements TrieProcessor<ITaskInstance> {
+//        
+//        /**
+//         * 
+//         */
+//        private Map<Integer, Integer> counters = new HashMap<Integer, Integer>();
+//        
+//        /* (non-Javadoc)
+//         * @see de.ugoe.cs.autoquest.usageprofiles.TrieProcessor#process(java.util.List, int)
+//         */
+//        @Override
+//        public TrieProcessor.Result process(List<ITaskInstance> subsequence, int count) {
+//            if (subsequence.size() == 1) {
+//                Integer value = counters.get(count);
+//                
+//                if (value == null) {
+//                    value = 0;
+//                }
+//                
+//                counters.put(count, value + 1);
+//                
+//                return TrieProcessor.Result.CONTINUE;
+//            }
+//            else {
+//                // ignore singular occurrences
+//                return TrieProcessor.Result.SKIP_NODE;
+//            }
+//        }
+//
+//        /**
+//         *  @return
+//         */
+//        public void dumpCounters() {
+//            int dumpedCounters = 0;
+//            
+//            int count = 1;
+//            while (dumpedCounters < counters.size()) {
+//                Integer value = counters.get(count++);
+//                if (value != null) {
+//                    System.out.println(value + " symbols occurred " + count + " times");
+//                    dumpedCounters++;
+//                }
+//            }
+//        }
+//
+//    }
+    
     /**
      * 
@@ -717,5 +843,5 @@
          * 
          */
-        private Trie<ITaskInstance> lastTrie;
+        private TaskInstanceTrie lastTrie;
         
         /**
@@ -761,5 +887,5 @@
          * @param lastTrie the lastTrie to set
          */
-        private void setLastTrie(Trie<ITaskInstance> lastTrie) {
+        private void setLastTrie(TaskInstanceTrie lastTrie) {
             this.lastTrie = lastTrie;
         }
@@ -768,5 +894,5 @@
          * @return the lastTrie
          */
-        private Trie<ITaskInstance> getLastTrie() {
+        private TaskInstanceTrie getLastTrie() {
             return lastTrie;
         }
@@ -882,212 +1008,21 @@
         }
 
-    }
-
-    /**
-     *
-     */
-    private static class TaskComparator implements SymbolComparator<ITaskInstance> {
-        
-        /**  */
-        private static final long serialVersionUID = 1L;
-
-        /** */
-        private TaskEquality minimalNodeEquality;
-
-        /** */
-        private transient Comparer comparer;
-
-        /** */
-        private transient Comparer lexicalComparer;
-
-        /** */
-        private transient HashMap<Long, Boolean> equalityBuffer = new HashMap<Long, Boolean>();
-
-        /** */
-        private transient HashMap<Long, Boolean> lexicalEqualityBuffer;
-
-        /**
-         *
-         */
-        public TaskComparator(TaskEquality minimalNodeEquality) {
-            this.minimalNodeEquality = minimalNodeEquality;
-            init();
-        }
-
         /* (non-Javadoc)
-         * @see de.ugoe.cs.autoquest.tasktrees.temporalrelation.SymbolComparator#equals(java.lang.Object, java.lang.Object)
+         * @see java.lang.Object#toString()
          */
         @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 void init() {
-            if (minimalNodeEquality == TaskEquality.LEXICALLY_EQUAL) {
-                comparer = new LexicalComparer();
-            }
-            else if (minimalNodeEquality == TaskEquality.SYNTACTICALLY_EQUAL) {
-                comparer = new SyntacticalComparer();
-            }
-            else if (minimalNodeEquality == TaskEquality.SEMANTICALLY_EQUAL) {
-                comparer = new SemanticalComparer();
-            }
-            else {
-                comparer = new DefaultComparer(this.minimalNodeEquality);
-            }
-            
-            if (minimalNodeEquality == TaskEquality.LEXICALLY_EQUAL) {
-                lexicalComparer = comparer;
-                lexicalEqualityBuffer = equalityBuffer;
-            }
-            else {
-                lexicalComparer = new LexicalComparer();
-                lexicalEqualityBuffer = new HashMap<Long, Boolean>();
-            }
-        }
-        
-        /**
-         * <p>
-         * deserialize this object and reinitialize the buffers
-         * </p>
-         */
-        private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
-            in.defaultReadObject();
-            init();
-        }
-    }
-
-    /**
-     * 
-     */
-    private static interface Comparer {
-        
-        /**
-         * 
-         */
-        boolean compare(ITask task1, ITask task2);
-    }
-
-    /**
-     * 
-     */
-    private static class LexicalComparer implements Comparer {
-        
-        /**
-         * 
-         */
-        public boolean compare(ITask task1, ITask task2) {
-            return TaskEqualityRuleManager.getInstance().areLexicallyEqual(task1, task2);
-        }
-    }
-
-    /**
-     * 
-     */
-    private static class SyntacticalComparer implements Comparer {
-        
-        /**
-         * 
-         */
-        public boolean compare(ITask task1, ITask task2) {
-            return TaskEqualityRuleManager.getInstance().areSyntacticallyEqual(task1, task2);
-        }
-    }
-
-    /**
-     * 
-     */
-    private static class SemanticalComparer implements Comparer {
-        
-        /**
-         * 
-         */
-        public boolean compare(ITask task1, ITask task2) {
-            return TaskEqualityRuleManager.getInstance().areSemanticallyEqual(task1, task2);
-        }
-    }
-
-    /**
-     * 
-     */
-    private static class DefaultComparer implements Comparer {
-        
-        /**
-         * <p>
-         * the minimal task equality two identified sublists need to have to consider them as equal
-         * </p>
-         */
-        private TaskEquality minimalNodeEquality;
-        
-        /**
-         *
-         */
-        public DefaultComparer(TaskEquality minimalNodeEquality) {
-           this.minimalNodeEquality = minimalNodeEquality;
-        }
-        
-        /**
-         * 
-         */
-        public boolean compare(ITask task1, ITask task2) {
-            return TaskEqualityRuleManager.getInstance().areAtLeastEqual
-                (task1, task2, minimalNodeEquality);
-        }
+        public String toString() {
+            StringBuffer result = new StringBuffer();
+            result.append(this.occurrenceCount);
+            result.append(" occurrences:\n");
+            
+            for (List<ITaskInstance> task : sequences) {
+                result.append(task);
+                result.append("\n");
+            }
+            
+            return result.toString();
+        }
+
     }
 }
Index: trunk/autoquest-core-tasktrees/src/main/java/de/ugoe/cs/autoquest/tasktrees/temporalrelation/TaskComparator.java
===================================================================
--- trunk/autoquest-core-tasktrees/src/main/java/de/ugoe/cs/autoquest/tasktrees/temporalrelation/TaskComparator.java	(revision 1256)
+++ trunk/autoquest-core-tasktrees/src/main/java/de/ugoe/cs/autoquest/tasktrees/temporalrelation/TaskComparator.java	(revision 1256)
@@ -0,0 +1,277 @@
+//   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.io.IOException;
+import java.io.ObjectInputStream;
+import java.util.HashMap;
+
+import de.ugoe.cs.autoquest.eventcore.IEventType;
+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.ITask;
+import de.ugoe.cs.autoquest.tasktrees.treeifc.ITaskInstance;
+import de.ugoe.cs.autoquest.usageprofiles.SymbolComparator;
+
+/**
+ * TODO comment
+ */
+class TaskComparator implements SymbolComparator<ITaskInstance> {
+    
+    /**  */
+    private static final long serialVersionUID = 1L;
+    
+    /** */
+    private static final int MAX_BUFFER_SIZE = 10 * 1024 * 1024;
+
+    /** */
+    private TaskEquality minimalNodeEquality;
+
+    /** */
+    private transient Comparer comparer;
+
+    /** */
+    private transient Comparer lexicalComparer;
+
+    /** */
+    private transient HashMap<Long, Boolean> equalityBuffer = new HashMap<Long, Boolean>();
+
+    /** */
+    private transient HashMap<Long, Boolean> lexicalEqualityBuffer;
+
+    /**
+     *
+     */
+    public TaskComparator(TaskEquality minimalNodeEquality) {
+        this.minimalNodeEquality = minimalNodeEquality;
+        init();
+    }
+
+    /* (non-Javadoc)
+     * @see SymbolComparator#equals(Object, 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);
+                    
+                    if (equalityBuffer.size() < MAX_BUFFER_SIZE) {
+                        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);
+                if (equalityBuffer.size() < 1024 * 1024 * 10) {
+                    lexicalEqualityBuffer.put(key, result);
+                }
+            }
+        }
+        else {
+            result = true;
+        }
+        
+        return result;
+    }
+    
+    /* (non-Javadoc)
+     * @see SymbolComparator#getBucketSearchOrder(Object)
+     */
+    @Override
+    public int[] getBucketSearchOrder(ITaskInstance taskInstance) {
+        // 0 = sequence; 1 = selection; 2 = iteration; 3 = optional; 4 = event task in general;
+        // other = hashCode of name of event type
+        
+        ITask task = taskInstance.getTask();
+        
+        if (task instanceof IEventTask) {
+            // event tasks are most likely equal to those of the event type with the same name,
+            // Afterwards, they may be equal to iterations, optionals, other event tasks,
+            // selections, and finally the rest.
+            IEventType eventType = ((IEventTask) task).getEventType();
+            return new int[] { eventType.getName().hashCode(), 2, 3, 4, 1 };                       
+        }
+        else if (task instanceof ISequence) {
+            return new int[] { 0, 2, 3, 1 };                       
+        }
+        else if (task instanceof ISelection) {
+            return new int[] { 1, 4, 2, 3 };                       
+        }
+        else if (task instanceof IIteration) {
+            return new int[] { 2, 1, 4 };                       
+        }
+        
+        return null;
+    }
+
+    /**
+     * 
+     */
+    private void init() {
+        if (minimalNodeEquality == TaskEquality.LEXICALLY_EQUAL) {
+            comparer = new LexicalComparer();
+        }
+        else if (minimalNodeEquality == TaskEquality.SYNTACTICALLY_EQUAL) {
+            comparer = new SyntacticalComparer();
+        }
+        else if (minimalNodeEquality == TaskEquality.SEMANTICALLY_EQUAL) {
+            comparer = new SemanticalComparer();
+        }
+        else {
+            comparer = new DefaultComparer(this.minimalNodeEquality);
+        }
+        
+        if (minimalNodeEquality == TaskEquality.LEXICALLY_EQUAL) {
+            lexicalComparer = comparer;
+            lexicalEqualityBuffer = equalityBuffer;
+        }
+        else {
+            lexicalComparer = new LexicalComparer();
+            lexicalEqualityBuffer = new HashMap<Long, Boolean>();
+        }
+    }
+    
+    /**
+     * <p>
+     * deserialize this object and reinitialize the buffers
+     * </p>
+     */
+    private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
+        in.defaultReadObject();
+        init();
+    }
+
+
+    /**
+     * 
+     */
+    private static interface Comparer {
+        
+        /**
+         * 
+         */
+        boolean compare(ITask task1, ITask task2);
+    }
+
+    /**
+     * 
+     */
+    private static class LexicalComparer implements Comparer {
+        
+        /**
+         * 
+         */
+        public boolean compare(ITask task1, ITask task2) {
+            return TaskEqualityRuleManager.getInstance().areLexicallyEqual(task1, task2);
+        }
+    }
+
+    /**
+     * 
+     */
+    private static class SyntacticalComparer implements Comparer {
+        
+        /**
+         * 
+         */
+        public boolean compare(ITask task1, ITask task2) {
+            return TaskEqualityRuleManager.getInstance().areSyntacticallyEqual(task1, task2);
+        }
+    }
+
+    /**
+     * 
+     */
+    private static class SemanticalComparer implements Comparer {
+        
+        /**
+         * 
+         */
+        public boolean compare(ITask task1, ITask task2) {
+            return TaskEqualityRuleManager.getInstance().areSemanticallyEqual(task1, task2);
+        }
+    }
+
+    /**
+     * 
+     */
+    private static class DefaultComparer implements Comparer {
+        
+        /**
+         * <p>
+         * the minimal task equality two identified sublists need to have to consider them as equal
+         * </p>
+         */
+        private TaskEquality minimalNodeEquality;
+        
+        /**
+         *
+         */
+        public DefaultComparer(TaskEquality minimalNodeEquality) {
+           this.minimalNodeEquality = minimalNodeEquality;
+        }
+        
+        /**
+         * 
+         */
+        public boolean compare(ITask task1, ITask task2) {
+            return TaskEqualityRuleManager.getInstance().areAtLeastEqual
+                (task1, task2, minimalNodeEquality);
+        }
+    }
+}
Index: trunk/autoquest-core-tasktrees/src/main/java/de/ugoe/cs/autoquest/tasktrees/temporalrelation/TaskInstanceTrie.java
===================================================================
--- trunk/autoquest-core-tasktrees/src/main/java/de/ugoe/cs/autoquest/tasktrees/temporalrelation/TaskInstanceTrie.java	(revision 1256)
+++ trunk/autoquest-core-tasktrees/src/main/java/de/ugoe/cs/autoquest/tasktrees/temporalrelation/TaskInstanceTrie.java	(revision 1256)
@@ -0,0 +1,197 @@
+//   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.HashMap;
+import java.util.LinkedList;
+import java.util.List;
+import java.util.Map;
+
+import de.ugoe.cs.autoquest.tasktrees.treeifc.ITaskInstance;
+import de.ugoe.cs.autoquest.tasktrees.treeifc.IUserSession;
+import de.ugoe.cs.autoquest.usageprofiles.SymbolMap;
+import de.ugoe.cs.autoquest.usageprofiles.Trie;
+import de.ugoe.cs.autoquest.usageprofiles.TrieProcessor;
+
+/**
+ * <p>
+ * TODO comment
+ * </p>
+ * 
+ * @author Patrick Harms
+ */
+public class TaskInstanceTrie extends Trie<ITaskInstance> {
+
+    /**  */
+    private static final long serialVersionUID = 1L;
+
+    /**
+     * <p>
+     * the task comparator to be used for comparing tasks
+     * </p>
+     */
+    private TaskComparator comparator;
+
+    /**
+     * <p>
+     * TODO: comment
+     * </p>
+     *
+     * @param taskComparator2
+     */
+    public TaskInstanceTrie(TaskComparator taskComparator) {
+        super(taskComparator);
+        this.comparator = taskComparator;
+    }
+
+    /**
+     *
+     */
+    public void trainSessions(List<IUserSession> userSessions, int maxOrder) {
+        if (maxOrder < 1) {
+            return;
+        }
+        
+        SymbolMap<ITaskInstance, List<ITaskInstance>> equalTaskInstancesMap =
+            new SymbolMap<ITaskInstance, List<ITaskInstance>>(comparator);
+        
+        Map<ITaskInstance, List<ITaskInstance>> taskInstancesMap =
+            new HashMap<ITaskInstance, List<ITaskInstance>>();
+        
+        System.out.println("preparing training");
+        for (IUserSession session : userSessions) {
+            for (ITaskInstance taskInstance : session) {
+                List<ITaskInstance> equalTaskInstances =
+                    equalTaskInstancesMap.getValue(taskInstance);
+                
+                if (equalTaskInstances == null) {
+                    equalTaskInstances = new LinkedList<ITaskInstance>();
+                    equalTaskInstancesMap.addSymbol(taskInstance, equalTaskInstances);
+                }
+                
+                equalTaskInstances.add(taskInstance);
+                taskInstancesMap.put(taskInstance, equalTaskInstances);
+            }
+        }
+        
+        System.out.println("performing training");
+        for (IUserSession session : userSessions) {
+            train(session, maxOrder, taskInstancesMap);
+        }      
+        
+        updateKnownSymbols();
+    }
+    
+    /**
+     * 
+     */
+    private void train(IUserSession                            userSession,
+                       int                                     maxOrder,
+                       Map<ITaskInstance, List<ITaskInstance>> taskInstancesMap)
+    {
+        List<ITaskInstance> executedTasks = userSession.getExecutedTasks();
+        
+        List<ITaskInstance> subsequence = new LinkedList<ITaskInstance>();
+        
+        int numberOfTrainedSubsequences = 0;
+        int sequenceMaxCount = 0;
+        
+        for (ITaskInstance currentTaskInstance : executedTasks) {
+            int occurrenceCount = taskInstancesMap.get(currentTaskInstance).size();
+            
+            if ((numberOfTrainedSubsequences % 10) == 0) {
+                sequenceMaxCount = getCurrentSequenceMaxCount();
+            }
+            
+            if (occurrenceCount < sequenceMaxCount) {
+                // this task instance does not need to be considered, as it occurs not often enough
+                // to be part of a sequence, that occurs most often. Therefore train all remaining
+                // sequences so far and go on, until the next useful sequence is found.
+                
+                while (subsequence.size() > 1) {
+                    add(subsequence);
+                    subsequence.remove(0);
+                }
+                
+                subsequence.clear();
+            }
+            else {
+                subsequence.add(currentTaskInstance);
+
+                if (subsequence.size() == maxOrder) {
+                    add(subsequence);
+                    subsequence.remove(0);
+
+                    numberOfTrainedSubsequences++;
+                }
+            }
+        }
+        
+        // add shorter remaining subsequences, if any
+        while (subsequence.size() > 1) {
+            add(subsequence);
+            subsequence.remove(0);
+        }
+    }
+
+    /**
+     * <p>
+     * TODO: comment
+     * </p>
+     *
+     * @return
+     */
+    private int getCurrentSequenceMaxCount() {
+        MaxSequenceCountFinder processor = new MaxSequenceCountFinder();
+        super.process(processor);
+        return processor.getMaxCount();
+    }
+
+    /**
+     * @author Patrick Harms
+     */
+    private class MaxSequenceCountFinder implements TrieProcessor<ITaskInstance> {
+        
+        /**
+         * 
+         */
+        private int currentCount = 0;
+        
+        /* (non-Javadoc)
+         * @see de.ugoe.cs.autoquest.usageprofiles.TrieProcessor#process(java.util.List, int)
+         */
+        @Override
+        public TrieProcessor.Result process(List<ITaskInstance> foundTask, int count) {
+            if (foundTask.size() == 2) {
+                this.currentCount = Math.max(this.currentCount, count);
+                
+                // do not consider children
+                return TrieProcessor.Result.SKIP_NODE;
+            }
+            else {
+                return TrieProcessor.Result.CONTINUE;
+            }
+        }
+
+        /**
+         * 
+         */
+        private int getMaxCount() {
+            return currentCount;
+        }
+
+    }
+    
+}
