Context Navigation

TrieTest.java @ 1118

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

Note: See TracBrowser for help on using the repository browser.

Download in other formats:

Original Format