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

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

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