//   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.usageprofiles;

import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;

import junitx.framework.ListAssert;

import org.junit.*;

import de.ugoe.cs.autoquest.usageprofiles.Trie;
import de.ugoe.cs.autoquest.usageprofiles.TrieNode;
import de.ugoe.cs.autoquest.usageprofiles.Trie.Edge;
import de.ugoe.cs.autoquest.usageprofiles.Trie.TrieVertex;
import static org.junit.Assert.*;

/**
 * The class <code>TrieTest</code> contains tests for the class <code>{@link Trie}</code>.
 * 
 * @author Steffen Herbold
 * @version 1.0
 */
public class TrieTest {

    List<String> sequence;
    Collection<String> symbols;

    private static void assertCollectionContent(Collection<?> c1, Collection<?> c2) {
        assertEquals(c1.size(), c2.size());
        for (Object obj : c1) {
            assertTrue(c2.contains(obj));
        }
    }

    @Test
    public void testTrie_1() throws Exception {

        Trie<String> result = new Trie<String>();

        assertNotNull(result);
        assertEquals(0, result.getNumLeafs());
        assertEquals(0, result.getNumSymbols());
        assertEquals(0, result.getNumLeafAncestors());
        assertTrue(result.getKnownSymbols().isEmpty());
    }

    @Test
    public void testTrie_2() throws Exception {
        Trie<String> trie1 = new Trie<String>();
        trie1.train(sequence, 3);

        Trie<String> result = new Trie<String>(trie1);

        assertEquals(trie1, result);
        assertNotSame(trie1, result);
    }

    @Test(expected = java.lang.IllegalArgumentException.class)
    public void testTrie_3() throws Exception {
        new Trie<String>((SymbolComparator<String>) null);
    }

    @Test(expected = java.lang.IllegalArgumentException.class)
    public void testTrie_4() throws Exception {
        new Trie<String>((Trie<String>) null);
    }

    @Test
    public void testAdd_1() throws Exception {
        Trie<String> fixture = new Trie<String>();
        List<String> seq = new ArrayList<String>();
        seq.add("a");
        seq.add("b");

        fixture.add(seq);

        assertEquals(1, fixture.getChild("a").getCount());
        assertEquals(1, fixture.getChild("a").getChild("b").getCount());
        assertNull(fixture.getChild("b"));
    }

    @Test
    public void testAdd_2() throws Exception {
        Trie<String> fixture = new Trie<String>();

        fixture.add(new ArrayList<String>());

        assertEquals(0, fixture.getNumSymbols());
    }

    @Test
    public void testAdd_3() throws Exception {
        Trie<String> fixture = new Trie<String>();

        fixture.add(null);

        assertEquals(0, fixture.getNumSymbols());
    }

    @Test
    public void testFind_1() throws Exception {
        Trie<String> fixture = new Trie<String>();
        fixture.train(sequence, 3);
        List<String> findSequence = new ArrayList<String>();
        findSequence.add("a");
        findSequence.add("b");
        findSequence.add("r");
        TrieNode<String> expected = fixture.getChild("a").getChild("b").getChild("r");

        TrieNode<String> result = fixture.find(findSequence);

        assertEquals(expected, result);
    }

    @Test
    public void testFind_2() throws Exception {
        Trie<String> fixture = new Trie<String>();
        fixture.train(sequence, 3);
        List<String> findSequence = new ArrayList<String>();
        findSequence.add("c");
        findSequence.add("a");
        TrieNode<String> expected = fixture.getChild("c").getChild("a");

        TrieNode<String> result = fixture.find(findSequence);

        assertEquals(expected, result);
    }

    @Test
    public void testFind_3() throws Exception {
        Trie<String> fixture = new Trie<String>();
        fixture.train(sequence, 3);
        List<String> findSequence = new ArrayList<String>();

        TrieNode<String> result = fixture.find(findSequence);

        assertTrue(result.isRoot());
    }

    @Test
    public void testFind_4() throws Exception {
        Trie<String> fixture = new Trie<String>();
        fixture.train(sequence, 3);

        TrieNode<String> result = fixture.find(null);

        assertTrue(result.isRoot());
    }

    @Test
    public void testGetChildCreate_1() throws Exception {
        Trie<String> fixture = new Trie<String>();
        String symbol = "a";

        TrieNode<String> result = fixture.getChildCreate(symbol);

        assertEquals(symbol, result.getSymbol());
        assertEquals(0, result.getCount());
        assertTrue(result.isLeaf());
    }

    @Test(expected = java.lang.IllegalArgumentException.class)
    public void testGetChildCreate_2() throws Exception {
        Trie<String> fixture = new Trie<String>();
        fixture.getChildCreate(null);
    }

    @Test
    public void testGetContextSuffix_1() throws Exception {
        Trie<String> fixture = new Trie<String>();
        fixture.train(sequence, 3);
        List<String> context = new ArrayList<String>();
        context.add("a");
        context.add("a");
        context.add("b");
        List<String> expected = new ArrayList<String>();
        expected.add("a");
        expected.add("b");

        List<String> result = fixture.getContextSuffix(context);

        ListAssert.assertEquals(expected, result);
    }

    @Test
    public void testGetContextSuffix_2() throws Exception {
        Trie<String> fixture = new Trie<String>();
        fixture.train(sequence, 3);
        List<String> context = new ArrayList<String>();
        context.add("a");
        context.add("a");
        context.add("b");
        context.add("r");
        List<String> expected = new ArrayList<String>();
        expected.add("b");
        expected.add("r");

        List<String> result = fixture.getContextSuffix(context);

        ListAssert.assertEquals(expected, result);
    }

    @Test
    public void testGetContextSuffix_3() throws Exception {
        Trie<String> fixture = new Trie<String>();
        fixture.train(sequence, 3);
        List<String> context = new ArrayList<String>();
        context.add("a");
        context.add("a");
        context.add("b");
        context.add("x");
        List<String> expected = new ArrayList<String>();

        List<String> result = fixture.getContextSuffix(context);

        ListAssert.assertEquals(expected, result);
    }

    @Test
    public void testGetContextSuffix_4() throws Exception {
        Trie<String> fixture = new Trie<String>();

        List<String> result = fixture.getContextSuffix(null);

        // add additional test code here
        assertNotNull(result);
        assertEquals(0, result.size());
    }

    @Test
    public void testGetContextSuffix_5() throws Exception {
        Trie<String> fixture = new Trie<String>();
        fixture.train(sequence, 3);
        List<String> context = new ArrayList<String>();
        context.add("a");
        context.add("a");
        context.add("b");
        List<String> expected = new ArrayList<String>();
        expected.add("a");
        expected.add("b");

        List<String> result = fixture.getContextSuffix(context);

        ListAssert.assertEquals(expected, result);
    }

    @Test
    public void testProcessWithTrieProcessor_1() throws Exception {
        Trie<String> fixture = new Trie<String>();
        fixture.train(sequence, 2);

        final List<String> sequences = new ArrayList<String>();
        TrieProcessor<String> processor = new TrieProcessor<String>() {
            @Override
            public TrieProcessor.Result process(List<String> sequence, int count) {
                sequences.add(count + "_" + sequence.toString());
                return TrieProcessor.Result.CONTINUE;
            }

        };

        fixture.process(processor);

        List<String> expected = new ArrayList<String>();

        expected.add("5_[a]");
        expected.add("2_[a, b]");
        expected.add("2_[b]");
        expected.add("2_[b, r]");
        expected.add("2_[r]");
        expected.add("2_[r, a]");
        expected.add("1_[a, c]");
        expected.add("1_[c]");
        expected.add("1_[c, a]");
        expected.add("1_[a, d]");
        expected.add("1_[d]");
        expected.add("1_[d, a]");

        assertEquals(expected.size(), sequences.size());

        for (String sequence : sequences) {
            ListAssert.assertContains(expected, sequence);
        }
    }

