Context Navigation

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

Last change on this file since 1734 was 1734, checked in by rkrimmel, 10 years ago
Added automatically created javadoc, still needs to be commented properly though
File size: 36.7 KB

Line
1	// Copyright 2012 Georg-August-Universität Göttingen, Germany
2	//
3	// Licensed under the Apache License, Version 2.0 (the "License");
4	// you may not use this file except in compliance with the License.
5	// You may obtain a copy of the License at
6	//
7	// http://www.apache.org/licenses/LICENSE-2.0
8	//
9	// Unless required by applicable law or agreed to in writing, software
10	// distributed under the License is distributed on an "AS IS" BASIS,
11	// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12	// See the License for the specific language governing permissions and
13	// limitations under the License.
14
15	package de.ugoe.cs.autoquest.tasktrees.temporalrelation;
16
17	import java.io.Serializable;
18	import java.util.ArrayList;
19	import java.util.Collections;
20	import java.util.Comparator;
21	import java.util.HashMap;
22	import java.util.HashSet;
23	import java.util.Iterator;
24	import java.util.LinkedList;
25	import java.util.List;
26	import java.util.Map;
27	import java.util.Set;
28	import java.util.concurrent.ExecutorService;
29	import java.util.concurrent.Executors;
30	import java.util.concurrent.TimeUnit;
31	import java.util.logging.Level;
32
33	import de.ugoe.cs.autoquest.tasktrees.alignment.algorithms.AlignmentAlgorithm;
34	import de.ugoe.cs.autoquest.tasktrees.alignment.algorithms.AlignmentAlgorithmFactory;
35	import de.ugoe.cs.autoquest.tasktrees.alignment.algorithms.Match;
36	import de.ugoe.cs.autoquest.tasktrees.alignment.algorithms.MatchOccurence;
37	import de.ugoe.cs.autoquest.tasktrees.alignment.algorithms.NumberSequence;
38	import de.ugoe.cs.autoquest.tasktrees.alignment.matrix.ObjectDistanceSubstitionMatrix;
39	import de.ugoe.cs.autoquest.tasktrees.taskequality.TaskEquality;
40	import de.ugoe.cs.autoquest.tasktrees.treeifc.IIteration;
41	import de.ugoe.cs.autoquest.tasktrees.treeifc.IIterationInstance;
42	import de.ugoe.cs.autoquest.tasktrees.treeifc.IOptional;
43	import de.ugoe.cs.autoquest.tasktrees.treeifc.ISelection;
44	import de.ugoe.cs.autoquest.tasktrees.treeifc.ISelectionInstance;
45	import de.ugoe.cs.autoquest.tasktrees.treeifc.ISequence;
46	import de.ugoe.cs.autoquest.tasktrees.treeifc.ISequenceInstance;
47	import de.ugoe.cs.autoquest.tasktrees.treeifc.ITask;
48	import de.ugoe.cs.autoquest.tasktrees.treeifc.ITaskBuilder;
49	import de.ugoe.cs.autoquest.tasktrees.treeifc.ITaskFactory;
50	import de.ugoe.cs.autoquest.tasktrees.treeifc.ITaskInstance;
51	import de.ugoe.cs.autoquest.tasktrees.treeifc.IUserSession;
52	import de.ugoe.cs.autoquest.usageprofiles.SymbolMap;
53	import de.ugoe.cs.util.StopWatch;
54	import de.ugoe.cs.util.console.Console;
55
56
57	/**
58	* <p>
59	* This class implements the major rule for creating task trees based on a set
60	* of recorded user sessions. For this, it first harmonizes all tasks. This
61	* eases later comparison. Then it searches the sessions for iterations and
62	* replaces them accordingly. Then it searches for sub sequences using alignment algorithms
63	* For each found sub sequence, it replaces
64	* the occurrences by creating appropriate {@link ISequence}s. Afterwards, again
65	* searches for iterations and then again for sub sequences until no more
66	* replacements are done.
67	* </p>
68	* <p>
69	*
70	*
71	* @author Ralph Krimmel
72	*/
73	public class SequenceForTaskDetectionRuleAlignment implements ISessionScopeRule {
74
75
76	/**
77	* The Class RuleApplicationData.
78	*/
79	private static class RuleApplicationData implements Serializable {
80
81	/** The Constant serialVersionUID. */
82	private static final long serialVersionUID = -7559657686755522960L;
83
84	/** The number2task HashMap. Since we align the tasks just by their integer id,
85	* we need this to convert them back to Tasks again*/
86	private final HashMap<Integer, ITask> number2task;
87
88
89	/** The unique tasks, keeps track about all unique tasks
90	* TODO: We Actually just need number2task here, this structure can be
91	* removed in the future.*/
92	private final HashSet<ITask> uniqueTasks;
93
94	/** The substitution matrix used by the alignment algorithm to be able to compare
95	* distances of tasks */
96	private final ObjectDistanceSubstitionMatrix submat;
97
98	/** HashMap for keeping track in which sequence which replacement has been performed.
99	* Neccessary for updating the indices of other occurrences accordingly */
100	public HashMap<Integer, List<MatchOccurence>> replacedOccurences;
101
102	/** The list of all found matches */
103	public LinkedList<Match> matchseqs;
104
105	/** The generated NumberSequences.
106	* This is the integer representation of the user sessions */
107	private ArrayList<NumberSequence> numberseqs;
108
109	/** The list of newly created tasks (of one iteration). */
110	private final LinkedList<ITask> newTasks;
111
112	/** The user sessions containing all EventTasks/Instances */
113	private final List<IUserSession> sessions;
114
115	/** True if we replaced something in the user sessions in one iteration. */
116	private boolean detectedAndReplacedTasks;
117
118	/** The result we give autoquest back */
119	private final RuleApplicationResult result;
120
121	/** Stop Watch to measure performance */
122	private final StopWatch stopWatch;
123
124	/**
125	* Instantiates a new rule application data.
126	*
127	* @param sessions The user sessions
128	*/
129	private RuleApplicationData(List<IUserSession> sessions) {
130	this.sessions = sessions;
131	numberseqs = new ArrayList<NumberSequence>();
132	uniqueTasks = new HashSet<ITask>();
133	number2task = new HashMap<Integer, ITask>();
134	stopWatch = new StopWatch();
135	result = new RuleApplicationResult();
136	submat = new ObjectDistanceSubstitionMatrix(6, -3, false);
137	newTasks = new LinkedList<ITask>();
138	this.detectedAndReplacedTasks = true;
139	}
140
141	/**
142	* Detected and replaced tasks.
143	*
144	* @return true, if successful
145	*/
146	private boolean detectedAndReplacedTasks() {
147	return detectedAndReplacedTasks;
148	}
149
150	/**
151	* Gets the matchseqs.
152	*
153	* @return the matchseqs
154	*/
155	public LinkedList<Match> getMatchseqs() {
156	return matchseqs;
157	}
158
159	/**
160	* Gets the new tasks.
161	*
162	* @return the new tasks
163	*/
164	public LinkedList<ITask> getNewTasks() {
165	return newTasks;
166	}
167
168	/**
169	* Gets the number2task.
170	*
171	* @return the number2task HashMap
172	*/
173	private HashMap<Integer, ITask> getNumber2Task() {
174	return number2task;
175	}
176
177	/**
178	* Gets the number sequences.
179	*
180	* @return the number sequences
181	*/
182	private ArrayList<NumberSequence> getNumberSequences() {
183	return numberseqs;
184	}
185
186	/**
187	* Gets the replaced occurrences.
188	*
189	* @return the replaced occurences
190	*/
191	public HashMap<Integer, List<MatchOccurence>> getReplacedOccurrences() {
192	return replacedOccurences;
193	}
194
195	/**
196	* Gets the result.
197	*
198	* @return the result
199	*/
200	private RuleApplicationResult getResult() {
201	return result;
202	}
203
204	/**
205	* Gets the sessions.
206	*
207	* @return the UserSessions as List.
208	*/
209	private List<IUserSession> getSessions() {
210	return sessions;
211	}
212
213	/**
214	* Gets the stop watch.
215	*
216	* @return the stopWatch
217	*/
218	private StopWatch getStopWatch() {
219	return stopWatch;
220	}
221
222	/**
223	* Gets the submat.
224	*
225	* @return the submat
226	*/
227	private ObjectDistanceSubstitionMatrix getSubmat() {
228	return submat;
229	}
230
231	/**
232	* Gets the unique tasks.
233	*
234	* @return the unique tasks
235	*/
236	private HashSet<ITask> getUniqueTasks() {
237	return uniqueTasks;
238	}
239
240	/**
241	* New task created.
242	*
243	* @param task the task
244	*/
245	private void newTaskCreated(ITask task) {
246	number2task.put(task.getId(), task);
247	newTasks.add(task);
248	}
249
250	/**
251	* Reset newly created tasks.
252	*/
253	synchronized private void resetNewlyCreatedTasks() {
254	uniqueTasks.addAll(newTasks);
255	newTasks.clear();
256	}
257
258	/**
259	* Sets the number sequences.
260	*
261	* @param numberseqs the new number sequences
262	*/
263	private void setNumberSequences(ArrayList<NumberSequence> numberseqs) {
264	this.numberseqs = numberseqs;
265	}
266
267	/**
268	* Sets the replaced occurences.
269	*
270	* @param replacedOccurences the replaced occurences
271	*/
272	public void setReplacedOccurences(
273	HashMap<Integer, List<MatchOccurence>> replacedOccurences) {
274	this.replacedOccurences = replacedOccurences;
275	}
276
277	/**
278	* Update substitution matrix.
279	*/
280	private void updateSubstitutionMatrix() {
281	submat.update(getNewTasks());
282	resetNewlyCreatedTasks();
283	}
284
285	}
286
287	/** The n threads. */
288	public static int nThreads = Runtime.getRuntime().availableProcessors() - 1;
289
290	/** The iteration. */
291	private int iteration = 0;
292
293	/** <p> the task factory to be used for creating substructures for the temporal relationships identified during rul application </p>. */
294	private final ITaskFactory taskFactory;
295
296	/** <p> the task builder to be used for creating substructures for the temporal relationships identified during rule application </p>. */
297	private final ITaskBuilder taskBuilder;
298
299	/**
300	* <p>
301	* the task handling strategy to be used for comparing tasks for
302	* preparation, i.e., before the tasks are harmonized
303	* </p>
304	*/
305	private final TaskHandlingStrategy preparationTaskHandlingStrategy;
306
307	/**
308	* <p>
309	* instantiates the rule and initializes it with a task equality to be
310	* considered when comparing tasks as well as a task factory and builder to
311	* be used for creating task structures.
312	* </p>
313	*
314	* @param minimalTaskEquality
315	* the task equality to be considered when comparing tasks
316	* @param taskFactory
317	* the task factory to be used for creating substructures
318	* @param taskBuilder
319	* the task builder to be used for creating substructures
320	*/
321
322	SequenceForTaskDetectionRuleAlignment(TaskEquality minimalTaskEquality,
323	ITaskFactory taskFactory, ITaskBuilder taskBuilder) {
324	this.taskFactory = taskFactory;
325	this.taskBuilder = taskBuilder;
326
327	this.preparationTaskHandlingStrategy = new TaskHandlingStrategy(
328	minimalTaskEquality);
329	}
330
331	/*
332	* (non-Javadoc)
333	*
334	* @see
335	* de.ugoe.cs.autoquest.tasktrees.temporalrelation.ISessionScopeRule#apply
336	* (java.util.List)
337	*/
338	@Override
339	public RuleApplicationResult apply(List<IUserSession> sessions) {
340	final RuleApplicationData appData = new RuleApplicationData(sessions);
341
342	harmonizeEventTaskInstancesModel(appData);
343
344
345	Console.traceln(Level.INFO, "generating substitution matrix from "
346	+ appData.getUniqueTasks().size() + " unique tasks");
347	appData.getStopWatch().start("substitution matrix");
348	appData.getSubmat().generate(appData.getUniqueTasks());
349	appData.getStopWatch().stop("substitution matrix");
350
351	Console.traceln(Level.INFO, "Starting main loop");
352	do {
353	Console.traceln(Level.INFO, "Iteration Number: " + iteration);
354	iteration++;
355	appData.detectedAndReplacedTasks = false;
356	appData.getStopWatch().start("whole loop");
357	detectAndReplaceIterations(appData);
358	appData.getStopWatch().start("task replacement");
359	appData.updateSubstitutionMatrix();
360	detectAndReplaceTasks(appData); //
361	appData.getStopWatch().stop("task replacement");
362	appData.getStopWatch().stop("whole loop");
363	appData.getStopWatch().dumpStatistics(System.out);
364	appData.getStopWatch().reset();
365
366	} while (appData.detectedAndReplacedTasks());
367
368	Console.println("created "
369	+ appData.getResult().getNewlyCreatedTasks().size()
370	+ " new tasks and "
371	+ appData.getResult().getNewlyCreatedTaskInstances().size()
372	+ " appropriate instances\n");
373
374	if ((appData.getResult().getNewlyCreatedTasks().size() > 0)
375	\|\| (appData.getResult().getNewlyCreatedTaskInstances().size() > 0)) {
376	appData.getResult().setRuleApplicationStatus(
377	RuleApplicationStatus.FINISHED);
378	}
379
380	return appData.getResult();
381	}
382
383	/**
384	* Creates the number sequences.
385	*
386	* @param appData the app data
387	* @return the array list
388	*/
389	private ArrayList<NumberSequence> createNumberSequences(
390	RuleApplicationData appData) {
391	final ArrayList<NumberSequence> result = new ArrayList<NumberSequence>();
392	for (int i = 0; i < appData.getSessions().size(); i++) {
393	final IUserSession session = appData.getSessions().get(i);
394	final NumberSequence templist = new NumberSequence(session.size());
395	for (int j = 0; j < session.size(); j++) {
396	final ITaskInstance taskInstance = session.get(j);
397	templist.getSequence()[j] = taskInstance.getTask().getId();
398	}
399	// Each NumberSequence is identified by its id, beginning to count
400	// at zero
401	templist.setId(i);
402	result.add(templist);
403	}
404	return result;
405	}
406
407	/**
408	* <p>
409	* searches for direct iterations of single tasks in all sequences and
410	* replaces them with {@link IIteration}s, respectively appropriate
411	* instances. Also all single occurrences of a task that is iterated
412	* somewhen are replaced with iterations to have again an efficient way for
413	* task comparisons.
414	* </p>
415	*
416	* @param appData
417	* the rule application data combining all data used for applying
418	* this rule
419	*/
420	private void detectAndReplaceIterations(RuleApplicationData appData) {
421	Console.traceln(Level.FINE, "detecting iterations");
422	appData.getStopWatch().start("detecting iterations");
423
424	final List<IUserSession> sessions = appData.getSessions();
425
426	final Set<ITask> iteratedTasks = searchIteratedTasks(sessions);
427
428	if (iteratedTasks.size() > 0) {
429	replaceIterationsOf(iteratedTasks, sessions, appData);
430	}
431
432	appData.getStopWatch().stop("detecting iterations");
433	Console.traceln(Level.INFO, "replaced " + iteratedTasks.size()
434	+ " iterated tasks");
435	}
436
437	/**
438	* Detect and replace tasks.
439	*
440	* @param appData the rule application data combining all data used for applying
441	* this rule
442	*/
443	private void detectAndReplaceTasks(RuleApplicationData appData) {
444	Console.traceln(Level.FINE, "detecting and replacing tasks");
445	appData.getStopWatch().start("detecting tasks");
446
447	// Create NumberSequences
448	appData.setNumberSequences(this.createNumberSequences(appData));
449
450	// Generate pairwise alignments
451	// appData.setMatchseqs(generatePairwiseAlignments(appData));
452	generatePairwiseAlignments(appData);
453
454	// Searching each match in all other sessions, counting its occurences
455	searchMatchesInAllSessions(appData);
456
457	// Sort results to get the most occurring results
458	Console.traceln(Level.INFO, "sorting " + appData.getMatchseqs().size()
459	+ " results");
460	final Comparator<Match> comparator = new Comparator<Match>() {
461	@Override
462	public int compare(Match m1, Match m2) {
463	return m2.occurenceCount() - m1.occurenceCount();
464
465	}
466	};
467	Collections.sort(appData.getMatchseqs(), comparator);
468	appData.getStopWatch().stop("detecting tasks");
469
470	// Replace matches in the sessions
471	Console.traceln(Level.INFO, "Replacing matches in sessions");
472	appData.getStopWatch().start("replacing tasks");
473	replaceMatches(appData);
474	appData.getStopWatch().stop("replacing tasks");
475	}
476
477
478	/**
479	* Generate pairwise alignments.
480	*
481	* @param appData the app data
482	*/
483	private void generatePairwiseAlignments(RuleApplicationData appData) {
484	final int numberSeqSize = appData.getNumberSequences().size();
485	appData.matchseqs = new LinkedList<Match>();
486	Console.traceln(Level.INFO, "generating pairwise alignments from "
487	+ numberSeqSize + " sessions with " + nThreads + " threads");
488
489	int newThreads = nThreads;
490	if (numberSeqSize < nThreads) {
491	newThreads = numberSeqSize;
492	}
493
494	final ExecutorService executor = Executors
495	.newFixedThreadPool(newThreads);
496	final int interval = numberSeqSize / newThreads;
497	int rest = numberSeqSize % newThreads;
498
499	for (int i = 0; i < (numberSeqSize - interval); i += interval) {
500	int offset = 0;
501	if (rest != 0) {
502	offset = 1;
503	rest--;
504	}
505	final int from = i;
506	final int to = i + interval + offset;
507	System.out.println("Creating thread for sessions " + from
508	+ " till " + to);
509	final ParallelPairwiseAligner aligner = new ParallelPairwiseAligner(
510	appData, from, to);
511	executor.execute(aligner);
512	}
513	executor.shutdown();
514	try {
515	executor.awaitTermination(2, TimeUnit.HOURS);
516	} catch (final InterruptedException e) {
517	// TODO Auto-generated catch block
518	e.printStackTrace();
519	}
520	}
521
522	/**
523	* <p>
524	* harmonizes the event task instances by unifying tasks. This is done, as
525	* initially the event tasks being equal with respect to the considered task
526	* equality are distinct objects. The comparison of these distinct objects
527	* is more time consuming than comparing the object references.
528	* </p>
529	*
530	* @param appData
531	* the rule application data combining all data used for applying
532	* this rule
533	* @return Returns the unique tasks symbol map
534	*/
535	private void harmonizeEventTaskInstancesModel(RuleApplicationData appData) {
536	Console.traceln(Level.INFO,
537	"harmonizing task model of event task instances");
538	appData.getStopWatch().start("harmonizing event tasks");
539	final SymbolMap<ITaskInstance, ITask> uniqueTasks = preparationTaskHandlingStrategy
540	.createSymbolMap();
541
542	final TaskInstanceComparator comparator = preparationTaskHandlingStrategy
543	.getTaskComparator();
544
545	int unifiedTasks = 0;
546	ITask task;
547	final List<IUserSession> sessions = appData.getSessions();
548	for (int j = 0; j < sessions.size(); j++) {
549	final IUserSession session = sessions.get(j);
550
551	for (int i = 0; i < session.size(); i++) {
552	final ITaskInstance taskInstance = session.get(i);
553	task = uniqueTasks.getValue(taskInstance);
554
555	if (task == null) {
556	uniqueTasks.addSymbol(taskInstance, taskInstance.getTask());
557	appData.getUniqueTasks().add(taskInstance.getTask());
558	appData.getNumber2Task().put(
559	taskInstance.getTask().getId(),
560	taskInstance.getTask());
561	} else {
562	taskBuilder.setTask(taskInstance, task);
563	unifiedTasks++;
564	}
565	}
566	comparator.clearBuffers();
567	}
568
569	appData.getStopWatch().stop("harmonizing event tasks");
570	Console.traceln(Level.INFO, "harmonized " + unifiedTasks
571	+ " task occurrences (still " + appData.getUniqueTasks().size()
572	+ " different tasks)");
573
574	appData.getStopWatch().dumpStatistics(System.out);
575	appData.getStopWatch().reset();
576	}
577
578	/**
579	* <p>
580	* TODO clarify why this is done
581	* </p>.
582	*
583	* @param iteration the iteration
584	* @param iterationInstances the iteration instances
585	*/
586	private void harmonizeIterationInstancesModel(IIteration iteration,
587	List<IIterationInstance> iterationInstances) {
588	final List<ITask> iteratedTaskVariants = new LinkedList<ITask>();
589	final TaskInstanceComparator comparator = preparationTaskHandlingStrategy
590	.getTaskComparator();
591
592	// merge the lexically different variants of iterated task to a unique
593	// list
594	for (final IIterationInstance iterationInstance : iterationInstances) {
595	for (final ITaskInstance executionVariant : iterationInstance) {
596	final ITask candidate = executionVariant.getTask();
597
598	boolean found = false;
599	for (final ITask taskVariant : iteratedTaskVariants) {
600	if (comparator.areLexicallyEqual(taskVariant, candidate)) {
601	taskBuilder.setTask(executionVariant, taskVariant);
602	found = true;
603	break;
604	}
605	}
606
607	if (!found) {
608	iteratedTaskVariants.add(candidate);
609	}
610	}
611	}
612
613	// if there are more than one lexically different variant of iterated
614	// tasks, adapt the
615	// iteration model to be a selection of different variants. In this case
616	// also adapt
617	// the generated iteration instances to correctly contain selection
618	// instances. If there
619	// is only one variant of an iterated task, simply set this as the
620	// marked task of the
621	// iteration. In this case, the instances can be preserved as is
622	if (iteratedTaskVariants.size() > 1) {
623	final ISelection selection = taskFactory.createNewSelection();
624
625	for (final ITask variant : iteratedTaskVariants) {
626	taskBuilder.addChild(selection, variant);
627	}
628
629	taskBuilder.setMarkedTask(iteration, selection);
630
631	for (final IIterationInstance instance : iterationInstances) {
632	for (int i = 0; i < instance.size(); i++) {
633	final ISelectionInstance selectionInstance = taskFactory
634	.createNewTaskInstance(selection);
635	taskBuilder.setChild(selectionInstance, instance.get(i));
636	taskBuilder.setTaskInstance(instance, i, selectionInstance);
637	}
638	}
639	} else {
640	taskBuilder.setMarkedTask(iteration, iteratedTaskVariants.get(0));
641	}
642	}
643
644
645	/**
646	* Match as sequence.
647	*
648	* @param appData , Ruleapplication Data needed to keep track of all created
649	* tasks
650	* @param m The match to be converted into a Task
651	* @return The task of the match with an ISequence as it's root
652	*/
653	synchronized public ISequence matchAsSequence(RuleApplicationData appData,
654	Match m) {
655	final ISequence sequence = taskFactory.createNewSequence();
656	appData.newTaskCreated(sequence);
657
658	final int[] first = m.getFirstSequence().getSequence();
659	final int[] second = m.getSecondSequence().getSequence();
660
661	// Both sequences of a match are equally long
662	for (int i = 0; i < m.getFirstSequence().size(); i++) {
663
664	// Two gaps aligned to each other: Have not seen it happening so
665	// far, just to handle it
666	if ((first[i] == -1) && (second[i] == -1)) {
667	// Do nothing here.
668	}
669	// Both events are equal, we can simply add the task referring to
670	// the number
671	else if (first[i] == second[i]) {
672	taskBuilder.addChild(sequence,
673	appData.getNumber2Task().get(first[i]));
674	}
675	// We have a gap in the first sequence, we need to add the task of
676	// the second sequence as optional
677	else if ((first[i] == -1) && (second[i] != -1)) {
678	final IOptional optional = taskFactory.createNewOptional();
679	appData.newTaskCreated(optional);
680	taskBuilder.setMarkedTask(optional, appData.getNumber2Task()
681	.get(second[i]));
682	taskBuilder.addChild(sequence, optional);
683	}
684	// We have a gap in the second sequence, we need to add the task of
685	// the first sequence as optional
686	else if ((first[i] != -1) && (second[i] == -1)) {
687	final IOptional optional = taskFactory.createNewOptional();
688	appData.newTaskCreated(optional);
689	taskBuilder.setMarkedTask(optional, appData.getNumber2Task()
690	.get(first[i]));
691	taskBuilder.addChild(sequence, optional);
692	}
693	// Both tasks are not equal, we need to insert a selection here.
694	// Check if the next position is not a selection
695	else if (i < (first.length - 1)) {
696
697	if ((first[i] != second[i])
698	&& (((first[i + 1] == second[i + 1])
699	\|\| (first[i + 1] == -1) \|\| (second[i + 1] == -1)))) {
700
701	final ISelection selection = taskFactory
702	.createNewSelection();
703	appData.newTaskCreated(selection);
704	taskBuilder.addChild(selection, appData.getNumber2Task()
705	.get(first[i]));
706	taskBuilder.addChild(selection, appData.getNumber2Task()
707	.get(second[i]));
708	taskBuilder.addChild(sequence, selection);
709	} else {
710	boolean selectionfound = true;
711	final ISelection selection = taskFactory
712	.createNewSelection();
713	appData.newTaskCreated(selection);
714
715	final ISequence subsequence1 = taskFactory
716	.createNewSequence();
717	appData.newTaskCreated(subsequence1);
718
719	final ISequence subsequence2 = taskFactory
720	.createNewSequence();
721	appData.newTaskCreated(subsequence2);
722
723	taskBuilder.addChild(selection, subsequence1);
724	taskBuilder.addChild(selection, subsequence2);
725	taskBuilder.addChild(sequence, selection);
726	while ((i < (first.length - 1)) && selectionfound) {
727	selectionfound = false;
728	taskBuilder.addChild(subsequence1, appData
729	.getNumber2Task().get(first[i]));
730	taskBuilder.addChild(subsequence2, appData
731	.getNumber2Task().get(second[i]));
732	if ((first[i + 1] != second[i + 1])
733	&& (first[i + 1] != -1)
734	&& (second[i + 1] != -1)) {
735	selectionfound = true;
736	} else {
737	continue;
738	}
739	i++;
740	}
741	if ((i == (first.length - 1)) && selectionfound) {
742	taskBuilder.addChild(subsequence1, appData
743	.getNumber2Task().get(first[i]));
744	taskBuilder.addChild(subsequence2, appData
745	.getNumber2Task().get(second[i]));
746	}
747	}
748	} else {
749	if ((first[i] != second[i])) {
750
751	final ISelection selection = taskFactory
752	.createNewSelection();
753	appData.newTaskCreated(selection);
754	taskBuilder.addChild(selection, appData.getNumber2Task()
755	.get(first[i]));
756	taskBuilder.addChild(selection, appData.getNumber2Task()
757	.get(second[i]));
758	taskBuilder.addChild(sequence, selection);
759	}
760	}
761
762	}
763	return sequence;
764	}
765
766	/**
767	* <p>
768	* replaces all occurrences of all tasks provided in the set with iterations
769	* </p>.
770	*
771	* @param iteratedTasks the tasks to be replaced with iterations
772	* @param sessions the sessions in which the tasks are to be replaced
773	* @param appData the rule application data combining all data used for applying
774	* this rule
775	*/
776	private void replaceIterationsOf(Set<ITask> iteratedTasks,
777	List<IUserSession> sessions, RuleApplicationData appData) {
778	final Map<ITask, IIteration> iterations = new HashMap<ITask, IIteration>();
779	final Map<IIteration, List<IIterationInstance>> iterationInstances = new HashMap<IIteration, List<IIterationInstance>>();
780
781	for (final ITask iteratedTask : iteratedTasks) {
782
783	final IIteration iteration = taskFactory.createNewIteration();
784	appData.newTaskCreated(iteration);
785	iterations.put(iteratedTask, iteration);
786	iterationInstances.put(iteration,
787	new LinkedList<IIterationInstance>());
788	}
789
790	IIterationInstance iterationInstance;
791
792	for (final IUserSession session : sessions) {
793	int index = 0;
794	iterationInstance = null;
795
796	while (index < session.size()) {
797	// we prepared the task instances to refer to unique tasks, if
798	// they are treated
799	// as equal. Therefore, we just compare the identity of the
800	// tasks of the task
801	// instances
802	final ITask currentTask = session.get(index).getTask();
803	final IIteration iteration = iterations.get(currentTask);
804	if (iteration != null) {
805	if ((iterationInstance == null)
806	\|\| (iterationInstance.getTask() != iteration)) {
807	iterationInstance = taskFactory
808	.createNewTaskInstance(iteration);
809	iterationInstances.get(iteration)
810	.add(iterationInstance);// TODO:: Don't create
811	// TaskInstances here,
812	// use a set of tasks
813	// instead
814	taskBuilder.addTaskInstance(session, index,
815	iterationInstance);
816	index++;
817	}
818
819	taskBuilder.addChild(iterationInstance, session.get(index));
820	taskBuilder.removeTaskInstance(session, index);
821	} else {
822	if (iterationInstance != null) {
823	iterationInstance = null;
824	}
825	index++;
826	}
827	}
828	}
829
830	for (final Map.Entry<IIteration, List<IIterationInstance>> entry : iterationInstances
831	.entrySet()) {
832	harmonizeIterationInstancesModel(entry.getKey(), entry.getValue());
833	}
834	}
835
836	/**
837	* Replace matches.
838	*
839	* @param appData the app data
840	*/
841	private void replaceMatches(RuleApplicationData appData) {
842	appData.replacedOccurences = new HashMap<Integer, List<MatchOccurence>>();
843
844	final int matchSeqSize = appData.getMatchseqs().size();
845	int newThreads = nThreads;
846	if (matchSeqSize < nThreads) {
847	newThreads = matchSeqSize;
848	}
849	final ExecutorService executor = Executors
850	.newFixedThreadPool(newThreads);
851	final int interval = matchSeqSize / newThreads;
852	int rest = matchSeqSize % newThreads;
853
854	for (int i = 0; i < (matchSeqSize - interval); i += interval) {
855	int offset = 0;
856	if (rest != 0) {
857	offset = 1;
858	rest--;
859	}
860	final int from = i;
861	final int to = i + interval + offset;
862	System.out
863	.println("Replacement: Creating thread with matches from "
864	+ from + " to " + to);
865	// search each match in every other sequence
866	final ParallelMatchReplacer replacer = new ParallelMatchReplacer(
867	appData, from, to);
868	executor.execute(replacer);
869	}
870	executor.shutdown();
871	try {
872	executor.awaitTermination(2, TimeUnit.HOURS);
873	} catch (final InterruptedException e) {
874	// TODO Auto-generated catch block
875	e.printStackTrace();
876	}
877	}
878
879
880	/**
881	* <p>
882	* searches the provided sessions for task iterations. If a task is
883	* iterated, it is added to the returned set.
884	* </p>
885	*
886	* @param sessions the sessions
887	* @return a set of tasks being iterated somewhere
888	*/
889	private Set<ITask> searchIteratedTasks(List<IUserSession> sessions) {
890	final Set<ITask> iteratedTasks = new HashSet<ITask>();
891	for (final IUserSession session : sessions) {
892	for (int i = 0; i < (session.size() - 1); i++) {
893	// we prepared the task instances to refer to unique tasks, if
894	// they are treated
895	// as equal. Therefore, we just compare the identity of the
896	// tasks of the task
897	// instances
898	if (session.get(i).getTask() == session.get(i + 1).getTask()) {
899	iteratedTasks.add(session.get(i).getTask());
900	}
901	}
902	}
903	return iteratedTasks;
904	}
905
906	/**
907	* Search matches in all sessions.
908	*
909	* @param appData the app data
910	*/
911	private void searchMatchesInAllSessions(RuleApplicationData appData) {
912	Console.traceln(Level.INFO,
913	"searching for patterns occuring most with " + nThreads
914	+ " threads");
915	// Prepare parallel search of matchseqs
916
917	final int matchSeqSize = appData.getMatchseqs().size();
918	int newThreads = nThreads;
919	if (matchSeqSize < nThreads) {
920	newThreads = matchSeqSize;
921	}
922	final int interval = matchSeqSize / newThreads;
923	int rest = matchSeqSize % newThreads;
924	final ExecutorService executor = Executors.newFixedThreadPool(nThreads);
925
926	for (int i = 0; i < (matchSeqSize - interval); i += interval) {
927	int offset = 0;
928	if (rest != 0) {
929	offset = 1;
930	rest--;
931	}
932	final int from = i;
933	final int to = i + interval + offset;
934	System.out
935	.println("Match finding: Creating thread with matches from "
936	+ from + " to " + to);
937	// search each match in every other sequence
938	final ParallelMatchOcurrencesFinder finder = new ParallelMatchOcurrencesFinder(
939	appData, from, to);
940	executor.execute(finder);
941	}
942	executor.shutdown();
943	try {
944	executor.awaitTermination(2, TimeUnit.HOURS);
945	} catch (final InterruptedException e) {
946	// TODO Auto-generated catch block
947	e.printStackTrace();
948	}
949
950	}
951
952	/*
953	* (non-Javadoc)
954	*
955	* @see java.lang.Object#toString()
956	*/
957	@Override
958	public String toString() {
959	return "SequenceForTaskDetectionRuleAlignment";
960	}
961
962	/**
963	* The Class ParallelMatchOcurrencesFinder.
964	*/
965	private class ParallelMatchOcurrencesFinder implements Runnable {
966
967	/** The app data. */
968	private final RuleApplicationData appData;
969
970	/** The from. */
971	private final int from;
972
973	/** The to. */
974	private final int to;
975
976	/**
977	* Instantiates a new parallel match ocurrences finder.
978	*
979	* @param appData the app data
980	* @param from the from
981	* @param to the to
982	*/
983	ParallelMatchOcurrencesFinder(RuleApplicationData appData, int from,
984	int to) {
985	this.appData = appData;
986	this.from = from;
987	this.to = to;
988	}
989
990	/* (non-Javadoc)
991	* @see java.lang.Runnable#run()
992	*/
993	@Override
994	public void run() {
995	int count = 0;
996	final int size = to - from;
997
998	for (int i = from; i < to; i++) {
999	final Match pattern = appData.getMatchseqs().get(i);
1000	count++;
1001	RuleUtils.printProgressPercentage("Match finding progress",
1002	count, size);
1003	// Skip sequences with more 0 events (scrolls) than other
1004	// events.
1005	// Both of the pattern sequences are equally long, so the zero
1006	// counts just need to be smaller than the length of one
1007	// sequence
1008	if ((pattern.getFirstSequence().eventCount(0)
1009	+ pattern.getSecondSequence().eventCount(0) + 1) > pattern
1010	.getFirstSequence().size()) {
1011	continue;
1012	}
1013
1014	for (int j = 0; j < appData.getNumberSequences().size(); j++) {
1015	final LinkedList<Integer> startpositions = appData
1016	.getNumberSequences().get(j)
1017	.containsPattern(pattern);
1018	if (startpositions.size() > 0) {
1019	for (final Iterator<Integer> jt = startpositions
1020	.iterator(); jt.hasNext();) {
1021	final int start = jt.next();
1022	pattern.addOccurence(new MatchOccurence(start,
1023	start + pattern.size(), j));
1024	}
1025	}
1026	}
1027	}
1028	}
1029	}
1030
1031	/**
1032	* The Class ParallelMatchReplacer.
1033	*/
1034	private class ParallelMatchReplacer implements Runnable {
1035
1036	/** The app data. */
1037	private final RuleApplicationData appData;
1038
1039	/** The from. */
1040	private final int from;
1041
1042	/** The to. */
1043	private final int to;
1044
1045	/**
1046	* Instantiates a new parallel match replacer.
1047	*
1048	* @param appData the app data
1049	* @param from the from
1050	* @param to the to
1051	*/
1052	ParallelMatchReplacer(RuleApplicationData appData, int from, int to) {
1053	this.appData = appData;
1054	this.from = from;
1055	this.to = to;
1056	}
1057
1058	/* (non-Javadoc)
1059	* @see java.lang.Runnable#run()
1060	*/
1061	@Override
1062	public void run() {
1063	// TODO Cleanup
1064	// int count = 0;
1065	// int size = to - from;
1066	for (int i = from; i < to; i++) {
1067	// count++;
1068	// Every pattern consists of 2 sequences, therefore the minimum
1069	// occurrences here is 2.
1070	// We just need the sequences also occurring in other sequences
1071	// as well
1072	if (appData.getMatchseqs().get(i).occurenceCount() > 2) {
1073
1074	final ISequence task = matchAsSequence(appData, appData
1075	.getMatchseqs().get(i));
1076	invalidOccurence: for (final Iterator<MatchOccurence> it = appData
1077	.getMatchseqs().get(i).getOccurences().iterator(); it
1078	.hasNext();) {
1079	final MatchOccurence oc = it.next();
1080
1081	// Check if nothing has been replaced in the sequence we
1082	// want to replace now
1083
1084	synchronized (appData.getReplacedOccurrences()) {
1085	if (appData.getReplacedOccurrences().get(
1086	oc.getSequenceId()) == null) {
1087	appData.getReplacedOccurrences().put(
1088	oc.getSequenceId(),
1089	new LinkedList<MatchOccurence>());
1090	} else {
1091	// check if we have any replaced occurence with
1092	// indexes
1093	// smaller than ours. If so, we need to adjust
1094	// our start
1095	// and endpoints
1096	// of the replacement.
1097	// Also do a check if we have replaced this
1098	// specific
1099	// MatchOccurence in this sequence already. Jump
1100	// to the
1101	// next occurence if this is the case.
1102	// This is no more neccessary once the matches
1103	// are
1104	// harmonized.
1105	for (final Iterator<MatchOccurence> jt = appData
1106	.getReplacedOccurrences()
1107	.get(oc.getSequenceId()).iterator(); jt
1108	.hasNext();) {
1109	final MatchOccurence tmpOC = jt.next();
1110
1111	if ((oc.getStartindex() >= tmpOC
1112	.getStartindex())
1113	&& (oc.getStartindex() <= tmpOC
1114	.getEndindex())) {
1115	continue invalidOccurence;
1116	}
1117	if (oc.getEndindex() >= tmpOC
1118	.getStartindex()) {
1119	continue invalidOccurence;
1120
1121	} else if (oc.getStartindex() > tmpOC
1122	.getEndindex()) {
1123	final int diff = tmpOC.getEndindex()
1124	- tmpOC.getStartindex();
1125	// Just to be sure.
1126	if (diff > 0) {
1127	oc.setStartindex((oc
1128	.getStartindex() - diff) + 1);
1129	oc.setEndindex((oc.getEndindex() - diff) + 1);
1130	} else {
1131	Console.traceln(Level.WARNING,
1132	"End index of a Match before start. This should never happen");
1133	}
1134	}
1135	}
1136	}
1137	System.out.println("Replacing in sequence"
1138	+ oc.getSequenceId());
1139	synchronized (appData) {
1140	appData.detectedAndReplacedTasks = true;
1141	}
1142	synchronized (appData.getSessions().get(
1143	oc.getSequenceId())) {
1144	final ISequenceInstance sequenceInstances = RuleUtils
1145	.createNewSubSequenceInRange(
1146	appData.getSessions().get(
1147	oc.getSequenceId()),
1148	oc.getStartindex(),
1149	oc.getEndindex(), task,
1150	taskFactory, taskBuilder);
1151	oc.setEndindex((oc.getStartindex() + sequenceInstances
1152	.size()) - RuleUtils.missedOptionals);
1153	}
1154	}
1155	// Adjust the length of the match regarding to the
1156	// length of
1157	// instance. (OptionalInstances may be shorter)
1158
1159	synchronized (appData.getReplacedOccurrences().get(
1160	oc.getSequenceId())) {
1161	appData.getReplacedOccurrences()
1162	.get(oc.getSequenceId()).add(oc);
1163	}
1164	}
1165	}
1166	}
1167	}
1168	}
1169
1170	/**
1171	* The Class ParallelPairwiseAligner.
1172	*/
1173	private class ParallelPairwiseAligner implements Runnable {
1174
1175	/** The app data. */
1176	private final RuleApplicationData appData;
1177
1178	/** The from. */
1179	private final int from;
1180
1181	/** The to. */
1182	private final int to;
1183
1184	/**
1185	* Instantiates a new parallel pairwise aligner.
1186	*
1187	* @param appData the app data
1188	* @param from the from
1189	* @param to the to
1190	*/
1191	ParallelPairwiseAligner(RuleApplicationData appData, int from, int to) {
1192	this.appData = appData;
1193	this.from = from;
1194	this.to = to;
1195	}
1196
1197	/* (non-Javadoc)
1198	* @see java.lang.Runnable#run()
1199	*/
1200	@Override
1201	public void run() {
1202	int count = 0;
1203	final int size = to - from;
1204
1205	for (int i = from; i < to; i++) {
1206	final NumberSequence ns1 = appData.getNumberSequences().get(i);
1207	count++;
1208	RuleUtils.printProgressPercentage("Aligning Progress", count,
1209	size);
1210	for (int j = 0; j < appData.getNumberSequences().size(); j++) {
1211	final NumberSequence ns2 = appData.getNumberSequences()
1212	.get(j);
1213	if (i != j) {
1214	final AlignmentAlgorithm aa = AlignmentAlgorithmFactory
1215	.create();
1216	aa.align(ns1, ns2, appData.getSubmat(), 9);
1217	synchronized (appData.getMatchseqs()) {
1218	appData.getMatchseqs().addAll(aa.getMatches());
1219	}
1220	}
1221	}
1222	}
1223	}
1224	}
1225
1226	}

Note: See TracBrowser for help on using the repository browser.

Download in other formats: