source: trunk/autoquest-core-usageprofiles-test/src/test/java/de/ugoe/cs/autoquest/usageprofiles/TrieTest.java @ 1253

Last change on this file since 1253 was 1253, checked in by pharms, 11 years ago
  • added a test for very large tries. First of all to see, if the trie works correctly with the new symbol map used internally, and also to see, how it scales with longer sequences and a large number of different symbols.
  • Property svn:mime-type set to text/plain
File size: 72.4 KB
Line 
1//   Copyright 2012 Georg-August-Universität Göttingen, Germany
2//
3//   Licensed under the Apache License, Version 2.0 (the "License");
4//   you may not use this file except in compliance with the License.
5//   You may obtain a copy of the License at
6//
7//       http://www.apache.org/licenses/LICENSE-2.0
8//
9//   Unless required by applicable law or agreed to in writing, software
10//   distributed under the License is distributed on an "AS IS" BASIS,
11//   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12//   See the License for the specific language governing permissions and
13//   limitations under the License.
14
15package de.ugoe.cs.autoquest.usageprofiles;
16
17import java.util.ArrayList;
18import java.util.Collection;
19import java.util.HashMap;
20import java.util.HashSet;
21import java.util.List;
22import java.util.Map;
23
24import junitx.framework.ListAssert;
25
26import org.junit.*;
27
28import de.ugoe.cs.autoquest.usageprofiles.Trie;
29import de.ugoe.cs.autoquest.usageprofiles.TrieNode;
30import de.ugoe.cs.autoquest.usageprofiles.Trie.Edge;
31import de.ugoe.cs.autoquest.usageprofiles.Trie.TrieVertex;
32import static org.junit.Assert.*;
33
34/**
35 * The class <code>TrieTest</code> contains tests for the class <code>{@link Trie}</code>.
36 *
37 * @author Steffen Herbold
38 * @version 1.0
39 */
40public class TrieTest {
41
42    List<String> sequence;
43    Collection<String> symbols;
44
45    private static void assertCollectionContent(Collection<?> c1, Collection<?> c2) {
46        assertEquals(c1.size(), c2.size());
47        for (Object obj : c1) {
48            assertTrue(c2.contains(obj));
49        }
50    }
51
52    @Test
53    public void testTrie_1() throws Exception {
54
55        Trie<String> result = new Trie<String>();
56
57        assertNotNull(result);
58        assertEquals(0, result.getNumLeafs());
59        assertEquals(0, result.getNumSymbols());
60        assertEquals(0, result.getNumLeafAncestors());
61        assertTrue(result.getKnownSymbols().isEmpty());
62    }
63
64    @Test
65    public void testTrie_2() throws Exception {
66        Trie<String> trie1 = new Trie<String>();
67        trie1.train(sequence, 3);
68
69        Trie<String> result = new Trie<String>(trie1);
70
71        assertEquals(trie1, result);
72        assertNotSame(trie1, result);
73    }
74
75    @Test(expected = java.lang.IllegalArgumentException.class)
76    public void testTrie_3() throws Exception {
77        new Trie<String>((SymbolComparator<String>) null);
78    }
79
80    @Test(expected = java.lang.IllegalArgumentException.class)
81    public void testTrie_4() throws Exception {
82        new Trie<String>((Trie<String>) null);
83    }
84
85    @Test
86    public void testAdd_1() throws Exception {
87        Trie<String> fixture = new Trie<String>();
88        List<String> seq = new ArrayList<String>();
89        seq.add("a");
90        seq.add("b");
91
92        fixture.add(seq);
93
94        assertEquals(1, fixture.getChild("a").getCount());
95        assertEquals(1, fixture.getChild("a").getChild("b").getCount());
96        assertNull(fixture.getChild("b"));
97    }
98
99    @Test
100    public void testAdd_2() throws Exception {
101        Trie<String> fixture = new Trie<String>();
102
103        fixture.add(new ArrayList<String>());
104
105        assertEquals(0, fixture.getNumSymbols());
106    }
107
108    @Test
109    public void testAdd_3() throws Exception {
110        Trie<String> fixture = new Trie<String>();
111
112        fixture.add(null);
113
114        assertEquals(0, fixture.getNumSymbols());
115    }
116
117    @Test
118    public void testFind_1() throws Exception {
119        Trie<String> fixture = new Trie<String>();
120        fixture.train(sequence, 3);
121        List<String> findSequence = new ArrayList<String>();
122        findSequence.add("a");
123        findSequence.add("b");
124        findSequence.add("r");
125        TrieNode<String> expected = fixture.getChild("a").getChild("b").getChild("r");
126
127        TrieNode<String> result = fixture.find(findSequence);
128
129        assertEquals(expected, result);
130    }
131
132    @Test
133    public void testFind_2() throws Exception {
134        Trie<String> fixture = new Trie<String>();
135        fixture.train(sequence, 3);
136        List<String> findSequence = new ArrayList<String>();
137        findSequence.add("c");
138        findSequence.add("a");
139        TrieNode<String> expected = fixture.getChild("c").getChild("a");
140
141        TrieNode<String> result = fixture.find(findSequence);
142
143        assertEquals(expected, result);
144    }
145
146    @Test
147    public void testFind_3() throws Exception {
148        Trie<String> fixture = new Trie<String>();
149        fixture.train(sequence, 3);
150        List<String> findSequence = new ArrayList<String>();
151
152        TrieNode<String> result = fixture.find(findSequence);
153
154        assertTrue(result.isRoot());
155    }
156
157    @Test
158    public void testFind_4() throws Exception {
159        Trie<String> fixture = new Trie<String>();
160        fixture.train(sequence, 3);
161
162        TrieNode<String> result = fixture.find(null);
163
164        assertTrue(result.isRoot());
165    }
166
167    @Test
168    public void testGetChildCreate_1() throws Exception {
169        Trie<String> fixture = new Trie<String>();
170        String symbol = "a";
171
172        TrieNode<String> result = fixture.getChildCreate(symbol);
173
174        assertEquals(symbol, result.getSymbol());
175        assertEquals(0, result.getCount());
176        assertTrue(result.isLeaf());
177    }
178
179    @Test(expected = java.lang.IllegalArgumentException.class)
180    public void testGetChildCreate_2() throws Exception {
181        Trie<String> fixture = new Trie<String>();
182        fixture.getChildCreate(null);
183    }
184
185    @Test
186    public void testGetContextSuffix_1() throws Exception {
187        Trie<String> fixture = new Trie<String>();
188        fixture.train(sequence, 3);
189        List<String> context = new ArrayList<String>();
190        context.add("a");
191        context.add("a");
192        context.add("b");
193        List<String> expected = new ArrayList<String>();
194        expected.add("a");
195        expected.add("b");
196
197        List<String> result = fixture.getContextSuffix(context);
198
199        ListAssert.assertEquals(expected, result);
200    }
201
202    @Test
203    public void testGetContextSuffix_2() throws Exception {
204        Trie<String> fixture = new Trie<String>();
205        fixture.train(sequence, 3);
206        List<String> context = new ArrayList<String>();
207        context.add("a");
208        context.add("a");
209        context.add("b");
210        context.add("r");
211        List<String> expected = new ArrayList<String>();
212        expected.add("b");
213        expected.add("r");
214
215        List<String> result = fixture.getContextSuffix(context);
216
217        ListAssert.assertEquals(expected, result);
218    }
219
220    @Test
221    public void testGetContextSuffix_3() throws Exception {
222        Trie<String> fixture = new Trie<String>();
223        fixture.train(sequence, 3);
224        List<String> context = new ArrayList<String>();
225        context.add("a");
226        context.add("a");
227        context.add("b");
228        context.add("x");
229        List<String> expected = new ArrayList<String>();
230
231        List<String> result = fixture.getContextSuffix(context);
232
233        ListAssert.assertEquals(expected, result);
234    }
235
236    @Test
237    public void testGetContextSuffix_4() throws Exception {
238        Trie<String> fixture = new Trie<String>();
239
240        List<String> result = fixture.getContextSuffix(null);
241
242        // add additional test code here
243        assertNotNull(result);
244        assertEquals(0, result.size());
245    }
246
247    @Test
248    public void testGetContextSuffix_5() throws Exception {
249        Trie<String> fixture = new Trie<String>();
250        fixture.train(sequence, 3);
251        List<String> context = new ArrayList<String>();
252        context.add("a");
253        context.add("a");
254        context.add("b");
255        List<String> expected = new ArrayList<String>();
256        expected.add("a");
257        expected.add("b");
258
259        List<String> result = fixture.getContextSuffix(context);
260
261        ListAssert.assertEquals(expected, result);
262    }
263
264    @Test
265    public void testProcessWithTrieProcessor_1() throws Exception {
266        Trie<String> fixture = new Trie<String>();
267        fixture.train(sequence, 2);
268
269        final List<String> sequences = new ArrayList<String>();
270        TrieProcessor<String> processor = new TrieProcessor<String>() {
271            @Override
272            public TrieProcessor.Result process(List<String> sequence, int count) {
273                sequences.add(count + "_" + sequence.toString());
274                return TrieProcessor.Result.CONTINUE;
275            }
276
277        };
278
279        fixture.process(processor);
280
281        List<String> expected = new ArrayList<String>();
282
283        expected.add("5_[a]");
284        expected.add("2_[a, b]");
285        expected.add("2_[b]");
286        expected.add("2_[b, r]");
287        expected.add("2_[r]");
288        expected.add("2_[r, a]");
289        expected.add("1_[a, c]");
290        expected.add("1_[c]");
291        expected.add("1_[c, a]");
292        expected.add("1_[a, d]");
293        expected.add("1_[d]");
294        expected.add("1_[d, a]");
295
296        assertEquals(expected.size(), sequences.size());
297
298        for (String sequence : sequences) {
299            ListAssert.assertContains(expected, sequence);
300        }
301    }
302
303    @Test
304    public void testProcessWithTrieProcessor_2() throws Exception {
305        Trie<String> fixture = new Trie<String>();
306        fixture.train(sequence, 3);
307
308        final List<String> sequences = new ArrayList<String>();
309        TrieProcessor<String> processor = new TrieProcessor<String>() {
310            @Override
311            public TrieProcessor.Result process(List<String> sequence, int count) {
312                sequences.add(count + "_" + sequence.toString());
313                return TrieProcessor.Result.CONTINUE;
314            }
315
316        };
317
318        fixture.process(processor);
319
320        List<String> expected = new ArrayList<String>();
321
322        expected.add("5_[a]");
323        expected.add("2_[a, b]");
324        expected.add("2_[a, b, r]");
325        expected.add("2_[b]");
326        expected.add("2_[b, r]");
327        expected.add("2_[b, r, a]");
328        expected.add("2_[r]");
329        expected.add("2_[r, a]");
330        expected.add("1_[r, a, c]");
331        expected.add("1_[a, c]");
332        expected.add("1_[a, c, a]");
333        expected.add("1_[c]");
334        expected.add("1_[c, a]");
335        expected.add("1_[c, a, d]");
336        expected.add("1_[a, d]");
337        expected.add("1_[a, d, a]");
338        expected.add("1_[d]");
339        expected.add("1_[d, a]");
340        expected.add("1_[d, a, b]");
341
342        assertEquals(expected.size(), sequences.size());
343
344        for (String sequence : sequences) {
345            ListAssert.assertContains(expected, sequence);
346        }
347    }
348
349    @Test
350    public void testProcessWithTrieProcessor_3() throws Exception {
351        Trie<String> fixture = new Trie<String>();
352        fixture.train(sequence, 4);
353
354        final List<String> sequences = new ArrayList<String>();
355        TrieProcessor<String> processor = new TrieProcessor<String>() {
356            @Override
357            public TrieProcessor.Result process(List<String> sequence, int count) {
358                sequences.add(count + "_" + sequence.toString());
359                return TrieProcessor.Result.CONTINUE;
360            }
361
362        };
363
364        fixture.process(processor);
365
366        List<String> expected = new ArrayList<String>();
367
368        expected.add("5_[a]");
369        expected.add("2_[a, b]");
370        expected.add("2_[a, b, r]");
371        expected.add("2_[a, b, r, a]");
372        expected.add("2_[b]");
373        expected.add("2_[b, r]");
374        expected.add("2_[b, r, a]");
375        expected.add("1_[b, r, a, c]");
376        expected.add("2_[r]");
377        expected.add("2_[r, a]");
378        expected.add("1_[r, a, c]");
379        expected.add("1_[r, a, c, a]");
380        expected.add("1_[a, c]");
381        expected.add("1_[a, c, a]");
382        expected.add("1_[a, c, a, d]");
383        expected.add("1_[c]");
384        expected.add("1_[c, a]");
385        expected.add("1_[c, a, d]");
386        expected.add("1_[c, a, d, a]");
387        expected.add("1_[a, d]");
388        expected.add("1_[a, d, a]");
389        expected.add("1_[a, d, a, b]");
390        expected.add("1_[d]");
391        expected.add("1_[d, a]");
392        expected.add("1_[d, a, b]");
393        expected.add("1_[d, a, b, r]");
394
395        assertEquals(expected.size(), sequences.size());
396
397        for (String sequence : sequences) {
398            ListAssert.assertContains(expected, sequence);
399        }
400    }
401
402    @Test
403    public void testProcessWithTrieProcessor_4() throws Exception {
404        Trie<String> fixture = new Trie<String>();
405        fixture.train(sequence, 5);
406
407        final List<String> sequences = new ArrayList<String>();
408        TrieProcessor<String> processor = new TrieProcessor<String>() {
409            @Override
410            public TrieProcessor.Result process(List<String> sequence, int count) {
411                sequences.add(count + "_" + sequence.toString());
412                return TrieProcessor.Result.CONTINUE;
413            }
414
415        };
416
417        fixture.process(processor);
418
419        List<String> expected = new ArrayList<String>();
420
421        expected.add("5_[a]");
422        expected.add("2_[a, b]");
423        expected.add("2_[a, b, r]");
424        expected.add("2_[a, b, r, a]");
425        expected.add("1_[a, b, r, a, c]");
426        expected.add("2_[b]");
427        expected.add("2_[b, r]");
428        expected.add("2_[b, r, a]");
429        expected.add("1_[b, r, a, c]");
430        expected.add("1_[b, r, a, c, a]");
431        expected.add("2_[r]");
432        expected.add("2_[r, a]");
433        expected.add("1_[r, a, c]");
434        expected.add("1_[r, a, c, a]");
435        expected.add("1_[r, a, c, a, d]");
436        expected.add("1_[a, c]");
437        expected.add("1_[a, c, a]");
438        expected.add("1_[a, c, a, d]");
439        expected.add("1_[a, c, a, d, a]");
440        expected.add("1_[c]");
441        expected.add("1_[c, a]");
442        expected.add("1_[c, a, d]");
443        expected.add("1_[c, a, d, a]");
444        expected.add("1_[c, a, d, a, b]");
445        expected.add("1_[a, d]");
446        expected.add("1_[a, d, a]");
447        expected.add("1_[a, d, a, b]");
448        expected.add("1_[a, d, a, b, r]");
449        expected.add("1_[d]");
450        expected.add("1_[d, a]");
451        expected.add("1_[d, a, b]");
452        expected.add("1_[d, a, b, r]");
453        expected.add("1_[d, a, b, r, a]");
454
455        assertEquals(expected.size(), sequences.size());
456
457        for (String sequence : sequences) {
458            ListAssert.assertContains(expected, sequence);
459        }
460    }
461
462    @Test
463    public void testProcessWithTrieProcessor_5() throws Exception {
464        Trie<String> fixture = new Trie<String>();
465        fixture.train(sequence, 6);
466
467        final List<String> sequences = new ArrayList<String>();
468        TrieProcessor<String> processor = new TrieProcessor<String>() {
469            @Override
470            public TrieProcessor.Result process(List<String> sequence, int count) {
471                sequences.add(count + "_" + sequence.toString());
472                return TrieProcessor.Result.CONTINUE;
473            }
474
475        };
476
477        fixture.process(processor);
478
479        List<String> expected = new ArrayList<String>();
480
481        expected.add("5_[a]");
482        expected.add("2_[a, b]");
483        expected.add("2_[a, b, r]");
484        expected.add("2_[a, b, r, a]");
485        expected.add("1_[a, b, r, a, c]");
486        expected.add("1_[a, b, r, a, c, a]");
487        expected.add("2_[b]");
488        expected.add("2_[b, r]");
489        expected.add("2_[b, r, a]");
490        expected.add("1_[b, r, a, c]");
491        expected.add("1_[b, r, a, c, a]");
492        expected.add("1_[b, r, a, c, a, d]");
493        expected.add("2_[r]");
494        expected.add("2_[r, a]");
495        expected.add("1_[r, a, c]");
496        expected.add("1_[r, a, c, a]");
497        expected.add("1_[r, a, c, a, d]");
498        expected.add("1_[r, a, c, a, d, a]");
499        expected.add("1_[a, c]");
500        expected.add("1_[a, c, a]");
501        expected.add("1_[a, c, a, d]");
502        expected.add("1_[a, c, a, d, a]");
503        expected.add("1_[a, c, a, d, a, b]");
504        expected.add("1_[c]");
505        expected.add("1_[c, a]");
506        expected.add("1_[c, a, d]");
507        expected.add("1_[c, a, d, a]");
508        expected.add("1_[c, a, d, a, b]");
509        expected.add("1_[c, a, d, a, b, r]");
510        expected.add("1_[a, d]");
511        expected.add("1_[a, d, a]");
512        expected.add("1_[a, d, a, b]");
513        expected.add("1_[a, d, a, b, r]");
514        expected.add("1_[a, d, a, b, r, a]");
515        expected.add("1_[d]");
516        expected.add("1_[d, a]");
517        expected.add("1_[d, a, b]");
518        expected.add("1_[d, a, b, r]");
519        expected.add("1_[d, a, b, r, a]");
520
521        assertEquals(expected.size(), sequences.size());
522
523        for (String sequence : sequences) {
524            ListAssert.assertContains(expected, sequence);
525        }
526    }
527
528    @Test
529    public void testProcessWithTrieProcessor_6() throws Exception {
530        Trie<String> fixture = new Trie<String>();
531        fixture.train(sequence, 7);
532
533        final List<String> sequences = new ArrayList<String>();
534        TrieProcessor<String> processor = new TrieProcessor<String>() {
535            @Override
536            public TrieProcessor.Result process(List<String> sequence, int count) {
537                sequences.add(count + "_" + sequence.toString());
538                return TrieProcessor.Result.CONTINUE;
539            }
540
541        };
542
543        fixture.process(processor);
544
545        List<String> expected = new ArrayList<String>();
546
547        expected.add("5_[a]");
548        expected.add("2_[a, b]");
549        expected.add("2_[a, b, r]");
550        expected.add("2_[a, b, r, a]");
551        expected.add("1_[a, b, r, a, c]");
552        expected.add("1_[a, b, r, a, c, a]");
553        expected.add("1_[a, b, r, a, c, a, d]");
554        expected.add("2_[b]");
555        expected.add("2_[b, r]");
556        expected.add("2_[b, r, a]");
557        expected.add("1_[b, r, a, c]");
558        expected.add("1_[b, r, a, c, a]");
559        expected.add("1_[b, r, a, c, a, d]");
560        expected.add("1_[b, r, a, c, a, d, a]");
561        expected.add("2_[r]");
562        expected.add("2_[r, a]");
563        expected.add("1_[r, a, c]");
564        expected.add("1_[r, a, c, a]");
565        expected.add("1_[r, a, c, a, d]");
566        expected.add("1_[r, a, c, a, d, a]");
567        expected.add("1_[r, a, c, a, d, a, b]");
568        expected.add("1_[a, c]");
569        expected.add("1_[a, c, a]");
570        expected.add("1_[a, c, a, d]");
571        expected.add("1_[a, c, a, d, a]");
572        expected.add("1_[a, c, a, d, a, b]");
573        expected.add("1_[a, c, a, d, a, b, r]");
574        expected.add("1_[c]");
575        expected.add("1_[c, a]");
576        expected.add("1_[c, a, d]");
577        expected.add("1_[c, a, d, a]");
578        expected.add("1_[c, a, d, a, b]");
579        expected.add("1_[c, a, d, a, b, r]");
580        expected.add("1_[c, a, d, a, b, r, a]");
581        expected.add("1_[a, d]");
582        expected.add("1_[a, d, a]");
583        expected.add("1_[a, d, a, b]");
584        expected.add("1_[a, d, a, b, r]");
585        expected.add("1_[a, d, a, b, r, a]");
586        expected.add("1_[d]");
587        expected.add("1_[d, a]");
588        expected.add("1_[d, a, b]");
589        expected.add("1_[d, a, b, r]");
590        expected.add("1_[d, a, b, r, a]");
591
592        assertEquals(expected.size(), sequences.size());
593
594        for (String sequence : sequences) {
595            ListAssert.assertContains(expected, sequence);
596        }
597    }
598
599    @Test
600    public void testProcessWithTrieProcessor_7() throws Exception {
601        Trie<String> fixture = new Trie<String>();
602        fixture.train(sequence, 8);
603
604        final List<String> sequences = new ArrayList<String>();
605        TrieProcessor<String> processor = new TrieProcessor<String>() {
606            @Override
607            public TrieProcessor.Result process(List<String> sequence, int count) {
608                sequences.add(count + "_" + sequence.toString());
609                return TrieProcessor.Result.CONTINUE;
610            }
611
612        };
613
614        fixture.process(processor);
615
616        List<String> expected = new ArrayList<String>();
617
618        expected.add("5_[a]");
619        expected.add("2_[a, b]");
620        expected.add("2_[a, b, r]");
621        expected.add("2_[a, b, r, a]");
622        expected.add("1_[a, b, r, a, c]");
623        expected.add("1_[a, b, r, a, c, a]");
624        expected.add("1_[a, b, r, a, c, a, d]");
625        expected.add("1_[a, b, r, a, c, a, d, a]");
626        expected.add("2_[b]");
627        expected.add("2_[b, r]");
628        expected.add("2_[b, r, a]");
629        expected.add("1_[b, r, a, c]");
630        expected.add("1_[b, r, a, c, a]");
631        expected.add("1_[b, r, a, c, a, d]");
632        expected.add("1_[b, r, a, c, a, d, a]");
633        expected.add("1_[b, r, a, c, a, d, a, b]");
634        expected.add("2_[r]");
635        expected.add("2_[r, a]");
636        expected.add("1_[r, a, c]");
637        expected.add("1_[r, a, c, a]");
638        expected.add("1_[r, a, c, a, d]");
639        expected.add("1_[r, a, c, a, d, a]");
640        expected.add("1_[r, a, c, a, d, a, b]");
641        expected.add("1_[r, a, c, a, d, a, b, r]");
642        expected.add("1_[a, c]");
643        expected.add("1_[a, c, a]");
644        expected.add("1_[a, c, a, d]");
645        expected.add("1_[a, c, a, d, a]");
646        expected.add("1_[a, c, a, d, a, b]");
647        expected.add("1_[a, c, a, d, a, b, r]");
648        expected.add("1_[a, c, a, d, a, b, r, a]");
649        expected.add("1_[c]");
650        expected.add("1_[c, a]");
651        expected.add("1_[c, a, d]");
652        expected.add("1_[c, a, d, a]");
653        expected.add("1_[c, a, d, a, b]");
654        expected.add("1_[c, a, d, a, b, r]");
655        expected.add("1_[c, a, d, a, b, r, a]");
656        expected.add("1_[a, d]");
657        expected.add("1_[a, d, a]");
658        expected.add("1_[a, d, a, b]");
659        expected.add("1_[a, d, a, b, r]");
660        expected.add("1_[a, d, a, b, r, a]");
661        expected.add("1_[d]");
662        expected.add("1_[d, a]");
663        expected.add("1_[d, a, b]");
664        expected.add("1_[d, a, b, r]");
665        expected.add("1_[d, a, b, r, a]");
666
667        assertEquals(expected.size(), sequences.size());
668
669        for (String sequence : sequences) {
670            ListAssert.assertContains(expected, sequence);
671        }
672    }
673
674    @Test
675    public void testProcessWithTrieProcessor_8() throws Exception {
676        Trie<String> fixture = new Trie<String>();
677        fixture.train(sequence, 9);
678
679        final List<String> sequences = new ArrayList<String>();
680        TrieProcessor<String> processor = new TrieProcessor<String>() {
681            @Override
682            public TrieProcessor.Result process(List<String> sequence, int count) {
683                sequences.add(count + "_" + sequence.toString());
684                return TrieProcessor.Result.CONTINUE;
685            }
686
687        };
688
689        fixture.process(processor);
690
691        List<String> expected = new ArrayList<String>();
692
693        expected.add("5_[a]");
694        expected.add("2_[a, b]");
695        expected.add("2_[a, b, r]");
696        expected.add("2_[a, b, r, a]");
697        expected.add("1_[a, b, r, a, c]");
698        expected.add("1_[a, b, r, a, c, a]");
699        expected.add("1_[a, b, r, a, c, a, d]");
700        expected.add("1_[a, b, r, a, c, a, d, a]");
701        expected.add("1_[a, b, r, a, c, a, d, a, b]");
702        expected.add("2_[b]");
703        expected.add("2_[b, r]");
704        expected.add("2_[b, r, a]");
705        expected.add("1_[b, r, a, c]");
706        expected.add("1_[b, r, a, c, a]");
707        expected.add("1_[b, r, a, c, a, d]");
708        expected.add("1_[b, r, a, c, a, d, a]");
709        expected.add("1_[b, r, a, c, a, d, a, b]");
710        expected.add("1_[b, r, a, c, a, d, a, b, r]");
711        expected.add("2_[r]");
712        expected.add("2_[r, a]");
713        expected.add("1_[r, a, c]");
714        expected.add("1_[r, a, c, a]");
715        expected.add("1_[r, a, c, a, d]");
716        expected.add("1_[r, a, c, a, d, a]");
717        expected.add("1_[r, a, c, a, d, a, b]");
718        expected.add("1_[r, a, c, a, d, a, b, r]");
719        expected.add("1_[r, a, c, a, d, a, b, r, a]");
720        expected.add("1_[a, c]");
721        expected.add("1_[a, c, a]");
722        expected.add("1_[a, c, a, d]");
723        expected.add("1_[a, c, a, d, a]");
724        expected.add("1_[a, c, a, d, a, b]");
725        expected.add("1_[a, c, a, d, a, b, r]");
726        expected.add("1_[a, c, a, d, a, b, r, a]");
727        expected.add("1_[c]");
728        expected.add("1_[c, a]");
729        expected.add("1_[c, a, d]");
730        expected.add("1_[c, a, d, a]");
731        expected.add("1_[c, a, d, a, b]");
732        expected.add("1_[c, a, d, a, b, r]");
733        expected.add("1_[c, a, d, a, b, r, a]");
734        expected.add("1_[a, d]");
735        expected.add("1_[a, d, a]");
736        expected.add("1_[a, d, a, b]");
737        expected.add("1_[a, d, a, b, r]");
738        expected.add("1_[a, d, a, b, r, a]");
739        expected.add("1_[d]");
740        expected.add("1_[d, a]");
741        expected.add("1_[d, a, b]");
742        expected.add("1_[d, a, b, r]");
743        expected.add("1_[d, a, b, r, a]");
744
745        assertEquals(expected.size(), sequences.size());
746
747        for (String sequence : sequences) {
748            ListAssert.assertContains(expected, sequence);
749        }
750    }
751
752    @Test
753    public void testProcessWithTrieProcessor_9() throws Exception {
754        Trie<String> fixture = new Trie<String>();
755        fixture.train(sequence, 10);
756
757        final List<String> sequences = new ArrayList<String>();
758        TrieProcessor<String> processor = new TrieProcessor<String>() {
759            @Override
760            public TrieProcessor.Result process(List<String> sequence, int count) {
761                sequences.add(count + "_" + sequence.toString());
762                return TrieProcessor.Result.CONTINUE;
763            }
764
765        };
766
767        fixture.process(processor);
768
769        List<String> expected = new ArrayList<String>();
770
771        expected.add("5_[a]");
772        expected.add("2_[a, b]");
773        expected.add("2_[a, b, r]");
774        expected.add("2_[a, b, r, a]");
775        expected.add("1_[a, b, r, a, c]");
776        expected.add("1_[a, b, r, a, c, a]");
777        expected.add("1_[a, b, r, a, c, a, d]");
778        expected.add("1_[a, b, r, a, c, a, d, a]");
779        expected.add("1_[a, b, r, a, c, a, d, a, b]");
780        expected.add("1_[a, b, r, a, c, a, d, a, b, r]");
781        expected.add("2_[b]");
782        expected.add("2_[b, r]");
783        expected.add("2_[b, r, a]");
784        expected.add("1_[b, r, a, c]");
785        expected.add("1_[b, r, a, c, a]");
786        expected.add("1_[b, r, a, c, a, d]");
787        expected.add("1_[b, r, a, c, a, d, a]");
788        expected.add("1_[b, r, a, c, a, d, a, b]");
789        expected.add("1_[b, r, a, c, a, d, a, b, r]");
790        expected.add("1_[b, r, a, c, a, d, a, b, r, a]");
791        expected.add("2_[r]");
792        expected.add("2_[r, a]");
793        expected.add("1_[r, a, c]");
794        expected.add("1_[r, a, c, a]");
795        expected.add("1_[r, a, c, a, d]");
796        expected.add("1_[r, a, c, a, d, a]");
797        expected.add("1_[r, a, c, a, d, a, b]");
798        expected.add("1_[r, a, c, a, d, a, b, r]");
799        expected.add("1_[r, a, c, a, d, a, b, r, a]");
800        expected.add("1_[a, c]");
801        expected.add("1_[a, c, a]");
802        expected.add("1_[a, c, a, d]");
803        expected.add("1_[a, c, a, d, a]");
804        expected.add("1_[a, c, a, d, a, b]");
805        expected.add("1_[a, c, a, d, a, b, r]");
806        expected.add("1_[a, c, a, d, a, b, r, a]");
807        expected.add("1_[c]");
808        expected.add("1_[c, a]");
809        expected.add("1_[c, a, d]");
810        expected.add("1_[c, a, d, a]");
811        expected.add("1_[c, a, d, a, b]");
812        expected.add("1_[c, a, d, a, b, r]");
813        expected.add("1_[c, a, d, a, b, r, a]");
814        expected.add("1_[a, d]");
815        expected.add("1_[a, d, a]");
816        expected.add("1_[a, d, a, b]");
817        expected.add("1_[a, d, a, b, r]");
818        expected.add("1_[a, d, a, b, r, a]");
819        expected.add("1_[d]");
820        expected.add("1_[d, a]");
821        expected.add("1_[d, a, b]");
822        expected.add("1_[d, a, b, r]");
823        expected.add("1_[d, a, b, r, a]");
824
825        assertEquals(expected.size(), sequences.size());
826
827        for (String sequence : sequences) {
828            ListAssert.assertContains(expected, sequence);
829        }
830    }
831
832    @Test
833    public void testProcessWithTrieProcessor_10() throws Exception {
834        Trie<String> fixture = new Trie<String>();
835        fixture.train(sequence, 11);
836
837        final List<String> sequences = new ArrayList<String>();
838        TrieProcessor<String> processor = new TrieProcessor<String>() {
839            @Override
840            public TrieProcessor.Result process(List<String> sequence, int count) {
841                sequences.add(count + "_" + sequence.toString());
842                return TrieProcessor.Result.CONTINUE;
843            }
844
845        };
846
847        fixture.process(processor);
848
849        List<String> expected = new ArrayList<String>();
850
851        expected.add("5_[a]");
852        expected.add("2_[a, b]");
853        expected.add("2_[a, b, r]");
854        expected.add("2_[a, b, r, a]");
855        expected.add("1_[a, b, r, a, c]");
856        expected.add("1_[a, b, r, a, c, a]");
857        expected.add("1_[a, b, r, a, c, a, d]");
858        expected.add("1_[a, b, r, a, c, a, d, a]");
859        expected.add("1_[a, b, r, a, c, a, d, a, b]");
860        expected.add("1_[a, b, r, a, c, a, d, a, b, r]");
861        expected.add("1_[a, b, r, a, c, a, d, a, b, r, a]");
862        expected.add("2_[b]");
863        expected.add("2_[b, r]");
864        expected.add("2_[b, r, a]");
865        expected.add("1_[b, r, a, c]");
866        expected.add("1_[b, r, a, c, a]");
867        expected.add("1_[b, r, a, c, a, d]");
868        expected.add("1_[b, r, a, c, a, d, a]");
869        expected.add("1_[b, r, a, c, a, d, a, b]");
870        expected.add("1_[b, r, a, c, a, d, a, b, r]");
871        expected.add("1_[b, r, a, c, a, d, a, b, r, a]");
872        expected.add("2_[r]");
873        expected.add("2_[r, a]");
874        expected.add("1_[r, a, c]");
875        expected.add("1_[r, a, c, a]");
876        expected.add("1_[r, a, c, a, d]");
877        expected.add("1_[r, a, c, a, d, a]");
878        expected.add("1_[r, a, c, a, d, a, b]");
879        expected.add("1_[r, a, c, a, d, a, b, r]");
880        expected.add("1_[r, a, c, a, d, a, b, r, a]");
881        expected.add("1_[a, c]");
882        expected.add("1_[a, c, a]");
883        expected.add("1_[a, c, a, d]");
884        expected.add("1_[a, c, a, d, a]");
885        expected.add("1_[a, c, a, d, a, b]");
886        expected.add("1_[a, c, a, d, a, b, r]");
887        expected.add("1_[a, c, a, d, a, b, r, a]");
888        expected.add("1_[c]");
889        expected.add("1_[c, a]");
890        expected.add("1_[c, a, d]");
891        expected.add("1_[c, a, d, a]");
892        expected.add("1_[c, a, d, a, b]");
893        expected.add("1_[c, a, d, a, b, r]");
894        expected.add("1_[c, a, d, a, b, r, a]");
895        expected.add("1_[a, d]");
896        expected.add("1_[a, d, a]");
897        expected.add("1_[a, d, a, b]");
898        expected.add("1_[a, d, a, b, r]");
899        expected.add("1_[a, d, a, b, r, a]");
900        expected.add("1_[d]");
901        expected.add("1_[d, a]");
902        expected.add("1_[d, a, b]");
903        expected.add("1_[d, a, b, r]");
904        expected.add("1_[d, a, b, r, a]");
905
906        assertEquals(expected.size(), sequences.size());
907
908        for (String sequence : sequences) {
909            ListAssert.assertContains(expected, sequence);
910        }
911    }
912
913    @Test
914    public void testGetSequencesWithMostOccurrences_1() throws Exception {
915        Trie<String> fixture = new Trie<String>();
916        fixture.train(sequence, 3);
917
918        // get all sequences with a minimal length of one that occur most often
919        Collection<List<String>> result = fixture.getSequencesWithOccurrenceCount(1, 0);
920
921        assertEquals(1, result.size());
922
923        List<String> expected = new ArrayList<String>();
924        expected.add("a");
925
926        ListAssert.assertEquals(expected, result.iterator().next());
927    }
928
929    @Test
930    public void testGetSequencesWithMostOccurrences_2() throws Exception {
931        Trie<String> fixture = new Trie<String>();
932        fixture.train(sequence, 3);
933
934        // get all sequences with a minimal length of one that occur exactly once
935        Collection<List<String>> result = fixture.getSequencesWithOccurrenceCount(1, 1);
936
937        assertEquals(11, result.size());
938
939        List<String> expected = new ArrayList<String>();
940        expected.add("r");
941        expected.add("a");
942        expected.add("c");
943        // rac
944        ListAssert.assertContains((List<List<String>>) result, expected);
945
946        expected.clear();
947        expected.add("a");
948        expected.add("c");
949        // ac
950        ListAssert.assertContains((List<List<String>>) result, expected);
951
952        expected.add("a");
953        // aca
954        ListAssert.assertContains((List<List<String>>) result, expected);
955
956        expected.clear();
957        expected.add("c");
958        // c
959        ListAssert.assertContains((List<List<String>>) result, expected);
960
961        expected.add("a");
962        // ca
963        ListAssert.assertContains((List<List<String>>) result, expected);
964
965        expected.add("d");
966        // cad
967        ListAssert.assertContains((List<List<String>>) result, expected);
968
969        expected.clear();
970        expected.add("a");
971        expected.add("d");
972        // ad
973        ListAssert.assertContains((List<List<String>>) result, expected);
974
975        expected.add("a");
976        // ada
977        ListAssert.assertContains((List<List<String>>) result, expected);
978
979        expected.clear();
980        expected.add("d");
981        // d
982        ListAssert.assertContains((List<List<String>>) result, expected);
983
984        expected.add("a");
985        // da
986        ListAssert.assertContains((List<List<String>>) result, expected);
987
988        expected.add("b");
989        // dab
990        ListAssert.assertContains((List<List<String>>) result, expected);
991    }
992
993    @Test
994    public void testGetSequencesWithMostOccurrences_3() throws Exception {
995        Trie<String> fixture = new Trie<String>();
996        fixture.train(sequence, 3);
997
998        // get all sequences with a minimal length of one that occur exactly twice
999        Collection<List<String>> result = fixture.getSequencesWithOccurrenceCount(1, 2);
1000
1001        assertEquals(7, result.size());
1002
1003        List<String> expected = new ArrayList<String>();
1004        expected.add("a");
1005        expected.add("b");
1006        // ab
1007        ListAssert.assertContains((List<List<String>>) result, expected);
1008
1009        expected.add("r");
1010        // abr
1011        ListAssert.assertContains((List<List<String>>) result, expected);
1012
1013        expected.clear();
1014        expected.add("b");
1015        // b
1016        ListAssert.assertContains((List<List<String>>) result, expected);
1017
1018        expected.add("r");
1019        // br
1020        ListAssert.assertContains((List<List<String>>) result, expected);
1021
1022        expected.add("a");
1023        // bra
1024        ListAssert.assertContains((List<List<String>>) result, expected);
1025
1026        expected.clear();
1027        expected.add("r");
1028        // r
1029        ListAssert.assertContains((List<List<String>>) result, expected);
1030
1031        expected.add("a");
1032        // ra
1033        ListAssert.assertContains((List<List<String>>) result, expected);
1034    }
1035
1036    @Test
1037    public void testGetSequencesWithMostOccurrences_4() throws Exception {
1038        Trie<String> fixture = new Trie<String>();
1039        fixture.train(sequence, 3);
1040
1041        // get all sequences with a minimal length of one that occur exactly three times
1042        Collection<List<String>> result = fixture.getSequencesWithOccurrenceCount(1, 3);
1043
1044        assertEquals(0, result.size());
1045    }
1046
1047    @Test
1048    public void testGetSequencesWithMostOccurrences_5() throws Exception {
1049        Trie<String> fixture = new Trie<String>();
1050        fixture.train(sequence, 3);
1051
1052        // get all sequences with a minimal length of one that occur exactly four times
1053        Collection<List<String>> result = fixture.getSequencesWithOccurrenceCount(1, 4);
1054
1055        assertEquals(0, result.size());
1056    }
1057
1058    @Test
1059    public void testGetSequencesWithMostOccurrences_6() throws Exception {
1060        Trie<String> fixture = new Trie<String>();
1061        fixture.train(sequence, 3);
1062
1063        // get all sequences with a minimal length of one that occur exactly five times
1064        Collection<List<String>> result = fixture.getSequencesWithOccurrenceCount(1, 5);
1065
1066        assertEquals(1, result.size());
1067
1068        List<String> expected = new ArrayList<String>();
1069        expected.add("a");
1070        ListAssert.assertContains((List<List<String>>) result, expected);
1071    }
1072
1073    @Test
1074    public void testGetSequencesWithMostOccurrences_7() throws Exception {
1075        Trie<String> fixture = new Trie<String>();
1076        fixture.train(sequence, 3);
1077
1078        // get all sequences with a minimal length of two that occur most often
1079        Collection<List<String>> result = fixture.getSequencesWithOccurrenceCount(2, 0);
1080
1081        assertEquals(5, result.size());
1082
1083        List<String> expected = new ArrayList<String>();
1084        expected.add("a");
1085        expected.add("b");
1086        ListAssert.assertContains((List<List<String>>) result, expected);
1087
1088        expected.add("r");
1089        ListAssert.assertContains((List<List<String>>) result, expected);
1090
1091        expected.clear();
1092        expected.add("b");
1093        expected.add("r");
1094        ListAssert.assertContains((List<List<String>>) result, expected);
1095
1096        expected.add("a");
1097        ListAssert.assertContains((List<List<String>>) result, expected);
1098
1099        expected.clear();
1100        expected.add("r");
1101        expected.add("a");
1102        ListAssert.assertContains((List<List<String>>) result, expected);
1103    }
1104
1105    @Test
1106    public void testGetSequencesWithMostOccurrences_8() throws Exception {
1107        Trie<String> fixture = new Trie<String>();
1108        fixture.train(sequence, 3);
1109
1110        // get all sequences with a minimal length of two that occur exactly once
1111        Collection<List<String>> result = fixture.getSequencesWithOccurrenceCount(2, 1);
1112
1113        assertEquals(9, result.size());
1114
1115        List<String> expected = new ArrayList<String>();
1116        expected.add("r");
1117        expected.add("a");
1118        expected.add("c");
1119        // rac
1120        ListAssert.assertContains((List<List<String>>) result, expected);
1121
1122        expected.clear();
1123        expected.add("a");
1124        expected.add("c");
1125        // ac
1126        ListAssert.assertContains((List<List<String>>) result, expected);
1127
1128        expected.add("a");
1129        // aca
1130        ListAssert.assertContains((List<List<String>>) result, expected);
1131
1132        expected.clear();
1133        expected.add("c");
1134        expected.add("a");
1135        // ca
1136        ListAssert.assertContains((List<List<String>>) result, expected);
1137
1138        expected.add("d");
1139        // cad
1140        ListAssert.assertContains((List<List<String>>) result, expected);
1141
1142        expected.clear();
1143        expected.add("a");
1144        expected.add("d");
1145        // ad
1146        ListAssert.assertContains((List<List<String>>) result, expected);
1147
1148        expected.add("a");
1149        // ada
1150        ListAssert.assertContains((List<List<String>>) result, expected);
1151
1152        expected.clear();
1153        expected.add("d");
1154        expected.add("a");
1155        // da
1156        ListAssert.assertContains((List<List<String>>) result, expected);
1157
1158        expected.add("b");
1159        // dab
1160        ListAssert.assertContains((List<List<String>>) result, expected);
1161    }
1162
1163    @Test
1164    public void testGetSequencesWithMostOccurrences_9() throws Exception {
1165        Trie<String> fixture = new Trie<String>();
1166        fixture.train(sequence, 3);
1167
1168        // get all sequences with a minimal length of two that occur exactly twice
1169        Collection<List<String>> result = fixture.getSequencesWithOccurrenceCount(2, 2);
1170
1171        assertEquals(5, result.size());
1172
1173        List<String> expected = new ArrayList<String>();
1174        expected.add("a");
1175        expected.add("b");
1176        // ab
1177        ListAssert.assertContains((List<List<String>>) result, expected);
1178
1179        expected.add("r");
1180        // abr
1181        ListAssert.assertContains((List<List<String>>) result, expected);
1182
1183        expected.clear();
1184        expected.add("b");
1185        expected.add("r");
1186        // br
1187        ListAssert.assertContains((List<List<String>>) result, expected);
1188
1189        expected.add("a");
1190        // bra
1191        ListAssert.assertContains((List<List<String>>) result, expected);
1192
1193        expected.clear();
1194        expected.add("r");
1195        expected.add("a");
1196        // ra
1197        ListAssert.assertContains((List<List<String>>) result, expected);
1198    }
1199
1200    @Test
1201    public void testGetSequencesWithMostOccurrences_10() throws Exception {
1202        Trie<String> fixture = new Trie<String>();
1203        fixture.train(sequence, 3);
1204
1205        // get all sequences with a minimal length of two that occur exactly three times
1206        Collection<List<String>> result = fixture.getSequencesWithOccurrenceCount(2, 3);
1207
1208        assertEquals(0, result.size());
1209    }
1210
1211    @Test
1212    public void testGetSequencesWithMostOccurrences_11() throws Exception {
1213        Trie<String> fixture = new Trie<String>();
1214        fixture.train(sequence, 3);
1215
1216        // get all sequences with a minimal length of three that occur most often
1217        Collection<List<String>> result = fixture.getSequencesWithOccurrenceCount(3, 0);
1218
1219        assertEquals(2, result.size());
1220
1221        List<String> expected = new ArrayList<String>();
1222        expected.add("a");
1223        expected.add("b");
1224        expected.add("r");
1225        ListAssert.assertContains((List<List<String>>) result, expected);
1226
1227        expected.clear();
1228        expected.add("b");
1229        expected.add("r");
1230        expected.add("a");
1231        ListAssert.assertContains((List<List<String>>) result, expected);
1232    }
1233
1234    @Test
1235    public void testGetSequencesWithMostOccurrences_12() throws Exception {
1236        Trie<String> fixture = new Trie<String>();
1237        fixture.train(sequence, 3);
1238
1239        // get all sequences with a minimal length of three that occur exactly once
1240        Collection<List<String>> result = fixture.getSequencesWithOccurrenceCount(3, 1);
1241
1242        assertEquals(5, result.size());
1243
1244        List<String> expected = new ArrayList<String>();
1245        expected.add("r");
1246        expected.add("a");
1247        expected.add("c");
1248        // rac
1249        ListAssert.assertContains((List<List<String>>) result, expected);
1250
1251        expected.clear();
1252        expected.add("a");
1253        expected.add("c");
1254        expected.add("a");
1255        // aca
1256        ListAssert.assertContains((List<List<String>>) result, expected);
1257
1258        expected.clear();
1259        expected.add("c");
1260        expected.add("a");
1261        expected.add("d");
1262        // cad
1263        ListAssert.assertContains((List<List<String>>) result, expected);
1264
1265        expected.clear();
1266        expected.add("a");
1267        expected.add("d");
1268        expected.add("a");
1269        // ada
1270        ListAssert.assertContains((List<List<String>>) result, expected);
1271
1272        expected.clear();
1273        expected.add("d");
1274        expected.add("a");
1275        expected.add("b");
1276        // dab
1277        ListAssert.assertContains((List<List<String>>) result, expected);
1278    }
1279
1280    @Test
1281    public void testGetSequencesWithMostOccurrences_13() throws Exception {
1282        Trie<String> fixture = new Trie<String>();
1283        fixture.train(sequence, 3);
1284
1285        // get all sequences with a minimal length of four that occur most often
1286        Collection<List<String>> result = fixture.getSequencesWithOccurrenceCount(4, 0);
1287
1288        // none of these exist, as the tree is only trained with sequences of length 3
1289        assertEquals(0, result.size());
1290    }
1291
1292    @Test
1293    public void testGetSequencesWithMostOccurrences_14() throws Exception {
1294        Trie<String> fixture = new Trie<String>();
1295        fixture.train(sequence, 3);
1296
1297        // get all sequences with a minimal length of four that occur exactly once
1298        Collection<List<String>> result = fixture.getSequencesWithOccurrenceCount(4, 1);
1299
1300        // none of these exist, as the tree is only trained with sequences of length 3
1301        assertEquals(0, result.size());
1302    }
1303
1304    @Test
1305    public void testGetCount_1() throws Exception {
1306        Trie<String> fixture = new Trie<String>();
1307        fixture.train(sequence, 3);
1308        List<String> subSequence = new ArrayList<String>();
1309        subSequence.add("a");
1310
1311        int result = fixture.getCount(subSequence);
1312
1313        assertEquals(5, result);
1314    }
1315
1316    @Test
1317    public void testGetCount_2() throws Exception {
1318        Trie<String> fixture = new Trie<String>();
1319        fixture.train(sequence, 3);
1320        List<String> subSequence = new ArrayList<String>();
1321        subSequence.add("a");
1322        subSequence.add("b");
1323
1324        int result = fixture.getCount(subSequence);
1325
1326        assertEquals(2, result);
1327    }
1328
1329    @Test
1330    public void testGetCount_3() throws Exception {
1331        Trie<String> fixture = new Trie<String>();
1332        fixture.train(sequence, 3);
1333        List<String> subSequence = new ArrayList<String>();
1334        subSequence.add("x");
1335
1336        int result = fixture.getCount(subSequence);
1337
1338        assertEquals(0, result);
1339    }
1340
1341    @Test
1342    public void testGetCount_4() throws Exception {
1343        Trie<String> fixture = new Trie<String>();
1344        fixture.train(sequence, 3);
1345        List<String> subSequence = new ArrayList<String>();
1346
1347        int result = fixture.getCount(subSequence, "a");
1348
1349        assertEquals(5, result);
1350    }
1351
1352    @Test
1353    public void testGetCount_5() throws Exception {
1354        Trie<String> fixture = new Trie<String>();
1355        fixture.train(sequence, 3);
1356        List<String> subSequence = new ArrayList<String>();
1357        subSequence.add("a");
1358        subSequence.add("b");
1359
1360        int result = fixture.getCount(subSequence, "r");
1361
1362        assertEquals(2, result);
1363    }
1364
1365    @Test
1366    public void testGetCount_6() throws Exception {
1367        Trie<String> fixture = new Trie<String>();
1368        fixture.train(sequence, 3);
1369        List<String> subSequence = new ArrayList<String>();
1370
1371        int result = fixture.getCount(subSequence, "x");
1372
1373        assertEquals(0, result);
1374    }
1375
1376    @Test
1377    public void testGetFollowingSymbols_1() throws Exception {
1378        Trie<String> fixture = new Trie<String>();
1379        fixture.train(sequence, 3);
1380        List<String> subSequence = new ArrayList<String>();
1381        subSequence.add("a");
1382        Collection<String> expected = new ArrayList<String>();
1383        expected.add("b");
1384        expected.add("c");
1385        expected.add("d");
1386
1387        Collection<String> result = fixture.getFollowingSymbols(subSequence);
1388
1389        assertCollectionContent(expected, result);
1390    }
1391
1392    @Test
1393    public void testGetFollowingSymbols_2() throws Exception {
1394        Trie<String> fixture = new Trie<String>();
1395        fixture.train(sequence, 3);
1396        List<String> subSequence = new ArrayList<String>();
1397        subSequence.add("a");
1398        subSequence.add("b");
1399        subSequence.add("r");
1400
1401        Collection<String> result = fixture.getFollowingSymbols(subSequence);
1402
1403        assertEquals(0, result.size());
1404    }
1405
1406    @Test
1407    public void testGetFollowingSymbols_3() throws Exception {
1408        Trie<String> fixture = new Trie<String>();
1409        fixture.train(sequence, 3);
1410        List<String> subSequence = new ArrayList<String>();
1411        subSequence.add("x");
1412
1413        Collection<String> result = fixture.getFollowingSymbols(subSequence);
1414
1415        assertEquals(0, result.size());
1416    }
1417
1418    @Test
1419    public void testGetNumLeafAncestors_1() throws Exception {
1420        Trie<String> fixture = new Trie<String>();
1421        fixture.train(sequence, 3);
1422
1423        int result = fixture.getNumLeafAncestors();
1424
1425        assertEquals(7, result);
1426    }
1427
1428    @Test
1429    public void testGetNumLeafs_1() throws Exception {
1430        Trie<String> fixture = new Trie<String>();
1431        fixture.train(sequence, 3);
1432
1433        int result = fixture.getNumLeafs();
1434
1435        assertEquals(7, result);
1436    }
1437
1438    @Test
1439    public void testGetNumSymbols_1() throws Exception {
1440        Trie<String> fixture = new Trie<String>();
1441        fixture.train(sequence, 3);
1442
1443        int result = fixture.getNumSymbols();
1444
1445        assertEquals(5, result);
1446    }
1447
1448    @Test
1449    public void testTrain_1() throws Exception {
1450        Trie<String> fixture = new Trie<String>();
1451        int maxOrder = 3;
1452
1453        fixture.train(sequence, maxOrder);
1454
1455        // check if symbols are correct
1456        assertCollectionContent(symbols, fixture.getKnownSymbols());
1457
1458        // check if counters are correct and only the correct nodes exist
1459        TrieNode<String> root = fixture.find(new ArrayList<String>());
1460        TrieNode<String> root_a = root.getChild("a");
1461        TrieNode<String> root_a_a = root_a.getChild("a");
1462        TrieNode<String> root_a_b = root_a.getChild("b");
1463        TrieNode<String> root_a_b_a = root_a_b.getChild("a");
1464        TrieNode<String> root_a_b_b = root_a_b.getChild("b");
1465        TrieNode<String> root_a_b_c = root_a_b.getChild("c");
1466        TrieNode<String> root_a_b_d = root_a_b.getChild("d");
1467        TrieNode<String> root_a_b_r = root_a_b.getChild("r");
1468        TrieNode<String> root_a_c = root_a.getChild("c");
1469        TrieNode<String> root_a_c_a = root_a_c.getChild("a");
1470        TrieNode<String> root_a_c_b = root_a_c.getChild("b");
1471        TrieNode<String> root_a_c_c = root_a_c.getChild("c");
1472        TrieNode<String> root_a_c_d = root_a_c.getChild("d");
1473        TrieNode<String> root_a_c_r = root_a_c.getChild("r");
1474        TrieNode<String> root_a_d = root_a.getChild("d");
1475        TrieNode<String> root_a_d_a = root_a_d.getChild("a");
1476        TrieNode<String> root_a_d_b = root_a_d.getChild("b");
1477        TrieNode<String> root_a_d_c = root_a_d.getChild("c");
1478        TrieNode<String> root_a_d_d = root_a_d.getChild("d");
1479        TrieNode<String> root_a_d_r = root_a_d.getChild("r");
1480        TrieNode<String> root_a_r = root_a.getChild("r");
1481        TrieNode<String> root_b = root.getChild("b");
1482        TrieNode<String> root_b_a = root_b.getChild("a");
1483        TrieNode<String> root_b_b = root_b.getChild("b");
1484        TrieNode<String> root_b_c = root_b.getChild("c");
1485        TrieNode<String> root_b_d = root_b.getChild("d");
1486        TrieNode<String> root_b_r = root_b.getChild("r");
1487        TrieNode<String> root_b_r_a = root_b_r.getChild("a");
1488        TrieNode<String> root_b_r_b = root_b_r.getChild("b");
1489        TrieNode<String> root_b_r_c = root_b_r.getChild("c");
1490        TrieNode<String> root_b_r_d = root_b_r.getChild("d");
1491        TrieNode<String> root_b_r_r = root_b_r.getChild("r");
1492        TrieNode<String> root_c = root.getChild("c");
1493        TrieNode<String> root_c_a = root_c.getChild("a");
1494        TrieNode<String> root_c_a_a = root_c_a.getChild("a");
1495        TrieNode<String> root_c_a_b = root_c_a.getChild("b");
1496        TrieNode<String> root_c_a_c = root_c_a.getChild("c");
1497        TrieNode<String> root_c_a_d = root_c_a.getChild("d");
1498        TrieNode<String> root_c_a_r = root_c_a.getChild("r");
1499        TrieNode<String> root_c_b = root_c.getChild("b");
1500        TrieNode<String> root_c_c = root_c.getChild("c");
1501        TrieNode<String> root_c_d = root_c.getChild("d");
1502        TrieNode<String> root_c_r = root_c.getChild("r");
1503        TrieNode<String> root_d = root.getChild("d");
1504        TrieNode<String> root_d_a = root_d.getChild("a");
1505        TrieNode<String> root_d_a_a = root_d_a.getChild("a");
1506        TrieNode<String> root_d_a_b = root_d_a.getChild("b");
1507        TrieNode<String> root_d_a_c = root_d_a.getChild("c");
1508        TrieNode<String> root_d_a_d = root_d_a.getChild("d");
1509        TrieNode<String> root_d_a_r = root_d_a.getChild("r");
1510        TrieNode<String> root_d_b = root_d.getChild("b");
1511        TrieNode<String> root_d_c = root_d.getChild("c");
1512        TrieNode<String> root_d_d = root_d.getChild("d");
1513        TrieNode<String> root_d_r = root_d.getChild("r");
1514        TrieNode<String> root_r = root.getChild("r");
1515        TrieNode<String> root_r_a = root_r.getChild("a");
1516        TrieNode<String> root_r_a_a = root_r_a.getChild("a");
1517        TrieNode<String> root_r_a_b = root_r_a.getChild("b");
1518        TrieNode<String> root_r_a_c = root_r_a.getChild("c");
1519        TrieNode<String> root_r_a_d = root_r_a.getChild("d");
1520        TrieNode<String> root_r_a_r = root_r_a.getChild("r");
1521        TrieNode<String> root_r_b = root_r.getChild("b");
1522        TrieNode<String> root_r_c = root_r.getChild("c");
1523        TrieNode<String> root_r_d = root_r.getChild("d");
1524        TrieNode<String> root_r_r = root_r.getChild("r");
1525
1526        assertEquals(5, root_a.getCount());
1527        assertNull(root_a_a);
1528        assertEquals(2, root_a_b.getCount());
1529        assertNull(root_a_b_a);
1530        assertNull(root_a_b_b);
1531        assertNull(root_a_b_c);
1532        assertNull(root_a_b_d);
1533        assertEquals(2, root_a_b_r.getCount());
1534        assertEquals(1, root_a_c.getCount());
1535        assertEquals(1, root_a_c_a.getCount());
1536        assertNull(root_a_c_b);
1537        assertNull(root_a_c_c);
1538        assertNull(root_a_c_d);
1539        assertNull(root_a_c_r);
1540        assertEquals(1, root_a_d.getCount());
1541        assertEquals(1, root_a_d_a.getCount());
1542        assertNull(root_a_d_b);
1543        assertNull(root_a_d_c);
1544        assertNull(root_a_d_d);
1545        assertNull(root_a_d_r);
1546        assertNull(root_a_r);
1547
1548        assertEquals(2, root_b.getCount());
1549        assertNull(root_b_a);
1550        assertNull(root_b_b);
1551        assertNull(root_b_c);
1552        assertNull(root_b_d);
1553        assertEquals(2, root_b_r.getCount());
1554        assertEquals(2, root_b_r_a.getCount());
1555        assertNull(root_b_r_b);
1556        assertNull(root_b_r_c);
1557        assertNull(root_b_r_d);
1558        assertNull(root_b_r_r);
1559
1560        assertEquals(1, root_c.getCount());
1561        assertEquals(1, root_c_a.getCount());
1562        assertNull(root_c_a_a);
1563        assertNull(root_c_a_b);
1564        assertNull(root_c_a_c);
1565        assertEquals(1, root_c_a_d.getCount());
1566        assertNull(root_c_a_r);
1567        assertNull(root_c_b);
1568        assertNull(root_c_c);
1569        assertNull(root_c_d);
1570        assertNull(root_c_r);
1571
1572        assertEquals(1, root_d.getCount());
1573        assertEquals(1, root_d_a.getCount());
1574        assertNull(root_d_a_a);
1575        assertEquals(1, root_d_a_b.getCount());
1576        assertNull(root_d_a_c);
1577        assertNull(root_d_a_d);
1578        assertNull(root_d_a_r);
1579        assertNull(root_d_b);
1580        assertNull(root_d_c);
1581        assertNull(root_d_d);
1582        assertNull(root_d_r);
1583
1584        assertEquals(2, root_r.getCount());
1585        assertEquals(2, root_r_a.getCount());
1586        assertNull(root_r_a_a);
1587        assertNull(root_r_a_b);
1588        assertEquals(1, root_r_a_c.getCount());
1589        assertNull(root_r_a_d);
1590        assertNull(root_r_a_r);
1591        assertNull(root_r_b);
1592        assertNull(root_r_c);
1593        assertNull(root_r_d);
1594        assertNull(root_r_r);
1595
1596        // check if leafs are really leafs
1597        assertTrue(root_a_b_r.isLeaf());
1598        assertTrue(root_a_c_a.isLeaf());
1599        assertTrue(root_a_d_a.isLeaf());
1600        assertTrue(root_b_r_a.isLeaf());
1601        assertTrue(root_c_a_d.isLeaf());
1602        assertTrue(root_d_a_b.isLeaf());
1603        assertTrue(root_r_a_c.isLeaf());
1604    }
1605
1606    @Test
1607    public void testTrain_2() throws Exception {
1608        Trie<String> fixture = new Trie<String>();
1609        int maxOrder = 0;
1610
1611        fixture.train(sequence, maxOrder);
1612
1613        assertTrue(fixture.getKnownSymbols().isEmpty());
1614    }
1615
1616    @Test
1617    public void testTrain_3() throws Exception {
1618        Trie<Object> fixture = new Trie<Object>();
1619        List<Object> sequence = new ArrayList<Object>();
1620        int maxOrder = 1;
1621
1622        fixture.train(sequence, maxOrder);
1623
1624        assertTrue(fixture.getKnownSymbols().isEmpty());
1625    }
1626
1627    @Test
1628    public void testTrain_4() throws Exception {
1629        Trie<String> fixture = new Trie<String>();
1630        List<String> sequence = new ArrayList<String>();
1631        sequence.add("a");
1632        sequence.add("b");
1633        int maxOrder = 3;
1634
1635        fixture.train(sequence, maxOrder);
1636
1637        assertCollectionContent(sequence, fixture.getKnownSymbols());
1638        TrieNode<String> root = fixture.find(new ArrayList<String>());
1639        TrieNode<String> root_a = root.getChild("a");
1640        TrieNode<String> root_a_a = root_a.getChild("a");
1641        TrieNode<String> root_a_b = root_a.getChild("b");
1642        TrieNode<String> root_b = root.getChild("b");
1643        TrieNode<String> root_b_a = root_b.getChild("a");
1644        TrieNode<String> root_b_b = root_b.getChild("b");
1645
1646        assertEquals(1, root_a.getCount());
1647        assertNull(root_a_a);
1648        assertEquals(1, root_a_b.getCount());
1649        assertEquals(1, root_b.getCount());
1650        assertNull(root_b_a);
1651        assertNull(root_b_b);
1652
1653        assertTrue(root_a_b.isLeaf());
1654        assertTrue(root_b.isLeaf());
1655    }
1656
1657    @Test
1658    public void testEdgeEdge_1() throws Exception {
1659        Edge result = new Edge();
1660
1661        assertNotNull(result);
1662    }
1663
1664    @Test
1665    public void testTrieVertexTrieVertex_1() throws Exception {
1666        String id = "idString";
1667
1668        TrieVertex result = new TrieVertex(id);
1669
1670        assertNotNull(result);
1671    }
1672
1673    @Test
1674    public void testTrieVertexToString_1() throws Exception {
1675        String id = "idString";
1676        TrieVertex fixture = new TrieVertex(id);
1677
1678        String result = fixture.toString();
1679
1680        assertEquals(id, result);
1681    }
1682
1683    @Test
1684    public void testEquals_1() throws Exception {
1685        Trie<String> trieOther = new Trie<String>();
1686        Trie<String> fixture = new Trie<String>();
1687
1688        boolean result = fixture.equals(trieOther);
1689
1690        assertEquals(true, result);
1691    }
1692
1693    @Test
1694    public void testEquals_2() throws Exception {
1695        Trie<String> trieOther = new Trie<String>();
1696        trieOther.train(sequence, 2);
1697        Trie<String> fixture = new Trie<String>();
1698        fixture.train(sequence, 2);
1699
1700        boolean result = fixture.equals(trieOther);
1701
1702        assertEquals(true, result);
1703    }
1704
1705    @Test
1706    public void testEquals_3() throws Exception {
1707        Trie<String> trieOther = new Trie<String>();
1708        trieOther.train(sequence, 2);
1709        Trie<String> fixture = new Trie<String>();
1710        fixture.train(sequence, 3);
1711
1712        boolean result = fixture.equals(trieOther);
1713
1714        assertEquals(false, result);
1715    }
1716
1717    @Test
1718    public void testEquals_4() throws Exception {
1719        Trie<String> trieOther = new Trie<String>();
1720        Trie<String> fixture = new Trie<String>();
1721        fixture.train(sequence, 2);
1722
1723        boolean result = fixture.equals(trieOther);
1724
1725        assertEquals(false, result);
1726    }
1727
1728    @Test
1729    public void testEquals_5() throws Exception {
1730        Trie<String> trieOther = new Trie<String>();
1731        trieOther.train(sequence, 2);
1732        Trie<String> fixture = new Trie<String>();
1733
1734        boolean result = fixture.equals(trieOther);
1735
1736        assertEquals(false, result);
1737    }
1738
1739    @Test
1740    public void testEquals_6() throws Exception {
1741        Trie<String> fixture = new Trie<String>();
1742        fixture.train(sequence, 2);
1743
1744        boolean result = fixture.equals(fixture);
1745
1746        assertEquals(true, result);
1747    }
1748
1749    @Test
1750    public void testEquals_7() throws Exception {
1751        Trie<String> fixture = new Trie<String>();
1752        fixture.train(sequence, 2);
1753
1754        boolean result = fixture.equals(null);
1755
1756        assertEquals(false, result);
1757    }
1758
1759    @Test
1760    public void testLargeTrie_1() throws Exception {
1761        Trie<Integer> fixture = new Trie<Integer>();
1762
1763        int order = 2;
1764       
1765        TrieTester tester = new TrieTester(3, 10, order);
1766
1767        List<Integer> sequence = new ArrayList<Integer>(tester.sequence.length);
1768       
1769        for (Integer elem : tester.sequence) {
1770            sequence.add(elem);
1771        }
1772       
1773        fixture.train(sequence, order);
1774       
1775        fixture.process(tester);
1776        assertTrue(tester.counts.isEmpty());
1777    }
1778
1779    @Test
1780    public void testLargeTrie_2() throws Exception {
1781        Trie<Integer> fixture = new Trie<Integer>();
1782
1783        int order = 2;
1784       
1785        TrieTester tester = new TrieTester(300, 100000, order);
1786
1787        List<Integer> sequence = new ArrayList<Integer>(tester.sequence.length);
1788       
1789        for (Integer elem : tester.sequence) {
1790            sequence.add(elem);
1791        }
1792       
1793        fixture.train(sequence, order);
1794       
1795        fixture.process(tester);
1796        assertTrue(tester.counts.isEmpty());
1797    }
1798
1799    @Test
1800    public void testLargeTrie_3() throws Exception {
1801        Trie<Integer> fixture = new Trie<Integer>();
1802
1803        int order = 2;
1804       
1805        TrieTester tester = new TrieTester(1000, 100000, order);
1806
1807        List<Integer> sequence = new ArrayList<Integer>(tester.sequence.length);
1808       
1809        for (Integer elem : tester.sequence) {
1810            sequence.add(elem);
1811        }
1812       
1813        fixture.train(sequence, order);
1814       
1815        fixture.process(tester);
1816        assertTrue(tester.counts.isEmpty());
1817    }
1818
1819    @Test
1820    public void testLargeTrie_4() throws Exception {
1821        Trie<Integer> fixture = new Trie<Integer>();
1822
1823        int order = 3;
1824       
1825        TrieTester tester = new TrieTester(3, 50, order);
1826
1827        List<Integer> sequence = new ArrayList<Integer>(tester.sequence.length);
1828       
1829        for (Integer elem : tester.sequence) {
1830            sequence.add(elem);
1831        }
1832       
1833        fixture.train(sequence, order);
1834       
1835        fixture.process(tester);
1836        assertTrue(tester.counts.isEmpty());
1837    }
1838
1839    @Test
1840    public void testLargeTrie_5() throws Exception {
1841        Trie<Integer> fixture = new Trie<Integer>();
1842
1843        int order = 3;
1844       
1845        TrieTester tester = new TrieTester(300, 100000, order);
1846
1847        List<Integer> sequence = new ArrayList<Integer>(tester.sequence.length);
1848       
1849        for (Integer elem : tester.sequence) {
1850            sequence.add(elem);
1851        }
1852       
1853        fixture.train(sequence, order);
1854       
1855        fixture.process(tester);
1856        assertTrue(tester.counts.isEmpty());
1857    }
1858
1859    @Test
1860    public void testLargeTrie_6() throws Exception {
1861        Trie<Integer> fixture = new Trie<Integer>();
1862
1863        int order = 3;
1864       
1865        TrieTester tester = new TrieTester(1000, 100000, order);
1866
1867        List<Integer> sequence = new ArrayList<Integer>(tester.sequence.length);
1868       
1869        for (Integer elem : tester.sequence) {
1870            sequence.add(elem);
1871        }
1872       
1873        fixture.train(sequence, order);
1874       
1875        fixture.process(tester);
1876        assertTrue(tester.counts.isEmpty());
1877    }
1878
1879    @Test
1880    public void testLargeTrie_7() throws Exception {
1881        Trie<Integer> fixture = new Trie<Integer>();
1882
1883        int order = 4;
1884       
1885        TrieTester tester = new TrieTester(3, 50, order);
1886
1887        List<Integer> sequence = new ArrayList<Integer>(tester.sequence.length);
1888       
1889        for (Integer elem : tester.sequence) {
1890            sequence.add(elem);
1891        }
1892       
1893        fixture.train(sequence, order);
1894       
1895        fixture.process(tester);
1896        assertTrue(tester.counts.isEmpty());
1897    }
1898
1899    @Test
1900    public void testLargeTrie_8() throws Exception {
1901        Trie<Integer> fixture = new Trie<Integer>();
1902
1903        int order = 4;
1904       
1905        TrieTester tester = new TrieTester(300, 100000, order);
1906
1907        List<Integer> sequence = new ArrayList<Integer>(tester.sequence.length);
1908       
1909        for (Integer elem : tester.sequence) {
1910            sequence.add(elem);
1911        }
1912       
1913        fixture.train(sequence, order);
1914       
1915        fixture.process(tester);
1916        assertTrue(tester.counts.isEmpty());
1917    }
1918
1919    @Test
1920    public void testLargeTrie_9() throws Exception {
1921        Trie<Integer> fixture = new Trie<Integer>();
1922
1923        int order = 4;
1924       
1925        TrieTester tester = new TrieTester(1000, 100000, order);
1926
1927        List<Integer> sequence = new ArrayList<Integer>(tester.sequence.length);
1928       
1929        for (Integer elem : tester.sequence) {
1930            sequence.add(elem);
1931        }
1932       
1933        fixture.train(sequence, order);
1934       
1935        fixture.process(tester);
1936        assertTrue(tester.counts.isEmpty());
1937    }
1938
1939    @Test
1940    public void testLargeTrie_10() throws Exception {
1941        Trie<Integer> fixture = new Trie<Integer>();
1942
1943        int order = 5;
1944       
1945        TrieTester tester = new TrieTester(3, 50, order);
1946
1947        List<Integer> sequence = new ArrayList<Integer>(tester.sequence.length);
1948       
1949        for (Integer elem : tester.sequence) {
1950            sequence.add(elem);
1951        }
1952       
1953        fixture.train(sequence, order);
1954       
1955        fixture.process(tester);
1956        assertTrue(tester.counts.isEmpty());
1957    }
1958
1959    @Test
1960    public void testLargeTrie_11() throws Exception {
1961        Trie<Integer> fixture = new Trie<Integer>();
1962
1963        int order = 5;
1964       
1965        TrieTester tester = new TrieTester(300, 100000, order);
1966
1967        List<Integer> sequence = new ArrayList<Integer>(tester.sequence.length);
1968       
1969        for (Integer elem : tester.sequence) {
1970            sequence.add(elem);
1971        }
1972       
1973        fixture.train(sequence, order);
1974       
1975        fixture.process(tester);
1976        assertTrue(tester.counts.isEmpty());
1977    }
1978
1979    @Test
1980    public void testLargeTrie_12() throws Exception {
1981        Trie<Integer> fixture = new Trie<Integer>();
1982
1983        int order = 5;
1984       
1985        TrieTester tester = new TrieTester(1000, 100000, order);
1986
1987        List<Integer> sequence = new ArrayList<Integer>(tester.sequence.length);
1988       
1989        for (Integer elem : tester.sequence) {
1990            sequence.add(elem);
1991        }
1992       
1993        fixture.train(sequence, order);
1994       
1995        fixture.process(tester);
1996        assertTrue(tester.counts.isEmpty());
1997    }
1998
1999    @Test
2000    public void testLargeTrie_13() throws Exception {
2001        Trie<Integer> fixture = new Trie<Integer>();
2002
2003        int order = 6;
2004       
2005        TrieTester tester = new TrieTester(3, 50, order);
2006
2007        List<Integer> sequence = new ArrayList<Integer>(tester.sequence.length);
2008       
2009        for (Integer elem : tester.sequence) {
2010            sequence.add(elem);
2011        }
2012       
2013        fixture.train(sequence, order);
2014       
2015        fixture.process(tester);
2016        assertTrue(tester.counts.isEmpty());
2017    }
2018
2019    @Test
2020    public void testLargeTrie_14() throws Exception {
2021        Trie<Integer> fixture = new Trie<Integer>();
2022
2023        int order = 6;
2024       
2025        TrieTester tester = new TrieTester(300, 100000, order);
2026
2027        List<Integer> sequence = new ArrayList<Integer>(tester.sequence.length);
2028       
2029        for (Integer elem : tester.sequence) {
2030            sequence.add(elem);
2031        }
2032       
2033        fixture.train(sequence, order);
2034       
2035        fixture.process(tester);
2036        assertTrue(tester.counts.isEmpty());
2037    }
2038
2039    @Test
2040    public void testLargeTrie_15() throws Exception {
2041        Trie<Integer> fixture = new Trie<Integer>();
2042
2043        int order = 6;
2044       
2045        TrieTester tester = new TrieTester(1000, 100000, order);
2046
2047        List<Integer> sequence = new ArrayList<Integer>(tester.sequence.length);
2048       
2049        for (Integer elem : tester.sequence) {
2050            sequence.add(elem);
2051        }
2052       
2053        fixture.train(sequence, order);
2054       
2055        fixture.process(tester);
2056        assertTrue(tester.counts.isEmpty());
2057    }
2058
2059    @Before
2060    public void setUp() throws Exception {
2061        sequence = new ArrayList<String>();
2062        sequence.add("a");
2063        sequence.add("b");
2064        sequence.add("r");
2065        sequence.add("a");
2066        sequence.add("c");
2067        sequence.add("a");
2068        sequence.add("d");
2069        sequence.add("a");
2070        sequence.add("b");
2071        sequence.add("r");
2072        sequence.add("a");
2073
2074        symbols = new HashSet<String>();
2075        symbols.add("a");
2076        symbols.add("b");
2077        symbols.add("c");
2078        symbols.add("d");
2079        symbols.add("r");
2080    }
2081
2082    public static void main(String[] args) {
2083        new org.junit.runner.JUnitCore().run(TrieTest.class);
2084    }
2085
2086    /**
2087     * <p>
2088     * class internally used for testing large tries.
2089     * </p>
2090     *
2091     * @author Patrick Harms
2092     */
2093    private static class TrieTester implements TrieProcessor<Integer> {
2094       
2095        /**
2096         * the symbols used for testing the trie
2097         */
2098        private int[] symbols;
2099
2100        /**
2101         * the simulated sequence
2102         */
2103        private int[] sequence;
2104
2105        /**
2106         * the trained order of the tested trie
2107         */
2108        private int maxOrder;
2109       
2110        /**
2111         * the expected counts of subsequences
2112         */
2113        private Map<Long, Integer> counts = new HashMap<Long, Integer>();
2114
2115        /**
2116         * generates a simulated sequence and thereby stores the expected counts of the
2117         * subsequences up to max order in a map. The technique uses integer and long values
2118         * to be efficient and to allow testing with large sequences and symbol numbers. However,
2119         * the technique is restricted to 1024 different symbols and a maximum tree depth of 6.
2120         * The tester is also used as a trie processor to check for any node in the tree, if the
2121         * trie calculated the count correctly and if it did not create too many nodes.
2122         */
2123        public TrieTester(int noOfSymbols, int sequenceLength, int maxOrder) {
2124            if (noOfSymbols > 1024) {
2125                throw new IllegalArgumentException("too large number of symbols");
2126            }
2127            if (maxOrder > 6) {
2128                throw new IllegalArgumentException("too large number of symbols");
2129            }
2130           
2131            this.symbols = new int[noOfSymbols];
2132           
2133            for (int i = 0; i < noOfSymbols; i++) {
2134                this.symbols[i] = i;
2135             }
2136           
2137            this.maxOrder = maxOrder;
2138           
2139            this.sequence = new int[sequenceLength];
2140
2141            for (int i = 0; i < sequenceLength; i++) {
2142                int symbolIndex = (int) (Math.random() * noOfSymbols);
2143                this.sequence[i] = this.symbols[symbolIndex];
2144               
2145                if ((i - maxOrder + 1) >= 0) {
2146                    storeCounts(this.sequence, i - maxOrder + 1, i);
2147                }
2148            }
2149           
2150            for (int i = sequenceLength - maxOrder + 1; i < sequenceLength; i++) {
2151                storeCounts(this.sequence, i, sequenceLength - 1);
2152            }
2153        }
2154
2155        /**
2156         * <p>
2157         * stores the counts for the subsequence denoted by the start and end index (inclusive).
2158         * </p>
2159         */
2160        private void storeCounts(int[] sequence, int startIndex, int endIndex) {
2161            long key = 0;
2162           
2163            for (int i = startIndex; i <= endIndex; i++) {
2164                key = key << 10;
2165                key += 1 + this.sequence[i];
2166           
2167                Integer count = this.counts.get(key);
2168                if (count == null) {
2169                    count = 0;
2170                }
2171           
2172                //System.out.println(key + "  " + (count + 1));
2173                this.counts.put(key, count + 1);
2174            }
2175        }
2176
2177        /* (non-Javadoc)
2178         * @see de.ugoe.cs.autoquest.usageprofiles.TrieProcessor#process(java.util.List, int)
2179         */
2180        @Override
2181        public TrieProcessor.Result process(List<Integer> sequence, int count) {
2182            long key = 0;
2183           
2184            for (Integer symbol : sequence) {
2185                key = key << 10;
2186                key += 1 + symbol;
2187            }
2188           
2189            Integer expectedCount = this.counts.remove(key);
2190            assertNotNull(expectedCount);
2191            assertEquals(expectedCount.intValue(), count);
2192           
2193            assertTrue(sequence.size() <= this.maxOrder);
2194           
2195            return TrieProcessor.Result.CONTINUE;
2196        }
2197
2198    }
2199}
Note: See TracBrowser for help on using the repository browser.