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

//   Copyright 2012 Georg-August-Universität Göttingen, Germany
//
//   Licensed under the Apache License, Version 2.0 (the "License");
//   you may not use this file except in compliance with the License.
//   You may obtain a copy of the License at
//
//       http://www.apache.org/licenses/LICENSE-2.0
//
//   Unless required by applicable law or agreed to in writing, software
//   distributed under the License is distributed on an "AS IS" BASIS,
//   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
//   See the License for the specific language governing permissions and
//   limitations under the License.

package de.ugoe.cs.autoquest.tasktrees.temporalrelation;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.IdentityHashMap;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;
import java.util.Map;
import java.util.Set;
import java.util.logging.Level;

import de.ugoe.cs.autoquest.tasktrees.taskequality.TaskEquality;
import de.ugoe.cs.autoquest.tasktrees.temporalrelation.utils.DebuggingHelper;
import de.ugoe.cs.autoquest.tasktrees.treeifc.IIteration;
import de.ugoe.cs.autoquest.tasktrees.treeifc.IIterationInstance;
import de.ugoe.cs.autoquest.tasktrees.treeifc.IOptional;
import de.ugoe.cs.autoquest.tasktrees.treeifc.IOptionalInstance;
import de.ugoe.cs.autoquest.tasktrees.treeifc.ISelection;
import de.ugoe.cs.autoquest.tasktrees.treeifc.ISelectionInstance;
import de.ugoe.cs.autoquest.tasktrees.treeifc.ISequence;
import de.ugoe.cs.autoquest.tasktrees.treeifc.ISequenceInstance;
import de.ugoe.cs.autoquest.tasktrees.treeifc.ITask;
import de.ugoe.cs.autoquest.tasktrees.treeifc.ITaskBuilder;
import de.ugoe.cs.autoquest.tasktrees.treeifc.ITaskFactory;
import de.ugoe.cs.autoquest.tasktrees.treeifc.ITaskInstance;
import de.ugoe.cs.autoquest.tasktrees.treeifc.ITaskInstanceList;
import de.ugoe.cs.autoquest.tasktrees.treeifc.IUserSession;
import de.ugoe.cs.autoquest.usageprofiles.SymbolMap;
import de.ugoe.cs.autoquest.usageprofiles.Trie;
import de.ugoe.cs.autoquest.usageprofiles.TrieProcessor;
import de.ugoe.cs.util.StopWatch;
import de.ugoe.cs.util.console.Console;

/**
 * <p>
 * This class implements the major rule for creating task trees based on a set of recorded
 * user sessions. For this, it first harmonizes all tasks. This eases later comparison. Then it
 * searches the sessions for iterations and replaces them accordingly. Then it searches for sub
 * sequences being the longest and occurring most often. For each found sub sequence, it replaces
 * the occurrences by creating appropriate {@link ISequence}s. Afterwards, again searches for
 * iterations and then again for sub sequences until no more replacements are done.
 * </p>
 * <p>
 * For determining the longest sequence occurring most often, the implementation uses a 
 * {@link Trie}. The depth of the tree is initially 3. If the algorithm has a longest sequence
 * occurring most often whose length is equal to the depth of the trie, it recalculates the trie
 * with an increased depth. 
 * </p>
 * 
 * @author Patrick Harms
 */
class SequenceForTaskDetectionRule implements ISessionScopeRule {
    
    /**
     * <p>
     * the task factory to be used for creating substructures for the temporal
     * relationships identified during rul application
     * </p>
     */
    private ITaskFactory taskFactory;
    /**
     * <p>
     * the task builder to be used for creating substructures for the temporal relationships
     * identified during rule application
     * </p>
     */
    private ITaskBuilder taskBuilder;

    /**
     * <p>
     * the task handling strategy to be used for comparing tasks for preparation, i.e., before
     * the tasks are harmonized
     * </p>
     */
    private TaskHandlingStrategy preparationTaskHandlingStrategy;
    
    /**
     * <p>
     * the task handling strategy to be used for comparing tasks during iteration detection an trie
     * generation, i.e., after the tasks are harmonized 
     * </p>
     */
    private TaskHandlingStrategy identityTaskHandlingStrategy;;
    
    /**
     * <p>
     * instantiates the rule and initializes it with a task equality to be considered when
     * comparing tasks as well as a task factory and builder to be used for creating task
     * structures.
     * </p>
     * 
     * @param minimalTaskEquality the task equality to be considered when comparing tasks
     * @param taskFactory         the task factory to be used for creating substructures
     * @param taskBuilder         the task builder to be used for creating substructures
     */
    SequenceForTaskDetectionRule(TaskEquality minimalTaskEquality,
                                 ITaskFactory taskFactory,
                                 ITaskBuilder taskBuilder)
    {
        this.taskFactory = taskFactory;
        this.taskBuilder = taskBuilder;
        
        this.preparationTaskHandlingStrategy = new TaskHandlingStrategy(minimalTaskEquality);
        this.identityTaskHandlingStrategy = new TaskHandlingStrategy(TaskEquality.IDENTICAL);
    }

    /* (non-Javadoc)
     * @see java.lang.Object#toString()
     */
    @Override
    public String toString() {
        return "SequenceForTaskDetectionRule";
    }

    /* (non-Javadoc)
     * @see de.ugoe.cs.autoquest.tasktrees.temporalrelation.ISessionScopeRule#apply(java.util.List)
     */
    @Override
    public RuleApplicationResult apply(List<IUserSession> sessions) {
        RuleApplicationData appData = new RuleApplicationData(sessions);
        
        // this is the real rule application. Loop while something is replaced.
        harmonizeEventTaskInstancesModel(appData);
        do {
            System.out.println();
            
            appData.getStopWatch().start("whole loop");
            detectAndReplaceIterations(appData);

            appData.getStopWatch().start("task replacement");
            detectAndReplaceTasks(appData);
            appData.getStopWatch().stop("task replacement");
            appData.getStopWatch().stop("whole loop");
            
            //((TaskTreeNodeComparator) taskComparator).getStopWatch().dumpStatistics(System.out);
            //((TaskTreeNodeComparator) taskComparator).getStopWatch().reset();
            
            appData.getStopWatch().dumpStatistics(System.out);
            appData.getStopWatch().reset();
            
        }
        while (appData.detectedAndReplacedTasks());
        
        Console.println
            ("created " + appData.getResult().getNewlyCreatedTasks().size() +
             " new tasks and " + appData.getResult().getNewlyCreatedTaskInstances().size() +
             " appropriate instances\n");
        
        if ((appData.getResult().getNewlyCreatedTasks().size() > 0) ||
            (appData.getResult().getNewlyCreatedTaskInstances().size() > 0))
        {
            appData.getResult().setRuleApplicationStatus(RuleApplicationStatus.FINISHED);
        }
        
        return appData.getResult();
    }

    /**
     * <p>
     * harmonizes the event task instances by unifying tasks. This is done, as initially the
     * event tasks being equal with respect to the considered task equality are distinct objects.
     * The comparison of these distinct objects is more time consuming than comparing the object
     * references.
     * </p>
     *
     * @param appData the rule application data combining all data used for applying this rule
     */
    private void harmonizeEventTaskInstancesModel(RuleApplicationData appData) {
        Console.traceln(Level.INFO, "harmonizing task model of event task instances");
        appData.getStopWatch().start("harmonizing event tasks");

        SymbolMap<ITask, ITask> uniqueTasks = preparationTaskHandlingStrategy.createSymbolMap();
        TaskComparator comparator = preparationTaskHandlingStrategy.getTaskComparator();
        
        int unifiedTasks = 0;
        ITask task;
        List<IUserSession> sessions = appData.getSessions();
        int sessionNo = 0;
        for (IUserSession session : sessions) {
            Console.traceln(Level.FINE, "handling " + (++sessionNo) + ". " + session);
            for (ITaskInstance taskInstance : session) {
                task = uniqueTasks.getValue(taskInstance.getTask());
                
                if (task == null) {
                    uniqueTasks.addSymbol(taskInstance.getTask(), taskInstance.getTask());
                }
                else {
                    taskBuilder.setTask(taskInstance, task);
                    unifiedTasks++;
                }
            }
            
            comparator.clearBuffers();
        }
        
        appData.getStopWatch().stop("harmonizing event tasks");
        Console.traceln(Level.INFO, "harmonized " + unifiedTasks + " task occurrences (still " +
                        uniqueTasks.size() + " different tasks)");

        appData.getStopWatch().dumpStatistics(System.out);
        appData.getStopWatch().reset();
    }

