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

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