//   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.File;
import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
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.CommandHelpers;
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;
import de.ugoe.cs.util.console.GlobalDataContainer;

/**
 * <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
 */
public class SequenceForTaskDetectionRuleAlignment implements ISessionScopeRule {
	
	public static int nThreads = Runtime.getRuntime().availableProcessors()-1;

	
	private int iteration = 0;
	/**
	 * <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>
	 * 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 java.lang.Object#toString()
	 */
	@Override
	public String toString() {
		return "SequenceForTaskDetectionRuleAlignment";
	}

	public void saveAppData(String name) {
		String objectName = name;
		String filename = name + ".dat";
		Object dataObject = GlobalDataContainer.getInstance().getData(
				objectName);
		if (dataObject == null) {
			CommandHelpers.objectNotFoundMessage(objectName);
		}
		FileOutputStream fos = null;
		ObjectOutputStream out = null;
		try {
			fos = new FileOutputStream(filename);
			out = new ObjectOutputStream(fos);
			out.writeObject(dataObject);
			out.close();
		} catch (IOException ex) {
			Console.logException(ex);
		}
	}
	
	public RuleApplicationData loadAppData(String name) {
		String objectName = name;
		String filename = name + ".dat";
	
		Object data = null;
		FileInputStream fis = null;
		ObjectInputStream in = null;
		try {
			fis = new FileInputStream(filename);
			in = new ObjectInputStream(fis);
			data = in.readObject();
			in.close();
		} catch (IOException ex) {
			Console.logException(ex);
		} catch (ClassNotFoundException ex) {
			Console.logException(ex);
		}
		if (GlobalDataContainer.getInstance().addData(objectName, data)) {
			CommandHelpers.dataOverwritten(objectName);
		}
		return (RuleApplicationData) GlobalDataContainer.getInstance().getData(name);
	}
	
