//   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.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.logging.Level;

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.PairwiseAlignmentGenerator;
import de.ugoe.cs.autoquest.tasktrees.alignment.matrix.PairwiseAlignmentStorage;
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.ITaskInstanceList;
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 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>
 * 
 * 
 * @author Patrick Harms
 */
class SequenceForTaskDetectionRuleAlignment 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 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
	 */

	SequenceForTaskDetectionRuleAlignment(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 "SequenceForTaskDetectionRuleAlignment";
	}

	/*
	 * (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.
		SymbolMap<ITaskInstance, ITask> uniqueTasks = harmonizeEventTaskInstancesModel(appData);

		// Generate a substitution matrix between all occurring events.
		Console.traceln(Level.INFO, "generating substitution matrix");
		ObjectDistanceSubstitionMatrix submat = new ObjectDistanceSubstitionMatrix(
				uniqueTasks, 6, -3);
		submat.generate();

		// Generate pairwise alignments
		Console.traceln(Level.INFO, "generating pairwise alignments");
		LinkedList<Match> matchseqs = new LinkedList<Match>();
		PairwiseAlignmentStorage alignments = PairwiseAlignmentGenerator
				.generate(appData.getNumberSequences(), submat, 9);

		// Retrieve all matches reached a specific threshold
		Console.traceln(Level.INFO, "retrieving significant sequence pieces");
		for (int i = 0; i < appData.getNumberSequences().size(); i++) {
			Console.traceln(
					Level.FINEST,
					"retrieving significant sequence pieces:  "
							+ Math.round((float) i
									/ (float) appData.getNumberSequences()
											.size() * 100) + "%");
			for (int j = 0; j < appData.getNumberSequences().size(); j++) {
				if (i != j) {
					matchseqs.addAll(alignments.get(i, j).getMatches());
				}
			}
		}
		Console.traceln(Level.FINEST,
				"retrieving significant sequence pieces:  100%");
		Console.traceln(Level.INFO, "searching for patterns occuring most");

		// search each match in every other sequence
		for (Iterator<Match> it = matchseqs.iterator(); it.hasNext();) {
			Match pattern = it.next();

			// 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++) {
				LinkedList<Integer> startpositions = appData
						.getNumberSequences().get(j).containsPattern(pattern);
				if (startpositions.size() > 0) {
					for (Iterator<Integer> jt = startpositions.iterator(); jt
							.hasNext();) {
						int start = jt.next();
						pattern.addOccurence(new MatchOccurence(start, start
								+ pattern.size(), j));
					}

				}
			}
		}

		Console.traceln(Level.INFO, "sorting results");
		// Sort results to get the most occurring results
		Comparator<Match> comparator = new Comparator<Match>() {
			public int compare(Match m1, Match m2) {
				return m2.occurenceCount() - m1.occurenceCount();

			}
		};
		Collections.sort(matchseqs, comparator);

		HashMap<Integer, List<MatchOccurence>> replacedOccurences = new HashMap<Integer, List<MatchOccurence>>();
		// Replace matches in the sessions
		for (int i = 0; i < matchseqs.size(); i++) {
			// 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 (matchseqs.get(i).occurenceCount() > 2) {

				ISequence task = matchAsSequence(appData, matchseqs.get(i));
				invalidOccurence: for (Iterator<MatchOccurence> it = matchseqs
						.get(i).getOccurences().iterator(); it.hasNext();) {
					MatchOccurence oc = it.next();
					/*
					System.out.println("Trying to replace sequence: ");
					matchseqs.get(i).getFirstSequence().printSequence();
					matchseqs.get(i).getSecondSequence().printSequence();
					System.out.println(" in session number: "
							+ (oc.getSequenceId() + 1)
							+ " at position "
							+ (oc.getStartindex())
							+ "-"
							+ oc.getEndindex());
					System.out.println();
					*/
					
					// System.out.println("Printing session: ");
					//for (int j = 0; j < sessions.get(oc.getSequenceId()).size(); j++) {
					//	System.out.println(j + ": "
					//			+ sessions.get(oc.getSequenceId()).get(j));
					//}

					// Check if nothing has been replaced in the sequence we
					// want to replace
					if (replacedOccurences.get(oc.getSequenceId()) == null) {
						replacedOccurences.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 (Iterator<MatchOccurence> jt = replacedOccurences
								.get(oc.getSequenceId()).iterator(); jt
								.hasNext();) {
							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()) {
								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");
								}
							}
						}
					}
					ISequenceInstance sequenceInstances = RuleUtils
							.createNewSubSequenceInRange(
									sessions.get(oc.getSequenceId()),
									oc.getStartindex(), oc.getEndindex(), task,
									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);
					replacedOccurences.get(oc.getSequenceId()).add(oc);
				}
			}
		}

		alignments = null;

		do {

			appData.getStopWatch().start("whole loop"); //
			detectAndReplaceIterations(appData);

			appData.getStopWatch().start("task replacement"); //
			// 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();
	}

	
	/**
	 * <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 SymbolMap<ITaskInstance, ITask> harmonizeEventTaskInstancesModel(
			RuleApplicationData appData) {
		Console.traceln(Level.INFO,
				"harmonizing task model of event task instances");
		appData.getStopWatch().start("harmonizing event tasks");

		SymbolMap<ITaskInstance, ITask> uniqueTasks = preparationTaskHandlingStrategy
				.createSymbolMap();
		TaskInstanceComparator comparator = preparationTaskHandlingStrategy
				.getTaskComparator();

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

			NumberSequence templist = new NumberSequence(session.size());

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

				if (task == null) {
					uniqueTasks.addSymbol(taskInstance, taskInstance.getTask());
					templist.getSequence()[i] = taskInstance.getTask().getId();

				} else {
					taskBuilder.setTask(taskInstance, task);
					templist.getSequence()[i] = task.getId();
					unifiedTasks++;
				}
				appData.getNumber2Task().put(templist.getSequence()[i],
						taskInstance.getTask());

				// if(j==1) {
				// System.out.println(i + ": TaskID: " +
				// taskInstance.getTask().getId()+ " Numbersequence: " +
				// templist.getSequence()[i]);
				// }

			}
			// Each NumberSequence is identified by its id, beginning to count
			// at zero
			templist.setId(j);
			appData.getNumberSequences().add(templist);
			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();
		return uniqueTasks;
	}

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

		for (ITask iteratedTask : iteratedTasks) {
			IIteration iteration = taskFactory.createNewIteration();
			iterations.put(iteratedTask, iteration);
			iterationInstances.put(iteration,
					new LinkedList<IIterationInstance>());
		}

		IIterationInstance iterationInstance;

		for (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
				ITask currentTask = session.get(index).getTask();
				IIteration iteration = iterations.get(currentTask);
				if (iteration != null) {
					if ((iterationInstance == null)
							|| (iterationInstance.getTask() != iteration)) {
						iterationInstance = taskFactory
								.createNewTaskInstance(iteration);
						iterationInstances.get(iteration)
								.add(iterationInstance);
						taskBuilder.addTaskInstance(session, index,
								iterationInstance);
						index++;
					}

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

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

	ISequence matchAsSequence(RuleApplicationData appData, Match m) {

		ISequence sequence = taskFactory.createNewSequence();

		int[] first = m.getFirstSequence().getSequence();
		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) {
				// TODO: Do nothing?
			}
			// 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) {
				IOptional optional = taskFactory.createNewOptional();
				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) {
				IOptional optional = taskFactory.createNewOptional();
				taskBuilder.setMarkedTask(optional, appData.getNumber2Task()
						.get(first[i]));
				taskBuilder.addChild(sequence, optional);
			}
			// Both tasks are unequal, we need to insert a selection here
			else {
				ISelection selection = taskFactory.createNewSelection();
				taskBuilder.addChild(selection,
						appData.getNumber2Task().get(first[i]));
				taskBuilder.addChild(selection,
						appData.getNumber2Task().get(second[i]));
				taskBuilder.addChild(sequence, selection);
			}
		}

		// TODO: Debug output
		/*
		 * for (int i =0;i<sequence.getChildren().size();i++) {
		 * System.out.println(sequence.getChildren().get(i));
		 * 
		 * if(sequence.getChildren().get(i).getType() == "selection") { for(int
		 * j=0; j< ((ISelection)
		 * sequence.getChildren().get(i)).getChildren().size();j++) {
		 * System.out.println("\t" +((ISelection)
		 * sequence.getChildren().get(i)).getChildren().get(j)); } } }
		 */
		return sequence;
	}

	/**
	 * <p>
	 * TODO clarify why this is done
	 * </p>
	 */
	private void harmonizeIterationInstancesModel(IIteration iteration,
			List<IIterationInstance> iterationInstances) {
		List<ITask> iteratedTaskVariants = new LinkedList<ITask>();
		TaskInstanceComparator 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");

		// getSequencesOccuringMostOften(appData);

		appData.getStopWatch().stop("detecting tasks");
		appData.getStopWatch().start("replacing tasks");

		replaceSequencesOccurringMostOften(appData);

		appData.getStopWatch().stop("replacing tasks");

		// Console.traceln(Level.INFO, "detected and replaced "
		// + appData.getLastFoundTasks().size() + " tasks occuring "
		// + appData.getLastFoundTasks().getOccurrenceCount() + " times");
	}

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

		/*
		 * Console.traceln(Level.FINER, "replacing tasks occurrences");
		 * 
		 * for (List<ITaskInstance> task : appData.getLastFoundTasks()) {
		 * ISequence sequence = taskFactory.createNewSequence();
		 * 
		 * Console.traceln(Level.FINEST, "replacing " + sequence.getId() + ": "
		 * + task);
		 * 
		 * List<ISequenceInstance> sequenceInstances = replaceTaskOccurrences(
		 * task, appData.getSessions(), sequence);
		 * 
		 * harmonizeSequenceInstancesModel(sequence, sequenceInstances,
		 * task.size()); appData.detectedAndReplacedTasks(appData
		 * .detectedAndReplacedTasks() || (sequenceInstances.size() > 0));
		 * 
		 * if (sequenceInstances.size() < appData.getLastFoundTasks()
		 * .getOccurrenceCount()) { Console.traceln(Level.FINE, sequence.getId()
		 * + ": replaced task only " + sequenceInstances.size() +
		 * " times instead of expected " + appData.getLastFoundTasks()
		 * .getOccurrenceCount()); } }
		 */
	}

	/**
     *
     */
	private void harmonizeSequenceInstancesModel(ISequence sequence,
			List<ISequenceInstance> sequenceInstances, int sequenceLength) {
		TaskInstanceComparator 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> replaceTaskOccurrences(
			List<ITaskInstance> task, List<IUserSession> sessions,
			ISequence temporalTaskModel) {
		List<ISequenceInstance> sequenceInstances = new LinkedList<ISequenceInstance>();

		for (IUserSession session : sessions) {
			int index = -1;

			do {
				index = getSubListIndex(session, task, ++index);

				if (index > -1) {
					sequenceInstances.add(RuleUtils
							.createNewSubSequenceInRange(session, index, index
									+ task.size() - 1, temporalTaskModel,
									taskFactory, taskBuilder));
				}
			} while (index > -1);
		}

		return sequenceInstances;
	}

	/**
	 * @param trie
	 * @param object
	 * @return
	 */
	private int getSubListIndex(ITaskInstanceList list,
			List<ITaskInstance> subList, int startIndex) {
		boolean matchFound;
		int result = -1;

		for (int i = startIndex; i <= list.size() - subList.size(); i++) {
			matchFound = true;

			for (int j = 0; j < subList.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() != subList.get(j).getTask()) {
					matchFound = false;
					break;
				}
			}

			if (matchFound) {
				result = i;
				break;
			}
		}

		return result;
	}

	/**
     * 
     */
	private static class RuleApplicationData {

		private HashMap<Integer, ITask> number2task;

		private ArrayList<NumberSequence> numberseqs;

		/**
         * 
         */
		private List<IUserSession> sessions;

		/**
         * 
         */
		private boolean detectedAndReplacedTasks;

		/**
         * 
         */
		private RuleApplicationResult result;

		/**
         * 
         */
		private StopWatch stopWatch;

		/**
         * 
         */
		private RuleApplicationData(List<IUserSession> sessions) {
			this.sessions = sessions;
			numberseqs = new ArrayList<NumberSequence>();
			number2task = new HashMap<Integer, ITask>();
			stopWatch = new StopWatch();
			result = new RuleApplicationResult();
		}

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

		private ArrayList<NumberSequence> getNumberSequences() {
			return numberseqs;
		}

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

		private HashMap<Integer, ITask> getNumber2Task() {
			return number2task;
		}

	}

}