source: branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/temporalrelation/SequenceForTaskDetectionRuleAlignment.java @ 1595

Last change on this file since 1595 was 1595, checked in by rkrimmel, 10 years ago

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