    /**
     * <p>
     * searches for direct iterations of single tasks in all sequences and replaces them with
     * {@link IIteration}s, respectively appropriate instances. Also all single occurrences of
     * a task that is iterated somewhen are replaced with iterations to have again an efficient
     * way for task comparisons. 
     * </p>
     * 
     * @param appData the rule application data combining all data used for applying this rule
     */
    private void detectAndReplaceIterations(RuleApplicationData appData) {
        Console.traceln(Level.FINE, "detecting iterations");
        appData.getStopWatch().start("detecting iterations");
        
        List<IUserSession> sessions = appData.getSessions();
        
        Set<ITask> iteratedTasks = searchIteratedTasks(sessions);
        
        if (iteratedTasks.size() > 0) {
            replaceIterationsOf(iteratedTasks, sessions, appData);
        }
        
        appData.getStopWatch().stop("detecting iterations");
        Console.traceln(Level.INFO, "replaced " + iteratedTasks.size() + " iterated tasks");
    }

    /**
     * <p>
     * searches the provided sessions for task iterations. If a task is iterated, it is added
     * to the returned set.
     * </p>
     * 
     * @param the session to search for iterations in
     * 
     * @return a set of tasks being iterated somewhere
     */
    private Set<ITask> searchIteratedTasks(List<IUserSession> sessions) {
        Set<ITask> iteratedTasks = new HashSet<ITask>();
        for (IUserSession session : sessions) {
            for (int i = 0; i < (session.size() - 1); i++) {
                // we prepared the task instances to refer to unique tasks, if they are treated
                // as equal. Therefore, we just compare the identity of the tasks of the task
                // instances
                if (session.get(i).getTask() == session.get(i + 1).getTask()) {
                    iteratedTasks.add(session.get(i).getTask());
                }
            }
        }
        
        return iteratedTasks;
    }

    /**
     * <p>
     * replaces all occurrences of all tasks provided in the set with iterations
     * </p>
     *
     * @param iteratedTasks the tasks to be replaced with iterations
     * @param sessions      the sessions in which the tasks are to be replaced
     * @param appData       the rule application data combining all data used for applying this rule
     */
    private void replaceIterationsOf(Set<ITask>          iteratedTasks,
                                     List<IUserSession>  sessions,
                                     RuleApplicationData appData)
    {
        Map<ITask, IIteration> iterations = new HashMap<ITask, IIteration>();
        Map<IIteration, IOptional> optionals = new HashMap<IIteration, IOptional>();
        Map<IIteration, List<IIterationInstance>> iterationInstances =
                new HashMap<IIteration, List<IIterationInstance>>();
            
        for (ITask iteratedTask : iteratedTasks) {
            IIteration iteration = taskFactory.createNewIteration();
            iterations.put(iteratedTask, iteration);
            
            if (iteratedTask instanceof IOptional) {
                IOptional optional = taskFactory.createNewOptional();
                taskBuilder.setMarkedTask(optional, iteration);
                optionals.put(iteration, optional);
            }
            
            iterationInstances.put(iteration, new LinkedList<IIterationInstance>());
        }
        
        IOptionalInstance optionalInstance;
        IIterationInstance iterationInstance;
        
        for (IUserSession session : sessions) {
            int index = 0;
            optionalInstance = null;
            iterationInstance = null;
            boolean inReplacement = false;

            while (index < session.size()) {
                // we prepared the task instances to refer to unique tasks, if they are treated
                // as equal. Therefore, we just compare the identity of the tasks of the task
                // instances
                ITask currentTask = session.get(index).getTask();
                IIteration iteration = iterations.get(currentTask);
                if (iteration != null) {
                    if (!inReplacement || (iterationInstance.getTask() != iteration)) {
                        if (currentTask instanceof IOptional) {
                            IOptional optional = optionals.get(iteration);
                            optionalInstance = taskFactory.createNewTaskInstance(optional);
                            taskBuilder.addTaskInstance(session, index, optionalInstance);
                        }
                        else {
                            iterationInstance = taskFactory.createNewTaskInstance(iteration);
                            iterationInstances.get(iteration).add(iterationInstance);
                            taskBuilder.addTaskInstance(session, index, iterationInstance);
                        }
                        inReplacement = true;
                        index++;
                    }
                    
                    if (currentTask instanceof IOptional) {
                        ITaskInstance child = ((IOptionalInstance) session.get(index)).getChild();
                        
                        if (child != null) {
                            if (iterationInstance == null) {
                                iterationInstance = taskFactory.createNewTaskInstance(iteration);
                                iterationInstances.get(iteration).add(iterationInstance);
                                taskBuilder.setChild(optionalInstance, iterationInstance);
                            }
                            taskBuilder.addChild(iterationInstance, child);
                        }
                    }
                    else {
                        taskBuilder.addChild(iterationInstance, session.get(index));
                    }
                    
                    taskBuilder.removeTaskInstance(session, index);
                }
                else {
                    if (iterationInstance != null) {
                        iterationInstance = null;
                        optionalInstance = null;
                        inReplacement = false;
                    }
                    index++;
                }
            }
        }
        
        for (Map.Entry<IIteration, List<IIterationInstance>> entry : iterationInstances.entrySet())
        {
            harmonizeIterationInstancesModel(entry.getKey(), entry.getValue());
        }
    }

    /**
     * <p>
     * TODO clarify why this is done
     * </p>
     */
    private void harmonizeIterationInstancesModel(IIteration               iteration,
                                                  List<IIterationInstance> iterationInstances)
    {
        List<ITask> iteratedTaskVariants = new LinkedList<ITask>();
        TaskComparator comparator = preparationTaskHandlingStrategy.getTaskComparator();
        
        // merge the lexically different variants of iterated task to a unique list 
        for (IIterationInstance iterationInstance : iterationInstances) {
            for (ITaskInstance executionVariant : iterationInstance) {
                ITask candidate = executionVariant.getTask();
            
                boolean found = false;
                for (ITask taskVariant : iteratedTaskVariants) {
                    if (comparator.areLexicallyEqual(taskVariant, candidate)) {
                        taskBuilder.setTask(executionVariant, taskVariant);
                        found = true;
                        break;
                    }
                }
                
                if (!found) {
                    iteratedTaskVariants.add(candidate);
                }
            }
        }
        
        // if there are more than one lexically different variant of iterated tasks, adapt the
        // iteration model to be a selection of different variants. In this case also adapt
        // the generated iteration instances to correctly contain selection instances. If there
        // is only one variant of an iterated task, simply set this as the marked task of the
        // iteration. In this case, the instances can be preserved as is
        if (iteratedTaskVariants.size() > 1) {
            ISelection selection = taskFactory.createNewSelection();
            
            for (ITask variant : iteratedTaskVariants) {
                taskBuilder.addChild(selection, variant);
            }
            
            taskBuilder.setMarkedTask(iteration, selection);
            
            for (IIterationInstance instance : iterationInstances) {
                for (int i = 0; i < instance.size(); i++) {
                    ISelectionInstance selectionInstance =
                        taskFactory.createNewTaskInstance(selection);
                    taskBuilder.setChild(selectionInstance, instance.get(i));
                    taskBuilder.setTaskInstance(instance, i, selectionInstance);
                }
            }
        }
        else {
            taskBuilder.setMarkedTask(iteration, iteratedTaskVariants.get(0));
        }
    }

    /**
     * TODO go on commenting
     * @param appData the rule application data combining all data used for applying this rule
     */
    private void detectAndReplaceTasks(RuleApplicationData appData) {
        Console.traceln(Level.FINE, "detecting and replacing tasks");
        appData.getStopWatch().start("detecting tasks");
        
        getSubsequencesOccuringMostOften(appData);
        
        appData.getStopWatch().stop("detecting tasks");
        appData.getStopWatch().start("sorting tasks");
        
        removeInterleavingTasks(appData);

        appData.getStopWatch().stop("sorting tasks");
        appData.getStopWatch().start("replacing tasks");
        
        replaceSequencesOccurringMostOften(appData);
        
        appData.getStopWatch().stop("replacing tasks");
        Console.traceln(Level.INFO, "detected and replaced " + appData.getLastFoundSubsequences().size() +
                        " tasks occuring " + appData.getLastFoundSubsequences().getOccurrenceCount() +
                        " times");
    }

