Context Navigation

TrieTest.java @ 257

Last change on this file since 257 was 257, checked in by sherbold, 13 years ago

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

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

Download in other formats:

Original Format