//   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 Patrick Harms
 * @version 1.0
 */
public class TaskInstanceTrieTest {

    /** */
    private ITaskBuilder taskBuilder = new TaskBuilder();

    /** */
    private ITaskFactory taskFactory = new TaskFactory();
    
    /** */
    private TaskTreeDecoder decoder = new TaskTreeDecoder(taskFactory, taskBuilder);
    
    /** */
    private TaskHandlingStrategy strategy =
        new TaskHandlingStrategy(TaskEquality.IDENTICAL);
    
    /** */
    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(strategy);

        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((TaskHandlingStrategy) null);
    }

    @Test
    public void testTrainSessions_1() throws Exception {
        TaskInstanceTrie fixture = new TaskInstanceTrie(strategy);
        
        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(strategy);
        
        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(strategy);
        
        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(strategy);
        
        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(strategy);
        
        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(strategy);
        
        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(strategy);
        
        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(strategy);
        
        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(strategy);
        
        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(strategy);
        
        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(strategy);
        
        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(strategy);
            
        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(strategy);
                
        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(strategy);
                
        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(strategy);
                
        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(strategy);
                
        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(strategy);
            
        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(strategy);
            
        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(strategy);
               
        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(strategy);
                
        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(strategy);
                
        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(strategy);
                
        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(strategy);
                    
        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(strategy);
                        
        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(strategy);
                            
        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(strategy);
                            
        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(strategy);
                            
        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(strategy);
                                
        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(strategy);
                                
        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(strategy);
                                    
        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(strategy);
                                        
        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(strategy);
                                        
        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(strategy);
                                            
        fixture.trainSessions(Arrays.asList(session), 3);

        int result = fixture.getNumLeafAncestors();

        assertEquals(7, result);
    }

    @Test
    public void testGetNumLeafs_1() throws Exception {
        TaskInstanceTrie fixture = new TaskInstanceTrie(strategy);
                                            
        fixture.trainSessions(Arrays.asList(session), 3);

        int result = fixture.getNumLeafs();

        assertEquals(7, result);
    }

    @Test
    public void testGetNumSymbols_1() throws Exception {
        TaskInstanceTrie fixture = new TaskInstanceTrie(strategy);
                                            
        fixture.trainSessions(Arrays.asList(session), 3);


        int result = fixture.getNumSymbols();

        assertEquals(5, result);
    }

    @Test
    public void testLargeTaskInstanceTrie_1() throws Exception {
        TaskInstanceTrie fixture = new TaskInstanceTrie(strategy);

        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(strategy);

        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(strategy);

        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(strategy);

        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(strategy);

        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(strategy);

        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(strategy);

        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(strategy);

        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(strategy);

        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(strategy);

        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(strategy);

        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(strategy);

        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(strategy);

        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(strategy);

        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(strategy);

        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(strategy);

        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(strategy);

        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(strategy);

        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(strategy);

        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(strategy);

        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(strategy);

        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(strategy);

        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(strategy);

        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(strategy);

        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(strategy);

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

    @Test
    public void testLargeTaskInstanceTrie_26() throws Exception {
        TaskInstanceTrie fixture = new TaskInstanceTrie(strategy);

        int order = 3;
        
        TaskInstanceTrieTester tester = new TaskInstanceTrieTester(1000, 100000, order);

        long start = System.currentTimeMillis();
        fixture.trainSessions(Arrays.asList(tester.userSession), order);
        System.out.println("testing session with 100000 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 (!strategy.getTaskComparator().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 (strategy.getTaskComparator().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;
        }

    }
}