    /**
     * @param appData the rule application data combining all data used for applying this rule
     */
    private void getSubsequencesOccuringMostOften(RuleApplicationData appData) {
        Console.traceln(Level.FINER, "determining most prominent subsequences");

        Subsequences subsequences;
        boolean createNewTrie = (appData.getLastTrie() == null) ||
            appData.detectedAndReplacedTasks(); // tree has changed
        
        do {
            if (createNewTrie) {
                createNewTrie(appData);
            }
            
            MaxCountAndLongestSubsequencesFinder finder = new MaxCountAndLongestSubsequencesFinder();
            appData.getLastTrie().process(finder);
        
            subsequences = finder.getFoundSubsequences();
            
            createNewTrie = false;
            
            for (Subsequence subsequence : subsequences) {
                if (subsequence.size() >= appData.getTrainedSubsequenceLength()) {
                    // Trie must be recreated with a longer sequence length to be sure that
                    // the found sequences occurring most often are found in their whole length
                    appData.setTrainedSubsequenceLength(appData.getTrainedSubsequenceLength() + 3);
                    createNewTrie = true;
                    break;
                }
            }
        }
        while (createNewTrie);
        
        // create a normal trie for comparison
        /*System.out.println("creating test trie for comparison");
        
        appData.getStopWatch().start("testtrie");
        Trie<ITaskInstance> trie = new Trie<ITaskInstance>(identityTaskComparator);
        
        for (IUserSession session : appData.getSessions()) {
            trie.train(session.getExecutedTasks(), appData.getTrainedSequenceLength());
        }
        
        appData.getStopWatch().stop("testtrie");
        
        MaxCountAndLongestTasksFinder finder = new MaxCountAndLongestTasksFinder();
        trie.process(finder);

        boolean allTasksEqual = finder.getFoundTasks().size() == tasks.size();
        
        allTasksEqual &= finder.getFoundTasks().occurrenceCount == tasks.occurrenceCount;
        
        for (List<ITaskInstance> task1 : finder.getFoundTasks()) {
            boolean foundTask = false;
            for (List<ITaskInstance> task2 : tasks) {
                boolean tasksEqual = false;
                if (task1.size() == task2.size()) {
                    tasksEqual = true;
                    for (int i = 0; i < task1.size(); i++) {
                        if (!identityTaskComparator.equals(task1.get(i).getTask(), task2.get(i).getTask()))
                        {
                            tasksEqual = false;
                        }
                    }
                }
                
                if (tasksEqual) {
                    foundTask = true;
                    break;
                }
            }
            
            if (!foundTask) {
                System.out.println("different is " + task1);
                allTasksEqual = false;
                break;
            }
        }
        
        if (!allTasksEqual) {
            System.out.println(finder.getFoundTasks());
            System.out.println(tasks);
            
            throw new IllegalArgumentException("both tries calculated different subsequences");
        }
        
        /*TrieStatisticsDumper dumper = new TrieStatisticsDumper();
        appData.getLastTrie().process(dumper);
        dumper.dumpCounters();*/
        
        appData.setLastFoundSubsequences(subsequences);

        Console.traceln(Level.FINE, "found " + appData.getLastFoundSubsequences().size() +
                        " tasks occurring " +
                        appData.getLastFoundSubsequences().getOccurrenceCount() + " times");
    }

    /**
     * @param appData the rule application data combining all data used for applying this rule
     */
    private void createNewTrie(RuleApplicationData appData) {
        Console.traceln(Level.FINEST, "training trie with a maximum sequence length of " +
                        appData.getTrainedSubsequenceLength());

        appData.getStopWatch().start("training trie");
        
        // we prepared the task instances to refer to unique tasks, if they are treated
        // as equal. Therefore, we just compare the identity of the tasks of the task
        // instances
        appData.setLastTrie(new TaskInstanceTrie(identityTaskHandlingStrategy));
    
        appData.getLastTrie().trainSessions
            (appData.getSessions(), appData.getTrainedSubsequenceLength());
        
        appData.getStopWatch().stop("training trie");
    }