	/*
	 * (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);
		//File harmonized = new File("harmonized.dat");
		//if(harmonized.exists() && !harmonized.isDirectory()) { 
		//	Console.traceln(Level.INFO,"loading harmonized sessions from file");
		//	appData = loadAppData("harmonized");
		//}
		//else {
			//appData.getStopWatch().start("harmonization");
			harmonizeEventTaskInstancesModel(appData);
			//appData.getStopWatch().stop("harmonization");
			GlobalDataContainer.getInstance().addData("harmonized", appData);
			//Saving intermediate results to file
			Console.traceln(Level.INFO,"saving substitution matrix to file");
			//saveAppData("harmonized");
		//}
		
		//File substitution = new File("substitution.dat");
		//if(!(substitution.exists() && !substitution.isDirectory())) { 
			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");
		//	GlobalDataContainer.getInstance().addData("substitution", appData);
		//	saveAppData("substitution");
		//}
		//else {
		//	Console.traceln(Level.INFO,"loading substitution matrix from file");
		//	appData = loadAppData("substitution");
		//}
		
		
		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();
	}


	private ArrayList<NumberSequence> createNumberSequences(
			RuleApplicationData appData) {
		ArrayList<NumberSequence> result = new ArrayList<NumberSequence>();
		for (int i = 0; i < appData.getSessions().size(); i++) {
			IUserSession session = appData.getSessions().get(i);
			NumberSequence templist = new NumberSequence(session.size());
			for (int j = 0; j < session.size(); j++) {
				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>
	 * 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");
		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);

			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());
					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>
	 * 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();
			appData.newTaskCreated(iteration);
			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);// 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 (Map.Entry<IIteration, List<IIterationInstance>> entry : iterationInstances
				.entrySet()) {
			harmonizeIterationInstancesModel(entry.getKey(), entry.getValue());
		}
	}

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

	/**
	 * @param appData
	 * @param m
	 * @return
	 */
	public ISequence matchAsSequence(RuleApplicationData appData, Match m) {	
		ISequence sequence = taskFactory.createNewSequence();
		appData.newTaskCreated(sequence);

		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) {
				// 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) {
				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) {
				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))) {

					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;
					ISelection selection = taskFactory.createNewSelection();
					appData.newTaskCreated(selection);

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

					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])) {

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

	/**
	 * 
	 * @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");
		Comparator<Match> comparator = new Comparator<Match>() {
			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");
		HashMap<Integer, List<MatchOccurence>> replacedOccurences = new HashMap<Integer, List<MatchOccurence>>();
		for (int i = 0; i < appData.getMatchseqs().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 (appData.getMatchseqs().get(i).occurenceCount() > 2) {
				appData.detectedAndReplacedTasks = true;
				ISequence task = matchAsSequence(appData, appData.getMatchseqs().get(i));
				invalidOccurence: for (Iterator<MatchOccurence> it = appData.getMatchseqs()
						.get(i).getOccurences().iterator(); it.hasNext();) {
					MatchOccurence oc = it.next();
					
					// 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");
								}
							}
						}
					}
					System.out.println("Replacing in sequence" + oc.getSequenceId());
					ISequenceInstance sequenceInstances = RuleUtils
							.createNewSubSequenceInRange(appData.getSessions()
									.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);
				}
			}
		}
		//appData.setMatchseqs(null);
		appData.getStopWatch().stop("replacing tasks");
	}
	
	
	

	private void searchMatchesInAllSessions(RuleApplicationData appData) {
		Console.traceln(Level.INFO, "searching for patterns occuring most with " + nThreads + " threads");
		//Prepare parallel search of matchseqs
		ExecutorService executor = Executors.newFixedThreadPool(nThreads);
		int matchSeqSize=appData.getMatchseqs().size();
		int interval = Math.round(matchSeqSize/nThreads);
		int rest = matchSeqSize % nThreads;
		
		for(int i =0;i<matchSeqSize-interval;i+=interval) {
			int offset =0;
			if(rest!=0) {
				offset=1;
				rest--;
			}
			int from = i;
			int to = i+interval+offset;
			System.out.println("Creating thread with matches from " + from + " to " + to);
			// search each match in every other sequence
			ParallelMatchOcurrencesFinder finder = new ParallelMatchOcurrencesFinder(appData,from,to);
			executor.execute(finder);
		}
		executor.shutdown();
		try {
			executor.awaitTermination(2, TimeUnit.HOURS);
		} catch (InterruptedException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		
	}

	//Print out the progress
	 private static void printProgressPercentage(int count, int size) {
		if(size>100) {
			if((count%(size/100)==0)) {	
				//Console.traceln(Level.INFO,("Thread" + Thread.currentThread().getName() + ": " + Math.round((float) count/size*100))+ "%");
				System.out.println("Thread" + Thread.currentThread().getName() + ": " + Math.round((float) count/size*100)+ "%");
			}
		}
		else {
			//Console.traceln(Level.INFO,("Thread" + Thread.currentThread().getName() + ": " +Math.round((float) count/size*100))+ "%");
			System.out.println("Thread" + Thread.currentThread().getName() + ": " +Math.round((float) count/size*100)+ "%");
			
		}
	}
	
	 
	 
	
	private class ParallelMatchOcurrencesFinder implements Runnable {
        private final RuleApplicationData appData;
        private final int from;
        private final int to;
            ParallelMatchOcurrencesFinder(RuleApplicationData appData, int from, int to) {
            this.appData = appData;
            this.from = from;
            this.to = to;
        }
        
        @Override
        public void run() {
        	int count = 0;
    		int size=to-from;
    		
    		for (int i=from; i<to;i++) { 
    			Match pattern = appData.getMatchseqs().get(i);
    			count++;
    			printProgressPercentage(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++) {
    				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));
    					}
    				}
    			}
    		}  
        }
	}
	
	
	private class ParallelPairwiseAligner implements Runnable {
        private final RuleApplicationData appData;
        private final int from;
        private final int to;
            ParallelPairwiseAligner(RuleApplicationData appData, int from, int to) {
            this.appData = appData;
            this.from = from;
            this.to = to;
        }
        
        @Override
        public void run() {
        	int count = 0;
    		int size=to-from;
    		
    		for (int i=from; i<to;i++) {
    			NumberSequence ns1 = appData.getNumberSequences().get(i);
				count++;
				printProgressPercentage(count,size);
				for (int j = 0; j < appData.getNumberSequences().size(); j++) {
					NumberSequence ns2 = appData.getNumberSequences().get(j);
					if (i != j) {
						AlignmentAlgorithm aa = AlignmentAlgorithmFactory.create();
						aa.align(ns1, ns2, appData.getSubmat(),9);
						synchronized(appData.getMatchseqs()) {
							appData.getMatchseqs().addAll(aa.getMatches());
						}
					}
				}
    		}  
    	}
	}

	//private LinkedList<Match> generatePairwiseAlignments(RuleApplicationData appData) {
	private void generatePairwiseAlignments(RuleApplicationData appData) {
		int numberSeqSize = appData.getNumberSequences().size();
		appData.matchseqs = new LinkedList<Match>();
		//Checking if i have an already calculated file result of this action in the working directory 
		//File aligned = new File("aligned" + iteration + ".dat");
		//if(!(aligned.exists() && !aligned.isDirectory())) {
			Console.traceln(Level.INFO, "generating pairwise alignments from " + numberSeqSize + " sessions with " + nThreads + " threads");
			ExecutorService executor = Executors.newFixedThreadPool(nThreads);
			int interval = Math.round(numberSeqSize/nThreads);
			int rest = numberSeqSize % nThreads;
			
			for (int i = 0; i < numberSeqSize-interval; i+=interval) {
				int offset = 0;
				if(rest!=0) {
					offset=1;
					rest--;
				}
				int from = i;
				int to = i+interval+offset;
				System.out.println("Creating thread for sessions " + from + " till " + to);
				ParallelPairwiseAligner aligner = new ParallelPairwiseAligner(appData,from,to);
				executor.execute(aligner);
			}
			executor.shutdown();
			try {
				executor.awaitTermination(10, TimeUnit.MINUTES);
			} catch (InterruptedException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
	
			//GlobalDataContainer.getInstance().addData("aligned" + iteration, appData);
			//saveAppData("aligned" + iteration);
		//	return result;
		}
		//else {
		//	Console.traceln(Level.INFO,"loading matches from file");
		//	appData = loadAppData("aligned"+iteration);
		//	return appData.getMatchseqs();
		//}
	

	/**
     * 
     */
	private static class RuleApplicationData implements Serializable {

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

		private HashMap<Integer, ITask> number2task;

		// TODO: We Actually just need number2task here, this structure can be removed in the future.
		private HashSet<ITask> uniqueTasks;
		
		ObjectDistanceSubstitionMatrix submat; 
		
		LinkedList<Match> matchseqs;
		
		private ArrayList<NumberSequence> numberseqs;

		private LinkedList<ITask> newTasks;
		
		/**
         * 
         */
		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>();
			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;
		}

		public LinkedList<Match> getMatchseqs() {
			return matchseqs;
		}


		private ObjectDistanceSubstitionMatrix getSubmat() {
			return submat;
		}
		
		private void resetNewlyCreatedTasks() {
			uniqueTasks.addAll(newTasks);
			newTasks.clear();
		}
		
		private void newTaskCreated(ITask task) {
			number2task.put(task.getId(), task);
			newTasks.add(task);
		}

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

		private HashSet<ITask> getUniqueTasks() {
			return uniqueTasks;
		}

		private void setNumberSequences(ArrayList<NumberSequence> numberseqs) {
			this.numberseqs = numberseqs;
		}

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

		private void updateSubstitutionMatrix() {
			submat.update(getNewTasks());
			resetNewlyCreatedTasks();
		}

		
		
		/**
         *
         */
		private boolean detectedAndReplacedTasks() {
			return detectedAndReplacedTasks;
		}

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

		public LinkedList<ITask> getNewTasks() {
			return newTasks;
		}
		
		/**
		 * @return the stopWatch
		 */
		private StopWatch getStopWatch() {
			return stopWatch;
		}

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

	}

}