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

Last change on this file since 1735 was 1735, checked in by rkrimmel, 10 years ago

Code cleanup
File size: 37.0 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
15package de.ugoe.cs.autoquest.tasktrees.temporalrelation;
16
17import java.io.Serializable;
18import java.util.ArrayList;
19import java.util.Collections;
20import java.util.Comparator;
21import java.util.HashMap;
22import java.util.HashSet;
23import java.util.Iterator;
24import java.util.LinkedList;
25import java.util.List;
26import java.util.Map;
27import java.util.Set;
28import java.util.concurrent.ExecutorService;
29import java.util.concurrent.Executors;
30import java.util.concurrent.TimeUnit;
31import java.util.logging.Level;
32
33import de.ugoe.cs.autoquest.tasktrees.alignment.algorithms.AlignmentAlgorithm;
34import de.ugoe.cs.autoquest.tasktrees.alignment.algorithms.AlignmentAlgorithmFactory;
35import de.ugoe.cs.autoquest.tasktrees.alignment.algorithms.Match;
36import de.ugoe.cs.autoquest.tasktrees.alignment.algorithms.MatchOccurence;
37import de.ugoe.cs.autoquest.tasktrees.alignment.algorithms.NumberSequence;
38import de.ugoe.cs.autoquest.tasktrees.alignment.matrix.ObjectDistanceSubstitionMatrix;
39import de.ugoe.cs.autoquest.tasktrees.taskequality.TaskEquality;
40import de.ugoe.cs.autoquest.tasktrees.treeifc.IIteration;
41import de.ugoe.cs.autoquest.tasktrees.treeifc.IIterationInstance;
42import de.ugoe.cs.autoquest.tasktrees.treeifc.IOptional;
43import de.ugoe.cs.autoquest.tasktrees.treeifc.ISelection;
44import de.ugoe.cs.autoquest.tasktrees.treeifc.ISelectionInstance;
45import de.ugoe.cs.autoquest.tasktrees.treeifc.ISequence;
46import de.ugoe.cs.autoquest.tasktrees.treeifc.ISequenceInstance;
47import de.ugoe.cs.autoquest.tasktrees.treeifc.ITask;
48import de.ugoe.cs.autoquest.tasktrees.treeifc.ITaskBuilder;
49import de.ugoe.cs.autoquest.tasktrees.treeifc.ITaskFactory;
50import de.ugoe.cs.autoquest.tasktrees.treeifc.ITaskInstance;
51import de.ugoe.cs.autoquest.tasktrees.treeifc.IUserSession;
52import de.ugoe.cs.autoquest.usageprofiles.SymbolMap;
53import de.ugoe.cs.util.StopWatch;
54import 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 */
73public 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                private HashMap<Integer, List<MatchOccurence>> replacedOccurences;
101
102                /** The list of all found matches */
103                private 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                        e.printStackTrace();
518                }
519        }
520
521        /**
522         * <p>
523         * harmonizes the event task instances by unifying tasks. This is done, as
524         * initially the event tasks being equal with respect to the considered task
525         * equality are distinct objects. The comparison of these distinct objects
526         * is more time consuming than comparing the object references.
527         * </p>
528         *
529         * @param appData
530         *            the rule application data combining all data used for applying
531         *            this rule
532         * @return Returns the unique tasks symbol map
533         */
534        private void harmonizeEventTaskInstancesModel(RuleApplicationData appData) {
535                Console.traceln(Level.INFO,
536                                "harmonizing task model of event task instances");
537                appData.getStopWatch().start("harmonizing event tasks");
538                final SymbolMap<ITaskInstance, ITask> uniqueTasks = preparationTaskHandlingStrategy
539                                .createSymbolMap();
540
541                final TaskInstanceComparator comparator = preparationTaskHandlingStrategy
542                                .getTaskComparator();
543
544                int unifiedTasks = 0;
545                ITask task;
546                final List<IUserSession> sessions = appData.getSessions();
547                for (int j = 0; j < sessions.size(); j++) {
548                        final IUserSession session = sessions.get(j);
549
550                        for (int i = 0; i < session.size(); i++) {
551                                final ITaskInstance taskInstance = session.get(i);
552                                task = uniqueTasks.getValue(taskInstance);
553
554                                if (task == null) {
555                                        uniqueTasks.addSymbol(taskInstance, taskInstance.getTask());
556                                        appData.getUniqueTasks().add(taskInstance.getTask());
557                                        appData.getNumber2Task().put(
558                                                        taskInstance.getTask().getId(),
559                                                        taskInstance.getTask());
560                                } else {
561                                        taskBuilder.setTask(taskInstance, task);
562                                        unifiedTasks++;
563                                }
564                        }
565                        comparator.clearBuffers();
566                }
567
568                appData.getStopWatch().stop("harmonizing event tasks");
569                Console.traceln(Level.INFO, "harmonized " + unifiedTasks
570                                + " task occurrences (still " + appData.getUniqueTasks().size()
571                                + " different tasks)");
572
573                appData.getStopWatch().dumpStatistics(System.out);
574                appData.getStopWatch().reset();
575        }
576
577        /**
578         * <p>
579         * TODO clarify why this is done (in fact, ask Patrick Harms)
580         * </p>.
581         *
582         * @param iteration the iteration
583         * @param iterationInstances the iteration instances
584         */
585        private void harmonizeIterationInstancesModel(IIteration iteration,
586                        List<IIterationInstance> iterationInstances) {
587                final List<ITask> iteratedTaskVariants = new LinkedList<ITask>();
588                final TaskInstanceComparator comparator = preparationTaskHandlingStrategy
589                                .getTaskComparator();
590
591                // merge the lexically different variants of iterated task to a unique
592                // list
593                for (final IIterationInstance iterationInstance : iterationInstances) {
594                        for (final ITaskInstance executionVariant : iterationInstance) {
595                                final ITask candidate = executionVariant.getTask();
596
597                                boolean found = false;
598                                for (final ITask taskVariant : iteratedTaskVariants) {
599                                        if (comparator.areLexicallyEqual(taskVariant, candidate)) {
600                                                taskBuilder.setTask(executionVariant, taskVariant);
601                                                found = true;
602                                                break;
603                                        }
604                                }
605
606                                if (!found) {
607                                        iteratedTaskVariants.add(candidate);
608                                }
609                        }
610                }
611
612                // if there are more than one lexically different variant of iterated
613                // tasks, adapt the
614                // iteration model to be a selection of different variants. In this case
615                // also adapt
616                // the generated iteration instances to correctly contain selection
617                // instances. If there
618                // is only one variant of an iterated task, simply set this as the
619                // marked task of the
620                // iteration. In this case, the instances can be preserved as is
621                if (iteratedTaskVariants.size() > 1) {
622                        final ISelection selection = taskFactory.createNewSelection();
623
624                        for (final ITask variant : iteratedTaskVariants) {
625                                taskBuilder.addChild(selection, variant);
626                        }
627
628                        taskBuilder.setMarkedTask(iteration, selection);
629
630                        for (final IIterationInstance instance : iterationInstances) {
631                                for (int i = 0; i < instance.size(); i++) {
632                                        final ISelectionInstance selectionInstance = taskFactory
633                                                        .createNewTaskInstance(selection);
634                                        taskBuilder.setChild(selectionInstance, instance.get(i));
635                                        taskBuilder.setTaskInstance(instance, i, selectionInstance);
636                                }
637                        }
638                } else {
639                        taskBuilder.setMarkedTask(iteration, iteratedTaskVariants.get(0));
640                }
641        }
642
643
644        /**
645         * Match as sequence.
646         *
647         * @param appData               RuleApplicationData needed to keep track of all created tasks
648         * @param m                             The match to be converted into a Task
649         * @return                              The task of the match with an ISequence as its root
650         */
651        synchronized public ISequence matchAsSequence(RuleApplicationData appData,
652                        Match m) {
653                final ISequence sequence = taskFactory.createNewSequence();
654                appData.newTaskCreated(sequence);
655
656                final int[] first = m.getFirstSequence().getSequence();
657                final int[] second = m.getSecondSequence().getSequence();
658
659                // Both sequences of a match are equally long
660                for (int i = 0; i < m.getFirstSequence().size(); i++) {
661
662                        // Two gaps aligned to each other: Have not seen it happening so
663                        // far, just to handle it
664                        if ((first[i] == -1) && (second[i] == -1)) {
665                                // Do nothing here.
666                        }
667                        // Both events are equal, we can simply add the task referring to
668                        // the number
669                        else if (first[i] == second[i]) {
670                                taskBuilder.addChild(sequence,
671                                                appData.getNumber2Task().get(first[i]));
672                        }
673                        // We have a gap in the first sequence, we need to add the task of
674                        // the second sequence as optional
675                        else if ((first[i] == -1) && (second[i] != -1)) {
676                                final IOptional optional = taskFactory.createNewOptional();
677                                appData.newTaskCreated(optional);
678                                taskBuilder.setMarkedTask(optional, appData.getNumber2Task()
679                                                .get(second[i]));
680                                taskBuilder.addChild(sequence, optional);
681                        }
682                        // We have a gap in the second sequence, we need to add the task of
683                        // the first sequence as optional
684                        else if ((first[i] != -1) && (second[i] == -1)) {
685                                final IOptional optional = taskFactory.createNewOptional();
686                                appData.newTaskCreated(optional);
687                                taskBuilder.setMarkedTask(optional, appData.getNumber2Task()
688                                                .get(first[i]));
689                                taskBuilder.addChild(sequence, optional);
690                        }
691                        // Both tasks are not equal, we need to insert a selection here.
692                        // Now things get complicated. We first need to check
693                        // if the next position is not a selection. Then we can just create a selection
694                        // of the both Tasks
695                        // In the other case (more than one selection following this selection), we want to
696                        // create a selection of sequences where each sequence gets the corresponding task of
697                        // the its sequence in the pattern.
698                        //
699                        else if (i < (first.length - 1)) {
700
701                                if ((first[i] != second[i])
702                                                && (((first[i + 1] == second[i + 1])
703                                                                || (first[i + 1] == -1) || (second[i + 1] == -1)))) {
704
705                                        final ISelection selection = taskFactory
706                                                        .createNewSelection();
707                                        appData.newTaskCreated(selection);
708                                        taskBuilder.addChild(selection, appData.getNumber2Task()
709                                                        .get(first[i]));
710                                        taskBuilder.addChild(selection, appData.getNumber2Task()
711                                                        .get(second[i]));
712                                        taskBuilder.addChild(sequence, selection);
713                                } else {
714                                        boolean selectionfound = true;
715                                        final ISelection selection = taskFactory
716                                                        .createNewSelection();
717                                        appData.newTaskCreated(selection);
718
719                                        final ISequence subsequence1 = taskFactory
720                                                        .createNewSequence();
721                                        appData.newTaskCreated(subsequence1);
722
723                                        final ISequence subsequence2 = taskFactory
724                                                        .createNewSequence();
725                                        appData.newTaskCreated(subsequence2);
726
727                                        taskBuilder.addChild(selection, subsequence1);
728                                        taskBuilder.addChild(selection, subsequence2);
729                                        taskBuilder.addChild(sequence, selection);
730                                        while ((i < (first.length - 1)) && selectionfound) {
731                                                selectionfound = false;
732                                                taskBuilder.addChild(subsequence1, appData
733                                                                .getNumber2Task().get(first[i]));
734                                                taskBuilder.addChild(subsequence2, appData
735                                                                .getNumber2Task().get(second[i]));
736                                                if ((first[i + 1] != second[i + 1])
737                                                                && (first[i + 1] != -1)
738                                                                && (second[i + 1] != -1)) {
739                                                        selectionfound = true;
740                                                } else {
741                                                        continue;
742                                                }
743                                                i++;
744                                        }
745                                        if ((i == (first.length - 1)) && selectionfound) {
746                                                taskBuilder.addChild(subsequence1, appData
747                                                                .getNumber2Task().get(first[i]));
748                                                taskBuilder.addChild(subsequence2, appData
749                                                                .getNumber2Task().get(second[i]));
750                                        }
751                                }
752                        } else {
753                                if ((first[i] != second[i])) {
754
755                                        final ISelection selection = taskFactory
756                                                        .createNewSelection();
757                                        appData.newTaskCreated(selection);
758                                        taskBuilder.addChild(selection, appData.getNumber2Task()
759                                                        .get(first[i]));
760                                        taskBuilder.addChild(selection, appData.getNumber2Task()
761                                                        .get(second[i]));
762                                        taskBuilder.addChild(sequence, selection);
763                                }
764                        }
765
766                }
767                return sequence;
768        }
769
770        /**
771         * <p>
772         * replaces all occurrences of all tasks provided in the set with iterations
773         * </p>.
774         *
775         * @param iteratedTasks            the tasks to be replaced with iterations
776         * @param sessions            the sessions in which the tasks are to be replaced
777         * @param appData            the rule application data combining all data used for applying
778         *            this rule
779         */
780        private void replaceIterationsOf(Set<ITask> iteratedTasks,
781                        List<IUserSession> sessions, RuleApplicationData appData) {
782                final Map<ITask, IIteration> iterations = new HashMap<ITask, IIteration>();
783                final Map<IIteration, List<IIterationInstance>> iterationInstances = new HashMap<IIteration, List<IIterationInstance>>();
784
785                for (final ITask iteratedTask : iteratedTasks) {
786
787                        final IIteration iteration = taskFactory.createNewIteration();
788                        appData.newTaskCreated(iteration);
789                        iterations.put(iteratedTask, iteration);
790                        iterationInstances.put(iteration,
791                                        new LinkedList<IIterationInstance>());
792                }
793
794                IIterationInstance iterationInstance;
795
796                for (final IUserSession session : sessions) {
797                        int index = 0;
798                        iterationInstance = null;
799
800                        while (index < session.size()) {
801                                // we prepared the task instances to refer to unique tasks, if
802                                // they are treated
803                                // as equal. Therefore, we just compare the identity of the
804                                // tasks of the task
805                                // instances
806                                final ITask currentTask = session.get(index).getTask();
807                                final IIteration iteration = iterations.get(currentTask);
808                                if (iteration != null) {
809                                        if ((iterationInstance == null)
810                                                        || (iterationInstance.getTask() != iteration)) {
811                                                iterationInstance = taskFactory
812                                                                .createNewTaskInstance(iteration);
813                                                iterationInstances.get(iteration)
814                                                                .add(iterationInstance);// TODO:: Don't create
815                                                // TaskInstances here,
816                                                // use a set of tasks
817                                                // instead
818                                                taskBuilder.addTaskInstance(session, index,
819                                                                iterationInstance);
820                                                index++;
821                                        }
822
823                                        taskBuilder.addChild(iterationInstance, session.get(index));
824                                        taskBuilder.removeTaskInstance(session, index);
825                                } else {
826                                        if (iterationInstance != null) {
827                                                iterationInstance = null;
828                                        }
829                                        index++;
830                                }
831                        }
832                }
833
834                for (final Map.Entry<IIteration, List<IIterationInstance>> entry : iterationInstances
835                                .entrySet()) {
836                        harmonizeIterationInstancesModel(entry.getKey(), entry.getValue());
837                }
838        }
839
840        /**
841         * Replace matches.
842         *
843         * @param appData the app data
844         */
845        private void replaceMatches(RuleApplicationData appData) {
846                appData.setReplacedOccurences(new HashMap<Integer, List<MatchOccurence>>());
847
848                final int matchSeqSize = appData.getMatchseqs().size();
849                int newThreads = nThreads;
850                if (matchSeqSize < nThreads) {
851                        newThreads = matchSeqSize;
852                }
853                final ExecutorService executor = Executors
854                                .newFixedThreadPool(newThreads);
855                final int interval = matchSeqSize / newThreads;
856                int rest = matchSeqSize % newThreads;
857
858                for (int i = 0; i < (matchSeqSize - interval); i += interval) {
859                        int offset = 0;
860                        if (rest != 0) {
861                                offset = 1;
862                                rest--;
863                        }
864                        final int from = i;
865                        final int to = i + interval + offset;
866                        System.out
867                        .println("Replacement: Creating thread with matches from "
868                                        + from + " to " + to);
869                        // search each match in every other sequence
870                        final ParallelMatchReplacer replacer = new ParallelMatchReplacer(
871                                        appData, from, to);
872                        executor.execute(replacer);
873                }
874                executor.shutdown();
875                try {
876                        executor.awaitTermination(2, TimeUnit.HOURS);
877                } catch (final InterruptedException e) {
878                        // TODO Auto-generated catch block
879                        e.printStackTrace();
880                }
881        }
882
883
884        /**
885         * <p>
886         * searches the provided sessions for task iterations. If a task is
887         * iterated, it is added to the returned set.
888         * </p>
889         *
890         * @param sessions the sessions
891         * @return a set of tasks being iterated somewhere
892         */
893        private Set<ITask> searchIteratedTasks(List<IUserSession> sessions) {
894                final Set<ITask> iteratedTasks = new HashSet<ITask>();
895                for (final IUserSession session : sessions) {
896                        for (int i = 0; i < (session.size() - 1); i++) {
897                                // we prepared the task instances to refer to unique tasks, if
898                                // they are treated
899                                // as equal. Therefore, we just compare the identity of the
900                                // tasks of the task
901                                // instances
902                                if (session.get(i).getTask() == session.get(i + 1).getTask()) {
903                                        iteratedTasks.add(session.get(i).getTask());
904                                }
905                        }
906                }
907                return iteratedTasks;
908        }
909
910        /**
911         * Search matches in all sessions.
912         *
913         * @param appData the app data
914         */
915        private void searchMatchesInAllSessions(RuleApplicationData appData) {
916                Console.traceln(Level.INFO,
917                                "searching for patterns occuring most with " + nThreads
918                                                + " threads");
919                // Prepare parallel search of matchseqs
920                final int matchSeqSize = appData.getMatchseqs().size();
921                int newThreads = nThreads;
922                if (matchSeqSize < nThreads) {
923                        newThreads = matchSeqSize;
924                }
925                final int interval = matchSeqSize / newThreads;
926                int rest = matchSeqSize % newThreads;
927                final ExecutorService executor = Executors.newFixedThreadPool(nThreads);
928
929                for (int i = 0; i < (matchSeqSize - interval); i += interval) {
930                        int offset = 0;
931                        if (rest != 0) {
932                                offset = 1;
933                                rest--;
934                        }
935                        final int from = i;
936                        final int to = i + interval + offset;
937                        System.out
938                        .println("Match finding: Creating thread with matches from "
939                                        + from + " to " + to);
940                        // search each match in every other sequence
941                        final ParallelMatchOcurrencesFinder finder = new ParallelMatchOcurrencesFinder(
942                                        appData, from, to);
943                        executor.execute(finder);
944                }
945                executor.shutdown();
946                try {
947                        executor.awaitTermination(2, TimeUnit.HOURS);
948                } catch (final InterruptedException e) {
949                        // TODO Auto-generated catch block
950                        e.printStackTrace();
951                }
952
953        }
954
955        /*
956         * (non-Javadoc)
957         *
958         * @see java.lang.Object#toString()
959         */
960        @Override
961        public String toString() {
962                return "SequenceForTaskDetectionRuleAlignment";
963        }
964
965        /**
966         * The Class ParallelMatchOcurrencesFinder.
967         */
968        private class ParallelMatchOcurrencesFinder implements Runnable {
969               
970                /** The app data. */
971                private final RuleApplicationData appData;
972               
973                /** The from. */
974                private final int from;
975               
976                /** The to. */
977                private final int to;
978
979                /**
980                 * Instantiates a new parallel match ocurrences finder.
981                 *
982                 * @param appData the app data
983                 * @param from the from
984                 * @param to the to
985                 */
986                ParallelMatchOcurrencesFinder(RuleApplicationData appData, int from,
987                                int to) {
988                        this.appData = appData;
989                        this.from = from;
990                        this.to = to;
991                }
992
993                /* (non-Javadoc)
994                 * @see java.lang.Runnable#run()
995                 */
996                @Override
997                public void run() {
998                        int count = 0;
999                        final int size = to - from;
1000
1001                        for (int i = from; i < to; i++) {
1002                                final Match pattern = appData.getMatchseqs().get(i);
1003                                count++;
1004                                RuleUtils.printProgressPercentage("Match finding progress",
1005                                                count, size);
1006                                // Skip sequences with more 0 events (scrolls) than other
1007                                // events.
1008                                // Both of the pattern sequences are equally long, so the zero
1009                                // counts just need to be smaller than the length of one
1010                                // sequence
1011                                if ((pattern.getFirstSequence().eventCount(0)
1012                                                + pattern.getSecondSequence().eventCount(0) + 1) > pattern
1013                                                .getFirstSequence().size()) {
1014                                        continue;
1015                                }
1016
1017                                for (int j = 0; j < appData.getNumberSequences().size(); j++) {
1018                                        final LinkedList<Integer> startpositions = appData
1019                                                        .getNumberSequences().get(j)
1020                                                        .containsPattern(pattern);
1021                                        if (startpositions.size() > 0) {
1022                                                for (final Iterator<Integer> jt = startpositions
1023                                                                .iterator(); jt.hasNext();) {
1024                                                        final int start = jt.next();
1025                                                        pattern.addOccurence(new MatchOccurence(start,
1026                                                                        start + pattern.size(), j));
1027                                                }
1028                                        }
1029                                }
1030                        }
1031                }
1032        }
1033
1034        /**
1035         * The Class ParallelMatchReplacer.
1036         */
1037        private class ParallelMatchReplacer implements Runnable {
1038
1039                /** The app data. */
1040                private final RuleApplicationData appData;
1041               
1042                /** The from. */
1043                private final int from;
1044               
1045                /** The to. */
1046                private final int to;
1047
1048                /**
1049                 * Instantiates a new parallel match replacer.
1050                 *
1051                 * @param appData the app data
1052                 * @param from the from
1053                 * @param to the to
1054                 */
1055                ParallelMatchReplacer(RuleApplicationData appData, int from, int to) {
1056                        this.appData = appData;
1057                        this.from = from;
1058                        this.to = to;
1059                }
1060
1061                /* (non-Javadoc)
1062                 * @see java.lang.Runnable#run()
1063                 */
1064                @Override
1065                public void run() {
1066                        // TODO Cleanup
1067                        // int count = 0;
1068                        // int size = to - from;
1069                        for (int i = from; i < to; i++) {
1070                                // count++;
1071                                // Every pattern consists of 2 sequences, therefore the minimum
1072                                // occurrences here is 2.
1073                                // We just need the sequences also occurring in other sequences
1074                                // as well
1075                                if (appData.getMatchseqs().get(i).occurenceCount() > 2) {
1076
1077                                        final ISequence task = matchAsSequence(appData, appData
1078                                                        .getMatchseqs().get(i));
1079                                        invalidOccurence: for (final Iterator<MatchOccurence> it = appData
1080                                                        .getMatchseqs().get(i).getOccurences().iterator(); it
1081                                                        .hasNext();) {
1082                                                final MatchOccurence oc = it.next();
1083
1084                                                // Check if nothing has been replaced in the sequence we
1085                                                // want to replace now
1086
1087                                                synchronized (appData.getReplacedOccurrences()) {
1088                                                        if (appData.getReplacedOccurrences().get(
1089                                                                        oc.getSequenceId()) == null) {
1090                                                                appData.getReplacedOccurrences().put(
1091                                                                                oc.getSequenceId(),
1092                                                                                new LinkedList<MatchOccurence>());
1093                                                        } else {
1094                                                                // check if we have any replaced occurence with
1095                                                                // indexes
1096                                                                // smaller than ours. If so, we need to adjust
1097                                                                // our start
1098                                                                // and endpoints
1099                                                                // of the replacement.
1100                                                                // Also do a check if we have replaced this
1101                                                                // specific
1102                                                                // MatchOccurence in this sequence already. Jump
1103                                                                // to the
1104                                                                // next occurence if this is the case.
1105                                                                // This is no more neccessary once the matches
1106                                                                // are
1107                                                                // harmonized.
1108                                                                for (final Iterator<MatchOccurence> jt = appData
1109                                                                                .getReplacedOccurrences()
1110                                                                                .get(oc.getSequenceId()).iterator(); jt
1111                                                                                .hasNext();) {
1112                                                                        final MatchOccurence tmpOC = jt.next();
1113
1114                                                                        if ((oc.getStartindex() >= tmpOC
1115                                                                                        .getStartindex())
1116                                                                                        && (oc.getStartindex() <= tmpOC
1117                                                                                        .getEndindex())) {
1118                                                                                continue invalidOccurence;
1119                                                                        }
1120                                                                        if (oc.getEndindex() >= tmpOC
1121                                                                                        .getStartindex()) {
1122                                                                                continue invalidOccurence;
1123
1124                                                                        } else if (oc.getStartindex() > tmpOC
1125                                                                                        .getEndindex()) {
1126                                                                                final int diff = tmpOC.getEndindex()
1127                                                                                                - tmpOC.getStartindex();
1128                                                                                // Just to be sure.
1129                                                                                if (diff > 0) {
1130                                                                                        oc.setStartindex((oc
1131                                                                                                        .getStartindex() - diff) + 1);
1132                                                                                        oc.setEndindex((oc.getEndindex() - diff) + 1);
1133                                                                                } else {
1134                                                                                        Console.traceln(Level.WARNING,
1135                                                                                                        "End index of a Match before start. This should never happen");
1136                                                                                }
1137                                                                        }
1138                                                                }
1139                                                        }
1140                                                        synchronized (appData) {
1141                                                                appData.detectedAndReplacedTasks = true;
1142                                                        }
1143                                                        synchronized (appData.getSessions().get(
1144                                                                        oc.getSequenceId())) {
1145                                                                final ISequenceInstance sequenceInstances = RuleUtils
1146                                                                                .createNewSubSequenceInRange(
1147                                                                                                appData.getSessions().get(
1148                                                                                                                oc.getSequenceId()),
1149                                                                                                                oc.getStartindex(),
1150                                                                                                                oc.getEndindex(), task,
1151                                                                                                                taskFactory, taskBuilder);
1152                                                                oc.setEndindex((oc.getStartindex() + sequenceInstances
1153                                                                                .size()) - RuleUtils.missedOptionals);
1154                                                        }
1155                                                }
1156                                                // Adjust the length of the match regarding to the
1157                                                // length of
1158                                                // instance. (OptionalInstances may be shorter)
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.