    /**
     * from the last found tasks, sort out those that interleave with each other as for them always
     * the same replacement order needs to be taken.
     */
    private void removeInterleavingTasks(RuleApplicationData appData) {
        // >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
        // >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> TEST IMPLEMENTATION >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
        // dumpSortedCollectionOfSubsequences
        //     ("found task", appData.getLastFoundSubsequences().subsequences);
        // <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
        // <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< TEST IMPLEMENTATION <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<

        List<InterleavingSubsequence> interleavings;
        
        do {
            interleavings = getInterleavings(appData.getLastFoundSubsequences(), appData);
            
            if (interleavings.size() > 0) {
                // dumpSorted(interleavings);

                // Console.traceln(Level.FINEST, "found " + interleavings.size() + " subsequences " +
                //                 "--> checking for most real interleavings");
                
                // we found interleaving subsequences. We need to decide for them, which to replace
                // first. For this, we need to remove some of them from the list of detected
                // subsequences in an ordered way to always have the same prioritization for
                // replacements. The ones to be removed are those with most interleavings.
                interleavings = getMostIntensiveInterleavings(interleavings);
                
                //dumpSorted(interleavings);
                
                if (interleavings.size() == 1) {
                    // Console.traceln(Level.FINEST, "found one most interleaving subsequence " +
                    //                 "--> removing it and checking for further interleavings");

                    // we have exactly one most interleaving detected subsequence. In this case,
                    // we remove it from the list of found subsequences and check again, if their
                    // are remaining interleavings. If not, we have the final list of non
                    // interleaving subsequences to be replaced. The order or their replacement
                    // doesn't matter as they are not interleaving.
                    appData.getLastFoundSubsequences().remove
                        (interleavings.get(0).getSubsequence());
                    
                    continue;
                }
                else if (interleavings.size() == 0) {
                    // this should never happen
                    throw new RuntimeException("Implementation error: don't know how I got here");
                }
                
                // Console.traceln(Level.FINEST, "found " + interleavings.size() + " most " +
                //                 "interleaving subsequences --> checking which are most often a " +
                //                 "successor");

                // there are several subsequences with the same amount of interleavings.
                // Check which of them is the most often a successor. This should be removed.
                interleavings = getMostInterleavingsAsSuccessor(interleavings);
                
                // dumpSorted(interleavings);

                if (interleavings.size() == 1) {
                    //  Console.traceln(Level.FINEST, "found one interleaving subsequence being most " +
                    //                  "often a successor --> removing it and checking for further " +
                    //                  "interleavings");

                    // we have exactly one interleaving subsequence that is most often a successor
                    // of the others. Remove it and try again to see if sufficient interleavings
                    // were cleared.
                    appData.getLastFoundSubsequences().remove
                        (interleavings.get(0).getSubsequence());
                    
                    continue;
                }
                else if (interleavings.size() == 0) {
                    // this should never happen
                    throw new RuntimeException("Implementation error: don't know how I got here");
                }
                
                // Console.traceln(Level.FINEST, "found " + interleavings.size() +
                //                 " most interleaving subsequences being most often a successor " +
                //                 "--> checking which is most seldom a predecessor");

                // there are several subsequences with the same amount of interleavings being also
                // the same times a successor of another subsequence. Hence, check which of them is
                // the least often a predecessor. This should be removed.
                interleavings = getLeastInterleavingsAsPredecessor(interleavings);
                
                //dumpSorted(interleavings);

                if (interleavings.size() == 1) {
                    // Console.traceln(Level.FINEST, "found one interleaving subsequence being most " +
                    //                 "often a successor and most seldom a predecessor --> " +
                    //                 "removing it and checking for further interleavings");

                    // we have exactly one interleaving subsequence that is most often a successor
                    // and most seldom a predecessor of the others. Remove it and try again to see
                    // if sufficient interleavings were cleared.
                    appData.getLastFoundSubsequences().remove
                        (interleavings.get(0).getSubsequence());
                    
                    continue;
                }
                else if (interleavings.size() == 0) {
                    // this should never happen
                    throw new RuntimeException("Implementation error: don't know how I got here");
                }
                
                // the remaining subsequences are interleaving the same amount of times and are
                // used the same amount of times as successors and as predecessors by all other
                // detected interleaving subsequences. Now lets check, which of them is mostly used
                // as successor and most seldom used as predecessor only considering the remaining
                // subsequences. If some of them do not interfere with the others, remove them and
                // try again to see if sufficient interleavings were cleared.
                
                // Console.traceln(Level.FINEST, "found " + interleavings.size() +
                //                 " most interleaving subsequences being most often a successor " +
                //                 "and most seldom a predecessor --> removing collision being not " +
                //                 "between themselves");

                interleavings = removeCollisionsOfOtherSubsequences(interleavings);
                
                // dumpSorted(interleavings);
                
                // Console.traceln(Level.FINEST, "removed collisions of other subsequences not " +
                //                 "belonging to the remaining interleaving subsequences --> " +
                //                 "checking of the remaining interleaving are most often a " +
                //                 "successor of another one");
                
                interleavings = getMostInterleavingsAsSuccessor(interleavings);
                interleavings = removeCollisionsOfOtherSubsequences(interleavings);
                
                // dumpSorted(interleavings);

                if (interleavings.size() == 1) {
                    // Console.traceln(Level.FINEST, "found one interleaving subsequence being most " +
                    //                 "often a successor in comparison to the other remaining " +
                    //                 "interleavings --> removing it and checking for further " +
                    //                 "interleavings");

                    appData.getLastFoundSubsequences().remove
                        (interleavings.get(0).getSubsequence());
                    
                    continue;
                }
                else if (interleavings.size() == 0) {
                    // this should never happen
                    throw new RuntimeException("Implementation error: don't know how I got here");
                }
                
                // Console.traceln(Level.FINEST, "found " + interleavings.size() +
                //                 " most interleaving subsequences being most often a successor in " +
                //                 "comparison to the other remaining interleavings --> checking " +
                //                 "which is most seldom a predecessor");

                interleavings = getLeastInterleavingsAsPredecessor(interleavings);
                interleavings = removeCollisionsOfOtherSubsequences(interleavings);
                
                // dumpSorted(interleavings);

                if (interleavings.size() == 1) {
                    // Console.traceln(Level.FINEST, "found one interleaving subsequence being most " +
                    //                 "often a successor and most seldom a predecessor in " +
                    //                 "comparison to the other remaining interleavings --> " +
                    //                 "removing it and checking for further interleavings");

                    appData.getLastFoundSubsequences().remove
                        (interleavings.get(0).getSubsequence());
                    
                    continue;
                }
                else if (interleavings.size() == 0) {
                    // this should never happen
                    throw new RuntimeException("Implementation error: don't know how I got here");
                }
                
                // Console.traceln(Level.FINEST, "found " + interleavings.size() +
                //                 " most interleaving subsequences being most often a successor " +
                //                 "and most seldom a predecessor in comparison to the other " +
                //                 "remaining interleavings --> this may happen if there are no " +
                //                 "collisions between them anymore. If so, remove all of them at " +
                //                 "once.");

                int collisionCount = 0;
                
                for (InterleavingSubsequence subsequence : interleavings) {
                    collisionCount += subsequence.getCollisionCounter();
                }
                
                if (collisionCount == 0) {
                    // Console.traceln(Level.FINEST, "remaining interleaving subsequences have no " +
                    //                 "further collisions with each other --> removing all of them " +
                    //                 "and checking for further interleavings");
                    
                    for (InterleavingSubsequence subsequence : interleavings) {
                        appData.getLastFoundSubsequences().remove(subsequence.getSubsequence());
                    }
                    
                    continue;
                }

                // Console.traceln(Level.FINEST, "remaining interleaving subsequences still have " +
                //                 "collisions with each other --> decide based on their occurrences" +
                //                 " in the sessions (remove those, coming later in comparison to " +
                //                 "the others)");
                
                // determine the predecessor collisions being the last in all sessions. Those
                // collisions show the interleaving subsequence occurring last 
                Map<IUserSession, Collision> sessions =
                    new IdentityHashMap<IUserSession, Collision>();
                
                for (InterleavingSubsequence interleaving : interleavings) {
                    for (Collision coll : interleaving.getPredecessorCollisions()) {
                        Collision maxPosColl = sessions.get(coll.getLocation().getSession());
                        
                        if ((maxPosColl == null) ||
                            (maxPosColl.getLocation().getIndex() < coll.getLocation().getIndex()))
                        {
                            sessions.put(coll.getLocation().getSession(), coll);
                        }
                    }
                }
                
                // determine, which of the subsequences occurs most often as the last one
                // interleaving with another
                Map<Subsequence, Integer> lastOccurrenceCounters =
                    new IdentityHashMap<Subsequence, Integer>();
                
                for (Collision coll : sessions.values()) {
                    Integer counter = lastOccurrenceCounters.get(coll.getSubsequence());
                    
                    if (counter == null) {
                        lastOccurrenceCounters.put(coll.getSubsequence(), 1);
                    }
                    else {
                        lastOccurrenceCounters.put(coll.getSubsequence(), counter + 1);
                    }
                }
                
                int maxCounter = 0;
                Subsequence toRemove = null;
                
                for (Map.Entry<Subsequence, Integer> entry : lastOccurrenceCounters.entrySet()) {
                    if (entry.getValue() > maxCounter) {
                        maxCounter = entry.getValue();
                        toRemove = entry.getKey();
                    }
                    else if (entry.getValue() == maxCounter) {
                        // we can not decide again
                        toRemove = null;
                        break;
                    }
                }
                
                if (toRemove != null) {
                    // Console.traceln(Level.FINEST, "one of the remaining interleaving subsequences" +
                    //                 " is most often the last to occur --> removing it and " +
                    //                 "checking for further interleavings");
            
                    appData.getLastFoundSubsequences().remove(toRemove);
                    continue;
                }
                
                // checking now, if there is one sequence, having the lowest index for any of
                // its collisions and preserve it. If there are several ones with the same minimum
                // index, check if they are independent. If not, throw an exception
                int minPosInAnySequence = Integer.MAX_VALUE;
                List<InterleavingSubsequence> subsequencesWithMinPos = new LinkedList<>();
                
                for (InterleavingSubsequence interleaving : interleavings) {
                    for (Collision collision : interleaving.getSuccessorCollisions()) {
                        if (minPosInAnySequence > collision.getLocation().getIndex()) {
                            minPosInAnySequence = collision.getLocation().getIndex();
                            subsequencesWithMinPos.clear();
                        }
                        
                        if (minPosInAnySequence == collision.getLocation().getIndex()) {
                            // several have the same min pos --> undecidable which to prefer
                            subsequencesWithMinPos.add(interleaving);
                        }
                    }
                }
                
                if (subsequencesWithMinPos.size() > 0) {
                    List<Subsequence> subsequencesToRemove = new LinkedList<Subsequence>();
                    
                    for (Subsequence candidate : appData.getLastFoundSubsequences()) {
                        boolean found = false;
                        
                        for (InterleavingSubsequence subsequenceWithMinPos : subsequencesWithMinPos)
                        {
                            if (candidate == subsequenceWithMinPos.getSubsequence()) {
                                found = true;
                            }
                        }
                        
                        if (!found) {
                            subsequencesToRemove.add(candidate);
                        }
                    }
                    
                    if (subsequencesToRemove.size() > 0) {
                        for (Subsequence candidate : subsequencesToRemove) {
                            appData.getLastFoundSubsequences().remove(candidate);
                        }
                    
                        continue;
                    }
                }
                
                // At this point, we can not decide anymore. But it should also not
                // happen. Even if two subsequences ab and ba one of them should be
                // more often a successor or predecessor than the other if they
                // directly follow each other. If not, it can not be decided, which of
                // them to replace first. Perhaps the one occurring more often as
                // the first in a session that the other. But this can be implemented
                // later.
                dumpSorted(interleavings, Level.SEVERE);
                
                throw new RuntimeException
                    ("can not decide which detected subsequence to replace first.");
            }
        }
        while (interleavings.size() > 0);

        // >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
        // >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> TEST IMPLEMENTATION >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
        // dumpSortedCollectionOfSubsequences
        //    ("to replace", appData.getLastFoundSubsequences().subsequences);
        // <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
        // <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< TEST IMPLEMENTATION <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
    }

    /**
     *
     */
    private List<InterleavingSubsequence> getInterleavings(Subsequences        subsequences,
                                                           RuleApplicationData appData)
    {
        List<InterleavingSubsequence> interleavings = new LinkedList<InterleavingSubsequence>();
        List<Subsequence> potentialPredecessors = new LinkedList<Subsequence>();
        List<Subsequence> potentialSuccessors = new LinkedList<Subsequence>();
        
        Map<Subsequence, List<SubsequenceLocation>> allLocations =
            getLocations(subsequences, appData);
        
        for (Subsequence subsequence : subsequences) {
            // Console.traceln
            //    (Level.FINEST, "searching for interleavings of " + toPlainStr(subsequence));

            potentialPredecessors.clear();
            potentialSuccessors.clear();
            
            getInterleavingSubsequences
                (subsequence, subsequences, potentialPredecessors, potentialSuccessors);
            
            if ((potentialPredecessors.size() <= 0) && (potentialSuccessors.size() <= 0)) {
                // subsequence is not interleaving with others. Check next one.
                continue;
            }
            
            // subsequence is interleaving. First, determine its locations in the user sessions.
            List<SubsequenceLocation> locations = allLocations.get(subsequence);
            
            List<Collision> precedingCollisions =
                getPrecedingCollisions(subsequence, locations, potentialPredecessors, appData);
            
            List<Collision> succeedingCollisions =
                getSucceedingCollisions(subsequence, locations, potentialSuccessors, appData);
            
            if ((precedingCollisions.size() <= 0) && (succeedingCollisions.size() <= 0)) {
                // subsequence is not interleaving with others. Check next one.
                continue;
            }
            
            interleavings.add(new InterleavingSubsequence(subsequence, precedingCollisions,
                                                          succeedingCollisions));
        }
        
        return interleavings;
    }

