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

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