Context Navigation

TrieTest.java @ 346

Last change on this file since 346 was 346, checked in by sherbold, 12 years ago
added JUnit test cases for public inner helper classes of de.ugoe.cs.eventbench.models.FirstOrderMarkovModel? and Trie
Property svn:mime-type set to `text/plain`
File size: 18.3 KB

Line
1	package de.ugoe.cs.eventbench.models;
2
3	import java.util.ArrayList;
4	import java.util.Collection;
5	import java.util.HashSet;
6	import java.util.List;
7
8	import junitx.framework.ListAssert;
9
10	import org.junit.*;
11
12	import de.ugoe.cs.eventbench.models.Trie.Edge;
13	import de.ugoe.cs.eventbench.models.Trie.TrieVertex;
14	import static org.junit.Assert.*;
15
16	/**
17	* The class <code>TrieTest</code> contains tests for the class <code>{@link Trie}</code>.
18	*
19	* @author Steffen Herbold
20	* @version 1.0
21	*/
22	public class TrieTest {
23
24	List<String> sequence;
25	Collection<String> symbols;
26
27	private static void assertCollectionContent(Collection<?> c1, Collection<?> c2) {
28	assertEquals(c1.size(), c2.size());
29	for( Object obj : c1 ) {
30	assertTrue(c2.contains(obj));
31	}
32	}
33
34	@Test
35	public void testTrie_1()
36	throws Exception {
37
38	Trie<String> result = new Trie<String>();
39
40	assertNotNull(result);
41	assertEquals(0, result.getNumLeafs());
42	assertEquals(0, result.getNumSymbols());
43	assertEquals(0, result.getNumLeafAncestors());
44	assertTrue(result.getKnownSymbols().isEmpty());
45	}
46
47	@Test
48	public void testAdd_1()
49	throws Exception {
50	Trie<String> fixture = new Trie<String>();
51	List<String> seq = new ArrayList<String>();
52	seq.add("a");
53	seq.add("b");
54
55	fixture.add(seq);
56
57	assertEquals(1, fixture.getChild("a").getCount());
58	assertEquals(1, fixture.getChild("a").getChild("b").getCount());
59	assertNull(fixture.getChild("b"));
60	}
61
62	@Test
63	public void testAdd_2()
64	throws Exception {
65	Trie<String> fixture = new Trie<String>();
66
67	fixture.add(new ArrayList<String>());
68
69	assertEquals(0, fixture.getNumSymbols());
70	}
71
72	@Test
73	public void testAdd_3()
74	throws Exception {
75	Trie<String> fixture = new Trie<String>();
76
77	fixture.add(null);
78
79	assertEquals(0, fixture.getNumSymbols());
80	}
81
82	@Test
83	public void testFind_1()
84	throws Exception {
85	Trie<String> fixture = new Trie<String>();
86	fixture.train(sequence, 3);
87	List<String> findSequence = new ArrayList<String>();
88	findSequence.add("a");
89	findSequence.add("b");
90	findSequence.add("r");
91	TrieNode<String> expected = fixture.getChild("a").getChild("b").getChild("r");
92
93	TrieNode<String> result = fixture.find(findSequence);
94
95	assertEquals(expected, result);
96	}
97
98	@Test
99	public void testFind_2()
100	throws Exception {
101	Trie<String> fixture = new Trie<String>();
102	fixture.train(sequence, 3);
103	List<String> findSequence = new ArrayList<String>();
104	findSequence.add("c");
105	findSequence.add("a");
106	TrieNode<String> expected = fixture.getChild("c").getChild("a");
107
108	TrieNode<String> result = fixture.find(findSequence);
109
110	assertEquals(expected, result);
111	}
112
113	@Test
114	public void testFind_3()
115	throws Exception {
116	Trie<String> fixture = new Trie<String>();
117	fixture.train(sequence, 3);
118	List<String> findSequence = new ArrayList<String>();
119
120	TrieNode<String> result = fixture.find(findSequence);
121
122	assertTrue(result.isRoot());
123	}
124
125	@Test
126	public void testFind_4()
127	throws Exception {
128	Trie<String> fixture = new Trie<String>();
129	fixture.train(sequence, 3);
130
131	TrieNode<String> result = fixture.find(null);
132
133	assertTrue(result.isRoot());
134	}
135
136	@Test
137	public void testGetChildCreate_1()
138	throws Exception {
139	Trie<String> fixture = new Trie<String>();
140	String symbol = "a";
141
142	TrieNode<String> result = fixture.getChildCreate(symbol);
143
144	assertEquals(symbol, result.getSymbol());
145	assertEquals(0, result.getCount());
146	assertTrue(result.isLeaf());
147	}
148
149	@Test(expected=java.security.InvalidParameterException.class)
150	public void testGetChildCreate_2()
151	throws Exception {
152	Trie<String> fixture = new Trie<String>();
153	fixture.getChildCreate(null);
154	}
155
156	@Test
157	public void testGetContextSuffix_1()
158	throws Exception {
159	Trie<String> fixture = new Trie<String>();
160	fixture.train(sequence, 3);
161	List<String> context = new ArrayList<String>();
162	context.add("a");
163	context.add("a");
164	context.add("b");
165	List<String> expected = new ArrayList<String>();
166	expected.add("a");
167	expected.add("b");
168
169
170	List<String> result = fixture.getContextSuffix(context);
171
172	ListAssert.assertEquals(expected, result);
173	}
174
175	@Test
176	public void testGetContextSuffix_2()
177	throws Exception {
178	Trie<String> fixture = new Trie<String>();
179	fixture.train(sequence, 3);
180	List<String> context = new ArrayList<String>();
181	context.add("a");
182	context.add("a");
183	context.add("b");
184	context.add("r");
185	List<String> expected = new ArrayList<String>();
186	expected.add("b");
187	expected.add("r");
188
189
190	List<String> result = fixture.getContextSuffix(context);
191
192	ListAssert.assertEquals(expected, result);
193	}
194
195	@Test
196	public void testGetContextSuffix_3()
197	throws Exception {
198	Trie<String> fixture = new Trie<String>();
199	fixture.train(sequence, 3);
200	List<String> context = new ArrayList<String>();
201	context.add("a");
202	context.add("a");
203	context.add("b");
204	context.add("x");
205	List<String> expected = new ArrayList<String>();
206
207	List<String> result = fixture.getContextSuffix(context);
208
209	ListAssert.assertEquals(expected, result);
210	}
211
212	@Test
213	public void testGetContextSuffix_4()
214	throws Exception {
215	Trie<String> fixture = new Trie<String>();
216
217	List<String> result = fixture.getContextSuffix(null);
218
219	// add additional test code here
220	assertNotNull(result);
221	assertEquals(0, result.size());
222	}
223
224	@Test
225	public void testGetContextSuffix_5()
226	throws Exception {
227	Trie<String> fixture = new Trie<String>();
228	fixture.train(sequence, 3);
229	List<String> context = new ArrayList<String>();
230	context.add("a");
231	context.add("a");
232	context.add("b");
233	List<String> expected = new ArrayList<String>();
234	expected.add("a");
235	expected.add("b");
236
237
238	List<String> result = fixture.getContextSuffix(context);
239
240	ListAssert.assertEquals(expected, result);
241	}
242
243	@Test
244	public void testGetCount_1()
245	throws Exception {
246	Trie<String> fixture = new Trie<String>();
247	fixture.train(sequence, 3);
248	List<String> subSequence = new ArrayList<String>();
249	subSequence.add("a");
250
251	int result = fixture.getCount(subSequence);
252
253	assertEquals(5, result);
254	}
255
256	@Test
257	public void testGetCount_2()
258	throws Exception {
259	Trie<String> fixture = new Trie<String>();
260	fixture.train(sequence, 3);
261	List<String> subSequence = new ArrayList<String>();
262	subSequence.add("a");
263	subSequence.add("b");
264
265	int result = fixture.getCount(subSequence);
266
267	assertEquals(2, result);
268	}
269
270	@Test
271	public void testGetCount_3()
272	throws Exception {
273	Trie<String> fixture = new Trie<String>();
274	fixture.train(sequence, 3);
275	List<String> subSequence = new ArrayList<String>();
276	subSequence.add("x");
277
278	int result = fixture.getCount(subSequence);
279
280	assertEquals(0, result);
281	}
282
283	@Test
284	public void testGetCount_4()
285	throws Exception {
286	Trie<String> fixture = new Trie<String>();
287	fixture.train(sequence, 3);
288	List<String> subSequence = new ArrayList<String>();
289
290	int result = fixture.getCount(subSequence, "a");
291
292	assertEquals(5, result);
293	}
294
295	@Test
296	public void testGetCount_5()
297	throws Exception {
298	Trie<String> fixture = new Trie<String>();
299	fixture.train(sequence, 3);
300	List<String> subSequence = new ArrayList<String>();
301	subSequence.add("a");
302	subSequence.add("b");
303
304	int result = fixture.getCount(subSequence, "r");
305
306	assertEquals(2, result);
307	}
308
309	@Test
310	public void testGetCount_6()
311	throws Exception {
312	Trie<String> fixture = new Trie<String>();
313	fixture.train(sequence, 3);
314	List<String> subSequence = new ArrayList<String>();
315
316	int result = fixture.getCount(subSequence, "x");
317
318	assertEquals(0, result);
319	}
320
321	@Test
322	public void testGetFollowingSymbols_1()
323	throws Exception {
324	Trie<String> fixture = new Trie<String>();
325	fixture.train(sequence, 3);
326	List<String> subSequence = new ArrayList<String>();
327	subSequence.add("a");
328	Collection<String> expected = new ArrayList<String>();
329	expected.add("b");
330	expected.add("c");
331	expected.add("d");
332
333	Collection<String> result = fixture.getFollowingSymbols(subSequence);
334
335	assertCollectionContent(expected, result);
336	}
337
338	@Test
339	public void testGetFollowingSymbols_2()
340	throws Exception {
341	Trie<String> fixture = new Trie<String>();
342	fixture.train(sequence, 3);
343	List<String> subSequence = new ArrayList<String>();
344	subSequence.add("a");
345	subSequence.add("b");
346	subSequence.add("r");
347
348	Collection<String> result = fixture.getFollowingSymbols(subSequence);
349
350	assertEquals(0, result.size());
351	}
352
353	@Test
354	public void testGetFollowingSymbols_3()
355	throws Exception {
356	Trie<String> fixture = new Trie<String>();
357	fixture.train(sequence, 3);
358	List<String> subSequence = new ArrayList<String>();
359	subSequence.add("x");
360
361	Collection<String> result = fixture.getFollowingSymbols(subSequence);
362
363	assertEquals(0, result.size());
364	}
365
366	@Test
367	public void testGetNumLeafAncestors_1()
368	throws Exception {
369	Trie<String> fixture = new Trie<String>();
370	fixture.train(sequence, 3);
371
372	int result = fixture.getNumLeafAncestors();
373
374	assertEquals(7, result);
375	}
376
377	@Test
378	public void testGetNumLeafs_1()
379	throws Exception {
380	Trie<String> fixture = new Trie<String>();
381	fixture.train(sequence, 3);
382
383	int result = fixture.getNumLeafs();
384
385	assertEquals(7, result);
386	}
387
388	@Test
389	public void testGetNumSymbols_1()
390	throws Exception {
391	Trie<String> fixture = new Trie<String>();
392	fixture.train(sequence, 3);
393
394	int result = fixture.getNumSymbols();
395
396	assertEquals(5, result);
397	}
398
399	@Test
400	public void testTrain_1()
401	throws Exception {
402	Trie<String> fixture = new Trie<String>();
403	int maxOrder = 3;
404
405	fixture.train(sequence, maxOrder);
406
407	// check if symbols are correct
408	assertCollectionContent(symbols, fixture.getKnownSymbols());
409
410	// check if counters are correct and only the correct nodes exist
411	TrieNode<String> root = fixture.find(new ArrayList<String>());
412	TrieNode<String> root_a = root.getChild("a");
413	TrieNode<String> root_a_a = root_a.getChild("a");
414	TrieNode<String> root_a_b = root_a.getChild("b");
415	TrieNode<String> root_a_b_a = root_a_b.getChild("a");
416	TrieNode<String> root_a_b_b = root_a_b.getChild("b");
417	TrieNode<String> root_a_b_c = root_a_b.getChild("c");
418	TrieNode<String> root_a_b_d = root_a_b.getChild("d");
419	TrieNode<String> root_a_b_r = root_a_b.getChild("r");
420	TrieNode<String> root_a_c = root_a.getChild("c");
421	TrieNode<String> root_a_c_a = root_a_c.getChild("a");
422	TrieNode<String> root_a_c_b = root_a_c.getChild("b");
423	TrieNode<String> root_a_c_c = root_a_c.getChild("c");
424	TrieNode<String> root_a_c_d = root_a_c.getChild("d");
425	TrieNode<String> root_a_c_r = root_a_c.getChild("r");
426	TrieNode<String> root_a_d = root_a.getChild("d");
427	TrieNode<String> root_a_d_a = root_a_d.getChild("a");
428	TrieNode<String> root_a_d_b = root_a_d.getChild("b");
429	TrieNode<String> root_a_d_c = root_a_d.getChild("c");
430	TrieNode<String> root_a_d_d = root_a_d.getChild("d");
431	TrieNode<String> root_a_d_r = root_a_d.getChild("r");
432	TrieNode<String> root_a_r = root_a.getChild("r");
433	TrieNode<String> root_b = root.getChild("b");
434	TrieNode<String> root_b_a = root_b.getChild("a");
435	TrieNode<String> root_b_b = root_b.getChild("b");
436	TrieNode<String> root_b_c = root_b.getChild("c");
437	TrieNode<String> root_b_d = root_b.getChild("d");
438	TrieNode<String> root_b_r = root_b.getChild("r");
439	TrieNode<String> root_b_r_a = root_b_r.getChild("a");
440	TrieNode<String> root_b_r_b = root_b_r.getChild("b");
441	TrieNode<String> root_b_r_c = root_b_r.getChild("c");
442	TrieNode<String> root_b_r_d = root_b_r.getChild("d");
443	TrieNode<String> root_b_r_r = root_b_r.getChild("r");
444	TrieNode<String> root_c = root.getChild("c");
445	TrieNode<String> root_c_a = root_c.getChild("a");
446	TrieNode<String> root_c_a_a = root_c_a.getChild("a");
447	TrieNode<String> root_c_a_b = root_c_a.getChild("b");
448	TrieNode<String> root_c_a_c = root_c_a.getChild("c");
449	TrieNode<String> root_c_a_d = root_c_a.getChild("d");
450	TrieNode<String> root_c_a_r = root_c_a.getChild("r");
451	TrieNode<String> root_c_b = root_c.getChild("b");
452	TrieNode<String> root_c_c = root_c.getChild("c");
453	TrieNode<String> root_c_d = root_c.getChild("d");
454	TrieNode<String> root_c_r = root_c.getChild("r");
455	TrieNode<String> root_d = root.getChild("d");
456	TrieNode<String> root_d_a = root_d.getChild("a");
457	TrieNode<String> root_d_a_a = root_d_a.getChild("a");
458	TrieNode<String> root_d_a_b = root_d_a.getChild("b");
459	TrieNode<String> root_d_a_c = root_d_a.getChild("c");
460	TrieNode<String> root_d_a_d = root_d_a.getChild("d");
461	TrieNode<String> root_d_a_r = root_d_a.getChild("r");
462	TrieNode<String> root_d_b = root_d.getChild("b");
463	TrieNode<String> root_d_c = root_d.getChild("c");
464	TrieNode<String> root_d_d = root_d.getChild("d");
465	TrieNode<String> root_d_r = root_d.getChild("r");
466	TrieNode<String> root_r = root.getChild("r");
467	TrieNode<String> root_r_a = root_r.getChild("a");
468	TrieNode<String> root_r_a_a = root_r_a.getChild("a");
469	TrieNode<String> root_r_a_b = root_r_a.getChild("b");
470	TrieNode<String> root_r_a_c = root_r_a.getChild("c");
471	TrieNode<String> root_r_a_d = root_r_a.getChild("d");
472	TrieNode<String> root_r_a_r = root_r_a.getChild("r");
473	TrieNode<String> root_r_b = root_r.getChild("b");
474	TrieNode<String> root_r_c = root_r.getChild("c");
475	TrieNode<String> root_r_d = root_r.getChild("d");
476	TrieNode<String> root_r_r = root_r.getChild("r");
477
478	assertEquals(5, root_a.getCount());
479	assertNull(root_a_a);
480	assertEquals(2, root_a_b.getCount());
481	assertNull(root_a_b_a);
482	assertNull(root_a_b_b);
483	assertNull(root_a_b_c);
484	assertNull(root_a_b_d);
485	assertEquals(2, root_a_b_r.getCount());
486	assertEquals(1, root_a_c.getCount());
487	assertEquals(1, root_a_c_a.getCount());
488	assertNull(root_a_c_b);
489	assertNull(root_a_c_c);
490	assertNull(root_a_c_d);
491	assertNull(root_a_c_r);
492	assertEquals(1, root_a_d.getCount());
493	assertEquals(1, root_a_d_a.getCount());
494	assertNull(root_a_d_b);
495	assertNull(root_a_d_c);
496	assertNull(root_a_d_d);
497	assertNull(root_a_d_r);
498	assertNull(root_a_r);
499
500	assertEquals(2, root_b.getCount());
501	assertNull(root_b_a);
502	assertNull(root_b_b);
503	assertNull(root_b_c);
504	assertNull(root_b_d);
505	assertEquals(2, root_b_r.getCount());
506	assertEquals(2, root_b_r_a.getCount());
507	assertNull(root_b_r_b);
508	assertNull(root_b_r_c);
509	assertNull(root_b_r_d);
510	assertNull(root_b_r_r);
511
512	assertEquals(1, root_c.getCount());
513	assertEquals(1, root_c_a.getCount());
514	assertNull(root_c_a_a);
515	assertNull(root_c_a_b);
516	assertNull(root_c_a_c);
517	assertEquals(1, root_c_a_d.getCount());
518	assertNull(root_c_a_r);
519	assertNull(root_c_b);
520	assertNull(root_c_c);
521	assertNull(root_c_d);
522	assertNull(root_c_r);
523
524	assertEquals(1, root_d.getCount());
525	assertEquals(1, root_d_a.getCount());
526	assertNull(root_d_a_a);
527	assertEquals(1, root_d_a_b.getCount());
528	assertNull(root_d_a_c);
529	assertNull(root_d_a_d);
530	assertNull(root_d_a_r);
531	assertNull(root_d_b);
532	assertNull(root_d_c);
533	assertNull(root_d_d);
534	assertNull(root_d_r);
535
536	assertEquals(2, root_r.getCount());
537	assertEquals(2, root_r_a.getCount());
538	assertNull(root_r_a_a);
539	assertNull(root_r_a_b);
540	assertEquals(1, root_r_a_c.getCount());
541	assertNull(root_r_a_d);
542	assertNull(root_r_a_r);
543	assertNull(root_r_b);
544	assertNull(root_r_c);
545	assertNull(root_r_d);
546	assertNull(root_r_r);
547
548	// check if leafs are really leafs
549	assertTrue(root_a_b_r.isLeaf());
550	assertTrue(root_a_c_a.isLeaf());
551	assertTrue(root_a_d_a.isLeaf());
552	assertTrue(root_b_r_a.isLeaf());
553	assertTrue(root_c_a_d.isLeaf());
554	assertTrue(root_d_a_b.isLeaf());
555	assertTrue(root_r_a_c.isLeaf());
556	}
557
558	@Test
559	public void testTrain_2()
560	throws Exception {
561	Trie<String> fixture = new Trie<String>();
562	int maxOrder = 0;
563
564	fixture.train(sequence, maxOrder);
565
566	assertTrue(fixture.getKnownSymbols().isEmpty());
567	}
568
569	@Test
570	public void testTrain_3()
571	throws Exception {
572	Trie<Object> fixture = new Trie<Object>();
573	List<Object> sequence = new ArrayList<Object>();
574	int maxOrder = 1;
575
576	fixture.train(sequence, maxOrder);
577
578	assertTrue(fixture.getKnownSymbols().isEmpty());
579	}
580
581	@Test
582	public void testTrain_4()
583	throws Exception {
584	Trie<String> fixture = new Trie<String>();
585	List<String> sequence = new ArrayList<String>();
586	sequence.add("a");
587	sequence.add("b");
588	int maxOrder = 3;
589
590	fixture.train(sequence, maxOrder);
591
592	assertCollectionContent(sequence, fixture.getKnownSymbols());
593	TrieNode<String> root = fixture.find(new ArrayList<String>());
594	TrieNode<String> root_a = root.getChild("a");
595	TrieNode<String> root_a_a = root_a.getChild("a");
596	TrieNode<String> root_a_b = root_a.getChild("b");
597	TrieNode<String> root_b = root.getChild("b");
598	TrieNode<String> root_b_a = root_b.getChild("a");
599	TrieNode<String> root_b_b = root_b.getChild("b");
600
601	assertEquals(1, root_a.getCount());
602	assertNull(root_a_a);
603	assertEquals(1, root_a_b.getCount());
604	assertEquals(1, root_b.getCount());
605	assertNull(root_b_a);
606	assertNull(root_b_b);
607
608	assertTrue(root_a_b.isLeaf());
609	assertTrue(root_b.isLeaf());
610	}
611
612	@Test
613	public void testEdgeEdge_1() throws Exception {
614	Edge result = new Edge();
615
616	assertNotNull(result);
617	}
618
619	@Test
620	public void testTrieVertexTrieVertex_1() throws Exception {
621	String id = "idString";
622
623	TrieVertex result = new TrieVertex(id);
624
625	assertNotNull(result);
626	}
627
628	@Test
629	public void testTrieVertexToString_1() throws Exception {
630	String id = "idString";
631	TrieVertex fixture = new TrieVertex(id);
632
633	String result = fixture.toString();
634
635	assertEquals(id, result);
636	}
637
638	@Before
639	public void setUp()
640	throws Exception {
641	sequence = new ArrayList<String>();
642	sequence.add("a");
643	sequence.add("b");
644	sequence.add("r");
645	sequence.add("a");
646	sequence.add("c");
647	sequence.add("a");
648	sequence.add("d");
649	sequence.add("a");
650	sequence.add("b");
651	sequence.add("r");
652	sequence.add("a");
653
654	symbols = new HashSet<String>();
655	symbols.add("a");
656	symbols.add("b");
657	symbols.add("c");
658	symbols.add("d");
659	symbols.add("r");
660	}
661
662	@After
663	public void tearDown()
664	throws Exception {
665	// Add additional tear down code here
666	}
667
668	public static void main(String[] args) {
669	new org.junit.runner.JUnitCore().run(TrieTest.class);
670	}
671	}

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

Download in other formats:

Original Format