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

Last change on this file since 1891 was 1888, checked in by pharms, 9 years ago
  • corrected selection of which task to detect first.
File size: 86.9 KB
Line 
1//   Copyright 2012 Georg-August-Universität Göttingen, Germany
2//
3//   Licensed under the Apache License, Version 2.0 (the "License");
4//   you may not use this file except in compliance with the License.
5//   You may obtain a copy of the License at
6//
7//       http://www.apache.org/licenses/LICENSE-2.0
8//
9//   Unless required by applicable law or agreed to in writing, software
10//   distributed under the License is distributed on an "AS IS" BASIS,
11//   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12//   See the License for the specific language governing permissions and
13//   limitations under the License.
14
15package de.ugoe.cs.autoquest.tasktrees.temporalrelation;
16
17import java.util.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() + 3);
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, check if they are indpendent. If not, throw an exception
838                int minPosInAnySequence = Integer.MAX_VALUE;
839                List<InterleavingSubsequence> subsequencesWithMinPos = new LinkedList<>();
840               
841                for (InterleavingSubsequence interleaving : interleavings) {
842                    for (Collision collision : interleaving.getSuccessorCollisions()) {
843                        if (minPosInAnySequence > collision.getLocation().getIndex()) {
844                            minPosInAnySequence = collision.getLocation().getIndex();
845                            subsequencesWithMinPos.clear();
846                        }
847                       
848                        if (minPosInAnySequence == collision.getLocation().getIndex()) {
849                            // several have the same min pos --> undecidable which to prefer
850                            subsequencesWithMinPos.add(interleaving);
851                        }
852                    }
853                }
854               
855                if (subsequencesWithMinPos.size() > 0) {
856                    List<Subsequence> subsequencesToRemove = new LinkedList<Subsequence>();
857                   
858                    for (Subsequence candidate : appData.getLastFoundSubsequences()) {
859                        boolean found = false;
860                       
861                        for (InterleavingSubsequence subsequenceWithMinPos : subsequencesWithMinPos)
862                        {
863                            if (candidate == subsequenceWithMinPos.getSubsequence()) {
864                                found = true;
865                            }
866                        }
867                       
868                        if (!found) {
869                            subsequencesToRemove.add(candidate);
870                        }
871                    }
872                   
873                    if (subsequencesToRemove.size() > 0) {
874                        for (Subsequence candidate : subsequencesToRemove) {
875                            appData.getLastFoundSubsequences().remove(candidate);
876                        }
877                   
878                        continue;
879                    }
880                }
881               
882                // At this point, we can not decide anymore. But it should also not
883                // happen. Even if two subsequences ab and ba one of them should be
884                // more often a successor or predecessor than the other if they
885                // directly follow each other. If not, it can not be decided, which of
886                // them to replace first. Perhaps the one occurring more often as
887                // the first in a session that the other. But this can be implemented
888                // later.
889                dumpSorted(interleavings, Level.SEVERE);
890               
891                throw new RuntimeException
892                    ("can not decide which detected subsequence to replace first.");
893            }
894        }
895        while (interleavings.size() > 0);
896
897        // >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
898        // >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> TEST IMPLEMENTATION >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
899        // dumpSortedCollectionOfSubsequences
900        //    ("to replace", appData.getLastFoundSubsequences().subsequences);
901        // <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
902        // <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< TEST IMPLEMENTATION <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
903    }
904
905    /**
906     *
907     */
908    private List<InterleavingSubsequence> getInterleavings(Subsequences        subsequences,
909                                                           RuleApplicationData appData)
910    {
911        List<InterleavingSubsequence> interleavings = new LinkedList<InterleavingSubsequence>();
912        List<Subsequence> potentialPredecessors = new LinkedList<Subsequence>();
913        List<Subsequence> potentialSuccessors = new LinkedList<Subsequence>();
914       
915        Map<Subsequence, List<SubsequenceLocation>> allLocations =
916            getLocations(subsequences, appData);
917       
918        for (Subsequence subsequence : subsequences) {
919            // Console.traceln
920            //    (Level.FINEST, "searching for interleavings of " + toPlainStr(subsequence));
921
922            potentialPredecessors.clear();
923            potentialSuccessors.clear();
924           
925            getInterleavingSubsequences
926                (subsequence, subsequences, potentialPredecessors, potentialSuccessors);
927           
928            if ((potentialPredecessors.size() <= 0) && (potentialSuccessors.size() <= 0)) {
929                // subsequence is not interleaving with others. Check next one.
930                continue;
931            }
932           
933            // subsequence is interleaving. First, determine its locations in the user sessions.
934            List<SubsequenceLocation> locations = allLocations.get(subsequence);
935           
936            List<Collision> precedingCollisions =
937                getPrecedingCollisions(subsequence, locations, potentialPredecessors, appData);
938           
939            List<Collision> succeedingCollisions =
940                getSucceedingCollisions(subsequence, locations, potentialSuccessors, appData);
941           
942            if ((precedingCollisions.size() <= 0) && (succeedingCollisions.size() <= 0)) {
943                // subsequence is not interleaving with others. Check next one.
944                continue;
945            }
946           
947            interleavings.add(new InterleavingSubsequence(subsequence, precedingCollisions,
948                                                          succeedingCollisions));
949        }
950       
951        return interleavings;
952    }
953
954    /**
955     *
956     */
957    private void getInterleavingSubsequences(Subsequence       subsequence,
958                                             Subsequences      allSubsequences,
959                                             List<Subsequence> potentialPredecessors,
960                                             List<Subsequence> potentialSuccessors)
961    {
962        TaskComparator comparator = identityTaskHandlingStrategy.getTaskComparator();
963       
964        for (Subsequence candidate : allSubsequences) {
965            if (comparator.equals(subsequence.get(subsequence.size() - 1), candidate.get(0))) {
966                potentialSuccessors.add(candidate);
967            }
968           
969            if (comparator.equals(subsequence.get(0), candidate.get(candidate.size() - 1))) {
970                potentialPredecessors.add(candidate);
971            }
972        }
973
974        // >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
975        // >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> TEST IMPLEMENTATION >>>>>>>>>>>>>>>>>>>>>>>>>>>>>
976        // Console.traceln(Level.FINEST, "  potential successors of " + toPlainStr(subsequence));
977        // dumpSortedCollectionOfSubsequences("    ", potentialSuccessors);
978       
979        // Console.traceln(Level.FINEST, "  potential predecessors of " + toPlainStr(subsequence));
980        // dumpSortedCollectionOfSubsequences("    ", potentialPredecessors);
981        // <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
982        // <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< TEST IMPLEMENTATION <<<<<<<<<<<<<<<<<<<<<<<<<<<<<
983    }
984
985    /**
986     *
987     */
988    private Map<Subsequence, List<SubsequenceLocation>> getLocations(Subsequences        subsequences,
989                                                                     RuleApplicationData appData)
990    {
991        Map<Subsequence, List<SubsequenceLocation>> result =
992            new IdentityHashMap<Subsequence, List<SubsequenceLocation>>();
993       
994        // fill the map with empty locations
995        for (Subsequence subsequence : subsequences) {
996            result.put(subsequence, new LinkedList<SubsequenceLocation>());
997        }
998       
999        LinkedList<LinkedList<Subsequence>> candidates = new LinkedList<LinkedList<Subsequence>>();
1000
1001        for (IUserSession session : appData.getSessions()) {
1002            for (int i = 0; i < session.size(); i++) {
1003                ITask currentTask = session.get(i).getTask();
1004               
1005                // create a list of candidates that may start here
1006                LinkedList<Subsequence> candidatesToStartHere = new LinkedList<Subsequence>();
1007               
1008                for (Subsequence candidate : subsequences) {
1009                    if (candidate.get(0) == currentTask) {
1010                        candidatesToStartHere.add(candidate);
1011                    }
1012                }
1013               
1014                candidates.addFirst(candidatesToStartHere);
1015               
1016                // check if the other candidates continue here.
1017                ListIterator<LinkedList<Subsequence>> candidatesIt = candidates.listIterator(1);
1018                int index = 1;
1019                while (candidatesIt.hasNext()) {
1020                    ListIterator<Subsequence> candidateIt = candidatesIt.next().listIterator();
1021                    while (candidateIt.hasNext()) {
1022                        Subsequence candidate = candidateIt.next();
1023                       
1024                        if (candidate.get(index) == currentTask) {
1025                            if (candidate.size() == (index + 1)) {
1026                                // subsequence was fully matched --> store location
1027                                result.get(candidate).add
1028                                    (new SubsequenceLocation(session, i - candidate.size() + 1));
1029                                candidateIt.remove();
1030                            }
1031                        }
1032                        else if (candidate.get(index) != currentTask) {
1033                            // remove the candidate as it is not located here
1034                            candidateIt.remove();
1035                        }
1036                    }
1037                   
1038                    index++;
1039                }
1040               
1041                // remove potential continuation being empty
1042                while ((candidates.size() > 0) && (candidates.getLast().size() == 0)) {
1043                    candidates.removeLast();
1044                }
1045            }
1046        }
1047       
1048        return result;
1049    }
1050
1051    /**
1052     *
1053     */
1054    private List<Collision> getPrecedingCollisions(Subsequence               subsequence,
1055                                                   List<SubsequenceLocation> locations,
1056                                                   List<Subsequence>         potentialPredecessors,
1057                                                   RuleApplicationData       appData)
1058    {
1059        List<Collision> precedingCollisions = new LinkedList<Collision>();
1060        int interleavingStartIndex;
1061        int interleavingEndIndex;
1062       
1063        for (SubsequenceLocation location : locations) {
1064            for (Subsequence predecessor : potentialPredecessors) {
1065                // start where the interleaving would start
1066                interleavingStartIndex = location.getIndex() - predecessor.size() + 1;
1067               
1068                if (interleavingStartIndex >= 0) {
1069                    interleavingEndIndex =
1070                        getSubListIndex(location.getSession(), predecessor, interleavingStartIndex);
1071               
1072                    if (interleavingStartIndex == interleavingEndIndex) {
1073                        precedingCollisions.add(new Collision(location, subsequence, predecessor));
1074                    }
1075                }
1076            }
1077        }
1078       
1079        return precedingCollisions;
1080    }
1081
1082    /**
1083     *
1084     */
1085    private List<Collision> getSucceedingCollisions(Subsequence               subsequence,
1086                                                    List<SubsequenceLocation> locations,
1087                                                    List<Subsequence>         potentialPredecessors,
1088                                                    RuleApplicationData       appData)
1089    {
1090        List<Collision> succeedingCollisions = new LinkedList<Collision>();
1091        int interleavingStartIndex;
1092        int interleavingEndIndex;
1093
1094        for (SubsequenceLocation location : locations) {
1095            for (Subsequence successor : potentialPredecessors) {
1096                interleavingStartIndex = location.getIndex() + subsequence.size() - 1;
1097                interleavingEndIndex =
1098                    getSubListIndex(location.getSession(), successor, interleavingStartIndex);
1099
1100                if (interleavingStartIndex == interleavingEndIndex) {
1101                    succeedingCollisions.add(new Collision(location, subsequence, successor));
1102                }
1103            }
1104        }
1105       
1106        return succeedingCollisions;
1107    }
1108   
1109    /**
1110     *
1111     */
1112    private List<InterleavingSubsequence> getMostIntensiveInterleavings
1113        (List<InterleavingSubsequence> interleavings)
1114    {
1115        List<InterleavingSubsequence> mostIntensiveInterleavings =
1116            new LinkedList<InterleavingSubsequence>();
1117       
1118        int collisionCounter = 0;
1119       
1120        for (InterleavingSubsequence interleaving : interleavings) {
1121            if (interleaving.getCollisionCounter() > collisionCounter) {
1122                collisionCounter = interleaving.getCollisionCounter();
1123                mostIntensiveInterleavings.clear();
1124            }
1125           
1126            if (interleaving.getCollisionCounter() == collisionCounter) {
1127                mostIntensiveInterleavings.add(interleaving);
1128            }
1129        }
1130       
1131        return mostIntensiveInterleavings;
1132    }
1133
1134    /**
1135     *
1136     */
1137    private List<InterleavingSubsequence> getLeastInterleavingsAsPredecessor
1138        (List<InterleavingSubsequence> interleavings)
1139    {
1140        List<InterleavingSubsequence> leastInterleavingsAsPredecessor =
1141            new LinkedList<InterleavingSubsequence>();
1142           
1143        int collisionCounter = Integer.MAX_VALUE;
1144
1145        for (InterleavingSubsequence interleaving : interleavings) {
1146            if (interleaving.getSuccessorCollisionCounter() < collisionCounter) {
1147                collisionCounter = interleaving.getSuccessorCollisionCounter();
1148                leastInterleavingsAsPredecessor.clear();
1149            }
1150
1151            if (interleaving.getSuccessorCollisionCounter() == collisionCounter) {
1152                leastInterleavingsAsPredecessor.add(interleaving);
1153            }
1154        }
1155
1156        return leastInterleavingsAsPredecessor;
1157    }
1158
1159    /**
1160     *
1161     */
1162    private List<InterleavingSubsequence> getMostInterleavingsAsSuccessor
1163        (List<InterleavingSubsequence> interleavings)
1164    {
1165        List<InterleavingSubsequence> mostInterleavingsAsSuccessor =
1166            new LinkedList<InterleavingSubsequence>();
1167           
1168        int collisionCounter = 0;
1169
1170        for (InterleavingSubsequence interleaving : interleavings) {
1171            if (interleaving.getPredecessorCollisionCounter() > collisionCounter) {
1172                collisionCounter = interleaving.getPredecessorCollisionCounter();
1173                mostInterleavingsAsSuccessor.clear();
1174            }
1175
1176            if (interleaving.getPredecessorCollisionCounter() == collisionCounter) {
1177                mostInterleavingsAsSuccessor.add(interleaving);
1178            }
1179        }
1180
1181        return mostInterleavingsAsSuccessor;
1182    }
1183
1184    /**
1185     *
1186     */
1187    private List<InterleavingSubsequence> removeCollisionsOfOtherSubsequences
1188        (List<InterleavingSubsequence> interleavings)
1189    {
1190        List<InterleavingSubsequence> subsequencesWithoutOtherCollisions =
1191            new LinkedList<InterleavingSubsequence>();
1192       
1193        for (InterleavingSubsequence interleaving : interleavings) {
1194            List<Collision> reducedPredecessorCollisions = new LinkedList<>();
1195           
1196            for (Collision collision : interleaving.getPredecessorCollisions()) {
1197                for (InterleavingSubsequence otherInterleaving : interleavings) {
1198                    if (otherInterleaving.getSubsequence() == collision.getCollidingWith()) {
1199                        reducedPredecessorCollisions.add(collision);
1200                        break;
1201                    }
1202                }
1203            }
1204           
1205            List<Collision> reducedSuccessorCollisions = new LinkedList<>();
1206           
1207            for (Collision collision : interleaving.getSuccessorCollisions()) {
1208                for (InterleavingSubsequence otherInterleaving : interleavings) {
1209                    if (otherInterleaving.getSubsequence() == collision.getCollidingWith()) {
1210                        reducedSuccessorCollisions.add(collision);
1211                        break;
1212                    }
1213                }
1214            }
1215           
1216            subsequencesWithoutOtherCollisions.add
1217                (new InterleavingSubsequence(interleaving.getSubsequence(),
1218                                             reducedPredecessorCollisions,
1219                                             reducedSuccessorCollisions));
1220        }
1221       
1222        return subsequencesWithoutOtherCollisions;
1223    }
1224
1225    /**
1226     * @param appData the rule application data combining all data used for applying this rule
1227     */
1228    private void replaceSequencesOccurringMostOften(RuleApplicationData appData) {
1229        appData.detectedAndReplacedTasks(false);
1230
1231        if ((appData.getLastFoundSubsequences().size() > 0) &&
1232            (appData.getLastFoundSubsequences().getOccurrenceCount() > 1))
1233        {
1234            Console.traceln(Level.FINER, "replacing tasks occurrences");
1235
1236            for (Subsequence subsequence : appData.getLastFoundSubsequences()) {
1237                ISequence sequence = taskFactory.createNewSequence();
1238               
1239                Console.traceln(Level.FINEST, "replacing " + sequence.getId() + ": " + subsequence);
1240
1241                List<ISequenceInstance> sequenceInstances = replaceSubsequenceOccurrences
1242                    (subsequence, appData.getSessions(), sequence);
1243               
1244                harmonizeSequenceInstancesModel(sequence, sequenceInstances, subsequence.size());
1245                appData.detectedAndReplacedTasks
1246                    (appData.detectedAndReplacedTasks() || (sequenceInstances.size() > 0));
1247
1248                if (sequenceInstances.size() < appData.getLastFoundSubsequences().getOccurrenceCount()) {
1249                    Console.traceln(Level.FINE, sequence.getId() + ": replaced task only " +
1250                                    sequenceInstances.size() + " times instead of expected " +
1251                                    appData.getLastFoundSubsequences().getOccurrenceCount());
1252                }
1253            }
1254        }
1255    }
1256
1257    /**
1258     *
1259     */
1260    private void harmonizeSequenceInstancesModel(ISequence               sequence,
1261                                                 List<ISequenceInstance> sequenceInstances,
1262                                                 int                     sequenceLength)
1263    {
1264        TaskComparator comparator = preparationTaskHandlingStrategy.getTaskComparator();
1265       
1266        // ensure for each subtask that lexically different variants are preserved
1267        for (int subTaskIndex = 0; subTaskIndex < sequenceLength; subTaskIndex++) {
1268            List<ITask> subTaskVariants = new LinkedList<ITask>();
1269           
1270            for (ISequenceInstance sequenceInstance : sequenceInstances) {
1271                ITask candidate = sequenceInstance.get(subTaskIndex).getTask();
1272               
1273                boolean found = false;
1274               
1275                for (int i = 0; i < subTaskVariants.size(); i++) {
1276                    if (comparator.areLexicallyEqual(subTaskVariants.get(i), candidate)) {
1277                        taskBuilder.setTask
1278                            (sequenceInstance.get(subTaskIndex), subTaskVariants.get(i));
1279                       
1280                        found = true;
1281                        break;
1282                    }
1283                }
1284               
1285                if (!found) {
1286                    subTaskVariants.add(candidate);
1287                }
1288            }
1289           
1290            // if there are more than one lexically different variant of the sub task at
1291            // the considered position, adapt the sequence model at that position to have
1292            // a selection of the different variants. In this case also adapt the
1293            // generated sequence instances to correctly contain selection instances. If
1294            // there is only one variant of sub tasks at the given position, simply set
1295            // this variant as the sub task of the selection. In this case, the instances
1296            // can be preserved as is
1297            if (subTaskVariants.size() > 1) {
1298                ISelection selection = taskFactory.createNewSelection();
1299               
1300                for (ITask variant : subTaskVariants) {
1301                    taskBuilder.addChild(selection, variant);
1302                }
1303               
1304                taskBuilder.addChild(sequence, selection);
1305               
1306                for (ISequenceInstance instance : sequenceInstances) {
1307                    ISelectionInstance selectionInstance =
1308                        taskFactory.createNewTaskInstance(selection);
1309                    taskBuilder.setChild(selectionInstance, instance.get(subTaskIndex));
1310                    taskBuilder.setTaskInstance(instance, subTaskIndex, selectionInstance);
1311                }
1312            }
1313            else if (subTaskVariants.size() == 1) {
1314                taskBuilder.addChild(sequence, subTaskVariants.get(0));
1315            }
1316        }
1317    }
1318
1319    /**
1320     * @param tree
1321     */
1322    private List<ISequenceInstance> replaceSubsequenceOccurrences(Subsequence         subsequence,
1323                                                                  List<IUserSession>  sessions,
1324                                                                  ISequence           temporalTaskModel)
1325    {
1326        List<ISequenceInstance> sequenceInstances = new LinkedList<ISequenceInstance>();
1327       
1328        for (IUserSession session : sessions) {
1329            int index = -1;
1330           
1331            do {
1332                index = getSubListIndex(session, subsequence, ++index);
1333
1334                if (index > -1) {
1335                    // subsequence is found --> perform replacement
1336                    sequenceInstances.add
1337                        (RuleUtils.createNewSubSequenceInRange
1338                             (session, index, index + subsequence.size() - 1, temporalTaskModel,
1339                              taskFactory, taskBuilder));
1340                }
1341            }
1342            while (index > -1);
1343        }
1344       
1345        return sequenceInstances;
1346    }
1347
1348    /**
1349     * @param trie
1350     * @param object
1351     * @return
1352     */
1353    private int getSubListIndex(ITaskInstanceList   list,
1354                                Subsequence         subsequence,
1355                                int                 startIndex)
1356    {
1357        boolean matchFound;
1358        int result = -1;
1359       
1360        for (int i = startIndex; i <= list.size() - subsequence.size(); i++) {
1361            matchFound = true;
1362           
1363            for (int j = 0; j < subsequence.size(); j++) {
1364                // we prepared the task instances to refer to unique tasks, if they are treated
1365                // as equal. Therefore, we just compare the identity of the tasks of the task
1366                // instances
1367                if (list.get(i + j).getTask() != subsequence.get(j)) {
1368                    matchFound = false;
1369                    break;
1370                }
1371            }
1372           
1373            if (matchFound) {
1374                result = i;
1375                break;
1376            }
1377        }
1378       
1379        return result;
1380    }
1381
1382    /**
1383     * @param trie
1384     * @param object
1385     * @return
1386     */
1387    private int getSubListIndex(Subsequence longerSubsequence,
1388                                Subsequence shorterSubsequence,
1389                                int         startIndex)
1390    {
1391        boolean matchFound;
1392        int result = -1;
1393       
1394        for (int i = startIndex; i <= longerSubsequence.size() - shorterSubsequence.size(); i++) {
1395            matchFound = true;
1396           
1397            for (int j = 0; j < shorterSubsequence.size(); j++) {
1398                // we prepared the task instances to refer to unique tasks, if they are treated
1399                // as equal. Therefore, we just compare the identity of the tasks of the task
1400                // instances
1401                if (longerSubsequence.get(i + j) != shorterSubsequence.get(j)) {
1402                    matchFound = false;
1403                    break;
1404                }
1405            }
1406           
1407            if (matchFound) {
1408                result = i;
1409                break;
1410            }
1411        }
1412       
1413        return result;
1414    }
1415
1416//  /**
1417//   *
1418//   */
1419//  private void dumpSorted(List<InterleavingSubsequence> interleavings) {
1420//      dumpSorted(interleavings, Level.FINEST);
1421//  }
1422
1423    /**
1424     *
1425     */
1426    private void dumpSorted(List<InterleavingSubsequence> interleavings, Level level) {
1427        List<String> tmpList = new LinkedList<String>();
1428
1429        for (InterleavingSubsequence interleaving : interleavings) {
1430            String taskStr = toPlainStr(interleaving);
1431            int index;
1432            for (index = 0; index < tmpList.size(); index++) {
1433                if (taskStr.compareTo(tmpList.get(index)) > 0) {
1434                    break;
1435                }
1436            }
1437
1438            tmpList.add(index, taskStr);
1439        }
1440
1441        for (String task : tmpList) {
1442            Console.traceln(level, task);
1443        }
1444    }
1445
1446//    /**
1447//     *
1448//     */
1449//    private void dumpSortedCollectionOfSubsequences(String                  prefix,
1450//                                                    Collection<Subsequence> subsequences)
1451//    {
1452//        List<String> tmpList = new LinkedList<String>();
1453//
1454//        for (Subsequence subsequence : subsequences) {
1455//            String taskStr = toPlainStr(subsequence);
1456//            int index;
1457//            for (index = 0; index < tmpList.size(); index++) {
1458//                if (taskStr.compareTo(tmpList.get(index)) > 0) {
1459//                    break;
1460//                }
1461//            }
1462//
1463//            tmpList.add(index, taskStr);
1464//        }
1465//
1466//        for (String task : tmpList) {
1467//            Console.traceln(Level.FINEST, prefix + " " + task);
1468//        }
1469//    }
1470
1471    /**
1472     *
1473     */
1474    private String toPlainStr(InterleavingSubsequence interleaving) {
1475        StringBuffer result = new StringBuffer();
1476        result.append("interleavings of ");
1477        result.append(toPlainStr(interleaving.getSubsequence()));
1478        result.append("\n  predecessor collisions:\n");
1479
1480        for (Collision collision : interleaving.getPredecessorCollisions()) {
1481            result.append("    ");
1482            result.append(toPlainStr(collision.getCollidingWith()));
1483            result.append(" (");
1484            result.append(collision.getLocation());
1485            result.append(")\n");
1486        }
1487
1488        result.append("  successor collisions:\n");
1489
1490        for (Collision collision : interleaving.getSuccessorCollisions()) {
1491            result.append("    ");
1492            result.append(toPlainStr(collision.getCollidingWith()));
1493            result.append(" (");
1494            result.append(collision.getLocation());
1495            result.append(")\n");
1496        }
1497
1498        return result.toString();
1499    }
1500
1501    /**
1502     *
1503     */
1504    private String toPlainStr(Subsequence subsequence) {
1505        StringBuffer result = new StringBuffer();
1506        result.append(subsequence.size());
1507        result.append(": ");
1508        for (ITask task : subsequence) {
1509            DebuggingHelper.toPlainStr(task, result);
1510            result.append(" --> ");
1511        }
1512
1513        return result.toString();
1514    }
1515   
1516   
1517    /**
1518     * @author Patrick Harms
1519     */
1520    private class MaxCountAndLongestSubsequencesFinder implements TrieProcessor<ITask> {
1521       
1522        /**
1523         *
1524         */
1525        private int currentCount;
1526       
1527        /**
1528         *
1529         */
1530        private LinkedList<Subsequence> foundSubsequences = new LinkedList<Subsequence>();
1531
1532        /**
1533         *
1534         */
1535        public MaxCountAndLongestSubsequencesFinder() {
1536            super();
1537            this.currentCount = 0;
1538        }
1539
1540        /* (non-Javadoc)
1541         * @see de.ugoe.cs.autoquest.usageprofiles.TrieProcessor#process(java.util.List, int)
1542         */
1543        @Override
1544        public TrieProcessor.Result process(List<ITask> foundTask, int count) {
1545            if (foundTask.size() < 2) {
1546                // ignore single tasks
1547                return TrieProcessor.Result.CONTINUE;
1548            }
1549           
1550            if (count < 2) {
1551                // ignore singular occurrences
1552                return TrieProcessor.Result.SKIP_NODE;
1553            }
1554
1555            if (this.currentCount > count) {
1556                // ignore this children of this task, as they may have only smaller counts than
1557                // the already found tasks
1558                return TrieProcessor.Result.SKIP_NODE;
1559            }
1560           
1561            if (this.currentCount < count) {
1562                // the provided task occurs more often that all tasks found so far.
1563                // clear all found tasks and use the new count as the one searched for
1564                foundSubsequences.clear();
1565                this.currentCount = count;
1566            }
1567           
1568            if (this.currentCount == count) {
1569                // the task is of interest. Sort it into the other found tasks so that
1570                // the longest come first
1571                boolean added = false;
1572                for (int i = 0; i < foundSubsequences.size(); i++) {
1573                    if (foundSubsequences.get(i).size() < foundTask.size()) {
1574                        foundSubsequences.add(i, new Subsequence(currentCount, foundTask));
1575                        added = true;
1576                        break;
1577                    }
1578                }
1579               
1580                if (!added) {
1581                    foundSubsequences.add(new Subsequence(currentCount, foundTask));
1582                }
1583            }
1584           
1585            return TrieProcessor.Result.CONTINUE;
1586        }
1587
1588        /**
1589         *  @return
1590         */
1591        private Subsequences getFoundSubsequences() {
1592            removePermutationsOfShorterTasks();
1593            return new Subsequences(currentCount, foundSubsequences);
1594        }
1595
1596        /**
1597         *
1598         */
1599        private void removePermutationsOfShorterTasks() {
1600            // now iterate the sorted list and for each task remove all other tasks that are shorter
1601            // (i.e. come later in the sorted list) and that represent a subpart of the task
1602           
1603            boolean removeI;
1604           
1605            for (int i = 0; i < foundSubsequences.size();) {
1606                removeI = false;
1607                boolean removeJ;
1608               
1609                for (int j = i + 1; j < foundSubsequences.size();) {
1610                    removeJ = false;
1611                   
1612                    if (foundSubsequences.get(j).size() < foundSubsequences.get(i).size()) {
1613                        // found a task that is a potential subtask. Check for this and remove the
1614                        // subtask if needed
1615                        Subsequence longTask = foundSubsequences.get(i);
1616                        Subsequence shortTask = foundSubsequences.get(j);
1617                       
1618                        int index = getSubListIndex(longTask, shortTask, 0);
1619                        if (index > -1) {
1620                            if (index == 0) {
1621                                // check if the short task is included in the long task partially
1622                                // a second time. If so, prefer the short task
1623                                boolean secondInclude = true;
1624                                for (int pos = shortTask.size(); pos < longTask.size(); pos++) {
1625                                    // we prepared the task instances to refer to unique tasks, if
1626                                    // they are treated as equal. Therefore, we just compare the
1627                                    // identity of the tasks of the task instances
1628                                    if (longTask.get(pos) != shortTask.get(pos % shortTask.size()))
1629                                    {
1630                                        secondInclude = false;
1631                                        break;
1632                                    }
1633                                }
1634                               
1635                                if (secondInclude) {
1636                                    // delete the long task
1637                                    // Console.traceln(Level.FINEST, "1: short task is contained several times in longer one --> removing it");
1638                                    // Console.traceln(Level.FINEST, "short: " + toPlainStr(shortTask));
1639                                    // Console.traceln(Level.FINEST, "long: " + toPlainStr(longTask));
1640                                    removeI = true;
1641                                }
1642                                else {
1643                                    // Console.traceln(Level.FINEST, "2: short task is a part of a longer one --> removing it");
1644                                    // Console.traceln(Level.FINEST, "short: " + toPlainStr(shortTask));
1645                                    // Console.traceln(Level.FINEST, "long: " + toPlainStr(longTask));
1646                                    removeJ = true;
1647                                }
1648                            }
1649                            else {
1650                                // Console.traceln(Level.FINEST, "3: short task is a part of a longer one --> removing it");
1651                                // Console.traceln(Level.FINEST, "short: " + toPlainStr(shortTask));
1652                                // Console.traceln(Level.FINEST, "long: " + toPlainStr(longTask));
1653                                removeJ = true;
1654                            }
1655                        }
1656                    }
1657                   
1658                    if (removeJ) {
1659                        foundSubsequences.remove(j);
1660                    }
1661                    else {
1662                        j++;
1663                    }
1664                }
1665               
1666                if (removeI) {
1667                    foundSubsequences.remove(i);
1668                }
1669                else {
1670                    i++;
1671                }
1672            }
1673        }
1674
1675    }
1676
1677//    /**
1678//     * @author Patrick Harms
1679//     */
1680//    private class TrieStatisticsDumper implements TrieProcessor<ITaskInstance> {
1681//       
1682//        /**
1683//         *
1684//         */
1685//        private Map<Integer, Integer> counters = new HashMap<Integer, Integer>();
1686//       
1687//        /* (non-Javadoc)
1688//         * @see de.ugoe.cs.autoquest.usageprofiles.TrieProcessor#process(java.util.List, int)
1689//         */
1690//        @Override
1691//        public TrieProcessor.Result process(List<ITaskInstance> subsequence, int count) {
1692//            if (subsequence.size() == 1) {
1693//                Integer value = counters.get(count);
1694//               
1695//                if (value == null) {
1696//                    value = 0;
1697//                }
1698//               
1699//                counters.put(count, value + 1);
1700//               
1701//                return TrieProcessor.Result.CONTINUE;
1702//            }
1703//            else {
1704//                // ignore singular occurrences
1705//                return TrieProcessor.Result.SKIP_NODE;
1706//            }
1707//        }
1708//
1709//        /**
1710//         *  @return
1711//         */
1712//        public void dumpCounters() {
1713//            int dumpedCounters = 0;
1714//           
1715//            int count = 1;
1716//            while (dumpedCounters < counters.size()) {
1717//                Integer value = counters.get(count++);
1718//                if (value != null) {
1719//                    System.out.println(value + " symbols occurred " + count + " times");
1720//                    dumpedCounters++;
1721//                }
1722//            }
1723//        }
1724//
1725//    }
1726   
1727    /**
1728     *
1729     */
1730    private static class RuleApplicationData {
1731       
1732        /**
1733         *
1734         */
1735        private List<IUserSession> sessions;
1736       
1737        /**
1738         *
1739         */
1740        private TaskInstanceTrie lastTrie;
1741       
1742        /**
1743         * default and minimum trained subsequence length is 3
1744         */
1745        private int trainedSubsequenceLength = 3;
1746       
1747        /**
1748         *
1749         */
1750        private Subsequences lastFoundSubsequences = new Subsequences(Integer.MAX_VALUE, null);
1751       
1752        /**
1753         *
1754         */
1755        private boolean detectedAndReplacedTasks;
1756       
1757        /**
1758         *
1759         */
1760        private RuleApplicationResult result = new RuleApplicationResult();
1761       
1762        /**
1763         *
1764         */
1765        private StopWatch stopWatch = new StopWatch();
1766       
1767        /**
1768         *
1769         */
1770        private RuleApplicationData(List<IUserSession> sessions) {
1771            this.sessions = sessions;
1772        }
1773
1774        /**
1775         * @return the tree
1776         */
1777        private List<IUserSession> getSessions() {
1778            return sessions;
1779        }
1780
1781        /**
1782         * @param lastTrie the lastTrie to set
1783         */
1784        private void setLastTrie(TaskInstanceTrie lastTrie) {
1785            this.lastTrie = lastTrie;
1786        }
1787
1788        /**
1789         * @return the lastTrie
1790         */
1791        private TaskInstanceTrie getLastTrie() {
1792            return lastTrie;
1793        }
1794
1795        /**
1796         * @param trainedSubsequenceLength the trainedSubsequenceLength to set
1797         */
1798        private void setTrainedSubsequenceLength(int trainedSubsequenceLength) {
1799            this.trainedSubsequenceLength = trainedSubsequenceLength;
1800        }
1801
1802        /**
1803         * @return the trainedSubsequenceLength
1804         */
1805        private int getTrainedSubsequenceLength() {
1806            return trainedSubsequenceLength;
1807        }
1808
1809        /**
1810         * @param lastFoundSequences the lastFoundSequences to set
1811         */
1812        private void setLastFoundSubsequences(Subsequences lastFoundSequences) {
1813            this.lastFoundSubsequences = lastFoundSequences;
1814        }
1815
1816        /**
1817         * @return the lastFoundSequences
1818         */
1819        private Subsequences getLastFoundSubsequences() {
1820            return lastFoundSubsequences;
1821        }
1822
1823        /**
1824         *
1825         */
1826        private void detectedAndReplacedTasks(boolean detectedAndReplacedTasks) {
1827            this.detectedAndReplacedTasks = detectedAndReplacedTasks;
1828        }
1829
1830        /**
1831         *
1832         */
1833        private boolean detectedAndReplacedTasks() {
1834            return detectedAndReplacedTasks;
1835        }
1836       
1837        /**
1838         * @return the result
1839         */
1840        private RuleApplicationResult getResult() {
1841            return result;
1842        }
1843
1844        /**
1845         * @return the stopWatch
1846         */
1847        private StopWatch getStopWatch() {
1848            return stopWatch;
1849        }
1850
1851    }
1852   
1853    /**
1854     * @author Patrick Harms
1855     */
1856    private static class Subsequence implements Iterable<ITask> {
1857       
1858        /**
1859         *
1860         */
1861        private int occurrenceCount;
1862
1863        /**
1864         *
1865         */
1866        private List<ITask> subsequence;
1867       
1868        /**
1869         * @param occurrenceCount
1870         * @param subsequences
1871         */
1872        private Subsequence(int occurrenceCount, List<ITask> subsequence) {
1873            super();
1874            this.occurrenceCount = occurrenceCount;
1875            this.subsequence = new ArrayList<ITask>(subsequence);
1876        }
1877
1878        /**
1879         * @return
1880         */
1881        private int size() {
1882            return this.subsequence.size();
1883        }
1884
1885        /**
1886         * @return
1887         */
1888        private ITask get(int index) {
1889            return this.subsequence.get(index);
1890        }
1891
1892        /* (non-Javadoc)
1893         * @see java.lang.Iterable#iterator()
1894         */
1895        @Override
1896        public Iterator<ITask> iterator() {
1897            return this.subsequence.iterator();
1898        }
1899
1900        /* (non-Javadoc)
1901         * @see java.lang.Object#toString()
1902         */
1903        @Override
1904        public String toString() {
1905            return subsequence.toString() + " (" + occurrenceCount + ")";
1906        }
1907    }
1908
1909    /**
1910     * @author Patrick Harms
1911     */
1912    private static class Subsequences implements Iterable<Subsequence> {
1913       
1914        /**
1915         *
1916         */
1917        private int occurrenceCount;
1918       
1919        /**
1920         *
1921         */
1922        private LinkedList<Subsequence> subsequences;
1923
1924        /**
1925         * @param occurrenceCount
1926         * @param sequences
1927         */
1928        private Subsequences(int occurrenceCount, LinkedList<Subsequence> subsequences) {
1929            super();
1930            this.occurrenceCount = occurrenceCount;
1931            this.subsequences = subsequences;
1932        }
1933
1934        /**
1935         *
1936         */
1937        private void remove(Subsequence subsequence) {
1938            ListIterator<Subsequence> it = subsequences.listIterator();
1939           
1940            while (it.hasNext()) {
1941                // reference comparison is sufficient
1942                if (it.next() == subsequence) {
1943                    it.remove();
1944                }
1945            }
1946        }
1947
1948        /**
1949         * @return
1950         */
1951        private int getOccurrenceCount() {
1952            return occurrenceCount;
1953        }
1954
1955        /**
1956         * @return
1957         */
1958        private int size() {
1959            return this.subsequences.size();
1960        }
1961
1962        /* (non-Javadoc)
1963         * @see java.lang.Iterable#iterator()
1964         */
1965        @Override
1966        public Iterator<Subsequence> iterator() {
1967            return this.subsequences.iterator();
1968        }
1969
1970        /* (non-Javadoc)
1971         * @see java.lang.Object#toString()
1972         */
1973        @Override
1974        public String toString() {
1975            StringBuffer result = new StringBuffer();
1976            result.append(" subsequences occuring ");
1977            result.append(this.occurrenceCount);
1978            result.append(" times:\n");
1979           
1980            for (Subsequence subsequence : subsequences) {
1981                result.append(subsequence);
1982                result.append("\n");
1983            }
1984           
1985            return result.toString();
1986        }
1987    }
1988   
1989    /**
1990     * @author Patrick Harms
1991     */
1992    private static class InterleavingSubsequence {
1993       
1994        /** */
1995        private Subsequence subsequence;
1996       
1997        /** */
1998        private List<Collision> successorCollisions;
1999       
2000        /** */
2001        private List<Collision> predecessorCollisions;
2002
2003        /**
2004         *
2005         */
2006        private InterleavingSubsequence(Subsequence     subsequence,
2007                                        List<Collision> predecessorCollisions,
2008                                        List<Collision> successorCollisions)
2009        {
2010            super();
2011            this.subsequence = subsequence;
2012            this.predecessorCollisions = predecessorCollisions;
2013            this.successorCollisions = successorCollisions;
2014        }
2015
2016        /**
2017         *
2018         */
2019        private int getCollisionCounter() {
2020            return getSuccessorCollisionCounter() + getPredecessorCollisionCounter();
2021        }
2022
2023        /**
2024         *
2025         */
2026        private int getSuccessorCollisionCounter() {
2027            return successorCollisions.size();
2028        }
2029
2030        /**
2031         *
2032         */
2033        private List<Collision> getSuccessorCollisions() {
2034            return successorCollisions;
2035        }
2036
2037        /**
2038         *
2039         */
2040        private int getPredecessorCollisionCounter() {
2041            return predecessorCollisions.size();
2042        }
2043
2044        /**
2045         *
2046         */
2047        private List<Collision> getPredecessorCollisions() {
2048            return predecessorCollisions;
2049        }
2050
2051        /**
2052         *
2053         */
2054        private Subsequence getSubsequence() {
2055            return subsequence;
2056        }
2057       
2058        /* (non-Javadoc)
2059         * @see java.lang.Object#toString()
2060         */
2061        @Override
2062        public String toString() {
2063            return "interleaving subsequence " + subsequence.toString() + " (" +
2064                successorCollisions.size() + " successor, " + predecessorCollisions.size() +
2065                " predecessor)";
2066        }
2067    }
2068       
2069    /**
2070     * @author Patrick Harms
2071     */
2072    private static class SubsequenceLocation {
2073       
2074        /** */
2075        private IUserSession session;
2076       
2077        /** */
2078        private int index;
2079       
2080        /**
2081         *
2082         */
2083        private SubsequenceLocation(IUserSession session, int index) {
2084            this.session = session;
2085            this.index = index;
2086        }
2087
2088        /**
2089         * @return the session
2090         */
2091        private IUserSession getSession() {
2092            return session;
2093        }
2094
2095        /**
2096         * @return the index
2097         */
2098        private int getIndex() {
2099            return index;
2100        }
2101       
2102        /* (non-Javadoc)
2103         * @see java.lang.Object#toString()
2104         */
2105        @Override
2106        public String toString() {
2107            return "location (" + session + ", " + index + ")";
2108        }
2109    }
2110   
2111    /**
2112     * @author Patrick Harms
2113     */
2114    private static class Collision {
2115       
2116        /** */
2117        private SubsequenceLocation location;
2118       
2119        /** */
2120        private Subsequence subsequence;
2121       
2122        /** */
2123        private Subsequence collidingWith;
2124       
2125        /**
2126         *
2127         */
2128        private Collision(SubsequenceLocation location,
2129                          Subsequence         subsequence,
2130                          Subsequence         collidingWith)
2131        {
2132            this.location = location;
2133            this.subsequence = subsequence;
2134            this.collidingWith = collidingWith;
2135        }
2136
2137        /**
2138         * @return the collidingWith
2139         */
2140        private Subsequence getCollidingWith() {
2141            return collidingWith;
2142        }
2143
2144        /**
2145         * @return the location
2146         */
2147        private SubsequenceLocation getLocation() {
2148            return location;
2149        }
2150
2151        /**
2152         * @return the subsequence
2153         */
2154        private Subsequence getSubsequence() {
2155            return subsequence;
2156        }
2157
2158        /* (non-Javadoc)
2159         * @see java.lang.Object#toString()
2160         */
2161        @Override
2162        public String toString() {
2163            return "collision (" + location + " ," + subsequence + ", " + collidingWith + ")";
2164        }
2165    }
2166   
2167    // methods for internal testing
2168//    private void checkMatchingOfSessions(List<List<Event>>  flattenedSessions,
2169//                                         List<IUserSession> sessions,
2170//                                         String             when)
2171//    {
2172//        List<List<Event>> currentFlattenedSessions = flattenSessions(sessions);
2173//        if (flattenedSessions.size() != currentFlattenedSessions.size()) {
2174//            System.out.println("################## number of sessions changed after " + when);
2175//        }
2176//        else {
2177//            for (int i = 0; i < flattenedSessions.size(); i++) {
2178//                List<Event> expected = flattenedSessions.get(i);
2179//                List<Event> current = currentFlattenedSessions.get(i);
2180//           
2181//                if (expected.size() != current.size()) {
2182//                    System.out.println
2183//                        ("################## length of session " + i + " changed after " + when);
2184//                }
2185//                else {
2186//                    for (int j = 0; j < expected.size(); j++) {
2187//                        if (!expected.get(j).equals(current.get(j))) {
2188//                            System.out.println("################## event " + j + " of session " +
2189//                                               i + " changed after " + when);
2190//                        }
2191//                    }
2192//                }
2193//            }     
2194//        }
2195//    }
2196//
2197//    private List<List<Event>> flattenSessions(List<IUserSession> sessions) {
2198//        List<List<Event>> flattenedSessions = new ArrayList<List<Event>>();
2199//        for (IUserSession session : sessions) {
2200//            List<Event> flattenedUserSession = new ArrayList<Event>();
2201//            flatten(session, flattenedUserSession);
2202//            flattenedSessions.add(flattenedUserSession);
2203//        }
2204//
2205//        return flattenedSessions;
2206//    }
2207//
2208//    private void flatten(IUserSession iUserSession, List<Event> flattenedUserSession) {
2209//        for (ITaskInstance instance : iUserSession) {
2210//            flatten(instance, flattenedUserSession);
2211//        }
2212//    }
2213//
2214//    private void flatten(ITaskInstance instance, List<Event> flattenedUserSession) {
2215//        if (instance instanceof ITaskInstanceList) {
2216//            for (ITaskInstance child : (ITaskInstanceList) instance) {
2217//                flatten(child, flattenedUserSession);
2218//            }
2219//        }
2220//        else if (instance instanceof ISelectionInstance) {
2221//            flatten(((ISelectionInstance) instance).getChild(), flattenedUserSession);
2222//        }
2223//        else if (instance instanceof IOptionalInstance) {
2224//            flatten(((IOptionalInstance) instance).getChild(), flattenedUserSession);
2225//        }
2226//        else if (instance instanceof IEventTaskInstance) {
2227//            flattenedUserSession.add(((IEventTaskInstance) instance).getEvent());
2228//        }
2229//    }
2230
2231}
Note: See TracBrowser for help on using the repository browser.