source: trunk/autoquest-core-tasktrees-test/src/test/java/de/ugoe/cs/autoquest/tasktrees/temporalrelation/TaskInstanceTrieTest.java @ 1256

Last change on this file since 1256 was 1256, checked in by pharms, 11 years ago
  • performance improvement for task tree generation
File size: 66.5 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
15package de.ugoe.cs.autoquest.tasktrees.temporalrelation;
16
17import java.util.ArrayList;
18import java.util.Arrays;
19import java.util.Collection;
20import java.util.HashMap;
21import java.util.List;
22import java.util.Map;
23
24import org.junit.*;
25
26import de.ugoe.cs.autoquest.tasktrees.TaskTreeDecoder;
27import de.ugoe.cs.autoquest.tasktrees.taskequality.TaskEquality;
28import de.ugoe.cs.autoquest.tasktrees.treeifc.ITaskBuilder;
29import de.ugoe.cs.autoquest.tasktrees.treeifc.ITaskFactory;
30import de.ugoe.cs.autoquest.tasktrees.treeifc.ITaskInstance;
31import de.ugoe.cs.autoquest.tasktrees.treeifc.IUserSession;
32import de.ugoe.cs.autoquest.tasktrees.treeimpl.TaskBuilder;
33import de.ugoe.cs.autoquest.tasktrees.treeimpl.TaskFactory;
34import de.ugoe.cs.autoquest.usageprofiles.TrieProcessor;
35
36import static org.junit.Assert.*;
37
38/**
39 * The class <code>TaskInstanceTrieTest</code> contains tests for the class <code>{@link TaskInstanceTrie}</code>.
40 *
41 * @author Steffen Herbold
42 * @version 1.0
43 */
44public class TaskInstanceTrieTest {
45
46    /** */
47    private ITaskBuilder taskBuilder = new TaskBuilder();
48
49    /** */
50    private ITaskFactory taskFactory = new TaskFactory();
51   
52    /** */
53    private TaskTreeDecoder decoder = new TaskTreeDecoder(taskFactory, taskBuilder);
54   
55    /** */
56    private TaskComparator comparator = new TaskComparator(TaskEquality.SEMANTICALLY_EQUAL);
57   
58    /** */
59    private IUserSession session = (IUserSession) decoder.decode
60         ("UserSession {" +
61          "  Event actionA {}" +
62          "  Event actionB {}" +
63          "  Event actionR {}" +
64          "  Event actionA {}" +
65          "  Event actionC {}" +
66          "  Event actionA {}" +
67          "  Event actionD {}" +
68          "  Event actionA {}" +
69          "  Event actionB {}" +
70          "  Event actionR {}" +
71          "  Event actionA {}" +
72          "}");
73
74    /**
75     *
76     */
77    private static void assertCollectionContent(Collection<?> c1, Collection<?> c2) {
78        assertEquals(c1.size(), c2.size());
79        for (Object obj : c1) {
80            assertTrue(c2.contains(obj));
81        }
82    }
83
84    @Test
85    public void testTaskInstanceTaskInstanceTrie_1() throws Exception {
86        TaskInstanceTrie result = new TaskInstanceTrie(comparator);
87
88        assertNotNull(result);
89        assertEquals(0, result.getNumLeafs());
90        assertEquals(0, result.getNumSymbols());
91        assertEquals(0, result.getNumLeafAncestors());
92        assertTrue(result.getKnownSymbols().isEmpty());
93    }
94
95    @Test(expected = java.lang.IllegalArgumentException.class)
96    public void testTaskInstanceTrie_2() throws Exception {
97        new TaskInstanceTrie((TaskComparator) null);
98    }
99
100    @Test
101    public void testTrainSessions_1() throws Exception {
102        TaskInstanceTrie fixture = new TaskInstanceTrie(comparator);
103       
104        IUserSession session = (IUserSession) decoder.decode
105            ("UserSession {" +
106             "  Event action1 {}" +
107             "  Event action2 {}" +
108             "  Event action3 {}" +
109             "  Event action4 {}" +
110             "}");
111       
112        fixture.trainSessions(Arrays.asList(session), 2);
113       
114        assertEquals(1, fixture.getCount(Arrays.asList(session.get(0))));
115        assertEquals(1, fixture.getCount(Arrays.asList(session.get(1))));
116        assertEquals(1, fixture.getCount(Arrays.asList(session.get(2))));
117       
118        // subsequences of length 1 are not trained. So for the single item sequence of the last
119        // task, the count must be 0
120        assertEquals(0, fixture.getCount(Arrays.asList(session.get(3))));
121       
122       
123        assertEquals(1, fixture.getCount(Arrays.asList(session.get(0), session.get(1))));
124        assertEquals(1, fixture.getCount(Arrays.asList(session.get(1), session.get(2))));
125        assertEquals(1, fixture.getCount(Arrays.asList(session.get(2), session.get(3))));
126       
127        // this must return 0 as we only trained shorter sequences
128        assertEquals(0, fixture.getCount(Arrays.asList(session.get(0), session.get(1),
129                                                       session.get(2))));
130       
131        // subsequences of length 1 are not trained. So the single item sequence of the last
132        // task, is not counted
133        assertEquals(3, fixture.getNumSymbols());
134    }
135
136    @Test
137    public void testTrainSessions_2() throws Exception {
138        TaskInstanceTrie fixture = new TaskInstanceTrie(comparator);
139       
140        IUserSession session = (IUserSession) decoder.decode
141            ("UserSession {" +
142             "  Event action1 {}" +
143             "  Event action1 {}" +
144             "  Event action1 {}" +
145             "  Event action1 {}" +
146             "}");
147       
148        fixture.trainSessions(Arrays.asList(session), 2);
149       
150        for (int i = 0; i < session.size(); i++) {
151            // subsequences of length 1 are not trained. So the single item sequence of the last
152            // task is not counted. Therefore, the result must be 3
153            assertEquals(3, fixture.getCount(Arrays.asList(session.get(i))));
154           
155            for (int j = 0; j < session.size(); j++) {
156                assertEquals(3, fixture.getCount(Arrays.asList(session.get(i), session.get(j))));
157            }
158        }
159           
160        // this must return 0 as we only trained shorter sequences
161        assertEquals(0, fixture.getCount(Arrays.asList(session.get(0), session.get(1),
162                                                       session.get(2))));
163       
164        assertEquals(1, fixture.getNumSymbols());
165    }
166
167    @Test
168    public void testTrainSessions_3() throws Exception {
169        TaskInstanceTrie fixture = new TaskInstanceTrie(comparator);
170       
171        IUserSession session = (IUserSession) decoder.decode
172            ("UserSession {" +
173             "  Event action1 {}" +
174             "  Event action2 {}" +
175             "  Event action1 {}" +
176             "  Event action2 {}" +
177             "}");
178       
179        fixture.trainSessions(Arrays.asList(session), 2);
180       
181        // subsequences of length 1 are not trained. So the single item sequence of the last
182        // task is not counted. Therefore, the result must be 3
183        assertEquals(2, fixture.getCount(Arrays.asList(session.get(0))));
184        assertEquals(1, fixture.getCount(Arrays.asList(session.get(1))));
185        assertEquals(2, fixture.getCount(Arrays.asList(session.get(2))));
186        assertEquals(1, fixture.getCount(Arrays.asList(session.get(3))));
187       
188        assertEquals(2, fixture.getCount(Arrays.asList(session.get(0), session.get(1))));
189        assertEquals(1, fixture.getCount(Arrays.asList(session.get(1), session.get(2))));
190        assertEquals(2, fixture.getCount(Arrays.asList(session.get(2), session.get(3))));
191       
192        // this must return 0 as we only trained shorter sequences
193        assertEquals(0, fixture.getCount(Arrays.asList(session.get(0), session.get(1),
194                                                       session.get(2))));
195       
196        assertEquals(2, fixture.getNumSymbols());
197    }
198
199    @Test
200    public void testTrainSessions_4() throws Exception {
201        TaskInstanceTrie fixture = new TaskInstanceTrie(comparator);
202       
203        IUserSession session = (IUserSession) decoder.decode
204            ("UserSession {" +
205             "  Event action1 {}" +
206             "  Event action2 {}" +
207             "  Event action3 {}" +
208             "  Event action4 {}" +
209             "}");
210       
211        fixture.trainSessions(Arrays.asList(session), 3);
212       
213        assertEquals(1, fixture.getCount(Arrays.asList(session.get(0))));
214        assertEquals(1, fixture.getCount(Arrays.asList(session.get(1))));
215        assertEquals(1, fixture.getCount(Arrays.asList(session.get(2))));
216       
217        // subsequences of length 1 are not trained. So for the single item sequence of the last
218        // task, the count must be 0
219        assertEquals(0, fixture.getCount(Arrays.asList(session.get(3))));
220       
221       
222        assertEquals(1, fixture.getCount(Arrays.asList(session.get(0), session.get(1))));
223        assertEquals(1, fixture.getCount(Arrays.asList(session.get(1), session.get(2))));
224        assertEquals(1, fixture.getCount(Arrays.asList(session.get(2), session.get(3))));
225       
226        assertEquals(1, fixture.getCount(Arrays.asList(session.get(0), session.get(1),
227                                                       session.get(2))));
228        assertEquals(1, fixture.getCount(Arrays.asList(session.get(1), session.get(2),
229                                                       session.get(3))));
230       
231        // we only trained shorter sequences, so we expect a count of 0 for longer ones
232        assertEquals(0, fixture.getCount(Arrays.asList(session.get(0), session.get(1),
233                                                       session.get(2), session.get(3))));
234       
235        // subsequences of length 1 are not trained. So the single item sequence of the last
236        // task, is not counted
237        assertEquals(3, fixture.getNumSymbols());
238    }
239
240    @Test
241    public void testTrainSessions_5() throws Exception {
242        TaskInstanceTrie fixture = new TaskInstanceTrie(comparator);
243       
244        IUserSession session = (IUserSession) decoder.decode
245            ("UserSession {" +
246             "  Event action1 {}" +
247             "  Event action1 {}" +
248             "  Event action1 {}" +
249             "  Event action1 {}" +
250             "}");
251       
252        fixture.trainSessions(Arrays.asList(session), 3);
253       
254        for (int i = 0; i < session.size(); i++) {
255            // subsequences of length 1 are not trained. So the single item sequence of the last
256            // task is not counted. Therefore, the result must be 3
257            assertEquals(3, fixture.getCount(Arrays.asList(session.get(i))));
258           
259            for (int j = 0; j < session.size(); j++) {
260                assertEquals(3, fixture.getCount(Arrays.asList(session.get(i), session.get(j))));
261               
262                for (int k = 0; k < session.size(); k++) {
263                    assertEquals(2, fixture.getCount(Arrays.asList(session.get(i), session.get(j),
264                                                                   session.get(k))));                   
265                }
266            }
267        }
268           
269        // we only trained shorter sequences, so we expect a count of 0 for longer ones
270        assertEquals(0, fixture.getCount(Arrays.asList(session.get(0), session.get(1),
271                                                       session.get(2), session.get(3))));
272       
273        assertEquals(1, fixture.getNumSymbols());
274    }
275
276    @Test
277    public void testTrainSessions_6() throws Exception {
278        TaskInstanceTrie fixture = new TaskInstanceTrie(comparator);
279       
280        IUserSession session = (IUserSession) decoder.decode
281            ("UserSession {" +
282             "  Event action1 {}" +
283             "  Event action2 {}" +
284             "  Event action1 {}" +
285             "  Event action2 {}" +
286             "}");
287       
288        fixture.trainSessions(Arrays.asList(session), 3);
289       
290        // subsequences of length 1 are not trained. So the single item sequence of the last
291        // task is not counted. Therefore, the result must be 3
292        assertEquals(2, fixture.getCount(Arrays.asList(session.get(0))));
293        assertEquals(1, fixture.getCount(Arrays.asList(session.get(1))));
294        assertEquals(2, fixture.getCount(Arrays.asList(session.get(2))));
295        assertEquals(1, fixture.getCount(Arrays.asList(session.get(3))));
296       
297        assertEquals(2, fixture.getCount(Arrays.asList(session.get(0), session.get(1))));
298        assertEquals(1, fixture.getCount(Arrays.asList(session.get(1), session.get(2))));
299        assertEquals(2, fixture.getCount(Arrays.asList(session.get(2), session.get(3))));
300       
301        assertEquals(1, fixture.getCount(Arrays.asList(session.get(0), session.get(1),
302                                                       session.get(2))));
303        assertEquals(1, fixture.getCount(Arrays.asList(session.get(1), session.get(2),
304                                                       session.get(3))));
305       
306        // we only trained shorter sequences, so we expect a count of 0 for longer ones
307        assertEquals(0, fixture.getCount(Arrays.asList(session.get(0), session.get(1),
308                                                       session.get(2), session.get(3))));
309       
310        assertEquals(2, fixture.getNumSymbols());
311    }
312
313    @Test
314    public void testTrainSessions_7() throws Exception {
315        TaskInstanceTrie fixture = new TaskInstanceTrie(comparator);
316       
317        IUserSession session = (IUserSession) decoder.decode
318            ("UserSession {" +
319             "  Event action1 {}" +
320             "  Event action2 {}" +
321             "  Event action3 {}" +
322             "  Event action4 {}" +
323             "}");
324       
325        fixture.trainSessions(Arrays.asList(session), 4);
326       
327        assertEquals(1, fixture.getCount(Arrays.asList(session.get(0))));
328        assertEquals(1, fixture.getCount(Arrays.asList(session.get(1))));
329        assertEquals(1, fixture.getCount(Arrays.asList(session.get(2))));
330       
331        // subsequences of length 1 are not trained. So for the single item sequence of the last
332        // task, the count must be 0
333        assertEquals(0, fixture.getCount(Arrays.asList(session.get(3))));
334       
335       
336        assertEquals(1, fixture.getCount(Arrays.asList(session.get(0), session.get(1))));
337        assertEquals(1, fixture.getCount(Arrays.asList(session.get(1), session.get(2))));
338        assertEquals(1, fixture.getCount(Arrays.asList(session.get(2), session.get(3))));
339       
340        assertEquals(1, fixture.getCount(Arrays.asList(session.get(0), session.get(1),
341                                                       session.get(2))));
342        assertEquals(1, fixture.getCount(Arrays.asList(session.get(1), session.get(2),
343                                                       session.get(3))));
344       
345        // we only trained shorter sequences, so we expect a count of 0 for longer ones
346        assertEquals(1, fixture.getCount(Arrays.asList(session.get(0), session.get(1),
347                                                       session.get(2), session.get(3))));
348       
349        // subsequences of length 1 are not trained. So the single item sequence of the last
350        // task, is not counted
351        assertEquals(3, fixture.getNumSymbols());
352    }
353
354    @Test
355    public void testTrainSessions_8() throws Exception {
356        TaskInstanceTrie fixture = new TaskInstanceTrie(comparator);
357       
358        IUserSession session = (IUserSession) decoder.decode
359            ("UserSession {" +
360             "  Event action1 {}" +
361             "  Event action1 {}" +
362             "  Event action1 {}" +
363             "  Event action1 {}" +
364             "}");
365       
366        fixture.trainSessions(Arrays.asList(session), 4);
367       
368        for (int i = 0; i < session.size(); i++) {
369            // subsequences of length 1 are not trained. So the single item sequence of the last
370            // task is not counted. Therefore, the result must be 3
371            assertEquals(3, fixture.getCount(Arrays.asList(session.get(i))));
372           
373            for (int j = 0; j < session.size(); j++) {
374                assertEquals(3, fixture.getCount(Arrays.asList(session.get(i), session.get(j))));
375               
376                for (int k = 0; k < session.size(); k++) {
377                    assertEquals(2, fixture.getCount(Arrays.asList(session.get(i), session.get(j),
378                                                                   session.get(k))));                   
379                }
380            }
381        }
382           
383        // we only trained shorter sequences, so we expect a count of 0 for longer ones
384        assertEquals(1, fixture.getCount(Arrays.asList(session.get(0), session.get(1),
385                                                       session.get(2), session.get(3))));
386       
387        assertEquals(1, fixture.getNumSymbols());
388    }
389
390    @Test
391    public void testTrainSessions_9() throws Exception {
392        TaskInstanceTrie fixture = new TaskInstanceTrie(comparator);
393       
394        IUserSession session = (IUserSession) decoder.decode
395            ("UserSession {" +
396             "  Event action1 {}" +
397             "  Event action2 {}" +
398             "  Event action1 {}" +
399             "  Event action2 {}" +
400             "}");
401       
402        fixture.trainSessions(Arrays.asList(session), 4);
403       
404        // subsequences of length 1 are not trained. So the single item sequence of the last
405        // task is not counted. Therefore, the result must be 3
406        assertEquals(2, fixture.getCount(Arrays.asList(session.get(0))));
407        assertEquals(1, fixture.getCount(Arrays.asList(session.get(1))));
408        assertEquals(2, fixture.getCount(Arrays.asList(session.get(2))));
409        assertEquals(1, fixture.getCount(Arrays.asList(session.get(3))));
410       
411        assertEquals(2, fixture.getCount(Arrays.asList(session.get(0), session.get(1))));
412        assertEquals(1, fixture.getCount(Arrays.asList(session.get(1), session.get(2))));
413        assertEquals(2, fixture.getCount(Arrays.asList(session.get(2), session.get(3))));
414       
415        assertEquals(1, fixture.getCount(Arrays.asList(session.get(0), session.get(1),
416                                                       session.get(2))));
417        assertEquals(1, fixture.getCount(Arrays.asList(session.get(1), session.get(2),
418                                                       session.get(3))));
419       
420        // we only trained shorter sequences, so we expect a count of 0 for longer ones
421        assertEquals(1, fixture.getCount(Arrays.asList(session.get(0), session.get(1),
422                                                       session.get(2), session.get(3))));
423       
424        assertEquals(2, fixture.getNumSymbols());
425    }
426
427
428    @Test
429    public void testGetSequencesWithMostOccurrences_1() throws Exception {
430        TaskInstanceTrie fixture = new TaskInstanceTrie(comparator);
431       
432        fixture.trainSessions(Arrays.asList(session), 3);
433
434        // get all sequences with a minimal length of one that occur most often
435        Collection<List<ITaskInstance>> result = fixture.getSequencesWithOccurrenceCount(1, 0);
436
437        assertEquals(1, result.size());
438       
439        List<ITaskInstance> expected = new ArrayList<ITaskInstance>();
440        expected.add(session.get(0));
441       
442        assertContains((List<List<ITaskInstance>>) result, expected);
443    }
444
445    @Test
446    public void testGetSequencesWithMostOccurrences_2() throws Exception {
447        TaskInstanceTrie fixture = new TaskInstanceTrie(comparator);
448       
449        fixture.trainSessions(Arrays.asList(session), 3);
450
451        // get all sequences with a minimal length of one that occur exactly once
452        Collection<List<ITaskInstance>> result = fixture.getSequencesWithOccurrenceCount(1, 1);
453
454        assertEquals(11, result.size());
455
456        List<ITaskInstance> expected = new ArrayList<ITaskInstance>();
457        expected.add(session.get(2)); //r
458        expected.add(session.get(0)); //a
459        expected.add(session.get(4)); //c
460        // rac
461        assertContains((List<List<ITaskInstance>>) result, expected);
462
463        expected.clear();
464        expected.add(session.get(0)); //a
465        expected.add(session.get(4)); //c
466        // ac
467        assertContains((List<List<ITaskInstance>>) result, expected);
468
469        expected.add(session.get(0)); //a
470        // aca
471        assertContains((List<List<ITaskInstance>>) result, expected);
472
473        expected.clear();
474        expected.add(session.get(4)); //c
475        // c
476        assertContains((List<List<ITaskInstance>>) result, expected);
477
478        expected.add(session.get(0)); //a
479        // ca
480        assertContains((List<List<ITaskInstance>>) result, expected);
481
482        expected.add(session.get(6)); //d
483        // cad
484        assertContains((List<List<ITaskInstance>>) result, expected);
485
486        expected.clear();
487        expected.add(session.get(0)); //a
488        expected.add(session.get(6)); //d
489        // ad
490        assertContains((List<List<ITaskInstance>>) result, expected);
491
492        expected.add(session.get(0)); //a
493        // ada
494        assertContains((List<List<ITaskInstance>>) result, expected);
495
496        expected.clear();
497        expected.add(session.get(6)); //d
498        // d
499        assertContains((List<List<ITaskInstance>>) result, expected);
500
501        expected.add(session.get(0)); //a
502        // da
503        assertContains((List<List<ITaskInstance>>) result, expected);
504
505        expected.add(session.get(1)); //b
506        // dab
507        assertContains((List<List<ITaskInstance>>) result, expected);
508    }
509
510    @Test
511    public void testGetSequencesWithMostOccurrences_3() throws Exception {
512        TaskInstanceTrie fixture = new TaskInstanceTrie(comparator);
513           
514        fixture.trainSessions(Arrays.asList(session), 3);
515
516        // get all sequences with a minimal length of one that occur exactly twice
517        Collection<List<ITaskInstance>> result = fixture.getSequencesWithOccurrenceCount(1, 2);
518
519        assertEquals(7, result.size());
520
521        List<ITaskInstance> expected = new ArrayList<ITaskInstance>();
522        expected.add(session.get(0)); //a
523        expected.add(session.get(1)); //b
524        // ab
525        assertContains((List<List<ITaskInstance>>) result, expected);
526
527        expected.add(session.get(2)); //r
528        // abr
529        assertContains((List<List<ITaskInstance>>) result, expected);
530
531        expected.clear();
532        expected.add(session.get(1)); //b
533        // b
534        assertContains((List<List<ITaskInstance>>) result, expected);
535
536        expected.add(session.get(2)); //r
537        // br
538        assertContains((List<List<ITaskInstance>>) result, expected);
539
540        expected.add(session.get(0)); //a
541        // bra
542        assertContains((List<List<ITaskInstance>>) result, expected);
543
544        expected.clear();
545        expected.add(session.get(2)); //r
546        // r
547        assertContains((List<List<ITaskInstance>>) result, expected);
548
549        expected.add(session.get(0)); //a
550        // ra
551        assertContains((List<List<ITaskInstance>>) result, expected);
552    }
553
554    @Test
555    public void testGetSequencesWithMostOccurrences_4() throws Exception {
556        TaskInstanceTrie fixture = new TaskInstanceTrie(comparator);
557               
558        fixture.trainSessions(Arrays.asList(session), 3);
559
560        // get all sequences with a minimal length of one that occur exactly three times
561        Collection<List<ITaskInstance>> result = fixture.getSequencesWithOccurrenceCount(1, 3);
562
563        assertEquals(0, result.size());
564    }
565
566    @Test
567    public void testGetSequencesWithMostOccurrences_5() throws Exception {
568        TaskInstanceTrie fixture = new TaskInstanceTrie(comparator);
569               
570        fixture.trainSessions(Arrays.asList(session), 3);
571
572        // get all sequences with a minimal length of one that occur exactly four times
573        Collection<List<ITaskInstance>> result = fixture.getSequencesWithOccurrenceCount(1, 4);
574
575        // as we did not train the last single action, we may expect the "a" action only 4 times
576        assertEquals(1, result.size());
577
578        List<ITaskInstance> expected = new ArrayList<ITaskInstance>();
579        expected.add(session.get(0)); //a
580        assertContains((List<List<ITaskInstance>>) result, expected);
581    }
582
583    @Test
584    public void testGetSequencesWithMostOccurrences_6() throws Exception {
585        TaskInstanceTrie fixture = new TaskInstanceTrie(comparator);
586               
587        fixture.trainSessions(Arrays.asList(session), 3);
588
589        // get all sequences with a minimal length of one that occur exactly five times
590        Collection<List<ITaskInstance>> result = fixture.getSequencesWithOccurrenceCount(1, 5);
591
592        // as we did not train the last single action, we may expect the "a" action only 4 times
593        assertEquals(0, result.size());
594    }
595
596    @Test
597    public void testGetSequencesWithMostOccurrences_7() throws Exception {
598        TaskInstanceTrie fixture = new TaskInstanceTrie(comparator);
599               
600        fixture.trainSessions(Arrays.asList(session), 3);
601
602        // get all sequences with a minimal length of two that occur most often
603        Collection<List<ITaskInstance>> result = fixture.getSequencesWithOccurrenceCount(2, 0);
604
605        assertEquals(5, result.size());
606
607        List<ITaskInstance> expected = new ArrayList<ITaskInstance>();
608        expected.add(session.get(0)); //a
609        expected.add(session.get(1)); //b
610        assertContains((List<List<ITaskInstance>>) result, expected);
611
612        expected.add(session.get(2)); //r
613        assertContains((List<List<ITaskInstance>>) result, expected);
614
615        expected.clear();
616        expected.add(session.get(1)); //b
617        expected.add(session.get(2)); //r
618        assertContains((List<List<ITaskInstance>>) result, expected);
619
620        expected.add(session.get(0)); //a
621        assertContains((List<List<ITaskInstance>>) result, expected);
622
623        expected.clear();
624        expected.add(session.get(2)); //r
625        expected.add(session.get(0)); //a
626        assertContains((List<List<ITaskInstance>>) result, expected);
627    }
628
629    @Test
630    public void testGetSequencesWithMostOccurrences_8() throws Exception {
631        TaskInstanceTrie fixture = new TaskInstanceTrie(comparator);
632           
633        fixture.trainSessions(Arrays.asList(session), 3);
634
635        // get all sequences with a minimal length of two that occur exactly once
636        Collection<List<ITaskInstance>> result = fixture.getSequencesWithOccurrenceCount(2, 1);
637
638        assertEquals(9, result.size());
639
640        List<ITaskInstance> expected = new ArrayList<ITaskInstance>();
641        expected.add(session.get(2)); //r
642        expected.add(session.get(0)); //a
643        expected.add(session.get(4)); //c
644        // rac
645        assertContains((List<List<ITaskInstance>>) result, expected);
646
647        expected.clear();
648        expected.add(session.get(0)); //a
649        expected.add(session.get(4)); //c
650        // ac
651        assertContains((List<List<ITaskInstance>>) result, expected);
652
653        expected.add(session.get(0)); //a
654        // aca
655        assertContains((List<List<ITaskInstance>>) result, expected);
656
657        expected.clear();
658        expected.add(session.get(4)); //c
659        expected.add(session.get(0)); //a
660        // ca
661        assertContains((List<List<ITaskInstance>>) result, expected);
662
663        expected.add(session.get(6)); //d
664        // cad
665        assertContains((List<List<ITaskInstance>>) result, expected);
666
667        expected.clear();
668        expected.add(session.get(0)); //a
669        expected.add(session.get(6)); //d
670        // ad
671        assertContains((List<List<ITaskInstance>>) result, expected);
672
673        expected.add(session.get(0)); //a
674        // ada
675        assertContains((List<List<ITaskInstance>>) result, expected);
676
677        expected.clear();
678        expected.add(session.get(6)); //d
679        expected.add(session.get(0)); //a
680        // da
681        assertContains((List<List<ITaskInstance>>) result, expected);
682
683        expected.add(session.get(1)); //b
684        // dab
685        assertContains((List<List<ITaskInstance>>) result, expected);
686    }
687
688    @Test
689    public void testGetSequencesWithMostOccurrences_9() throws Exception {
690        TaskInstanceTrie fixture = new TaskInstanceTrie(comparator);
691           
692        fixture.trainSessions(Arrays.asList(session), 3);
693
694        // get all sequences with a minimal length of two that occur exactly twice
695        Collection<List<ITaskInstance>> result = fixture.getSequencesWithOccurrenceCount(2, 2);
696
697        assertEquals(5, result.size());
698
699        List<ITaskInstance> expected = new ArrayList<ITaskInstance>();
700        expected.add(session.get(0)); //a
701        expected.add(session.get(1)); //b
702        // ab
703        assertContains((List<List<ITaskInstance>>) result, expected);
704
705        expected.add(session.get(2)); //r
706        // abr
707        assertContains((List<List<ITaskInstance>>) result, expected);
708
709        expected.clear();
710        expected.add(session.get(1)); //b
711        expected.add(session.get(2)); //r
712        // br
713        assertContains((List<List<ITaskInstance>>) result, expected);
714
715        expected.add(session.get(0)); //a
716        // bra
717        assertContains((List<List<ITaskInstance>>) result, expected);
718
719        expected.clear();
720        expected.add(session.get(2)); //r
721        expected.add(session.get(0)); //a
722        // ra
723        assertContains((List<List<ITaskInstance>>) result, expected);
724    }
725
726    @Test
727    public void testGetSequencesWithMostOccurrences_10() throws Exception {
728        TaskInstanceTrie fixture = new TaskInstanceTrie(comparator);
729               
730        fixture.trainSessions(Arrays.asList(session), 3);
731
732        // get all sequences with a minimal length of two that occur exactly three times
733        Collection<List<ITaskInstance>> result = fixture.getSequencesWithOccurrenceCount(2, 3);
734
735        assertEquals(0, result.size());
736    }
737
738    @Test
739    public void testGetSequencesWithMostOccurrences_11() throws Exception {
740        TaskInstanceTrie fixture = new TaskInstanceTrie(comparator);
741               
742        fixture.trainSessions(Arrays.asList(session), 3);
743
744        // get all sequences with a minimal length of three that occur most often
745        Collection<List<ITaskInstance>> result = fixture.getSequencesWithOccurrenceCount(3, 0);
746
747        assertEquals(2, result.size());
748
749        List<ITaskInstance> expected = new ArrayList<ITaskInstance>();
750        expected.add(session.get(0)); //a
751        expected.add(session.get(1)); //b
752        expected.add(session.get(2)); //r
753        assertContains((List<List<ITaskInstance>>) result, expected);
754
755        expected.clear();
756        expected.add(session.get(1)); //b
757        expected.add(session.get(2)); //r
758        expected.add(session.get(0)); //a
759        assertContains((List<List<ITaskInstance>>) result, expected);
760    }
761
762    @Test
763    public void testGetSequencesWithMostOccurrences_12() throws Exception {
764        TaskInstanceTrie fixture = new TaskInstanceTrie(comparator);
765               
766        fixture.trainSessions(Arrays.asList(session), 3);
767
768        // get all sequences with a minimal length of three that occur exactly once
769        Collection<List<ITaskInstance>> result = fixture.getSequencesWithOccurrenceCount(3, 1);
770
771        assertEquals(5, result.size());
772
773        List<ITaskInstance> expected = new ArrayList<ITaskInstance>();
774        expected.add(session.get(2)); //r
775        expected.add(session.get(0)); //a
776        expected.add(session.get(4)); //c
777        // rac
778        assertContains((List<List<ITaskInstance>>) result, expected);
779
780        expected.clear();
781        expected.add(session.get(0)); //a
782        expected.add(session.get(4)); //c
783        expected.add(session.get(0)); //a
784        // aca
785        assertContains((List<List<ITaskInstance>>) result, expected);
786
787        expected.clear();
788        expected.add(session.get(4)); //c
789        expected.add(session.get(0)); //a
790        expected.add(session.get(6)); //d
791        // cad
792        assertContains((List<List<ITaskInstance>>) result, expected);
793
794        expected.clear();
795        expected.add(session.get(0)); //a
796        expected.add(session.get(6)); //d
797        expected.add(session.get(0)); //a
798        // ada
799        assertContains((List<List<ITaskInstance>>) result, expected);
800
801        expected.clear();
802        expected.add(session.get(6)); //d
803        expected.add(session.get(0)); //a
804        expected.add(session.get(1)); //b
805        // dab
806        assertContains((List<List<ITaskInstance>>) result, expected);
807    }
808
809    @Test
810    public void testGetSequencesWithMostOccurrences_13() throws Exception {
811        TaskInstanceTrie fixture = new TaskInstanceTrie(comparator);
812               
813        fixture.trainSessions(Arrays.asList(session), 3);
814
815        // get all sequences with a minimal length of four that occur most often
816        Collection<List<ITaskInstance>> result = fixture.getSequencesWithOccurrenceCount(4, 0);
817
818        // none of these exist, as the tree is only trained with sequences of length 3
819        assertEquals(0, result.size());
820    }
821
822    @Test
823    public void testGetSequencesWithMostOccurrences_14() throws Exception {
824        TaskInstanceTrie fixture = new TaskInstanceTrie(comparator);
825                   
826        fixture.trainSessions(Arrays.asList(session), 3);
827
828        // get all sequences with a minimal length of four that occur exactly once
829        Collection<List<ITaskInstance>> result = fixture.getSequencesWithOccurrenceCount(4, 1);
830
831        // none of these exist, as the tree is only trained with sequences of length 3
832        assertEquals(0, result.size());
833    }
834
835    @Test
836    public void testGetCount_1() throws Exception {
837        TaskInstanceTrie fixture = new TaskInstanceTrie(comparator);
838                       
839        fixture.trainSessions(Arrays.asList(session), 3);
840
841        List<ITaskInstance> subSequence = new ArrayList<ITaskInstance>();
842        subSequence.add(session.get(0)); //a
843
844        int result = fixture.getCount(subSequence);
845
846        // as we did not train the last single action, we may expect the "a" action only 4 times
847        assertEquals(4, result);
848    }
849
850    @Test
851    public void testGetCount_2() throws Exception {
852        TaskInstanceTrie fixture = new TaskInstanceTrie(comparator);
853                           
854        fixture.trainSessions(Arrays.asList(session), 3);
855
856        List<ITaskInstance> subSequence = new ArrayList<ITaskInstance>();
857        subSequence.add(session.get(0)); //a
858        subSequence.add(session.get(1)); //b
859
860        int result = fixture.getCount(subSequence);
861
862        assertEquals(2, result);
863    }
864
865    @Test
866    public void testGetCount_3() throws Exception {
867        TaskInstanceTrie fixture = new TaskInstanceTrie(comparator);
868                           
869        fixture.trainSessions(Arrays.asList(session), 3);
870
871        List<ITaskInstance> subSequence = new ArrayList<ITaskInstance>();
872        subSequence.add(taskFactory.createNewTaskInstance(taskFactory.createNewSequence()));
873
874        int result = fixture.getCount(subSequence);
875
876        assertEquals(0, result);
877    }
878
879    @Test
880    public void testGetCount_4() throws Exception {
881        TaskInstanceTrie fixture = new TaskInstanceTrie(comparator);
882                           
883        fixture.trainSessions(Arrays.asList(session), 3);
884
885        List<ITaskInstance> subSequence = new ArrayList<ITaskInstance>();
886
887        int result = fixture.getCount(subSequence, session.get(0)); //a
888
889        // as we did not train the last single action, we may expect the "a" action only 4 times
890        assertEquals(4, result);
891    }
892
893    @Test
894    public void testGetCount_5() throws Exception {
895        TaskInstanceTrie fixture = new TaskInstanceTrie(comparator);
896                               
897        fixture.trainSessions(Arrays.asList(session), 3);
898
899        List<ITaskInstance> subSequence = new ArrayList<ITaskInstance>();
900        subSequence.add(session.get(0)); //a
901        subSequence.add(session.get(1)); //b
902
903        int result = fixture.getCount(subSequence, session.get(2)); //r
904
905        assertEquals(2, result);
906    }
907
908    @Test
909    public void testGetCount_6() throws Exception {
910        TaskInstanceTrie fixture = new TaskInstanceTrie(comparator);
911                               
912        fixture.trainSessions(Arrays.asList(session), 3);
913
914        List<ITaskInstance> subSequence = new ArrayList<ITaskInstance>();
915
916        int result = fixture.getCount
917            (subSequence, taskFactory.createNewTaskInstance(taskFactory.createNewSequence()));
918
919        assertEquals(0, result);
920    }
921
922    @Test
923    public void testGetFollowingSymbols_1() throws Exception {
924        TaskInstanceTrie fixture = new TaskInstanceTrie(comparator);
925                                   
926        fixture.trainSessions(Arrays.asList(session), 3);
927
928        List<ITaskInstance> subSequence = new ArrayList<ITaskInstance>();
929        subSequence.add(session.get(0)); //a
930        Collection<ITaskInstance> expected = new ArrayList<ITaskInstance>();
931        expected.add(session.get(1)); //b
932        expected.add(session.get(4)); //c
933        expected.add(session.get(6)); //d
934
935        Collection<ITaskInstance> result = fixture.getFollowingSymbols(subSequence);
936
937        assertCollectionContent(expected, result);
938    }
939
940    @Test
941    public void testGetFollowingSymbols_2() throws Exception {
942        TaskInstanceTrie fixture = new TaskInstanceTrie(comparator);
943                                       
944        fixture.trainSessions(Arrays.asList(session), 3);
945
946        List<ITaskInstance> subSequence = new ArrayList<ITaskInstance>();
947        subSequence.add(session.get(0)); //a
948        subSequence.add(session.get(1)); //b
949        subSequence.add(session.get(2)); //r
950
951        Collection<ITaskInstance> result = fixture.getFollowingSymbols(subSequence);
952
953        assertEquals(0, result.size());
954    }
955
956    @Test
957    public void testGetFollowingSymbols_3() throws Exception {
958        TaskInstanceTrie fixture = new TaskInstanceTrie(comparator);
959                                       
960        fixture.trainSessions(Arrays.asList(session), 3);
961
962        List<ITaskInstance> subSequence = new ArrayList<ITaskInstance>();
963        subSequence.add(taskFactory.createNewTaskInstance(taskFactory.createNewSequence()));
964
965        Collection<ITaskInstance> result = fixture.getFollowingSymbols(subSequence);
966
967        assertEquals(0, result.size());
968    }
969
970    @Test
971    public void testGetNumLeafAncestors_1() throws Exception {
972        TaskInstanceTrie fixture = new TaskInstanceTrie(comparator);
973                                           
974        fixture.trainSessions(Arrays.asList(session), 3);
975
976        int result = fixture.getNumLeafAncestors();
977
978        assertEquals(7, result);
979    }
980
981    @Test
982    public void testGetNumLeafs_1() throws Exception {
983        TaskInstanceTrie fixture = new TaskInstanceTrie(comparator);
984                                           
985        fixture.trainSessions(Arrays.asList(session), 3);
986
987        int result = fixture.getNumLeafs();
988
989        assertEquals(7, result);
990    }
991
992    @Test
993    public void testGetNumSymbols_1() throws Exception {
994        TaskInstanceTrie fixture = new TaskInstanceTrie(comparator);
995                                           
996        fixture.trainSessions(Arrays.asList(session), 3);
997
998
999        int result = fixture.getNumSymbols();
1000
1001        assertEquals(5, result);
1002    }
1003
1004    @Test
1005    public void testLargeTaskInstanceTrie_1() throws Exception {
1006        TaskInstanceTrie fixture = new TaskInstanceTrie(comparator);
1007
1008        int order = 2;
1009       
1010        TaskInstanceTrieTester tester = new TaskInstanceTrieTester(3, 50, order);
1011
1012        long start = System.currentTimeMillis();
1013        fixture.trainSessions(Arrays.asList(tester.userSession), order);
1014        System.out.println("testing session with 50 task instances and 3 symbols took " +
1015                           (System.currentTimeMillis() - start) + "ms");
1016       
1017        fixture.process(tester);
1018       
1019        // do not check if counts is empty, as some sequences may not be part of the reduced trie
1020        // and may therefore not be processed by the tester.
1021        //assertTrue(tester.counts.isEmpty());
1022    }
1023
1024    @Test
1025    public void testLargeTaskInstanceTrie_2() throws Exception {
1026        TaskInstanceTrie fixture = new TaskInstanceTrie(comparator);
1027
1028        int order = 2;
1029       
1030        TaskInstanceTrieTester tester = new TaskInstanceTrieTester(3, 10000, order);
1031
1032        long start = System.currentTimeMillis();
1033        fixture.trainSessions(Arrays.asList(tester.userSession), order);
1034        System.out.println("testing session with 10000 task instances and 3 symbols took " +
1035                           (System.currentTimeMillis() - start) + "ms");
1036       
1037        fixture.process(tester);
1038       
1039        // do not check if counts is empty, as some sequences may not be part of the reduced trie
1040        // and may therefore not be processed by the tester.
1041        //assertTrue(tester.counts.isEmpty());
1042    }
1043
1044    @Test
1045    public void testLargeTaskInstanceTrie_3() throws Exception {
1046        TaskInstanceTrie fixture = new TaskInstanceTrie(comparator);
1047
1048        int order = 2;
1049       
1050        TaskInstanceTrieTester tester = new TaskInstanceTrieTester(30, 10000, order);
1051
1052        long start = System.currentTimeMillis();
1053        fixture.trainSessions(Arrays.asList(tester.userSession), order);
1054        System.out.println("testing session with 10000 task instances and 30 symbols took " +
1055                           (System.currentTimeMillis() - start) + "ms");
1056       
1057        fixture.process(tester);
1058       
1059        // do not check if counts is empty, as some sequences may not be part of the reduced trie
1060        // and may therefore not be processed by the tester.
1061        //assertTrue(tester.counts.isEmpty());
1062    }
1063
1064    @Test
1065    public void testLargeTaskInstanceTrie_4() throws Exception {
1066        TaskInstanceTrie fixture = new TaskInstanceTrie(comparator);
1067
1068        int order = 2;
1069       
1070        TaskInstanceTrieTester tester = new TaskInstanceTrieTester(300, 10000, order);
1071
1072        long start = System.currentTimeMillis();
1073        fixture.trainSessions(Arrays.asList(tester.userSession), order);
1074        System.out.println("testing session with 10000 task instances and 300 symbols took " +
1075                           (System.currentTimeMillis() - start) + "ms");
1076       
1077        fixture.process(tester);
1078       
1079        // do not check if counts is empty, as some sequences may not be part of the reduced trie
1080        // and may therefore not be processed by the tester.
1081        //assertTrue(tester.counts.isEmpty());
1082    }
1083
1084    @Test
1085    public void testLargeTaskInstanceTrie_5() throws Exception {
1086        TaskInstanceTrie fixture = new TaskInstanceTrie(comparator);
1087
1088        int order = 2;
1089       
1090        TaskInstanceTrieTester tester = new TaskInstanceTrieTester(1000, 10000, order);
1091
1092        long start = System.currentTimeMillis();
1093        fixture.trainSessions(Arrays.asList(tester.userSession), order);
1094        System.out.println("testing session with 10000 task instances and 1000 symbols took " +
1095                           (System.currentTimeMillis() - start) + "ms");
1096       
1097        fixture.process(tester);
1098       
1099        // do not check if counts is empty, as some sequences may not be part of the reduced trie
1100        // and may therefore not be processed by the tester.
1101        //assertTrue(tester.counts.isEmpty());
1102    }
1103
1104    @Test
1105    public void testLargeTaskInstanceTrie_6() throws Exception {
1106        TaskInstanceTrie fixture = new TaskInstanceTrie(comparator);
1107
1108        int order = 3;
1109       
1110        TaskInstanceTrieTester tester = new TaskInstanceTrieTester(3, 50, order);
1111
1112        long start = System.currentTimeMillis();
1113        fixture.trainSessions(Arrays.asList(tester.userSession), order);
1114        System.out.println("testing session with 50 task instances and 3 symbols took " +
1115                           (System.currentTimeMillis() - start) + "ms");
1116       
1117        fixture.process(tester);
1118       
1119        // do not check if counts is empty, as some sequences may not be part of the reduced trie
1120        // and may therefore not be processed by the tester.
1121        //assertTrue(tester.counts.isEmpty());
1122    }
1123
1124    @Test
1125    public void testLargeTaskInstanceTrie_7() throws Exception {
1126        TaskInstanceTrie fixture = new TaskInstanceTrie(comparator);
1127
1128        int order = 3;
1129       
1130        TaskInstanceTrieTester tester = new TaskInstanceTrieTester(3, 10000, order);
1131
1132        long start = System.currentTimeMillis();
1133        fixture.trainSessions(Arrays.asList(tester.userSession), order);
1134        System.out.println("testing session with 10000 task instances and 3 symbols took " +
1135                           (System.currentTimeMillis() - start) + "ms");
1136       
1137        fixture.process(tester);
1138       
1139        // do not check if counts is empty, as some sequences may not be part of the reduced trie
1140        // and may therefore not be processed by the tester.
1141        //assertTrue(tester.counts.isEmpty());
1142    }
1143
1144    @Test
1145    public void testLargeTaskInstanceTrie_8() throws Exception {
1146        TaskInstanceTrie fixture = new TaskInstanceTrie(comparator);
1147
1148        int order = 3;
1149       
1150        TaskInstanceTrieTester tester = new TaskInstanceTrieTester(30, 10000, order);
1151
1152        long start = System.currentTimeMillis();
1153        fixture.trainSessions(Arrays.asList(tester.userSession), order);
1154        System.out.println("testing session with 10000 task instances and 30 symbols took " +
1155                           (System.currentTimeMillis() - start) + "ms");
1156       
1157        fixture.process(tester);
1158       
1159        // do not check if counts is empty, as some sequences may not be part of the reduced trie
1160        // and may therefore not be processed by the tester.
1161        //assertTrue(tester.counts.isEmpty());
1162    }
1163
1164    @Test
1165    public void testLargeTaskInstanceTrie_9() throws Exception {
1166        TaskInstanceTrie fixture = new TaskInstanceTrie(comparator);
1167
1168        int order = 3;
1169       
1170        TaskInstanceTrieTester tester = new TaskInstanceTrieTester(300, 10000, order);
1171
1172        long start = System.currentTimeMillis();
1173        fixture.trainSessions(Arrays.asList(tester.userSession), order);
1174        System.out.println("testing session with 10000 task instances and 300 symbols took " +
1175                           (System.currentTimeMillis() - start) + "ms");
1176       
1177        fixture.process(tester);
1178       
1179        // do not check if counts is empty, as some sequences may not be part of the reduced trie
1180        // and may therefore not be processed by the tester.
1181        //assertTrue(tester.counts.isEmpty());
1182    }
1183
1184    @Test
1185    public void testLargeTaskInstanceTrie_10() throws Exception {
1186        TaskInstanceTrie fixture = new TaskInstanceTrie(comparator);
1187
1188        int order = 3;
1189       
1190        TaskInstanceTrieTester tester = new TaskInstanceTrieTester(1000, 10000, order);
1191
1192        long start = System.currentTimeMillis();
1193        fixture.trainSessions(Arrays.asList(tester.userSession), order);
1194        System.out.println("testing session with 10000 task instances and 1000 symbols took " +
1195                           (System.currentTimeMillis() - start) + "ms");
1196       
1197        fixture.process(tester);
1198       
1199        // do not check if counts is empty, as some sequences may not be part of the reduced trie
1200        // and may therefore not be processed by the tester.
1201        //assertTrue(tester.counts.isEmpty());
1202    }
1203
1204    @Test
1205    public void testLargeTaskInstanceTrie_11() throws Exception {
1206        TaskInstanceTrie fixture = new TaskInstanceTrie(comparator);
1207
1208        int order = 4;
1209       
1210        TaskInstanceTrieTester tester = new TaskInstanceTrieTester(3, 50, order);
1211
1212        long start = System.currentTimeMillis();
1213        fixture.trainSessions(Arrays.asList(tester.userSession), order);
1214        System.out.println("testing session with 50 task instances and 3 symbols took " +
1215                           (System.currentTimeMillis() - start) + "ms");
1216       
1217        fixture.process(tester);
1218       
1219        // do not check if counts is empty, as some sequences may not be part of the reduced trie
1220        // and may therefore not be processed by the tester.
1221        //assertTrue(tester.counts.isEmpty());
1222    }
1223
1224    @Test
1225    public void testLargeTaskInstanceTrie_12() throws Exception {
1226        TaskInstanceTrie fixture = new TaskInstanceTrie(comparator);
1227
1228        int order = 4;
1229       
1230        TaskInstanceTrieTester tester = new TaskInstanceTrieTester(3, 10000, order);
1231
1232        long start = System.currentTimeMillis();
1233        fixture.trainSessions(Arrays.asList(tester.userSession), order);
1234        System.out.println("testing session with 10000 task instances and 3 symbols took " +
1235                           (System.currentTimeMillis() - start) + "ms");
1236       
1237        fixture.process(tester);
1238       
1239        // do not check if counts is empty, as some sequences may not be part of the reduced trie
1240        // and may therefore not be processed by the tester.
1241        //assertTrue(tester.counts.isEmpty());
1242    }
1243
1244    @Test
1245    public void testLargeTaskInstanceTrie_13() throws Exception {
1246        TaskInstanceTrie fixture = new TaskInstanceTrie(comparator);
1247
1248        int order = 4;
1249       
1250        TaskInstanceTrieTester tester = new TaskInstanceTrieTester(30, 10000, order);
1251
1252        long start = System.currentTimeMillis();
1253        fixture.trainSessions(Arrays.asList(tester.userSession), order);
1254        System.out.println("testing session with 10000 task instances and 30 symbols took " +
1255                           (System.currentTimeMillis() - start) + "ms");
1256       
1257        fixture.process(tester);
1258       
1259        // do not check if counts is empty, as some sequences may not be part of the reduced trie
1260        // and may therefore not be processed by the tester.
1261        //assertTrue(tester.counts.isEmpty());
1262    }
1263
1264    @Test
1265    public void testLargeTaskInstanceTrie_14() throws Exception {
1266        TaskInstanceTrie fixture = new TaskInstanceTrie(comparator);
1267
1268        int order = 4;
1269       
1270        TaskInstanceTrieTester tester = new TaskInstanceTrieTester(300, 10000, order);
1271
1272        long start = System.currentTimeMillis();
1273        fixture.trainSessions(Arrays.asList(tester.userSession), order);
1274        System.out.println("testing session with 10000 task instances and 300 symbols took " +
1275                           (System.currentTimeMillis() - start) + "ms");
1276       
1277        fixture.process(tester);
1278       
1279        // do not check if counts is empty, as some sequences may not be part of the reduced trie
1280        // and may therefore not be processed by the tester.
1281        //assertTrue(tester.counts.isEmpty());
1282    }
1283
1284    @Test
1285    public void testLargeTaskInstanceTrie_15() throws Exception {
1286        TaskInstanceTrie fixture = new TaskInstanceTrie(comparator);
1287
1288        int order = 4;
1289       
1290        TaskInstanceTrieTester tester = new TaskInstanceTrieTester(1000, 10000, order);
1291
1292        long start = System.currentTimeMillis();
1293        fixture.trainSessions(Arrays.asList(tester.userSession), order);
1294        System.out.println("testing session with 10000 task instances and 1000 symbols took " +
1295                           (System.currentTimeMillis() - start) + "ms");
1296       
1297        fixture.process(tester);
1298       
1299        // do not check if counts is empty, as some sequences may not be part of the reduced trie
1300        // and may therefore not be processed by the tester.
1301        //assertTrue(tester.counts.isEmpty());
1302    }
1303
1304    @Test
1305    public void testLargeTaskInstanceTrie_16() throws Exception {
1306        TaskInstanceTrie fixture = new TaskInstanceTrie(comparator);
1307
1308        int order = 5;
1309       
1310        TaskInstanceTrieTester tester = new TaskInstanceTrieTester(3, 50, order);
1311
1312        long start = System.currentTimeMillis();
1313        fixture.trainSessions(Arrays.asList(tester.userSession), order);
1314        System.out.println("testing session with 50 task instances and 3 symbols took " +
1315                           (System.currentTimeMillis() - start) + "ms");
1316       
1317        fixture.process(tester);
1318       
1319        // do not check if counts is empty, as some sequences may not be part of the reduced trie
1320        // and may therefore not be processed by the tester.
1321        //assertTrue(tester.counts.isEmpty());
1322    }
1323
1324    @Test
1325    public void testLargeTaskInstanceTrie_17() throws Exception {
1326        TaskInstanceTrie fixture = new TaskInstanceTrie(comparator);
1327
1328        int order = 5;
1329       
1330        TaskInstanceTrieTester tester = new TaskInstanceTrieTester(3, 10000, order);
1331
1332        long start = System.currentTimeMillis();
1333        fixture.trainSessions(Arrays.asList(tester.userSession), order);
1334        System.out.println("testing session with 10000 task instances and 3 symbols took " +
1335                           (System.currentTimeMillis() - start) + "ms");
1336       
1337        fixture.process(tester);
1338       
1339        // do not check if counts is empty, as some sequences may not be part of the reduced trie
1340        // and may therefore not be processed by the tester.
1341        //assertTrue(tester.counts.isEmpty());
1342    }
1343
1344    @Test
1345    public void testLargeTaskInstanceTrie_18() throws Exception {
1346        TaskInstanceTrie fixture = new TaskInstanceTrie(comparator);
1347
1348        int order = 5;
1349       
1350        TaskInstanceTrieTester tester = new TaskInstanceTrieTester(30, 10000, order);
1351
1352        long start = System.currentTimeMillis();
1353        fixture.trainSessions(Arrays.asList(tester.userSession), order);
1354        System.out.println("testing session with 10000 task instances and 30 symbols took " +
1355                           (System.currentTimeMillis() - start) + "ms");
1356       
1357        fixture.process(tester);
1358       
1359        // do not check if counts is empty, as some sequences may not be part of the reduced trie
1360        // and may therefore not be processed by the tester.
1361        //assertTrue(tester.counts.isEmpty());
1362    }
1363
1364    @Test
1365    public void testLargeTaskInstanceTrie_19() throws Exception {
1366        TaskInstanceTrie fixture = new TaskInstanceTrie(comparator);
1367
1368        int order = 5;
1369       
1370        TaskInstanceTrieTester tester = new TaskInstanceTrieTester(300, 10000, order);
1371
1372        long start = System.currentTimeMillis();
1373        fixture.trainSessions(Arrays.asList(tester.userSession), order);
1374        System.out.println("testing session with 10000 task instances and 300 symbols took " +
1375                           (System.currentTimeMillis() - start) + "ms");
1376       
1377        fixture.process(tester);
1378       
1379        // do not check if counts is empty, as some sequences may not be part of the reduced trie
1380        // and may therefore not be processed by the tester.
1381        //assertTrue(tester.counts.isEmpty());
1382    }
1383
1384    @Test
1385    public void testLargeTaskInstanceTrie_20() throws Exception {
1386        TaskInstanceTrie fixture = new TaskInstanceTrie(comparator);
1387
1388        int order = 5;
1389       
1390        TaskInstanceTrieTester tester = new TaskInstanceTrieTester(1000, 10000, order);
1391
1392        long start = System.currentTimeMillis();
1393        fixture.trainSessions(Arrays.asList(tester.userSession), order);
1394        System.out.println("testing session with 10000 task instances and 1000 symbols took " +
1395                           (System.currentTimeMillis() - start) + "ms");
1396       
1397        fixture.process(tester);
1398       
1399        // do not check if counts is empty, as some sequences may not be part of the reduced trie
1400        // and may therefore not be processed by the tester.
1401        //assertTrue(tester.counts.isEmpty());
1402    }
1403
1404    @Test
1405    public void testLargeTaskInstanceTrie_21() throws Exception {
1406        TaskInstanceTrie fixture = new TaskInstanceTrie(comparator);
1407
1408        int order = 6;
1409       
1410        TaskInstanceTrieTester tester = new TaskInstanceTrieTester(3, 50, order);
1411
1412        long start = System.currentTimeMillis();
1413        fixture.trainSessions(Arrays.asList(tester.userSession), order);
1414        System.out.println("testing session with 50 task instances and 3 symbols took " +
1415                           (System.currentTimeMillis() - start) + "ms");
1416       
1417        fixture.process(tester);
1418       
1419        // do not check if counts is empty, as some sequences may not be part of the reduced trie
1420        // and may therefore not be processed by the tester.
1421        //assertTrue(tester.counts.isEmpty());
1422    }
1423
1424    @Test
1425    public void testLargeTaskInstanceTrie_22() throws Exception {
1426        TaskInstanceTrie fixture = new TaskInstanceTrie(comparator);
1427
1428        int order = 6;
1429       
1430        TaskInstanceTrieTester tester = new TaskInstanceTrieTester(3, 10000, order);
1431
1432        long start = System.currentTimeMillis();
1433        fixture.trainSessions(Arrays.asList(tester.userSession), order);
1434        System.out.println("testing session with 10000 task instances and 3 symbols took " +
1435                           (System.currentTimeMillis() - start) + "ms");
1436       
1437        fixture.process(tester);
1438       
1439        // do not check if counts is empty, as some sequences may not be part of the reduced trie
1440        // and may therefore not be processed by the tester.
1441        //assertTrue(tester.counts.isEmpty());
1442    }
1443
1444    @Test
1445    public void testLargeTaskInstanceTrie_23() throws Exception {
1446        TaskInstanceTrie fixture = new TaskInstanceTrie(comparator);
1447
1448        int order = 6;
1449       
1450        TaskInstanceTrieTester tester = new TaskInstanceTrieTester(30, 10000, order);
1451
1452        long start = System.currentTimeMillis();
1453        fixture.trainSessions(Arrays.asList(tester.userSession), order);
1454        System.out.println("testing session with 10000 task instances and 30 symbols took " +
1455                           (System.currentTimeMillis() - start) + "ms");
1456       
1457        fixture.process(tester);
1458       
1459        // do not check if counts is empty, as some sequences may not be part of the reduced trie
1460        // and may therefore not be processed by the tester.
1461        //assertTrue(tester.counts.isEmpty());
1462    }
1463
1464    @Test
1465    public void testLargeTaskInstanceTrie_24() throws Exception {
1466        TaskInstanceTrie fixture = new TaskInstanceTrie(comparator);
1467
1468        int order = 6;
1469       
1470        TaskInstanceTrieTester tester = new TaskInstanceTrieTester(300, 10000, order);
1471
1472        long start = System.currentTimeMillis();
1473        fixture.trainSessions(Arrays.asList(tester.userSession), order);
1474        System.out.println("testing session with 10000 task instances and 300 symbols took " +
1475                           (System.currentTimeMillis() - start) + "ms");
1476       
1477        fixture.process(tester);
1478       
1479        // do not check if counts is empty, as some sequences may not be part of the reduced trie
1480        // and may therefore not be processed by the tester.
1481        //assertTrue(tester.counts.isEmpty());
1482    }
1483
1484    @Test
1485    public void testLargeTaskInstanceTrie_25() throws Exception {
1486        TaskInstanceTrie fixture = new TaskInstanceTrie(comparator);
1487
1488        int order = 6;
1489       
1490        TaskInstanceTrieTester tester = new TaskInstanceTrieTester(1000, 10000, order);
1491
1492        long start = System.currentTimeMillis();
1493        fixture.trainSessions(Arrays.asList(tester.userSession), order);
1494        System.out.println("testing session with 10000 task instances and 1000 symbols took " +
1495                           (System.currentTimeMillis() - start) + "ms");
1496       
1497        fixture.process(tester);
1498       
1499        // do not check if counts is empty, as some sequences may not be part of the reduced trie
1500        // and may therefore not be processed by the tester.
1501        //assertTrue(tester.counts.isEmpty());
1502    }
1503
1504    /**
1505     *
1506     */
1507    private void assertContains(List<List<ITaskInstance>> listOfList,
1508                                List<ITaskInstance>       containedList)
1509    {
1510        boolean found = false;
1511        for (List<ITaskInstance> candidate : listOfList) {
1512            if (candidate.size() == containedList.size()) {
1513                found = true;
1514                for (int i = 0; i < containedList.size(); i++) {
1515                    if (!comparator.equals(candidate.get(0), containedList.get(0))) {
1516                        found = false;
1517                        break;
1518                    }
1519                }
1520               
1521                if (found) {
1522                    break;
1523                }
1524            }
1525        }
1526           
1527        assertTrue(found);
1528    }
1529
1530    public static void main(String[] args) {
1531        new org.junit.runner.JUnitCore().run(TaskInstanceTrieTest.class);
1532    }
1533   
1534    /**
1535     * <p>
1536     * class internally used for testing large tries.
1537     * </p>
1538     *
1539     * @author Patrick Harms
1540     */
1541    private class TaskInstanceTrieTester implements TrieProcessor<ITaskInstance> {
1542       
1543        /**
1544         * the symbols used for testing the trie
1545         */
1546        private Map<Integer, ITaskInstance> symbols = new HashMap<Integer, ITaskInstance>();
1547
1548        /**
1549         * the simulated sequence
1550         */
1551        private IUserSession userSession;
1552
1553        /**
1554         * the trained order of the tested trie
1555         */
1556        private int maxOrder;
1557       
1558        /**
1559         * the expected counts of subsequences
1560         */
1561        private Map<Long, Integer> counts = new HashMap<Long, Integer>();
1562       
1563        /**
1564         * the maximal observed count of a subsequence
1565         */
1566        private int maxCount = 0;
1567
1568        /**
1569         * generates a simulated sequence and thereby stores the expected counts of the
1570         * subsequences up to max order in a map. The technique uses integer and long values
1571         * to be efficient and to allow testing with large sequences and symbol numbers. However,
1572         * the technique is restricted to 1024 different symbols and a maximum tree depth of 6.
1573         * The tester is also used as a trie processor to check for any node in the tree, if the
1574         * trie calculated the count correctly and if it did not create too many nodes.
1575         */
1576        public TaskInstanceTrieTester(int noOfSymbols, int sequenceLength, int maxOrder) {
1577            if (noOfSymbols > 1024) {
1578                throw new IllegalArgumentException("too large number of symbols");
1579            }
1580            if (maxOrder > 6) {
1581                throw new IllegalArgumentException("too large number of symbols");
1582            }
1583           
1584            StringBuffer dummyUserSessionDef = new StringBuffer("UserSession {");
1585            for (int i = 0; i < noOfSymbols; i++) {
1586                dummyUserSessionDef.append("  Event action");
1587                dummyUserSessionDef.append(i);
1588                dummyUserSessionDef.append(" {}");
1589            }
1590            dummyUserSessionDef.append("}");
1591           
1592            IUserSession dummySession =
1593                (IUserSession) decoder.decode(dummyUserSessionDef.toString());
1594           
1595            for (int i = 0; i < dummySession.size(); i++) {
1596                this.symbols.put(i, dummySession.get(i));
1597            }
1598           
1599            this.maxOrder = maxOrder;
1600           
1601            dummyUserSessionDef = new StringBuffer("UserSession {");
1602            int[] symbolIds = new int[sequenceLength];
1603
1604            for (int i = 0; i < sequenceLength; i++) {
1605                int symbolIndex = (int) (Math.random() * noOfSymbols);
1606                dummyUserSessionDef.append("  Event action");
1607                dummyUserSessionDef.append(symbolIndex);
1608                dummyUserSessionDef.append(" {}");
1609               
1610                symbolIds[i] = symbolIndex;
1611               
1612                if ((i - maxOrder + 1) >= 0) {
1613                    storeCounts(symbolIds, i - maxOrder + 1, i);
1614                }
1615            }
1616            dummyUserSessionDef.append("}");
1617           
1618            this.userSession = (IUserSession) decoder.decode(dummyUserSessionDef.toString());
1619           
1620            for (int i = sequenceLength - maxOrder + 1; i < sequenceLength; i++) {
1621                storeCounts(symbolIds, i, sequenceLength - 1);
1622            }
1623        }
1624
1625        /**
1626         * <p>
1627         * stores the counts for the subsequence denoted by the start and end index (inclusive).
1628         * </p>
1629         */
1630        private void storeCounts(int[] sequence, int startIndex, int endIndex) {
1631            long key = 0;
1632           
1633            for (int i = startIndex; i <= endIndex; i++) {
1634                key = key << 10;
1635                key += 1 + sequence[i];
1636           
1637                Integer count = this.counts.get(key);
1638                if (count == null) {
1639                    count = 0;
1640                }
1641           
1642                //System.out.println(key + "  " + (count + 1));
1643               
1644                count++;
1645                this.counts.put(key, count);
1646               
1647                maxCount = Math.max(count, maxCount);
1648            }
1649        }
1650
1651        /* (non-Javadoc)
1652         * @see de.ugoe.cs.autoquest.usageprofiles.TaskInstanceTrieProcessor#process(List, int)
1653         */
1654        @Override
1655        public TrieProcessor.Result process(List<ITaskInstance> sequence, int count) {
1656            long key = 0;
1657           
1658            for (ITaskInstance symbol : sequence) {
1659                int symbolIndex = -1;
1660               
1661                for (Map.Entry<Integer, ITaskInstance> entry : symbols.entrySet()) {
1662                    if (comparator.equals(entry.getValue(), symbol)) {
1663                        symbolIndex = entry.getKey();
1664                        break;
1665                    }
1666                }
1667               
1668                assertTrue("could not find symbol", symbolIndex > -1);
1669               
1670                key = key << 10;
1671                key += 1 + symbolIndex;
1672            }
1673           
1674            Integer expectedCount = this.counts.remove(key);
1675            assertNotNull(expectedCount);
1676           
1677            if (count == maxCount) {
1678                assertEquals(expectedCount.intValue(), count);
1679            }
1680            else {
1681                assertTrue(count < maxCount);
1682            }
1683           
1684            assertTrue(sequence.size() <= this.maxOrder);
1685           
1686            return TrieProcessor.Result.CONTINUE;
1687        }
1688
1689    }
1690}
Note: See TracBrowser for help on using the repository browser.