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

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