    /**
     *
     */
    private void getInterleavingSubsequences(Subsequence       subsequence,
                                             Subsequences      allSubsequences,
                                             List<Subsequence> potentialPredecessors,
                                             List<Subsequence> potentialSuccessors)
    {
        TaskComparator comparator = identityTaskHandlingStrategy.getTaskComparator();
        
        for (Subsequence candidate : allSubsequences) {
            if (comparator.equals(subsequence.get(subsequence.size() - 1), candidate.get(0))) {
                potentialSuccessors.add(candidate);
            }
            
            if (comparator.equals(subsequence.get(0), candidate.get(candidate.size() - 1))) {
                potentialPredecessors.add(candidate);
            }
        }

        // >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
        // >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> TEST IMPLEMENTATION >>>>>>>>>>>>>>>>>>>>>>>>>>>>>
        // Console.traceln(Level.FINEST, "  potential successors of " + toPlainStr(subsequence));
        // dumpSortedCollectionOfSubsequences("    ", potentialSuccessors);
        
        // Console.traceln(Level.FINEST, "  potential predecessors of " + toPlainStr(subsequence));
        // dumpSortedCollectionOfSubsequences("    ", potentialPredecessors);
        // <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
        // <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< TEST IMPLEMENTATION <<<<<<<<<<<<<<<<<<<<<<<<<<<<<
    }

    /**
     *
     */
    private Map<Subsequence, List<SubsequenceLocation>> getLocations(Subsequences        subsequences,
                                                                     RuleApplicationData appData)
    {
        Map<Subsequence, List<SubsequenceLocation>> result =
            new IdentityHashMap<Subsequence, List<SubsequenceLocation>>();
        
        // fill the map with empty locations
        for (Subsequence subsequence : subsequences) {
            result.put(subsequence, new LinkedList<SubsequenceLocation>());
        }
        
        LinkedList<LinkedList<Subsequence>> candidates = new LinkedList<LinkedList<Subsequence>>();

        for (IUserSession session : appData.getSessions()) {
            for (int i = 0; i < session.size(); i++) {
                ITask currentTask = session.get(i).getTask();
                
                // create a list of candidates that may start here
                LinkedList<Subsequence> candidatesToStartHere = new LinkedList<Subsequence>();
                
                for (Subsequence candidate : subsequences) {
                    if (candidate.get(0) == currentTask) {
                        candidatesToStartHere.add(candidate);
                    }
                }
                
                candidates.addFirst(candidatesToStartHere);
                
                // check if the other candidates continue here.
                ListIterator<LinkedList<Subsequence>> candidatesIt = candidates.listIterator(1);
                int index = 1;
                while (candidatesIt.hasNext()) {
                    ListIterator<Subsequence> candidateIt = candidatesIt.next().listIterator();
                    while (candidateIt.hasNext()) {
                        Subsequence candidate = candidateIt.next();
                        
                        if (candidate.get(index) == currentTask) {
                            if (candidate.size() == (index + 1)) {
                                // subsequence was fully matched --> store location
                                result.get(candidate).add
                                    (new SubsequenceLocation(session, i - candidate.size() + 1));
                                candidateIt.remove();
                            }
                        }
                        else if (candidate.get(index) != currentTask) {
                            // remove the candidate as it is not located here
                            candidateIt.remove();
                        }
                    }
                    
                    index++;
                }
                
                // remove potential continuation being empty
                while ((candidates.size() > 0) && (candidates.getLast().size() == 0)) {
                    candidates.removeLast();
                }
            }
        }
        
        return result;
    }

    /**
     *
     */
    private List<Collision> getPrecedingCollisions(Subsequence               subsequence,
                                                   List<SubsequenceLocation> locations,
                                                   List<Subsequence>         potentialPredecessors,
                                                   RuleApplicationData       appData)
    {
        List<Collision> precedingCollisions = new LinkedList<Collision>();
        int interleavingStartIndex;
        int interleavingEndIndex;
        
        for (SubsequenceLocation location : locations) {
            for (Subsequence predecessor : potentialPredecessors) {
                // start where the interleaving would start
                interleavingStartIndex = location.getIndex() - predecessor.size() + 1;
                
                if (interleavingStartIndex >= 0) {
                    interleavingEndIndex =
                        getSubListIndex(location.getSession(), predecessor, interleavingStartIndex);
                
                    if (interleavingStartIndex == interleavingEndIndex) {
                        precedingCollisions.add(new Collision(location, subsequence, predecessor));
                    }
                }
            }
        }
        
        return precedingCollisions;
    }

    /**
     *
     */
    private List<Collision> getSucceedingCollisions(Subsequence               subsequence,
                                                    List<SubsequenceLocation> locations,
                                                    List<Subsequence>         potentialPredecessors,
                                                    RuleApplicationData       appData)
    {
        List<Collision> succeedingCollisions = new LinkedList<Collision>();
        int interleavingStartIndex;
        int interleavingEndIndex;

        for (SubsequenceLocation location : locations) {
            for (Subsequence successor : potentialPredecessors) {
                interleavingStartIndex = location.getIndex() + subsequence.size() - 1;
                interleavingEndIndex =
                    getSubListIndex(location.getSession(), successor, interleavingStartIndex);

                if (interleavingStartIndex == interleavingEndIndex) {
                    succeedingCollisions.add(new Collision(location, subsequence, successor));
                }
            }
        }
        
        return succeedingCollisions;
    }
    
    /**
     *
     */
    private List<InterleavingSubsequence> getMostIntensiveInterleavings
        (List<InterleavingSubsequence> interleavings)
    {
        List<InterleavingSubsequence> mostIntensiveInterleavings =
            new LinkedList<InterleavingSubsequence>();
        
        int collisionCounter = 0;
        
        for (InterleavingSubsequence interleaving : interleavings) {
            if (interleaving.getCollisionCounter() > collisionCounter) {
                collisionCounter = interleaving.getCollisionCounter();
                mostIntensiveInterleavings.clear();
            }
            
            if (interleaving.getCollisionCounter() == collisionCounter) {
                mostIntensiveInterleavings.add(interleaving);
            }
        }
        
        return mostIntensiveInterleavings;
    }

    /**
     *
     */
    private List<InterleavingSubsequence> getLeastInterleavingsAsPredecessor
        (List<InterleavingSubsequence> interleavings)
    {
        List<InterleavingSubsequence> leastInterleavingsAsPredecessor =
            new LinkedList<InterleavingSubsequence>();
            
        int collisionCounter = Integer.MAX_VALUE;

        for (InterleavingSubsequence interleaving : interleavings) {
            if (interleaving.getSuccessorCollisionCounter() < collisionCounter) {
                collisionCounter = interleaving.getSuccessorCollisionCounter();
                leastInterleavingsAsPredecessor.clear();
            }

            if (interleaving.getSuccessorCollisionCounter() == collisionCounter) {
                leastInterleavingsAsPredecessor.add(interleaving);
            }
        }

        return leastInterleavingsAsPredecessor;
    }

    /**
     *
     */
    private List<InterleavingSubsequence> getMostInterleavingsAsSuccessor
        (List<InterleavingSubsequence> interleavings)
    {
        List<InterleavingSubsequence> mostInterleavingsAsSuccessor =
            new LinkedList<InterleavingSubsequence>();
           
        int collisionCounter = 0;

        for (InterleavingSubsequence interleaving : interleavings) {
            if (interleaving.getPredecessorCollisionCounter() > collisionCounter) {
                collisionCounter = interleaving.getPredecessorCollisionCounter();
                mostInterleavingsAsSuccessor.clear();
            }

            if (interleaving.getPredecessorCollisionCounter() == collisionCounter) {
                mostInterleavingsAsSuccessor.add(interleaving);
            }
        }

        return mostInterleavingsAsSuccessor;
    }

    /**
     *
     */
    private List<InterleavingSubsequence> removeCollisionsOfOtherSubsequences
        (List<InterleavingSubsequence> interleavings)
    {
        List<InterleavingSubsequence> subsequencesWithoutOtherCollisions =
            new LinkedList<InterleavingSubsequence>();
        
        for (InterleavingSubsequence interleaving : interleavings) {
            List<Collision> reducedPredecessorCollisions = new LinkedList<>();
            
            for (Collision collision : interleaving.getPredecessorCollisions()) {
                for (InterleavingSubsequence otherInterleaving : interleavings) {
                    if (otherInterleaving.getSubsequence() == collision.getCollidingWith()) {
                        reducedPredecessorCollisions.add(collision);
                        break;
                    }
                }
            }
            
            List<Collision> reducedSuccessorCollisions = new LinkedList<>();
            
            for (Collision collision : interleaving.getSuccessorCollisions()) {
                for (InterleavingSubsequence otherInterleaving : interleavings) {
                    if (otherInterleaving.getSubsequence() == collision.getCollidingWith()) {
                        reducedSuccessorCollisions.add(collision);
                        break;
                    }
                }
            }
            
            subsequencesWithoutOtherCollisions.add
                (new InterleavingSubsequence(interleaving.getSubsequence(),
                                             reducedPredecessorCollisions,
                                             reducedSuccessorCollisions));
        }
        
        return subsequencesWithoutOtherCollisions;
    }