    @Test
    public void testProcessWithTrieProcessor_2() throws Exception {
        Trie<String> fixture = new Trie<String>();
        fixture.train(sequence, 3);

        final List<String> sequences = new ArrayList<String>();
        TrieProcessor<String> processor = new TrieProcessor<String>() {
            @Override
            public TrieProcessor.Result process(List<String> sequence, int count) {
                sequences.add(count + "_" + sequence.toString());
                return TrieProcessor.Result.CONTINUE;
            }

        };

        fixture.process(processor);

        List<String> expected = new ArrayList<String>();

        expected.add("5_[a]");
        expected.add("2_[a, b]");
        expected.add("2_[a, b, r]");
        expected.add("2_[b]");
        expected.add("2_[b, r]");
        expected.add("2_[b, r, a]");
        expected.add("2_[r]");
        expected.add("2_[r, a]");
        expected.add("1_[r, a, c]");
        expected.add("1_[a, c]");
        expected.add("1_[a, c, a]");
        expected.add("1_[c]");
        expected.add("1_[c, a]");
        expected.add("1_[c, a, d]");
        expected.add("1_[a, d]");
        expected.add("1_[a, d, a]");
        expected.add("1_[d]");
        expected.add("1_[d, a]");
        expected.add("1_[d, a, b]");

        assertEquals(expected.size(), sequences.size());

        for (String sequence : sequences) {
            ListAssert.assertContains(expected, sequence);
        }
    }

    @Test
    public void testProcessWithTrieProcessor_3() throws Exception {
        Trie<String> fixture = new Trie<String>();
        fixture.train(sequence, 4);

        final List<String> sequences = new ArrayList<String>();
        TrieProcessor<String> processor = new TrieProcessor<String>() {
            @Override
            public TrieProcessor.Result process(List<String> sequence, int count) {
                sequences.add(count + "_" + sequence.toString());
                return TrieProcessor.Result.CONTINUE;
            }

        };

        fixture.process(processor);

        List<String> expected = new ArrayList<String>();

        expected.add("5_[a]");
        expected.add("2_[a, b]");
        expected.add("2_[a, b, r]");
        expected.add("2_[a, b, r, a]");
        expected.add("2_[b]");
        expected.add("2_[b, r]");
        expected.add("2_[b, r, a]");
        expected.add("1_[b, r, a, c]");
        expected.add("2_[r]");
        expected.add("2_[r, a]");
        expected.add("1_[r, a, c]");
        expected.add("1_[r, a, c, a]");
        expected.add("1_[a, c]");
        expected.add("1_[a, c, a]");
        expected.add("1_[a, c, a, d]");
        expected.add("1_[c]");
        expected.add("1_[c, a]");
        expected.add("1_[c, a, d]");
        expected.add("1_[c, a, d, a]");
        expected.add("1_[a, d]");
        expected.add("1_[a, d, a]");
        expected.add("1_[a, d, a, b]");
        expected.add("1_[d]");
        expected.add("1_[d, a]");
        expected.add("1_[d, a, b]");
        expected.add("1_[d, a, b, r]");

        assertEquals(expected.size(), sequences.size());

        for (String sequence : sequences) {
            ListAssert.assertContains(expected, sequence);
        }
    }

    @Test
    public void testProcessWithTrieProcessor_4() throws Exception {
        Trie<String> fixture = new Trie<String>();
        fixture.train(sequence, 5);

        final List<String> sequences = new ArrayList<String>();
        TrieProcessor<String> processor = new TrieProcessor<String>() {
            @Override
            public TrieProcessor.Result process(List<String> sequence, int count) {
                sequences.add(count + "_" + sequence.toString());
                return TrieProcessor.Result.CONTINUE;
            }

        };

        fixture.process(processor);

        List<String> expected = new ArrayList<String>();

        expected.add("5_[a]");
        expected.add("2_[a, b]");
        expected.add("2_[a, b, r]");
        expected.add("2_[a, b, r, a]");
        expected.add("1_[a, b, r, a, c]");
        expected.add("2_[b]");
        expected.add("2_[b, r]");
        expected.add("2_[b, r, a]");
        expected.add("1_[b, r, a, c]");
        expected.add("1_[b, r, a, c, a]");
        expected.add("2_[r]");
        expected.add("2_[r, a]");
        expected.add("1_[r, a, c]");
        expected.add("1_[r, a, c, a]");
        expected.add("1_[r, a, c, a, d]");
        expected.add("1_[a, c]");
        expected.add("1_[a, c, a]");
        expected.add("1_[a, c, a, d]");
        expected.add("1_[a, c, a, d, a]");
        expected.add("1_[c]");
        expected.add("1_[c, a]");
        expected.add("1_[c, a, d]");
        expected.add("1_[c, a, d, a]");
        expected.add("1_[c, a, d, a, b]");
        expected.add("1_[a, d]");
        expected.add("1_[a, d, a]");
        expected.add("1_[a, d, a, b]");
        expected.add("1_[a, d, a, b, r]");
        expected.add("1_[d]");
        expected.add("1_[d, a]");
        expected.add("1_[d, a, b]");
        expected.add("1_[d, a, b, r]");
        expected.add("1_[d, a, b, r, a]");

        assertEquals(expected.size(), sequences.size());

        for (String sequence : sequences) {
            ListAssert.assertContains(expected, sequence);
        }
    }

    @Test
    public void testProcessWithTrieProcessor_5() throws Exception {
        Trie<String> fixture = new Trie<String>();
        fixture.train(sequence, 6);

        final List<String> sequences = new ArrayList<String>();
        TrieProcessor<String> processor = new TrieProcessor<String>() {
            @Override
            public TrieProcessor.Result process(List<String> sequence, int count) {
                sequences.add(count + "_" + sequence.toString());
                return TrieProcessor.Result.CONTINUE;
            }

        };

        fixture.process(processor);

        List<String> expected = new ArrayList<String>();

        expected.add("5_[a]");
        expected.add("2_[a, b]");
        expected.add("2_[a, b, r]");
        expected.add("2_[a, b, r, a]");
        expected.add("1_[a, b, r, a, c]");
        expected.add("1_[a, b, r, a, c, a]");
        expected.add("2_[b]");
        expected.add("2_[b, r]");
        expected.add("2_[b, r, a]");
        expected.add("1_[b, r, a, c]");
        expected.add("1_[b, r, a, c, a]");
        expected.add("1_[b, r, a, c, a, d]");
        expected.add("2_[r]");
        expected.add("2_[r, a]");
        expected.add("1_[r, a, c]");
        expected.add("1_[r, a, c, a]");
        expected.add("1_[r, a, c, a, d]");
        expected.add("1_[r, a, c, a, d, a]");
        expected.add("1_[a, c]");
        expected.add("1_[a, c, a]");
        expected.add("1_[a, c, a, d]");
        expected.add("1_[a, c, a, d, a]");
        expected.add("1_[a, c, a, d, a, b]");
        expected.add("1_[c]");
        expected.add("1_[c, a]");
        expected.add("1_[c, a, d]");
        expected.add("1_[c, a, d, a]");
        expected.add("1_[c, a, d, a, b]");
        expected.add("1_[c, a, d, a, b, r]");
        expected.add("1_[a, d]");
        expected.add("1_[a, d, a]");
        expected.add("1_[a, d, a, b]");
        expected.add("1_[a, d, a, b, r]");
        expected.add("1_[a, d, a, b, r, a]");
        expected.add("1_[d]");
        expected.add("1_[d, a]");
        expected.add("1_[d, a, b]");
        expected.add("1_[d, a, b, r]");
        expected.add("1_[d, a, b, r, a]");

        assertEquals(expected.size(), sequences.size());

        for (String sequence : sequences) {
            ListAssert.assertContains(expected, sequence);
        }
    }

    @Test
    public void testProcessWithTrieProcessor_6() throws Exception {
        Trie<String> fixture = new Trie<String>();
        fixture.train(sequence, 7);

        final List<String> sequences = new ArrayList<String>();
        TrieProcessor<String> processor = new TrieProcessor<String>() {
            @Override
            public TrieProcessor.Result process(List<String> sequence, int count) {
                sequences.add(count + "_" + sequence.toString());
                return TrieProcessor.Result.CONTINUE;
            }

        };

        fixture.process(processor);

        List<String> expected = new ArrayList<String>();

        expected.add("5_[a]");
        expected.add("2_[a, b]");
        expected.add("2_[a, b, r]");
        expected.add("2_[a, b, r, a]");
        expected.add("1_[a, b, r, a, c]");
        expected.add("1_[a, b, r, a, c, a]");
        expected.add("1_[a, b, r, a, c, a, d]");
        expected.add("2_[b]");
        expected.add("2_[b, r]");
        expected.add("2_[b, r, a]");
        expected.add("1_[b, r, a, c]");
        expected.add("1_[b, r, a, c, a]");
        expected.add("1_[b, r, a, c, a, d]");
        expected.add("1_[b, r, a, c, a, d, a]");
        expected.add("2_[r]");
        expected.add("2_[r, a]");
        expected.add("1_[r, a, c]");
        expected.add("1_[r, a, c, a]");
        expected.add("1_[r, a, c, a, d]");
        expected.add("1_[r, a, c, a, d, a]");
        expected.add("1_[r, a, c, a, d, a, b]");
        expected.add("1_[a, c]");
        expected.add("1_[a, c, a]");
        expected.add("1_[a, c, a, d]");
        expected.add("1_[a, c, a, d, a]");
        expected.add("1_[a, c, a, d, a, b]");
        expected.add("1_[a, c, a, d, a, b, r]");
        expected.add("1_[c]");
        expected.add("1_[c, a]");
        expected.add("1_[c, a, d]");
        expected.add("1_[c, a, d, a]");
        expected.add("1_[c, a, d, a, b]");
        expected.add("1_[c, a, d, a, b, r]");
        expected.add("1_[c, a, d, a, b, r, a]");
        expected.add("1_[a, d]");
        expected.add("1_[a, d, a]");
        expected.add("1_[a, d, a, b]");
        expected.add("1_[a, d, a, b, r]");
        expected.add("1_[a, d, a, b, r, a]");
        expected.add("1_[d]");
        expected.add("1_[d, a]");
        expected.add("1_[d, a, b]");
        expected.add("1_[d, a, b, r]");
        expected.add("1_[d, a, b, r, a]");

        assertEquals(expected.size(), sequences.size());

        for (String sequence : sequences) {
            ListAssert.assertContains(expected, sequence);
        }
    }

