source: branches/autoquest-core-tasktrees-alignment/src/main/java/de/ugoe/cs/autoquest/tasktrees/temporalrelation/SequenceForTaskDetectionRuleAlignment.java @ 1749

//   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.io.Serializable;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Set;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.TimeUnit;
import java.util.logging.Level;

import de.ugoe.cs.autoquest.tasktrees.alignment.algorithms.AlignmentAlgorithm;
import de.ugoe.cs.autoquest.tasktrees.alignment.algorithms.AlignmentAlgorithmFactory;
import de.ugoe.cs.autoquest.tasktrees.alignment.algorithms.Match;
import de.ugoe.cs.autoquest.tasktrees.alignment.algorithms.MatchOccurrence;
import de.ugoe.cs.autoquest.tasktrees.alignment.algorithms.NumberSequence;
import de.ugoe.cs.autoquest.tasktrees.alignment.matrix.ObjectDistanceSubstitionMatrix;
import de.ugoe.cs.autoquest.tasktrees.taskequality.TaskEquality;
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.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.IUserSession;
import de.ugoe.cs.autoquest.usageprofiles.SymbolMap;
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
 * using alignment algorithms 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>
 * 
 * 
 * @author Ralph Krimmel
 */
public class SequenceForTaskDetectionRuleAlignment implements ISessionScopeRule {

    /** The n threads. */
    public static int nThreads = Runtime.getRuntime().availableProcessors() - 1;
    //public static int nThreads = 1;

    /** The iteration. */
    private int iteration = 0;

    private int maxIterations = 10
            ;

    private static int alignmentThreshold = 9;
    private static int gapPenalty = -3;

    private static float maxSubstitutionScore = 6;

    /**
     * <p>
     * the task factory to be used for creating substructures for the temporal relationships
     * identified during rul application
     * </p>
     * .
     */
    private final ITaskFactory taskFactory;

    /**
     * <p>
     * the task builder to be used for creating substructures for the temporal relationships
     * identified during rule application
     * </p>
     * .
     */
    private final ITaskBuilder taskBuilder;

    /**
     * <p>
     * the task handling strategy to be used for comparing tasks for preparation, i.e., before the
     * tasks are harmonized
     * </p>
     */
    private final TaskHandlingStrategy preparationTaskHandlingStrategy;

    /**
     * <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
     */

    SequenceForTaskDetectionRuleAlignment(TaskEquality minimalTaskEquality,
                                          ITaskFactory taskFactory,
                                          ITaskBuilder taskBuilder)
    {
        this.taskFactory = taskFactory;
        this.taskBuilder = taskBuilder;

        this.preparationTaskHandlingStrategy = new TaskHandlingStrategy(minimalTaskEquality);
    }