    /**
     * @param appData the rule application data combining all data used for applying this rule
     */
    private void replaceSequencesOccurringMostOften(RuleApplicationData appData) {
        appData.detectedAndReplacedTasks(false);

        if ((appData.getLastFoundSubsequences().size() > 0) &&
            (appData.getLastFoundSubsequences().getOccurrenceCount() > 1))
        {
            Console.traceln(Level.FINER, "replacing tasks occurrences");

            for (Subsequence subsequence : appData.getLastFoundSubsequences()) {
                ISequence sequence = taskFactory.createNewSequence();
                
                Console.traceln(Level.FINEST, "replacing " + sequence.getId() + ": " + subsequence);

                List<ISequenceInstance> sequenceInstances = replaceSubsequenceOccurrences
                    (subsequence, appData.getSessions(), sequence);
                
                harmonizeSequenceInstancesModel(sequence, sequenceInstances, subsequence.size());
                appData.detectedAndReplacedTasks
                    (appData.detectedAndReplacedTasks() || (sequenceInstances.size() > 0));

                if (sequenceInstances.size() < appData.getLastFoundSubsequences().getOccurrenceCount()) {
                    Console.traceln(Level.FINE, sequence.getId() + ": replaced task only " +
                                    sequenceInstances.size() + " times instead of expected " +
                                    appData.getLastFoundSubsequences().getOccurrenceCount());
                }
            }
        }
    }

    /**
     *
     */
    private void harmonizeSequenceInstancesModel(ISequence               sequence,
                                                 List<ISequenceInstance> sequenceInstances,
                                                 int                     sequenceLength)
    {
        TaskComparator comparator = preparationTaskHandlingStrategy.getTaskComparator();
        
        // ensure for each subtask that lexically different variants are preserved
        for (int subTaskIndex = 0; subTaskIndex < sequenceLength; subTaskIndex++) {
            List<ITask> subTaskVariants = new LinkedList<ITask>();
            
            for (ISequenceInstance sequenceInstance : sequenceInstances) {
                ITask candidate = sequenceInstance.get(subTaskIndex).getTask();
                
                boolean found = false;
                
                for (int i = 0; i < subTaskVariants.size(); i++) {
                    if (comparator.areLexicallyEqual(subTaskVariants.get(i), candidate)) {
                        taskBuilder.setTask
                            (sequenceInstance.get(subTaskIndex), subTaskVariants.get(i));
                        
                        found = true;
                        break;
                    }
                }
                
                if (!found) {
                    subTaskVariants.add(candidate);
                }
            }
            
            // if there are more than one lexically different variant of the sub task at
            // the considered position, adapt the sequence model at that position to have
            // a selection of the different variants. In this case also adapt the
            // generated sequence instances to correctly contain selection instances. If
            // there is only one variant of sub tasks at the given position, simply set
            // this variant as the sub task of the selection. In this case, the instances
            // can be preserved as is
            if (subTaskVariants.size() > 1) {
                ISelection selection = taskFactory.createNewSelection();
                
                for (ITask variant : subTaskVariants) {
                    taskBuilder.addChild(selection, variant);
                }
                
                taskBuilder.addChild(sequence, selection);
                
                for (ISequenceInstance instance : sequenceInstances) {
                    ISelectionInstance selectionInstance =
                        taskFactory.createNewTaskInstance(selection);
                    taskBuilder.setChild(selectionInstance, instance.get(subTaskIndex));
                    taskBuilder.setTaskInstance(instance, subTaskIndex, selectionInstance);
                }
            }
            else if (subTaskVariants.size() == 1) {
                taskBuilder.addChild(sequence, subTaskVariants.get(0));
            }
        }
    }

    /**
     * @param tree
     */
    private List<ISequenceInstance> replaceSubsequenceOccurrences(Subsequence         subsequence,
                                                                  List<IUserSession>  sessions,
                                                                  ISequence           temporalTaskModel)
    {
        List<ISequenceInstance> sequenceInstances = new LinkedList<ISequenceInstance>();
        
        for (IUserSession session : sessions) {
            int index = -1;
            
            do {
                index = getSubListIndex(session, subsequence, ++index);

                if (index > -1) {
                    // subsequence is found --> perform replacement
                    sequenceInstances.add
                        (RuleUtils.createNewSubSequenceInRange
                             (session, index, index + subsequence.size() - 1, temporalTaskModel,
                              taskFactory, taskBuilder));
                }
            }
            while (index > -1);
        }
        
        return sequenceInstances;
    }

    /**
     * @param trie
     * @param object
     * @return
     */
    private int getSubListIndex(ITaskInstanceList   list,
                                Subsequence         subsequence,
                                int                 startIndex)
    {
        boolean matchFound;
        int result = -1;
        
        for (int i = startIndex; i <= list.size() - subsequence.size(); i++) {
            matchFound = true;
            
            for (int j = 0; j < subsequence.size(); j++) {
                // we prepared the task instances to refer to unique tasks, if they are treated
                // as equal. Therefore, we just compare the identity of the tasks of the task
                // instances
                if (list.get(i + j).getTask() != subsequence.get(j)) {
                    matchFound = false;
                    break;
                }
            }
            
            if (matchFound) {
                result = i;
                break;
            }
        }
        
        return result;
    }

    /**
     * @param trie
     * @param object
     * @return
     */
    private int getSubListIndex(Subsequence longerSubsequence,
                                Subsequence shorterSubsequence,
                                int         startIndex)
    {
        boolean matchFound;
        int result = -1;
        
        for (int i = startIndex; i <= longerSubsequence.size() - shorterSubsequence.size(); i++) {
            matchFound = true;
            
            for (int j = 0; j < shorterSubsequence.size(); j++) {
                // we prepared the task instances to refer to unique tasks, if they are treated
                // as equal. Therefore, we just compare the identity of the tasks of the task
                // instances
                if (longerSubsequence.get(i + j) != shorterSubsequence.get(j)) {
                    matchFound = false;
                    break;
                }
            }
            
            if (matchFound) {
                result = i;
                break;
            }
        }
        
        return result;
    }

//  /**
//   *
//   */
//  private void dumpSorted(List<InterleavingSubsequence> interleavings) {
//      dumpSorted(interleavings, Level.FINEST);
//  }

    /**
     *
     */
    private void dumpSorted(List<InterleavingSubsequence> interleavings, Level level) {
        List<String> tmpList = new LinkedList<String>();

        for (InterleavingSubsequence interleaving : interleavings) {
            String taskStr = toPlainStr(interleaving);
            int index;
            for (index = 0; index < tmpList.size(); index++) {
                if (taskStr.compareTo(tmpList.get(index)) > 0) {
                    break;
                }
            }

            tmpList.add(index, taskStr);
        }

        for (String task : tmpList) {
            Console.traceln(level, task);
        }
    }

//    /**
//     *
//     */
//    private void dumpSortedCollectionOfSubsequences(String                  prefix,
//                                                    Collection<Subsequence> subsequences)
//    {
//        List<String> tmpList = new LinkedList<String>();
//
//        for (Subsequence subsequence : subsequences) {
//            String taskStr = toPlainStr(subsequence);
//            int index;
//            for (index = 0; index < tmpList.size(); index++) {
//                if (taskStr.compareTo(tmpList.get(index)) > 0) {
//                    break;
//                }
//            }
//
//            tmpList.add(index, taskStr);
//        }
//
//        for (String task : tmpList) {
//            Console.traceln(Level.FINEST, prefix + " " + task);
//        }
//    }

    /**
     *
     */
    private String toPlainStr(InterleavingSubsequence interleaving) {
        StringBuffer result = new StringBuffer();
        result.append("interleavings of ");
        result.append(toPlainStr(interleaving.getSubsequence()));
        result.append("\n  predecessor collisions:\n");

        for (Collision collision : interleaving.getPredecessorCollisions()) {
            result.append("    ");
            result.append(toPlainStr(collision.getCollidingWith()));
            result.append(" (");
            result.append(collision.getLocation());
            result.append(")\n");
        }

        result.append("  successor collisions:\n");

        for (Collision collision : interleaving.getSuccessorCollisions()) {
            result.append("    ");
            result.append(toPlainStr(collision.getCollidingWith()));
            result.append(" (");
            result.append(collision.getLocation());
            result.append(")\n");
        }

        return result.toString();
    }

