//   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.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.MatchOccurence;
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 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 unique tasks, keeps track about all unique tasks 
		 * TODO: We Actually just need number2task here, this structure can be
		 * removed in the future.*/
		private final HashSet<ITask> uniqueTasks;

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

		/** HashMap for keeping track in which sequence which replacement has been performed.
		 *  Neccessary for updating the indices of other occurrences accordingly */
		public HashMap<Integer, List<MatchOccurence>> replacedOccurences;

		/** The list of all found matches */
		public LinkedList<Match> matchseqs;

		/** 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 give autoquest back */
		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>();
			uniqueTasks = new HashSet<ITask>();
			number2task = new HashMap<Integer, ITask>();
			stopWatch = new StopWatch();
			result = new RuleApplicationResult();
			submat = new ObjectDistanceSubstitionMatrix(6, -3, false);
			newTasks = new LinkedList<ITask>();
			this.detectedAndReplacedTasks = true;
		}

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

		/**
		 * Gets the matchseqs.
		 *
		 * @return the matchseqs
		 */
		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 replaced occurrences.
		 *
		 * @return the replaced occurences
		 */
		public HashMap<Integer, List<MatchOccurence>> getReplacedOccurrences() {
			return replacedOccurences;
		}

		/**
		 * 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 submat.
		 *
		 * @return the submat
		 */
		private ObjectDistanceSubstitionMatrix getSubmat() {
			return submat;
		}

		/**
		 * Gets the unique tasks.
		 *
		 * @return the unique tasks
		 */
		private HashSet<ITask> getUniqueTasks() {
			return uniqueTasks;
		}

		/**
		 * New task created.
		 *
		 * @param task the task
		 */
		private void newTaskCreated(ITask task) {
			number2task.put(task.getId(), task);
			newTasks.add(task);
		}

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

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

		/**
		 * Sets the replaced occurences.
		 *
		 * @param replacedOccurences the replaced occurences
		 */
		public void setReplacedOccurences(
				HashMap<Integer, List<MatchOccurence>> replacedOccurences) {
			this.replacedOccurences = replacedOccurences;
		}

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

	}

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

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

	/** <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.getUniqueTasks().size() + " unique tasks");
		appData.getStopWatch().start("substitution matrix");
		appData.getSubmat().generate(appData.getUniqueTasks());
		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");
			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());

		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();
	}

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

		// 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) {
				return m2.occurenceCount() - m1.occurenceCount();

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

		// Replace matches in the sessions
		Console.traceln(Level.INFO, "Replacing matches in sessions");
		appData.getStopWatch().start("replacing tasks");
		replaceMatches(appData);
		appData.getStopWatch().stop("replacing tasks");
	}

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

		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;
			System.out.println("Creating thread for sessions " + from
					+ " till " + to);
			final ParallelPairwiseAligner aligner = new ParallelPairwiseAligner(
					appData, from, to);
			executor.execute(aligner);
		}
		executor.shutdown();
		try {
			executor.awaitTermination(2, TimeUnit.HOURS);
		} catch (final InterruptedException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}

	/**
	 * <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.getUniqueTasks().add(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 " + appData.getUniqueTasks().size()
				+ " different tasks)");

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

	/**
	 * <p>
	 * TODO clarify why this is done
	 * </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            , Ruleapplication Data 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 it's 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.
			// Check if the next position is not a selection
			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);
					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 {
				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());
		}
	}

	/**
	 * Replace matches.
	 *
	 * @param appData the app data
	 */
	private void replaceMatches(RuleApplicationData appData) {
		appData.replacedOccurences = new HashMap<Integer, List<MatchOccurence>>();

		final int matchSeqSize = appData.getMatchseqs().size();
		int newThreads = nThreads;
		if (matchSeqSize < nThreads) {
			newThreads = matchSeqSize;
		}
		final ExecutorService executor = Executors
				.newFixedThreadPool(newThreads);
		final int interval = matchSeqSize / newThreads;
		int rest = matchSeqSize % newThreads;

		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;
			System.out
			.println("Replacement: 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);
		}
		executor.shutdown();
		try {
			executor.awaitTermination(2, TimeUnit.HOURS);
		} catch (final InterruptedException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}


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

	/**
	 * Search matches in all sessions.
	 *
	 * @param appData the app data
	 */
	private void searchMatchesInAllSessions(RuleApplicationData appData) {
		Console.traceln(Level.INFO,
				"searching for patterns occuring most with " + nThreads
						+ " threads");
		// Prepare parallel search of matchseqs

		final int matchSeqSize = appData.getMatchseqs().size();
		int newThreads = nThreads;
		if (matchSeqSize < nThreads) {
			newThreads = matchSeqSize;
		}
		final int interval = matchSeqSize / newThreads;
		int rest = matchSeqSize % newThreads;
		final ExecutorService executor = Executors.newFixedThreadPool(nThreads);

		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;
			System.out
			.println("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);
		}
		executor.shutdown();
		try {
			executor.awaitTermination(2, TimeUnit.HOURS);
		} catch (final InterruptedException e) {
			// TODO Auto-generated catch block
			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 - 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 MatchOccurence(start,
									start + pattern.size(), j));
						}
					}
				}
			}
		}
	}

	/**
	 * The Class ParallelMatchReplacer.
	 */
	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 match replacer.
		 *
		 * @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() {
			// TODO Cleanup
			// int count = 0;
			// int size = to - from;
			for (int i = from; i < to; i++) {
				// count++;
				// Every pattern consists of 2 sequences, therefore the minimum
				// occurrences here is 2.
				// We just need the sequences also occurring in other sequences
				// as well
				if (appData.getMatchseqs().get(i).occurenceCount() > 2) {

					final ISequence task = matchAsSequence(appData, appData
							.getMatchseqs().get(i));
					invalidOccurence: for (final Iterator<MatchOccurence> it = appData
							.getMatchseqs().get(i).getOccurences().iterator(); it
							.hasNext();) {
						final MatchOccurence oc = it.next();

						// Check if nothing has been replaced in the sequence we
						// want to replace now

						synchronized (appData.getReplacedOccurrences()) {
							if (appData.getReplacedOccurrences().get(
									oc.getSequenceId()) == null) {
								appData.getReplacedOccurrences().put(
										oc.getSequenceId(),
										new LinkedList<MatchOccurence>());
							} else {
								// check if we have any replaced occurence with
								// indexes
								// smaller than ours. If so, we need to adjust
								// our start
								// and endpoints
								// of the replacement.
								// Also do a check if we have replaced this
								// specific
								// MatchOccurence in this sequence already. Jump
								// to the
								// next occurence if this is the case.
								// This is no more neccessary once the matches
								// are
								// harmonized.
								for (final Iterator<MatchOccurence> jt = appData
										.getReplacedOccurrences()
										.get(oc.getSequenceId()).iterator(); jt
										.hasNext();) {
									final MatchOccurence 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");
										}
									}
								}
							}
							System.out.println("Replacing in sequence"
									+ oc.getSequenceId());
							synchronized (appData) {
								appData.detectedAndReplacedTasks = true;
							}
							synchronized (appData.getSessions().get(
									oc.getSequenceId())) {
								final ISequenceInstance sequenceInstances = RuleUtils
										.createNewSubSequenceInRange(
												appData.getSessions().get(
														oc.getSequenceId()),
														oc.getStartindex(),
														oc.getEndindex(), task,
														taskFactory, taskBuilder);
								oc.setEndindex((oc.getStartindex() + sequenceInstances
										.size()) - RuleUtils.missedOptionals);
							}
						}
						// Adjust the length of the match regarding to the
						// length of
						// instance. (OptionalInstances may be shorter)

						synchronized (appData.getReplacedOccurrences().get(
								oc.getSequenceId())) {
							appData.getReplacedOccurrences()
							.get(oc.getSequenceId()).add(oc);
						}
					}
				}
			}
		}
	}

	/**
	 * 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 - 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();
						aa.align(ns1, ns2, appData.getSubmat(), 9);
						synchronized (appData.getMatchseqs()) {
							appData.getMatchseqs().addAll(aa.getMatches());
						}
					}
				}
			}
		}
	}
	
}