    /*
     * (non-Javadoc)
     * 
     * @see de.ugoe.cs.autoquest.tasktrees.temporalrelation.ISessionScopeRule#apply (java.util.List)
     */
    @Override
    public RuleApplicationResult apply(List<IUserSession> sessions) {
        final RuleApplicationData appData = new RuleApplicationData(sessions);

        harmonizeEventTaskInstancesModel(appData);

        Console.traceln(Level.INFO, "generating substitution matrix from " +
            appData.getNumber2Task().size() + " unique tasks");
        appData.getStopWatch().start("substitution matrix");
        appData.getSubmat().generate(appData.getNumber2Task().values());
        appData.getStopWatch().stop("substitution matrix");

        Console.traceln(Level.INFO, "Starting main loop");
        do {
            Console.traceln(Level.INFO, "Iteration Number: " + iteration);
            iteration++;
            appData.detectedAndReplacedTasks = false;
            appData.getStopWatch().start("whole loop");
            detectAndReplaceIterations(appData);
            appData.getStopWatch().start("task replacement");
            // Just does anything if the substitution matrix is created with the
            // option to do so
            appData.updateSubstitutionMatrix();
            detectAndReplaceTasks(appData); //
            appData.getStopWatch().stop("task replacement");
            appData.getStopWatch().stop("whole loop");
            // appData.getStopWatch().dumpStatistics(System.out);
            appData.getStopWatch().reset();

            // } while (appData.detectedAndReplacedTasks()||iteration < maxIterations);
        }
        while (iteration < maxIterations);
        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);
        }
        // new TaskTreeValidator().validate(appData.getSessions());
        return appData.getResult();
    }

    /**
     * Creates the number sequences.
     *
     * @param appData
     *            the app data
     * @return the array list
     */
    private ArrayList<NumberSequence> createNumberSequences(RuleApplicationData appData) {
        final ArrayList<NumberSequence> result = new ArrayList<NumberSequence>();
        for (int i = 0; i < appData.getSessions().size(); i++) {
            final IUserSession session = appData.getSessions().get(i);
            final NumberSequence templist = new NumberSequence(session.size());
            for (int j = 0; j < session.size(); j++) {
                final ITaskInstance taskInstance = session.get(j);
                templist.getSequence()[j] = taskInstance.getTask().getId();
            }
            // Each NumberSequence is identified by its id, beginning to count
            // at zero
            templist.setId(i);
            result.add(templist);
        }
        return result;
    }

    /**
     * <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");

        final List<IUserSession> sessions = appData.getSessions();

        final 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");
    }

    /**
     * Detect and replace tasks.
     *
     * @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");

        // Create NumberSequences
        appData.setNumberSequences(this.createNumberSequences(appData));

        // Generate pairwise alignments
        // appData.setMatchseqs(generatePairwiseAlignments(appData));
        generatePairwiseAlignments(appData);
        Console.traceln(Level.FINE, "Found " + appData.getMatchseqs().size() + " results");

        // Nothing found, we can end here
        if (appData.getMatchseqs().size() == 0) {
            appData.detectedAndReplacedTasks = false;
            return;
        }

        // Searching each match in all other sessions, counting its occurences
        searchMatchesInAllSessions(appData);

        // Sort results to get the most occurring results
        Console.traceln(Level.INFO, "sorting " + appData.getMatchseqs().size() + " results");
        final Comparator<Match> comparator = new Comparator<Match>() {
            @Override
            public int compare(Match m1, Match m2) {
                int cmp = m2.occurenceCount() - m1.occurenceCount();
                if (cmp != 0) {
                    return cmp;
                }
                else {
                    cmp = m2.size() - m1.size();
                    if (cmp != 0) {
                        return cmp;
                    }
                    else {
                        // This should rarely happen
                        cmp = m2.ocurrenceIDSum() - m1.ocurrenceIDSum();
                        if (cmp != 0) {
                            return cmp;
                        }
                        else {
                            cmp = m2.taskIdSum() - m1.taskIdSum();

                            return cmp;
                        }
                    }
                }
            }
        };

        Collections.sort(appData.getMatchseqs(), comparator);
        appData.getStopWatch().stop("detecting tasks");

        Console.traceln(Level.INFO, "Preparing replacments");
        prepareReplacements(appData);
        Console.traceln(Level.INFO, "Replacing matches in sessions");
        appData.getStopWatch().start("replacing tasks");
        replaceMatches(appData);
        appData.getStopWatch().stop("replacing tasks");
    }

    // TODO: DEBUG METHOD
    @SuppressWarnings("unused")
    private void printMatches(RuleApplicationData appData) {
        LinkedList<Match> matchseqs = appData.getMatchseqs();
        if (iteration > 1) {
            System.out.println("PRINTING MATCHES");
            for (Iterator<Match> it = matchseqs.iterator(); it.hasNext();) {
                Match m = it.next();
                m.getFirstSequence().printSequence();
                m.getSecondSequence().printSequence();
                for (Iterator<MatchOccurrence> jt = m.getOccurences().iterator(); jt.hasNext();) {
                    MatchOccurrence mo = jt.next();
                    System.out.print(mo.getSequenceId() + " ");
                }
                System.out.println();
                System.out.println();
            }
        }
    }

    /**
     * <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
     * @return Returns the unique tasks symbol map
     */
    private void harmonizeEventTaskInstancesModel(RuleApplicationData appData) {
        Console.traceln(Level.INFO, "harmonizing task model of event task instances");
        appData.getStopWatch().start("harmonizing event tasks");
        final SymbolMap<ITaskInstance, ITask> uniqueTasks =
            preparationTaskHandlingStrategy.createSymbolMap();

        final TaskInstanceComparator comparator =
            preparationTaskHandlingStrategy.getTaskComparator();

        int unifiedTasks = 0;
        ITask task;
        final List<IUserSession> sessions = appData.getSessions();
        for (int j = 0; j < sessions.size(); j++) {
            final IUserSession session = sessions.get(j);

            for (int i = 0; i < session.size(); i++) {
                final ITaskInstance taskInstance = session.get(i);
                task = uniqueTasks.getValue(taskInstance);

                if (task == null) {
                    uniqueTasks.addSymbol(taskInstance, taskInstance.getTask());
                    appData.getNumber2Task().put(taskInstance.getTask().getId(),
                                                 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>
     * TODO clarify why this is done (in fact, ask Patrick Harms)
     * </p>
     * .
     *
     * @param iteration
     *            the iteration
     * @param iterationInstances
     *            the iteration instances
     */
    private void harmonizeIterationInstancesModel(IIteration iteration,
                                                  List<IIterationInstance> iterationInstances)
    {
        final List<ITask> iteratedTaskVariants = new LinkedList<ITask>();
        final TaskInstanceComparator comparator =
            preparationTaskHandlingStrategy.getTaskComparator();

        // merge the lexically different variants of iterated task to a unique
        // list
        for (final IIterationInstance iterationInstance : iterationInstances) {
            for (final ITaskInstance executionVariant : iterationInstance) {
                final ITask candidate = executionVariant.getTask();

                boolean found = false;
                for (final 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) {
            final ISelection selection = taskFactory.createNewSelection();

            for (final ITask variant : iteratedTaskVariants) {
                taskBuilder.addChild(selection, variant);
            }

            taskBuilder.setMarkedTask(iteration, selection);

            for (final IIterationInstance instance : iterationInstances) {
                for (int i = 0; i < instance.size(); i++) {
                    final ISelectionInstance selectionInstance =
                        taskFactory.createNewTaskInstance(selection);
                    taskBuilder.setChild(selectionInstance, instance.get(i));
                    taskBuilder.setTaskInstance(instance, i, selectionInstance);
                }
            }
        }
        else {
            taskBuilder.setMarkedTask(iteration, iteratedTaskVariants.get(0));
        }
    }

    /**
     * Match as sequence.
     *
     * @param appData
     *            RuleApplicationData needed to keep track of all created tasks
     * @param m
     *            The match to be converted into a Task
     * @return The task of the match with an ISequence as its root
     */
    synchronized public ISequence matchAsSequence(RuleApplicationData appData, Match m) {
        final ISequence sequence = taskFactory.createNewSequence();
        appData.newTaskCreated(sequence);

        final int[] first = m.getFirstSequence().getSequence();
        final int[] second = m.getSecondSequence().getSequence();

        // Both sequences of a match are equally long
        for (int i = 0; i < m.getFirstSequence().size(); i++) {

            // Two gaps aligned to each other: Have not seen it happening so
            // far, just to handle it
            if ((first[i] == -1) && (second[i] == -1)) {
                // Do nothing here.
            }
            // Both events are equal, we can simply add the task referring to
            // the number
            else if (first[i] == second[i]) {
                taskBuilder.addChild(sequence, appData.getNumber2Task().get(first[i]));
            }
            // We have a gap in the first sequence, we need to add the task of
            // the second sequence as optional
            else if ((first[i] == -1) && (second[i] != -1)) {
                final IOptional optional = taskFactory.createNewOptional();
                appData.newTaskCreated(optional);
                taskBuilder.setMarkedTask(optional, appData.getNumber2Task().get(second[i]));
                taskBuilder.addChild(sequence, optional);
            }
            // We have a gap in the second sequence, we need to add the task of
            // the first sequence as optional
            else if ((first[i] != -1) && (second[i] == -1)) {
                final IOptional optional = taskFactory.createNewOptional();
                appData.newTaskCreated(optional);
                taskBuilder.setMarkedTask(optional, appData.getNumber2Task().get(first[i]));
                taskBuilder.addChild(sequence, optional);
            }
            // Both tasks are not equal, we need to insert a selection here.
            // Now things get complicated. We first need to check
            // if the next position is not a selection. Then we can just create
            // a selection
            // of the both Tasks
            // In the other case (more than one selection following this
            // selection), we want to
            // create a selection of sequences where each sequence gets the
            // corresponding task of
            // the its sequence in the pattern.
            //
            else if (i < (first.length - 1)) {

                if ((first[i] != second[i]) &&
                    (((first[i + 1] == second[i + 1]) || (first[i + 1] == -1) || (second[i + 1] == -1))))
                {

                    final ISelection selection = taskFactory.createNewSelection();
                    appData.newTaskCreated(selection);
                    taskBuilder.addChild(selection, appData.getNumber2Task().get(first[i]));
                    taskBuilder.addChild(selection, appData.getNumber2Task().get(second[i]));
                    taskBuilder.addChild(sequence, selection);
                }
                else {
                    boolean selectionfound = true;
                    final ISelection selection = taskFactory.createNewSelection();
                    appData.newTaskCreated(selection);

                    final ISequence subsequence1 = taskFactory.createNewSequence();
                    appData.newTaskCreated(subsequence1);

                    final ISequence subsequence2 = taskFactory.createNewSequence();
                    appData.newTaskCreated(subsequence2);

                    taskBuilder.addChild(selection, subsequence1);
                    taskBuilder.addChild(selection, subsequence2);
                    taskBuilder.addChild(sequence, selection);
                    // TODO: We may not run till the end!
                    while ((i < (first.length - 1)) && selectionfound) {
                        selectionfound = false;
                        taskBuilder.addChild(subsequence1, appData.getNumber2Task().get(first[i]));
                        taskBuilder.addChild(subsequence2, appData.getNumber2Task().get(second[i]));
                        if ((first[i + 1] != second[i + 1]) && (first[i + 1] != -1) &&
                            (second[i + 1] != -1))
                        {
                            selectionfound = true;
                        }
                        else {
                            continue;
                        }
                        i++;
                    }
                    if ((i == (first.length - 1)) && selectionfound) {
                        taskBuilder.addChild(subsequence1, appData.getNumber2Task().get(first[i]));
                        taskBuilder.addChild(subsequence2, appData.getNumber2Task().get(second[i]));
                    }
                }
            }
            else {
                // i = length-1
                if ((first[i] != second[i])) {

                    final ISelection selection = taskFactory.createNewSelection();
                    appData.newTaskCreated(selection);
                    taskBuilder.addChild(selection, appData.getNumber2Task().get(first[i]));
                    taskBuilder.addChild(selection, appData.getNumber2Task().get(second[i]));
                    taskBuilder.addChild(sequence, selection);
                }
            }

        }
        return sequence;
    }

    /**
     * <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)
    {
        final Map<ITask, IIteration> iterations = new HashMap<ITask, IIteration>();
        final Map<IIteration, List<IIterationInstance>> iterationInstances =
            new HashMap<IIteration, List<IIterationInstance>>();

        for (final ITask iteratedTask : iteratedTasks) {

            final IIteration iteration = taskFactory.createNewIteration();
            appData.newTaskCreated(iteration);
            iterations.put(iteratedTask, iteration);
            iterationInstances.put(iteration, new LinkedList<IIterationInstance>());
        }

        IIterationInstance iterationInstance;

        for (final IUserSession session : sessions) {
            int index = 0;
            iterationInstance = null;

            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
                final ITask currentTask = session.get(index).getTask();
                final IIteration iteration = iterations.get(currentTask);
                if (iteration != null) {
                    if ((iterationInstance == null) || (iterationInstance.getTask() != iteration)) {
                        iterationInstance = taskFactory.createNewTaskInstance(iteration);
                        iterationInstances.get(iteration).add(iterationInstance);// TODO:: Don't
                                                                                 // create
                        // TaskInstances here,
                        // use a set of tasks
                        // instead
                        taskBuilder.addTaskInstance(session, index, iterationInstance);
                        index++;
                    }

                    taskBuilder.addChild(iterationInstance, session.get(index));
                    taskBuilder.removeTaskInstance(session, index);
                }
                else {
                    if (iterationInstance != null) {
                        iterationInstance = null;
                    }
                    index++;
                }
            }
        }

        for (final Map.Entry<IIteration, List<IIterationInstance>> entry : iterationInstances
            .entrySet())
        {
            harmonizeIterationInstancesModel(entry.getKey(), entry.getValue());
        }
    }

    /**
     * Prepare replacements.
     *
     * @param appData
     *            the app data
     */
    private void prepareReplacements(RuleApplicationData appData) {
        appData.initializeQueues(appData.getSessions().size());
        int taskId=0;
        for (Iterator<Match> it = appData.getMatchseqs().iterator(); it.hasNext();) {
            Match m = it.next();
            if (m.getOccurences().size() > 2) {
                final ISequence task = matchAsSequence(appData, m);
                appData.getPreparedTasks().add(task);
                
                for (Iterator<MatchOccurrence> jt = m.getOccurences().iterator(); jt.hasNext();) {
                    MatchOccurrence mo = jt.next();
                    // System.out.println("Found this match in sequence " +mo.getSequenceId());
                    PlannedReplacement pr = new PlannedReplacement(taskId,mo);
                    // System.out.println("Adding match to sequence " + mo.getSequenceId());
                    appData.getPlannedReplacements()[mo.getSequenceId()].add(pr);
                }
                taskId++;
            }
        }
    }

    /**
     * Replace matches.
     *
     * @param appData
     *            the app data
     */
    private void replaceMatches(RuleApplicationData appData) {

        final int numberSeqSize = appData.getNumberSequences().size();
        Console.traceln(Level.INFO, "replacing matches with " + nThreads + " threads");
        int newThreads = nThreads;
        if (numberSeqSize < nThreads) {
            newThreads = numberSeqSize;
        }
        final int interval = numberSeqSize / newThreads;
        int rest = numberSeqSize % newThreads;
        final ExecutorService executor = Executors.newFixedThreadPool(nThreads);
        for (int i = 0; i <= (numberSeqSize - interval); i += interval) {
            int offset = 0;
            if (rest != 0) {
                offset = 1;
                rest--;
            }
            final int from = i;
            final int to = i + interval + offset - 1;
            Console.traceln(Level.FINE, "Match replacing: Creating thread with matches from " +
                from + " to " + to);
            // search each match in every other sequence
            final ParallelMatchReplacer replacer = new ParallelMatchReplacer(appData, from, to);
            executor.execute(replacer);
            i += offset;
        }
        executor.shutdown();
        try {
            executor.awaitTermination(2, TimeUnit.HOURS);
        }
        catch (final InterruptedException e) {
            e.printStackTrace();
        }
        appData.getPreparedTasks().clear();
    }

    /**
     * <p>
     * searches the provided sessions for task iterations. If a task is iterated, it is added to the
     * returned set.
     * </p>
     *
     * @param sessions
     *            the sessions
     * @return a set of tasks being iterated somewhere
     */
    private Set<ITask> searchIteratedTasks(List<IUserSession> sessions) {
        final Set<ITask> iteratedTasks = new HashSet<ITask>();
        for (final 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;
    }

    /**
     * Generate pairwise alignments.
     *
     * @param appData
     *            the app data
     */
    private void generatePairwiseAlignments(RuleApplicationData appData) {
        final int numberSeqSize = appData.getNumberSequences().size();
        appData.matchseqs = new LinkedList<Match>();
        Console.traceln(Level.INFO, "generating pairwise alignments from " + numberSeqSize +
            " sessions with " + nThreads + " threads");

        int newThreads = nThreads;
        if (numberSeqSize < nThreads) {
            newThreads = numberSeqSize;
        }

        final ExecutorService executor = Executors.newFixedThreadPool(newThreads);
        final int interval = numberSeqSize / newThreads;
        int rest = numberSeqSize % newThreads;
        Console.traceln(Level.FINE, "Interval: " + interval + " Rest: " + rest);
        for (int i = 0; i <= (numberSeqSize - interval); i += interval) {
            int offset = 0;
            if (rest != 0) {
                offset = 1;
                rest--;
            }

            final int from = i;
            final int to = i + interval + offset - 1;
            Console.traceln(Level.FINER, "Aligning: Creating thread for sessions " + from +
                " till " + to);
            final ParallelPairwiseAligner aligner = new ParallelPairwiseAligner(appData, from, to);
            executor.execute(aligner);
            i += offset;
        }
        executor.shutdown();
        try {
            executor.awaitTermination(2, TimeUnit.HOURS);
        }
        catch (final InterruptedException e) {
            e.printStackTrace();
        }
    }

    /**
     * Search matches in all sessions.
     *
     * @param appData
     *            the app data
     */
    private void searchMatchesInAllSessions(RuleApplicationData appData) {

        // Prepare parallel search of matchseqs
        final int matchSeqSize = appData.getMatchseqs().size();
        Console.traceln(Level.INFO, "searching for patterns (" + matchSeqSize +
            ") occuring most with " + nThreads + " threads");
        int newThreads = nThreads;
        if (matchSeqSize < nThreads) {
            newThreads = matchSeqSize;
        }
        final int interval = matchSeqSize / newThreads;
        int rest = matchSeqSize % newThreads;
        final ExecutorService executor = Executors.newFixedThreadPool(nThreads);
        Console.traceln(Level.FINER, "Interval: " + interval + " Rest: " + rest);
        for (int i = 0; i <= (matchSeqSize - interval); i += interval) {
            int offset = 0;
            if (rest != 0) {
                offset = 1;
                rest--;
            }
            final int from = i;
            final int to = i + interval + offset - 1;
            Console.traceln(Level.FINE, "Match finding: Creating thread with matches from " + from +
                " to " + to);
            // search each match in every other sequence
            final ParallelMatchOcurrencesFinder finder =
                new ParallelMatchOcurrencesFinder(appData, from, to);
            executor.execute(finder);
            i += offset;
        }
        executor.shutdown();
        try {
            executor.awaitTermination(2, TimeUnit.HOURS);
        }
        catch (final InterruptedException e) {
            e.printStackTrace();
        }

    }

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

    /**
     * The Class ParallelMatchOcurrencesFinder.
     */
    private class ParallelMatchOcurrencesFinder implements Runnable {

        /** The app data. */
        private final RuleApplicationData appData;

        /** The from. */
        private final int from;

        /** The to. */
        private final int to;

        /**
         * Instantiates a new parallel match ocurrences finder.
         *
         * @param appData
         *            the app data
         * @param from
         *            the from
         * @param to
         *            the to
         */
        ParallelMatchOcurrencesFinder(RuleApplicationData appData, int from, int to) {
            this.appData = appData;
            this.from = from;
            this.to = to;
        }

        /*
         * (non-Javadoc)
         * 
         * @see java.lang.Runnable#run()
         */
        @Override
        public void run() {
            int count = 0;
            final int size = to + 1 - from;

            for (int i = from; i <= to; i++) {
                final Match pattern = appData.getMatchseqs().get(i);
                count++;
                RuleUtils.printProgressPercentage("Match finding progress", count, size);
                // Skip sequences with more 0 events (scrolls) than other
                // events.
                // Both of the pattern sequences are equally long, so the zero
                // counts just need to be smaller than the length of one
                // sequence
                if ((pattern.getFirstSequence().eventCount(0) +
                    pattern.getSecondSequence().eventCount(0) + 1) > pattern.getFirstSequence()
                    .size())
                {
                    continue;
                }

                for (int j = 0; j < appData.getNumberSequences().size(); j++) {
                    final LinkedList<Integer> startpositions =
                        appData.getNumberSequences().get(j).containsPattern(pattern);
                    if (startpositions.size() > 0) {
                        for (final Iterator<Integer> jt = startpositions.iterator(); jt.hasNext();)
                        {
                            final int start = jt.next();
                            pattern.addOccurence(new MatchOccurrence(start, start + pattern.size(),
                                                                     j));
                        }
                    }
                }
            }
        }
    }

    /**
     * The Class ParallelPairwiseAligner.
     */
    private class ParallelPairwiseAligner implements Runnable {

        /** The app data. */
        private final RuleApplicationData appData;

        /** The from. */
        private final int from;

        /** The to. */
        private final int to;

        /**
         * Instantiates a new parallel pairwise aligner.
         *
         * @param appData
         *            the app data
         * @param from
         *            the from
         * @param to
         *            the to
         */
        ParallelPairwiseAligner(RuleApplicationData appData, int from, int to) {
            this.appData = appData;
            this.from = from;
            this.to = to;
        }

        /*
         * (non-Javadoc)
         * 
         * @see java.lang.Runnable#run()
         */
        @Override
        public void run() {
            int count = 0;
            final int size = to + 1 - from;

            for (int i = from; i <= to; i++) {
                final NumberSequence ns1 = appData.getNumberSequences().get(i);
                count++;
                RuleUtils.printProgressPercentage("Aligning Progress", count, size);
                for (int j = 0; j < appData.getNumberSequences().size(); j++) {
                    final NumberSequence ns2 = appData.getNumberSequences().get(j);
                    if (i != j) {
                        final AlignmentAlgorithm aa = AlignmentAlgorithmFactory.create();
                        // threshold was 9
                        aa.align(ns1, ns2, appData.getSubmat(),
                                 SequenceForTaskDetectionRuleAlignment.alignmentThreshold);
                        synchronized (appData.getMatchseqs()) {
                            appData.getMatchseqs().addAll(aa.getMatches());
                        }
                    }
                }
            }
        }
    }

    /**
     * The Class ParallelPairwiseAligner.
     */
    private class ParallelMatchReplacer implements Runnable {

        /** The app data. */
        private final RuleApplicationData appData;

        /** The from. */
        private final int from;

        /** The to. */
        private final int to;

        /**
         * Instantiates a new parallel pairwise aligner.
         *
         * @param appData
         *            the app data
         * @param from
         *            the from
         * @param to
         *            the to
         */
        ParallelMatchReplacer(RuleApplicationData appData, int from, int to) {
            this.appData = appData;
            this.from = from;
            this.to = to;
        }

        /*
         * (non-Javadoc)
         * 
         * @see java.lang.Runnable#run()
         */
        @Override
        public void run() {
            for (int i = from; i <= to; i++) {
                //System.out.println("Replacing in SEQUENCE " + i);
                /*
                 * HashMap for keeping track in which sequence which replacement has been performed.
                 * Neccessary for updating the indices of other occurrences accordingly
                 */
                LinkedList<MatchOccurrence> replacedOccurrences = new LinkedList<MatchOccurrence>();
                invalidOccurence: while (!appData.getPlannedReplacements()[i].isEmpty()) {

                    PlannedReplacement pr = appData.getPlannedReplacements()[i].remove();
                    
                    MatchOccurrence oc = pr.getOccurrence();
                    // check if we have any replaced occurrence with
                    // indexes
                    // smaller than ours. If so, we need to adjust
                    // our start and end points of the replacement.
                    // Also do a check if we have replaced this
                    // specific MatchOccurence in this sequence already.
                    // Jump to the next occurrence if this is the case.
                    // This is no more necessary once the matches
                    // are harmonized.

                    for (final Iterator<MatchOccurrence> jt = replacedOccurrences.iterator(); jt
                        .hasNext();)
                    {
                        final MatchOccurrence tmpOC = jt.next();

                        if ((oc.getStartindex() >= tmpOC.getStartindex()) &&
                            (oc.getStartindex() <= tmpOC.getEndindex()))
                        {
                            continue invalidOccurence;
                        }
                        if (oc.getEndindex() >= tmpOC.getStartindex()) {
                            continue invalidOccurence;

                        }
                        else if (oc.getStartindex() > tmpOC.getEndindex()) {
                            final int diff = tmpOC.getEndindex() - tmpOC.getStartindex();
                            // Just to be sure.
                            if (diff > 0) {
                                oc.setStartindex((oc.getStartindex() - diff) + 1);
                                oc.setEndindex((oc.getEndindex() - diff) + 1);
                            }
                            else {
                                Console
                                    .traceln(Level.WARNING,
                                             "End index of a Match before start. This should never happen");
                            }
                        }
                    }
                    synchronized (appData) {
                        appData.detectedAndReplacedTasks = true;
                    }
                   

                    //System.out.println("Replacing in Sequence " + oc.getSequenceId() +
                    //    " at position " + oc.getStartindex() + " till " + oc.getEndindex());
                    final ISequenceInstance sequenceInstances =
                        RuleUtils.createNewSubSequenceInRange(appData.getSessions()
                                                                  .get(oc.getSequenceId()), oc
                                                                  .getStartindex(), oc
                                                                  .getEndindex(), (ISequence) appData.getPreparedTasks().get(pr.getMatchId()),
                                                              taskFactory, taskBuilder);

                    // Adjust the length of the match regarding to the
                    // length of
                    // instance. (OptionalInstances may be shorter)
                    oc.setEndindex((oc.getStartindex() + sequenceInstances.size()) -
                        RuleUtils.missedOptionals);

                    replacedOccurrences.add(oc);

                }
            }
        }
    }
    
    private static class PlannedReplacement {
        private int matchId;
        private int getMatchId() {
            return matchId;
        }

        private MatchOccurrence getOccurrence() {
            return occurrence;
        }

        private MatchOccurrence occurrence;
        
        private PlannedReplacement(int matchId,MatchOccurrence occurrence) {
            this.matchId = matchId;
            this.occurrence = occurrence;
        }
    }

    /**
     * The Class RuleApplicationData.
     */
    private static class RuleApplicationData implements Serializable {

        /** The Constant serialVersionUID. */
        private static final long serialVersionUID = -7559657686755522960L;

        /**
         * The number2task HashMap. Since we align the tasks just by their integer id, we need this
         * to convert them back to Tasks again
         */
        private final HashMap<Integer, ITask> number2task;


        /**
         * The substitution matrix used by the alignment algorithm to be able to compare distances
         * of tasks
         */
        private final ObjectDistanceSubstitionMatrix submat;

        private LinkedList<PlannedReplacement>[] plannedReplacements;

        /** The list of all found matches */
        private LinkedList<Match> matchseqs;
        
        private ArrayList<ITask> preparedTasks;

        public ArrayList<ITask> getPreparedTasks() {
            return preparedTasks;
        }

        /**
         * The generated NumberSequences. This is the integer representation of the user sessions
         */
        private ArrayList<NumberSequence> numberseqs;

        /** The list of newly created tasks (of one iteration). */
        private final LinkedList<ITask> newTasks;

        /** The user sessions containing all EventTasks/Instances */
        private final List<IUserSession> sessions;

        /** True if we replaced something in the user sessions in one iteration. */
        private boolean detectedAndReplacedTasks;

        /** The result we return from this rule */
        private final RuleApplicationResult result;

        /** Stop Watch to measure performance */
        private final StopWatch stopWatch;

        /**
         * Instantiates a new rule application data.
         *
         * @param sessions
         *            The user sessions
         */
        private RuleApplicationData(List<IUserSession> sessions) {
            this.sessions = sessions;
            numberseqs = new ArrayList<NumberSequence>();
            number2task = new HashMap<Integer, ITask>();
            stopWatch = new StopWatch();
            result = new RuleApplicationResult();
            preparedTasks = new ArrayList<ITask>();
            submat = new ObjectDistanceSubstitionMatrix(maxSubstitutionScore, gapPenalty, false);
            newTasks = new LinkedList<ITask>();
            this.detectedAndReplacedTasks = true;
        }

        private void initializeQueues(int size) {
            plannedReplacements = new LinkedList[size];
            for (int i = 0; i < size; i++) {
                plannedReplacements[i] = new LinkedList<PlannedReplacement>();
            }
        }

        public Queue<PlannedReplacement>[] getPlannedReplacements() {
            return plannedReplacements;
        }

        /**
         * Detected and replaced tasks.
         *
         * @return true, if successful
         */
        private boolean detectedAndReplacedTasks() {
            return detectedAndReplacedTasks;
        }

        /**
         * Gets the match sequences.
         *
         * @return the match sequences
         */
        public LinkedList<Match> getMatchseqs() {
            return matchseqs;
        }

        /**
         * Gets the new tasks.
         *
         * @return the new tasks
         */
        public LinkedList<ITask> getNewTasks() {
            return newTasks;
        }

        /**
         * Gets the number2task.
         *
         * @return the number2task HashMap
         */
        private HashMap<Integer, ITask> getNumber2Task() {
            return number2task;
        }

        /**
         * Gets the number sequences.
         *
         * @return the number sequences
         */
        private ArrayList<NumberSequence> getNumberSequences() {
            return numberseqs;
        }

        /**
         * Gets the result.
         *
         * @return the result
         */
        private RuleApplicationResult getResult() {
            return result;
        }

        /**
         * Gets the sessions.
         *
         * @return the UserSessions as List.
         */
        private List<IUserSession> getSessions() {
            return sessions;
        }

        /**
         * Gets the stop watch.
         *
         * @return the stopWatch
         */
        private StopWatch getStopWatch() {
            return stopWatch;
        }

        /**
         * Gets the substitution matrix.
         *
         * @return the substitution matrix
         */
        private ObjectDistanceSubstitionMatrix getSubmat() {
            return submat;
        }

        /**
         * New task created.
         *
         * @param task
         *            can be called when new tasks are created to keep track of all newly created
         *            tasks
         */
        private void newTaskCreated(ITask task) {
            number2task.put(task.getId(), task);
            newTasks.add(task);
        }

        /**
         * Reset newly created tasks.
         */
        synchronized private void resetNewlyCreatedTasks() {
            newTasks.clear();
        }

        /**
         * Sets the number sequences.
         *
         * @param numberseqs
         *            the new number sequences
         */
        private void setNumberSequences(ArrayList<NumberSequence> numberseqs) {
            this.numberseqs = numberseqs;
        }

        /**
         * Update substitution matrix.
         */
        private void updateSubstitutionMatrix() {
            submat.update(getNewTasks());
            resetNewlyCreatedTasks();
        }

    }

}