    /**
     *
     */
    private String toPlainStr(Subsequence subsequence) {
        StringBuffer result = new StringBuffer();
        result.append(subsequence.size());
        result.append(": ");
        for (ITask task : subsequence) {
            DebuggingHelper.toPlainStr(task, result);
            result.append(" --> ");
        }

        return result.toString();
    }
    
    
    /**
     * @author Patrick Harms
     */
    private class MaxCountAndLongestSubsequencesFinder implements TrieProcessor<ITask> {
        
        /**
         * 
         */
        private int currentCount;
        
        /**
         * 
         */
        private LinkedList<Subsequence> foundSubsequences = new LinkedList<Subsequence>();

        /**
         *
         */
        public MaxCountAndLongestSubsequencesFinder() {
            super();
            this.currentCount = 0;
        }

        /* (non-Javadoc)
         * @see de.ugoe.cs.autoquest.usageprofiles.TrieProcessor#process(java.util.List, int)
         */
        @Override
        public TrieProcessor.Result process(List<ITask> foundTask, int count) {
            if (foundTask.size() < 2) {
                // ignore single tasks
                return TrieProcessor.Result.CONTINUE;
            }
            
            if (count < 2) {
                // ignore singular occurrences
                return TrieProcessor.Result.SKIP_NODE;
            }

            if (this.currentCount > count) {
                // ignore this children of this task, as they may have only smaller counts than
                // the already found tasks
                return TrieProcessor.Result.SKIP_NODE;
            }
            
            if (this.currentCount < count) {
                // the provided task occurs more often that all tasks found so far.
                // clear all found tasks and use the new count as the one searched for
                foundSubsequences.clear();
                this.currentCount = count;
            }
            
            if (this.currentCount == count) {
                // the task is of interest. Sort it into the other found tasks so that
                // the longest come first
                boolean added = false;
                for (int i = 0; i < foundSubsequences.size(); i++) {
                    if (foundSubsequences.get(i).size() < foundTask.size()) {
                        foundSubsequences.add(i, new Subsequence(currentCount, foundTask));
                        added = true;
                        break;
                    }
                }
                
                if (!added) {
                    foundSubsequences.add(new Subsequence(currentCount, foundTask));
                }
            }
            
            return TrieProcessor.Result.CONTINUE;
        }

        /**
         *  @return
         */
        private Subsequences getFoundSubsequences() {
            removePermutationsOfShorterTasks();
            return new Subsequences(currentCount, foundSubsequences);
        }

        /**
         *
         */
        private void removePermutationsOfShorterTasks() {
            // now iterate the sorted list and for each task remove all other tasks that are shorter
            // (i.e. come later in the sorted list) and that represent a subpart of the task
            
            boolean removeI;
            
            for (int i = 0; i < foundSubsequences.size();) {
                removeI = false;
                boolean removeJ;
                
                for (int j = i + 1; j < foundSubsequences.size();) {
                    removeJ = false;
                    
                    if (foundSubsequences.get(j).size() < foundSubsequences.get(i).size()) {
                        // found a task that is a potential subtask. Check for this and remove the
                        // subtask if needed
                        Subsequence longTask = foundSubsequences.get(i);
                        Subsequence shortTask = foundSubsequences.get(j);
                        
                        int index = getSubListIndex(longTask, shortTask, 0);
                        if (index > -1) {
                            if (index == 0) {
                                // check if the short task is included in the long task partially
                                // a second time. If so, prefer the short task
                                boolean secondInclude = true;
                                for (int pos = shortTask.size(); pos < longTask.size(); pos++) {
                                    // we prepared the task instances to refer to unique tasks, if
                                    // they are treated as equal. Therefore, we just compare the
                                    // identity of the tasks of the task instances
                                    if (longTask.get(pos) != shortTask.get(pos % shortTask.size()))
                                    {
                                        secondInclude = false;
                                        break;
                                    }
                                }
                                
                                if (secondInclude) {
                                    // delete the long task
                                    // Console.traceln(Level.FINEST, "1: short task is contained several times in longer one --> removing it");
                                    // Console.traceln(Level.FINEST, "short: " + toPlainStr(shortTask));
                                    // Console.traceln(Level.FINEST, "long: " + toPlainStr(longTask));
                                    removeI = true;
                                }
                                else {
                                    // Console.traceln(Level.FINEST, "2: short task is a part of a longer one --> removing it");
                                    // Console.traceln(Level.FINEST, "short: " + toPlainStr(shortTask));
                                    // Console.traceln(Level.FINEST, "long: " + toPlainStr(longTask));
                                    removeJ = true;
                                }
                            }
                            else {
                                // Console.traceln(Level.FINEST, "3: short task is a part of a longer one --> removing it");
                                // Console.traceln(Level.FINEST, "short: " + toPlainStr(shortTask));
                                // Console.traceln(Level.FINEST, "long: " + toPlainStr(longTask));
                                removeJ = true;
                            }
                        }
                    }
                    
                    if (removeJ) {
                        foundSubsequences.remove(j);
                    }
                    else {
                        j++;
                    }
                }
                
                if (removeI) {
                    foundSubsequences.remove(i);
                }
                else {
                    i++;
                }
            }
        }

    }

//    /**
//     * @author Patrick Harms
//     */
//    private class TrieStatisticsDumper implements TrieProcessor<ITaskInstance> {
//        
//        /**
//         * 
//         */
//        private Map<Integer, Integer> counters = new HashMap<Integer, Integer>();
//        
//        /* (non-Javadoc)
//         * @see de.ugoe.cs.autoquest.usageprofiles.TrieProcessor#process(java.util.List, int)
//         */
//        @Override
//        public TrieProcessor.Result process(List<ITaskInstance> subsequence, int count) {
//            if (subsequence.size() == 1) {
//                Integer value = counters.get(count);
//                
//                if (value == null) {
//                    value = 0;
//                }
//                
//                counters.put(count, value + 1);
//                
//                return TrieProcessor.Result.CONTINUE;
//            }
//            else {
//                // ignore singular occurrences
//                return TrieProcessor.Result.SKIP_NODE;
//            }
//        }
//
//        /**
//         *  @return
//         */
//        public void dumpCounters() {
//            int dumpedCounters = 0;
//            
//            int count = 1;
//            while (dumpedCounters < counters.size()) {
//                Integer value = counters.get(count++);
//                if (value != null) {
//                    System.out.println(value + " symbols occurred " + count + " times");
//                    dumpedCounters++;
//                }
//            }
//        }
//
//    }
    
    /**
     * 
     */
    private static class RuleApplicationData {
        
        /**
         * 
         */
        private List<IUserSession> sessions;
        
        /**
         * 
         */
        private TaskInstanceTrie lastTrie;
        
        /**
         * default and minimum trained subsequence length is 3
         */
        private int trainedSubsequenceLength = 3;
        
        /**
         * 
         */
        private Subsequences lastFoundSubsequences = new Subsequences(Integer.MAX_VALUE, null);
        
        /**
         * 
         */
        private boolean detectedAndReplacedTasks;
        
        /**
         * 
         */
        private RuleApplicationResult result = new RuleApplicationResult();
        
        /**
         * 
         */
        private StopWatch stopWatch = new StopWatch();
        
        /**
         * 
         */
        private RuleApplicationData(List<IUserSession> sessions) {
            this.sessions = sessions;
        }

        /**
         * @return the tree
         */
        private List<IUserSession> getSessions() {
            return sessions;
        }

        /**
         * @param lastTrie the lastTrie to set
         */
        private void setLastTrie(TaskInstanceTrie lastTrie) {
            this.lastTrie = lastTrie;
        }

        /**
         * @return the lastTrie
         */
        private TaskInstanceTrie getLastTrie() {
            return lastTrie;
        }

        /**
         * @param trainedSubsequenceLength the trainedSubsequenceLength to set
         */
        private void setTrainedSubsequenceLength(int trainedSubsequenceLength) {
            this.trainedSubsequenceLength = trainedSubsequenceLength;
        }

        /**
         * @return the trainedSubsequenceLength
         */
        private int getTrainedSubsequenceLength() {
            return trainedSubsequenceLength;
        }

        /**
         * @param lastFoundSequences the lastFoundSequences to set
         */
        private void setLastFoundSubsequences(Subsequences lastFoundSequences) {
            this.lastFoundSubsequences = lastFoundSequences;
        }

        /**
         * @return the lastFoundSequences
         */
        private Subsequences getLastFoundSubsequences() {
            return lastFoundSubsequences;
        }

        /**
         *
         */
        private void detectedAndReplacedTasks(boolean detectedAndReplacedTasks) {
            this.detectedAndReplacedTasks = detectedAndReplacedTasks;
        }

