Index: trunk/autoquest-core-usageprofiles-test/src/test/java/de/ugoe/cs/autoquest/usageprofiles/TrieTest.java
===================================================================
--- trunk/autoquest-core-usageprofiles-test/src/test/java/de/ugoe/cs/autoquest/usageprofiles/TrieTest.java	(revision 1252)
+++ trunk/autoquest-core-usageprofiles-test/src/test/java/de/ugoe/cs/autoquest/usageprofiles/TrieTest.java	(revision 1253)
@@ -17,6 +17,8 @@
 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;
@@ -1755,4 +1757,304 @@
     }
 
+    @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 {
@@ -1782,3 +2084,116 @@
     }
 
+    /**
+     * <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 + this.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;
+        }
+
+    }
 }