    @Test
    public void testProcessWithTrieProcessor_7() throws Exception {
        Trie<String> fixture = new Trie<String>();
        fixture.train(sequence, 8);

        final List<String> sequences = new ArrayList<String>();
        TrieProcessor<String> processor = new TrieProcessor<String>() {
            @Override
            public TrieProcessor.Result process(List<String> sequence, int count) {
                sequences.add(count + "_" + sequence.toString());
                return TrieProcessor.Result.CONTINUE;
            }

        };

        fixture.process(processor);

        List<String> expected = new ArrayList<String>();

        expected.add("5_[a]");
        expected.add("2_[a, b]");
        expected.add("2_[a, b, r]");
        expected.add("2_[a, b, r, a]");
        expected.add("1_[a, b, r, a, c]");
        expected.add("1_[a, b, r, a, c, a]");
        expected.add("1_[a, b, r, a, c, a, d]");
        expected.add("1_[a, b, r, a, c, a, d, a]");
        expected.add("2_[b]");
        expected.add("2_[b, r]");
        expected.add("2_[b, r, a]");
        expected.add("1_[b, r, a, c]");
        expected.add("1_[b, r, a, c, a]");
        expected.add("1_[b, r, a, c, a, d]");
        expected.add("1_[b, r, a, c, a, d, a]");
        expected.add("1_[b, r, a, c, a, d, a, b]");
        expected.add("2_[r]");
        expected.add("2_[r, a]");
        expected.add("1_[r, a, c]");
        expected.add("1_[r, a, c, a]");
        expected.add("1_[r, a, c, a, d]");
        expected.add("1_[r, a, c, a, d, a]");
        expected.add("1_[r, a, c, a, d, a, b]");
        expected.add("1_[r, a, c, a, d, a, b, r]");
        expected.add("1_[a, c]");
        expected.add("1_[a, c, a]");
        expected.add("1_[a, c, a, d]");
        expected.add("1_[a, c, a, d, a]");
        expected.add("1_[a, c, a, d, a, b]");
        expected.add("1_[a, c, a, d, a, b, r]");
        expected.add("1_[a, c, a, d, a, b, r, a]");
        expected.add("1_[c]");
        expected.add("1_[c, a]");
        expected.add("1_[c, a, d]");
        expected.add("1_[c, a, d, a]");
        expected.add("1_[c, a, d, a, b]");
        expected.add("1_[c, a, d, a, b, r]");
        expected.add("1_[c, a, d, a, b, r, a]");
        expected.add("1_[a, d]");
        expected.add("1_[a, d, a]");
        expected.add("1_[a, d, a, b]");
        expected.add("1_[a, d, a, b, r]");
        expected.add("1_[a, d, a, b, r, a]");
        expected.add("1_[d]");
        expected.add("1_[d, a]");
        expected.add("1_[d, a, b]");
        expected.add("1_[d, a, b, r]");
        expected.add("1_[d, a, b, r, a]");

        assertEquals(expected.size(), sequences.size());

        for (String sequence : sequences) {
            ListAssert.assertContains(expected, sequence);
        }
    }

    @Test
    public void testProcessWithTrieProcessor_8() throws Exception {
        Trie<String> fixture = new Trie<String>();
        fixture.train(sequence, 9);

        final List<String> sequences = new ArrayList<String>();
        TrieProcessor<String> processor = new TrieProcessor<String>() {
            @Override
            public TrieProcessor.Result process(List<String> sequence, int count) {
                sequences.add(count + "_" + sequence.toString());
                return TrieProcessor.Result.CONTINUE;
            }

        };

        fixture.process(processor);

        List<String> expected = new ArrayList<String>();

        expected.add("5_[a]");
        expected.add("2_[a, b]");
        expected.add("2_[a, b, r]");
        expected.add("2_[a, b, r, a]");
        expected.add("1_[a, b, r, a, c]");
        expected.add("1_[a, b, r, a, c, a]");
        expected.add("1_[a, b, r, a, c, a, d]");
        expected.add("1_[a, b, r, a, c, a, d, a]");
        expected.add("1_[a, b, r, a, c, a, d, a, b]");
        expected.add("2_[b]");
        expected.add("2_[b, r]");
        expected.add("2_[b, r, a]");
        expected.add("1_[b, r, a, c]");
        expected.add("1_[b, r, a, c, a]");
        expected.add("1_[b, r, a, c, a, d]");
        expected.add("1_[b, r, a, c, a, d, a]");
        expected.add("1_[b, r, a, c, a, d, a, b]");
        expected.add("1_[b, r, a, c, a, d, a, b, r]");
        expected.add("2_[r]");
        expected.add("2_[r, a]");
        expected.add("1_[r, a, c]");
        expected.add("1_[r, a, c, a]");
        expected.add("1_[r, a, c, a, d]");
        expected.add("1_[r, a, c, a, d, a]");
        expected.add("1_[r, a, c, a, d, a, b]");
        expected.add("1_[r, a, c, a, d, a, b, r]");
        expected.add("1_[r, a, c, a, d, a, b, r, a]");
        expected.add("1_[a, c]");
        expected.add("1_[a, c, a]");
        expected.add("1_[a, c, a, d]");
        expected.add("1_[a, c, a, d, a]");
        expected.add("1_[a, c, a, d, a, b]");
        expected.add("1_[a, c, a, d, a, b, r]");
        expected.add("1_[a, c, a, d, a, b, r, a]");
        expected.add("1_[c]");
        expected.add("1_[c, a]");
        expected.add("1_[c, a, d]");
        expected.add("1_[c, a, d, a]");
        expected.add("1_[c, a, d, a, b]");
        expected.add("1_[c, a, d, a, b, r]");
        expected.add("1_[c, a, d, a, b, r, a]");
        expected.add("1_[a, d]");
        expected.add("1_[a, d, a]");
        expected.add("1_[a, d, a, b]");
        expected.add("1_[a, d, a, b, r]");
        expected.add("1_[a, d, a, b, r, a]");
        expected.add("1_[d]");
        expected.add("1_[d, a]");
        expected.add("1_[d, a, b]");
        expected.add("1_[d, a, b, r]");
        expected.add("1_[d, a, b, r, a]");

        assertEquals(expected.size(), sequences.size());

        for (String sequence : sequences) {
            ListAssert.assertContains(expected, sequence);
        }
    }