        /**
         *
         */
        private boolean detectedAndReplacedTasks() {
            return detectedAndReplacedTasks;
        }
        
        /**
         * @return the result
         */
        private RuleApplicationResult getResult() {
            return result;
        }

        /**
         * @return the stopWatch
         */
        private StopWatch getStopWatch() {
            return stopWatch;
        }

    }
    
    /**
     * @author Patrick Harms
     */
    private static class Subsequence implements Iterable<ITask> {
        
        /**
         * 
         */
        private int occurrenceCount;

        /**
         * 
         */
        private List<ITask> subsequence;
        
        /**
         * @param occurrenceCount
         * @param subsequences
         */
        private Subsequence(int occurrenceCount, List<ITask> subsequence) {
            super();
            this.occurrenceCount = occurrenceCount;
            this.subsequence = new ArrayList<ITask>(subsequence);
        }

        /**
         * @return
         */
        private int size() {
            return this.subsequence.size();
        }

        /**
         * @return
         */
        private ITask get(int index) {
            return this.subsequence.get(index);
        }

        /* (non-Javadoc)
         * @see java.lang.Iterable#iterator()
         */
        @Override
        public Iterator<ITask> iterator() {
            return this.subsequence.iterator();
        }

        /* (non-Javadoc)
         * @see java.lang.Object#toString()
         */
        @Override
        public String toString() {
            return subsequence.toString() + " (" + occurrenceCount + ")";
        }
    }

    /**
     * @author Patrick Harms
     */
    private static class Subsequences implements Iterable<Subsequence> {
        
        /**
         * 
         */
        private int occurrenceCount;
        
        /**
         * 
         */
        private LinkedList<Subsequence> subsequences;

        /**
         * @param occurrenceCount
         * @param sequences
         */
        private Subsequences(int occurrenceCount, LinkedList<Subsequence> subsequences) {
            super();
            this.occurrenceCount = occurrenceCount;
            this.subsequences = subsequences;
        }

        /**
         *
         */
        private void remove(Subsequence subsequence) {
            ListIterator<Subsequence> it = subsequences.listIterator();
            
            while (it.hasNext()) {
                // reference comparison is sufficient
                if (it.next() == subsequence) {
                    it.remove();
                }
            }
        }

        /**
         * @return
         */
        private int getOccurrenceCount() {
            return occurrenceCount;
        }

        /**
         * @return
         */
        private int size() {
            return this.subsequences.size();
        }

        /* (non-Javadoc)
         * @see java.lang.Iterable#iterator()
         */
        @Override
        public Iterator<Subsequence> iterator() {
            return this.subsequences.iterator();
        }

        /* (non-Javadoc)
         * @see java.lang.Object#toString()
         */
        @Override
        public String toString() {
            StringBuffer result = new StringBuffer();
            result.append(" subsequences occuring ");
            result.append(this.occurrenceCount);
            result.append(" times:\n");
            
            for (Subsequence subsequence : subsequences) {
                result.append(subsequence);
                result.append("\n");
            }
            
            return result.toString();
        }
    }
    
    /**
     * @author Patrick Harms
     */
    private static class InterleavingSubsequence {
        
        /** */
        private Subsequence subsequence;
        
        /** */
        private List<Collision> successorCollisions;
        
        /** */
        private List<Collision> predecessorCollisions;

        /**
         *
         */
        private InterleavingSubsequence(Subsequence     subsequence,
                                        List<Collision> predecessorCollisions,
                                        List<Collision> successorCollisions)
        {
            super();
            this.subsequence = subsequence;
            this.predecessorCollisions = predecessorCollisions;
            this.successorCollisions = successorCollisions;
        }

        /**
         *
         */
        private int getCollisionCounter() {
            return getSuccessorCollisionCounter() + getPredecessorCollisionCounter();
        }

        /**
         *
         */
        private int getSuccessorCollisionCounter() {
            return successorCollisions.size();
        }

        /**
         *
         */
        private List<Collision> getSuccessorCollisions() {
            return successorCollisions;
        }

        /**
         *
         */
        private int getPredecessorCollisionCounter() {
            return predecessorCollisions.size();
        }

        /**
         *
         */
        private List<Collision> getPredecessorCollisions() {
            return predecessorCollisions;
        }

        /**
         *
         */
        private Subsequence getSubsequence() {
            return subsequence;
        }
        
        /* (non-Javadoc)
         * @see java.lang.Object#toString()
         */
        @Override
        public String toString() {
            return "interleaving subsequence " + subsequence.toString() + " (" +
                successorCollisions.size() + " successor, " + predecessorCollisions.size() +
                " predecessor)";
        }
    }
        
    /**
     * @author Patrick Harms
     */
    private static class SubsequenceLocation {
        
        /** */
        private IUserSession session;
        
        /** */
        private int index;
        
        /**
         * 
         */
        private SubsequenceLocation(IUserSession session, int index) {
            this.session = session;
            this.index = index;
        }

        /**
         * @return the session
         */
        private IUserSession getSession() {
            return session;
        }

        /**
         * @return the index
         */
        private int getIndex() {
            return index;
        }
        
        /* (non-Javadoc)
         * @see java.lang.Object#toString()
         */
        @Override
        public String toString() {
            return "location (" + session + ", " + index + ")";
        }
    }
    
    /**
     * @author Patrick Harms
     */
    private static class Collision {
        
        /** */
        private SubsequenceLocation location;
        
        /** */
        private Subsequence subsequence;
        
        /** */
        private Subsequence collidingWith;
        
        /**
         * 
         */
        private Collision(SubsequenceLocation location,
                          Subsequence         subsequence,
                          Subsequence         collidingWith)
        {
            this.location = location;
            this.subsequence = subsequence;
            this.collidingWith = collidingWith;
        }

        /**
         * @return the collidingWith
         */
        private Subsequence getCollidingWith() {
            return collidingWith;
        }

        /**
         * @return the location
         */
        private SubsequenceLocation getLocation() {
            return location;
        }

        /**
         * @return the subsequence
         */
        private Subsequence getSubsequence() {
            return subsequence;
        }

        /* (non-Javadoc)
         * @see java.lang.Object#toString()
         */
        @Override
        public String toString() {
            return "collision (" + location + " ," + subsequence + ", " + collidingWith + ")";
        }
    }
    
    // methods for internal testing
//    private void checkMatchingOfSessions(List<List<Event>>  flattenedSessions,
//                                         List<IUserSession> sessions,
//                                         String             when)
//    {
//        List<List<Event>> currentFlattenedSessions = flattenSessions(sessions);
//        if (flattenedSessions.size() != currentFlattenedSessions.size()) {
//            System.out.println("################## number of sessions changed after " + when);
//        }
//        else {
//            for (int i = 0; i < flattenedSessions.size(); i++) {
//                List<Event> expected = flattenedSessions.get(i);
//                List<Event> current = currentFlattenedSessions.get(i);
//            
//                if (expected.size() != current.size()) {
//                    System.out.println
//                        ("################## length of session " + i + " changed after " + when);
//                }
//                else {
//                    for (int j = 0; j < expected.size(); j++) {
//                        if (!expected.get(j).equals(current.get(j))) {
//                            System.out.println("################## event " + j + " of session " +
//                                               i + " changed after " + when);
//                        }
//                    }
//                }
//            }     
//        }
//    }
//
//    private List<List<Event>> flattenSessions(List<IUserSession> sessions) {
//        List<List<Event>> flattenedSessions = new ArrayList<List<Event>>();
//        for (IUserSession session : sessions) {
//            List<Event> flattenedUserSession = new ArrayList<Event>();
//            flatten(session, flattenedUserSession);
//            flattenedSessions.add(flattenedUserSession);
//        }
//
//        return flattenedSessions;
//    }
//
//    private void flatten(IUserSession iUserSession, List<Event> flattenedUserSession) {
//        for (ITaskInstance instance : iUserSession) {
//            flatten(instance, flattenedUserSession);
//        }
//    }
//
//    private void flatten(ITaskInstance instance, List<Event> flattenedUserSession) {
//        if (instance instanceof ITaskInstanceList) {
//            for (ITaskInstance child : (ITaskInstanceList) instance) {
//                flatten(child, flattenedUserSession);
//            }
//        }
//        else if (instance instanceof ISelectionInstance) {
//            flatten(((ISelectionInstance) instance).getChild(), flattenedUserSession);
//        }
//        else if (instance instanceof IOptionalInstance) {
//            flatten(((IOptionalInstance) instance).getChild(), flattenedUserSession);
//        }
//        else if (instance instanceof IEventTaskInstance) {
//            flattenedUserSession.add(((IEventTaskInstance) instance).getEvent());
//        }
//    }

}