source: trunk/autoquest-core-tasktrees/src/main/java/de/ugoe/cs/autoquest/tasktrees/temporalrelation/SequenceForTaskDetectionRule.java @ 1287

Last change on this file since 1287 was 1287, checked in by pharms, 11 years ago
  • added counting of task occurrences
File size: 34.9 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.HashMap;
18import java.util.HashSet;
19import java.util.Iterator;
20import java.util.LinkedList;
21import java.util.List;
22import java.util.Map;
23import java.util.Set;
24import java.util.logging.Level;
25
26import de.ugoe.cs.autoquest.tasktrees.taskequality.TaskEquality;
27import de.ugoe.cs.autoquest.tasktrees.treeifc.IIteration;
28import de.ugoe.cs.autoquest.tasktrees.treeifc.ISelection;
29import de.ugoe.cs.autoquest.tasktrees.treeifc.ISequence;
30import de.ugoe.cs.autoquest.tasktrees.treeifc.ITask;
31import de.ugoe.cs.autoquest.tasktrees.treeifc.ITaskBuilder;
32import de.ugoe.cs.autoquest.tasktrees.treeifc.ITaskFactory;
33import de.ugoe.cs.autoquest.tasktrees.treeifc.ITaskInstance;
34import de.ugoe.cs.autoquest.tasktrees.treeifc.ITaskInstanceList;
35import de.ugoe.cs.autoquest.tasktrees.treeifc.IUserSession;
36import de.ugoe.cs.autoquest.usageprofiles.SymbolMap;
37import de.ugoe.cs.autoquest.usageprofiles.TrieProcessor;
38import de.ugoe.cs.util.StopWatch;
39import de.ugoe.cs.util.console.Console;
40
41/**
42 * <p>
43 * TODO comment
44 * </p>
45 *
46 * @author Patrick Harms
47 */
48class SequenceForTaskDetectionRule implements ISessionScopeRule {
49   
50    /**
51     * <p>
52     * the task factory to be used for creating substructures for the temporal
53     * relationships identified during rule
54     * </p>
55     */
56    private ITaskFactory taskFactory;
57    /**
58     * <p>
59     * the task builder to be used for creating substructures for the temporal relationships
60     * identified during rule application
61     * </p>
62     */
63    private ITaskBuilder taskBuilder;
64
65    /**
66     * <p>
67     * the task comparator to be used for comparing tasks for preparation
68     * </p>
69     */
70    private TaskHandlingStrategy preparationTaskHandlingStrategy;
71   
72    /**
73     * <p>
74     * the task comparator to be used for comparing tasks during iteration detection an trie
75     * generation
76     * </p>
77     */
78    private TaskHandlingStrategy identityTaskHandlingStrategy;;
79   
80    /**
81     * <p>
82     * instantiates the rule and initializes it with a task equality rule manager and the minimal
83     * task equality identified sublist must have to consider them as iterated.
84     * </p>
85     */
86    SequenceForTaskDetectionRule(TaskEquality minimalTaskEquality,
87                                 ITaskFactory taskFactory,
88                                 ITaskBuilder taskBuilder)
89    {
90        this.taskFactory = taskFactory;
91        this.taskBuilder = taskBuilder;
92       
93        this.preparationTaskHandlingStrategy = new TaskHandlingStrategy(minimalTaskEquality);
94        this.identityTaskHandlingStrategy = new TaskHandlingStrategy(TaskEquality.IDENTICAL);
95    }
96
97    /* (non-Javadoc)
98     * @see java.lang.Object#toString()
99     */
100    @Override
101    public String toString() {
102        return "SequenceForTaskDetectionRule";
103    }
104
105    /* (non-Javadoc)
106     * @see de.ugoe.cs.autoquest.tasktrees.temporalrelation.ISessionScopeRule#apply(java.util.List)
107     */
108    @Override
109    public RuleApplicationResult apply(List<IUserSession> sessions) {
110        RuleApplicationData appData = new RuleApplicationData(sessions);
111
112        // this is the real rule application. Loop while something is replaced.
113        harmonizeEventTaskInstancesModel(appData);
114        do {
115            System.out.println();
116           
117            appData.getStopWatch().start("whole loop");
118            detectAndReplaceIterations(appData);
119
120            appData.getStopWatch().start("task replacement");
121            detectAndReplaceTasks(appData);
122            appData.getStopWatch().stop("task replacement");
123            appData.getStopWatch().stop("whole loop");
124           
125            //((TaskTreeNodeComparator) taskComparator).getStopWatch().dumpStatistics(System.out);
126            //((TaskTreeNodeComparator) taskComparator).getStopWatch().reset();
127           
128            appData.getStopWatch().dumpStatistics(System.out);
129            appData.getStopWatch().reset();
130           
131        }
132        while (appData.detectedAndReplacedTasks());
133       
134        System.out.println
135            ("created " + appData.getResult().getNewlyCreatedTasks().size() +
136             " new tasks and " + appData.getResult().getNewlyCreatedTaskInstances().size() +
137             " appropriate instances\n");
138       
139        if ((appData.getResult().getNewlyCreatedTasks().size() > 0) ||
140            (appData.getResult().getNewlyCreatedTaskInstances().size() > 0))
141        {
142            appData.getResult().setRuleApplicationStatus(RuleApplicationStatus.FINISHED);
143        }
144       
145        return appData.getResult();
146    }
147
148    /**
149     * <p>
150     * TODO: comment
151     * </p>
152     *
153     * @param appData
154     */
155    private void harmonizeEventTaskInstancesModel(RuleApplicationData appData) {
156        Console.traceln(Level.INFO, "harmonizing task model of event task instances");
157        appData.getStopWatch().start("harmonizing event tasks");
158
159        SymbolMap<ITaskInstance, ITask> uniqueTasks =
160            preparationTaskHandlingStrategy.createSymbolMap();
161        TaskComparator comparator = preparationTaskHandlingStrategy.getTaskComparator();
162       
163        int unifiedTasks = 0;
164        ITask task;
165        List<IUserSession> sessions = appData.getSessions();
166        for (IUserSession session : sessions) {
167            Console.traceln(Level.FINE, "handling session " + session);
168            for (ITaskInstance taskInstance : session) {
169                task = uniqueTasks.getValue(taskInstance);
170               
171                if (task == null) {
172                    uniqueTasks.addSymbol(taskInstance, taskInstance.getTask());
173                }
174                else {
175                    taskBuilder.setTask(taskInstance, task);
176                    unifiedTasks++;
177                }
178            }
179           
180            comparator.clearBuffers();
181        }
182       
183        appData.getStopWatch().stop("harmonizing event tasks");
184        Console.traceln(Level.INFO, "harmonized " + unifiedTasks + " task occurrences (still " +
185                        uniqueTasks.size() + " different tasks)");
186
187        appData.getStopWatch().dumpStatistics(System.out);
188        appData.getStopWatch().reset();
189    }
190
191    /**
192     * @param appData
193     */
194    private void detectAndReplaceIterations(RuleApplicationData appData) {
195        Console.traceln(Level.FINE, "detecting iterations");
196        appData.getStopWatch().start("detecting iterations");
197       
198        List<IUserSession> sessions = appData.getSessions();
199       
200        Set<ITask> iteratedTasks = searchIteratedTasks(sessions);
201       
202        if (iteratedTasks.size() > 0) {
203            replaceIterationsOf(iteratedTasks, sessions, appData);
204        }
205       
206        appData.getStopWatch().stop("detecting iterations");
207        Console.traceln(Level.INFO, "replaced " + iteratedTasks.size() + " iterated tasks");
208    }
209
210    /**
211     *
212     */
213    private Set<ITask> searchIteratedTasks(List<IUserSession> sessions) {
214        Set<ITask> iteratedTasks = new HashSet<ITask>();
215        for (IUserSession session : sessions) {
216            for (int i = 0; i < (session.size() - 1); i++) {
217                // we prepared the task instances to refer to unique tasks, if they are treated
218                // as equal. Therefore, we just compare the identity of the tasks of the task
219                // instances
220                if (session.get(i).getTask() == session.get(i + 1).getTask()) {
221                    iteratedTasks.add(session.get(i).getTask());
222                }
223            }
224        }
225       
226        return iteratedTasks;
227    }
228
229    /**
230     *
231     */
232    private void replaceIterationsOf(Set<ITask>          iteratedTasks,
233                                     List<IUserSession>  sessions,
234                                     RuleApplicationData appData)
235    {
236        Map<ITask, IIteration> iterations = new HashMap<ITask, IIteration>();
237        Map<IIteration, List<ITaskInstance>> iterationInstances =
238                new HashMap<IIteration, List<ITaskInstance>>();
239           
240        for (ITask iteratedTask : iteratedTasks) {
241            IIteration iteration = taskFactory.createNewIteration();
242            iterations.put(iteratedTask, iteration);
243            iterationInstances.put(iteration, new LinkedList<ITaskInstance>());
244        }
245       
246        ITaskInstance iterationInstance = null;
247       
248        for (IUserSession session : sessions) {
249            int index = 0;
250            while (index < session.size()) {
251                // we prepared the task instances to refer to unique tasks, if they are treated
252                // as equal. Therefore, we just compare the identity of the tasks of the task
253                // instances
254                ITask currentTask = session.get(index).getTask();
255                IIteration iteration = iterations.get(currentTask);
256                if (iteration != null) {
257                    if ((iterationInstance == null) || (iterationInstance.getTask() != iteration))
258                    {
259                        iterationInstance = taskFactory.createNewTaskInstance(iteration);
260                        iterationInstances.get(iteration).add(iterationInstance);
261                        taskBuilder.addTaskInstance(session, index, iterationInstance);
262                        index++;
263                    }
264                   
265                    taskBuilder.addChild(iterationInstance, session.get(index));
266                    taskBuilder.removeTaskInstance(session, index);
267                }
268                else {
269                    if (iterationInstance != null) {
270                        iterationInstance = null;
271                    }
272                    index++;
273                }
274            }
275        }
276       
277        for (Map.Entry<IIteration, List<ITaskInstance>> entry : iterationInstances.entrySet()) {
278            harmonizeIterationInstancesModel(entry.getKey(), entry.getValue());
279        }
280    }
281
282    /**
283     *
284     */
285    private void harmonizeIterationInstancesModel(IIteration          iteration,
286                                                  List<ITaskInstance> iterationInstances)
287    {
288        List<ITask> iteratedTaskVariants = new LinkedList<ITask>();
289        TaskComparator comparator = preparationTaskHandlingStrategy.getTaskComparator();
290       
291        // merge the lexically different variants of iterated task to a unique list
292        for (ITaskInstance iterationInstance : iterationInstances) {
293            for (ITaskInstance executionVariant : iterationInstance) {
294                ITask candidate = executionVariant.getTask();
295           
296                boolean found = false;
297                for (ITask taskVariant : iteratedTaskVariants) {
298                    if (comparator.areLexicallyEqual(taskVariant, candidate)) {
299                        taskBuilder.setTask(executionVariant, taskVariant);
300                        found = true;
301                        break;
302                    }
303                }
304               
305                if (!found) {
306                    iteratedTaskVariants.add(candidate);
307                }
308            }
309        }
310       
311        // if there are more than one lexically different variant of iterated tasks, adapt the
312        // iteration model to be a selection of different variants. In this case also adapt
313        // the generated iteration instances to correctly contain selection instances. If there
314        // is only one variant of an iterated task, simply set this as the marked task of the
315        // iteration. In this case, the instances can be preserved as is
316        if (iteratedTaskVariants.size() > 1) {
317            ISelection selection = taskFactory.createNewSelection();
318           
319            for (ITask variant : iteratedTaskVariants) {
320                taskBuilder.addChild(selection, variant);
321            }
322           
323            taskBuilder.setMarkedTask(iteration, selection);
324           
325            for (ITaskInstance instance : iterationInstances) {
326                for (int i = 0; i < instance.size(); i++) {
327                    ITaskInstance selectionInstance = taskFactory.createNewTaskInstance(selection);
328                    taskBuilder.addChild(selectionInstance, instance.get(i));
329                    taskBuilder.setTaskInstance(instance, i, selectionInstance);
330                }
331            }
332        }
333        else {
334            taskBuilder.setMarkedTask(iteration, iteratedTaskVariants.get(0));
335        }
336    }
337
338    /**
339     * @param appData
340     */
341    private void detectAndReplaceTasks(RuleApplicationData appData) {
342        Console.traceln(Level.FINE, "detecting and replacing tasks");
343        appData.getStopWatch().start("detecting tasks");
344       
345        getSequencesOccuringMostOften(appData);
346
347        appData.getStopWatch().stop("detecting tasks");
348        appData.getStopWatch().start("replacing tasks");
349       
350        replaceSequencesOccurringMostOften(appData);
351       
352        appData.getStopWatch().stop("replacing tasks");
353        Console.traceln(Level.INFO, "detected and replaced " + appData.getLastFoundTasks().size() +
354                        " tasks occuring " + appData.getLastFoundTasks().getOccurrenceCount() +
355                        " times");
356    }
357
358    /**
359     * @return
360     */
361    private void getSequencesOccuringMostOften(RuleApplicationData appData) {
362        Console.traceln(Level.FINE, "determining most prominent tasks");
363
364        Tasks tasks;
365        boolean createNewTrie = (appData.getLastTrie() == null) ||
366            appData.detectedAndReplacedTasks(); // tree has changed
367       
368        do {
369            if (createNewTrie) {
370                createNewTrie(appData);
371            }
372           
373            MaxCountAndLongestTasksFinder finder = new MaxCountAndLongestTasksFinder();
374            appData.getLastTrie().process(finder);
375       
376            tasks = finder.getFoundTasks();
377           
378            createNewTrie = false;
379           
380            for (List<ITaskInstance> task : tasks) {
381                if (task.size() >= appData.getTrainedSequenceLength()) {
382                    // Trie must be recreated with a longer sequence length to be sure that
383                    // the found sequences occurring most often are found in their whole length
384                    appData.setTrainedSequenceLength(appData.getTrainedSequenceLength() + 1);
385                    createNewTrie = true;
386                    break;
387                }
388            }
389        }
390        while (createNewTrie);
391       
392        // create a normal trie for comparison
393        /*System.out.println("creating test trie for comparison");
394       
395        appData.getStopWatch().start("testtrie");
396        Trie<ITaskInstance> trie = new Trie<ITaskInstance>(identityTaskComparator);
397       
398        for (IUserSession session : appData.getSessions()) {
399            trie.train(session.getExecutedTasks(), appData.getTrainedSequenceLength());
400        }
401       
402        appData.getStopWatch().stop("testtrie");
403       
404        MaxCountAndLongestTasksFinder finder = new MaxCountAndLongestTasksFinder();
405        trie.process(finder);
406
407        boolean allTasksEqual = finder.getFoundTasks().size() == tasks.size();
408       
409        allTasksEqual &= finder.getFoundTasks().occurrenceCount == tasks.occurrenceCount;
410       
411        for (List<ITaskInstance> task1 : finder.getFoundTasks()) {
412            boolean foundTask = false;
413            for (List<ITaskInstance> task2 : tasks) {
414                boolean tasksEqual = false;
415                if (task1.size() == task2.size()) {
416                    tasksEqual = true;
417                    for (int i = 0; i < task1.size(); i++) {
418                        if (!identityTaskComparator.equals(task1.get(i).getTask(), task2.get(i).getTask()))
419                        {
420                            tasksEqual = false;
421                        }
422                    }
423                }
424               
425                if (tasksEqual) {
426                    foundTask = true;
427                    break;
428                }
429            }
430           
431            if (!foundTask) {
432                System.out.println("different is " + task1);
433                allTasksEqual = false;
434                break;
435            }
436        }
437       
438        if (!allTasksEqual) {
439            System.out.println(finder.getFoundTasks());
440            System.out.println(tasks);
441           
442            throw new IllegalArgumentException("both tries calculated different subsequences");
443        }
444       
445        /*TrieStatisticsDumper dumper = new TrieStatisticsDumper();
446        appData.getLastTrie().process(dumper);
447        dumper.dumpCounters();*/
448       
449        appData.setLastFoundTasks(tasks);
450
451        Console.traceln(Level.FINE, "found " + appData.getLastFoundTasks().size() + " tasks " +
452                        "occurring " + appData.getLastFoundTasks().getOccurrenceCount() + " times");
453    }
454
455    /**
456     * @param parent
457     * @return
458     */
459    private void createNewTrie(RuleApplicationData appData) {
460        Console.traceln(Level.FINER, "training trie with a maximum sequence length of " +
461                        appData.getTrainedSequenceLength());
462
463        appData.getStopWatch().start("training trie");
464       
465        // we prepared the task instances to refer to unique tasks, if they are treated
466        // as equal. Therefore, we just compare the identity of the tasks of the task
467        // instances
468        appData.setLastTrie(new TaskInstanceTrie(identityTaskHandlingStrategy));
469   
470        appData.getLastTrie().trainSessions
471            (appData.getSessions(), appData.getTrainedSequenceLength());
472       
473        appData.getStopWatch().stop("training trie");
474    }
475
476    /**
477     * @param appData
478     */
479    private void replaceSequencesOccurringMostOften(RuleApplicationData appData) {
480        appData.detectedAndReplacedTasks(false);
481
482        if ((appData.getLastFoundTasks().size() > 0) &&
483            (appData.getLastFoundTasks().getOccurrenceCount() > 1))
484        {
485            Console.traceln(Level.FINER, "replacing tasks occurrences");
486
487            for (List<ITaskInstance> task : appData.getLastFoundTasks()) {
488                ISequence sequence = taskFactory.createNewSequence();
489               
490                Console.traceln(Level.FINEST, "replacing " + sequence.getId() + ": " + task);
491
492                List<ITaskInstance> sequenceInstances =
493                    replaceTaskOccurrences(task, appData.getSessions(), sequence);
494               
495                harmonizeSequenceInstancesModel(sequence, sequenceInstances,task.size());
496                appData.detectedAndReplacedTasks
497                    (appData.detectedAndReplacedTasks() || (sequenceInstances.size() > 0));
498
499                if (sequenceInstances.size() < appData.getLastFoundTasks().getOccurrenceCount()) {
500                    Console.traceln(Level.FINE, sequence.getId() + ": replaced task only " +
501                                    sequenceInstances.size() + " times instead of expected " +
502                                    appData.getLastFoundTasks().getOccurrenceCount());
503                }
504            }
505        }
506       
507    }
508
509    /**
510     *
511     */
512    private void harmonizeSequenceInstancesModel(ISequence           sequence,
513                                                 List<ITaskInstance> sequenceInstances,
514                                                 int                 sequenceLength)
515    {
516        TaskComparator comparator = preparationTaskHandlingStrategy.getTaskComparator();
517       
518        // ensure for each subtask that lexically different variants are preserved
519        for (int subTaskIndex = 0; subTaskIndex < sequenceLength; subTaskIndex++) {
520            List<ITask> subTaskVariants = new LinkedList<ITask>();
521           
522            for (ITaskInstance sequenceInstance : sequenceInstances) {
523                ITask candidate = sequenceInstance.get(subTaskIndex).getTask();
524               
525                boolean found = false;
526               
527                for (int i = 0; i < subTaskVariants.size(); i++) {
528                    if (comparator.areLexicallyEqual(subTaskVariants.get(i), candidate)) {
529                        taskBuilder.setTask
530                            (sequenceInstance.get(subTaskIndex), subTaskVariants.get(i));
531                       
532                        found = true;
533                        break;
534                    }
535                }
536               
537                if (!found) {
538                    subTaskVariants.add(candidate);
539                }
540            }
541           
542            // if there are more than one lexically different variant of the sub task at
543            // the considered position, adapt the sequence model at that position to have
544            // a selection of the different variants. In this case also adapt the
545            // generated sequence instances to correctly contain selection instances. If
546            // there is only one variant of sub tasks at the given position, simply set
547            // this variant as the sub task of the selection. In this case, the instances
548            // can be preserved as is
549            if (subTaskVariants.size() > 1) {
550                ISelection selection = taskFactory.createNewSelection();
551               
552                for (ITask variant : subTaskVariants) {
553                    taskBuilder.addChild(selection, variant);
554                }
555               
556                taskBuilder.addChild(sequence, selection);
557               
558                for (ITaskInstance instance : sequenceInstances) {
559                    ITaskInstance selectionInstance =
560                        taskFactory.createNewTaskInstance(selection);
561                    taskBuilder.addChild(selectionInstance, instance.get(subTaskIndex));
562                    taskBuilder.setTaskInstance(instance, subTaskIndex, selectionInstance);
563                }
564            }
565            else if (subTaskVariants.size() == 1) {
566                taskBuilder.addChild(sequence, subTaskVariants.get(0));
567            }
568        }
569    }
570
571    /**
572     * @param tree
573     */
574    private List<ITaskInstance> replaceTaskOccurrences(List<ITaskInstance> task,
575                                                       List<IUserSession>  sessions,
576                                                       ISequence           temporalTaskModel)
577    {
578        List<ITaskInstance> sequenceInstances = new LinkedList<ITaskInstance>();
579       
580        for (IUserSession session : sessions) {
581            int index = -1;
582               
583            do {
584                index = getSubListIndex(session, task, ++index);
585
586                if (index > -1) {
587                    sequenceInstances.add
588                        (RuleUtils.createNewSubSequenceInRange
589                             (session, index, index + task.size() - 1, temporalTaskModel,
590                              taskFactory, taskBuilder));
591                }
592            }
593            while (index > -1);
594        }
595       
596        return sequenceInstances;
597    }
598
599    /**
600     * @param trie
601     * @param object
602     * @return
603     */
604    private int getSubListIndex(ITaskInstanceList   list,
605                                List<ITaskInstance> subList,
606                                int                 startIndex)
607    {
608        boolean matchFound;
609        int result = -1;
610       
611        for (int i = startIndex; i <= list.size() - subList.size(); i++) {
612            matchFound = true;
613           
614            for (int j = 0; j < subList.size(); j++) {
615                // we prepared the task instances to refer to unique tasks, if they are treated
616                // as equal. Therefore, we just compare the identity of the tasks of the task
617                // instances
618                if (list.get(i + j).getTask() != subList.get(j).getTask()) {
619                    matchFound = false;
620                    break;
621                }
622            }
623           
624            if (matchFound) {
625                result = i;
626                break;
627            }
628        }
629       
630        return result;
631    }
632
633    /**
634     * @param trie
635     * @param object
636     * @return
637     */
638    private int getSubListIndex(List<ITaskInstance> list,
639                                List<ITaskInstance> subList,
640                                int                 startIndex)
641    {
642        boolean matchFound;
643        int result = -1;
644       
645        for (int i = startIndex; i <= list.size() - subList.size(); i++) {
646            matchFound = true;
647           
648            for (int j = 0; j < subList.size(); j++) {
649                // we prepared the task instances to refer to unique tasks, if they are treated
650                // as equal. Therefore, we just compare the identity of the tasks of the task
651                // instances
652                if (list.get(i + j) != subList.get(j)) {
653                    matchFound = false;
654                    break;
655                }
656            }
657           
658            if (matchFound) {
659                result = i;
660                break;
661            }
662        }
663       
664        return result;
665    }
666   
667    /**
668     * @author Patrick Harms
669     */
670    private class MaxCountAndLongestTasksFinder implements TrieProcessor<ITaskInstance> {
671       
672        /**
673         *
674         */
675        private int currentCount;
676       
677        /**
678         *
679         */
680        private List<List<ITaskInstance>> foundTasks = new LinkedList<List<ITaskInstance>>();
681
682        /**
683         *
684         */
685        public MaxCountAndLongestTasksFinder() {
686            super();
687            this.currentCount = 0;
688        }
689
690        /* (non-Javadoc)
691         * @see de.ugoe.cs.autoquest.usageprofiles.TrieProcessor#process(java.util.List, int)
692         */
693        @Override
694        public TrieProcessor.Result process(List<ITaskInstance> foundTask, int count) {
695            if (foundTask.size() < 2) {
696                // ignore single tasks
697                return TrieProcessor.Result.CONTINUE;
698            }
699           
700            if (count < 2) {
701                // ignore singular occurrences
702                return TrieProcessor.Result.SKIP_NODE;
703            }
704
705            if (this.currentCount > count) {
706                // ignore this children of this task, as they may have only smaller counts than
707                // the already found tasks
708                return TrieProcessor.Result.SKIP_NODE;
709            }
710           
711            if (this.currentCount < count) {
712                // the provided task occurs more often that all tasks found so far.
713                // clear all found tasks and use the new count as the one searched for
714                foundTasks.clear();
715                this.currentCount = count;
716            }
717           
718            if (this.currentCount == count) {
719                // the task is of interest. Sort it into the other found tasks so that
720                // the longest come first
721                boolean added = false;
722                for (int i = 0; i < foundTasks.size(); i++) {
723                    if (foundTasks.get(i).size() < foundTask.size()) {
724                        // defensive copy
725                        foundTasks.add(i, new LinkedList<ITaskInstance>(foundTask)); // defensive copy
726                        added = true;
727                        break;
728                    }
729                }
730               
731                if (!added) {
732                    foundTasks.add(new LinkedList<ITaskInstance>(foundTask)); // defensive copy
733                }
734            }
735           
736            return TrieProcessor.Result.CONTINUE;
737        }
738
739        /**
740         *  @return
741         */
742        public Tasks getFoundTasks() {
743            removePermutationsOfShorterTasks();
744            return new Tasks(currentCount, foundTasks);
745        }
746
747        /**
748         *
749         */
750        private void removePermutationsOfShorterTasks() {
751            // now iterate the sorted list and for each task remove all other tasks that are shorter
752            // (i.e. come later in the sorted list) and that represent a subpart of the task
753            for (int i = 0; i < foundTasks.size(); i++) {
754                for (int j = i + 1; j < foundTasks.size();) {
755                    if (foundTasks.get(j).size() < foundTasks.get(i).size()) {
756                        // found a task that is a potential subtask. Check for this and remove the
757                        // subtask if needed
758                        List<ITaskInstance> longTask = foundTasks.get(i);
759                        List<ITaskInstance> shortTask = foundTasks.get(j);
760                       
761                        if (getSubListIndex(longTask, shortTask, 0) > -1) {
762                            foundTasks.remove(j);
763                        }
764                        else {
765                            j++;
766                        }
767                    }
768                    else {
769                        j++;
770                    }
771                }
772            }
773        }
774
775    }
776   
777//    /**
778//     * @author Patrick Harms
779//     */
780//    private class TrieStatisticsDumper implements TrieProcessor<ITaskInstance> {
781//       
782//        /**
783//         *
784//         */
785//        private Map<Integer, Integer> counters = new HashMap<Integer, Integer>();
786//       
787//        /* (non-Javadoc)
788//         * @see de.ugoe.cs.autoquest.usageprofiles.TrieProcessor#process(java.util.List, int)
789//         */
790//        @Override
791//        public TrieProcessor.Result process(List<ITaskInstance> subsequence, int count) {
792//            if (subsequence.size() == 1) {
793//                Integer value = counters.get(count);
794//               
795//                if (value == null) {
796//                    value = 0;
797//                }
798//               
799//                counters.put(count, value + 1);
800//               
801//                return TrieProcessor.Result.CONTINUE;
802//            }
803//            else {
804//                // ignore singular occurrences
805//                return TrieProcessor.Result.SKIP_NODE;
806//            }
807//        }
808//
809//        /**
810//         *  @return
811//         */
812//        public void dumpCounters() {
813//            int dumpedCounters = 0;
814//           
815//            int count = 1;
816//            while (dumpedCounters < counters.size()) {
817//                Integer value = counters.get(count++);
818//                if (value != null) {
819//                    System.out.println(value + " symbols occurred " + count + " times");
820//                    dumpedCounters++;
821//                }
822//            }
823//        }
824//
825//    }
826   
827    /**
828     *
829     */
830    private static class RuleApplicationData {
831       
832        /**
833         *
834         */
835        private List<IUserSession> sessions;
836       
837        /**
838         *
839         */
840        private TaskInstanceTrie lastTrie;
841       
842        /**
843         * default and minimum trained sequence length is 3
844         */
845        private int trainedSequenceLength = 3;
846       
847        /**
848         *
849         */
850        private Tasks lastFoundTasks = new Tasks(Integer.MAX_VALUE, null);
851       
852        /**
853         *
854         */
855        private boolean detectedAndReplacedTasks;
856       
857        /**
858         *
859         */
860        private RuleApplicationResult result = new RuleApplicationResult();
861       
862        /**
863         *
864         */
865        private StopWatch stopWatch = new StopWatch();
866       
867        /**
868         *
869         */
870        private RuleApplicationData(List<IUserSession> sessions) {
871            this.sessions = sessions;
872        }
873
874        /**
875         * @return the tree
876         */
877        private List<IUserSession> getSessions() {
878            return sessions;
879        }
880
881        /**
882         * @param lastTrie the lastTrie to set
883         */
884        private void setLastTrie(TaskInstanceTrie lastTrie) {
885            this.lastTrie = lastTrie;
886        }
887
888        /**
889         * @return the lastTrie
890         */
891        private TaskInstanceTrie getLastTrie() {
892            return lastTrie;
893        }
894
895        /**
896         * @param trainedSequenceLength the trainedSequenceLength to set
897         */
898        private void setTrainedSequenceLength(int trainedSequenceLength) {
899            this.trainedSequenceLength = trainedSequenceLength;
900        }
901
902        /**
903         * @return the trainedSequenceLength
904         */
905        private int getTrainedSequenceLength() {
906            return trainedSequenceLength;
907        }
908
909        /**
910         * @param lastFoundSequences the lastFoundSequences to set
911         */
912        private void setLastFoundTasks(Tasks lastFoundSequences) {
913            this.lastFoundTasks = lastFoundSequences;
914        }
915
916        /**
917         * @return the lastFoundSequences
918         */
919        private Tasks getLastFoundTasks() {
920            return lastFoundTasks;
921        }
922
923        /**
924         *
925         */
926        private void detectedAndReplacedTasks(boolean detectedAndReplacedTasks) {
927            this.detectedAndReplacedTasks = detectedAndReplacedTasks;
928        }
929
930        /**
931         *
932         */
933        private boolean detectedAndReplacedTasks() {
934            return detectedAndReplacedTasks;
935        }
936       
937        /**
938         * @return the result
939         */
940        private RuleApplicationResult getResult() {
941            return result;
942        }
943
944        /**
945         * @return the stopWatch
946         */
947        private StopWatch getStopWatch() {
948            return stopWatch;
949        }
950
951    }
952   
953
954    /**
955     * @author Patrick Harms
956     */
957    private static class Tasks implements Iterable<List<ITaskInstance>> {
958       
959        /**
960         *
961         */
962        private int occurrenceCount;
963       
964        /**
965         *
966         */
967        private List<List<ITaskInstance>> sequences;
968
969        /**
970         * @param occurrenceCount
971         * @param sequences
972         */
973        private Tasks(int occurrenceCount, List<List<ITaskInstance>> sequences) {
974            super();
975            this.occurrenceCount = occurrenceCount;
976            this.sequences = sequences;
977        }
978
979        /**
980         * @return
981         */
982        private int getOccurrenceCount() {
983            return occurrenceCount;
984        }
985
986        /**
987         * @return
988         */
989        private int size() {
990            return this.sequences.size();
991        }
992
993        /**
994         *
995         */
996
997        /* (non-Javadoc)
998         * @see java.lang.Iterable#iterator()
999         */
1000        @Override
1001        public Iterator<List<ITaskInstance>> iterator() {
1002            return this.sequences.iterator();
1003        }
1004
1005        /* (non-Javadoc)
1006         * @see java.lang.Object#toString()
1007         */
1008        @Override
1009        public String toString() {
1010            StringBuffer result = new StringBuffer();
1011            result.append(this.occurrenceCount);
1012            result.append(" occurrences:\n");
1013           
1014            for (List<ITaskInstance> task : sequences) {
1015                result.append(task);
1016                result.append("\n");
1017            }
1018           
1019            return result.toString();
1020        }
1021
1022    }
1023}
Note: See TracBrowser for help on using the repository browser.