Context Navigation

TrieTest.java @ 1282

Last change on this file since 1282 was 1282, checked in by pharms, 11 years ago
added support for symbol management strategy in tries, especially for storing them adapted comparator approach accordingly provided default implementation for symbol management strategies added, extended and improved java doc
Property svn:mime-type set to `text/plain`
File size: 72.4 KB

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

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

Download in other formats:

Original Format