Index: trunk/autoquest-core-tasktrees-test/src/test/java/de/ugoe/cs/autoquest/tasktrees/temporalrelation/TaskInstanceTrieTest.java
===================================================================
--- trunk/autoquest-core-tasktrees-test/src/test/java/de/ugoe/cs/autoquest/tasktrees/temporalrelation/TaskInstanceTrieTest.java	(revision 1256)
+++ trunk/autoquest-core-tasktrees-test/src/test/java/de/ugoe/cs/autoquest/tasktrees/temporalrelation/TaskInstanceTrieTest.java	(revision 1256)
@@ -0,0 +1,1690 @@
+//   Copyright 2012 Georg-August-Universität Göttingen, Germany
+//
+//   Licensed under the Apache License, Version 2.0 (the "License");
+//   you may not use this file except in compliance with the License.
+//   You may obtain a copy of the License at
+//
+//       http://www.apache.org/licenses/LICENSE-2.0
+//
+//   Unless required by applicable law or agreed to in writing, software
+//   distributed under the License is distributed on an "AS IS" BASIS,
+//   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+//   See the License for the specific language governing permissions and
+//   limitations under the License.
+
+package de.ugoe.cs.autoquest.tasktrees.temporalrelation;
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collection;
+import java.util.HashMap;
+import java.util.List;
+import java.util.Map;
+
+import org.junit.*;
+
+import de.ugoe.cs.autoquest.tasktrees.TaskTreeDecoder;
+import de.ugoe.cs.autoquest.tasktrees.taskequality.TaskEquality;
+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.IUserSession;
+import de.ugoe.cs.autoquest.tasktrees.treeimpl.TaskBuilder;
+import de.ugoe.cs.autoquest.tasktrees.treeimpl.TaskFactory;
+import de.ugoe.cs.autoquest.usageprofiles.TrieProcessor;
+
+import static org.junit.Assert.*;
+
+/**
+ * The class <code>TaskInstanceTrieTest</code> contains tests for the class <code>{@link TaskInstanceTrie}</code>.
+ * 
+ * @author Steffen Herbold
+ * @version 1.0
+ */
+public class TaskInstanceTrieTest {
+
+    /** */
+    private ITaskBuilder taskBuilder = new TaskBuilder();
+
+    /** */
+    private ITaskFactory taskFactory = new TaskFactory();
+    
+    /** */
+    private TaskTreeDecoder decoder = new TaskTreeDecoder(taskFactory, taskBuilder);
+    
+    /** */
+    private TaskComparator comparator = new TaskComparator(TaskEquality.SEMANTICALLY_EQUAL);
+    
+    /** */
+    private IUserSession session = (IUserSession) decoder.decode
+         ("UserSession {" +
+          "  Event actionA {}" +
+          "  Event actionB {}" +
+          "  Event actionR {}" +
+          "  Event actionA {}" +
+          "  Event actionC {}" +
+          "  Event actionA {}" +
+          "  Event actionD {}" +
+          "  Event actionA {}" +
+          "  Event actionB {}" +
+          "  Event actionR {}" +
+          "  Event actionA {}" +
+          "}");
+
+    /**
+     * 
+     */
+    private static void assertCollectionContent(Collection<?> c1, Collection<?> c2) {
+        assertEquals(c1.size(), c2.size());
+        for (Object obj : c1) {
+            assertTrue(c2.contains(obj));
+        }
+    }
+
+    @Test
+    public void testTaskInstanceTaskInstanceTrie_1() throws Exception {
+        TaskInstanceTrie result = new TaskInstanceTrie(comparator);
+
+        assertNotNull(result);
+        assertEquals(0, result.getNumLeafs());
+        assertEquals(0, result.getNumSymbols());
+        assertEquals(0, result.getNumLeafAncestors());
+        assertTrue(result.getKnownSymbols().isEmpty());
+    }
+
+    @Test(expected = java.lang.IllegalArgumentException.class)
+    public void testTaskInstanceTrie_2() throws Exception {
+        new TaskInstanceTrie((TaskComparator) null);
+    }
+
+    @Test
+    public void testTrainSessions_1() throws Exception {
+        TaskInstanceTrie fixture = new TaskInstanceTrie(comparator);
+        
+        IUserSession session = (IUserSession) decoder.decode
+            ("UserSession {" +
+             "  Event action1 {}" +
+             "  Event action2 {}" +
+             "  Event action3 {}" +
+             "  Event action4 {}" +
+             "}");
+        
+        fixture.trainSessions(Arrays.asList(session), 2);
+        
+        assertEquals(1, fixture.getCount(Arrays.asList(session.get(0))));
+        assertEquals(1, fixture.getCount(Arrays.asList(session.get(1))));
+        assertEquals(1, fixture.getCount(Arrays.asList(session.get(2))));
+        
+        // subsequences of length 1 are not trained. So for the single item sequence of the last
+        // task, the count must be 0
+        assertEquals(0, fixture.getCount(Arrays.asList(session.get(3))));
+        
+        
+        assertEquals(1, fixture.getCount(Arrays.asList(session.get(0), session.get(1))));
+        assertEquals(1, fixture.getCount(Arrays.asList(session.get(1), session.get(2))));
+        assertEquals(1, fixture.getCount(Arrays.asList(session.get(2), session.get(3))));
+        
+        // this must return 0 as we only trained shorter sequences
+        assertEquals(0, fixture.getCount(Arrays.asList(session.get(0), session.get(1),
+                                                       session.get(2))));
+        
+        // subsequences of length 1 are not trained. So the single item sequence of the last
+        // task, is not counted
+        assertEquals(3, fixture.getNumSymbols());
+    }
+
+    @Test
+    public void testTrainSessions_2() throws Exception {
+        TaskInstanceTrie fixture = new TaskInstanceTrie(comparator);
+        
+        IUserSession session = (IUserSession) decoder.decode
+            ("UserSession {" +
+             "  Event action1 {}" +
+             "  Event action1 {}" +
+             "  Event action1 {}" +
+             "  Event action1 {}" +
+             "}");
+        
+        fixture.trainSessions(Arrays.asList(session), 2);
+        
+        for (int i = 0; i < session.size(); i++) {
+            // subsequences of length 1 are not trained. So the single item sequence of the last
+            // task is not counted. Therefore, the result must be 3
+            assertEquals(3, fixture.getCount(Arrays.asList(session.get(i))));
+            
+            for (int j = 0; j < session.size(); j++) {
+                assertEquals(3, fixture.getCount(Arrays.asList(session.get(i), session.get(j))));
+            }
+        }
+            
+        // this must return 0 as we only trained shorter sequences
+        assertEquals(0, fixture.getCount(Arrays.asList(session.get(0), session.get(1),
+                                                       session.get(2))));
+        
+        assertEquals(1, fixture.getNumSymbols());
+    }
+
+    @Test
+    public void testTrainSessions_3() throws Exception {
+        TaskInstanceTrie fixture = new TaskInstanceTrie(comparator);
+        
+        IUserSession session = (IUserSession) decoder.decode
+            ("UserSession {" +
+             "  Event action1 {}" +
+             "  Event action2 {}" +
+             "  Event action1 {}" +
+             "  Event action2 {}" +
+             "}");
+        
+        fixture.trainSessions(Arrays.asList(session), 2);
+        
+        // subsequences of length 1 are not trained. So the single item sequence of the last
+        // task is not counted. Therefore, the result must be 3
+        assertEquals(2, fixture.getCount(Arrays.asList(session.get(0))));
+        assertEquals(1, fixture.getCount(Arrays.asList(session.get(1))));
+        assertEquals(2, fixture.getCount(Arrays.asList(session.get(2))));
+        assertEquals(1, fixture.getCount(Arrays.asList(session.get(3))));
+        
+        assertEquals(2, fixture.getCount(Arrays.asList(session.get(0), session.get(1))));
+        assertEquals(1, fixture.getCount(Arrays.asList(session.get(1), session.get(2))));
+        assertEquals(2, fixture.getCount(Arrays.asList(session.get(2), session.get(3))));
+        
+        // this must return 0 as we only trained shorter sequences
+        assertEquals(0, fixture.getCount(Arrays.asList(session.get(0), session.get(1),
+                                                       session.get(2))));
+        
+        assertEquals(2, fixture.getNumSymbols());
+    }
+
+    @Test
+    public void testTrainSessions_4() throws Exception {
+        TaskInstanceTrie fixture = new TaskInstanceTrie(comparator);
+        
+        IUserSession session = (IUserSession) decoder.decode
+            ("UserSession {" +
+             "  Event action1 {}" +
+             "  Event action2 {}" +
+             "  Event action3 {}" +
+             "  Event action4 {}" +
+             "}");
+        
+        fixture.trainSessions(Arrays.asList(session), 3);
+        
+        assertEquals(1, fixture.getCount(Arrays.asList(session.get(0))));
+        assertEquals(1, fixture.getCount(Arrays.asList(session.get(1))));
+        assertEquals(1, fixture.getCount(Arrays.asList(session.get(2))));
+        
+        // subsequences of length 1 are not trained. So for the single item sequence of the last
+        // task, the count must be 0
+        assertEquals(0, fixture.getCount(Arrays.asList(session.get(3))));
+        
+        
+        assertEquals(1, fixture.getCount(Arrays.asList(session.get(0), session.get(1))));
+        assertEquals(1, fixture.getCount(Arrays.asList(session.get(1), session.get(2))));
+        assertEquals(1, fixture.getCount(Arrays.asList(session.get(2), session.get(3))));
+        
+        assertEquals(1, fixture.getCount(Arrays.asList(session.get(0), session.get(1),
+                                                       session.get(2))));
+        assertEquals(1, fixture.getCount(Arrays.asList(session.get(1), session.get(2),
+                                                       session.get(3))));
+        
+        // we only trained shorter sequences, so we expect a count of 0 for longer ones
+        assertEquals(0, fixture.getCount(Arrays.asList(session.get(0), session.get(1),
+                                                       session.get(2), session.get(3))));
+        
+        // subsequences of length 1 are not trained. So the single item sequence of the last
+        // task, is not counted
+        assertEquals(3, fixture.getNumSymbols());
+    }
+
+    @Test
+    public void testTrainSessions_5() throws Exception {
+        TaskInstanceTrie fixture = new TaskInstanceTrie(comparator);
+        
+        IUserSession session = (IUserSession) decoder.decode
+            ("UserSession {" +
+             "  Event action1 {}" +
+             "  Event action1 {}" +
+             "  Event action1 {}" +
+             "  Event action1 {}" +
+             "}");
+        
+        fixture.trainSessions(Arrays.asList(session), 3);
+        
+        for (int i = 0; i < session.size(); i++) {
+            // subsequences of length 1 are not trained. So the single item sequence of the last
+            // task is not counted. Therefore, the result must be 3
+            assertEquals(3, fixture.getCount(Arrays.asList(session.get(i))));
+            
+            for (int j = 0; j < session.size(); j++) {
+                assertEquals(3, fixture.getCount(Arrays.asList(session.get(i), session.get(j))));
+                
+                for (int k = 0; k < session.size(); k++) {
+                    assertEquals(2, fixture.getCount(Arrays.asList(session.get(i), session.get(j),
+                                                                   session.get(k))));                    
+                }
+            }
+        }
+            
+        // we only trained shorter sequences, so we expect a count of 0 for longer ones
+        assertEquals(0, fixture.getCount(Arrays.asList(session.get(0), session.get(1),
+                                                       session.get(2), session.get(3))));
+        
+        assertEquals(1, fixture.getNumSymbols());
+    }
+
+    @Test
+    public void testTrainSessions_6() throws Exception {
+        TaskInstanceTrie fixture = new TaskInstanceTrie(comparator);
+        
+        IUserSession session = (IUserSession) decoder.decode
+            ("UserSession {" +
+             "  Event action1 {}" +
+             "  Event action2 {}" +
+             "  Event action1 {}" +
+             "  Event action2 {}" +
+             "}");
+        
+        fixture.trainSessions(Arrays.asList(session), 3);
+        
+        // subsequences of length 1 are not trained. So the single item sequence of the last
+        // task is not counted. Therefore, the result must be 3
+        assertEquals(2, fixture.getCount(Arrays.asList(session.get(0))));
+        assertEquals(1, fixture.getCount(Arrays.asList(session.get(1))));
+        assertEquals(2, fixture.getCount(Arrays.asList(session.get(2))));
+        assertEquals(1, fixture.getCount(Arrays.asList(session.get(3))));
+        
+        assertEquals(2, fixture.getCount(Arrays.asList(session.get(0), session.get(1))));
+        assertEquals(1, fixture.getCount(Arrays.asList(session.get(1), session.get(2))));
+        assertEquals(2, fixture.getCount(Arrays.asList(session.get(2), session.get(3))));
+        
+        assertEquals(1, fixture.getCount(Arrays.asList(session.get(0), session.get(1),
+                                                       session.get(2))));
+        assertEquals(1, fixture.getCount(Arrays.asList(session.get(1), session.get(2),
+                                                       session.get(3))));
+        
+        // we only trained shorter sequences, so we expect a count of 0 for longer ones
+        assertEquals(0, fixture.getCount(Arrays.asList(session.get(0), session.get(1),
+                                                       session.get(2), session.get(3))));
+        
+        assertEquals(2, fixture.getNumSymbols());
+    }
+
+    @Test
+    public void testTrainSessions_7() throws Exception {
+        TaskInstanceTrie fixture = new TaskInstanceTrie(comparator);
+        
+        IUserSession session = (IUserSession) decoder.decode
+            ("UserSession {" +
+             "  Event action1 {}" +
+             "  Event action2 {}" +
+             "  Event action3 {}" +
+             "  Event action4 {}" +
+             "}");
+        
+        fixture.trainSessions(Arrays.asList(session), 4);
+        
+        assertEquals(1, fixture.getCount(Arrays.asList(session.get(0))));
+        assertEquals(1, fixture.getCount(Arrays.asList(session.get(1))));
+        assertEquals(1, fixture.getCount(Arrays.asList(session.get(2))));
+        
+        // subsequences of length 1 are not trained. So for the single item sequence of the last
+        // task, the count must be 0
+        assertEquals(0, fixture.getCount(Arrays.asList(session.get(3))));
+        
+        
+        assertEquals(1, fixture.getCount(Arrays.asList(session.get(0), session.get(1))));
+        assertEquals(1, fixture.getCount(Arrays.asList(session.get(1), session.get(2))));
+        assertEquals(1, fixture.getCount(Arrays.asList(session.get(2), session.get(3))));
+        
+        assertEquals(1, fixture.getCount(Arrays.asList(session.get(0), session.get(1),
+                                                       session.get(2))));
+        assertEquals(1, fixture.getCount(Arrays.asList(session.get(1), session.get(2),
+                                                       session.get(3))));
+        
+        // we only trained shorter sequences, so we expect a count of 0 for longer ones
+        assertEquals(1, fixture.getCount(Arrays.asList(session.get(0), session.get(1),
+                                                       session.get(2), session.get(3))));
+        
+        // subsequences of length 1 are not trained. So the single item sequence of the last
+        // task, is not counted
+        assertEquals(3, fixture.getNumSymbols());
+    }
+
+    @Test
+    public void testTrainSessions_8() throws Exception {
+        TaskInstanceTrie fixture = new TaskInstanceTrie(comparator);
+        
+        IUserSession session = (IUserSession) decoder.decode
+            ("UserSession {" +
+             "  Event action1 {}" +
+             "  Event action1 {}" +
+             "  Event action1 {}" +
+             "  Event action1 {}" +
+             "}");
+        
+        fixture.trainSessions(Arrays.asList(session), 4);
+        
+        for (int i = 0; i < session.size(); i++) {
+            // subsequences of length 1 are not trained. So the single item sequence of the last
+            // task is not counted. Therefore, the result must be 3
+            assertEquals(3, fixture.getCount(Arrays.asList(session.get(i))));
+            
+            for (int j = 0; j < session.size(); j++) {
+                assertEquals(3, fixture.getCount(Arrays.asList(session.get(i), session.get(j))));
+                
+                for (int k = 0; k < session.size(); k++) {
+                    assertEquals(2, fixture.getCount(Arrays.asList(session.get(i), session.get(j),
+                                                                   session.get(k))));                    
+                }
+            }
+        }
+            
+        // we only trained shorter sequences, so we expect a count of 0 for longer ones
+        assertEquals(1, fixture.getCount(Arrays.asList(session.get(0), session.get(1),
+                                                       session.get(2), session.get(3))));
+        
+        assertEquals(1, fixture.getNumSymbols());
+    }
+
+    @Test
+    public void testTrainSessions_9() throws Exception {
+        TaskInstanceTrie fixture = new TaskInstanceTrie(comparator);
+        
+        IUserSession session = (IUserSession) decoder.decode
+            ("UserSession {" +
+             "  Event action1 {}" +
+             "  Event action2 {}" +
+             "  Event action1 {}" +
+             "  Event action2 {}" +
+             "}");
+        
+        fixture.trainSessions(Arrays.asList(session), 4);
+        
+        // subsequences of length 1 are not trained. So the single item sequence of the last
+        // task is not counted. Therefore, the result must be 3
+        assertEquals(2, fixture.getCount(Arrays.asList(session.get(0))));
+        assertEquals(1, fixture.getCount(Arrays.asList(session.get(1))));
+        assertEquals(2, fixture.getCount(Arrays.asList(session.get(2))));
+        assertEquals(1, fixture.getCount(Arrays.asList(session.get(3))));
+        
+        assertEquals(2, fixture.getCount(Arrays.asList(session.get(0), session.get(1))));
+        assertEquals(1, fixture.getCount(Arrays.asList(session.get(1), session.get(2))));
+        assertEquals(2, fixture.getCount(Arrays.asList(session.get(2), session.get(3))));
+        
+        assertEquals(1, fixture.getCount(Arrays.asList(session.get(0), session.get(1),
+                                                       session.get(2))));
+        assertEquals(1, fixture.getCount(Arrays.asList(session.get(1), session.get(2),
+                                                       session.get(3))));
+        
+        // we only trained shorter sequences, so we expect a count of 0 for longer ones
+        assertEquals(1, fixture.getCount(Arrays.asList(session.get(0), session.get(1),
+                                                       session.get(2), session.get(3))));
+        
+        assertEquals(2, fixture.getNumSymbols());
+    }
+
+
+    @Test
+    public void testGetSequencesWithMostOccurrences_1() throws Exception {
+        TaskInstanceTrie fixture = new TaskInstanceTrie(comparator);
+        
+        fixture.trainSessions(Arrays.asList(session), 3);
+
+        // get all sequences with a minimal length of one that occur most often
+        Collection<List<ITaskInstance>> result = fixture.getSequencesWithOccurrenceCount(1, 0);
+
+        assertEquals(1, result.size());
+        
+        List<ITaskInstance> expected = new ArrayList<ITaskInstance>();
+        expected.add(session.get(0));
+        
+        assertContains((List<List<ITaskInstance>>) result, expected);
+    }
+
+    @Test
+    public void testGetSequencesWithMostOccurrences_2() throws Exception {
+        TaskInstanceTrie fixture = new TaskInstanceTrie(comparator);
+        
+        fixture.trainSessions(Arrays.asList(session), 3);
+
+        // get all sequences with a minimal length of one that occur exactly once
+        Collection<List<ITaskInstance>> result = fixture.getSequencesWithOccurrenceCount(1, 1);
+
+        assertEquals(11, result.size());
+
+        List<ITaskInstance> expected = new ArrayList<ITaskInstance>();
+        expected.add(session.get(2)); //r
+        expected.add(session.get(0)); //a
+        expected.add(session.get(4)); //c
+        // rac
+        assertContains((List<List<ITaskInstance>>) result, expected);
+
+        expected.clear();
+        expected.add(session.get(0)); //a
+        expected.add(session.get(4)); //c
+        // ac
+        assertContains((List<List<ITaskInstance>>) result, expected);
+
+        expected.add(session.get(0)); //a
+        // aca
+        assertContains((List<List<ITaskInstance>>) result, expected);
+
+        expected.clear();
+        expected.add(session.get(4)); //c
+        // c
+        assertContains((List<List<ITaskInstance>>) result, expected);
+
+        expected.add(session.get(0)); //a
+        // ca
+        assertContains((List<List<ITaskInstance>>) result, expected);
+
+        expected.add(session.get(6)); //d
+        // cad
+        assertContains((List<List<ITaskInstance>>) result, expected);
+
+        expected.clear();
+        expected.add(session.get(0)); //a
+        expected.add(session.get(6)); //d
+        // ad
+        assertContains((List<List<ITaskInstance>>) result, expected);
+
+        expected.add(session.get(0)); //a
+        // ada
+        assertContains((List<List<ITaskInstance>>) result, expected);
+
+        expected.clear();
+        expected.add(session.get(6)); //d
+        // d
+        assertContains((List<List<ITaskInstance>>) result, expected);
+
+        expected.add(session.get(0)); //a
+        // da
+        assertContains((List<List<ITaskInstance>>) result, expected);
+
+        expected.add(session.get(1)); //b
+        // dab
+        assertContains((List<List<ITaskInstance>>) result, expected);
+    }
+
+    @Test
+    public void testGetSequencesWithMostOccurrences_3() throws Exception {
+        TaskInstanceTrie fixture = new TaskInstanceTrie(comparator);
+            
+        fixture.trainSessions(Arrays.asList(session), 3);
+
+        // get all sequences with a minimal length of one that occur exactly twice
+        Collection<List<ITaskInstance>> result = fixture.getSequencesWithOccurrenceCount(1, 2);
+
+        assertEquals(7, result.size());
+
+        List<ITaskInstance> expected = new ArrayList<ITaskInstance>();
+        expected.add(session.get(0)); //a
+        expected.add(session.get(1)); //b
+        // ab
+        assertContains((List<List<ITaskInstance>>) result, expected);
+
+        expected.add(session.get(2)); //r
+        // abr
+        assertContains((List<List<ITaskInstance>>) result, expected);
+
+        expected.clear();
+        expected.add(session.get(1)); //b
+        // b
+        assertContains((List<List<ITaskInstance>>) result, expected);
+
+        expected.add(session.get(2)); //r
+        // br
+        assertContains((List<List<ITaskInstance>>) result, expected);
+
+        expected.add(session.get(0)); //a
+        // bra
+        assertContains((List<List<ITaskInstance>>) result, expected);
+
+        expected.clear();
+        expected.add(session.get(2)); //r
+        // r
+        assertContains((List<List<ITaskInstance>>) result, expected);
+
+        expected.add(session.get(0)); //a
+        // ra
+        assertContains((List<List<ITaskInstance>>) result, expected);
+    }
+
+    @Test
+    public void testGetSequencesWithMostOccurrences_4() throws Exception {
+        TaskInstanceTrie fixture = new TaskInstanceTrie(comparator);
+                
+        fixture.trainSessions(Arrays.asList(session), 3);
+
+        // get all sequences with a minimal length of one that occur exactly three times
+        Collection<List<ITaskInstance>> result = fixture.getSequencesWithOccurrenceCount(1, 3);
+
+        assertEquals(0, result.size());
+    }
+
+    @Test
+    public void testGetSequencesWithMostOccurrences_5() throws Exception {
+        TaskInstanceTrie fixture = new TaskInstanceTrie(comparator);
+                
+        fixture.trainSessions(Arrays.asList(session), 3);
+
+        // get all sequences with a minimal length of one that occur exactly four times
+        Collection<List<ITaskInstance>> result = fixture.getSequencesWithOccurrenceCount(1, 4);
+
+        // as we did not train the last single action, we may expect the "a" action only 4 times
+        assertEquals(1, result.size());
+
+        List<ITaskInstance> expected = new ArrayList<ITaskInstance>();
+        expected.add(session.get(0)); //a
+        assertContains((List<List<ITaskInstance>>) result, expected);
+    }
+
+    @Test
+    public void testGetSequencesWithMostOccurrences_6() throws Exception {
+        TaskInstanceTrie fixture = new TaskInstanceTrie(comparator);
+                
+        fixture.trainSessions(Arrays.asList(session), 3);
+
+        // get all sequences with a minimal length of one that occur exactly five times
+        Collection<List<ITaskInstance>> result = fixture.getSequencesWithOccurrenceCount(1, 5);
+
+        // as we did not train the last single action, we may expect the "a" action only 4 times
+        assertEquals(0, result.size());
+    }
+
+    @Test
+    public void testGetSequencesWithMostOccurrences_7() throws Exception {
+        TaskInstanceTrie fixture = new TaskInstanceTrie(comparator);
+                
+        fixture.trainSessions(Arrays.asList(session), 3);
+
+        // get all sequences with a minimal length of two that occur most often
+        Collection<List<ITaskInstance>> result = fixture.getSequencesWithOccurrenceCount(2, 0);
+
+        assertEquals(5, result.size());
+
+        List<ITaskInstance> expected = new ArrayList<ITaskInstance>();
+        expected.add(session.get(0)); //a
+        expected.add(session.get(1)); //b
+        assertContains((List<List<ITaskInstance>>) result, expected);
+
+        expected.add(session.get(2)); //r
+        assertContains((List<List<ITaskInstance>>) result, expected);
+
+        expected.clear();
+        expected.add(session.get(1)); //b
+        expected.add(session.get(2)); //r
+        assertContains((List<List<ITaskInstance>>) result, expected);
+
+        expected.add(session.get(0)); //a
+        assertContains((List<List<ITaskInstance>>) result, expected);
+
+        expected.clear();
+        expected.add(session.get(2)); //r
+        expected.add(session.get(0)); //a
+        assertContains((List<List<ITaskInstance>>) result, expected);
+    }
+
+    @Test
+    public void testGetSequencesWithMostOccurrences_8() throws Exception {
+        TaskInstanceTrie fixture = new TaskInstanceTrie(comparator);
+            
+        fixture.trainSessions(Arrays.asList(session), 3);
+
+        // get all sequences with a minimal length of two that occur exactly once
+        Collection<List<ITaskInstance>> result = fixture.getSequencesWithOccurrenceCount(2, 1);
+
+        assertEquals(9, result.size());
+
+        List<ITaskInstance> expected = new ArrayList<ITaskInstance>();
+        expected.add(session.get(2)); //r
+        expected.add(session.get(0)); //a
+        expected.add(session.get(4)); //c
+        // rac
+        assertContains((List<List<ITaskInstance>>) result, expected);
+
+        expected.clear();
+        expected.add(session.get(0)); //a
+        expected.add(session.get(4)); //c
+        // ac
+        assertContains((List<List<ITaskInstance>>) result, expected);
+
+        expected.add(session.get(0)); //a
+        // aca
+        assertContains((List<List<ITaskInstance>>) result, expected);
+
+        expected.clear();
+        expected.add(session.get(4)); //c
+        expected.add(session.get(0)); //a
+        // ca
+        assertContains((List<List<ITaskInstance>>) result, expected);
+
+        expected.add(session.get(6)); //d
+        // cad
+        assertContains((List<List<ITaskInstance>>) result, expected);
+
+        expected.clear();
+        expected.add(session.get(0)); //a
+        expected.add(session.get(6)); //d
+        // ad
+        assertContains((List<List<ITaskInstance>>) result, expected);
+
+        expected.add(session.get(0)); //a
+        // ada
+        assertContains((List<List<ITaskInstance>>) result, expected);
+
+        expected.clear();
+        expected.add(session.get(6)); //d
+        expected.add(session.get(0)); //a
+        // da
+        assertContains((List<List<ITaskInstance>>) result, expected);
+
+        expected.add(session.get(1)); //b
+        // dab
+        assertContains((List<List<ITaskInstance>>) result, expected);
+    }
+
+    @Test
+    public void testGetSequencesWithMostOccurrences_9() throws Exception {
+        TaskInstanceTrie fixture = new TaskInstanceTrie(comparator);
+            
+        fixture.trainSessions(Arrays.asList(session), 3);
+
+        // get all sequences with a minimal length of two that occur exactly twice
+        Collection<List<ITaskInstance>> result = fixture.getSequencesWithOccurrenceCount(2, 2);
+
+        assertEquals(5, result.size());
+
+        List<ITaskInstance> expected = new ArrayList<ITaskInstance>();
+        expected.add(session.get(0)); //a
+        expected.add(session.get(1)); //b
+        // ab
+        assertContains((List<List<ITaskInstance>>) result, expected);
+
+        expected.add(session.get(2)); //r
+        // abr
+        assertContains((List<List<ITaskInstance>>) result, expected);
+
+        expected.clear();
+        expected.add(session.get(1)); //b
+        expected.add(session.get(2)); //r
+        // br
+        assertContains((List<List<ITaskInstance>>) result, expected);
+
+        expected.add(session.get(0)); //a
+        // bra
+        assertContains((List<List<ITaskInstance>>) result, expected);
+
+        expected.clear();
+        expected.add(session.get(2)); //r
+        expected.add(session.get(0)); //a
+        // ra
+        assertContains((List<List<ITaskInstance>>) result, expected);
+    }
+
+    @Test
+    public void testGetSequencesWithMostOccurrences_10() throws Exception {
+        TaskInstanceTrie fixture = new TaskInstanceTrie(comparator);
+               
+        fixture.trainSessions(Arrays.asList(session), 3);
+
+        // get all sequences with a minimal length of two that occur exactly three times
+        Collection<List<ITaskInstance>> result = fixture.getSequencesWithOccurrenceCount(2, 3);
+
+        assertEquals(0, result.size());
+    }
+
+    @Test
+    public void testGetSequencesWithMostOccurrences_11() throws Exception {
+        TaskInstanceTrie fixture = new TaskInstanceTrie(comparator);
+                
+        fixture.trainSessions(Arrays.asList(session), 3);
+
+        // get all sequences with a minimal length of three that occur most often
+        Collection<List<ITaskInstance>> result = fixture.getSequencesWithOccurrenceCount(3, 0);
+
+        assertEquals(2, result.size());
+
+        List<ITaskInstance> expected = new ArrayList<ITaskInstance>();
+        expected.add(session.get(0)); //a
+        expected.add(session.get(1)); //b
+        expected.add(session.get(2)); //r
+        assertContains((List<List<ITaskInstance>>) result, expected);
+
+        expected.clear();
+        expected.add(session.get(1)); //b
+        expected.add(session.get(2)); //r
+        expected.add(session.get(0)); //a
+        assertContains((List<List<ITaskInstance>>) result, expected);
+    }
+
+    @Test
+    public void testGetSequencesWithMostOccurrences_12() throws Exception {
+        TaskInstanceTrie fixture = new TaskInstanceTrie(comparator);
+                
+        fixture.trainSessions(Arrays.asList(session), 3);
+
+        // get all sequences with a minimal length of three that occur exactly once
+        Collection<List<ITaskInstance>> result = fixture.getSequencesWithOccurrenceCount(3, 1);
+
+        assertEquals(5, result.size());
+
+        List<ITaskInstance> expected = new ArrayList<ITaskInstance>();
+        expected.add(session.get(2)); //r
+        expected.add(session.get(0)); //a
+        expected.add(session.get(4)); //c
+        // rac
+        assertContains((List<List<ITaskInstance>>) result, expected);
+
+        expected.clear();
+        expected.add(session.get(0)); //a
+        expected.add(session.get(4)); //c
+        expected.add(session.get(0)); //a
+        // aca
+        assertContains((List<List<ITaskInstance>>) result, expected);
+
+        expected.clear();
+        expected.add(session.get(4)); //c
+        expected.add(session.get(0)); //a
+        expected.add(session.get(6)); //d
+        // cad
+        assertContains((List<List<ITaskInstance>>) result, expected);
+
+        expected.clear();
+        expected.add(session.get(0)); //a
+        expected.add(session.get(6)); //d
+        expected.add(session.get(0)); //a
+        // ada
+        assertContains((List<List<ITaskInstance>>) result, expected);
+
+        expected.clear();
+        expected.add(session.get(6)); //d
+        expected.add(session.get(0)); //a
+        expected.add(session.get(1)); //b
+        // dab
+        assertContains((List<List<ITaskInstance>>) result, expected);
+    }
+
+    @Test
+    public void testGetSequencesWithMostOccurrences_13() throws Exception {
+        TaskInstanceTrie fixture = new TaskInstanceTrie(comparator);
+                
+        fixture.trainSessions(Arrays.asList(session), 3);
+
+        // get all sequences with a minimal length of four that occur most often
+        Collection<List<ITaskInstance>> result = fixture.getSequencesWithOccurrenceCount(4, 0);
+
+        // none of these exist, as the tree is only trained with sequences of length 3
+        assertEquals(0, result.size());
+    }
+
+    @Test
+    public void testGetSequencesWithMostOccurrences_14() throws Exception {
+        TaskInstanceTrie fixture = new TaskInstanceTrie(comparator);
+                    
+        fixture.trainSessions(Arrays.asList(session), 3);
+
+        // get all sequences with a minimal length of four that occur exactly once
+        Collection<List<ITaskInstance>> result = fixture.getSequencesWithOccurrenceCount(4, 1);
+
+        // none of these exist, as the tree is only trained with sequences of length 3
+        assertEquals(0, result.size());
+    }
+
+    @Test
+    public void testGetCount_1() throws Exception {
+        TaskInstanceTrie fixture = new TaskInstanceTrie(comparator);
+                        
+        fixture.trainSessions(Arrays.asList(session), 3);
+
+        List<ITaskInstance> subSequence = new ArrayList<ITaskInstance>();
+        subSequence.add(session.get(0)); //a
+
+        int result = fixture.getCount(subSequence);
+
+        // as we did not train the last single action, we may expect the "a" action only 4 times
+        assertEquals(4, result);
+    }
+
+    @Test
+    public void testGetCount_2() throws Exception {
+        TaskInstanceTrie fixture = new TaskInstanceTrie(comparator);
+                            
+        fixture.trainSessions(Arrays.asList(session), 3);
+
+        List<ITaskInstance> subSequence = new ArrayList<ITaskInstance>();
+        subSequence.add(session.get(0)); //a
+        subSequence.add(session.get(1)); //b
+
+        int result = fixture.getCount(subSequence);
+
+        assertEquals(2, result);
+    }
+
+    @Test
+    public void testGetCount_3() throws Exception {
+        TaskInstanceTrie fixture = new TaskInstanceTrie(comparator);
+                            
+        fixture.trainSessions(Arrays.asList(session), 3);
+
+        List<ITaskInstance> subSequence = new ArrayList<ITaskInstance>();
+        subSequence.add(taskFactory.createNewTaskInstance(taskFactory.createNewSequence()));
+
+        int result = fixture.getCount(subSequence);
+
+        assertEquals(0, result);
+    }
+
+    @Test
+    public void testGetCount_4() throws Exception {
+        TaskInstanceTrie fixture = new TaskInstanceTrie(comparator);
+                            
+        fixture.trainSessions(Arrays.asList(session), 3);
+
+        List<ITaskInstance> subSequence = new ArrayList<ITaskInstance>();
+
+        int result = fixture.getCount(subSequence, session.get(0)); //a
+
+        // as we did not train the last single action, we may expect the "a" action only 4 times
+        assertEquals(4, result);
+    }
+
+    @Test
+    public void testGetCount_5() throws Exception {
+        TaskInstanceTrie fixture = new TaskInstanceTrie(comparator);
+                                
+        fixture.trainSessions(Arrays.asList(session), 3);
+
+        List<ITaskInstance> subSequence = new ArrayList<ITaskInstance>();
+        subSequence.add(session.get(0)); //a
+        subSequence.add(session.get(1)); //b
+
+        int result = fixture.getCount(subSequence, session.get(2)); //r
+
+        assertEquals(2, result);
+    }
+
+    @Test
+    public void testGetCount_6() throws Exception {
+        TaskInstanceTrie fixture = new TaskInstanceTrie(comparator);
+                                
+        fixture.trainSessions(Arrays.asList(session), 3);
+
+        List<ITaskInstance> subSequence = new ArrayList<ITaskInstance>();
+
+        int result = fixture.getCount
+            (subSequence, taskFactory.createNewTaskInstance(taskFactory.createNewSequence()));
+
+        assertEquals(0, result);
+    }
+
+    @Test
+    public void testGetFollowingSymbols_1() throws Exception {
+        TaskInstanceTrie fixture = new TaskInstanceTrie(comparator);
+                                    
+        fixture.trainSessions(Arrays.asList(session), 3);
+
+        List<ITaskInstance> subSequence = new ArrayList<ITaskInstance>();
+        subSequence.add(session.get(0)); //a
+        Collection<ITaskInstance> expected = new ArrayList<ITaskInstance>();
+        expected.add(session.get(1)); //b
+        expected.add(session.get(4)); //c
+        expected.add(session.get(6)); //d
+
+        Collection<ITaskInstance> result = fixture.getFollowingSymbols(subSequence);
+
+        assertCollectionContent(expected, result);
+    }
+
+    @Test
+    public void testGetFollowingSymbols_2() throws Exception {
+        TaskInstanceTrie fixture = new TaskInstanceTrie(comparator);
+                                        
+        fixture.trainSessions(Arrays.asList(session), 3);
+
+        List<ITaskInstance> subSequence = new ArrayList<ITaskInstance>();
+        subSequence.add(session.get(0)); //a
+        subSequence.add(session.get(1)); //b
+        subSequence.add(session.get(2)); //r
+
+        Collection<ITaskInstance> result = fixture.getFollowingSymbols(subSequence);
+
+        assertEquals(0, result.size());
+    }
+
+    @Test
+    public void testGetFollowingSymbols_3() throws Exception {
+        TaskInstanceTrie fixture = new TaskInstanceTrie(comparator);
+                                        
+        fixture.trainSessions(Arrays.asList(session), 3);
+
+        List<ITaskInstance> subSequence = new ArrayList<ITaskInstance>();
+        subSequence.add(taskFactory.createNewTaskInstance(taskFactory.createNewSequence()));
+
+        Collection<ITaskInstance> result = fixture.getFollowingSymbols(subSequence);
+
+        assertEquals(0, result.size());
+    }
+
+    @Test
+    public void testGetNumLeafAncestors_1() throws Exception {
+        TaskInstanceTrie fixture = new TaskInstanceTrie(comparator);
+                                            
+        fixture.trainSessions(Arrays.asList(session), 3);
+
+        int result = fixture.getNumLeafAncestors();
+
+        assertEquals(7, result);
+    }
+
+    @Test
+    public void testGetNumLeafs_1() throws Exception {
+        TaskInstanceTrie fixture = new TaskInstanceTrie(comparator);
+                                            
+        fixture.trainSessions(Arrays.asList(session), 3);
+
+        int result = fixture.getNumLeafs();
+
+        assertEquals(7, result);
+    }
+
+    @Test
+    public void testGetNumSymbols_1() throws Exception {
+        TaskInstanceTrie fixture = new TaskInstanceTrie(comparator);
+                                            
+        fixture.trainSessions(Arrays.asList(session), 3);
+
+
+        int result = fixture.getNumSymbols();
+
+        assertEquals(5, result);
+    }
+
+    @Test
+    public void testLargeTaskInstanceTrie_1() throws Exception {
+        TaskInstanceTrie fixture = new TaskInstanceTrie(comparator);
+
+        int order = 2;
+        
+        TaskInstanceTrieTester tester = new TaskInstanceTrieTester(3, 50, order);
+
+        long start = System.currentTimeMillis();
+        fixture.trainSessions(Arrays.asList(tester.userSession), order);
+        System.out.println("testing session with 50 task instances and 3 symbols took " +
+                           (System.currentTimeMillis() - start) + "ms");
+        
+        fixture.process(tester);
+        
+        // do not check if counts is empty, as some sequences may not be part of the reduced trie
+        // and may therefore not be processed by the tester.
+        //assertTrue(tester.counts.isEmpty());
+    }
+
+    @Test
+    public void testLargeTaskInstanceTrie_2() throws Exception {
+        TaskInstanceTrie fixture = new TaskInstanceTrie(comparator);
+
+        int order = 2;
+        
+        TaskInstanceTrieTester tester = new TaskInstanceTrieTester(3, 10000, order);
+
+        long start = System.currentTimeMillis();
+        fixture.trainSessions(Arrays.asList(tester.userSession), order);
+        System.out.println("testing session with 10000 task instances and 3 symbols took " +
+                           (System.currentTimeMillis() - start) + "ms");
+        
+        fixture.process(tester);
+        
+        // do not check if counts is empty, as some sequences may not be part of the reduced trie
+        // and may therefore not be processed by the tester.
+        //assertTrue(tester.counts.isEmpty());
+    }
+
+    @Test
+    public void testLargeTaskInstanceTrie_3() throws Exception {
+        TaskInstanceTrie fixture = new TaskInstanceTrie(comparator);
+
+        int order = 2;
+        
+        TaskInstanceTrieTester tester = new TaskInstanceTrieTester(30, 10000, order);
+
+        long start = System.currentTimeMillis();
+        fixture.trainSessions(Arrays.asList(tester.userSession), order);
+        System.out.println("testing session with 10000 task instances and 30 symbols took " +
+                           (System.currentTimeMillis() - start) + "ms");
+        
+        fixture.process(tester);
+        
+        // do not check if counts is empty, as some sequences may not be part of the reduced trie
+        // and may therefore not be processed by the tester.
+        //assertTrue(tester.counts.isEmpty());
+    }
+
+    @Test
+    public void testLargeTaskInstanceTrie_4() throws Exception {
+        TaskInstanceTrie fixture = new TaskInstanceTrie(comparator);
+
+        int order = 2;
+        
+        TaskInstanceTrieTester tester = new TaskInstanceTrieTester(300, 10000, order);
+
+        long start = System.currentTimeMillis();
+        fixture.trainSessions(Arrays.asList(tester.userSession), order);
+        System.out.println("testing session with 10000 task instances and 300 symbols took " +
+                           (System.currentTimeMillis() - start) + "ms");
+        
+        fixture.process(tester);
+        
+        // do not check if counts is empty, as some sequences may not be part of the reduced trie
+        // and may therefore not be processed by the tester.
+        //assertTrue(tester.counts.isEmpty());
+    }
+
+    @Test
+    public void testLargeTaskInstanceTrie_5() throws Exception {
+        TaskInstanceTrie fixture = new TaskInstanceTrie(comparator);
+
+        int order = 2;
+        
+        TaskInstanceTrieTester tester = new TaskInstanceTrieTester(1000, 10000, order);
+
+        long start = System.currentTimeMillis();
+        fixture.trainSessions(Arrays.asList(tester.userSession), order);
+        System.out.println("testing session with 10000 task instances and 1000 symbols took " +
+                           (System.currentTimeMillis() - start) + "ms");
+        
+        fixture.process(tester);
+        
+        // do not check if counts is empty, as some sequences may not be part of the reduced trie
+        // and may therefore not be processed by the tester.
+        //assertTrue(tester.counts.isEmpty());
+    }
+
+    @Test
+    public void testLargeTaskInstanceTrie_6() throws Exception {
+        TaskInstanceTrie fixture = new TaskInstanceTrie(comparator);
+
+        int order = 3;
+        
+        TaskInstanceTrieTester tester = new TaskInstanceTrieTester(3, 50, order);
+
+        long start = System.currentTimeMillis();
+        fixture.trainSessions(Arrays.asList(tester.userSession), order);
+        System.out.println("testing session with 50 task instances and 3 symbols took " +
+                           (System.currentTimeMillis() - start) + "ms");
+        
+        fixture.process(tester);
+        
+        // do not check if counts is empty, as some sequences may not be part of the reduced trie
+        // and may therefore not be processed by the tester.
+        //assertTrue(tester.counts.isEmpty());
+    }
+
+    @Test
+    public void testLargeTaskInstanceTrie_7() throws Exception {
+        TaskInstanceTrie fixture = new TaskInstanceTrie(comparator);
+
+        int order = 3;
+        
+        TaskInstanceTrieTester tester = new TaskInstanceTrieTester(3, 10000, order);
+
+        long start = System.currentTimeMillis();
+        fixture.trainSessions(Arrays.asList(tester.userSession), order);
+        System.out.println("testing session with 10000 task instances and 3 symbols took " +
+                           (System.currentTimeMillis() - start) + "ms");
+        
+        fixture.process(tester);
+        
+        // do not check if counts is empty, as some sequences may not be part of the reduced trie
+        // and may therefore not be processed by the tester.
+        //assertTrue(tester.counts.isEmpty());
+    }
+
+    @Test
+    public void testLargeTaskInstanceTrie_8() throws Exception {
+        TaskInstanceTrie fixture = new TaskInstanceTrie(comparator);
+
+        int order = 3;
+        
+        TaskInstanceTrieTester tester = new TaskInstanceTrieTester(30, 10000, order);
+
+        long start = System.currentTimeMillis();
+        fixture.trainSessions(Arrays.asList(tester.userSession), order);
+        System.out.println("testing session with 10000 task instances and 30 symbols took " +
+                           (System.currentTimeMillis() - start) + "ms");
+        
+        fixture.process(tester);
+        
+        // do not check if counts is empty, as some sequences may not be part of the reduced trie
+        // and may therefore not be processed by the tester.
+        //assertTrue(tester.counts.isEmpty());
+    }
+
+    @Test
+    public void testLargeTaskInstanceTrie_9() throws Exception {
+        TaskInstanceTrie fixture = new TaskInstanceTrie(comparator);
+
+        int order = 3;
+        
+        TaskInstanceTrieTester tester = new TaskInstanceTrieTester(300, 10000, order);
+
+        long start = System.currentTimeMillis();
+        fixture.trainSessions(Arrays.asList(tester.userSession), order);
+        System.out.println("testing session with 10000 task instances and 300 symbols took " +
+                           (System.currentTimeMillis() - start) + "ms");
+        
+        fixture.process(tester);
+        
+        // do not check if counts is empty, as some sequences may not be part of the reduced trie
+        // and may therefore not be processed by the tester.
+        //assertTrue(tester.counts.isEmpty());
+    }
+
+    @Test
+    public void testLargeTaskInstanceTrie_10() throws Exception {
+        TaskInstanceTrie fixture = new TaskInstanceTrie(comparator);
+
+        int order = 3;
+        
+        TaskInstanceTrieTester tester = new TaskInstanceTrieTester(1000, 10000, order);
+
+        long start = System.currentTimeMillis();
+        fixture.trainSessions(Arrays.asList(tester.userSession), order);
+        System.out.println("testing session with 10000 task instances and 1000 symbols took " +
+                           (System.currentTimeMillis() - start) + "ms");
+        
+        fixture.process(tester);
+        
+        // do not check if counts is empty, as some sequences may not be part of the reduced trie
+        // and may therefore not be processed by the tester.
+        //assertTrue(tester.counts.isEmpty());
+    }
+
+    @Test
+    public void testLargeTaskInstanceTrie_11() throws Exception {
+        TaskInstanceTrie fixture = new TaskInstanceTrie(comparator);
+
+        int order = 4;
+        
+        TaskInstanceTrieTester tester = new TaskInstanceTrieTester(3, 50, order);
+
+        long start = System.currentTimeMillis();
+        fixture.trainSessions(Arrays.asList(tester.userSession), order);
+        System.out.println("testing session with 50 task instances and 3 symbols took " +
+                           (System.currentTimeMillis() - start) + "ms");
+        
+        fixture.process(tester);
+        
+        // do not check if counts is empty, as some sequences may not be part of the reduced trie
+        // and may therefore not be processed by the tester.
+        //assertTrue(tester.counts.isEmpty());
+    }
+
+    @Test
+    public void testLargeTaskInstanceTrie_12() throws Exception {
+        TaskInstanceTrie fixture = new TaskInstanceTrie(comparator);
+
+        int order = 4;
+        
+        TaskInstanceTrieTester tester = new TaskInstanceTrieTester(3, 10000, order);
+
+        long start = System.currentTimeMillis();
+        fixture.trainSessions(Arrays.asList(tester.userSession), order);
+        System.out.println("testing session with 10000 task instances and 3 symbols took " +
+                           (System.currentTimeMillis() - start) + "ms");
+        
+        fixture.process(tester);
+        
+        // do not check if counts is empty, as some sequences may not be part of the reduced trie
+        // and may therefore not be processed by the tester.
+        //assertTrue(tester.counts.isEmpty());
+    }
+
+    @Test
+    public void testLargeTaskInstanceTrie_13() throws Exception {
+        TaskInstanceTrie fixture = new TaskInstanceTrie(comparator);
+
+        int order = 4;
+        
+        TaskInstanceTrieTester tester = new TaskInstanceTrieTester(30, 10000, order);
+
+        long start = System.currentTimeMillis();
+        fixture.trainSessions(Arrays.asList(tester.userSession), order);
+        System.out.println("testing session with 10000 task instances and 30 symbols took " +
+                           (System.currentTimeMillis() - start) + "ms");
+        
+        fixture.process(tester);
+        
+        // do not check if counts is empty, as some sequences may not be part of the reduced trie
+        // and may therefore not be processed by the tester.
+        //assertTrue(tester.counts.isEmpty());
+    }
+
+    @Test
+    public void testLargeTaskInstanceTrie_14() throws Exception {
+        TaskInstanceTrie fixture = new TaskInstanceTrie(comparator);
+
+        int order = 4;
+        
+        TaskInstanceTrieTester tester = new TaskInstanceTrieTester(300, 10000, order);
+
+        long start = System.currentTimeMillis();
+        fixture.trainSessions(Arrays.asList(tester.userSession), order);
+        System.out.println("testing session with 10000 task instances and 300 symbols took " +
+                           (System.currentTimeMillis() - start) + "ms");
+        
+        fixture.process(tester);
+        
+        // do not check if counts is empty, as some sequences may not be part of the reduced trie
+        // and may therefore not be processed by the tester.
+        //assertTrue(tester.counts.isEmpty());
+    }
+
+    @Test
+    public void testLargeTaskInstanceTrie_15() throws Exception {
+        TaskInstanceTrie fixture = new TaskInstanceTrie(comparator);
+
+        int order = 4;
+        
+        TaskInstanceTrieTester tester = new TaskInstanceTrieTester(1000, 10000, order);
+
+        long start = System.currentTimeMillis();
+        fixture.trainSessions(Arrays.asList(tester.userSession), order);
+        System.out.println("testing session with 10000 task instances and 1000 symbols took " +
+                           (System.currentTimeMillis() - start) + "ms");
+        
+        fixture.process(tester);
+        
+        // do not check if counts is empty, as some sequences may not be part of the reduced trie
+        // and may therefore not be processed by the tester.
+        //assertTrue(tester.counts.isEmpty());
+    }
+
+    @Test
+    public void testLargeTaskInstanceTrie_16() throws Exception {
+        TaskInstanceTrie fixture = new TaskInstanceTrie(comparator);
+
+        int order = 5;
+        
+        TaskInstanceTrieTester tester = new TaskInstanceTrieTester(3, 50, order);
+
+        long start = System.currentTimeMillis();
+        fixture.trainSessions(Arrays.asList(tester.userSession), order);
+        System.out.println("testing session with 50 task instances and 3 symbols took " +
+                           (System.currentTimeMillis() - start) + "ms");
+        
+        fixture.process(tester);
+        
+        // do not check if counts is empty, as some sequences may not be part of the reduced trie
+        // and may therefore not be processed by the tester.
+        //assertTrue(tester.counts.isEmpty());
+    }
+
+    @Test
+    public void testLargeTaskInstanceTrie_17() throws Exception {
+        TaskInstanceTrie fixture = new TaskInstanceTrie(comparator);
+
+        int order = 5;
+        
+        TaskInstanceTrieTester tester = new TaskInstanceTrieTester(3, 10000, order);
+
+        long start = System.currentTimeMillis();
+        fixture.trainSessions(Arrays.asList(tester.userSession), order);
+        System.out.println("testing session with 10000 task instances and 3 symbols took " +
+                           (System.currentTimeMillis() - start) + "ms");
+        
+        fixture.process(tester);
+        
+        // do not check if counts is empty, as some sequences may not be part of the reduced trie
+        // and may therefore not be processed by the tester.
+        //assertTrue(tester.counts.isEmpty());
+    }
+
+    @Test
+    public void testLargeTaskInstanceTrie_18() throws Exception {
+        TaskInstanceTrie fixture = new TaskInstanceTrie(comparator);
+
+        int order = 5;
+        
+        TaskInstanceTrieTester tester = new TaskInstanceTrieTester(30, 10000, order);
+
+        long start = System.currentTimeMillis();
+        fixture.trainSessions(Arrays.asList(tester.userSession), order);
+        System.out.println("testing session with 10000 task instances and 30 symbols took " +
+                           (System.currentTimeMillis() - start) + "ms");
+        
+        fixture.process(tester);
+        
+        // do not check if counts is empty, as some sequences may not be part of the reduced trie
+        // and may therefore not be processed by the tester.
+        //assertTrue(tester.counts.isEmpty());
+    }
+
+    @Test
+    public void testLargeTaskInstanceTrie_19() throws Exception {
+        TaskInstanceTrie fixture = new TaskInstanceTrie(comparator);
+
+        int order = 5;
+        
+        TaskInstanceTrieTester tester = new TaskInstanceTrieTester(300, 10000, order);
+
+        long start = System.currentTimeMillis();
+        fixture.trainSessions(Arrays.asList(tester.userSession), order);
+        System.out.println("testing session with 10000 task instances and 300 symbols took " +
+                           (System.currentTimeMillis() - start) + "ms");
+        
+        fixture.process(tester);
+        
+        // do not check if counts is empty, as some sequences may not be part of the reduced trie
+        // and may therefore not be processed by the tester.
+        //assertTrue(tester.counts.isEmpty());
+    }
+
+    @Test
+    public void testLargeTaskInstanceTrie_20() throws Exception {
+        TaskInstanceTrie fixture = new TaskInstanceTrie(comparator);
+
+        int order = 5;
+        
+        TaskInstanceTrieTester tester = new TaskInstanceTrieTester(1000, 10000, order);
+
+        long start = System.currentTimeMillis();
+        fixture.trainSessions(Arrays.asList(tester.userSession), order);
+        System.out.println("testing session with 10000 task instances and 1000 symbols took " +
+                           (System.currentTimeMillis() - start) + "ms");
+        
+        fixture.process(tester);
+        
+        // do not check if counts is empty, as some sequences may not be part of the reduced trie
+        // and may therefore not be processed by the tester.
+        //assertTrue(tester.counts.isEmpty());
+    }
+
+    @Test
+    public void testLargeTaskInstanceTrie_21() throws Exception {
+        TaskInstanceTrie fixture = new TaskInstanceTrie(comparator);
+
+        int order = 6;
+        
+        TaskInstanceTrieTester tester = new TaskInstanceTrieTester(3, 50, order);
+
+        long start = System.currentTimeMillis();
+        fixture.trainSessions(Arrays.asList(tester.userSession), order);
+        System.out.println("testing session with 50 task instances and 3 symbols took " +
+                           (System.currentTimeMillis() - start) + "ms");
+        
+        fixture.process(tester);
+        
+        // do not check if counts is empty, as some sequences may not be part of the reduced trie
+        // and may therefore not be processed by the tester.
+        //assertTrue(tester.counts.isEmpty());
+    }
+
+    @Test
+    public void testLargeTaskInstanceTrie_22() throws Exception {
+        TaskInstanceTrie fixture = new TaskInstanceTrie(comparator);
+
+        int order = 6;
+        
+        TaskInstanceTrieTester tester = new TaskInstanceTrieTester(3, 10000, order);
+
+        long start = System.currentTimeMillis();
+        fixture.trainSessions(Arrays.asList(tester.userSession), order);
+        System.out.println("testing session with 10000 task instances and 3 symbols took " +
+                           (System.currentTimeMillis() - start) + "ms");
+        
+        fixture.process(tester);
+        
+        // do not check if counts is empty, as some sequences may not be part of the reduced trie
+        // and may therefore not be processed by the tester.
+        //assertTrue(tester.counts.isEmpty());
+    }
+
+    @Test
+    public void testLargeTaskInstanceTrie_23() throws Exception {
+        TaskInstanceTrie fixture = new TaskInstanceTrie(comparator);
+
+        int order = 6;
+        
+        TaskInstanceTrieTester tester = new TaskInstanceTrieTester(30, 10000, order);
+
+        long start = System.currentTimeMillis();
+        fixture.trainSessions(Arrays.asList(tester.userSession), order);
+        System.out.println("testing session with 10000 task instances and 30 symbols took " +
+                           (System.currentTimeMillis() - start) + "ms");
+        
+        fixture.process(tester);
+        
+        // do not check if counts is empty, as some sequences may not be part of the reduced trie
+        // and may therefore not be processed by the tester.
+        //assertTrue(tester.counts.isEmpty());
+    }
+
+    @Test
+    public void testLargeTaskInstanceTrie_24() throws Exception {
+        TaskInstanceTrie fixture = new TaskInstanceTrie(comparator);
+
+        int order = 6;
+        
+        TaskInstanceTrieTester tester = new TaskInstanceTrieTester(300, 10000, order);
+
+        long start = System.currentTimeMillis();
+        fixture.trainSessions(Arrays.asList(tester.userSession), order);
+        System.out.println("testing session with 10000 task instances and 300 symbols took " +
+                           (System.currentTimeMillis() - start) + "ms");
+        
+        fixture.process(tester);
+        
+        // do not check if counts is empty, as some sequences may not be part of the reduced trie
+        // and may therefore not be processed by the tester.
+        //assertTrue(tester.counts.isEmpty());
+    }
+
+    @Test
+    public void testLargeTaskInstanceTrie_25() throws Exception {
+        TaskInstanceTrie fixture = new TaskInstanceTrie(comparator);
+
+        int order = 6;
+        
+        TaskInstanceTrieTester tester = new TaskInstanceTrieTester(1000, 10000, order);
+
+        long start = System.currentTimeMillis();
+        fixture.trainSessions(Arrays.asList(tester.userSession), order);
+        System.out.println("testing session with 10000 task instances and 1000 symbols took " +
+                           (System.currentTimeMillis() - start) + "ms");
+        
+        fixture.process(tester);
+        
+        // do not check if counts is empty, as some sequences may not be part of the reduced trie
+        // and may therefore not be processed by the tester.
+        //assertTrue(tester.counts.isEmpty());
+    }
+
+    /**
+     * 
+     */
+    private void assertContains(List<List<ITaskInstance>> listOfList,
+                                List<ITaskInstance>       containedList)
+    {
+        boolean found = false;
+        for (List<ITaskInstance> candidate : listOfList) {
+            if (candidate.size() == containedList.size()) {
+                found = true;
+                for (int i = 0; i < containedList.size(); i++) {
+                    if (!comparator.equals(candidate.get(0), containedList.get(0))) {
+                        found = false;
+                        break;
+                    }
+                }
+                
+                if (found) {
+                    break;
+                }
+            }
+        }
+            
+        assertTrue(found);
+    }
+
+    public static void main(String[] args) {
+        new org.junit.runner.JUnitCore().run(TaskInstanceTrieTest.class);
+    }
+    
+    /**
+     * <p>
+     * class internally used for testing large tries.
+     * </p>
+     * 
+     * @author Patrick Harms
+     */
+    private class TaskInstanceTrieTester implements TrieProcessor<ITaskInstance> {
+        
+        /**
+         * the symbols used for testing the trie
+         */
+        private Map<Integer, ITaskInstance> symbols = new HashMap<Integer, ITaskInstance>();
+
+        /**
+         * the simulated sequence
+         */
+        private IUserSession userSession;
+
+        /**
+         * the trained order of the tested trie
+         */
+        private int maxOrder;
+        
+        /**
+         * the expected counts of subsequences
+         */
+        private Map<Long, Integer> counts = new HashMap<Long, Integer>();
+        
+        /**
+         * the maximal observed count of a subsequence
+         */
+        private int maxCount = 0;
+
+        /**
+         * generates a simulated sequence and thereby stores the expected counts of the
+         * subsequences up to max order in a map. The technique uses integer and long values
+         * to be efficient and to allow testing with large sequences and symbol numbers. However,
+         * the technique is restricted to 1024 different symbols and a maximum tree depth of 6.
+         * The tester is also used as a trie processor to check for any node in the tree, if the
+         * trie calculated the count correctly and if it did not create too many nodes.
+         */
+        public TaskInstanceTrieTester(int noOfSymbols, int sequenceLength, int maxOrder) {
+            if (noOfSymbols > 1024) {
+                throw new IllegalArgumentException("too large number of symbols");
+            }
+            if (maxOrder > 6) {
+                throw new IllegalArgumentException("too large number of symbols");
+            }
+            
+            StringBuffer dummyUserSessionDef = new StringBuffer("UserSession {");
+            for (int i = 0; i < noOfSymbols; i++) {
+                dummyUserSessionDef.append("  Event action");
+                dummyUserSessionDef.append(i);
+                dummyUserSessionDef.append(" {}");
+            }
+            dummyUserSessionDef.append("}");
+            
+            IUserSession dummySession =
+                (IUserSession) decoder.decode(dummyUserSessionDef.toString());
+            
+            for (int i = 0; i < dummySession.size(); i++) {
+                this.symbols.put(i, dummySession.get(i));
+            }
+            
+            this.maxOrder = maxOrder;
+            
+            dummyUserSessionDef = new StringBuffer("UserSession {");
+            int[] symbolIds = new int[sequenceLength];
+
+            for (int i = 0; i < sequenceLength; i++) {
+                int symbolIndex = (int) (Math.random() * noOfSymbols);
+                dummyUserSessionDef.append("  Event action");
+                dummyUserSessionDef.append(symbolIndex);
+                dummyUserSessionDef.append(" {}");
+                
+                symbolIds[i] = symbolIndex;
+                
+                if ((i - maxOrder + 1) >= 0) {
+                    storeCounts(symbolIds, i - maxOrder + 1, i);
+                }
+            }
+            dummyUserSessionDef.append("}");
+            
+            this.userSession = (IUserSession) decoder.decode(dummyUserSessionDef.toString());
+            
+            for (int i = sequenceLength - maxOrder + 1; i < sequenceLength; i++) {
+                storeCounts(symbolIds, i, sequenceLength - 1);
+            }
+        }
+
+        /**
+         * <p>
+         * stores the counts for the subsequence denoted by the start and end index (inclusive).
+         * </p>
+         */
+        private void storeCounts(int[] sequence, int startIndex, int endIndex) {
+            long key = 0;
+            
+            for (int i = startIndex; i <= endIndex; i++) {
+                key = key << 10;
+                key += 1 + sequence[i];
+            
+                Integer count = this.counts.get(key);
+                if (count == null) {
+                    count = 0;
+                }
+            
+                //System.out.println(key + "  " + (count + 1));
+                
+                count++;
+                this.counts.put(key, count);
+                
+                maxCount = Math.max(count, maxCount);
+            }
+        }
+
+        /* (non-Javadoc)
+         * @see de.ugoe.cs.autoquest.usageprofiles.TaskInstanceTrieProcessor#process(List, int)
+         */
+        @Override
+        public TrieProcessor.Result process(List<ITaskInstance> sequence, int count) {
+            long key = 0;
+            
+            for (ITaskInstance symbol : sequence) {
+                int symbolIndex = -1;
+                
+                for (Map.Entry<Integer, ITaskInstance> entry : symbols.entrySet()) {
+                    if (comparator.equals(entry.getValue(), symbol)) {
+                        symbolIndex = entry.getKey();
+                        break;
+                    }
+                }
+                
+                assertTrue("could not find symbol", symbolIndex > -1);
+                
+                key = key << 10;
+                key += 1 + symbolIndex;
+            }
+            
+            Integer expectedCount = this.counts.remove(key);
+            assertNotNull(expectedCount);
+            
+            if (count == maxCount) {
+                assertEquals(expectedCount.intValue(), count);
+            }
+            else {
+                assertTrue(count < maxCount);
+            }
+            
+            assertTrue(sequence.size() <= this.maxOrder);
+            
+            return TrieProcessor.Result.CONTINUE;
+        }
+
+    }
+}