Context Navigation

TrieTest.java @ 1110

Last change on this file since 1110 was 1110, checked in by pharms, 11 years ago
allowed to search for all sub sequences with a dedicated number of occurrence
Property svn:mime-type set to `text/plain`
File size: 37.2 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 testGetSequencesWithMostOccurrences_1() throws Exception {
267	Trie<String> fixture = new Trie<String>();
268	fixture.train(sequence, 3);
269
270	// get all sequences with a minimal length of one that occur most often
271	Collection<List<String>> result = fixture.getSequencesWithOccurrenceCount(1, 0);
272
273	assertEquals(1, result.size());
274
275	List<String> expected = new ArrayList<String>();
276	expected.add("a");
277
278	ListAssert.assertEquals(expected, result.iterator().next());
279	}
280
281	@Test
282	public void testGetSequencesWithMostOccurrences_2() throws Exception {
283	Trie<String> fixture = new Trie<String>();
284	fixture.train(sequence, 3);
285
286	// get all sequences with a minimal length of one that occur exactly once
287	Collection<List<String>> result = fixture.getSequencesWithOccurrenceCount(1, 1);
288
289	assertEquals(11, result.size());
290
291	List<String> expected = new ArrayList<String>();
292	expected.add("r");
293	expected.add("a");
294	expected.add("c");
295	// rac
296	ListAssert.assertContains((List<List<String>>) result, expected);
297
298	expected.clear();
299	expected.add("a");
300	expected.add("c");
301	// ac
302	ListAssert.assertContains((List<List<String>>) result, expected);
303
304	expected.add("a");
305	// aca
306	ListAssert.assertContains((List<List<String>>) result, expected);
307
308	expected.clear();
309	expected.add("c");
310	// c
311	ListAssert.assertContains((List<List<String>>) result, expected);
312
313	expected.add("a");
314	// ca
315	ListAssert.assertContains((List<List<String>>) result, expected);
316
317	expected.add("d");
318	// cad
319	ListAssert.assertContains((List<List<String>>) result, expected);
320
321	expected.clear();
322	expected.add("a");
323	expected.add("d");
324	// ad
325	ListAssert.assertContains((List<List<String>>) result, expected);
326
327	expected.add("a");
328	// ada
329	ListAssert.assertContains((List<List<String>>) result, expected);
330
331	expected.clear();
332	expected.add("d");
333	// d
334	ListAssert.assertContains((List<List<String>>) result, expected);
335
336	expected.add("a");
337	// da
338	ListAssert.assertContains((List<List<String>>) result, expected);
339
340	expected.add("b");
341	// dab
342	ListAssert.assertContains((List<List<String>>) result, expected);
343	}
344
345	@Test
346	public void testGetSequencesWithMostOccurrences_3() throws Exception {
347	Trie<String> fixture = new Trie<String>();
348	fixture.train(sequence, 3);
349
350	// get all sequences with a minimal length of one that occur exactly twice
351	Collection<List<String>> result = fixture.getSequencesWithOccurrenceCount(1, 2);
352
353	assertEquals(7, result.size());
354
355	List<String> expected = new ArrayList<String>();
356	expected.add("a");
357	expected.add("b");
358	// ab
359	ListAssert.assertContains((List<List<String>>) result, expected);
360
361	expected.add("r");
362	// abr
363	ListAssert.assertContains((List<List<String>>) result, expected);
364
365	expected.clear();
366	expected.add("b");
367	// b
368	ListAssert.assertContains((List<List<String>>) result, expected);
369
370	expected.add("r");
371	// br
372	ListAssert.assertContains((List<List<String>>) result, expected);
373
374	expected.add("a");
375	// bra
376	ListAssert.assertContains((List<List<String>>) result, expected);
377
378	expected.clear();
379	expected.add("r");
380	// r
381	ListAssert.assertContains((List<List<String>>) result, expected);
382
383	expected.add("a");
384	// ra
385	ListAssert.assertContains((List<List<String>>) result, expected);
386	}
387
388	@Test
389	public void testGetSequencesWithMostOccurrences_4() throws Exception {
390	Trie<String> fixture = new Trie<String>();
391	fixture.train(sequence, 3);
392
393	// get all sequences with a minimal length of one that occur exactly three times
394	Collection<List<String>> result = fixture.getSequencesWithOccurrenceCount(1, 3);
395
396	assertEquals(0, result.size());
397	}
398
399	@Test
400	public void testGetSequencesWithMostOccurrences_5() throws Exception {
401	Trie<String> fixture = new Trie<String>();
402	fixture.train(sequence, 3);
403
404	// get all sequences with a minimal length of one that occur exactly four times
405	Collection<List<String>> result = fixture.getSequencesWithOccurrenceCount(1, 4);
406
407	assertEquals(0, result.size());
408	}
409
410	@Test
411	public void testGetSequencesWithMostOccurrences_6() throws Exception {
412	Trie<String> fixture = new Trie<String>();
413	fixture.train(sequence, 3);
414
415	// get all sequences with a minimal length of one that occur exactly five times
416	Collection<List<String>> result = fixture.getSequencesWithOccurrenceCount(1, 5);
417
418	assertEquals(1, result.size());
419
420	List<String> expected = new ArrayList<String>();
421	expected.add("a");
422	ListAssert.assertContains((List<List<String>>) result, expected);
423	}
424
425	@Test
426	public void testGetSequencesWithMostOccurrences_7() throws Exception {
427	Trie<String> fixture = new Trie<String>();
428	fixture.train(sequence, 3);
429
430	// get all sequences with a minimal length of two that occur most often
431	Collection<List<String>> result = fixture.getSequencesWithOccurrenceCount(2, 0);
432
433	assertEquals(5, result.size());
434
435	List<String> expected = new ArrayList<String>();
436	expected.add("a");
437	expected.add("b");
438	ListAssert.assertContains((List<List<String>>) result, expected);
439
440	expected.add("r");
441	ListAssert.assertContains((List<List<String>>) result, expected);
442
443	expected.clear();
444	expected.add("b");
445	expected.add("r");
446	ListAssert.assertContains((List<List<String>>) result, expected);
447
448	expected.add("a");
449	ListAssert.assertContains((List<List<String>>) result, expected);
450
451	expected.clear();
452	expected.add("r");
453	expected.add("a");
454	ListAssert.assertContains((List<List<String>>) result, expected);
455	}
456
457	@Test
458	public void testGetSequencesWithMostOccurrences_8() throws Exception {
459	Trie<String> fixture = new Trie<String>();
460	fixture.train(sequence, 3);
461
462	// get all sequences with a minimal length of two that occur exactly once
463	Collection<List<String>> result = fixture.getSequencesWithOccurrenceCount(2, 1);
464
465	assertEquals(9, result.size());
466
467	List<String> expected = new ArrayList<String>();
468	expected.add("r");
469	expected.add("a");
470	expected.add("c");
471	// rac
472	ListAssert.assertContains((List<List<String>>) result, expected);
473
474	expected.clear();
475	expected.add("a");
476	expected.add("c");
477	// ac
478	ListAssert.assertContains((List<List<String>>) result, expected);
479
480	expected.add("a");
481	// aca
482	ListAssert.assertContains((List<List<String>>) result, expected);
483
484	expected.clear();
485	expected.add("c");
486	expected.add("a");
487	// ca
488	ListAssert.assertContains((List<List<String>>) result, expected);
489
490	expected.add("d");
491	// cad
492	ListAssert.assertContains((List<List<String>>) result, expected);
493
494	expected.clear();
495	expected.add("a");
496	expected.add("d");
497	// ad
498	ListAssert.assertContains((List<List<String>>) result, expected);
499
500	expected.add("a");
501	// ada
502	ListAssert.assertContains((List<List<String>>) result, expected);
503
504	expected.clear();
505	expected.add("d");
506	expected.add("a");
507	// da
508	ListAssert.assertContains((List<List<String>>) result, expected);
509
510	expected.add("b");
511	// dab
512	ListAssert.assertContains((List<List<String>>) result, expected);
513	}
514
515	@Test
516	public void testGetSequencesWithMostOccurrences_9() throws Exception {
517	Trie<String> fixture = new Trie<String>();
518	fixture.train(sequence, 3);
519
520	// get all sequences with a minimal length of two that occur exactly twice
521	Collection<List<String>> result = fixture.getSequencesWithOccurrenceCount(2, 2);
522
523	assertEquals(5, result.size());
524
525	List<String> expected = new ArrayList<String>();
526	expected.add("a");
527	expected.add("b");
528	// ab
529	ListAssert.assertContains((List<List<String>>) result, expected);
530
531	expected.add("r");
532	// abr
533	ListAssert.assertContains((List<List<String>>) result, expected);
534
535	expected.clear();
536	expected.add("b");
537	expected.add("r");
538	// br
539	ListAssert.assertContains((List<List<String>>) result, expected);
540
541	expected.add("a");
542	// bra
543	ListAssert.assertContains((List<List<String>>) result, expected);
544
545	expected.clear();
546	expected.add("r");
547	expected.add("a");
548	// ra
549	ListAssert.assertContains((List<List<String>>) result, expected);
550	}
551
552	@Test
553	public void testGetSequencesWithMostOccurrences_10() throws Exception {
554	Trie<String> fixture = new Trie<String>();
555	fixture.train(sequence, 3);
556
557	// get all sequences with a minimal length of two that occur exactly three times
558	Collection<List<String>> result = fixture.getSequencesWithOccurrenceCount(2, 3);
559
560	assertEquals(0, result.size());
561	}
562
563	@Test
564	public void testGetSequencesWithMostOccurrences_11() throws Exception {
565	Trie<String> fixture = new Trie<String>();
566	fixture.train(sequence, 3);
567
568	// get all sequences with a minimal length of three that occur most often
569	Collection<List<String>> result = fixture.getSequencesWithOccurrenceCount(3, 0);
570
571	assertEquals(2, result.size());
572
573	List<String> expected = new ArrayList<String>();
574	expected.add("a");
575	expected.add("b");
576	expected.add("r");
577	ListAssert.assertContains((List<List<String>>) result, expected);
578
579	expected.clear();
580	expected.add("b");
581	expected.add("r");
582	expected.add("a");
583	ListAssert.assertContains((List<List<String>>) result, expected);
584	}
585
586	@Test
587	public void testGetSequencesWithMostOccurrences_12() throws Exception {
588	Trie<String> fixture = new Trie<String>();
589	fixture.train(sequence, 3);
590
591	// get all sequences with a minimal length of three that occur exactly once
592	Collection<List<String>> result = fixture.getSequencesWithOccurrenceCount(3, 1);
593
594	assertEquals(5, result.size());
595
596	List<String> expected = new ArrayList<String>();
597	expected.add("r");
598	expected.add("a");
599	expected.add("c");
600	// rac
601	ListAssert.assertContains((List<List<String>>) result, expected);
602
603	expected.clear();
604	expected.add("a");
605	expected.add("c");
606	expected.add("a");
607	// aca
608	ListAssert.assertContains((List<List<String>>) result, expected);
609
610	expected.clear();
611	expected.add("c");
612	expected.add("a");
613	expected.add("d");
614	// cad
615	ListAssert.assertContains((List<List<String>>) result, expected);
616
617	expected.clear();
618	expected.add("a");
619	expected.add("d");
620	expected.add("a");
621	// ada
622	ListAssert.assertContains((List<List<String>>) result, expected);
623
624	expected.clear();
625	expected.add("d");
626	expected.add("a");
627	expected.add("b");
628	// dab
629	ListAssert.assertContains((List<List<String>>) result, expected);
630	}
631
632	@Test
633	public void testGetSequencesWithMostOccurrences_13() throws Exception {
634	Trie<String> fixture = new Trie<String>();
635	fixture.train(sequence, 3);
636
637	// get all sequences with a minimal length of four that occur most often
638	Collection<List<String>> result = fixture.getSequencesWithOccurrenceCount(4, 0);
639
640	// none of these exist, as the tree is only trained with sequences of length 3
641	assertEquals(0, result.size());
642	}
643
644	@Test
645	public void testGetSequencesWithMostOccurrences_14() throws Exception {
646	Trie<String> fixture = new Trie<String>();
647	fixture.train(sequence, 3);
648
649	// get all sequences with a minimal length of four that occur exactly once
650	Collection<List<String>> result = fixture.getSequencesWithOccurrenceCount(4, 1);
651
652	// none of these exist, as the tree is only trained with sequences of length 3
653	assertEquals(0, result.size());
654	}
655
656	@Test
657	public void testGetCount_1() throws Exception {
658	Trie<String> fixture = new Trie<String>();
659	fixture.train(sequence, 3);
660	List<String> subSequence = new ArrayList<String>();
661	subSequence.add("a");
662
663	int result = fixture.getCount(subSequence);
664
665	assertEquals(5, result);
666	}
667
668	@Test
669	public void testGetCount_2() throws Exception {
670	Trie<String> fixture = new Trie<String>();
671	fixture.train(sequence, 3);
672	List<String> subSequence = new ArrayList<String>();
673	subSequence.add("a");
674	subSequence.add("b");
675
676	int result = fixture.getCount(subSequence);
677
678	assertEquals(2, result);
679	}
680
681	@Test
682	public void testGetCount_3() throws Exception {
683	Trie<String> fixture = new Trie<String>();
684	fixture.train(sequence, 3);
685	List<String> subSequence = new ArrayList<String>();
686	subSequence.add("x");
687
688	int result = fixture.getCount(subSequence);
689
690	assertEquals(0, result);
691	}
692
693	@Test
694	public void testGetCount_4() throws Exception {
695	Trie<String> fixture = new Trie<String>();
696	fixture.train(sequence, 3);
697	List<String> subSequence = new ArrayList<String>();
698
699	int result = fixture.getCount(subSequence, "a");
700
701	assertEquals(5, result);
702	}
703
704	@Test
705	public void testGetCount_5() throws Exception {
706	Trie<String> fixture = new Trie<String>();
707	fixture.train(sequence, 3);
708	List<String> subSequence = new ArrayList<String>();
709	subSequence.add("a");
710	subSequence.add("b");
711
712	int result = fixture.getCount(subSequence, "r");
713
714	assertEquals(2, result);
715	}
716
717	@Test
718	public void testGetCount_6() throws Exception {
719	Trie<String> fixture = new Trie<String>();
720	fixture.train(sequence, 3);
721	List<String> subSequence = new ArrayList<String>();
722
723	int result = fixture.getCount(subSequence, "x");
724
725	assertEquals(0, result);
726	}
727
728	@Test
729	public void testGetFollowingSymbols_1() throws Exception {
730	Trie<String> fixture = new Trie<String>();
731	fixture.train(sequence, 3);
732	List<String> subSequence = new ArrayList<String>();
733	subSequence.add("a");
734	Collection<String> expected = new ArrayList<String>();
735	expected.add("b");
736	expected.add("c");
737	expected.add("d");
738
739	Collection<String> result = fixture.getFollowingSymbols(subSequence);
740
741	assertCollectionContent(expected, result);
742	}
743
744	@Test
745	public void testGetFollowingSymbols_2() throws Exception {
746	Trie<String> fixture = new Trie<String>();
747	fixture.train(sequence, 3);
748	List<String> subSequence = new ArrayList<String>();
749	subSequence.add("a");
750	subSequence.add("b");
751	subSequence.add("r");
752
753	Collection<String> result = fixture.getFollowingSymbols(subSequence);
754
755	assertEquals(0, result.size());
756	}
757
758	@Test
759	public void testGetFollowingSymbols_3() throws Exception {
760	Trie<String> fixture = new Trie<String>();
761	fixture.train(sequence, 3);
762	List<String> subSequence = new ArrayList<String>();
763	subSequence.add("x");
764
765	Collection<String> result = fixture.getFollowingSymbols(subSequence);
766
767	assertEquals(0, result.size());
768	}
769
770	@Test
771	public void testGetNumLeafAncestors_1() throws Exception {
772	Trie<String> fixture = new Trie<String>();
773	fixture.train(sequence, 3);
774
775	int result = fixture.getNumLeafAncestors();
776
777	assertEquals(7, result);
778	}
779
780	@Test
781	public void testGetNumLeafs_1() throws Exception {
782	Trie<String> fixture = new Trie<String>();
783	fixture.train(sequence, 3);
784
785	int result = fixture.getNumLeafs();
786
787	assertEquals(7, result);
788	}
789
790	@Test
791	public void testGetNumSymbols_1() throws Exception {
792	Trie<String> fixture = new Trie<String>();
793	fixture.train(sequence, 3);
794
795	int result = fixture.getNumSymbols();
796
797	assertEquals(5, result);
798	}
799
800	@Test
801	public void testTrain_1() throws Exception {
802	Trie<String> fixture = new Trie<String>();
803	int maxOrder = 3;
804
805	fixture.train(sequence, maxOrder);
806
807	// check if symbols are correct
808	assertCollectionContent(symbols, fixture.getKnownSymbols());
809
810	// check if counters are correct and only the correct nodes exist
811	TrieNode<String> root = fixture.find(new ArrayList<String>());
812	TrieNode<String> root_a = root.getChild("a");
813	TrieNode<String> root_a_a = root_a.getChild("a");
814	TrieNode<String> root_a_b = root_a.getChild("b");
815	TrieNode<String> root_a_b_a = root_a_b.getChild("a");
816	TrieNode<String> root_a_b_b = root_a_b.getChild("b");
817	TrieNode<String> root_a_b_c = root_a_b.getChild("c");
818	TrieNode<String> root_a_b_d = root_a_b.getChild("d");
819	TrieNode<String> root_a_b_r = root_a_b.getChild("r");
820	TrieNode<String> root_a_c = root_a.getChild("c");
821	TrieNode<String> root_a_c_a = root_a_c.getChild("a");
822	TrieNode<String> root_a_c_b = root_a_c.getChild("b");
823	TrieNode<String> root_a_c_c = root_a_c.getChild("c");
824	TrieNode<String> root_a_c_d = root_a_c.getChild("d");
825	TrieNode<String> root_a_c_r = root_a_c.getChild("r");
826	TrieNode<String> root_a_d = root_a.getChild("d");
827	TrieNode<String> root_a_d_a = root_a_d.getChild("a");
828	TrieNode<String> root_a_d_b = root_a_d.getChild("b");
829	TrieNode<String> root_a_d_c = root_a_d.getChild("c");
830	TrieNode<String> root_a_d_d = root_a_d.getChild("d");
831	TrieNode<String> root_a_d_r = root_a_d.getChild("r");
832	TrieNode<String> root_a_r = root_a.getChild("r");
833	TrieNode<String> root_b = root.getChild("b");
834	TrieNode<String> root_b_a = root_b.getChild("a");
835	TrieNode<String> root_b_b = root_b.getChild("b");
836	TrieNode<String> root_b_c = root_b.getChild("c");
837	TrieNode<String> root_b_d = root_b.getChild("d");
838	TrieNode<String> root_b_r = root_b.getChild("r");
839	TrieNode<String> root_b_r_a = root_b_r.getChild("a");
840	TrieNode<String> root_b_r_b = root_b_r.getChild("b");
841	TrieNode<String> root_b_r_c = root_b_r.getChild("c");
842	TrieNode<String> root_b_r_d = root_b_r.getChild("d");
843	TrieNode<String> root_b_r_r = root_b_r.getChild("r");
844	TrieNode<String> root_c = root.getChild("c");
845	TrieNode<String> root_c_a = root_c.getChild("a");
846	TrieNode<String> root_c_a_a = root_c_a.getChild("a");
847	TrieNode<String> root_c_a_b = root_c_a.getChild("b");
848	TrieNode<String> root_c_a_c = root_c_a.getChild("c");
849	TrieNode<String> root_c_a_d = root_c_a.getChild("d");
850	TrieNode<String> root_c_a_r = root_c_a.getChild("r");
851	TrieNode<String> root_c_b = root_c.getChild("b");
852	TrieNode<String> root_c_c = root_c.getChild("c");
853	TrieNode<String> root_c_d = root_c.getChild("d");
854	TrieNode<String> root_c_r = root_c.getChild("r");
855	TrieNode<String> root_d = root.getChild("d");
856	TrieNode<String> root_d_a = root_d.getChild("a");
857	TrieNode<String> root_d_a_a = root_d_a.getChild("a");
858	TrieNode<String> root_d_a_b = root_d_a.getChild("b");
859	TrieNode<String> root_d_a_c = root_d_a.getChild("c");
860	TrieNode<String> root_d_a_d = root_d_a.getChild("d");
861	TrieNode<String> root_d_a_r = root_d_a.getChild("r");
862	TrieNode<String> root_d_b = root_d.getChild("b");
863	TrieNode<String> root_d_c = root_d.getChild("c");
864	TrieNode<String> root_d_d = root_d.getChild("d");
865	TrieNode<String> root_d_r = root_d.getChild("r");
866	TrieNode<String> root_r = root.getChild("r");
867	TrieNode<String> root_r_a = root_r.getChild("a");
868	TrieNode<String> root_r_a_a = root_r_a.getChild("a");
869	TrieNode<String> root_r_a_b = root_r_a.getChild("b");
870	TrieNode<String> root_r_a_c = root_r_a.getChild("c");
871	TrieNode<String> root_r_a_d = root_r_a.getChild("d");
872	TrieNode<String> root_r_a_r = root_r_a.getChild("r");
873	TrieNode<String> root_r_b = root_r.getChild("b");
874	TrieNode<String> root_r_c = root_r.getChild("c");
875	TrieNode<String> root_r_d = root_r.getChild("d");
876	TrieNode<String> root_r_r = root_r.getChild("r");
877
878	assertEquals(5, root_a.getCount());
879	assertNull(root_a_a);
880	assertEquals(2, root_a_b.getCount());
881	assertNull(root_a_b_a);
882	assertNull(root_a_b_b);
883	assertNull(root_a_b_c);
884	assertNull(root_a_b_d);
885	assertEquals(2, root_a_b_r.getCount());
886	assertEquals(1, root_a_c.getCount());
887	assertEquals(1, root_a_c_a.getCount());
888	assertNull(root_a_c_b);
889	assertNull(root_a_c_c);
890	assertNull(root_a_c_d);
891	assertNull(root_a_c_r);
892	assertEquals(1, root_a_d.getCount());
893	assertEquals(1, root_a_d_a.getCount());
894	assertNull(root_a_d_b);
895	assertNull(root_a_d_c);
896	assertNull(root_a_d_d);
897	assertNull(root_a_d_r);
898	assertNull(root_a_r);
899
900	assertEquals(2, root_b.getCount());
901	assertNull(root_b_a);
902	assertNull(root_b_b);
903	assertNull(root_b_c);
904	assertNull(root_b_d);
905	assertEquals(2, root_b_r.getCount());
906	assertEquals(2, root_b_r_a.getCount());
907	assertNull(root_b_r_b);
908	assertNull(root_b_r_c);
909	assertNull(root_b_r_d);
910	assertNull(root_b_r_r);
911
912	assertEquals(1, root_c.getCount());
913	assertEquals(1, root_c_a.getCount());
914	assertNull(root_c_a_a);
915	assertNull(root_c_a_b);
916	assertNull(root_c_a_c);
917	assertEquals(1, root_c_a_d.getCount());
918	assertNull(root_c_a_r);
919	assertNull(root_c_b);
920	assertNull(root_c_c);
921	assertNull(root_c_d);
922	assertNull(root_c_r);
923
924	assertEquals(1, root_d.getCount());
925	assertEquals(1, root_d_a.getCount());
926	assertNull(root_d_a_a);
927	assertEquals(1, root_d_a_b.getCount());
928	assertNull(root_d_a_c);
929	assertNull(root_d_a_d);
930	assertNull(root_d_a_r);
931	assertNull(root_d_b);
932	assertNull(root_d_c);
933	assertNull(root_d_d);
934	assertNull(root_d_r);
935
936	assertEquals(2, root_r.getCount());
937	assertEquals(2, root_r_a.getCount());
938	assertNull(root_r_a_a);
939	assertNull(root_r_a_b);
940	assertEquals(1, root_r_a_c.getCount());
941	assertNull(root_r_a_d);
942	assertNull(root_r_a_r);
943	assertNull(root_r_b);
944	assertNull(root_r_c);
945	assertNull(root_r_d);
946	assertNull(root_r_r);
947
948	// check if leafs are really leafs
949	assertTrue(root_a_b_r.isLeaf());
950	assertTrue(root_a_c_a.isLeaf());
951	assertTrue(root_a_d_a.isLeaf());
952	assertTrue(root_b_r_a.isLeaf());
953	assertTrue(root_c_a_d.isLeaf());
954	assertTrue(root_d_a_b.isLeaf());
955	assertTrue(root_r_a_c.isLeaf());
956	}
957
958	@Test
959	public void testTrain_2() throws Exception {
960	Trie<String> fixture = new Trie<String>();
961	int maxOrder = 0;
962
963	fixture.train(sequence, maxOrder);
964
965	assertTrue(fixture.getKnownSymbols().isEmpty());
966	}
967
968	@Test
969	public void testTrain_3() throws Exception {
970	Trie<Object> fixture = new Trie<Object>();
971	List<Object> sequence = new ArrayList<Object>();
972	int maxOrder = 1;
973
974	fixture.train(sequence, maxOrder);
975
976	assertTrue(fixture.getKnownSymbols().isEmpty());
977	}
978
979	@Test
980	public void testTrain_4() throws Exception {
981	Trie<String> fixture = new Trie<String>();
982	List<String> sequence = new ArrayList<String>();
983	sequence.add("a");
984	sequence.add("b");
985	int maxOrder = 3;
986
987	fixture.train(sequence, maxOrder);
988
989	assertCollectionContent(sequence, fixture.getKnownSymbols());
990	TrieNode<String> root = fixture.find(new ArrayList<String>());
991	TrieNode<String> root_a = root.getChild("a");
992	TrieNode<String> root_a_a = root_a.getChild("a");
993	TrieNode<String> root_a_b = root_a.getChild("b");
994	TrieNode<String> root_b = root.getChild("b");
995	TrieNode<String> root_b_a = root_b.getChild("a");
996	TrieNode<String> root_b_b = root_b.getChild("b");
997
998	assertEquals(1, root_a.getCount());
999	assertNull(root_a_a);
1000	assertEquals(1, root_a_b.getCount());
1001	assertEquals(1, root_b.getCount());
1002	assertNull(root_b_a);
1003	assertNull(root_b_b);
1004
1005	assertTrue(root_a_b.isLeaf());
1006	assertTrue(root_b.isLeaf());
1007	}
1008
1009	@Test
1010	public void testEdgeEdge_1() throws Exception {
1011	Edge result = new Edge();
1012
1013	assertNotNull(result);
1014	}
1015
1016	@Test
1017	public void testTrieVertexTrieVertex_1() throws Exception {
1018	String id = "idString";
1019
1020	TrieVertex result = new TrieVertex(id);
1021
1022	assertNotNull(result);
1023	}
1024
1025	@Test
1026	public void testTrieVertexToString_1() throws Exception {
1027	String id = "idString";
1028	TrieVertex fixture = new TrieVertex(id);
1029
1030	String result = fixture.toString();
1031
1032	assertEquals(id, result);
1033	}
1034
1035	@Test
1036	public void testEquals_1() throws Exception {
1037	Trie<String> trieOther = new Trie<String>();
1038	Trie<String> fixture = new Trie<String>();
1039
1040	boolean result = fixture.equals(trieOther);
1041
1042	assertEquals(true, result);
1043	}
1044
1045	@Test
1046	public void testEquals_2() throws Exception {
1047	Trie<String> trieOther = new Trie<String>();
1048	trieOther.train(sequence, 2);
1049	Trie<String> fixture = new Trie<String>();
1050	fixture.train(sequence, 2);
1051
1052	boolean result = fixture.equals(trieOther);
1053
1054	assertEquals(true, result);
1055	}
1056
1057	@Test
1058	public void testEquals_3() throws Exception {
1059	Trie<String> trieOther = new Trie<String>();
1060	trieOther.train(sequence, 2);
1061	Trie<String> fixture = new Trie<String>();
1062	fixture.train(sequence, 3);
1063
1064	boolean result = fixture.equals(trieOther);
1065
1066	assertEquals(false, result);
1067	}
1068
1069	@Test
1070	public void testEquals_4() throws Exception {
1071	Trie<String> trieOther = new Trie<String>();
1072	Trie<String> fixture = new Trie<String>();
1073	fixture.train(sequence, 2);
1074
1075	boolean result = fixture.equals(trieOther);
1076
1077	assertEquals(false, result);
1078	}
1079
1080	@Test
1081	public void testEquals_5() throws Exception {
1082	Trie<String> trieOther = new Trie<String>();
1083	trieOther.train(sequence, 2);
1084	Trie<String> fixture = new Trie<String>();
1085
1086	boolean result = fixture.equals(trieOther);
1087
1088	assertEquals(false, result);
1089	}
1090
1091	@Test
1092	public void testEquals_6() throws Exception {
1093	Trie<String> fixture = new Trie<String>();
1094	fixture.train(sequence, 2);
1095
1096	boolean result = fixture.equals(fixture);
1097
1098	assertEquals(true, result);
1099	}
1100
1101	@Test
1102	public void testEquals_7() throws Exception {
1103	Trie<String> fixture = new Trie<String>();
1104	fixture.train(sequence, 2);
1105
1106	boolean result = fixture.equals(null);
1107
1108	assertEquals(false, result);
1109	}
1110
1111	@Before
1112	public void setUp() throws Exception {
1113	sequence = new ArrayList<String>();
1114	sequence.add("a");
1115	sequence.add("b");
1116	sequence.add("r");
1117	sequence.add("a");
1118	sequence.add("c");
1119	sequence.add("a");
1120	sequence.add("d");
1121	sequence.add("a");
1122	sequence.add("b");
1123	sequence.add("r");
1124	sequence.add("a");
1125
1126	symbols = new HashSet<String>();
1127	symbols.add("a");
1128	symbols.add("b");
1129	symbols.add("c");
1130	symbols.add("d");
1131	symbols.add("r");
1132	}
1133
1134	public static void main(String[] args) {
1135	new org.junit.runner.JUnitCore().run(TrieTest.class);
1136	}
1137	}

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

Download in other formats:

Original Format