    @Test
    public void testProcessWithTrieProcessor_9() throws Exception {
        Trie<String> fixture = new Trie<String>();
        fixture.train(sequence, 10);

        final List<String> sequences = new ArrayList<String>();
        TrieProcessor<String> processor = new TrieProcessor<String>() {
            @Override
            public TrieProcessor.Result process(List<String> sequence, int count) {
                sequences.add(count + "_" + sequence.toString());
                return TrieProcessor.Result.CONTINUE;
            }

        };

        fixture.process(processor);

        List<String> expected = new ArrayList<String>();

        expected.add("5_[a]");
        expected.add("2_[a, b]");
        expected.add("2_[a, b, r]");
        expected.add("2_[a, b, r, a]");
        expected.add("1_[a, b, r, a, c]");
        expected.add("1_[a, b, r, a, c, a]");
        expected.add("1_[a, b, r, a, c, a, d]");
        expected.add("1_[a, b, r, a, c, a, d, a]");
        expected.add("1_[a, b, r, a, c, a, d, a, b]");
        expected.add("1_[a, b, r, a, c, a, d, a, b, r]");
        expected.add("2_[b]");
        expected.add("2_[b, r]");
        expected.add("2_[b, r, a]");
        expected.add("1_[b, r, a, c]");
        expected.add("1_[b, r, a, c, a]");
        expected.add("1_[b, r, a, c, a, d]");
        expected.add("1_[b, r, a, c, a, d, a]");
        expected.add("1_[b, r, a, c, a, d, a, b]");
        expected.add("1_[b, r, a, c, a, d, a, b, r]");
        expected.add("1_[b, r, a, c, a, d, a, b, r, a]");
        expected.add("2_[r]");
        expected.add("2_[r, a]");
        expected.add("1_[r, a, c]");
        expected.add("1_[r, a, c, a]");
        expected.add("1_[r, a, c, a, d]");
        expected.add("1_[r, a, c, a, d, a]");
        expected.add("1_[r, a, c, a, d, a, b]");
        expected.add("1_[r, a, c, a, d, a, b, r]");
        expected.add("1_[r, a, c, a, d, a, b, r, a]");
        expected.add("1_[a, c]");
        expected.add("1_[a, c, a]");
        expected.add("1_[a, c, a, d]");
        expected.add("1_[a, c, a, d, a]");
        expected.add("1_[a, c, a, d, a, b]");
        expected.add("1_[a, c, a, d, a, b, r]");
        expected.add("1_[a, c, a, d, a, b, r, a]");
        expected.add("1_[c]");
        expected.add("1_[c, a]");
        expected.add("1_[c, a, d]");
        expected.add("1_[c, a, d, a]");
        expected.add("1_[c, a, d, a, b]");
        expected.add("1_[c, a, d, a, b, r]");
        expected.add("1_[c, a, d, a, b, r, a]");
        expected.add("1_[a, d]");
        expected.add("1_[a, d, a]");
        expected.add("1_[a, d, a, b]");
        expected.add("1_[a, d, a, b, r]");
        expected.add("1_[a, d, a, b, r, a]");
        expected.add("1_[d]");
        expected.add("1_[d, a]");
        expected.add("1_[d, a, b]");
        expected.add("1_[d, a, b, r]");
        expected.add("1_[d, a, b, r, a]");

        assertEquals(expected.size(), sequences.size());

        for (String sequence : sequences) {
            ListAssert.assertContains(expected, sequence);
        }
    }

    @Test
    public void testProcessWithTrieProcessor_10() throws Exception {
        Trie<String> fixture = new Trie<String>();
        fixture.train(sequence, 11);

        final List<String> sequences = new ArrayList<String>();
        TrieProcessor<String> processor = new TrieProcessor<String>() {
            @Override
            public TrieProcessor.Result process(List<String> sequence, int count) {
                sequences.add(count + "_" + sequence.toString());
                return TrieProcessor.Result.CONTINUE;
            }

        };

        fixture.process(processor);

        List<String> expected = new ArrayList<String>();

        expected.add("5_[a]");
        expected.add("2_[a, b]");
        expected.add("2_[a, b, r]");
        expected.add("2_[a, b, r, a]");
        expected.add("1_[a, b, r, a, c]");
        expected.add("1_[a, b, r, a, c, a]");
        expected.add("1_[a, b, r, a, c, a, d]");
        expected.add("1_[a, b, r, a, c, a, d, a]");
        expected.add("1_[a, b, r, a, c, a, d, a, b]");
        expected.add("1_[a, b, r, a, c, a, d, a, b, r]");
        expected.add("1_[a, b, r, a, c, a, d, a, b, r, a]");
        expected.add("2_[b]");
        expected.add("2_[b, r]");
        expected.add("2_[b, r, a]");
        expected.add("1_[b, r, a, c]");
        expected.add("1_[b, r, a, c, a]");
        expected.add("1_[b, r, a, c, a, d]");
        expected.add("1_[b, r, a, c, a, d, a]");
        expected.add("1_[b, r, a, c, a, d, a, b]");
        expected.add("1_[b, r, a, c, a, d, a, b, r]");
        expected.add("1_[b, r, a, c, a, d, a, b, r, a]");
        expected.add("2_[r]");
        expected.add("2_[r, a]");
        expected.add("1_[r, a, c]");
        expected.add("1_[r, a, c, a]");
        expected.add("1_[r, a, c, a, d]");
        expected.add("1_[r, a, c, a, d, a]");
        expected.add("1_[r, a, c, a, d, a, b]");
        expected.add("1_[r, a, c, a, d, a, b, r]");
        expected.add("1_[r, a, c, a, d, a, b, r, a]");
        expected.add("1_[a, c]");
        expected.add("1_[a, c, a]");
        expected.add("1_[a, c, a, d]");
        expected.add("1_[a, c, a, d, a]");
        expected.add("1_[a, c, a, d, a, b]");
        expected.add("1_[a, c, a, d, a, b, r]");
        expected.add("1_[a, c, a, d, a, b, r, a]");
        expected.add("1_[c]");
        expected.add("1_[c, a]");
        expected.add("1_[c, a, d]");
        expected.add("1_[c, a, d, a]");
        expected.add("1_[c, a, d, a, b]");
        expected.add("1_[c, a, d, a, b, r]");
        expected.add("1_[c, a, d, a, b, r, a]");
        expected.add("1_[a, d]");
        expected.add("1_[a, d, a]");
        expected.add("1_[a, d, a, b]");
        expected.add("1_[a, d, a, b, r]");
        expected.add("1_[a, d, a, b, r, a]");
        expected.add("1_[d]");
        expected.add("1_[d, a]");
        expected.add("1_[d, a, b]");
        expected.add("1_[d, a, b, r]");
        expected.add("1_[d, a, b, r, a]");

        assertEquals(expected.size(), sequences.size());

        for (String sequence : sequences) {
            ListAssert.assertContains(expected, sequence);
        }
    }

    @Test
    public void testGetSequencesWithMostOccurrences_1() throws Exception {
        Trie<String> fixture = new Trie<String>();
        fixture.train(sequence, 3);

        // get all sequences with a minimal length of one that occur most often
        Collection<List<String>> result = fixture.getSequencesWithOccurrenceCount(1, 0);

        assertEquals(1, result.size());

        List<String> expected = new ArrayList<String>();
        expected.add("a");

        ListAssert.assertEquals(expected, result.iterator().next());
    }

    @Test
    public void testGetSequencesWithMostOccurrences_2() throws Exception {
        Trie<String> fixture = new Trie<String>();
        fixture.train(sequence, 3);

        // get all sequences with a minimal length of one that occur exactly once
        Collection<List<String>> result = fixture.getSequencesWithOccurrenceCount(1, 1);

        assertEquals(11, result.size());

        List<String> expected = new ArrayList<String>();
        expected.add("r");
        expected.add("a");
        expected.add("c");
        // rac
        ListAssert.assertContains((List<List<String>>) result, expected);

        expected.clear();
        expected.add("a");
        expected.add("c");
        // ac
        ListAssert.assertContains((List<List<String>>) result, expected);

        expected.add("a");
        // aca
        ListAssert.assertContains((List<List<String>>) result, expected);

        expected.clear();
        expected.add("c");
        // c
        ListAssert.assertContains((List<List<String>>) result, expected);

        expected.add("a");
        // ca
        ListAssert.assertContains((List<List<String>>) result, expected);

        expected.add("d");
        // cad
        ListAssert.assertContains((List<List<String>>) result, expected);

        expected.clear();
        expected.add("a");
        expected.add("d");
        // ad
        ListAssert.assertContains((List<List<String>>) result, expected);

        expected.add("a");
        // ada
        ListAssert.assertContains((List<List<String>>) result, expected);

        expected.clear();
        expected.add("d");
        // d
        ListAssert.assertContains((List<List<String>>) result, expected);

        expected.add("a");
        // da
        ListAssert.assertContains((List<List<String>>) result, expected);

        expected.add("b");
        // dab
        ListAssert.assertContains((List<List<String>>) result, expected);
    }

