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

Last change on this file since 1855 was 1855, checked in by pharms, 10 years ago
  • refactoring to use correct terminology
  • implemented selection of which detected subsequence to replace first to be deterministic
  • corrected selection of shorter or longer detected subsequences if the shorter one is part of the longer one
File size: 86.3 KB
Line 
1//   Copyright 2012 Georg-August-Universität Göttingen, Germany
2//
3//   Licensed under the Apache License, Version 2.0 (the "License");
4//   you may not use this file except in compliance with the License.
5//   You may obtain a copy of the License at
6//
7//       http://www.apache.org/licenses/LICENSE-2.0
8//
9//   Unless required by applicable law or agreed to in writing, software
10//   distributed under the License is distributed on an "AS IS" BASIS,
11//   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12//   See the License for the specific language governing permissions and
13//   limitations under the License.
14
15package de.ugoe.cs.autoquest.tasktrees.temporalrelation;
16
17import java.util.ArrayList;
18import java.util.HashMap;
19import java.util.HashSet;
20import java.util.IdentityHashMap;
21import java.util.Iterator;
22import java.util.LinkedList;
23import java.util.List;
24import java.util.ListIterator;
25import java.util.Map;
26import java.util.Set;
27import java.util.logging.Level;
28
29import de.ugoe.cs.autoquest.tasktrees.taskequality.TaskEquality;
30import de.ugoe.cs.autoquest.tasktrees.temporalrelation.utils.DebuggingHelper;
31import de.ugoe.cs.autoquest.tasktrees.treeifc.IIteration;
32import de.ugoe.cs.autoquest.tasktrees.treeifc.IIterationInstance;
33import de.ugoe.cs.autoquest.tasktrees.treeifc.IOptional;
34import de.ugoe.cs.autoquest.tasktrees.treeifc.IOptionalInstance;
35import de.ugoe.cs.autoquest.tasktrees.treeifc.ISelection;
36import de.ugoe.cs.autoquest.tasktrees.treeifc.ISelectionInstance;
37import de.ugoe.cs.autoquest.tasktrees.treeifc.ISequence;
38import de.ugoe.cs.autoquest.tasktrees.treeifc.ISequenceInstance;
39import de.ugoe.cs.autoquest.tasktrees.treeifc.ITask;
40import de.ugoe.cs.autoquest.tasktrees.treeifc.ITaskBuilder;
41import de.ugoe.cs.autoquest.tasktrees.treeifc.ITaskFactory;
42import de.ugoe.cs.autoquest.tasktrees.treeifc.ITaskInstance;
43import de.ugoe.cs.autoquest.tasktrees.treeifc.ITaskInstanceList;
44import de.ugoe.cs.autoquest.tasktrees.treeifc.IUserSession;
45import de.ugoe.cs.autoquest.usageprofiles.SymbolMap;
46import de.ugoe.cs.autoquest.usageprofiles.Trie;
47import de.ugoe.cs.autoquest.usageprofiles.TrieProcessor;
48import de.ugoe.cs.util.StopWatch;
49import de.ugoe.cs.util.console.Console;
50
51/**
52 * <p>
53 * This class implements the major rule for creating task trees based on a set of recorded
54 * user sessions. For this, it first harmonizes all tasks. This eases later comparison. Then it
55 * searches the sessions for iterations and replaces them accordingly. Then it searches for sub
56 * sequences being the longest and occurring most often. For each found sub sequence, it replaces
57 * the occurrences by creating appropriate {@link ISequence}s. Afterwards, again searches for
58 * iterations and then again for sub sequences until no more replacements are done.
59 * </p>
60 * <p>
61 * For determining the longest sequence occurring most often, the implementation uses a
62 * {@link Trie}. The depth of the tree is initially 3. If the algorithm has a longest sequence
63 * occurring most often whose length is equal to the depth of the trie, it recalculates the trie
64 * with an increased depth.
65 * </p>
66 *
67 * @author Patrick Harms
68 */
69class SequenceForTaskDetectionRule 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 relationships
81     * 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 preparation, i.e., before
89     * 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 iteration detection an trie
97     * generation, i.e., after the tasks are harmonized
98     * </p>
99     */
100    private TaskHandlingStrategy identityTaskHandlingStrategy;;
101   
102    /**
103     * <p>
104     * instantiates the rule and initializes it with a task equality to be considered when
105     * comparing tasks as well as a task factory and builder to be used for creating task
106     * structures.
107     * </p>
108     *
109     * @param minimalTaskEquality the task equality to be considered when comparing tasks
110     * @param taskFactory         the task factory to be used for creating substructures
111     * @param taskBuilder         the task builder to be used for creating substructures
112     */
113    SequenceForTaskDetectionRule(TaskEquality minimalTaskEquality,
114                                 ITaskFactory taskFactory,
115                                 ITaskBuilder taskBuilder)
116    {
117        this.taskFactory = taskFactory;
118        this.taskBuilder = taskBuilder;
119       
120        this.preparationTaskHandlingStrategy = new TaskHandlingStrategy(minimalTaskEquality);
121        this.identityTaskHandlingStrategy = new TaskHandlingStrategy(TaskEquality.IDENTICAL);
122    }
123
124    /* (non-Javadoc)
125     * @see java.lang.Object#toString()
126     */
127    @Override
128    public String toString() {
129        return "SequenceForTaskDetectionRule";
130    }
131
132    /* (non-Javadoc)
133     * @see de.ugoe.cs.autoquest.tasktrees.temporalrelation.ISessionScopeRule#apply(java.util.List)
134     */
135    @Override
136    public RuleApplicationResult apply(List<IUserSession> sessions) {
137        RuleApplicationData appData = new RuleApplicationData(sessions);
138       
139        // this is the real rule application. Loop while something is replaced.
140        harmonizeEventTaskInstancesModel(appData);
141        do {
142            System.out.println();
143           
144            appData.getStopWatch().start("whole loop");
145            detectAndReplaceIterations(appData);
146
147            appData.getStopWatch().start("task replacement");
148            detectAndReplaceTasks(appData);
149            appData.getStopWatch().stop("task replacement");
150            appData.getStopWatch().stop("whole loop");
151           
152            //((TaskTreeNodeComparator) taskComparator).getStopWatch().dumpStatistics(System.out);
153            //((TaskTreeNodeComparator) taskComparator).getStopWatch().reset();
154           
155            appData.getStopWatch().dumpStatistics(System.out);
156            appData.getStopWatch().reset();
157           
158        }
159        while (appData.detectedAndReplacedTasks());
160       
161        Console.println
162            ("created " + appData.getResult().getNewlyCreatedTasks().size() +
163             " new tasks and " + appData.getResult().getNewlyCreatedTaskInstances().size() +
164             " appropriate instances\n");
165       
166        if ((appData.getResult().getNewlyCreatedTasks().size() > 0) ||
167            (appData.getResult().getNewlyCreatedTaskInstances().size() > 0))
168        {
169            appData.getResult().setRuleApplicationStatus(RuleApplicationStatus.FINISHED);
170        }
171       
172        return appData.getResult();
173    }
174
175    /**
176     * <p>
177     * harmonizes the event task instances by unifying tasks. This is done, as initially the
178     * event tasks being equal with respect to the considered task equality are distinct objects.
179     * The comparison of these distinct objects is more time consuming than comparing the object
180     * references.
181     * </p>
182     *
183     * @param appData the rule application data combining all data used for applying this rule
184     */
185    private void harmonizeEventTaskInstancesModel(RuleApplicationData appData) {
186        Console.traceln(Level.INFO, "harmonizing task model of event task instances");
187        appData.getStopWatch().start("harmonizing event tasks");
188
189        SymbolMap<ITask, ITask> uniqueTasks = preparationTaskHandlingStrategy.createSymbolMap();
190        TaskComparator comparator = preparationTaskHandlingStrategy.getTaskComparator();
191       
192        int unifiedTasks = 0;
193        ITask task;
194        List<IUserSession> sessions = appData.getSessions();
195        int sessionNo = 0;
196        for (IUserSession session : sessions) {
197            Console.traceln(Level.FINE, "handling " + (++sessionNo) + ". " + session);
198            for (ITaskInstance taskInstance : session) {
199                task = uniqueTasks.getValue(taskInstance.getTask());
200               
201                if (task == null) {
202                    uniqueTasks.addSymbol(taskInstance.getTask(), taskInstance.getTask());
203                }
204                else {
205                    taskBuilder.setTask(taskInstance, task);
206                    unifiedTasks++;
207                }
208            }
209           
210            comparator.clearBuffers();
211        }
212       
213        appData.getStopWatch().stop("harmonizing event tasks");
214        Console.traceln(Level.INFO, "harmonized " + unifiedTasks + " task occurrences (still " +
215                        uniqueTasks.size() + " different tasks)");
216
217        appData.getStopWatch().dumpStatistics(System.out);
218        appData.getStopWatch().reset();
219    }
220
221    /**
222     * <p>
223     * searches for direct iterations of single tasks in all sequences and replaces them with
224     * {@link IIteration}s, respectively appropriate instances. Also all single occurrences of
225     * a task that is iterated somewhen are replaced with iterations to have again an efficient
226     * way for task comparisons.
227     * </p>
228     *
229     * @param appData the rule application data combining all data used for applying this rule
230     */
231    private void detectAndReplaceIterations(RuleApplicationData appData) {
232        Console.traceln(Level.FINE, "detecting iterations");
233        appData.getStopWatch().start("detecting iterations");
234       
235        List<IUserSession> sessions = appData.getSessions();
236       
237        Set<ITask> iteratedTasks = searchIteratedTasks(sessions);
238       
239        if (iteratedTasks.size() > 0) {
240            replaceIterationsOf(iteratedTasks, sessions, appData);
241        }
242       
243        appData.getStopWatch().stop("detecting iterations");
244        Console.traceln(Level.INFO, "replaced " + iteratedTasks.size() + " iterated tasks");
245    }
246
247    /**
248     * <p>
249     * searches the provided sessions for task iterations. If a task is iterated, it is added
250     * to the returned set.
251     * </p>
252     *
253     * @param the session to search for iterations in
254     *
255     * @return a set of tasks being iterated somewhere
256     */
257    private Set<ITask> searchIteratedTasks(List<IUserSession> sessions) {
258        Set<ITask> iteratedTasks = new HashSet<ITask>();
259        for (IUserSession session : sessions) {
260            for (int i = 0; i < (session.size() - 1); i++) {
261                // we prepared the task instances to refer to unique tasks, if they are treated
262                // as equal. Therefore, we just compare the identity of the tasks of the task
263                // instances
264                if (session.get(i).getTask() == session.get(i + 1).getTask()) {
265                    iteratedTasks.add(session.get(i).getTask());
266                }
267            }
268        }
269       
270        return iteratedTasks;
271    }
272
273    /**
274     * <p>
275     * replaces all occurrences of all tasks provided in the set with iterations
276     * </p>
277     *
278     * @param iteratedTasks the tasks to be replaced with iterations
279     * @param sessions      the sessions in which the tasks are to be replaced
280     * @param appData       the rule application data combining all data used for applying this rule
281     */
282    private void replaceIterationsOf(Set<ITask>          iteratedTasks,
283                                     List<IUserSession>  sessions,
284                                     RuleApplicationData appData)
285    {
286        Map<ITask, IIteration> iterations = new HashMap<ITask, IIteration>();
287        Map<IIteration, IOptional> optionals = new HashMap<IIteration, IOptional>();
288        Map<IIteration, List<IIterationInstance>> iterationInstances =
289                new HashMap<IIteration, List<IIterationInstance>>();
290           
291        for (ITask iteratedTask : iteratedTasks) {
292            IIteration iteration = taskFactory.createNewIteration();
293            iterations.put(iteratedTask, iteration);
294           
295            if (iteratedTask instanceof IOptional) {
296                IOptional optional = taskFactory.createNewOptional();
297                taskBuilder.setMarkedTask(optional, iteration);
298                optionals.put(iteration, optional);
299            }
300           
301            iterationInstances.put(iteration, new LinkedList<IIterationInstance>());
302        }
303       
304        IOptionalInstance optionalInstance;
305        IIterationInstance iterationInstance;
306       
307        for (IUserSession session : sessions) {
308            int index = 0;
309            optionalInstance = null;
310            iterationInstance = null;
311            boolean inReplacement = false;
312
313            while (index < session.size()) {
314                // we prepared the task instances to refer to unique tasks, if they are treated
315                // as equal. Therefore, we just compare the identity of the tasks of the task
316                // instances
317                ITask currentTask = session.get(index).getTask();
318                IIteration iteration = iterations.get(currentTask);
319                if (iteration != null) {
320                    if (!inReplacement || (iterationInstance.getTask() != iteration)) {
321                        if (currentTask instanceof IOptional) {
322                            IOptional optional = optionals.get(iteration);
323                            optionalInstance = taskFactory.createNewTaskInstance(optional);
324                            taskBuilder.addTaskInstance(session, index, optionalInstance);
325                        }
326                        else {
327                            iterationInstance = taskFactory.createNewTaskInstance(iteration);
328                            iterationInstances.get(iteration).add(iterationInstance);
329                            taskBuilder.addTaskInstance(session, index, iterationInstance);
330                        }
331                        inReplacement = true;
332                        index++;
333                    }
334                   
335                    if (currentTask instanceof IOptional) {
336                        ITaskInstance child = ((IOptionalInstance) session.get(index)).getChild();
337                       
338                        if (child != null) {
339                            if (iterationInstance == null) {
340                                iterationInstance = taskFactory.createNewTaskInstance(iteration);
341                                iterationInstances.get(iteration).add(iterationInstance);
342                                taskBuilder.setChild(optionalInstance, iterationInstance);
343                            }
344                            taskBuilder.addChild(iterationInstance, child);
345                        }
346                    }
347                    else {
348                        taskBuilder.addChild(iterationInstance, session.get(index));
349                    }
350                   
351                    taskBuilder.removeTaskInstance(session, index);
352                }
353                else {
354                    if (iterationInstance != null) {
355                        iterationInstance = null;
356                        optionalInstance = null;
357                        inReplacement = false;
358                    }
359                    index++;
360                }
361            }
362        }
363       
364        for (Map.Entry<IIteration, List<IIterationInstance>> entry : iterationInstances.entrySet())
365        {
366            harmonizeIterationInstancesModel(entry.getKey(), entry.getValue());
367        }
368    }
369
370    /**
371     * <p>
372     * TODO clarify why this is done
373     * </p>
374     */
375    private void harmonizeIterationInstancesModel(IIteration               iteration,
376                                                  List<IIterationInstance> iterationInstances)
377    {
378        List<ITask> iteratedTaskVariants = new LinkedList<ITask>();
379        TaskComparator comparator = preparationTaskHandlingStrategy.getTaskComparator();
380       
381        // merge the lexically different variants of iterated task to a unique list
382        for (IIterationInstance iterationInstance : iterationInstances) {
383            for (ITaskInstance executionVariant : iterationInstance) {
384                ITask candidate = executionVariant.getTask();
385           
386                boolean found = false;
387                for (ITask taskVariant : iteratedTaskVariants) {
388                    if (comparator.areLexicallyEqual(taskVariant, candidate)) {
389                        taskBuilder.setTask(executionVariant, taskVariant);
390                        found = true;
391                        break;
392                    }
393                }
394               
395                if (!found) {
396                    iteratedTaskVariants.add(candidate);
397                }
398            }
399        }
400       
401        // if there are more than one lexically different variant of iterated tasks, adapt the
402        // iteration model to be a selection of different variants. In this case also adapt
403        // the generated iteration instances to correctly contain selection instances. If there
404        // is only one variant of an iterated task, simply set this as the marked task of the
405        // iteration. In this case, the instances can be preserved as is
406        if (iteratedTaskVariants.size() > 1) {
407            ISelection selection = taskFactory.createNewSelection();
408           
409            for (ITask variant : iteratedTaskVariants) {
410                taskBuilder.addChild(selection, variant);
411            }
412           
413            taskBuilder.setMarkedTask(iteration, selection);
414           
415            for (IIterationInstance instance : iterationInstances) {
416                for (int i = 0; i < instance.size(); i++) {
417                    ISelectionInstance selectionInstance =
418                        taskFactory.createNewTaskInstance(selection);
419                    taskBuilder.setChild(selectionInstance, instance.get(i));
420                    taskBuilder.setTaskInstance(instance, i, selectionInstance);
421                }
422            }
423        }
424        else {
425            taskBuilder.setMarkedTask(iteration, iteratedTaskVariants.get(0));
426        }
427    }
428
429    /**
430     * TODO go on commenting
431     * @param appData the rule application data combining all data used for applying this rule
432     */
433    private void detectAndReplaceTasks(RuleApplicationData appData) {
434        Console.traceln(Level.FINE, "detecting and replacing tasks");
435        appData.getStopWatch().start("detecting tasks");
436       
437        getSubsequencesOccuringMostOften(appData);
438       
439        appData.getStopWatch().stop("detecting tasks");
440        appData.getStopWatch().start("sorting tasks");
441       
442        removeInterleavingTasks(appData);
443
444        appData.getStopWatch().stop("sorting tasks");
445        appData.getStopWatch().start("replacing tasks");
446       
447        replaceSequencesOccurringMostOften(appData);
448       
449        appData.getStopWatch().stop("replacing tasks");
450        Console.traceln(Level.INFO, "detected and replaced " + appData.getLastFoundSubsequences().size() +
451                        " tasks occuring " + appData.getLastFoundSubsequences().getOccurrenceCount() +
452                        " times");
453    }
454
455    /**
456     * @param appData the rule application data combining all data used for applying this rule
457     */
458    private void getSubsequencesOccuringMostOften(RuleApplicationData appData) {
459        Console.traceln(Level.FINER, "determining most prominent subsequences");
460
461        Subsequences subsequences;
462        boolean createNewTrie = (appData.getLastTrie() == null) ||
463            appData.detectedAndReplacedTasks(); // tree has changed
464       
465        do {
466            if (createNewTrie) {
467                createNewTrie(appData);
468            }
469           
470            MaxCountAndLongestSubsequencesFinder finder = new MaxCountAndLongestSubsequencesFinder();
471            appData.getLastTrie().process(finder);
472       
473            subsequences = finder.getFoundSubsequences();
474           
475            createNewTrie = false;
476           
477            for (Subsequence subsequence : subsequences) {
478                if (subsequence.size() >= appData.getTrainedSubsequenceLength()) {
479                    // Trie must be recreated with a longer sequence length to be sure that
480                    // the found sequences occurring most often are found in their whole length
481                    appData.setTrainedSubsequenceLength(appData.getTrainedSubsequenceLength() + 1);
482                    createNewTrie = true;
483                    break;
484                }
485            }
486        }
487        while (createNewTrie);
488       
489        // create a normal trie for comparison
490        /*System.out.println("creating test trie for comparison");
491       
492        appData.getStopWatch().start("testtrie");
493        Trie<ITaskInstance> trie = new Trie<ITaskInstance>(identityTaskComparator);
494       
495        for (IUserSession session : appData.getSessions()) {
496            trie.train(session.getExecutedTasks(), appData.getTrainedSequenceLength());
497        }
498       
499        appData.getStopWatch().stop("testtrie");
500       
501        MaxCountAndLongestTasksFinder finder = new MaxCountAndLongestTasksFinder();
502        trie.process(finder);
503
504        boolean allTasksEqual = finder.getFoundTasks().size() == tasks.size();
505       
506        allTasksEqual &= finder.getFoundTasks().occurrenceCount == tasks.occurrenceCount;
507       
508        for (List<ITaskInstance> task1 : finder.getFoundTasks()) {
509            boolean foundTask = false;
510            for (List<ITaskInstance> task2 : tasks) {
511                boolean tasksEqual = false;
512                if (task1.size() == task2.size()) {
513                    tasksEqual = true;
514                    for (int i = 0; i < task1.size(); i++) {
515                        if (!identityTaskComparator.equals(task1.get(i).getTask(), task2.get(i).getTask()))
516                        {
517                            tasksEqual = false;
518                        }
519                    }
520                }
521               
522                if (tasksEqual) {
523                    foundTask = true;
524                    break;
525                }
526            }
527           
528            if (!foundTask) {
529                System.out.println("different is " + task1);
530                allTasksEqual = false;
531                break;
532            }
533        }
534       
535        if (!allTasksEqual) {
536            System.out.println(finder.getFoundTasks());
537            System.out.println(tasks);
538           
539            throw new IllegalArgumentException("both tries calculated different subsequences");
540        }
541       
542        /*TrieStatisticsDumper dumper = new TrieStatisticsDumper();
543        appData.getLastTrie().process(dumper);
544        dumper.dumpCounters();*/
545       
546        appData.setLastFoundSubsequences(subsequences);
547
548        Console.traceln(Level.FINE, "found " + appData.getLastFoundSubsequences().size() +
549                        " tasks occurring " +
550                        appData.getLastFoundSubsequences().getOccurrenceCount() + " times");
551    }
552
553    /**
554     * @param appData the rule application data combining all data used for applying this rule
555     */
556    private void createNewTrie(RuleApplicationData appData) {
557        Console.traceln(Level.FINEST, "training trie with a maximum sequence length of " +
558                        appData.getTrainedSubsequenceLength());
559
560        appData.getStopWatch().start("training trie");
561       
562        // we prepared the task instances to refer to unique tasks, if they are treated
563        // as equal. Therefore, we just compare the identity of the tasks of the task
564        // instances
565        appData.setLastTrie(new TaskInstanceTrie(identityTaskHandlingStrategy));
566   
567        appData.getLastTrie().trainSessions
568            (appData.getSessions(), appData.getTrainedSubsequenceLength());
569       
570        appData.getStopWatch().stop("training trie");
571    }
572
573    /**
574     * from the last found tasks, sort out those that interleave with each other as for them always
575     * the same replacement order needs to be taken.
576     */
577    private void removeInterleavingTasks(RuleApplicationData appData) {
578        // >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
579        // >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> TEST IMPLEMENTATION >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
580        // dumpSortedCollectionOfSubsequences
581        //     ("found task", appData.getLastFoundSubsequences().subsequences);
582        // <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
583        // <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< TEST IMPLEMENTATION <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
584
585        List<InterleavingSubsequence> interleavings;
586       
587        do {
588            interleavings = getInterleavings(appData.getLastFoundSubsequences(), appData);
589           
590            if (interleavings.size() > 0) {
591                // dumpSorted(interleavings);
592
593                // Console.traceln(Level.FINEST, "found " + interleavings.size() + " subsequences " +
594                //                 "--> checking for most real interleavings");
595               
596                // we found interleaving subsequences. We need to decide for them, which to replace
597                // first. For this, we need to remove some of them from the list of detected
598                // subsequences in an ordered way to always have the same prioritization for
599                // replacements. The ones to be removed are those with most interleavings.
600                interleavings = getMostIntensiveInterleavings(interleavings);
601               
602                //dumpSorted(interleavings);
603               
604                if (interleavings.size() == 1) {
605                    // Console.traceln(Level.FINEST, "found one most interleaving subsequence " +
606                    //                 "--> removing it and checking for further interleavings");
607
608                    // we have exactly one most interleaving detected subsequence. In this case,
609                    // we remove it from the list of found subsequences and check again, if their
610                    // are remaining interleavings. If not, we have the final list of non
611                    // interleaving subsequences to be replaced. The order or their replacement
612                    // doesn't matter as they are not interleaving.
613                    appData.getLastFoundSubsequences().remove
614                        (interleavings.get(0).getSubsequence());
615                   
616                    continue;
617                }
618                else if (interleavings.size() == 0) {
619                    // this should never happen
620                    throw new RuntimeException("Implementation error: don't know how I got here");
621                }
622               
623                // Console.traceln(Level.FINEST, "found " + interleavings.size() + " most " +
624                //                 "interleaving subsequences --> checking which are most often a " +
625                //                 "successor");
626
627                // there are several subsequences with the same amount of interleavings.
628                // Check which of them is the most often a successor. This should be removed.
629                interleavings = getMostInterleavingsAsSuccessor(interleavings);
630               
631                // dumpSorted(interleavings);
632
633                if (interleavings.size() == 1) {
634                    //  Console.traceln(Level.FINEST, "found one interleaving subsequence being most " +
635                    //                  "often a successor --> removing it and checking for further " +
636                    //                  "interleavings");
637
638                    // we have exactly one interleaving subsequence that is most often a successor
639                    // of the others. Remove it and try again to see if sufficient interleavings
640                    // were cleared.
641                    appData.getLastFoundSubsequences().remove
642                        (interleavings.get(0).getSubsequence());
643                   
644                    continue;
645                }
646                else if (interleavings.size() == 0) {
647                    // this should never happen
648                    throw new RuntimeException("Implementation error: don't know how I got here");
649                }
650               
651                // Console.traceln(Level.FINEST, "found " + interleavings.size() +
652                //                 " most interleaving subsequences being most often a successor " +
653                //                 "--> checking which is most seldom a predecessor");
654
655                // there are several subsequences with the same amount of interleavings being also
656                // the same times a successor of another subsequence. Hence, check which of them is
657                // the least often a predecessor. This should be removed.
658                interleavings = getLeastInterleavingsAsPredecessor(interleavings);
659               
660                //dumpSorted(interleavings);
661
662                if (interleavings.size() == 1) {
663                    // Console.traceln(Level.FINEST, "found one interleaving subsequence being most " +
664                    //                 "often a successor and most seldom a predecessor --> " +
665                    //                 "removing it and checking for further interleavings");
666
667                    // we have exactly one interleaving subsequence that is most often a successor
668                    // and most seldom a predecessor of the others. Remove it and try again to see
669                    // if sufficient interleavings were cleared.
670                    appData.getLastFoundSubsequences().remove
671                        (interleavings.get(0).getSubsequence());
672                   
673                    continue;
674                }
675                else if (interleavings.size() == 0) {
676                    // this should never happen
677                    throw new RuntimeException("Implementation error: don't know how I got here");
678                }
679               
680                // the remaining subsequences are interleaving the same amount of times and are
681                // used the same amount of times as successors and as predecessors by all other
682                // detected interleaving subsequences. Now lets check, which of them is mostly used
683                // as successor and most seldom used as predecessor only considering the remaining
684                // subsequences. If some of them do not interfere with the others, remove them and
685                // try again to see if sufficient interleavings were cleared.
686               
687                // Console.traceln(Level.FINEST, "found " + interleavings.size() +
688                //                 " most interleaving subsequences being most often a successor " +
689                //                 "and most seldom a predecessor --> removing collision being not " +
690                //                 "between themselves");
691
692                interleavings = removeCollisionsOfOtherSubsequences(interleavings);
693               
694                // dumpSorted(interleavings);
695               
696                // Console.traceln(Level.FINEST, "removed collisions of other subsequences not " +
697                //                 "belonging to the remaining interleaving subsequences --> " +
698                //                 "checking of the remaining interleaving are most often a " +
699                //                 "successor of another one");
700               
701                interleavings = getMostInterleavingsAsSuccessor(interleavings);
702                interleavings = removeCollisionsOfOtherSubsequences(interleavings);
703               
704                // dumpSorted(interleavings);
705
706                if (interleavings.size() == 1) {
707                    // Console.traceln(Level.FINEST, "found one interleaving subsequence being most " +
708                    //                 "often a successor in comparison to the other remaining " +
709                    //                 "interleavings --> removing it and checking for further " +
710                    //                 "interleavings");
711
712                    appData.getLastFoundSubsequences().remove
713                        (interleavings.get(0).getSubsequence());
714                   
715                    continue;
716                }
717                else if (interleavings.size() == 0) {
718                    // this should never happen
719                    throw new RuntimeException("Implementation error: don't know how I got here");
720                }
721               
722                // Console.traceln(Level.FINEST, "found " + interleavings.size() +
723                //                 " most interleaving subsequences being most often a successor in " +
724                //                 "comparison to the other remaining interleavings --> checking " +
725                //                 "which is most seldom a predecessor");
726
727                interleavings = getLeastInterleavingsAsPredecessor(interleavings);
728                interleavings = removeCollisionsOfOtherSubsequences(interleavings);
729               
730                // dumpSorted(interleavings);
731
732                if (interleavings.size() == 1) {
733                    // Console.traceln(Level.FINEST, "found one interleaving subsequence being most " +
734                    //                 "often a successor and most seldom a predecessor in " +
735                    //                 "comparison to the other remaining interleavings --> " +
736                    //                 "removing it and checking for further interleavings");
737
738                    appData.getLastFoundSubsequences().remove
739                        (interleavings.get(0).getSubsequence());
740                   
741                    continue;
742                }
743                else if (interleavings.size() == 0) {
744                    // this should never happen
745                    throw new RuntimeException("Implementation error: don't know how I got here");
746                }
747               
748                // Console.traceln(Level.FINEST, "found " + interleavings.size() +
749                //                 " most interleaving subsequences being most often a successor " +
750                //                 "and most seldom a predecessor in comparison to the other " +
751                //                 "remaining interleavings --> this may happen if there are no " +
752                //                 "collisions between them anymore. If so, remove all of them at " +
753                //                 "once.");
754
755                int collisionCount = 0;
756               
757                for (InterleavingSubsequence subsequence : interleavings) {
758                    collisionCount += subsequence.getCollisionCounter();
759                }
760               
761                if (collisionCount == 0) {
762                    // Console.traceln(Level.FINEST, "remaining interleaving subsequences have no " +
763                    //                 "further collisions with each other --> removing all of them " +
764                    //                 "and checking for further interleavings");
765                   
766                    for (InterleavingSubsequence subsequence : interleavings) {
767                        appData.getLastFoundSubsequences().remove(subsequence.getSubsequence());
768                    }
769                   
770                    continue;
771                }
772
773                // Console.traceln(Level.FINEST, "remaining interleaving subsequences still have " +
774                //                 "collisions with each other --> decide based on their occurrences" +
775                //                 " in the sessions (remove those, coming later in comparison to " +
776                //                 "the others)");
777               
778                // determine the predecessor collisions being the last in all sessions. Those
779                // collisions show the interleaving subsequence occurring last
780                Map<IUserSession, Collision> sessions =
781                    new IdentityHashMap<IUserSession, Collision>();
782               
783                for (InterleavingSubsequence interleaving : interleavings) {
784                    for (Collision coll : interleaving.getPredecessorCollisions()) {
785                        Collision maxPosColl = sessions.get(coll.getLocation().getSession());
786                       
787                        if ((maxPosColl == null) ||
788                            (maxPosColl.getLocation().getIndex() < coll.getLocation().getIndex()))
789                        {
790                            sessions.put(coll.getLocation().getSession(), coll);
791                        }
792                    }
793                }
794               
795                // determine, which of the subsequences occurs most often as the last one
796                // interleaving with another
797                Map<Subsequence, Integer> lastOccurrenceCounters =
798                    new IdentityHashMap<Subsequence, Integer>();
799               
800                for (Collision coll : sessions.values()) {
801                    Integer counter = lastOccurrenceCounters.get(coll.getSubsequence());
802                   
803                    if (counter == null) {
804                        lastOccurrenceCounters.put(coll.getSubsequence(), 1);
805                    }
806                    else {
807                        lastOccurrenceCounters.put(coll.getSubsequence(), counter + 1);
808                    }
809                }
810               
811                int maxCounter = 0;
812                Subsequence toRemove = null;
813               
814                for (Map.Entry<Subsequence, Integer> entry : lastOccurrenceCounters.entrySet()) {
815                    if (entry.getValue() > maxCounter) {
816                        maxCounter = entry.getValue();
817                        toRemove = entry.getKey();
818                    }
819                    else if (entry.getValue() == maxCounter) {
820                        // we can not decide again
821                        toRemove = null;
822                        break;
823                    }
824                }
825               
826                if (toRemove != null) {
827                    // Console.traceln(Level.FINEST, "one of the remaining interleaving subsequences" +
828                    //                 " is most often the last to occur --> removing it and " +
829                    //                 "checking for further interleavings");
830           
831                    appData.getLastFoundSubsequences().remove(toRemove);
832                    continue;
833                }
834               
835                // checking now, if there is one sequence, having the lowest index for any of
836                // its collisions and preserve it. If there are several ones with the same minimum
837                // index, throw an exception
838                int minPosInAnySequence = Integer.MAX_VALUE;
839                InterleavingSubsequence subsequenceWithMinPos = null;
840               
841                for (InterleavingSubsequence interleaving : interleavings) {
842                    for (Collision collision : interleaving.getSuccessorCollisions()) {
843                        if (minPosInAnySequence > collision.getLocation().getIndex()) {
844                            minPosInAnySequence = collision.getLocation().getIndex();
845                            subsequenceWithMinPos = interleaving;
846                        }
847                        else if (minPosInAnySequence == collision.getLocation().getIndex()) {
848                            // several have the same min pos --> undecidable which to prefer
849                            subsequenceWithMinPos = null;
850                        }
851                    }
852                }
853               
854                if (subsequenceWithMinPos != null) {
855                    List<Subsequence> subsequencesToRemove = new LinkedList<Subsequence>();
856                   
857                    for (Subsequence candidate : appData.getLastFoundSubsequences()) {
858                        if (candidate != subsequenceWithMinPos.getSubsequence()) {
859                            subsequencesToRemove.add(candidate);
860                        }
861                    }
862                   
863                    for (Subsequence candidate : subsequencesToRemove) {
864                        appData.getLastFoundSubsequences().remove(candidate);
865                    }
866                   
867                    continue;
868                }
869               
870                // At this point, we can not decide anymore. But it should also not
871                // happen. Even if two subsequences ab and ba one of them should be
872                // more often a successor or predecessor than the other if they
873                // directly follow each other. If not, it can not be decided, which of
874                // them to replace first. Perhaps the one occurring more often as
875                // the first in a session that the other. But this can be implemented
876                // later.
877                dumpSorted(interleavings, Level.SEVERE);
878               
879                throw new RuntimeException
880                    ("can not decide which detected subsequence to replace first.");
881            }
882        }
883        while (interleavings.size() > 0);
884
885        // >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
886        // >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> TEST IMPLEMENTATION >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
887        // dumpSortedCollectionOfSubsequences
888        //    ("to replace", appData.getLastFoundSubsequences().subsequences);
889        // <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
890        // <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< TEST IMPLEMENTATION <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
891    }
892
893    /**
894     *
895     */
896    private List<InterleavingSubsequence> getInterleavings(Subsequences        subsequences,
897                                                           RuleApplicationData appData)
898    {
899        List<InterleavingSubsequence> interleavings = new LinkedList<InterleavingSubsequence>();
900        List<Subsequence> potentialPredecessors = new LinkedList<Subsequence>();
901        List<Subsequence> potentialSuccessors = new LinkedList<Subsequence>();
902       
903        Map<Subsequence, List<SubsequenceLocation>> allLocations =
904            getLocations(subsequences, appData);
905       
906        for (Subsequence subsequence : subsequences) {
907            // Console.traceln
908            //    (Level.FINEST, "searching for interleavings of " + toPlainStr(subsequence));
909
910            potentialPredecessors.clear();
911            potentialSuccessors.clear();
912           
913            getInterleavingSubsequences
914                (subsequence, subsequences, potentialPredecessors, potentialSuccessors);
915           
916            if ((potentialPredecessors.size() <= 0) && (potentialSuccessors.size() <= 0)) {
917                // subsequence is not interleaving with others. Check next one.
918                continue;
919            }
920           
921            // subsequence is interleaving. First, determine its locations in the user sessions.
922            List<SubsequenceLocation> locations = allLocations.get(subsequence);
923           
924            List<Collision> precedingCollisions =
925                getPrecedingCollisions(subsequence, locations, potentialPredecessors, appData);
926           
927            List<Collision> succeedingCollisions =
928                getSucceedingCollisions(subsequence, locations, potentialSuccessors, appData);
929           
930            if ((precedingCollisions.size() <= 0) && (succeedingCollisions.size() <= 0)) {
931                // subsequence is not interleaving with others. Check next one.
932                continue;
933            }
934           
935            interleavings.add(new InterleavingSubsequence(subsequence, precedingCollisions,
936                                                          succeedingCollisions));
937        }
938       
939        return interleavings;
940    }
941
942    /**
943     *
944     */
945    private void getInterleavingSubsequences(Subsequence       subsequence,
946                                             Subsequences      allSubsequences,
947                                             List<Subsequence> potentialPredecessors,
948                                             List<Subsequence> potentialSuccessors)
949    {
950        TaskComparator comparator = identityTaskHandlingStrategy.getTaskComparator();
951       
952        for (Subsequence candidate : allSubsequences) {
953            if (comparator.equals(subsequence.get(subsequence.size() - 1), candidate.get(0))) {
954                potentialSuccessors.add(candidate);
955            }
956           
957            if (comparator.equals(subsequence.get(0), candidate.get(candidate.size() - 1))) {
958                potentialPredecessors.add(candidate);
959            }
960        }
961
962        // >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
963        // >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> TEST IMPLEMENTATION >>>>>>>>>>>>>>>>>>>>>>>>>>>>>
964        // Console.traceln(Level.FINEST, "  potential successors of " + toPlainStr(subsequence));
965        // dumpSortedCollectionOfSubsequences("    ", potentialSuccessors);
966       
967        // Console.traceln(Level.FINEST, "  potential predecessors of " + toPlainStr(subsequence));
968        // dumpSortedCollectionOfSubsequences("    ", potentialPredecessors);
969        // <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
970        // <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< TEST IMPLEMENTATION <<<<<<<<<<<<<<<<<<<<<<<<<<<<<
971    }
972
973    /**
974     *
975     */
976    private Map<Subsequence, List<SubsequenceLocation>> getLocations(Subsequences        subsequences,
977                                                                     RuleApplicationData appData)
978    {
979        Map<Subsequence, List<SubsequenceLocation>> result =
980            new IdentityHashMap<Subsequence, List<SubsequenceLocation>>();
981       
982        // fill the map with empty locations
983        for (Subsequence subsequence : subsequences) {
984            result.put(subsequence, new LinkedList<SubsequenceLocation>());
985        }
986       
987        LinkedList<LinkedList<Subsequence>> candidates = new LinkedList<LinkedList<Subsequence>>();
988
989        for (IUserSession session : appData.getSessions()) {
990            for (int i = 0; i < session.size(); i++) {
991                ITask currentTask = session.get(i).getTask();
992               
993                // create a list of candidates that may start here
994                LinkedList<Subsequence> candidatesToStartHere = new LinkedList<Subsequence>();
995               
996                for (Subsequence candidate : subsequences) {
997                    if (candidate.get(0) == currentTask) {
998                        candidatesToStartHere.add(candidate);
999                    }
1000                }
1001               
1002                candidates.addFirst(candidatesToStartHere);
1003               
1004                // check if the other candidates continue here.
1005                ListIterator<LinkedList<Subsequence>> candidatesIt = candidates.listIterator(1);
1006                int index = 1;
1007                while (candidatesIt.hasNext()) {
1008                    ListIterator<Subsequence> candidateIt = candidatesIt.next().listIterator();
1009                    while (candidateIt.hasNext()) {
1010                        Subsequence candidate = candidateIt.next();
1011                       
1012                        if (candidate.get(index) == currentTask) {
1013                            if (candidate.size() == (index + 1)) {
1014                                // subsequence was fully matched --> store location
1015                                result.get(candidate).add
1016                                    (new SubsequenceLocation(session, i - candidate.size() + 1));
1017                                candidateIt.remove();
1018                            }
1019                        }
1020                        else if (candidate.get(index) != currentTask) {
1021                            // remove the candidate as it is not located here
1022                            candidateIt.remove();
1023                        }
1024                    }
1025                   
1026                    index++;
1027                }
1028               
1029                // remove potential continuation being empty
1030                while ((candidates.size() > 0) && (candidates.getLast().size() == 0)) {
1031                    candidates.removeLast();
1032                }
1033            }
1034        }
1035       
1036        return result;
1037    }
1038
1039    /**
1040     *
1041     */
1042    private List<Collision> getPrecedingCollisions(Subsequence               subsequence,
1043                                                   List<SubsequenceLocation> locations,
1044                                                   List<Subsequence>         potentialPredecessors,
1045                                                   RuleApplicationData       appData)
1046    {
1047        List<Collision> precedingCollisions = new LinkedList<Collision>();
1048        int interleavingStartIndex;
1049        int interleavingEndIndex;
1050       
1051        for (SubsequenceLocation location : locations) {
1052            for (Subsequence predecessor : potentialPredecessors) {
1053                // start where the interleaving would start
1054                interleavingStartIndex = location.getIndex() - predecessor.size() + 1;
1055               
1056                if (interleavingStartIndex >= 0) {
1057                    interleavingEndIndex =
1058                        getSubListIndex(location.getSession(), predecessor, interleavingStartIndex);
1059               
1060                    if (interleavingStartIndex == interleavingEndIndex) {
1061                        precedingCollisions.add(new Collision(location, subsequence, predecessor));
1062                    }
1063                }
1064            }
1065        }
1066       
1067        return precedingCollisions;
1068    }
1069
1070    /**
1071     *
1072     */
1073    private List<Collision> getSucceedingCollisions(Subsequence               subsequence,
1074                                                    List<SubsequenceLocation> locations,
1075                                                    List<Subsequence>         potentialPredecessors,
1076                                                    RuleApplicationData       appData)
1077    {
1078        List<Collision> succeedingCollisions = new LinkedList<Collision>();
1079        int interleavingStartIndex;
1080        int interleavingEndIndex;
1081
1082        for (SubsequenceLocation location : locations) {
1083            for (Subsequence successor : potentialPredecessors) {
1084                interleavingStartIndex = location.getIndex() + subsequence.size() - 1;
1085                interleavingEndIndex =
1086                    getSubListIndex(location.getSession(), successor, interleavingStartIndex);
1087
1088                if (interleavingStartIndex == interleavingEndIndex) {
1089                    succeedingCollisions.add(new Collision(location, subsequence, successor));
1090                }
1091            }
1092        }
1093       
1094        return succeedingCollisions;
1095    }
1096   
1097    /**
1098     *
1099     */
1100    private List<InterleavingSubsequence> getMostIntensiveInterleavings
1101        (List<InterleavingSubsequence> interleavings)
1102    {
1103        List<InterleavingSubsequence> mostIntensiveInterleavings =
1104            new LinkedList<InterleavingSubsequence>();
1105       
1106        int collisionCounter = 0;
1107       
1108        for (InterleavingSubsequence interleaving : interleavings) {
1109            if (interleaving.getCollisionCounter() > collisionCounter) {
1110                collisionCounter = interleaving.getCollisionCounter();
1111                mostIntensiveInterleavings.clear();
1112            }
1113           
1114            if (interleaving.getCollisionCounter() == collisionCounter) {
1115                mostIntensiveInterleavings.add(interleaving);
1116            }
1117        }
1118       
1119        return mostIntensiveInterleavings;
1120    }
1121
1122    /**
1123     *
1124     */
1125    private List<InterleavingSubsequence> getLeastInterleavingsAsPredecessor
1126        (List<InterleavingSubsequence> interleavings)
1127    {
1128        List<InterleavingSubsequence> leastInterleavingsAsPredecessor =
1129            new LinkedList<InterleavingSubsequence>();
1130           
1131        int collisionCounter = Integer.MAX_VALUE;
1132
1133        for (InterleavingSubsequence interleaving : interleavings) {
1134            if (interleaving.getSuccessorCollisionCounter() < collisionCounter) {
1135                collisionCounter = interleaving.getSuccessorCollisionCounter();
1136                leastInterleavingsAsPredecessor.clear();
1137            }
1138
1139            if (interleaving.getSuccessorCollisionCounter() == collisionCounter) {
1140                leastInterleavingsAsPredecessor.add(interleaving);
1141            }
1142        }
1143
1144        return leastInterleavingsAsPredecessor;
1145    }
1146
1147    /**
1148     *
1149     */
1150    private List<InterleavingSubsequence> getMostInterleavingsAsSuccessor
1151        (List<InterleavingSubsequence> interleavings)
1152    {
1153        List<InterleavingSubsequence> mostInterleavingsAsSuccessor =
1154            new LinkedList<InterleavingSubsequence>();
1155           
1156        int collisionCounter = 0;
1157
1158        for (InterleavingSubsequence interleaving : interleavings) {
1159            if (interleaving.getPredecessorCollisionCounter() > collisionCounter) {
1160                collisionCounter = interleaving.getPredecessorCollisionCounter();
1161                mostInterleavingsAsSuccessor.clear();
1162            }
1163
1164            if (interleaving.getPredecessorCollisionCounter() == collisionCounter) {
1165                mostInterleavingsAsSuccessor.add(interleaving);
1166            }
1167        }
1168
1169        return mostInterleavingsAsSuccessor;
1170    }
1171
1172    /**
1173     *
1174     */
1175    private List<InterleavingSubsequence> removeCollisionsOfOtherSubsequences
1176        (List<InterleavingSubsequence> interleavings)
1177    {
1178        List<InterleavingSubsequence> subsequencesWithoutOtherCollisions =
1179            new LinkedList<InterleavingSubsequence>();
1180       
1181        for (InterleavingSubsequence interleaving : interleavings) {
1182            List<Collision> reducedPredecessorCollisions = new LinkedList<>();
1183           
1184            for (Collision collision : interleaving.getPredecessorCollisions()) {
1185                for (InterleavingSubsequence otherInterleaving : interleavings) {
1186                    if (otherInterleaving.getSubsequence() == collision.getCollidingWith()) {
1187                        reducedPredecessorCollisions.add(collision);
1188                        break;
1189                    }
1190                }
1191            }
1192           
1193            List<Collision> reducedSuccessorCollisions = new LinkedList<>();
1194           
1195            for (Collision collision : interleaving.getSuccessorCollisions()) {
1196                for (InterleavingSubsequence otherInterleaving : interleavings) {
1197                    if (otherInterleaving.getSubsequence() == collision.getCollidingWith()) {
1198                        reducedSuccessorCollisions.add(collision);
1199                        break;
1200                    }
1201                }
1202            }
1203           
1204            subsequencesWithoutOtherCollisions.add
1205                (new InterleavingSubsequence(interleaving.getSubsequence(),
1206                                             reducedPredecessorCollisions,
1207                                             reducedSuccessorCollisions));
1208        }
1209       
1210        return subsequencesWithoutOtherCollisions;
1211    }
1212
1213    /**
1214     * @param appData the rule application data combining all data used for applying this rule
1215     */
1216    private void replaceSequencesOccurringMostOften(RuleApplicationData appData) {
1217        appData.detectedAndReplacedTasks(false);
1218
1219        if ((appData.getLastFoundSubsequences().size() > 0) &&
1220            (appData.getLastFoundSubsequences().getOccurrenceCount() > 1))
1221        {
1222            Console.traceln(Level.FINER, "replacing tasks occurrences");
1223
1224            for (Subsequence subsequence : appData.getLastFoundSubsequences()) {
1225                ISequence sequence = taskFactory.createNewSequence();
1226               
1227                Console.traceln(Level.FINEST, "replacing " + sequence.getId() + ": " + subsequence);
1228
1229                List<ISequenceInstance> sequenceInstances = replaceSubsequenceOccurrences
1230                    (subsequence, appData.getSessions(), sequence);
1231               
1232                harmonizeSequenceInstancesModel(sequence, sequenceInstances, subsequence.size());
1233                appData.detectedAndReplacedTasks
1234                    (appData.detectedAndReplacedTasks() || (sequenceInstances.size() > 0));
1235
1236                if (sequenceInstances.size() < appData.getLastFoundSubsequences().getOccurrenceCount()) {
1237                    Console.traceln(Level.FINE, sequence.getId() + ": replaced task only " +
1238                                    sequenceInstances.size() + " times instead of expected " +
1239                                    appData.getLastFoundSubsequences().getOccurrenceCount());
1240                }
1241            }
1242        }
1243    }
1244
1245    /**
1246     *
1247     */
1248    private void harmonizeSequenceInstancesModel(ISequence               sequence,
1249                                                 List<ISequenceInstance> sequenceInstances,
1250                                                 int                     sequenceLength)
1251    {
1252        TaskComparator comparator = preparationTaskHandlingStrategy.getTaskComparator();
1253       
1254        // ensure for each subtask that lexically different variants are preserved
1255        for (int subTaskIndex = 0; subTaskIndex < sequenceLength; subTaskIndex++) {
1256            List<ITask> subTaskVariants = new LinkedList<ITask>();
1257           
1258            for (ISequenceInstance sequenceInstance : sequenceInstances) {
1259                ITask candidate = sequenceInstance.get(subTaskIndex).getTask();
1260               
1261                boolean found = false;
1262               
1263                for (int i = 0; i < subTaskVariants.size(); i++) {
1264                    if (comparator.areLexicallyEqual(subTaskVariants.get(i), candidate)) {
1265                        taskBuilder.setTask
1266                            (sequenceInstance.get(subTaskIndex), subTaskVariants.get(i));
1267                       
1268                        found = true;
1269                        break;
1270                    }
1271                }
1272               
1273                if (!found) {
1274                    subTaskVariants.add(candidate);
1275                }
1276            }
1277           
1278            // if there are more than one lexically different variant of the sub task at
1279            // the considered position, adapt the sequence model at that position to have
1280            // a selection of the different variants. In this case also adapt the
1281            // generated sequence instances to correctly contain selection instances. If
1282            // there is only one variant of sub tasks at the given position, simply set
1283            // this variant as the sub task of the selection. In this case, the instances
1284            // can be preserved as is
1285            if (subTaskVariants.size() > 1) {
1286                ISelection selection = taskFactory.createNewSelection();
1287               
1288                for (ITask variant : subTaskVariants) {
1289                    taskBuilder.addChild(selection, variant);
1290                }
1291               
1292                taskBuilder.addChild(sequence, selection);
1293               
1294                for (ISequenceInstance instance : sequenceInstances) {
1295                    ISelectionInstance selectionInstance =
1296                        taskFactory.createNewTaskInstance(selection);
1297                    taskBuilder.setChild(selectionInstance, instance.get(subTaskIndex));
1298                    taskBuilder.setTaskInstance(instance, subTaskIndex, selectionInstance);
1299                }
1300            }
1301            else if (subTaskVariants.size() == 1) {
1302                taskBuilder.addChild(sequence, subTaskVariants.get(0));
1303            }
1304        }
1305    }
1306
1307    /**
1308     * @param tree
1309     */
1310    private List<ISequenceInstance> replaceSubsequenceOccurrences(Subsequence         subsequence,
1311                                                                  List<IUserSession>  sessions,
1312                                                                  ISequence           temporalTaskModel)
1313    {
1314        List<ISequenceInstance> sequenceInstances = new LinkedList<ISequenceInstance>();
1315       
1316        for (IUserSession session : sessions) {
1317            int index = -1;
1318           
1319            do {
1320                index = getSubListIndex(session, subsequence, ++index);
1321
1322                if (index > -1) {
1323                    // subsequence is found --> perform replacement
1324                    sequenceInstances.add
1325                        (RuleUtils.createNewSubSequenceInRange
1326                             (session, index, index + subsequence.size() - 1, temporalTaskModel,
1327                              taskFactory, taskBuilder));
1328                }
1329            }
1330            while (index > -1);
1331        }
1332       
1333        return sequenceInstances;
1334    }
1335
1336    /**
1337     * @param trie
1338     * @param object
1339     * @return
1340     */
1341    private int getSubListIndex(ITaskInstanceList   list,
1342                                Subsequence         subsequence,
1343                                int                 startIndex)
1344    {
1345        boolean matchFound;
1346        int result = -1;
1347       
1348        for (int i = startIndex; i <= list.size() - subsequence.size(); i++) {
1349            matchFound = true;
1350           
1351            for (int j = 0; j < subsequence.size(); j++) {
1352                // we prepared the task instances to refer to unique tasks, if they are treated
1353                // as equal. Therefore, we just compare the identity of the tasks of the task
1354                // instances
1355                if (list.get(i + j).getTask() != subsequence.get(j)) {
1356                    matchFound = false;
1357                    break;
1358                }
1359            }
1360           
1361            if (matchFound) {
1362                result = i;
1363                break;
1364            }
1365        }
1366       
1367        return result;
1368    }
1369
1370    /**
1371     * @param trie
1372     * @param object
1373     * @return
1374     */
1375    private int getSubListIndex(Subsequence longerSubsequence,
1376                                Subsequence shorterSubsequence,
1377                                int         startIndex)
1378    {
1379        boolean matchFound;
1380        int result = -1;
1381       
1382        for (int i = startIndex; i <= longerSubsequence.size() - shorterSubsequence.size(); i++) {
1383            matchFound = true;
1384           
1385            for (int j = 0; j < shorterSubsequence.size(); j++) {
1386                // we prepared the task instances to refer to unique tasks, if they are treated
1387                // as equal. Therefore, we just compare the identity of the tasks of the task
1388                // instances
1389                if (longerSubsequence.get(i + j) != shorterSubsequence.get(j)) {
1390                    matchFound = false;
1391                    break;
1392                }
1393            }
1394           
1395            if (matchFound) {
1396                result = i;
1397                break;
1398            }
1399        }
1400       
1401        return result;
1402    }
1403
1404//  /**
1405//   *
1406//   */
1407//  private void dumpSorted(List<InterleavingSubsequence> interleavings) {
1408//      dumpSorted(interleavings, Level.FINEST);
1409//  }
1410
1411    /**
1412     *
1413     */
1414    private void dumpSorted(List<InterleavingSubsequence> interleavings, Level level) {
1415        List<String> tmpList = new LinkedList<String>();
1416
1417        for (InterleavingSubsequence interleaving : interleavings) {
1418            String taskStr = toPlainStr(interleaving);
1419            int index;
1420            for (index = 0; index < tmpList.size(); index++) {
1421                if (taskStr.compareTo(tmpList.get(index)) > 0) {
1422                    break;
1423                }
1424            }
1425
1426            tmpList.add(index, taskStr);
1427        }
1428
1429        for (String task : tmpList) {
1430            Console.traceln(level, task);
1431        }
1432    }
1433
1434//    /**
1435//     *
1436//     */
1437//    private void dumpSortedCollectionOfSubsequences(String                  prefix,
1438//                                                    Collection<Subsequence> subsequences)
1439//    {
1440//        List<String> tmpList = new LinkedList<String>();
1441//
1442//        for (Subsequence subsequence : subsequences) {
1443//            String taskStr = toPlainStr(subsequence);
1444//            int index;
1445//            for (index = 0; index < tmpList.size(); index++) {
1446//                if (taskStr.compareTo(tmpList.get(index)) > 0) {
1447//                    break;
1448//                }
1449//            }
1450//
1451//            tmpList.add(index, taskStr);
1452//        }
1453//
1454//        for (String task : tmpList) {
1455//            Console.traceln(Level.FINEST, prefix + " " + task);
1456//        }
1457//    }
1458
1459    /**
1460     *
1461     */
1462    private String toPlainStr(InterleavingSubsequence interleaving) {
1463        StringBuffer result = new StringBuffer();
1464        result.append("interleavings of ");
1465        result.append(toPlainStr(interleaving.getSubsequence()));
1466        result.append("\n  predecessor collisions:\n");
1467
1468        for (Collision collision : interleaving.getPredecessorCollisions()) {
1469            result.append("    ");
1470            result.append(toPlainStr(collision.getCollidingWith()));
1471            result.append(" (");
1472            result.append(collision.getLocation());
1473            result.append(")\n");
1474        }
1475
1476        result.append("  successor collisions:\n");
1477
1478        for (Collision collision : interleaving.getSuccessorCollisions()) {
1479            result.append("    ");
1480            result.append(toPlainStr(collision.getCollidingWith()));
1481            result.append(" (");
1482            result.append(collision.getLocation());
1483            result.append(")\n");
1484        }
1485
1486        return result.toString();
1487    }
1488
1489    /**
1490     *
1491     */
1492    private String toPlainStr(Subsequence subsequence) {
1493        StringBuffer result = new StringBuffer();
1494        result.append(subsequence.size());
1495        result.append(": ");
1496        for (ITask task : subsequence) {
1497            DebuggingHelper.toPlainStr(task, result);
1498            result.append(" --> ");
1499        }
1500
1501        return result.toString();
1502    }
1503   
1504   
1505    /**
1506     * @author Patrick Harms
1507     */
1508    private class MaxCountAndLongestSubsequencesFinder implements TrieProcessor<ITask> {
1509       
1510        /**
1511         *
1512         */
1513        private int currentCount;
1514       
1515        /**
1516         *
1517         */
1518        private LinkedList<Subsequence> foundSubsequences = new LinkedList<Subsequence>();
1519
1520        /**
1521         *
1522         */
1523        public MaxCountAndLongestSubsequencesFinder() {
1524            super();
1525            this.currentCount = 0;
1526        }
1527
1528        /* (non-Javadoc)
1529         * @see de.ugoe.cs.autoquest.usageprofiles.TrieProcessor#process(java.util.List, int)
1530         */
1531        @Override
1532        public TrieProcessor.Result process(List<ITask> foundTask, int count) {
1533            if (foundTask.size() < 2) {
1534                // ignore single tasks
1535                return TrieProcessor.Result.CONTINUE;
1536            }
1537           
1538            if (count < 2) {
1539                // ignore singular occurrences
1540                return TrieProcessor.Result.SKIP_NODE;
1541            }
1542
1543            if (this.currentCount > count) {
1544                // ignore this children of this task, as they may have only smaller counts than
1545                // the already found tasks
1546                return TrieProcessor.Result.SKIP_NODE;
1547            }
1548           
1549            if (this.currentCount < count) {
1550                // the provided task occurs more often that all tasks found so far.
1551                // clear all found tasks and use the new count as the one searched for
1552                foundSubsequences.clear();
1553                this.currentCount = count;
1554            }
1555           
1556            if (this.currentCount == count) {
1557                // the task is of interest. Sort it into the other found tasks so that
1558                // the longest come first
1559                boolean added = false;
1560                for (int i = 0; i < foundSubsequences.size(); i++) {
1561                    if (foundSubsequences.get(i).size() < foundTask.size()) {
1562                        foundSubsequences.add(i, new Subsequence(currentCount, foundTask));
1563                        added = true;
1564                        break;
1565                    }
1566                }
1567               
1568                if (!added) {
1569                    foundSubsequences.add(new Subsequence(currentCount, foundTask));
1570                }
1571            }
1572           
1573            return TrieProcessor.Result.CONTINUE;
1574        }
1575
1576        /**
1577         *  @return
1578         */
1579        private Subsequences getFoundSubsequences() {
1580            removePermutationsOfShorterTasks();
1581            return new Subsequences(currentCount, foundSubsequences);
1582        }
1583
1584        /**
1585         *
1586         */
1587        private void removePermutationsOfShorterTasks() {
1588            // now iterate the sorted list and for each task remove all other tasks that are shorter
1589            // (i.e. come later in the sorted list) and that represent a subpart of the task
1590           
1591            boolean removeI;
1592           
1593            for (int i = 0; i < foundSubsequences.size();) {
1594                removeI = false;
1595                boolean removeJ;
1596               
1597                for (int j = i + 1; j < foundSubsequences.size();) {
1598                    removeJ = false;
1599                   
1600                    if (foundSubsequences.get(j).size() < foundSubsequences.get(i).size()) {
1601                        // found a task that is a potential subtask. Check for this and remove the
1602                        // subtask if needed
1603                        Subsequence longTask = foundSubsequences.get(i);
1604                        Subsequence shortTask = foundSubsequences.get(j);
1605                       
1606                        int index = getSubListIndex(longTask, shortTask, 0);
1607                        if (index > -1) {
1608                            if (index == 0) {
1609                                // check if the short task is included in the long task partially
1610                                // a second time. If so, prefer the short task
1611                                boolean secondInclude = true;
1612                                for (int pos = shortTask.size(); pos < longTask.size(); pos++) {
1613                                    // we prepared the task instances to refer to unique tasks, if
1614                                    // they are treated as equal. Therefore, we just compare the
1615                                    // identity of the tasks of the task instances
1616                                    if (longTask.get(pos) != shortTask.get(pos % shortTask.size()))
1617                                    {
1618                                        secondInclude = false;
1619                                        break;
1620                                    }
1621                                }
1622                               
1623                                if (secondInclude) {
1624                                    // delete the long task
1625                                    // Console.traceln(Level.FINEST, "1: short task is contained several times in longer one --> removing it");
1626                                    // Console.traceln(Level.FINEST, "short: " + toPlainStr(shortTask));
1627                                    // Console.traceln(Level.FINEST, "long: " + toPlainStr(longTask));
1628                                    removeI = true;
1629                                }
1630                                else {
1631                                    // Console.traceln(Level.FINEST, "2: short task is a part of a longer one --> removing it");
1632                                    // Console.traceln(Level.FINEST, "short: " + toPlainStr(shortTask));
1633                                    // Console.traceln(Level.FINEST, "long: " + toPlainStr(longTask));
1634                                    removeJ = true;
1635                                }
1636                            }
1637                            else {
1638                                // Console.traceln(Level.FINEST, "3: short task is a part of a longer one --> removing it");
1639                                // Console.traceln(Level.FINEST, "short: " + toPlainStr(shortTask));
1640                                // Console.traceln(Level.FINEST, "long: " + toPlainStr(longTask));
1641                                removeJ = true;
1642                            }
1643                        }
1644                    }
1645                   
1646                    if (removeJ) {
1647                        foundSubsequences.remove(j);
1648                    }
1649                    else {
1650                        j++;
1651                    }
1652                }
1653               
1654                if (removeI) {
1655                    foundSubsequences.remove(i);
1656                }
1657                else {
1658                    i++;
1659                }
1660            }
1661        }
1662
1663    }
1664
1665//    /**
1666//     * @author Patrick Harms
1667//     */
1668//    private class TrieStatisticsDumper implements TrieProcessor<ITaskInstance> {
1669//       
1670//        /**
1671//         *
1672//         */
1673//        private Map<Integer, Integer> counters = new HashMap<Integer, Integer>();
1674//       
1675//        /* (non-Javadoc)
1676//         * @see de.ugoe.cs.autoquest.usageprofiles.TrieProcessor#process(java.util.List, int)
1677//         */
1678//        @Override
1679//        public TrieProcessor.Result process(List<ITaskInstance> subsequence, int count) {
1680//            if (subsequence.size() == 1) {
1681//                Integer value = counters.get(count);
1682//               
1683//                if (value == null) {
1684//                    value = 0;
1685//                }
1686//               
1687//                counters.put(count, value + 1);
1688//               
1689//                return TrieProcessor.Result.CONTINUE;
1690//            }
1691//            else {
1692//                // ignore singular occurrences
1693//                return TrieProcessor.Result.SKIP_NODE;
1694//            }
1695//        }
1696//
1697//        /**
1698//         *  @return
1699//         */
1700//        public void dumpCounters() {
1701//            int dumpedCounters = 0;
1702//           
1703//            int count = 1;
1704//            while (dumpedCounters < counters.size()) {
1705//                Integer value = counters.get(count++);
1706//                if (value != null) {
1707//                    System.out.println(value + " symbols occurred " + count + " times");
1708//                    dumpedCounters++;
1709//                }
1710//            }
1711//        }
1712//
1713//    }
1714   
1715    /**
1716     *
1717     */
1718    private static class RuleApplicationData {
1719       
1720        /**
1721         *
1722         */
1723        private List<IUserSession> sessions;
1724       
1725        /**
1726         *
1727         */
1728        private TaskInstanceTrie lastTrie;
1729       
1730        /**
1731         * default and minimum trained subsequence length is 3
1732         */
1733        private int trainedSubsequenceLength = 3;
1734       
1735        /**
1736         *
1737         */
1738        private Subsequences lastFoundSubsequences = new Subsequences(Integer.MAX_VALUE, null);
1739       
1740        /**
1741         *
1742         */
1743        private boolean detectedAndReplacedTasks;
1744       
1745        /**
1746         *
1747         */
1748        private RuleApplicationResult result = new RuleApplicationResult();
1749       
1750        /**
1751         *
1752         */
1753        private StopWatch stopWatch = new StopWatch();
1754       
1755        /**
1756         *
1757         */
1758        private RuleApplicationData(List<IUserSession> sessions) {
1759            this.sessions = sessions;
1760        }
1761
1762        /**
1763         * @return the tree
1764         */
1765        private List<IUserSession> getSessions() {
1766            return sessions;
1767        }
1768
1769        /**
1770         * @param lastTrie the lastTrie to set
1771         */
1772        private void setLastTrie(TaskInstanceTrie lastTrie) {
1773            this.lastTrie = lastTrie;
1774        }
1775
1776        /**
1777         * @return the lastTrie
1778         */
1779        private TaskInstanceTrie getLastTrie() {
1780            return lastTrie;
1781        }
1782
1783        /**
1784         * @param trainedSubsequenceLength the trainedSubsequenceLength to set
1785         */
1786        private void setTrainedSubsequenceLength(int trainedSubsequenceLength) {
1787            this.trainedSubsequenceLength = trainedSubsequenceLength;
1788        }
1789
1790        /**
1791         * @return the trainedSubsequenceLength
1792         */
1793        private int getTrainedSubsequenceLength() {
1794            return trainedSubsequenceLength;
1795        }
1796
1797        /**
1798         * @param lastFoundSequences the lastFoundSequences to set
1799         */
1800        private void setLastFoundSubsequences(Subsequences lastFoundSequences) {
1801            this.lastFoundSubsequences = lastFoundSequences;
1802        }
1803
1804        /**
1805         * @return the lastFoundSequences
1806         */
1807        private Subsequences getLastFoundSubsequences() {
1808            return lastFoundSubsequences;
1809        }
1810
1811        /**
1812         *
1813         */
1814        private void detectedAndReplacedTasks(boolean detectedAndReplacedTasks) {
1815            this.detectedAndReplacedTasks = detectedAndReplacedTasks;
1816        }
1817
1818        /**
1819         *
1820         */
1821        private boolean detectedAndReplacedTasks() {
1822            return detectedAndReplacedTasks;
1823        }
1824       
1825        /**
1826         * @return the result
1827         */
1828        private RuleApplicationResult getResult() {
1829            return result;
1830        }
1831
1832        /**
1833         * @return the stopWatch
1834         */
1835        private StopWatch getStopWatch() {
1836            return stopWatch;
1837        }
1838
1839    }
1840   
1841    /**
1842     * @author Patrick Harms
1843     */
1844    private static class Subsequence implements Iterable<ITask> {
1845       
1846        /**
1847         *
1848         */
1849        private int occurrenceCount;
1850
1851        /**
1852         *
1853         */
1854        private List<ITask> subsequence;
1855       
1856        /**
1857         * @param occurrenceCount
1858         * @param subsequences
1859         */
1860        private Subsequence(int occurrenceCount, List<ITask> subsequence) {
1861            super();
1862            this.occurrenceCount = occurrenceCount;
1863            this.subsequence = new ArrayList<ITask>(subsequence);
1864        }
1865
1866        /**
1867         * @return
1868         */
1869        private int size() {
1870            return this.subsequence.size();
1871        }
1872
1873        /**
1874         * @return
1875         */
1876        private ITask get(int index) {
1877            return this.subsequence.get(index);
1878        }
1879
1880        /* (non-Javadoc)
1881         * @see java.lang.Iterable#iterator()
1882         */
1883        @Override
1884        public Iterator<ITask> iterator() {
1885            return this.subsequence.iterator();
1886        }
1887
1888        /* (non-Javadoc)
1889         * @see java.lang.Object#toString()
1890         */
1891        @Override
1892        public String toString() {
1893            return subsequence.toString() + " (" + occurrenceCount + ")";
1894        }
1895    }
1896
1897    /**
1898     * @author Patrick Harms
1899     */
1900    private static class Subsequences implements Iterable<Subsequence> {
1901       
1902        /**
1903         *
1904         */
1905        private int occurrenceCount;
1906       
1907        /**
1908         *
1909         */
1910        private LinkedList<Subsequence> subsequences;
1911
1912        /**
1913         * @param occurrenceCount
1914         * @param sequences
1915         */
1916        private Subsequences(int occurrenceCount, LinkedList<Subsequence> subsequences) {
1917            super();
1918            this.occurrenceCount = occurrenceCount;
1919            this.subsequences = subsequences;
1920        }
1921
1922        /**
1923         *
1924         */
1925        private void remove(Subsequence subsequence) {
1926            ListIterator<Subsequence> it = subsequences.listIterator();
1927           
1928            while (it.hasNext()) {
1929                // reference comparison is sufficient
1930                if (it.next() == subsequence) {
1931                    it.remove();
1932                }
1933            }
1934        }
1935
1936        /**
1937         * @return
1938         */
1939        private int getOccurrenceCount() {
1940            return occurrenceCount;
1941        }
1942
1943        /**
1944         * @return
1945         */
1946        private int size() {
1947            return this.subsequences.size();
1948        }
1949
1950        /* (non-Javadoc)
1951         * @see java.lang.Iterable#iterator()
1952         */
1953        @Override
1954        public Iterator<Subsequence> iterator() {
1955            return this.subsequences.iterator();
1956        }
1957
1958        /* (non-Javadoc)
1959         * @see java.lang.Object#toString()
1960         */
1961        @Override
1962        public String toString() {
1963            StringBuffer result = new StringBuffer();
1964            result.append(" subsequences occuring ");
1965            result.append(this.occurrenceCount);
1966            result.append(" times:\n");
1967           
1968            for (Subsequence subsequence : subsequences) {
1969                result.append(subsequence);
1970                result.append("\n");
1971            }
1972           
1973            return result.toString();
1974        }
1975    }
1976   
1977    /**
1978     * @author Patrick Harms
1979     */
1980    private static class InterleavingSubsequence {
1981       
1982        /** */
1983        private Subsequence subsequence;
1984       
1985        /** */
1986        private List<Collision> successorCollisions;
1987       
1988        /** */
1989        private List<Collision> predecessorCollisions;
1990
1991        /**
1992         *
1993         */
1994        private InterleavingSubsequence(Subsequence     subsequence,
1995                                        List<Collision> predecessorCollisions,
1996                                        List<Collision> successorCollisions)
1997        {
1998            super();
1999            this.subsequence = subsequence;
2000            this.predecessorCollisions = predecessorCollisions;
2001            this.successorCollisions = successorCollisions;
2002        }
2003
2004        /**
2005         *
2006         */
2007        private int getCollisionCounter() {
2008            return getSuccessorCollisionCounter() + getPredecessorCollisionCounter();
2009        }
2010
2011        /**
2012         *
2013         */
2014        private int getSuccessorCollisionCounter() {
2015            return successorCollisions.size();
2016        }
2017
2018        /**
2019         *
2020         */
2021        private List<Collision> getSuccessorCollisions() {
2022            return successorCollisions;
2023        }
2024
2025        /**
2026         *
2027         */
2028        private int getPredecessorCollisionCounter() {
2029            return predecessorCollisions.size();
2030        }
2031
2032        /**
2033         *
2034         */
2035        private List<Collision> getPredecessorCollisions() {
2036            return predecessorCollisions;
2037        }
2038
2039        /**
2040         *
2041         */
2042        private Subsequence getSubsequence() {
2043            return subsequence;
2044        }
2045       
2046        /* (non-Javadoc)
2047         * @see java.lang.Object#toString()
2048         */
2049        @Override
2050        public String toString() {
2051            return "interleaving subsequence " + subsequence.toString() + " (" +
2052                successorCollisions.size() + " successor, " + predecessorCollisions.size() +
2053                " predecessor)";
2054        }
2055    }
2056       
2057    /**
2058     * @author Patrick Harms
2059     */
2060    private static class SubsequenceLocation {
2061       
2062        /** */
2063        private IUserSession session;
2064       
2065        /** */
2066        private int index;
2067       
2068        /**
2069         *
2070         */
2071        private SubsequenceLocation(IUserSession session, int index) {
2072            this.session = session;
2073            this.index = index;
2074        }
2075
2076        /**
2077         * @return the session
2078         */
2079        private IUserSession getSession() {
2080            return session;
2081        }
2082
2083        /**
2084         * @return the index
2085         */
2086        private int getIndex() {
2087            return index;
2088        }
2089       
2090        /* (non-Javadoc)
2091         * @see java.lang.Object#toString()
2092         */
2093        @Override
2094        public String toString() {
2095            return "location (" + session + ", " + index + ")";
2096        }
2097    }
2098   
2099    /**
2100     * @author Patrick Harms
2101     */
2102    private static class Collision {
2103       
2104        /** */
2105        private SubsequenceLocation location;
2106       
2107        /** */
2108        private Subsequence subsequence;
2109       
2110        /** */
2111        private Subsequence collidingWith;
2112       
2113        /**
2114         *
2115         */
2116        private Collision(SubsequenceLocation location,
2117                          Subsequence         subsequence,
2118                          Subsequence         collidingWith)
2119        {
2120            this.location = location;
2121            this.subsequence = subsequence;
2122            this.collidingWith = collidingWith;
2123        }
2124
2125        /**
2126         * @return the collidingWith
2127         */
2128        private Subsequence getCollidingWith() {
2129            return collidingWith;
2130        }
2131
2132        /**
2133         * @return the location
2134         */
2135        private SubsequenceLocation getLocation() {
2136            return location;
2137        }
2138
2139        /**
2140         * @return the subsequence
2141         */
2142        private Subsequence getSubsequence() {
2143            return subsequence;
2144        }
2145
2146        /* (non-Javadoc)
2147         * @see java.lang.Object#toString()
2148         */
2149        @Override
2150        public String toString() {
2151            return "collision (" + location + " ," + subsequence + ", " + collidingWith + ")";
2152        }
2153    }
2154   
2155    // methods for internal testing
2156//    private void checkMatchingOfSessions(List<List<Event>>  flattenedSessions,
2157//                                         List<IUserSession> sessions,
2158//                                         String             when)
2159//    {
2160//        List<List<Event>> currentFlattenedSessions = flattenSessions(sessions);
2161//        if (flattenedSessions.size() != currentFlattenedSessions.size()) {
2162//            System.out.println("################## number of sessions changed after " + when);
2163//        }
2164//        else {
2165//            for (int i = 0; i < flattenedSessions.size(); i++) {
2166//                List<Event> expected = flattenedSessions.get(i);
2167//                List<Event> current = currentFlattenedSessions.get(i);
2168//           
2169//                if (expected.size() != current.size()) {
2170//                    System.out.println
2171//                        ("################## length of session " + i + " changed after " + when);
2172//                }
2173//                else {
2174//                    for (int j = 0; j < expected.size(); j++) {
2175//                        if (!expected.get(j).equals(current.get(j))) {
2176//                            System.out.println("################## event " + j + " of session " +
2177//                                               i + " changed after " + when);
2178//                        }
2179//                    }
2180//                }
2181//            }     
2182//        }
2183//    }
2184//
2185//    private List<List<Event>> flattenSessions(List<IUserSession> sessions) {
2186//        List<List<Event>> flattenedSessions = new ArrayList<List<Event>>();
2187//        for (IUserSession session : sessions) {
2188//            List<Event> flattenedUserSession = new ArrayList<Event>();
2189//            flatten(session, flattenedUserSession);
2190//            flattenedSessions.add(flattenedUserSession);
2191//        }
2192//
2193//        return flattenedSessions;
2194//    }
2195//
2196//    private void flatten(IUserSession iUserSession, List<Event> flattenedUserSession) {
2197//        for (ITaskInstance instance : iUserSession) {
2198//            flatten(instance, flattenedUserSession);
2199//        }
2200//    }
2201//
2202//    private void flatten(ITaskInstance instance, List<Event> flattenedUserSession) {
2203//        if (instance instanceof ITaskInstanceList) {
2204//            for (ITaskInstance child : (ITaskInstanceList) instance) {
2205//                flatten(child, flattenedUserSession);
2206//            }
2207//        }
2208//        else if (instance instanceof ISelectionInstance) {
2209//            flatten(((ISelectionInstance) instance).getChild(), flattenedUserSession);
2210//        }
2211//        else if (instance instanceof IOptionalInstance) {
2212//            flatten(((IOptionalInstance) instance).getChild(), flattenedUserSession);
2213//        }
2214//        else if (instance instanceof IEventTaskInstance) {
2215//            flattenedUserSession.add(((IEventTaskInstance) instance).getEvent());
2216//        }
2217//    }
2218
2219}
Note: See TracBrowser for help on using the repository browser.