source: trunk/EventBenchCoreTest/src/de/ugoe/cs/eventbench/models/TrieTest.java @ 334

Last change on this file since 334 was 315, checked in by sherbold, 13 years ago
  • fixed test case de.ugoe.cs.eventbench.models.TrieTest?.testGetContextSuffix_2, which had the wrong expected result
  • Property svn:mime-type set to text/plain
File size: 17.6 KB
Line 
1package de.ugoe.cs.eventbench.models;
2
3import java.util.ArrayList;
4import java.util.Collection;
5import java.util.HashSet;
6import java.util.List;
7
8import junitx.framework.ListAssert;
9
10import org.junit.*;
11import 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 */
19public 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("b");
184                expected.add("r");
185               
186
187                List<String> result = fixture.getContextSuffix(context);
188
189                ListAssert.assertEquals(expected, result);
190        }
191
192        @Test
193        public void testGetContextSuffix_3()
194                throws Exception {
195                Trie<String> fixture = new Trie<String>();
196                fixture.train(sequence, 3);
197                List<String> context = new ArrayList<String>();
198                context.add("a");
199                context.add("a");
200                context.add("b");
201                context.add("x");
202                List<String> expected = new ArrayList<String>();
203
204                List<String> result = fixture.getContextSuffix(context);
205
206                ListAssert.assertEquals(expected, result);
207        }
208
209        @Test
210        public void testGetContextSuffix_4()
211                throws Exception {
212                Trie<String> fixture = new Trie<String>();
213
214                List<String> result = fixture.getContextSuffix(null);
215
216                // add additional test code here
217                assertNotNull(result);
218                assertEquals(0, result.size());
219        }
220
221        @Test
222        public void testGetContextSuffix_5()
223                throws Exception {
224                Trie<String> fixture = new Trie<String>();
225                fixture.train(sequence, 3);
226                List<String> context = new ArrayList<String>();
227                context.add("a");
228                context.add("a");
229                context.add("b");
230                List<String> expected = new ArrayList<String>();
231                expected.add("a");
232                expected.add("b");
233               
234
235                List<String> result = fixture.getContextSuffix(context);
236
237                ListAssert.assertEquals(expected, result);
238        }
239
240        @Test
241        public void testGetCount_1()
242                throws Exception {
243                Trie<String> fixture = new Trie<String>();
244                fixture.train(sequence, 3);
245                List<String> subSequence = new ArrayList<String>();
246                subSequence.add("a");
247
248                int result = fixture.getCount(subSequence);
249
250                assertEquals(5, result);
251        }
252
253        @Test
254        public void testGetCount_2()
255                throws Exception {
256                Trie<String> fixture = new Trie<String>();
257                fixture.train(sequence, 3);
258                List<String> subSequence = new ArrayList<String>();
259                subSequence.add("a");
260                subSequence.add("b");
261
262                int result = fixture.getCount(subSequence);
263               
264                assertEquals(2, result);
265        }
266
267        @Test
268        public void testGetCount_3()
269                throws Exception {
270                Trie<String> fixture = new Trie<String>();
271                fixture.train(sequence, 3);
272                List<String> subSequence = new ArrayList<String>();
273                subSequence.add("x");
274
275                int result = fixture.getCount(subSequence);
276
277                assertEquals(0, result);
278        }
279       
280        @Test
281        public void testGetCount_4()
282                throws Exception {
283                Trie<String> fixture = new Trie<String>();
284                fixture.train(sequence, 3);
285                List<String> subSequence = new ArrayList<String>();
286
287                int result = fixture.getCount(subSequence, "a");
288
289                assertEquals(5, result);
290        }
291
292        @Test
293        public void testGetCount_5()
294                throws Exception {
295                Trie<String> fixture = new Trie<String>();
296                fixture.train(sequence, 3);
297                List<String> subSequence = new ArrayList<String>();
298                subSequence.add("a");
299                subSequence.add("b");
300
301                int result = fixture.getCount(subSequence, "r");
302               
303                assertEquals(2, result);
304        }
305
306        @Test
307        public void testGetCount_6()
308                throws Exception {
309                Trie<String> fixture = new Trie<String>();
310                fixture.train(sequence, 3);
311                List<String> subSequence = new ArrayList<String>();
312
313                int result = fixture.getCount(subSequence, "x");
314
315                assertEquals(0, result);
316        }
317
318        @Test
319        public void testGetFollowingSymbols_1()
320                throws Exception {
321                Trie<String> fixture = new Trie<String>();
322                fixture.train(sequence, 3);
323                List<String> subSequence = new ArrayList<String>();
324                subSequence.add("a");
325                Collection<String> expected = new ArrayList<String>();
326                expected.add("b");
327                expected.add("c");
328                expected.add("d");
329               
330                Collection<String> result = fixture.getFollowingSymbols(subSequence);
331
332                assertCollectionContent(expected, result);
333        }
334
335        @Test
336        public void testGetFollowingSymbols_2()
337                throws Exception {
338                Trie<String> fixture = new Trie<String>();
339                fixture.train(sequence, 3);
340                List<String> subSequence = new ArrayList<String>();
341                subSequence.add("a");
342                subSequence.add("b");
343                subSequence.add("r");
344
345                Collection<String> result = fixture.getFollowingSymbols(subSequence);
346
347                assertEquals(0, result.size());
348        }
349       
350        @Test
351        public void testGetFollowingSymbols_3()
352                throws Exception {
353                Trie<String> fixture = new Trie<String>();
354                fixture.train(sequence, 3);
355                List<String> subSequence = new ArrayList<String>();
356                subSequence.add("x");
357
358                Collection<String> result = fixture.getFollowingSymbols(subSequence);
359
360                assertEquals(0, result.size());
361        }
362       
363        @Test
364        public void testGetNumLeafAncestors_1()
365                throws Exception {
366                Trie<String> fixture = new Trie<String>();
367                fixture.train(sequence, 3);
368
369                int result = fixture.getNumLeafAncestors();
370
371                assertEquals(7, result);
372        }
373       
374        @Test
375        public void testGetNumLeafs_1()
376                throws Exception {
377                Trie<String> fixture = new Trie<String>();
378                fixture.train(sequence, 3);
379
380                int result = fixture.getNumLeafs();
381
382                assertEquals(7, result);
383        }
384       
385        @Test
386        public void testGetNumSymbols_1()
387                throws Exception {
388                Trie<String> fixture = new Trie<String>();
389                fixture.train(sequence, 3);
390
391                int result = fixture.getNumSymbols();
392
393                assertEquals(5, result);
394        }
395
396        @Test
397        public void testTrain_1()
398                throws Exception {
399                Trie<String> fixture = new Trie<String>();
400                int maxOrder = 3;
401
402                fixture.train(sequence, maxOrder);
403               
404                // check if symbols are correct
405                assertCollectionContent(symbols, fixture.getKnownSymbols());
406               
407                // check if counters are correct and only the correct nodes exist
408                TrieNode<String> root = fixture.find(new ArrayList<String>());
409                TrieNode<String> root_a = root.getChild("a");
410                TrieNode<String> root_a_a = root_a.getChild("a");
411                TrieNode<String> root_a_b = root_a.getChild("b");
412                TrieNode<String> root_a_b_a = root_a_b.getChild("a");
413                TrieNode<String> root_a_b_b = root_a_b.getChild("b");
414                TrieNode<String> root_a_b_c = root_a_b.getChild("c");
415                TrieNode<String> root_a_b_d = root_a_b.getChild("d");
416                TrieNode<String> root_a_b_r = root_a_b.getChild("r");
417                TrieNode<String> root_a_c = root_a.getChild("c");
418                TrieNode<String> root_a_c_a = root_a_c.getChild("a");
419                TrieNode<String> root_a_c_b = root_a_c.getChild("b");
420                TrieNode<String> root_a_c_c = root_a_c.getChild("c");
421                TrieNode<String> root_a_c_d = root_a_c.getChild("d");
422                TrieNode<String> root_a_c_r = root_a_c.getChild("r");
423                TrieNode<String> root_a_d = root_a.getChild("d");
424                TrieNode<String> root_a_d_a = root_a_d.getChild("a");
425                TrieNode<String> root_a_d_b = root_a_d.getChild("b");
426                TrieNode<String> root_a_d_c = root_a_d.getChild("c");
427                TrieNode<String> root_a_d_d = root_a_d.getChild("d");
428                TrieNode<String> root_a_d_r = root_a_d.getChild("r");
429                TrieNode<String> root_a_r = root_a.getChild("r");
430                TrieNode<String> root_b = root.getChild("b");
431                TrieNode<String> root_b_a = root_b.getChild("a");
432                TrieNode<String> root_b_b = root_b.getChild("b");
433                TrieNode<String> root_b_c = root_b.getChild("c");
434                TrieNode<String> root_b_d = root_b.getChild("d");
435                TrieNode<String> root_b_r = root_b.getChild("r");
436                TrieNode<String> root_b_r_a = root_b_r.getChild("a");
437                TrieNode<String> root_b_r_b = root_b_r.getChild("b");
438                TrieNode<String> root_b_r_c = root_b_r.getChild("c");
439                TrieNode<String> root_b_r_d = root_b_r.getChild("d");
440                TrieNode<String> root_b_r_r = root_b_r.getChild("r");
441                TrieNode<String> root_c = root.getChild("c");
442                TrieNode<String> root_c_a = root_c.getChild("a");
443                TrieNode<String> root_c_a_a = root_c_a.getChild("a");
444                TrieNode<String> root_c_a_b = root_c_a.getChild("b");
445                TrieNode<String> root_c_a_c = root_c_a.getChild("c");
446                TrieNode<String> root_c_a_d = root_c_a.getChild("d");
447                TrieNode<String> root_c_a_r = root_c_a.getChild("r");
448                TrieNode<String> root_c_b = root_c.getChild("b");
449                TrieNode<String> root_c_c = root_c.getChild("c");
450                TrieNode<String> root_c_d = root_c.getChild("d");
451                TrieNode<String> root_c_r = root_c.getChild("r");
452                TrieNode<String> root_d = root.getChild("d");
453                TrieNode<String> root_d_a = root_d.getChild("a");
454                TrieNode<String> root_d_a_a = root_d_a.getChild("a");
455                TrieNode<String> root_d_a_b = root_d_a.getChild("b");
456                TrieNode<String> root_d_a_c = root_d_a.getChild("c");
457                TrieNode<String> root_d_a_d = root_d_a.getChild("d");
458                TrieNode<String> root_d_a_r = root_d_a.getChild("r");
459                TrieNode<String> root_d_b = root_d.getChild("b");
460                TrieNode<String> root_d_c = root_d.getChild("c");
461                TrieNode<String> root_d_d = root_d.getChild("d");
462                TrieNode<String> root_d_r = root_d.getChild("r");
463                TrieNode<String> root_r = root.getChild("r");
464                TrieNode<String> root_r_a = root_r.getChild("a");
465                TrieNode<String> root_r_a_a = root_r_a.getChild("a");
466                TrieNode<String> root_r_a_b = root_r_a.getChild("b");
467                TrieNode<String> root_r_a_c = root_r_a.getChild("c");
468                TrieNode<String> root_r_a_d = root_r_a.getChild("d");
469                TrieNode<String> root_r_a_r = root_r_a.getChild("r");
470                TrieNode<String> root_r_b = root_r.getChild("b");
471                TrieNode<String> root_r_c = root_r.getChild("c");
472                TrieNode<String> root_r_d = root_r.getChild("d");
473                TrieNode<String> root_r_r = root_r.getChild("r");
474               
475                assertEquals(5, root_a.getCount());
476                assertNull(root_a_a);
477                assertEquals(2, root_a_b.getCount());
478                assertNull(root_a_b_a);
479                assertNull(root_a_b_b);
480                assertNull(root_a_b_c);
481                assertNull(root_a_b_d);
482                assertEquals(2, root_a_b_r.getCount());
483                assertEquals(1, root_a_c.getCount());
484                assertEquals(1, root_a_c_a.getCount());
485                assertNull(root_a_c_b);
486                assertNull(root_a_c_c);
487                assertNull(root_a_c_d);
488                assertNull(root_a_c_r);
489                assertEquals(1, root_a_d.getCount());
490                assertEquals(1, root_a_d_a.getCount());
491                assertNull(root_a_d_b);
492                assertNull(root_a_d_c);
493                assertNull(root_a_d_d);
494                assertNull(root_a_d_r);
495                assertNull(root_a_r);
496               
497                assertEquals(2, root_b.getCount());
498                assertNull(root_b_a);
499                assertNull(root_b_b);
500                assertNull(root_b_c);
501                assertNull(root_b_d);
502                assertEquals(2, root_b_r.getCount());
503                assertEquals(2, root_b_r_a.getCount());
504                assertNull(root_b_r_b);
505                assertNull(root_b_r_c);
506                assertNull(root_b_r_d);
507                assertNull(root_b_r_r);
508               
509                assertEquals(1, root_c.getCount());
510                assertEquals(1, root_c_a.getCount());
511                assertNull(root_c_a_a);
512                assertNull(root_c_a_b);
513                assertNull(root_c_a_c);
514                assertEquals(1, root_c_a_d.getCount());
515                assertNull(root_c_a_r);
516                assertNull(root_c_b);
517                assertNull(root_c_c);
518                assertNull(root_c_d);
519                assertNull(root_c_r);
520               
521                assertEquals(1, root_d.getCount());
522                assertEquals(1, root_d_a.getCount());
523                assertNull(root_d_a_a);
524                assertEquals(1, root_d_a_b.getCount());
525                assertNull(root_d_a_c);
526                assertNull(root_d_a_d);
527                assertNull(root_d_a_r);
528                assertNull(root_d_b);
529                assertNull(root_d_c);
530                assertNull(root_d_d);
531                assertNull(root_d_r);
532               
533                assertEquals(2, root_r.getCount());
534                assertEquals(2, root_r_a.getCount());
535                assertNull(root_r_a_a);
536                assertNull(root_r_a_b);
537                assertEquals(1, root_r_a_c.getCount());
538                assertNull(root_r_a_d);
539                assertNull(root_r_a_r);
540                assertNull(root_r_b);
541                assertNull(root_r_c);
542                assertNull(root_r_d);
543                assertNull(root_r_r);
544               
545                // check if leafs are really leafs
546                assertTrue(root_a_b_r.isLeaf());
547                assertTrue(root_a_c_a.isLeaf());
548                assertTrue(root_a_d_a.isLeaf());
549                assertTrue(root_b_r_a.isLeaf());
550                assertTrue(root_c_a_d.isLeaf());
551                assertTrue(root_d_a_b.isLeaf());
552                assertTrue(root_r_a_c.isLeaf());
553        }
554
555        @Test
556        public void testTrain_2()
557                throws Exception {
558                Trie<String> fixture = new Trie<String>();
559                int maxOrder = 0;
560
561                fixture.train(sequence, maxOrder);
562
563                assertTrue(fixture.getKnownSymbols().isEmpty());
564        }
565
566        @Test
567        public void testTrain_3()
568                throws Exception {
569                Trie<Object> fixture = new Trie<Object>();
570                List<Object> sequence = new ArrayList<Object>();
571                int maxOrder = 1;
572
573                fixture.train(sequence, maxOrder);
574               
575                assertTrue(fixture.getKnownSymbols().isEmpty());
576        }
577
578        @Test
579        public void testTrain_4()
580                throws Exception {
581                Trie<String> fixture = new Trie<String>();
582                List<String> sequence = new ArrayList<String>();
583                sequence.add("a");
584                sequence.add("b");
585                int maxOrder = 3;
586
587                fixture.train(sequence, maxOrder);
588               
589                assertCollectionContent(sequence, fixture.getKnownSymbols());
590                TrieNode<String> root = fixture.find(new ArrayList<String>());
591                TrieNode<String> root_a = root.getChild("a");
592                TrieNode<String> root_a_a = root_a.getChild("a");
593                TrieNode<String> root_a_b = root_a.getChild("b");
594                TrieNode<String> root_b = root.getChild("b");
595                TrieNode<String> root_b_a = root_b.getChild("a");
596                TrieNode<String> root_b_b = root_b.getChild("b");
597               
598                assertEquals(1, root_a.getCount());
599                assertNull(root_a_a);
600                assertEquals(1, root_a_b.getCount());
601                assertEquals(1, root_b.getCount());
602                assertNull(root_b_a);
603                assertNull(root_b_b);
604               
605                assertTrue(root_a_b.isLeaf());
606                assertTrue(root_b.isLeaf());
607        }
608
609        @Before
610        public void setUp()
611                throws Exception {
612                sequence = new ArrayList<String>();
613                sequence.add("a");
614                sequence.add("b");
615                sequence.add("r");
616                sequence.add("a");
617                sequence.add("c");
618                sequence.add("a");
619                sequence.add("d");
620                sequence.add("a");
621                sequence.add("b");
622                sequence.add("r");
623                sequence.add("a");
624               
625                symbols = new HashSet<String>();
626                symbols.add("a");
627                symbols.add("b");
628                symbols.add("c");
629                symbols.add("d");
630                symbols.add("r");
631        }
632
633        @After
634        public void tearDown()
635                throws Exception {
636                // Add additional tear down code here
637        }
638
639        public static void main(String[] args) {
640                new org.junit.runner.JUnitCore().run(TrieTest.class);
641        }
642}
Note: See TracBrowser for help on using the repository browser.