    @Test
    public void testGetSequencesWithMostOccurrences_3() throws Exception {
        Trie<String> fixture = new Trie<String>();
        fixture.train(sequence, 3);

        // get all sequences with a minimal length of one that occur exactly twice
        Collection<List<String>> result = fixture.getSequencesWithOccurrenceCount(1, 2);

        assertEquals(7, result.size());

        List<String> expected = new ArrayList<String>();
        expected.add("a");
        expected.add("b");
        // ab
        ListAssert.assertContains((List<List<String>>) result, expected);

        expected.add("r");
        // abr
        ListAssert.assertContains((List<List<String>>) result, expected);

        expected.clear();
        expected.add("b");
        // b
        ListAssert.assertContains((List<List<String>>) result, expected);

        expected.add("r");
        // br
        ListAssert.assertContains((List<List<String>>) result, expected);

        expected.add("a");
        // bra
        ListAssert.assertContains((List<List<String>>) result, expected);

        expected.clear();
        expected.add("r");
        // r
        ListAssert.assertContains((List<List<String>>) result, expected);

        expected.add("a");
        // ra
        ListAssert.assertContains((List<List<String>>) result, expected);
    }

    @Test
    public void testGetSequencesWithMostOccurrences_4() throws Exception {
        Trie<String> fixture = new Trie<String>();
        fixture.train(sequence, 3);

        // get all sequences with a minimal length of one that occur exactly three times
        Collection<List<String>> result = fixture.getSequencesWithOccurrenceCount(1, 3);

        assertEquals(0, result.size());
    }

    @Test
    public void testGetSequencesWithMostOccurrences_5() throws Exception {
        Trie<String> fixture = new Trie<String>();
        fixture.train(sequence, 3);

        // get all sequences with a minimal length of one that occur exactly four times
        Collection<List<String>> result = fixture.getSequencesWithOccurrenceCount(1, 4);

        assertEquals(0, result.size());
    }

    @Test
    public void testGetSequencesWithMostOccurrences_6() throws Exception {
        Trie<String> fixture = new Trie<String>();
        fixture.train(sequence, 3);

        // get all sequences with a minimal length of one that occur exactly five times
        Collection<List<String>> result = fixture.getSequencesWithOccurrenceCount(1, 5);

        assertEquals(1, result.size());

        List<String> expected = new ArrayList<String>();
        expected.add("a");
        ListAssert.assertContains((List<List<String>>) result, expected);
    }

    @Test
    public void testGetSequencesWithMostOccurrences_7() throws Exception {
        Trie<String> fixture = new Trie<String>();
        fixture.train(sequence, 3);

        // get all sequences with a minimal length of two that occur most often
        Collection<List<String>> result = fixture.getSequencesWithOccurrenceCount(2, 0);

        assertEquals(5, result.size());

        List<String> expected = new ArrayList<String>();
        expected.add("a");
        expected.add("b");
        ListAssert.assertContains((List<List<String>>) result, expected);

        expected.add("r");
        ListAssert.assertContains((List<List<String>>) result, expected);

        expected.clear();
        expected.add("b");
        expected.add("r");
        ListAssert.assertContains((List<List<String>>) result, expected);

        expected.add("a");
        ListAssert.assertContains((List<List<String>>) result, expected);

        expected.clear();
        expected.add("r");
        expected.add("a");
        ListAssert.assertContains((List<List<String>>) result, expected);
    }

    @Test
    public void testGetSequencesWithMostOccurrences_8() throws Exception {
        Trie<String> fixture = new Trie<String>();
        fixture.train(sequence, 3);

        // get all sequences with a minimal length of two that occur exactly once
        Collection<List<String>> result = fixture.getSequencesWithOccurrenceCount(2, 1);

        assertEquals(9, result.size());

        List<String> expected = new ArrayList<String>();
        expected.add("r");
        expected.add("a");
        expected.add("c");
        // rac
        ListAssert.assertContains((List<List<String>>) result, expected);

        expected.clear();
        expected.add("a");
        expected.add("c");
        // ac
        ListAssert.assertContains((List<List<String>>) result, expected);

        expected.add("a");
        // aca
        ListAssert.assertContains((List<List<String>>) result, expected);

        expected.clear();
        expected.add("c");
        expected.add("a");
        // ca
        ListAssert.assertContains((List<List<String>>) result, expected);

        expected.add("d");
        // cad
        ListAssert.assertContains((List<List<String>>) result, expected);

        expected.clear();
        expected.add("a");
        expected.add("d");
        // ad
        ListAssert.assertContains((List<List<String>>) result, expected);

        expected.add("a");
        // ada
        ListAssert.assertContains((List<List<String>>) result, expected);

        expected.clear();
        expected.add("d");
        expected.add("a");
        // da
        ListAssert.assertContains((List<List<String>>) result, expected);

        expected.add("b");
        // dab
        ListAssert.assertContains((List<List<String>>) result, expected);
    }

    @Test
    public void testGetSequencesWithMostOccurrences_9() throws Exception {
        Trie<String> fixture = new Trie<String>();
        fixture.train(sequence, 3);

        // get all sequences with a minimal length of two that occur exactly twice
        Collection<List<String>> result = fixture.getSequencesWithOccurrenceCount(2, 2);

        assertEquals(5, result.size());

        List<String> expected = new ArrayList<String>();
        expected.add("a");
        expected.add("b");
        // ab
        ListAssert.assertContains((List<List<String>>) result, expected);

        expected.add("r");
        // abr
        ListAssert.assertContains((List<List<String>>) result, expected);

        expected.clear();
        expected.add("b");
        expected.add("r");
        // br
        ListAssert.assertContains((List<List<String>>) result, expected);

        expected.add("a");
        // bra
        ListAssert.assertContains((List<List<String>>) result, expected);

        expected.clear();
        expected.add("r");
        expected.add("a");
        // ra
        ListAssert.assertContains((List<List<String>>) result, expected);
    }

    @Test
    public void testGetSequencesWithMostOccurrences_10() throws Exception {
        Trie<String> fixture = new Trie<String>();
        fixture.train(sequence, 3);

        // get all sequences with a minimal length of two that occur exactly three times
        Collection<List<String>> result = fixture.getSequencesWithOccurrenceCount(2, 3);

        assertEquals(0, result.size());
    }

    @Test
    public void testGetSequencesWithMostOccurrences_11() throws Exception {
        Trie<String> fixture = new Trie<String>();
        fixture.train(sequence, 3);

        // get all sequences with a minimal length of three that occur most often
        Collection<List<String>> result = fixture.getSequencesWithOccurrenceCount(3, 0);

        assertEquals(2, result.size());

        List<String> expected = new ArrayList<String>();
        expected.add("a");
        expected.add("b");
        expected.add("r");
        ListAssert.assertContains((List<List<String>>) result, expected);

        expected.clear();
        expected.add("b");
        expected.add("r");
        expected.add("a");
        ListAssert.assertContains((List<List<String>>) result, expected);
    }

    @Test
    public void testGetSequencesWithMostOccurrences_12() throws Exception {
        Trie<String> fixture = new Trie<String>();
        fixture.train(sequence, 3);

        // get all sequences with a minimal length of three that occur exactly once
        Collection<List<String>> result = fixture.getSequencesWithOccurrenceCount(3, 1);

        assertEquals(5, result.size());

        List<String> expected = new ArrayList<String>();
        expected.add("r");
        expected.add("a");
        expected.add("c");
        // rac
        ListAssert.assertContains((List<List<String>>) result, expected);

        expected.clear();
        expected.add("a");
        expected.add("c");
        expected.add("a");
        // aca
        ListAssert.assertContains((List<List<String>>) result, expected);

        expected.clear();
        expected.add("c");
        expected.add("a");
        expected.add("d");
        // cad
        ListAssert.assertContains((List<List<String>>) result, expected);

        expected.clear();
        expected.add("a");
        expected.add("d");
        expected.add("a");
        // ada
        ListAssert.assertContains((List<List<String>>) result, expected);

        expected.clear();
        expected.add("d");
        expected.add("a");
        expected.add("b");
        // dab
        ListAssert.assertContains((List<List<String>>) result, expected);
    }

