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

Last change on this file since 1252 was 1252, checked in by pharms, 11 years ago
  • corrected formating
  • Property svn:mime-type set to text/plain
File size: 60.3 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.HashSet;
20import java.util.List;
21
22import junitx.framework.ListAssert;
23
24import org.junit.*;
25
26import de.ugoe.cs.autoquest.usageprofiles.Trie;
27import de.ugoe.cs.autoquest.usageprofiles.TrieNode;
28import de.ugoe.cs.autoquest.usageprofiles.Trie.Edge;
29import de.ugoe.cs.autoquest.usageprofiles.Trie.TrieVertex;
30import static org.junit.Assert.*;
31
32/**
33 * The class <code>TrieTest</code> contains tests for the class <code>{@link Trie}</code>.
34 *
35 * @author Steffen Herbold
36 * @version 1.0
37 */
38public class TrieTest {
39
40    List<String> sequence;
41    Collection<String> symbols;
42
43    private static void assertCollectionContent(Collection<?> c1, Collection<?> c2) {
44        assertEquals(c1.size(), c2.size());
45        for (Object obj : c1) {
46            assertTrue(c2.contains(obj));
47        }
48    }
49
50    @Test
51    public void testTrie_1() throws Exception {
52
53        Trie<String> result = new Trie<String>();
54
55        assertNotNull(result);
56        assertEquals(0, result.getNumLeafs());
57        assertEquals(0, result.getNumSymbols());
58        assertEquals(0, result.getNumLeafAncestors());
59        assertTrue(result.getKnownSymbols().isEmpty());
60    }
61
62    @Test
63    public void testTrie_2() throws Exception {
64        Trie<String> trie1 = new Trie<String>();
65        trie1.train(sequence, 3);
66
67        Trie<String> result = new Trie<String>(trie1);
68
69        assertEquals(trie1, result);
70        assertNotSame(trie1, result);
71    }
72
73    @Test(expected = java.lang.IllegalArgumentException.class)
74    public void testTrie_3() throws Exception {
75        new Trie<String>((SymbolComparator<String>) null);
76    }
77
78    @Test(expected = java.lang.IllegalArgumentException.class)
79    public void testTrie_4() throws Exception {
80        new Trie<String>((Trie<String>) null);
81    }
82
83    @Test
84    public void testAdd_1() throws Exception {
85        Trie<String> fixture = new Trie<String>();
86        List<String> seq = new ArrayList<String>();
87        seq.add("a");
88        seq.add("b");
89
90        fixture.add(seq);
91
92        assertEquals(1, fixture.getChild("a").getCount());
93        assertEquals(1, fixture.getChild("a").getChild("b").getCount());
94        assertNull(fixture.getChild("b"));
95    }
96
97    @Test
98    public void testAdd_2() throws Exception {
99        Trie<String> fixture = new Trie<String>();
100
101        fixture.add(new ArrayList<String>());
102
103        assertEquals(0, fixture.getNumSymbols());
104    }
105
106    @Test
107    public void testAdd_3() throws Exception {
108        Trie<String> fixture = new Trie<String>();
109
110        fixture.add(null);
111
112        assertEquals(0, fixture.getNumSymbols());
113    }
114
115    @Test
116    public void testFind_1() throws Exception {
117        Trie<String> fixture = new Trie<String>();
118        fixture.train(sequence, 3);
119        List<String> findSequence = new ArrayList<String>();
120        findSequence.add("a");
121        findSequence.add("b");
122        findSequence.add("r");
123        TrieNode<String> expected = fixture.getChild("a").getChild("b").getChild("r");
124
125        TrieNode<String> result = fixture.find(findSequence);
126
127        assertEquals(expected, result);
128    }
129
130    @Test
131    public void testFind_2() throws Exception {
132        Trie<String> fixture = new Trie<String>();
133        fixture.train(sequence, 3);
134        List<String> findSequence = new ArrayList<String>();
135        findSequence.add("c");
136        findSequence.add("a");
137        TrieNode<String> expected = fixture.getChild("c").getChild("a");
138
139        TrieNode<String> result = fixture.find(findSequence);
140
141        assertEquals(expected, result);
142    }
143
144    @Test
145    public void testFind_3() throws Exception {
146        Trie<String> fixture = new Trie<String>();
147        fixture.train(sequence, 3);
148        List<String> findSequence = new ArrayList<String>();
149
150        TrieNode<String> result = fixture.find(findSequence);
151
152        assertTrue(result.isRoot());
153    }
154
155    @Test
156    public void testFind_4() throws Exception {
157        Trie<String> fixture = new Trie<String>();
158        fixture.train(sequence, 3);
159
160        TrieNode<String> result = fixture.find(null);
161
162        assertTrue(result.isRoot());
163    }
164
165    @Test
166    public void testGetChildCreate_1() throws Exception {
167        Trie<String> fixture = new Trie<String>();
168        String symbol = "a";
169
170        TrieNode<String> result = fixture.getChildCreate(symbol);
171
172        assertEquals(symbol, result.getSymbol());
173        assertEquals(0, result.getCount());
174        assertTrue(result.isLeaf());
175    }
176
177    @Test(expected = java.lang.IllegalArgumentException.class)
178    public void testGetChildCreate_2() throws Exception {
179        Trie<String> fixture = new Trie<String>();
180        fixture.getChildCreate(null);
181    }
182
183    @Test
184    public void testGetContextSuffix_1() throws Exception {
185        Trie<String> fixture = new Trie<String>();
186        fixture.train(sequence, 3);
187        List<String> context = new ArrayList<String>();
188        context.add("a");
189        context.add("a");
190        context.add("b");
191        List<String> expected = new ArrayList<String>();
192        expected.add("a");
193        expected.add("b");
194
195        List<String> result = fixture.getContextSuffix(context);
196
197        ListAssert.assertEquals(expected, result);
198    }
199
200    @Test
201    public void testGetContextSuffix_2() throws Exception {
202        Trie<String> fixture = new Trie<String>();
203        fixture.train(sequence, 3);
204        List<String> context = new ArrayList<String>();
205        context.add("a");
206        context.add("a");
207        context.add("b");
208        context.add("r");
209        List<String> expected = new ArrayList<String>();
210        expected.add("b");
211        expected.add("r");
212
213        List<String> result = fixture.getContextSuffix(context);
214
215        ListAssert.assertEquals(expected, result);
216    }
217
218    @Test
219    public void testGetContextSuffix_3() throws Exception {
220        Trie<String> fixture = new Trie<String>();
221        fixture.train(sequence, 3);
222        List<String> context = new ArrayList<String>();
223        context.add("a");
224        context.add("a");
225        context.add("b");
226        context.add("x");
227        List<String> expected = new ArrayList<String>();
228
229        List<String> result = fixture.getContextSuffix(context);
230
231        ListAssert.assertEquals(expected, result);
232    }
233
234    @Test
235    public void testGetContextSuffix_4() throws Exception {
236        Trie<String> fixture = new Trie<String>();
237
238        List<String> result = fixture.getContextSuffix(null);
239
240        // add additional test code here
241        assertNotNull(result);
242        assertEquals(0, result.size());
243    }
244
245    @Test
246    public void testGetContextSuffix_5() throws Exception {
247        Trie<String> fixture = new Trie<String>();
248        fixture.train(sequence, 3);
249        List<String> context = new ArrayList<String>();
250        context.add("a");
251        context.add("a");
252        context.add("b");
253        List<String> expected = new ArrayList<String>();
254        expected.add("a");
255        expected.add("b");
256
257        List<String> result = fixture.getContextSuffix(context);
258
259        ListAssert.assertEquals(expected, result);
260    }
261
262    @Test
263    public void testProcessWithTrieProcessor_1() throws Exception {
264        Trie<String> fixture = new Trie<String>();
265        fixture.train(sequence, 2);
266
267        final List<String> sequences = new ArrayList<String>();
268        TrieProcessor<String> processor = new TrieProcessor<String>() {
269            @Override
270            public TrieProcessor.Result process(List<String> sequence, int count) {
271                sequences.add(count + "_" + sequence.toString());
272                return TrieProcessor.Result.CONTINUE;
273            }
274
275        };
276
277        fixture.process(processor);
278
279        List<String> expected = new ArrayList<String>();
280
281        expected.add("5_[a]");
282        expected.add("2_[a, b]");
283        expected.add("2_[b]");
284        expected.add("2_[b, r]");
285        expected.add("2_[r]");
286        expected.add("2_[r, a]");
287        expected.add("1_[a, c]");
288        expected.add("1_[c]");
289        expected.add("1_[c, a]");
290        expected.add("1_[a, d]");
291        expected.add("1_[d]");
292        expected.add("1_[d, a]");
293
294        assertEquals(expected.size(), sequences.size());
295
296        for (String sequence : sequences) {
297            ListAssert.assertContains(expected, sequence);
298        }
299    }
300
301    @Test
302    public void testProcessWithTrieProcessor_2() throws Exception {
303        Trie<String> fixture = new Trie<String>();
304        fixture.train(sequence, 3);
305
306        final List<String> sequences = new ArrayList<String>();
307        TrieProcessor<String> processor = new TrieProcessor<String>() {
308            @Override
309            public TrieProcessor.Result process(List<String> sequence, int count) {
310                sequences.add(count + "_" + sequence.toString());
311                return TrieProcessor.Result.CONTINUE;
312            }
313
314        };
315
316        fixture.process(processor);
317
318        List<String> expected = new ArrayList<String>();
319
320        expected.add("5_[a]");
321        expected.add("2_[a, b]");
322        expected.add("2_[a, b, r]");
323        expected.add("2_[b]");
324        expected.add("2_[b, r]");
325        expected.add("2_[b, r, a]");
326        expected.add("2_[r]");
327        expected.add("2_[r, a]");
328        expected.add("1_[r, a, c]");
329        expected.add("1_[a, c]");
330        expected.add("1_[a, c, a]");
331        expected.add("1_[c]");
332        expected.add("1_[c, a]");
333        expected.add("1_[c, a, d]");
334        expected.add("1_[a, d]");
335        expected.add("1_[a, d, a]");
336        expected.add("1_[d]");
337        expected.add("1_[d, a]");
338        expected.add("1_[d, a, b]");
339
340        assertEquals(expected.size(), sequences.size());
341
342        for (String sequence : sequences) {
343            ListAssert.assertContains(expected, sequence);
344        }
345    }
346
347    @Test
348    public void testProcessWithTrieProcessor_3() throws Exception {
349        Trie<String> fixture = new Trie<String>();
350        fixture.train(sequence, 4);
351
352        final List<String> sequences = new ArrayList<String>();
353        TrieProcessor<String> processor = new TrieProcessor<String>() {
354            @Override
355            public TrieProcessor.Result process(List<String> sequence, int count) {
356                sequences.add(count + "_" + sequence.toString());
357                return TrieProcessor.Result.CONTINUE;
358            }
359
360        };
361
362        fixture.process(processor);
363
364        List<String> expected = new ArrayList<String>();
365
366        expected.add("5_[a]");
367        expected.add("2_[a, b]");
368        expected.add("2_[a, b, r]");
369        expected.add("2_[a, b, r, a]");
370        expected.add("2_[b]");
371        expected.add("2_[b, r]");
372        expected.add("2_[b, r, a]");
373        expected.add("1_[b, r, a, c]");
374        expected.add("2_[r]");
375        expected.add("2_[r, a]");
376        expected.add("1_[r, a, c]");
377        expected.add("1_[r, a, c, a]");
378        expected.add("1_[a, c]");
379        expected.add("1_[a, c, a]");
380        expected.add("1_[a, c, a, d]");
381        expected.add("1_[c]");
382        expected.add("1_[c, a]");
383        expected.add("1_[c, a, d]");
384        expected.add("1_[c, a, d, a]");
385        expected.add("1_[a, d]");
386        expected.add("1_[a, d, a]");
387        expected.add("1_[a, d, a, b]");
388        expected.add("1_[d]");
389        expected.add("1_[d, a]");
390        expected.add("1_[d, a, b]");
391        expected.add("1_[d, a, b, r]");
392
393        assertEquals(expected.size(), sequences.size());
394
395        for (String sequence : sequences) {
396            ListAssert.assertContains(expected, sequence);
397        }
398    }
399
400    @Test
401    public void testProcessWithTrieProcessor_4() throws Exception {
402        Trie<String> fixture = new Trie<String>();
403        fixture.train(sequence, 5);
404
405        final List<String> sequences = new ArrayList<String>();
406        TrieProcessor<String> processor = new TrieProcessor<String>() {
407            @Override
408            public TrieProcessor.Result process(List<String> sequence, int count) {
409                sequences.add(count + "_" + sequence.toString());
410                return TrieProcessor.Result.CONTINUE;
411            }
412
413        };
414
415        fixture.process(processor);
416
417        List<String> expected = new ArrayList<String>();
418
419        expected.add("5_[a]");
420        expected.add("2_[a, b]");
421        expected.add("2_[a, b, r]");
422        expected.add("2_[a, b, r, a]");
423        expected.add("1_[a, b, r, a, c]");
424        expected.add("2_[b]");
425        expected.add("2_[b, r]");
426        expected.add("2_[b, r, a]");
427        expected.add("1_[b, r, a, c]");
428        expected.add("1_[b, r, a, c, a]");
429        expected.add("2_[r]");
430        expected.add("2_[r, a]");
431        expected.add("1_[r, a, c]");
432        expected.add("1_[r, a, c, a]");
433        expected.add("1_[r, a, c, a, d]");
434        expected.add("1_[a, c]");
435        expected.add("1_[a, c, a]");
436        expected.add("1_[a, c, a, d]");
437        expected.add("1_[a, c, a, d, a]");
438        expected.add("1_[c]");
439        expected.add("1_[c, a]");
440        expected.add("1_[c, a, d]");
441        expected.add("1_[c, a, d, a]");
442        expected.add("1_[c, a, d, a, b]");
443        expected.add("1_[a, d]");
444        expected.add("1_[a, d, a]");
445        expected.add("1_[a, d, a, b]");
446        expected.add("1_[a, d, a, b, r]");
447        expected.add("1_[d]");
448        expected.add("1_[d, a]");
449        expected.add("1_[d, a, b]");
450        expected.add("1_[d, a, b, r]");
451        expected.add("1_[d, a, b, r, a]");
452
453        assertEquals(expected.size(), sequences.size());
454
455        for (String sequence : sequences) {
456            ListAssert.assertContains(expected, sequence);
457        }
458    }
459
460    @Test
461    public void testProcessWithTrieProcessor_5() throws Exception {
462        Trie<String> fixture = new Trie<String>();
463        fixture.train(sequence, 6);
464
465        final List<String> sequences = new ArrayList<String>();
466        TrieProcessor<String> processor = new TrieProcessor<String>() {
467            @Override
468            public TrieProcessor.Result process(List<String> sequence, int count) {
469                sequences.add(count + "_" + sequence.toString());
470                return TrieProcessor.Result.CONTINUE;
471            }
472
473        };
474
475        fixture.process(processor);
476
477        List<String> expected = new ArrayList<String>();
478
479        expected.add("5_[a]");
480        expected.add("2_[a, b]");
481        expected.add("2_[a, b, r]");
482        expected.add("2_[a, b, r, a]");
483        expected.add("1_[a, b, r, a, c]");
484        expected.add("1_[a, b, r, a, c, a]");
485        expected.add("2_[b]");
486        expected.add("2_[b, r]");
487        expected.add("2_[b, r, a]");
488        expected.add("1_[b, r, a, c]");
489        expected.add("1_[b, r, a, c, a]");
490        expected.add("1_[b, r, a, c, a, d]");
491        expected.add("2_[r]");
492        expected.add("2_[r, a]");
493        expected.add("1_[r, a, c]");
494        expected.add("1_[r, a, c, a]");
495        expected.add("1_[r, a, c, a, d]");
496        expected.add("1_[r, a, c, a, d, a]");
497        expected.add("1_[a, c]");
498        expected.add("1_[a, c, a]");
499        expected.add("1_[a, c, a, d]");
500        expected.add("1_[a, c, a, d, a]");
501        expected.add("1_[a, c, a, d, a, b]");
502        expected.add("1_[c]");
503        expected.add("1_[c, a]");
504        expected.add("1_[c, a, d]");
505        expected.add("1_[c, a, d, a]");
506        expected.add("1_[c, a, d, a, b]");
507        expected.add("1_[c, a, d, a, b, r]");
508        expected.add("1_[a, d]");
509        expected.add("1_[a, d, a]");
510        expected.add("1_[a, d, a, b]");
511        expected.add("1_[a, d, a, b, r]");
512        expected.add("1_[a, d, a, b, r, a]");
513        expected.add("1_[d]");
514        expected.add("1_[d, a]");
515        expected.add("1_[d, a, b]");
516        expected.add("1_[d, a, b, r]");
517        expected.add("1_[d, a, b, r, a]");
518
519        assertEquals(expected.size(), sequences.size());
520
521        for (String sequence : sequences) {
522            ListAssert.assertContains(expected, sequence);
523        }
524    }
525
526    @Test
527    public void testProcessWithTrieProcessor_6() throws Exception {
528        Trie<String> fixture = new Trie<String>();
529        fixture.train(sequence, 7);
530
531        final List<String> sequences = new ArrayList<String>();
532        TrieProcessor<String> processor = new TrieProcessor<String>() {
533            @Override
534            public TrieProcessor.Result process(List<String> sequence, int count) {
535                sequences.add(count + "_" + sequence.toString());
536                return TrieProcessor.Result.CONTINUE;
537            }
538
539        };
540
541        fixture.process(processor);
542
543        List<String> expected = new ArrayList<String>();
544
545        expected.add("5_[a]");
546        expected.add("2_[a, b]");
547        expected.add("2_[a, b, r]");
548        expected.add("2_[a, b, r, a]");
549        expected.add("1_[a, b, r, a, c]");
550        expected.add("1_[a, b, r, a, c, a]");
551        expected.add("1_[a, b, r, a, c, a, d]");
552        expected.add("2_[b]");
553        expected.add("2_[b, r]");
554        expected.add("2_[b, r, a]");
555        expected.add("1_[b, r, a, c]");
556        expected.add("1_[b, r, a, c, a]");
557        expected.add("1_[b, r, a, c, a, d]");
558        expected.add("1_[b, r, a, c, a, d, a]");
559        expected.add("2_[r]");
560        expected.add("2_[r, a]");
561        expected.add("1_[r, a, c]");
562        expected.add("1_[r, a, c, a]");
563        expected.add("1_[r, a, c, a, d]");
564        expected.add("1_[r, a, c, a, d, a]");
565        expected.add("1_[r, a, c, a, d, a, b]");
566        expected.add("1_[a, c]");
567        expected.add("1_[a, c, a]");
568        expected.add("1_[a, c, a, d]");
569        expected.add("1_[a, c, a, d, a]");
570        expected.add("1_[a, c, a, d, a, b]");
571        expected.add("1_[a, c, a, d, a, b, r]");
572        expected.add("1_[c]");
573        expected.add("1_[c, a]");
574        expected.add("1_[c, a, d]");
575        expected.add("1_[c, a, d, a]");
576        expected.add("1_[c, a, d, a, b]");
577        expected.add("1_[c, a, d, a, b, r]");
578        expected.add("1_[c, a, d, a, b, r, a]");
579        expected.add("1_[a, d]");
580        expected.add("1_[a, d, a]");
581        expected.add("1_[a, d, a, b]");
582        expected.add("1_[a, d, a, b, r]");
583        expected.add("1_[a, d, a, b, r, a]");
584        expected.add("1_[d]");
585        expected.add("1_[d, a]");
586        expected.add("1_[d, a, b]");
587        expected.add("1_[d, a, b, r]");
588        expected.add("1_[d, a, b, r, a]");
589
590        assertEquals(expected.size(), sequences.size());
591
592        for (String sequence : sequences) {
593            ListAssert.assertContains(expected, sequence);
594        }
595    }
596
597    @Test
598    public void testProcessWithTrieProcessor_7() throws Exception {
599        Trie<String> fixture = new Trie<String>();
600        fixture.train(sequence, 8);
601
602        final List<String> sequences = new ArrayList<String>();
603        TrieProcessor<String> processor = new TrieProcessor<String>() {
604            @Override
605            public TrieProcessor.Result process(List<String> sequence, int count) {
606                sequences.add(count + "_" + sequence.toString());
607                return TrieProcessor.Result.CONTINUE;
608            }
609
610        };
611
612        fixture.process(processor);
613
614        List<String> expected = new ArrayList<String>();
615
616        expected.add("5_[a]");
617        expected.add("2_[a, b]");
618        expected.add("2_[a, b, r]");
619        expected.add("2_[a, b, r, a]");
620        expected.add("1_[a, b, r, a, c]");
621        expected.add("1_[a, b, r, a, c, a]");
622        expected.add("1_[a, b, r, a, c, a, d]");
623        expected.add("1_[a, b, r, a, c, a, d, a]");
624        expected.add("2_[b]");
625        expected.add("2_[b, r]");
626        expected.add("2_[b, r, a]");
627        expected.add("1_[b, r, a, c]");
628        expected.add("1_[b, r, a, c, a]");
629        expected.add("1_[b, r, a, c, a, d]");
630        expected.add("1_[b, r, a, c, a, d, a]");
631        expected.add("1_[b, r, a, c, a, d, a, b]");
632        expected.add("2_[r]");
633        expected.add("2_[r, a]");
634        expected.add("1_[r, a, c]");
635        expected.add("1_[r, a, c, a]");
636        expected.add("1_[r, a, c, a, d]");
637        expected.add("1_[r, a, c, a, d, a]");
638        expected.add("1_[r, a, c, a, d, a, b]");
639        expected.add("1_[r, a, c, a, d, a, b, r]");
640        expected.add("1_[a, c]");
641        expected.add("1_[a, c, a]");
642        expected.add("1_[a, c, a, d]");
643        expected.add("1_[a, c, a, d, a]");
644        expected.add("1_[a, c, a, d, a, b]");
645        expected.add("1_[a, c, a, d, a, b, r]");
646        expected.add("1_[a, c, a, d, a, b, r, a]");
647        expected.add("1_[c]");
648        expected.add("1_[c, a]");
649        expected.add("1_[c, a, d]");
650        expected.add("1_[c, a, d, a]");
651        expected.add("1_[c, a, d, a, b]");
652        expected.add("1_[c, a, d, a, b, r]");
653        expected.add("1_[c, a, d, a, b, r, a]");
654        expected.add("1_[a, d]");
655        expected.add("1_[a, d, a]");
656        expected.add("1_[a, d, a, b]");
657        expected.add("1_[a, d, a, b, r]");
658        expected.add("1_[a, d, a, b, r, a]");
659        expected.add("1_[d]");
660        expected.add("1_[d, a]");
661        expected.add("1_[d, a, b]");
662        expected.add("1_[d, a, b, r]");
663        expected.add("1_[d, a, b, r, a]");
664
665        assertEquals(expected.size(), sequences.size());
666
667        for (String sequence : sequences) {
668            ListAssert.assertContains(expected, sequence);
669        }
670    }
671
672    @Test
673    public void testProcessWithTrieProcessor_8() throws Exception {
674        Trie<String> fixture = new Trie<String>();
675        fixture.train(sequence, 9);
676
677        final List<String> sequences = new ArrayList<String>();
678        TrieProcessor<String> processor = new TrieProcessor<String>() {
679            @Override
680            public TrieProcessor.Result process(List<String> sequence, int count) {
681                sequences.add(count + "_" + sequence.toString());
682                return TrieProcessor.Result.CONTINUE;
683            }
684
685        };
686
687        fixture.process(processor);
688
689        List<String> expected = new ArrayList<String>();
690
691        expected.add("5_[a]");
692        expected.add("2_[a, b]");
693        expected.add("2_[a, b, r]");
694        expected.add("2_[a, b, r, a]");
695        expected.add("1_[a, b, r, a, c]");
696        expected.add("1_[a, b, r, a, c, a]");
697        expected.add("1_[a, b, r, a, c, a, d]");
698        expected.add("1_[a, b, r, a, c, a, d, a]");
699        expected.add("1_[a, b, r, a, c, a, d, a, b]");
700        expected.add("2_[b]");
701        expected.add("2_[b, r]");
702        expected.add("2_[b, r, a]");
703        expected.add("1_[b, r, a, c]");
704        expected.add("1_[b, r, a, c, a]");
705        expected.add("1_[b, r, a, c, a, d]");
706        expected.add("1_[b, r, a, c, a, d, a]");
707        expected.add("1_[b, r, a, c, a, d, a, b]");
708        expected.add("1_[b, r, a, c, a, d, a, b, r]");
709        expected.add("2_[r]");
710        expected.add("2_[r, a]");
711        expected.add("1_[r, a, c]");
712        expected.add("1_[r, a, c, a]");
713        expected.add("1_[r, a, c, a, d]");
714        expected.add("1_[r, a, c, a, d, a]");
715        expected.add("1_[r, a, c, a, d, a, b]");
716        expected.add("1_[r, a, c, a, d, a, b, r]");
717        expected.add("1_[r, a, c, a, d, a, b, r, a]");
718        expected.add("1_[a, c]");
719        expected.add("1_[a, c, a]");
720        expected.add("1_[a, c, a, d]");
721        expected.add("1_[a, c, a, d, a]");
722        expected.add("1_[a, c, a, d, a, b]");
723        expected.add("1_[a, c, a, d, a, b, r]");
724        expected.add("1_[a, c, a, d, a, b, r, a]");
725        expected.add("1_[c]");
726        expected.add("1_[c, a]");
727        expected.add("1_[c, a, d]");
728        expected.add("1_[c, a, d, a]");
729        expected.add("1_[c, a, d, a, b]");
730        expected.add("1_[c, a, d, a, b, r]");
731        expected.add("1_[c, a, d, a, b, r, a]");
732        expected.add("1_[a, d]");
733        expected.add("1_[a, d, a]");
734        expected.add("1_[a, d, a, b]");
735        expected.add("1_[a, d, a, b, r]");
736        expected.add("1_[a, d, a, b, r, a]");
737        expected.add("1_[d]");
738        expected.add("1_[d, a]");
739        expected.add("1_[d, a, b]");
740        expected.add("1_[d, a, b, r]");
741        expected.add("1_[d, a, b, r, a]");
742
743        assertEquals(expected.size(), sequences.size());
744
745        for (String sequence : sequences) {
746            ListAssert.assertContains(expected, sequence);
747        }
748    }
749
750    @Test
751    public void testProcessWithTrieProcessor_9() throws Exception {
752        Trie<String> fixture = new Trie<String>();
753        fixture.train(sequence, 10);
754
755        final List<String> sequences = new ArrayList<String>();
756        TrieProcessor<String> processor = new TrieProcessor<String>() {
757            @Override
758            public TrieProcessor.Result process(List<String> sequence, int count) {
759                sequences.add(count + "_" + sequence.toString());
760                return TrieProcessor.Result.CONTINUE;
761            }
762
763        };
764
765        fixture.process(processor);
766
767        List<String> expected = new ArrayList<String>();
768
769        expected.add("5_[a]");
770        expected.add("2_[a, b]");
771        expected.add("2_[a, b, r]");
772        expected.add("2_[a, b, r, a]");
773        expected.add("1_[a, b, r, a, c]");
774        expected.add("1_[a, b, r, a, c, a]");
775        expected.add("1_[a, b, r, a, c, a, d]");
776        expected.add("1_[a, b, r, a, c, a, d, a]");
777        expected.add("1_[a, b, r, a, c, a, d, a, b]");
778        expected.add("1_[a, b, r, a, c, a, d, a, b, r]");
779        expected.add("2_[b]");
780        expected.add("2_[b, r]");
781        expected.add("2_[b, r, a]");
782        expected.add("1_[b, r, a, c]");
783        expected.add("1_[b, r, a, c, a]");
784        expected.add("1_[b, r, a, c, a, d]");
785        expected.add("1_[b, r, a, c, a, d, a]");
786        expected.add("1_[b, r, a, c, a, d, a, b]");
787        expected.add("1_[b, r, a, c, a, d, a, b, r]");
788        expected.add("1_[b, r, a, c, a, d, a, b, r, a]");
789        expected.add("2_[r]");
790        expected.add("2_[r, a]");
791        expected.add("1_[r, a, c]");
792        expected.add("1_[r, a, c, a]");
793        expected.add("1_[r, a, c, a, d]");
794        expected.add("1_[r, a, c, a, d, a]");
795        expected.add("1_[r, a, c, a, d, a, b]");
796        expected.add("1_[r, a, c, a, d, a, b, r]");
797        expected.add("1_[r, a, c, a, d, a, b, r, a]");
798        expected.add("1_[a, c]");
799        expected.add("1_[a, c, a]");
800        expected.add("1_[a, c, a, d]");
801        expected.add("1_[a, c, a, d, a]");
802        expected.add("1_[a, c, a, d, a, b]");
803        expected.add("1_[a, c, a, d, a, b, r]");
804        expected.add("1_[a, c, a, d, a, b, r, a]");
805        expected.add("1_[c]");
806        expected.add("1_[c, a]");
807        expected.add("1_[c, a, d]");
808        expected.add("1_[c, a, d, a]");
809        expected.add("1_[c, a, d, a, b]");
810        expected.add("1_[c, a, d, a, b, r]");
811        expected.add("1_[c, a, d, a, b, r, a]");
812        expected.add("1_[a, d]");
813        expected.add("1_[a, d, a]");
814        expected.add("1_[a, d, a, b]");
815        expected.add("1_[a, d, a, b, r]");
816        expected.add("1_[a, d, a, b, r, a]");
817        expected.add("1_[d]");
818        expected.add("1_[d, a]");
819        expected.add("1_[d, a, b]");
820        expected.add("1_[d, a, b, r]");
821        expected.add("1_[d, a, b, r, a]");
822
823        assertEquals(expected.size(), sequences.size());
824
825        for (String sequence : sequences) {
826            ListAssert.assertContains(expected, sequence);
827        }
828    }
829
830    @Test
831    public void testProcessWithTrieProcessor_10() throws Exception {
832        Trie<String> fixture = new Trie<String>();
833        fixture.train(sequence, 11);
834
835        final List<String> sequences = new ArrayList<String>();
836        TrieProcessor<String> processor = new TrieProcessor<String>() {
837            @Override
838            public TrieProcessor.Result process(List<String> sequence, int count) {
839                sequences.add(count + "_" + sequence.toString());
840                return TrieProcessor.Result.CONTINUE;
841            }
842
843        };
844
845        fixture.process(processor);
846
847        List<String> expected = new ArrayList<String>();
848
849        expected.add("5_[a]");
850        expected.add("2_[a, b]");
851        expected.add("2_[a, b, r]");
852        expected.add("2_[a, b, r, a]");
853        expected.add("1_[a, b, r, a, c]");
854        expected.add("1_[a, b, r, a, c, a]");
855        expected.add("1_[a, b, r, a, c, a, d]");
856        expected.add("1_[a, b, r, a, c, a, d, a]");
857        expected.add("1_[a, b, r, a, c, a, d, a, b]");
858        expected.add("1_[a, b, r, a, c, a, d, a, b, r]");
859        expected.add("1_[a, b, r, a, c, a, d, a, b, r, a]");
860        expected.add("2_[b]");
861        expected.add("2_[b, r]");
862        expected.add("2_[b, r, a]");
863        expected.add("1_[b, r, a, c]");
864        expected.add("1_[b, r, a, c, a]");
865        expected.add("1_[b, r, a, c, a, d]");
866        expected.add("1_[b, r, a, c, a, d, a]");
867        expected.add("1_[b, r, a, c, a, d, a, b]");
868        expected.add("1_[b, r, a, c, a, d, a, b, r]");
869        expected.add("1_[b, r, a, c, a, d, a, b, r, a]");
870        expected.add("2_[r]");
871        expected.add("2_[r, a]");
872        expected.add("1_[r, a, c]");
873        expected.add("1_[r, a, c, a]");
874        expected.add("1_[r, a, c, a, d]");
875        expected.add("1_[r, a, c, a, d, a]");
876        expected.add("1_[r, a, c, a, d, a, b]");
877        expected.add("1_[r, a, c, a, d, a, b, r]");
878        expected.add("1_[r, a, c, a, d, a, b, r, a]");
879        expected.add("1_[a, c]");
880        expected.add("1_[a, c, a]");
881        expected.add("1_[a, c, a, d]");
882        expected.add("1_[a, c, a, d, a]");
883        expected.add("1_[a, c, a, d, a, b]");
884        expected.add("1_[a, c, a, d, a, b, r]");
885        expected.add("1_[a, c, a, d, a, b, r, a]");
886        expected.add("1_[c]");
887        expected.add("1_[c, a]");
888        expected.add("1_[c, a, d]");
889        expected.add("1_[c, a, d, a]");
890        expected.add("1_[c, a, d, a, b]");
891        expected.add("1_[c, a, d, a, b, r]");
892        expected.add("1_[c, a, d, a, b, r, a]");
893        expected.add("1_[a, d]");
894        expected.add("1_[a, d, a]");
895        expected.add("1_[a, d, a, b]");
896        expected.add("1_[a, d, a, b, r]");
897        expected.add("1_[a, d, a, b, r, a]");
898        expected.add("1_[d]");
899        expected.add("1_[d, a]");
900        expected.add("1_[d, a, b]");
901        expected.add("1_[d, a, b, r]");
902        expected.add("1_[d, a, b, r, a]");
903
904        assertEquals(expected.size(), sequences.size());
905
906        for (String sequence : sequences) {
907            ListAssert.assertContains(expected, sequence);
908        }
909    }
910
911    @Test
912    public void testGetSequencesWithMostOccurrences_1() throws Exception {
913        Trie<String> fixture = new Trie<String>();
914        fixture.train(sequence, 3);
915
916        // get all sequences with a minimal length of one that occur most often
917        Collection<List<String>> result = fixture.getSequencesWithOccurrenceCount(1, 0);
918
919        assertEquals(1, result.size());
920
921        List<String> expected = new ArrayList<String>();
922        expected.add("a");
923
924        ListAssert.assertEquals(expected, result.iterator().next());
925    }
926
927    @Test
928    public void testGetSequencesWithMostOccurrences_2() throws Exception {
929        Trie<String> fixture = new Trie<String>();
930        fixture.train(sequence, 3);
931
932        // get all sequences with a minimal length of one that occur exactly once
933        Collection<List<String>> result = fixture.getSequencesWithOccurrenceCount(1, 1);
934
935        assertEquals(11, result.size());
936
937        List<String> expected = new ArrayList<String>();
938        expected.add("r");
939        expected.add("a");
940        expected.add("c");
941        // rac
942        ListAssert.assertContains((List<List<String>>) result, expected);
943
944        expected.clear();
945        expected.add("a");
946        expected.add("c");
947        // ac
948        ListAssert.assertContains((List<List<String>>) result, expected);
949
950        expected.add("a");
951        // aca
952        ListAssert.assertContains((List<List<String>>) result, expected);
953
954        expected.clear();
955        expected.add("c");
956        // c
957        ListAssert.assertContains((List<List<String>>) result, expected);
958
959        expected.add("a");
960        // ca
961        ListAssert.assertContains((List<List<String>>) result, expected);
962
963        expected.add("d");
964        // cad
965        ListAssert.assertContains((List<List<String>>) result, expected);
966
967        expected.clear();
968        expected.add("a");
969        expected.add("d");
970        // ad
971        ListAssert.assertContains((List<List<String>>) result, expected);
972
973        expected.add("a");
974        // ada
975        ListAssert.assertContains((List<List<String>>) result, expected);
976
977        expected.clear();
978        expected.add("d");
979        // d
980        ListAssert.assertContains((List<List<String>>) result, expected);
981
982        expected.add("a");
983        // da
984        ListAssert.assertContains((List<List<String>>) result, expected);
985
986        expected.add("b");
987        // dab
988        ListAssert.assertContains((List<List<String>>) result, expected);
989    }
990
991    @Test
992    public void testGetSequencesWithMostOccurrences_3() throws Exception {
993        Trie<String> fixture = new Trie<String>();
994        fixture.train(sequence, 3);
995
996        // get all sequences with a minimal length of one that occur exactly twice
997        Collection<List<String>> result = fixture.getSequencesWithOccurrenceCount(1, 2);
998
999        assertEquals(7, result.size());
1000
1001        List<String> expected = new ArrayList<String>();
1002        expected.add("a");
1003        expected.add("b");
1004        // ab
1005        ListAssert.assertContains((List<List<String>>) result, expected);
1006
1007        expected.add("r");
1008        // abr
1009        ListAssert.assertContains((List<List<String>>) result, expected);
1010
1011        expected.clear();
1012        expected.add("b");
1013        // b
1014        ListAssert.assertContains((List<List<String>>) result, expected);
1015
1016        expected.add("r");
1017        // br
1018        ListAssert.assertContains((List<List<String>>) result, expected);
1019
1020        expected.add("a");
1021        // bra
1022        ListAssert.assertContains((List<List<String>>) result, expected);
1023
1024        expected.clear();
1025        expected.add("r");
1026        // r
1027        ListAssert.assertContains((List<List<String>>) result, expected);
1028
1029        expected.add("a");
1030        // ra
1031        ListAssert.assertContains((List<List<String>>) result, expected);
1032    }
1033
1034    @Test
1035    public void testGetSequencesWithMostOccurrences_4() throws Exception {
1036        Trie<String> fixture = new Trie<String>();
1037        fixture.train(sequence, 3);
1038
1039        // get all sequences with a minimal length of one that occur exactly three times
1040        Collection<List<String>> result = fixture.getSequencesWithOccurrenceCount(1, 3);
1041
1042        assertEquals(0, result.size());
1043    }
1044
1045    @Test
1046    public void testGetSequencesWithMostOccurrences_5() throws Exception {
1047        Trie<String> fixture = new Trie<String>();
1048        fixture.train(sequence, 3);
1049
1050        // get all sequences with a minimal length of one that occur exactly four times
1051        Collection<List<String>> result = fixture.getSequencesWithOccurrenceCount(1, 4);
1052
1053        assertEquals(0, result.size());
1054    }
1055
1056    @Test
1057    public void testGetSequencesWithMostOccurrences_6() throws Exception {
1058        Trie<String> fixture = new Trie<String>();
1059        fixture.train(sequence, 3);
1060
1061        // get all sequences with a minimal length of one that occur exactly five times
1062        Collection<List<String>> result = fixture.getSequencesWithOccurrenceCount(1, 5);
1063
1064        assertEquals(1, result.size());
1065
1066        List<String> expected = new ArrayList<String>();
1067        expected.add("a");
1068        ListAssert.assertContains((List<List<String>>) result, expected);
1069    }
1070
1071    @Test
1072    public void testGetSequencesWithMostOccurrences_7() throws Exception {
1073        Trie<String> fixture = new Trie<String>();
1074        fixture.train(sequence, 3);
1075
1076        // get all sequences with a minimal length of two that occur most often
1077        Collection<List<String>> result = fixture.getSequencesWithOccurrenceCount(2, 0);
1078
1079        assertEquals(5, result.size());
1080
1081        List<String> expected = new ArrayList<String>();
1082        expected.add("a");
1083        expected.add("b");
1084        ListAssert.assertContains((List<List<String>>) result, expected);
1085
1086        expected.add("r");
1087        ListAssert.assertContains((List<List<String>>) result, expected);
1088
1089        expected.clear();
1090        expected.add("b");
1091        expected.add("r");
1092        ListAssert.assertContains((List<List<String>>) result, expected);
1093
1094        expected.add("a");
1095        ListAssert.assertContains((List<List<String>>) result, expected);
1096
1097        expected.clear();
1098        expected.add("r");
1099        expected.add("a");
1100        ListAssert.assertContains((List<List<String>>) result, expected);
1101    }
1102
1103    @Test
1104    public void testGetSequencesWithMostOccurrences_8() throws Exception {
1105        Trie<String> fixture = new Trie<String>();
1106        fixture.train(sequence, 3);
1107
1108        // get all sequences with a minimal length of two that occur exactly once
1109        Collection<List<String>> result = fixture.getSequencesWithOccurrenceCount(2, 1);
1110
1111        assertEquals(9, result.size());
1112
1113        List<String> expected = new ArrayList<String>();
1114        expected.add("r");
1115        expected.add("a");
1116        expected.add("c");
1117        // rac
1118        ListAssert.assertContains((List<List<String>>) result, expected);
1119
1120        expected.clear();
1121        expected.add("a");
1122        expected.add("c");
1123        // ac
1124        ListAssert.assertContains((List<List<String>>) result, expected);
1125
1126        expected.add("a");
1127        // aca
1128        ListAssert.assertContains((List<List<String>>) result, expected);
1129
1130        expected.clear();
1131        expected.add("c");
1132        expected.add("a");
1133        // ca
1134        ListAssert.assertContains((List<List<String>>) result, expected);
1135
1136        expected.add("d");
1137        // cad
1138        ListAssert.assertContains((List<List<String>>) result, expected);
1139
1140        expected.clear();
1141        expected.add("a");
1142        expected.add("d");
1143        // ad
1144        ListAssert.assertContains((List<List<String>>) result, expected);
1145
1146        expected.add("a");
1147        // ada
1148        ListAssert.assertContains((List<List<String>>) result, expected);
1149
1150        expected.clear();
1151        expected.add("d");
1152        expected.add("a");
1153        // da
1154        ListAssert.assertContains((List<List<String>>) result, expected);
1155
1156        expected.add("b");
1157        // dab
1158        ListAssert.assertContains((List<List<String>>) result, expected);
1159    }
1160
1161    @Test
1162    public void testGetSequencesWithMostOccurrences_9() throws Exception {
1163        Trie<String> fixture = new Trie<String>();
1164        fixture.train(sequence, 3);
1165
1166        // get all sequences with a minimal length of two that occur exactly twice
1167        Collection<List<String>> result = fixture.getSequencesWithOccurrenceCount(2, 2);
1168
1169        assertEquals(5, result.size());
1170
1171        List<String> expected = new ArrayList<String>();
1172        expected.add("a");
1173        expected.add("b");
1174        // ab
1175        ListAssert.assertContains((List<List<String>>) result, expected);
1176
1177        expected.add("r");
1178        // abr
1179        ListAssert.assertContains((List<List<String>>) result, expected);
1180
1181        expected.clear();
1182        expected.add("b");
1183        expected.add("r");
1184        // br
1185        ListAssert.assertContains((List<List<String>>) result, expected);
1186
1187        expected.add("a");
1188        // bra
1189        ListAssert.assertContains((List<List<String>>) result, expected);
1190
1191        expected.clear();
1192        expected.add("r");
1193        expected.add("a");
1194        // ra
1195        ListAssert.assertContains((List<List<String>>) result, expected);
1196    }
1197
1198    @Test
1199    public void testGetSequencesWithMostOccurrences_10() throws Exception {
1200        Trie<String> fixture = new Trie<String>();
1201        fixture.train(sequence, 3);
1202
1203        // get all sequences with a minimal length of two that occur exactly three times
1204        Collection<List<String>> result = fixture.getSequencesWithOccurrenceCount(2, 3);
1205
1206        assertEquals(0, result.size());
1207    }
1208
1209    @Test
1210    public void testGetSequencesWithMostOccurrences_11() throws Exception {
1211        Trie<String> fixture = new Trie<String>();
1212        fixture.train(sequence, 3);
1213
1214        // get all sequences with a minimal length of three that occur most often
1215        Collection<List<String>> result = fixture.getSequencesWithOccurrenceCount(3, 0);
1216
1217        assertEquals(2, result.size());
1218
1219        List<String> expected = new ArrayList<String>();
1220        expected.add("a");
1221        expected.add("b");
1222        expected.add("r");
1223        ListAssert.assertContains((List<List<String>>) result, expected);
1224
1225        expected.clear();
1226        expected.add("b");
1227        expected.add("r");
1228        expected.add("a");
1229        ListAssert.assertContains((List<List<String>>) result, expected);
1230    }
1231
1232    @Test
1233    public void testGetSequencesWithMostOccurrences_12() throws Exception {
1234        Trie<String> fixture = new Trie<String>();
1235        fixture.train(sequence, 3);
1236
1237        // get all sequences with a minimal length of three that occur exactly once
1238        Collection<List<String>> result = fixture.getSequencesWithOccurrenceCount(3, 1);
1239
1240        assertEquals(5, result.size());
1241
1242        List<String> expected = new ArrayList<String>();
1243        expected.add("r");
1244        expected.add("a");
1245        expected.add("c");
1246        // rac
1247        ListAssert.assertContains((List<List<String>>) result, expected);
1248
1249        expected.clear();
1250        expected.add("a");
1251        expected.add("c");
1252        expected.add("a");
1253        // aca
1254        ListAssert.assertContains((List<List<String>>) result, expected);
1255
1256        expected.clear();
1257        expected.add("c");
1258        expected.add("a");
1259        expected.add("d");
1260        // cad
1261        ListAssert.assertContains((List<List<String>>) result, expected);
1262
1263        expected.clear();
1264        expected.add("a");
1265        expected.add("d");
1266        expected.add("a");
1267        // ada
1268        ListAssert.assertContains((List<List<String>>) result, expected);
1269
1270        expected.clear();
1271        expected.add("d");
1272        expected.add("a");
1273        expected.add("b");
1274        // dab
1275        ListAssert.assertContains((List<List<String>>) result, expected);
1276    }
1277
1278    @Test
1279    public void testGetSequencesWithMostOccurrences_13() throws Exception {
1280        Trie<String> fixture = new Trie<String>();
1281        fixture.train(sequence, 3);
1282
1283        // get all sequences with a minimal length of four that occur most often
1284        Collection<List<String>> result = fixture.getSequencesWithOccurrenceCount(4, 0);
1285
1286        // none of these exist, as the tree is only trained with sequences of length 3
1287        assertEquals(0, result.size());
1288    }
1289
1290    @Test
1291    public void testGetSequencesWithMostOccurrences_14() throws Exception {
1292        Trie<String> fixture = new Trie<String>();
1293        fixture.train(sequence, 3);
1294
1295        // get all sequences with a minimal length of four that occur exactly once
1296        Collection<List<String>> result = fixture.getSequencesWithOccurrenceCount(4, 1);
1297
1298        // none of these exist, as the tree is only trained with sequences of length 3
1299        assertEquals(0, result.size());
1300    }
1301
1302    @Test
1303    public void testGetCount_1() throws Exception {
1304        Trie<String> fixture = new Trie<String>();
1305        fixture.train(sequence, 3);
1306        List<String> subSequence = new ArrayList<String>();
1307        subSequence.add("a");
1308
1309        int result = fixture.getCount(subSequence);
1310
1311        assertEquals(5, result);
1312    }
1313
1314    @Test
1315    public void testGetCount_2() throws Exception {
1316        Trie<String> fixture = new Trie<String>();
1317        fixture.train(sequence, 3);
1318        List<String> subSequence = new ArrayList<String>();
1319        subSequence.add("a");
1320        subSequence.add("b");
1321
1322        int result = fixture.getCount(subSequence);
1323
1324        assertEquals(2, result);
1325    }
1326
1327    @Test
1328    public void testGetCount_3() throws Exception {
1329        Trie<String> fixture = new Trie<String>();
1330        fixture.train(sequence, 3);
1331        List<String> subSequence = new ArrayList<String>();
1332        subSequence.add("x");
1333
1334        int result = fixture.getCount(subSequence);
1335
1336        assertEquals(0, result);
1337    }
1338
1339    @Test
1340    public void testGetCount_4() throws Exception {
1341        Trie<String> fixture = new Trie<String>();
1342        fixture.train(sequence, 3);
1343        List<String> subSequence = new ArrayList<String>();
1344
1345        int result = fixture.getCount(subSequence, "a");
1346
1347        assertEquals(5, result);
1348    }
1349
1350    @Test
1351    public void testGetCount_5() throws Exception {
1352        Trie<String> fixture = new Trie<String>();
1353        fixture.train(sequence, 3);
1354        List<String> subSequence = new ArrayList<String>();
1355        subSequence.add("a");
1356        subSequence.add("b");
1357
1358        int result = fixture.getCount(subSequence, "r");
1359
1360        assertEquals(2, result);
1361    }
1362
1363    @Test
1364    public void testGetCount_6() throws Exception {
1365        Trie<String> fixture = new Trie<String>();
1366        fixture.train(sequence, 3);
1367        List<String> subSequence = new ArrayList<String>();
1368
1369        int result = fixture.getCount(subSequence, "x");
1370
1371        assertEquals(0, result);
1372    }
1373
1374    @Test
1375    public void testGetFollowingSymbols_1() throws Exception {
1376        Trie<String> fixture = new Trie<String>();
1377        fixture.train(sequence, 3);
1378        List<String> subSequence = new ArrayList<String>();
1379        subSequence.add("a");
1380        Collection<String> expected = new ArrayList<String>();
1381        expected.add("b");
1382        expected.add("c");
1383        expected.add("d");
1384
1385        Collection<String> result = fixture.getFollowingSymbols(subSequence);
1386
1387        assertCollectionContent(expected, result);
1388    }
1389
1390    @Test
1391    public void testGetFollowingSymbols_2() throws Exception {
1392        Trie<String> fixture = new Trie<String>();
1393        fixture.train(sequence, 3);
1394        List<String> subSequence = new ArrayList<String>();
1395        subSequence.add("a");
1396        subSequence.add("b");
1397        subSequence.add("r");
1398
1399        Collection<String> result = fixture.getFollowingSymbols(subSequence);
1400
1401        assertEquals(0, result.size());
1402    }
1403
1404    @Test
1405    public void testGetFollowingSymbols_3() throws Exception {
1406        Trie<String> fixture = new Trie<String>();
1407        fixture.train(sequence, 3);
1408        List<String> subSequence = new ArrayList<String>();
1409        subSequence.add("x");
1410
1411        Collection<String> result = fixture.getFollowingSymbols(subSequence);
1412
1413        assertEquals(0, result.size());
1414    }
1415
1416    @Test
1417    public void testGetNumLeafAncestors_1() throws Exception {
1418        Trie<String> fixture = new Trie<String>();
1419        fixture.train(sequence, 3);
1420
1421        int result = fixture.getNumLeafAncestors();
1422
1423        assertEquals(7, result);
1424    }
1425
1426    @Test
1427    public void testGetNumLeafs_1() throws Exception {
1428        Trie<String> fixture = new Trie<String>();
1429        fixture.train(sequence, 3);
1430
1431        int result = fixture.getNumLeafs();
1432
1433        assertEquals(7, result);
1434    }
1435
1436    @Test
1437    public void testGetNumSymbols_1() throws Exception {
1438        Trie<String> fixture = new Trie<String>();
1439        fixture.train(sequence, 3);
1440
1441        int result = fixture.getNumSymbols();
1442
1443        assertEquals(5, result);
1444    }
1445
1446    @Test
1447    public void testTrain_1() throws Exception {
1448        Trie<String> fixture = new Trie<String>();
1449        int maxOrder = 3;
1450
1451        fixture.train(sequence, maxOrder);
1452
1453        // check if symbols are correct
1454        assertCollectionContent(symbols, fixture.getKnownSymbols());
1455
1456        // check if counters are correct and only the correct nodes exist
1457        TrieNode<String> root = fixture.find(new ArrayList<String>());
1458        TrieNode<String> root_a = root.getChild("a");
1459        TrieNode<String> root_a_a = root_a.getChild("a");
1460        TrieNode<String> root_a_b = root_a.getChild("b");
1461        TrieNode<String> root_a_b_a = root_a_b.getChild("a");
1462        TrieNode<String> root_a_b_b = root_a_b.getChild("b");
1463        TrieNode<String> root_a_b_c = root_a_b.getChild("c");
1464        TrieNode<String> root_a_b_d = root_a_b.getChild("d");
1465        TrieNode<String> root_a_b_r = root_a_b.getChild("r");
1466        TrieNode<String> root_a_c = root_a.getChild("c");
1467        TrieNode<String> root_a_c_a = root_a_c.getChild("a");
1468        TrieNode<String> root_a_c_b = root_a_c.getChild("b");
1469        TrieNode<String> root_a_c_c = root_a_c.getChild("c");
1470        TrieNode<String> root_a_c_d = root_a_c.getChild("d");
1471        TrieNode<String> root_a_c_r = root_a_c.getChild("r");
1472        TrieNode<String> root_a_d = root_a.getChild("d");
1473        TrieNode<String> root_a_d_a = root_a_d.getChild("a");
1474        TrieNode<String> root_a_d_b = root_a_d.getChild("b");
1475        TrieNode<String> root_a_d_c = root_a_d.getChild("c");
1476        TrieNode<String> root_a_d_d = root_a_d.getChild("d");
1477        TrieNode<String> root_a_d_r = root_a_d.getChild("r");
1478        TrieNode<String> root_a_r = root_a.getChild("r");
1479        TrieNode<String> root_b = root.getChild("b");
1480        TrieNode<String> root_b_a = root_b.getChild("a");
1481        TrieNode<String> root_b_b = root_b.getChild("b");
1482        TrieNode<String> root_b_c = root_b.getChild("c");
1483        TrieNode<String> root_b_d = root_b.getChild("d");
1484        TrieNode<String> root_b_r = root_b.getChild("r");
1485        TrieNode<String> root_b_r_a = root_b_r.getChild("a");
1486        TrieNode<String> root_b_r_b = root_b_r.getChild("b");
1487        TrieNode<String> root_b_r_c = root_b_r.getChild("c");
1488        TrieNode<String> root_b_r_d = root_b_r.getChild("d");
1489        TrieNode<String> root_b_r_r = root_b_r.getChild("r");
1490        TrieNode<String> root_c = root.getChild("c");
1491        TrieNode<String> root_c_a = root_c.getChild("a");
1492        TrieNode<String> root_c_a_a = root_c_a.getChild("a");
1493        TrieNode<String> root_c_a_b = root_c_a.getChild("b");
1494        TrieNode<String> root_c_a_c = root_c_a.getChild("c");
1495        TrieNode<String> root_c_a_d = root_c_a.getChild("d");
1496        TrieNode<String> root_c_a_r = root_c_a.getChild("r");
1497        TrieNode<String> root_c_b = root_c.getChild("b");
1498        TrieNode<String> root_c_c = root_c.getChild("c");
1499        TrieNode<String> root_c_d = root_c.getChild("d");
1500        TrieNode<String> root_c_r = root_c.getChild("r");
1501        TrieNode<String> root_d = root.getChild("d");
1502        TrieNode<String> root_d_a = root_d.getChild("a");
1503        TrieNode<String> root_d_a_a = root_d_a.getChild("a");
1504        TrieNode<String> root_d_a_b = root_d_a.getChild("b");
1505        TrieNode<String> root_d_a_c = root_d_a.getChild("c");
1506        TrieNode<String> root_d_a_d = root_d_a.getChild("d");
1507        TrieNode<String> root_d_a_r = root_d_a.getChild("r");
1508        TrieNode<String> root_d_b = root_d.getChild("b");
1509        TrieNode<String> root_d_c = root_d.getChild("c");
1510        TrieNode<String> root_d_d = root_d.getChild("d");
1511        TrieNode<String> root_d_r = root_d.getChild("r");
1512        TrieNode<String> root_r = root.getChild("r");
1513        TrieNode<String> root_r_a = root_r.getChild("a");
1514        TrieNode<String> root_r_a_a = root_r_a.getChild("a");
1515        TrieNode<String> root_r_a_b = root_r_a.getChild("b");
1516        TrieNode<String> root_r_a_c = root_r_a.getChild("c");
1517        TrieNode<String> root_r_a_d = root_r_a.getChild("d");
1518        TrieNode<String> root_r_a_r = root_r_a.getChild("r");
1519        TrieNode<String> root_r_b = root_r.getChild("b");
1520        TrieNode<String> root_r_c = root_r.getChild("c");
1521        TrieNode<String> root_r_d = root_r.getChild("d");
1522        TrieNode<String> root_r_r = root_r.getChild("r");
1523
1524        assertEquals(5, root_a.getCount());
1525        assertNull(root_a_a);
1526        assertEquals(2, root_a_b.getCount());
1527        assertNull(root_a_b_a);
1528        assertNull(root_a_b_b);
1529        assertNull(root_a_b_c);
1530        assertNull(root_a_b_d);
1531        assertEquals(2, root_a_b_r.getCount());
1532        assertEquals(1, root_a_c.getCount());
1533        assertEquals(1, root_a_c_a.getCount());
1534        assertNull(root_a_c_b);
1535        assertNull(root_a_c_c);
1536        assertNull(root_a_c_d);
1537        assertNull(root_a_c_r);
1538        assertEquals(1, root_a_d.getCount());
1539        assertEquals(1, root_a_d_a.getCount());
1540        assertNull(root_a_d_b);
1541        assertNull(root_a_d_c);
1542        assertNull(root_a_d_d);
1543        assertNull(root_a_d_r);
1544        assertNull(root_a_r);
1545
1546        assertEquals(2, root_b.getCount());
1547        assertNull(root_b_a);
1548        assertNull(root_b_b);
1549        assertNull(root_b_c);
1550        assertNull(root_b_d);
1551        assertEquals(2, root_b_r.getCount());
1552        assertEquals(2, root_b_r_a.getCount());
1553        assertNull(root_b_r_b);
1554        assertNull(root_b_r_c);
1555        assertNull(root_b_r_d);
1556        assertNull(root_b_r_r);
1557
1558        assertEquals(1, root_c.getCount());
1559        assertEquals(1, root_c_a.getCount());
1560        assertNull(root_c_a_a);
1561        assertNull(root_c_a_b);
1562        assertNull(root_c_a_c);
1563        assertEquals(1, root_c_a_d.getCount());
1564        assertNull(root_c_a_r);
1565        assertNull(root_c_b);
1566        assertNull(root_c_c);
1567        assertNull(root_c_d);
1568        assertNull(root_c_r);
1569
1570        assertEquals(1, root_d.getCount());
1571        assertEquals(1, root_d_a.getCount());
1572        assertNull(root_d_a_a);
1573        assertEquals(1, root_d_a_b.getCount());
1574        assertNull(root_d_a_c);
1575        assertNull(root_d_a_d);
1576        assertNull(root_d_a_r);
1577        assertNull(root_d_b);
1578        assertNull(root_d_c);
1579        assertNull(root_d_d);
1580        assertNull(root_d_r);
1581
1582        assertEquals(2, root_r.getCount());
1583        assertEquals(2, root_r_a.getCount());
1584        assertNull(root_r_a_a);
1585        assertNull(root_r_a_b);
1586        assertEquals(1, root_r_a_c.getCount());
1587        assertNull(root_r_a_d);
1588        assertNull(root_r_a_r);
1589        assertNull(root_r_b);
1590        assertNull(root_r_c);
1591        assertNull(root_r_d);
1592        assertNull(root_r_r);
1593
1594        // check if leafs are really leafs
1595        assertTrue(root_a_b_r.isLeaf());
1596        assertTrue(root_a_c_a.isLeaf());
1597        assertTrue(root_a_d_a.isLeaf());
1598        assertTrue(root_b_r_a.isLeaf());
1599        assertTrue(root_c_a_d.isLeaf());
1600        assertTrue(root_d_a_b.isLeaf());
1601        assertTrue(root_r_a_c.isLeaf());
1602    }
1603
1604    @Test
1605    public void testTrain_2() throws Exception {
1606        Trie<String> fixture = new Trie<String>();
1607        int maxOrder = 0;
1608
1609        fixture.train(sequence, maxOrder);
1610
1611        assertTrue(fixture.getKnownSymbols().isEmpty());
1612    }
1613
1614    @Test
1615    public void testTrain_3() throws Exception {
1616        Trie<Object> fixture = new Trie<Object>();
1617        List<Object> sequence = new ArrayList<Object>();
1618        int maxOrder = 1;
1619
1620        fixture.train(sequence, maxOrder);
1621
1622        assertTrue(fixture.getKnownSymbols().isEmpty());
1623    }
1624
1625    @Test
1626    public void testTrain_4() throws Exception {
1627        Trie<String> fixture = new Trie<String>();
1628        List<String> sequence = new ArrayList<String>();
1629        sequence.add("a");
1630        sequence.add("b");
1631        int maxOrder = 3;
1632
1633        fixture.train(sequence, maxOrder);
1634
1635        assertCollectionContent(sequence, fixture.getKnownSymbols());
1636        TrieNode<String> root = fixture.find(new ArrayList<String>());
1637        TrieNode<String> root_a = root.getChild("a");
1638        TrieNode<String> root_a_a = root_a.getChild("a");
1639        TrieNode<String> root_a_b = root_a.getChild("b");
1640        TrieNode<String> root_b = root.getChild("b");
1641        TrieNode<String> root_b_a = root_b.getChild("a");
1642        TrieNode<String> root_b_b = root_b.getChild("b");
1643
1644        assertEquals(1, root_a.getCount());
1645        assertNull(root_a_a);
1646        assertEquals(1, root_a_b.getCount());
1647        assertEquals(1, root_b.getCount());
1648        assertNull(root_b_a);
1649        assertNull(root_b_b);
1650
1651        assertTrue(root_a_b.isLeaf());
1652        assertTrue(root_b.isLeaf());
1653    }
1654
1655    @Test
1656    public void testEdgeEdge_1() throws Exception {
1657        Edge result = new Edge();
1658
1659        assertNotNull(result);
1660    }
1661
1662    @Test
1663    public void testTrieVertexTrieVertex_1() throws Exception {
1664        String id = "idString";
1665
1666        TrieVertex result = new TrieVertex(id);
1667
1668        assertNotNull(result);
1669    }
1670
1671    @Test
1672    public void testTrieVertexToString_1() throws Exception {
1673        String id = "idString";
1674        TrieVertex fixture = new TrieVertex(id);
1675
1676        String result = fixture.toString();
1677
1678        assertEquals(id, result);
1679    }
1680
1681    @Test
1682    public void testEquals_1() throws Exception {
1683        Trie<String> trieOther = new Trie<String>();
1684        Trie<String> fixture = new Trie<String>();
1685
1686        boolean result = fixture.equals(trieOther);
1687
1688        assertEquals(true, result);
1689    }
1690
1691    @Test
1692    public void testEquals_2() throws Exception {
1693        Trie<String> trieOther = new Trie<String>();
1694        trieOther.train(sequence, 2);
1695        Trie<String> fixture = new Trie<String>();
1696        fixture.train(sequence, 2);
1697
1698        boolean result = fixture.equals(trieOther);
1699
1700        assertEquals(true, result);
1701    }
1702
1703    @Test
1704    public void testEquals_3() throws Exception {
1705        Trie<String> trieOther = new Trie<String>();
1706        trieOther.train(sequence, 2);
1707        Trie<String> fixture = new Trie<String>();
1708        fixture.train(sequence, 3);
1709
1710        boolean result = fixture.equals(trieOther);
1711
1712        assertEquals(false, result);
1713    }
1714
1715    @Test
1716    public void testEquals_4() throws Exception {
1717        Trie<String> trieOther = new Trie<String>();
1718        Trie<String> fixture = new Trie<String>();
1719        fixture.train(sequence, 2);
1720
1721        boolean result = fixture.equals(trieOther);
1722
1723        assertEquals(false, result);
1724    }
1725
1726    @Test
1727    public void testEquals_5() throws Exception {
1728        Trie<String> trieOther = new Trie<String>();
1729        trieOther.train(sequence, 2);
1730        Trie<String> fixture = new Trie<String>();
1731
1732        boolean result = fixture.equals(trieOther);
1733
1734        assertEquals(false, result);
1735    }
1736
1737    @Test
1738    public void testEquals_6() throws Exception {
1739        Trie<String> fixture = new Trie<String>();
1740        fixture.train(sequence, 2);
1741
1742        boolean result = fixture.equals(fixture);
1743
1744        assertEquals(true, result);
1745    }
1746
1747    @Test
1748    public void testEquals_7() throws Exception {
1749        Trie<String> fixture = new Trie<String>();
1750        fixture.train(sequence, 2);
1751
1752        boolean result = fixture.equals(null);
1753
1754        assertEquals(false, result);
1755    }
1756
1757    @Before
1758    public void setUp() throws Exception {
1759        sequence = new ArrayList<String>();
1760        sequence.add("a");
1761        sequence.add("b");
1762        sequence.add("r");
1763        sequence.add("a");
1764        sequence.add("c");
1765        sequence.add("a");
1766        sequence.add("d");
1767        sequence.add("a");
1768        sequence.add("b");
1769        sequence.add("r");
1770        sequence.add("a");
1771
1772        symbols = new HashSet<String>();
1773        symbols.add("a");
1774        symbols.add("b");
1775        symbols.add("c");
1776        symbols.add("d");
1777        symbols.add("r");
1778    }
1779
1780    public static void main(String[] args) {
1781        new org.junit.runner.JUnitCore().run(TrieTest.class);
1782    }
1783
1784}
Note: See TracBrowser for help on using the repository browser.