    @Test
    public void testGetSequencesWithMostOccurrences_13() throws Exception {
        Trie<String> fixture = new Trie<String>();
        fixture.train(sequence, 3);

        // get all sequences with a minimal length of four that occur most often
        Collection<List<String>> 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 {
        Trie<String> fixture = new Trie<String>();
        fixture.train(sequence, 3);

        // get all sequences with a minimal length of four that occur exactly once
        Collection<List<String>> 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 {
        Trie<String> fixture = new Trie<String>();
        fixture.train(sequence, 3);
        List<String> subSequence = new ArrayList<String>();
        subSequence.add("a");

        int result = fixture.getCount(subSequence);

        assertEquals(5, result);
    }

    @Test
    public void testGetCount_2() throws Exception {
        Trie<String> fixture = new Trie<String>();
        fixture.train(sequence, 3);
        List<String> subSequence = new ArrayList<String>();
        subSequence.add("a");
        subSequence.add("b");

        int result = fixture.getCount(subSequence);

        assertEquals(2, result);
    }

    @Test
    public void testGetCount_3() throws Exception {
        Trie<String> fixture = new Trie<String>();
        fixture.train(sequence, 3);
        List<String> subSequence = new ArrayList<String>();
        subSequence.add("x");

        int result = fixture.getCount(subSequence);

        assertEquals(0, result);
    }

    @Test
    public void testGetCount_4() throws Exception {
        Trie<String> fixture = new Trie<String>();
        fixture.train(sequence, 3);
        List<String> subSequence = new ArrayList<String>();

        int result = fixture.getCount(subSequence, "a");

        assertEquals(5, result);
    }

    @Test
    public void testGetCount_5() throws Exception {
        Trie<String> fixture = new Trie<String>();
        fixture.train(sequence, 3);
        List<String> subSequence = new ArrayList<String>();
        subSequence.add("a");
        subSequence.add("b");

        int result = fixture.getCount(subSequence, "r");

        assertEquals(2, result);
    }

    @Test
    public void testGetCount_6() throws Exception {
        Trie<String> fixture = new Trie<String>();
        fixture.train(sequence, 3);
        List<String> subSequence = new ArrayList<String>();

        int result = fixture.getCount(subSequence, "x");

        assertEquals(0, result);
    }

    @Test
    public void testGetFollowingSymbols_1() throws Exception {
        Trie<String> fixture = new Trie<String>();
        fixture.train(sequence, 3);
        List<String> subSequence = new ArrayList<String>();
        subSequence.add("a");
        Collection<String> expected = new ArrayList<String>();
        expected.add("b");
        expected.add("c");
        expected.add("d");

        Collection<String> result = fixture.getFollowingSymbols(subSequence);

        assertCollectionContent(expected, result);
    }

    @Test
    public void testGetFollowingSymbols_2() throws Exception {
        Trie<String> fixture = new Trie<String>();
        fixture.train(sequence, 3);
        List<String> subSequence = new ArrayList<String>();
        subSequence.add("a");
        subSequence.add("b");
        subSequence.add("r");

        Collection<String> result = fixture.getFollowingSymbols(subSequence);

        assertEquals(0, result.size());
    }

    @Test
    public void testGetFollowingSymbols_3() throws Exception {
        Trie<String> fixture = new Trie<String>();
        fixture.train(sequence, 3);
        List<String> subSequence = new ArrayList<String>();
        subSequence.add("x");

        Collection<String> result = fixture.getFollowingSymbols(subSequence);

        assertEquals(0, result.size());
    }

    @Test
    public void testGetNumLeafAncestors_1() throws Exception {
        Trie<String> fixture = new Trie<String>();
        fixture.train(sequence, 3);

        int result = fixture.getNumLeafAncestors();

        assertEquals(7, result);
    }

    @Test
    public void testGetNumLeafs_1() throws Exception {
        Trie<String> fixture = new Trie<String>();
        fixture.train(sequence, 3);

        int result = fixture.getNumLeafs();

        assertEquals(7, result);
    }

    @Test
    public void testGetNumSymbols_1() throws Exception {
        Trie<String> fixture = new Trie<String>();
        fixture.train(sequence, 3);

        int result = fixture.getNumSymbols();

        assertEquals(5, result);
    }

    @Test
    public void testTrain_1() throws Exception {
        Trie<String> fixture = new Trie<String>();
        int maxOrder = 3;

        fixture.train(sequence, maxOrder);

        // check if symbols are correct
        assertCollectionContent(symbols, fixture.getKnownSymbols());

        // check if counters are correct and only the correct nodes exist
        TrieNode<String> root = fixture.find(new ArrayList<String>());
        TrieNode<String> root_a = root.getChild("a");
        TrieNode<String> root_a_a = root_a.getChild("a");
        TrieNode<String> root_a_b = root_a.getChild("b");
        TrieNode<String> root_a_b_a = root_a_b.getChild("a");
        TrieNode<String> root_a_b_b = root_a_b.getChild("b");
        TrieNode<String> root_a_b_c = root_a_b.getChild("c");
        TrieNode<String> root_a_b_d = root_a_b.getChild("d");
        TrieNode<String> root_a_b_r = root_a_b.getChild("r");
        TrieNode<String> root_a_c = root_a.getChild("c");
        TrieNode<String> root_a_c_a = root_a_c.getChild("a");
        TrieNode<String> root_a_c_b = root_a_c.getChild("b");
        TrieNode<String> root_a_c_c = root_a_c.getChild("c");
        TrieNode<String> root_a_c_d = root_a_c.getChild("d");
        TrieNode<String> root_a_c_r = root_a_c.getChild("r");
        TrieNode<String> root_a_d = root_a.getChild("d");
        TrieNode<String> root_a_d_a = root_a_d.getChild("a");
        TrieNode<String> root_a_d_b = root_a_d.getChild("b");
        TrieNode<String> root_a_d_c = root_a_d.getChild("c");
        TrieNode<String> root_a_d_d = root_a_d.getChild("d");
        TrieNode<String> root_a_d_r = root_a_d.getChild("r");
        TrieNode<String> root_a_r = root_a.getChild("r");
        TrieNode<String> root_b = root.getChild("b");
        TrieNode<String> root_b_a = root_b.getChild("a");
        TrieNode<String> root_b_b = root_b.getChild("b");
        TrieNode<String> root_b_c = root_b.getChild("c");
        TrieNode<String> root_b_d = root_b.getChild("d");
        TrieNode<String> root_b_r = root_b.getChild("r");
        TrieNode<String> root_b_r_a = root_b_r.getChild("a");
        TrieNode<String> root_b_r_b = root_b_r.getChild("b");
        TrieNode<String> root_b_r_c = root_b_r.getChild("c");
        TrieNode<String> root_b_r_d = root_b_r.getChild("d");
        TrieNode<String> root_b_r_r = root_b_r.getChild("r");
        TrieNode<String> root_c = root.getChild("c");
        TrieNode<String> root_c_a = root_c.getChild("a");
        TrieNode<String> root_c_a_a = root_c_a.getChild("a");
        TrieNode<String> root_c_a_b = root_c_a.getChild("b");
        TrieNode<String> root_c_a_c = root_c_a.getChild("c");
        TrieNode<String> root_c_a_d = root_c_a.getChild("d");
        TrieNode<String> root_c_a_r = root_c_a.getChild("r");
        TrieNode<String> root_c_b = root_c.getChild("b");
        TrieNode<String> root_c_c = root_c.getChild("c");
        TrieNode<String> root_c_d = root_c.getChild("d");
        TrieNode<String> root_c_r = root_c.getChild("r");
        TrieNode<String> root_d = root.getChild("d");
        TrieNode<String> root_d_a = root_d.getChild("a");
        TrieNode<String> root_d_a_a = root_d_a.getChild("a");
        TrieNode<String> root_d_a_b = root_d_a.getChild("b");
        TrieNode<String> root_d_a_c = root_d_a.getChild("c");
        TrieNode<String> root_d_a_d = root_d_a.getChild("d");
        TrieNode<String> root_d_a_r = root_d_a.getChild("r");
        TrieNode<String> root_d_b = root_d.getChild("b");
        TrieNode<String> root_d_c = root_d.getChild("c");
        TrieNode<String> root_d_d = root_d.getChild("d");
        TrieNode<String> root_d_r = root_d.getChild("r");
        TrieNode<String> root_r = root.getChild("r");
        TrieNode<String> root_r_a = root_r.getChild("a");
        TrieNode<String> root_r_a_a = root_r_a.getChild("a");
        TrieNode<String> root_r_a_b = root_r_a.getChild("b");
        TrieNode<String> root_r_a_c = root_r_a.getChild("c");
        TrieNode<String> root_r_a_d = root_r_a.getChild("d");
        TrieNode<String> root_r_a_r = root_r_a.getChild("r");
        TrieNode<String> root_r_b = root_r.getChild("b");
        TrieNode<String> root_r_c = root_r.getChild("c");
        TrieNode<String> root_r_d = root_r.getChild("d");
        TrieNode<String> root_r_r = root_r.getChild("r");

        assertEquals(5, root_a.getCount());
        assertNull(root_a_a);
        assertEquals(2, root_a_b.getCount());
        assertNull(root_a_b_a);
        assertNull(root_a_b_b);
        assertNull(root_a_b_c);
        assertNull(root_a_b_d);
        assertEquals(2, root_a_b_r.getCount());
        assertEquals(1, root_a_c.getCount());
        assertEquals(1, root_a_c_a.getCount());
        assertNull(root_a_c_b);
        assertNull(root_a_c_c);
        assertNull(root_a_c_d);
        assertNull(root_a_c_r);
        assertEquals(1, root_a_d.getCount());
        assertEquals(1, root_a_d_a.getCount());
        assertNull(root_a_d_b);
        assertNull(root_a_d_c);
        assertNull(root_a_d_d);
        assertNull(root_a_d_r);
        assertNull(root_a_r);

        assertEquals(2, root_b.getCount());
        assertNull(root_b_a);
        assertNull(root_b_b);
        assertNull(root_b_c);
        assertNull(root_b_d);
        assertEquals(2, root_b_r.getCount());
        assertEquals(2, root_b_r_a.getCount());
        assertNull(root_b_r_b);
        assertNull(root_b_r_c);
        assertNull(root_b_r_d);
        assertNull(root_b_r_r);

        assertEquals(1, root_c.getCount());
        assertEquals(1, root_c_a.getCount());
        assertNull(root_c_a_a);
        assertNull(root_c_a_b);
        assertNull(root_c_a_c);
        assertEquals(1, root_c_a_d.getCount());
        assertNull(root_c_a_r);
        assertNull(root_c_b);
        assertNull(root_c_c);
        assertNull(root_c_d);
        assertNull(root_c_r);

        assertEquals(1, root_d.getCount());
        assertEquals(1, root_d_a.getCount());
        assertNull(root_d_a_a);
        assertEquals(1, root_d_a_b.getCount());
        assertNull(root_d_a_c);
        assertNull(root_d_a_d);
        assertNull(root_d_a_r);
        assertNull(root_d_b);
        assertNull(root_d_c);
        assertNull(root_d_d);
        assertNull(root_d_r);

        assertEquals(2, root_r.getCount());
        assertEquals(2, root_r_a.getCount());
        assertNull(root_r_a_a);
        assertNull(root_r_a_b);
        assertEquals(1, root_r_a_c.getCount());
        assertNull(root_r_a_d);
        assertNull(root_r_a_r);
        assertNull(root_r_b);
        assertNull(root_r_c);
        assertNull(root_r_d);
        assertNull(root_r_r);

        // check if leafs are really leafs
        assertTrue(root_a_b_r.isLeaf());
        assertTrue(root_a_c_a.isLeaf());
        assertTrue(root_a_d_a.isLeaf());
        assertTrue(root_b_r_a.isLeaf());
        assertTrue(root_c_a_d.isLeaf());
        assertTrue(root_d_a_b.isLeaf());
        assertTrue(root_r_a_c.isLeaf());
    }

    @Test
    public void testTrain_2() throws Exception {
        Trie<String> fixture = new Trie<String>();
        int maxOrder = 0;

        fixture.train(sequence, maxOrder);

        assertTrue(fixture.getKnownSymbols().isEmpty());
    }

    @Test
    public void testTrain_3() throws Exception {
        Trie<Object> fixture = new Trie<Object>();
        List<Object> sequence = new ArrayList<Object>();
        int maxOrder = 1;

        fixture.train(sequence, maxOrder);

        assertTrue(fixture.getKnownSymbols().isEmpty());
    }

    @Test
    public void testTrain_4() throws Exception {
        Trie<String> fixture = new Trie<String>();
        List<String> sequence = new ArrayList<String>();
        sequence.add("a");
        sequence.add("b");
        int maxOrder = 3;

        fixture.train(sequence, maxOrder);

        assertCollectionContent(sequence, fixture.getKnownSymbols());
        TrieNode<String> root = fixture.find(new ArrayList<String>());
        TrieNode<String> root_a = root.getChild("a");
        TrieNode<String> root_a_a = root_a.getChild("a");
        TrieNode<String> root_a_b = root_a.getChild("b");
        TrieNode<String> root_b = root.getChild("b");
        TrieNode<String> root_b_a = root_b.getChild("a");
        TrieNode<String> root_b_b = root_b.getChild("b");

        assertEquals(1, root_a.getCount());
        assertNull(root_a_a);
        assertEquals(1, root_a_b.getCount());
        assertEquals(1, root_b.getCount());
        assertNull(root_b_a);
        assertNull(root_b_b);

        assertTrue(root_a_b.isLeaf());
        assertTrue(root_b.isLeaf());
    }

    @Test
    public void testEdgeEdge_1() throws Exception {
        Edge result = new Edge();

        assertNotNull(result);
    }

    @Test
    public void testTrieVertexTrieVertex_1() throws Exception {
        String id = "idString";

        TrieVertex result = new TrieVertex(id);

        assertNotNull(result);
    }

    @Test
    public void testTrieVertexToString_1() throws Exception {
        String id = "idString";
        TrieVertex fixture = new TrieVertex(id);

        String result = fixture.toString();

        assertEquals(id, result);
    }

    @Test
    public void testEquals_1() throws Exception {
        Trie<String> trieOther = new Trie<String>();
        Trie<String> fixture = new Trie<String>();

        boolean result = fixture.equals(trieOther);

        assertEquals(true, result);
    }

    @Test
    public void testEquals_2() throws Exception {
        Trie<String> trieOther = new Trie<String>();
        trieOther.train(sequence, 2);
        Trie<String> fixture = new Trie<String>();
        fixture.train(sequence, 2);

        boolean result = fixture.equals(trieOther);

        assertEquals(true, result);
    }

    @Test
    public void testEquals_3() throws Exception {
        Trie<String> trieOther = new Trie<String>();
        trieOther.train(sequence, 2);
        Trie<String> fixture = new Trie<String>();
        fixture.train(sequence, 3);

        boolean result = fixture.equals(trieOther);

        assertEquals(false, result);
    }

    @Test
    public void testEquals_4() throws Exception {
        Trie<String> trieOther = new Trie<String>();
        Trie<String> fixture = new Trie<String>();
        fixture.train(sequence, 2);

        boolean result = fixture.equals(trieOther);

        assertEquals(false, result);
    }

    @Test
    public void testEquals_5() throws Exception {
        Trie<String> trieOther = new Trie<String>();
        trieOther.train(sequence, 2);
        Trie<String> fixture = new Trie<String>();

        boolean result = fixture.equals(trieOther);

        assertEquals(false, result);
    }

    @Test
    public void testEquals_6() throws Exception {
        Trie<String> fixture = new Trie<String>();
        fixture.train(sequence, 2);

        boolean result = fixture.equals(fixture);

        assertEquals(true, result);
    }

    @Test
    public void testEquals_7() throws Exception {
        Trie<String> fixture = new Trie<String>();
        fixture.train(sequence, 2);

        boolean result = fixture.equals(null);

        assertEquals(false, result);
    }

    @Test
    public void testLargeTrie_1() throws Exception {
        Trie<Integer> fixture = new Trie<Integer>();

        int order = 2;
        
        TrieTester tester = new TrieTester(3, 10, order);

        List<Integer> sequence = new ArrayList<Integer>(tester.sequence.length);
        
        for (Integer elem : tester.sequence) {
            sequence.add(elem);
        }
        
        fixture.train(sequence, order);
        
        fixture.process(tester);
        assertTrue(tester.counts.isEmpty());
    }

    @Test
    public void testLargeTrie_2() throws Exception {
        Trie<Integer> fixture = new Trie<Integer>();

        int order = 2;
        
        TrieTester tester = new TrieTester(300, 100000, order);

        List<Integer> sequence = new ArrayList<Integer>(tester.sequence.length);
        
        for (Integer elem : tester.sequence) {
            sequence.add(elem);
        }
        
        fixture.train(sequence, order);
        
        fixture.process(tester);
        assertTrue(tester.counts.isEmpty());
    }

    @Test
    public void testLargeTrie_3() throws Exception {
        Trie<Integer> fixture = new Trie<Integer>();

        int order = 2;
        
        TrieTester tester = new TrieTester(1000, 100000, order);

        List<Integer> sequence = new ArrayList<Integer>(tester.sequence.length);
        
        for (Integer elem : tester.sequence) {
            sequence.add(elem);
        }
        
        fixture.train(sequence, order);
        
        fixture.process(tester);
        assertTrue(tester.counts.isEmpty());
    }

    @Test
    public void testLargeTrie_4() throws Exception {
        Trie<Integer> fixture = new Trie<Integer>();

        int order = 3;
        
        TrieTester tester = new TrieTester(3, 50, order);

        List<Integer> sequence = new ArrayList<Integer>(tester.sequence.length);
        
        for (Integer elem : tester.sequence) {
            sequence.add(elem);
        }
        
        fixture.train(sequence, order);
        
        fixture.process(tester);
        assertTrue(tester.counts.isEmpty());
    }

    @Test
    public void testLargeTrie_5() throws Exception {
        Trie<Integer> fixture = new Trie<Integer>();

        int order = 3;
        
        TrieTester tester = new TrieTester(300, 100000, order);

        List<Integer> sequence = new ArrayList<Integer>(tester.sequence.length);
        
        for (Integer elem : tester.sequence) {
            sequence.add(elem);
        }
        
        fixture.train(sequence, order);
        
        fixture.process(tester);
        assertTrue(tester.counts.isEmpty());
    }

    @Test
    public void testLargeTrie_6() throws Exception {
        Trie<Integer> fixture = new Trie<Integer>();

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

        List<Integer> sequence = new ArrayList<Integer>(tester.sequence.length);
        
        for (Integer elem : tester.sequence) {
            sequence.add(elem);
        }
        
        fixture.train(sequence, order);
        
        fixture.process(tester);
        assertTrue(tester.counts.isEmpty());
    }

    @Test
    public void testLargeTrie_7() throws Exception {
        Trie<Integer> fixture = new Trie<Integer>();

        int order = 4;
        
        TrieTester tester = new TrieTester(3, 50, order);

        List<Integer> sequence = new ArrayList<Integer>(tester.sequence.length);
        
        for (Integer elem : tester.sequence) {
            sequence.add(elem);
        }
        
        fixture.train(sequence, order);
        
        fixture.process(tester);
        assertTrue(tester.counts.isEmpty());
    }

    @Test
    public void testLargeTrie_8() throws Exception {
        Trie<Integer> fixture = new Trie<Integer>();

        int order = 4;
        
        TrieTester tester = new TrieTester(300, 100000, order);

        List<Integer> sequence = new ArrayList<Integer>(tester.sequence.length);
        
        for (Integer elem : tester.sequence) {
            sequence.add(elem);
        }
        
        fixture.train(sequence, order);
        
        fixture.process(tester);
        assertTrue(tester.counts.isEmpty());
    }

    @Test
    public void testLargeTrie_9() throws Exception {
        Trie<Integer> fixture = new Trie<Integer>();

        int order = 4;
        
        TrieTester tester = new TrieTester(1000, 100000, order);

        List<Integer> sequence = new ArrayList<Integer>(tester.sequence.length);
        
        for (Integer elem : tester.sequence) {
            sequence.add(elem);
        }
        
        fixture.train(sequence, order);
        
        fixture.process(tester);
        assertTrue(tester.counts.isEmpty());
    }

    @Test
    public void testLargeTrie_10() throws Exception {
        Trie<Integer> fixture = new Trie<Integer>();

        int order = 5;
        
        TrieTester tester = new TrieTester(3, 50, order);

        List<Integer> sequence = new ArrayList<Integer>(tester.sequence.length);
        
        for (Integer elem : tester.sequence) {
            sequence.add(elem);
        }
        
        fixture.train(sequence, order);
        
        fixture.process(tester);
        assertTrue(tester.counts.isEmpty());
    }

    @Test
    public void testLargeTrie_11() throws Exception {
        Trie<Integer> fixture = new Trie<Integer>();

        int order = 5;
        
        TrieTester tester = new TrieTester(300, 100000, order);

        List<Integer> sequence = new ArrayList<Integer>(tester.sequence.length);
        
        for (Integer elem : tester.sequence) {
            sequence.add(elem);
        }
        
        fixture.train(sequence, order);
        
        fixture.process(tester);
        assertTrue(tester.counts.isEmpty());
    }

    @Test
    public void testLargeTrie_12() throws Exception {
        Trie<Integer> fixture = new Trie<Integer>();

        int order = 5;
        
        TrieTester tester = new TrieTester(1000, 100000, order);

        List<Integer> sequence = new ArrayList<Integer>(tester.sequence.length);
        
        for (Integer elem : tester.sequence) {
            sequence.add(elem);
        }
        
        fixture.train(sequence, order);
        
        fixture.process(tester);
        assertTrue(tester.counts.isEmpty());
    }

    @Test
    public void testLargeTrie_13() throws Exception {
        Trie<Integer> fixture = new Trie<Integer>();

        int order = 6;
        
        TrieTester tester = new TrieTester(3, 50, order);

        List<Integer> sequence = new ArrayList<Integer>(tester.sequence.length);
        
        for (Integer elem : tester.sequence) {
            sequence.add(elem);
        }
        
        fixture.train(sequence, order);
        
        fixture.process(tester);
        assertTrue(tester.counts.isEmpty());
    }

    @Test
    public void testLargeTrie_14() throws Exception {
        Trie<Integer> fixture = new Trie<Integer>();

        int order = 6;
        
        TrieTester tester = new TrieTester(300, 100000, order);

        List<Integer> sequence = new ArrayList<Integer>(tester.sequence.length);
        
        for (Integer elem : tester.sequence) {
            sequence.add(elem);
        }
        
        fixture.train(sequence, order);
        
        fixture.process(tester);
        assertTrue(tester.counts.isEmpty());
    }

    @Test
    public void testLargeTrie_15() throws Exception {
        Trie<Integer> fixture = new Trie<Integer>();

        int order = 6;
        
        TrieTester tester = new TrieTester(1000, 100000, order);

        List<Integer> sequence = new ArrayList<Integer>(tester.sequence.length);
        
        for (Integer elem : tester.sequence) {
            sequence.add(elem);
        }
        
        fixture.train(sequence, order);
        
        fixture.process(tester);
        assertTrue(tester.counts.isEmpty());
    }

    @Before
    public void setUp() throws Exception {
        sequence = new ArrayList<String>();
        sequence.add("a");
        sequence.add("b");
        sequence.add("r");
        sequence.add("a");
        sequence.add("c");
        sequence.add("a");
        sequence.add("d");
        sequence.add("a");
        sequence.add("b");
        sequence.add("r");
        sequence.add("a");

        symbols = new HashSet<String>();
        symbols.add("a");
        symbols.add("b");
        symbols.add("c");
        symbols.add("d");
        symbols.add("r");
    }

    public static void main(String[] args) {
        new org.junit.runner.JUnitCore().run(TrieTest.class);
    }

    /**
     * <p>
     * class internally used for testing large tries.
     * </p>
     * 
     * @author Patrick Harms
     */
    private static class TrieTester implements TrieProcessor<Integer> {
        
        /**
         * the symbols used for testing the trie
         */
        private int[] symbols;

        /**
         * the simulated sequence
         */
        private int[] sequence;

        /**
         * the trained order of the tested trie
         */
        private int maxOrder;
        
        /**
         * the expected counts of subsequences
         */
        private Map<Long, Integer> counts = new HashMap<Long, Integer>();

        /**
         * 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 TrieTester(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");
            }
            
            this.symbols = new int[noOfSymbols];
            
            for (int i = 0; i < noOfSymbols; i++) {
                this.symbols[i] = i;
             }
            
            this.maxOrder = maxOrder;
            
            this.sequence = new int[sequenceLength];

            for (int i = 0; i < sequenceLength; i++) {
                int symbolIndex = (int) (Math.random() * noOfSymbols);
                this.sequence[i] = this.symbols[symbolIndex];
                
                if ((i - maxOrder + 1) >= 0) {
                    storeCounts(this.sequence, i - maxOrder + 1, i);
                }
            }
            
            for (int i = sequenceLength - maxOrder + 1; i < sequenceLength; i++) {
                storeCounts(this.sequence, 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));
                this.counts.put(key, count + 1);
            }
        }

        /* (non-Javadoc)
         * @see de.ugoe.cs.autoquest.usageprofiles.TrieProcessor#process(java.util.List, int)
         */
        @Override
        public TrieProcessor.Result process(List<Integer> sequence, int count) {
            long key = 0;
            
            for (Integer symbol : sequence) {
                key = key << 10;
                key += 1 + symbol;
            }
            
            Integer expectedCount = this.counts.remove(key);
            assertNotNull(expectedCount);
            assertEquals(expectedCount.intValue(), count);
            
            assertTrue(sequence.size() <= this.maxOrder);
            
            return TrieProcessor.Result.CONTINUE;
        }

    }
}