Changeset 1855 for trunk/autoquest-core-tasktrees/src/main/java/de/ugoe

Timestamp:

12/23/14 11:49:50 (10 years ago)

Author:

pharms

Message:

• refactoring to use correct terminology
• implemented selection of which detected subsequence to replace first to be deterministic
• corrected selection of shorter or longer detected subsequences if the shorter one is part of the longer one

File:

• trunk/autoquest-core-tasktrees/src/main/java/de/ugoe/cs/autoquest/tasktrees/temporalrelation/SequenceForTaskDetectionRule.java (modified) (39 diffs)

trunk/autoquest-core-tasktrees/src/main/java/de/ugoe/cs/autoquest/tasktrees/temporalrelation/SequenceForTaskDetectionRule.java

@@ -15 +15 @@
 package de.ugoe.cs.autoquest.tasktrees.temporalrelation;
 
+import java.util.ArrayList;
 import java.util.HashMap;
 import java.util.HashSet;
+import java.util.IdentityHashMap;
 import java.util.Iterator;
 import java.util.LinkedList;
 import java.util.List;
+import java.util.ListIterator;
 import java.util.Map;
 import java.util.Set;
@@ -25 +28 @@
 
 import de.ugoe.cs.autoquest.tasktrees.taskequality.TaskEquality;
+import de.ugoe.cs.autoquest.tasktrees.temporalrelation.utils.DebuggingHelper;
 import de.ugoe.cs.autoquest.tasktrees.treeifc.IIteration;
 import de.ugoe.cs.autoquest.tasktrees.treeifc.IIterationInstance;
@@ -183 +187 @@
         appData.getStopWatch().start("harmonizing event tasks");
 
-        SymbolMap<ITaskInstance, ITask> uniqueTasks =
-            preparationTaskHandlingStrategy.createSymbolMap();
-        TaskInstanceComparator comparator = preparationTaskHandlingStrategy.getTaskComparator();
+        SymbolMap<ITask, ITask> uniqueTasks = preparationTaskHandlingStrategy.createSymbolMap();
+        TaskComparator comparator = preparationTaskHandlingStrategy.getTaskComparator();
         
         int unifiedTasks = 0;
@@ -194 +197 @@
             Console.traceln(Level.FINE, "handling " + (++sessionNo) + ". " + session);
             for (ITaskInstance taskInstance : session) {
-                task = uniqueTasks.getValue(taskInstance);
+                task = uniqueTasks.getValue(taskInstance.getTask());
                 
                 if (task == null) {
-                    uniqueTasks.addSymbol(taskInstance, taskInstance.getTask());
+                    uniqueTasks.addSymbol(taskInstance.getTask(), taskInstance.getTask());
                 }
                 else {
@@ -374 +377 @@
     {
         List<ITask> iteratedTaskVariants = new LinkedList<ITask>();
-        TaskInstanceComparator comparator = preparationTaskHandlingStrategy.getTaskComparator();
+        TaskComparator comparator = preparationTaskHandlingStrategy.getTaskComparator();
         
         // merge the lexically different variants of iterated task to a unique list 
@@ -432 +435 @@
         appData.getStopWatch().start("detecting tasks");
         
-        getSequencesOccuringMostOften(appData);
-
+        getSubsequencesOccuringMostOften(appData);
+        
         appData.getStopWatch().stop("detecting tasks");
+        appData.getStopWatch().start("sorting tasks");
+        
+        removeInterleavingTasks(appData);
+
+        appData.getStopWatch().stop("sorting tasks");
         appData.getStopWatch().start("replacing tasks");
         
@@ -440 +448 @@
         
         appData.getStopWatch().stop("replacing tasks");
-        Console.traceln(Level.INFO, "detected and replaced " + appData.getLastFoundTasks().size() +
-                        " tasks occuring " + appData.getLastFoundTasks().getOccurrenceCount() +
+        Console.traceln(Level.INFO, "detected and replaced " + appData.getLastFoundSubsequences().size() +
+                        " tasks occuring " + appData.getLastFoundSubsequences().getOccurrenceCount() +
                         " times");
     }
@@ -448 +456 @@
      * @param appData the rule application data combining all data used for applying this rule
      */
-    private void getSequencesOccuringMostOften(RuleApplicationData appData) {
-        Console.traceln(Level.FINE, "determining most prominent tasks");
-
-        Tasks tasks;
+    private void getSubsequencesOccuringMostOften(RuleApplicationData appData) {
+        Console.traceln(Level.FINER, "determining most prominent subsequences");
+
+        Subsequences subsequences;
         boolean createNewTrie = (appData.getLastTrie() == null) ||
             appData.detectedAndReplacedTasks(); // tree has changed
@@ -460 +468 @@
             }
             
-            MaxCountAndLongestTasksFinder finder = new MaxCountAndLongestTasksFinder();
+            MaxCountAndLongestSubsequencesFinder finder = new MaxCountAndLongestSubsequencesFinder();
             appData.getLastTrie().process(finder);
         
-            tasks = finder.getFoundTasks();
+            subsequences = finder.getFoundSubsequences();
             
             createNewTrie = false;
             
-            for (List<ITaskInstance> task : tasks) {
-                if (task.size() >= appData.getTrainedSequenceLength()) {
+            for (Subsequence subsequence : subsequences) {
+                if (subsequence.size() >= appData.getTrainedSubsequenceLength()) {
                     // Trie must be recreated with a longer sequence length to be sure that
                     // the found sequences occurring most often are found in their whole length
-                    appData.setTrainedSequenceLength(appData.getTrainedSequenceLength() + 1);
+                    appData.setTrainedSubsequenceLength(appData.getTrainedSubsequenceLength() + 1);
                     createNewTrie = true;
                     break;
@@ -536 +544 @@
         dumper.dumpCounters();*/
         
-        appData.setLastFoundTasks(tasks);
-
-        Console.traceln(Level.FINE, "found " + appData.getLastFoundTasks().size() + " tasks " +
-                        "occurring " + appData.getLastFoundTasks().getOccurrenceCount() + " times");
+        appData.setLastFoundSubsequences(subsequences);
+
+        Console.traceln(Level.FINE, "found " + appData.getLastFoundSubsequences().size() +
+                        " tasks occurring " +
+                        appData.getLastFoundSubsequences().getOccurrenceCount() + " times");
     }
 
@@ -546 +555 @@
      */
     private void createNewTrie(RuleApplicationData appData) {
-        Console.traceln(Level.FINER, "training trie with a maximum sequence length of " +
-                        appData.getTrainedSequenceLength());
+        Console.traceln(Level.FINEST, "training trie with a maximum sequence length of " +
+                        appData.getTrainedSubsequenceLength());
 
         appData.getStopWatch().start("training trie");
@@ -557 +566 @@
     
         appData.getLastTrie().trainSessions
-            (appData.getSessions(), appData.getTrainedSequenceLength());
+            (appData.getSessions(), appData.getTrainedSubsequenceLength());
         
         appData.getStopWatch().stop("training trie");
+    }
+
+    /**
+     * from the last found tasks, sort out those that interleave with each other as for them always
+     * the same replacement order needs to be taken.
+     */
+    private void removeInterleavingTasks(RuleApplicationData appData) {
+        // >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
+        // >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> TEST IMPLEMENTATION >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
+        // dumpSortedCollectionOfSubsequences
+        //     ("found task", appData.getLastFoundSubsequences().subsequences);
+        // <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
+        // <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< TEST IMPLEMENTATION <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
+
+        List<InterleavingSubsequence> interleavings;
+        
+        do {
+            interleavings = getInterleavings(appData.getLastFoundSubsequences(), appData);
+            
+            if (interleavings.size() > 0) {
+                // dumpSorted(interleavings);
+
+                // Console.traceln(Level.FINEST, "found " + interleavings.size() + " subsequences " +
+                //                 "--> checking for most real interleavings");
+                
+                // we found interleaving subsequences. We need to decide for them, which to replace
+                // first. For this, we need to remove some of them from the list of detected
+                // subsequences in an ordered way to always have the same prioritization for
+                // replacements. The ones to be removed are those with most interleavings.
+                interleavings = getMostIntensiveInterleavings(interleavings);
+                
+                //dumpSorted(interleavings);
+                
+                if (interleavings.size() == 1) {
+                    // Console.traceln(Level.FINEST, "found one most interleaving subsequence " +
+                    //                 "--> removing it and checking for further interleavings");
+
+                    // we have exactly one most interleaving detected subsequence. In this case,
+                    // we remove it from the list of found subsequences and check again, if their
+                    // are remaining interleavings. If not, we have the final list of non
+                    // interleaving subsequences to be replaced. The order or their replacement
+                    // doesn't matter as they are not interleaving.
+                    appData.getLastFoundSubsequences().remove
+                        (interleavings.get(0).getSubsequence());
+                    
+                    continue;
+                }
+                else if (interleavings.size() == 0) {
+                    // this should never happen
+                    throw new RuntimeException("Implementation error: don't know how I got here");
+                }
+                
+                // Console.traceln(Level.FINEST, "found " + interleavings.size() + " most " +
+                //                 "interleaving subsequences --> checking which are most often a " +
+                //                 "successor");
+
+                // there are several subsequences with the same amount of interleavings.
+                // Check which of them is the most often a successor. This should be removed.
+                interleavings = getMostInterleavingsAsSuccessor(interleavings);
+                
+                // dumpSorted(interleavings);
+
+                if (interleavings.size() == 1) {
+                    //  Console.traceln(Level.FINEST, "found one interleaving subsequence being most " +
+                    //                  "often a successor --> removing it and checking for further " +
+                    //                  "interleavings");
+
+                    // we have exactly one interleaving subsequence that is most often a successor
+                    // of the others. Remove it and try again to see if sufficient interleavings
+                    // were cleared.
+                    appData.getLastFoundSubsequences().remove
+                        (interleavings.get(0).getSubsequence());
+                    
+                    continue;
+                }
+                else if (interleavings.size() == 0) {
+                    // this should never happen
+                    throw new RuntimeException("Implementation error: don't know how I got here");
+                }
+                
+                // Console.traceln(Level.FINEST, "found " + interleavings.size() +
+                //                 " most interleaving subsequences being most often a successor " +
+                //                 "--> checking which is most seldom a predecessor");
+
+                // there are several subsequences with the same amount of interleavings being also
+                // the same times a successor of another subsequence. Hence, check which of them is
+                // the least often a predecessor. This should be removed.
+                interleavings = getLeastInterleavingsAsPredecessor(interleavings);
+                
+                //dumpSorted(interleavings);
+
+                if (interleavings.size() == 1) {
+                    // Console.traceln(Level.FINEST, "found one interleaving subsequence being most " +
+                    //                 "often a successor and most seldom a predecessor --> " +
+                    //                 "removing it and checking for further interleavings");
+
+                    // we have exactly one interleaving subsequence that is most often a successor
+                    // and most seldom a predecessor of the others. Remove it and try again to see
+                    // if sufficient interleavings were cleared.
+                    appData.getLastFoundSubsequences().remove
+                        (interleavings.get(0).getSubsequence());
+                    
+                    continue;
+                }
+                else if (interleavings.size() == 0) {
+                    // this should never happen
+                    throw new RuntimeException("Implementation error: don't know how I got here");
+                }
+                
+                // the remaining subsequences are interleaving the same amount of times and are
+                // used the same amount of times as successors and as predecessors by all other
+                // detected interleaving subsequences. Now lets check, which of them is mostly used
+                // as successor and most seldom used as predecessor only considering the remaining
+                // subsequences. If some of them do not interfere with the others, remove them and
+                // try again to see if sufficient interleavings were cleared.
+                
+                // Console.traceln(Level.FINEST, "found " + interleavings.size() +
+                //                 " most interleaving subsequences being most often a successor " +
+                //                 "and most seldom a predecessor --> removing collision being not " +
+                //                 "between themselves");
+
+                interleavings = removeCollisionsOfOtherSubsequences(interleavings);
+                
+                // dumpSorted(interleavings);
+                
+                // Console.traceln(Level.FINEST, "removed collisions of other subsequences not " +
+                //                 "belonging to the remaining interleaving subsequences --> " +
+                //                 "checking of the remaining interleaving are most often a " +
+                //                 "successor of another one");
+                
+                interleavings = getMostInterleavingsAsSuccessor(interleavings);
+                interleavings = removeCollisionsOfOtherSubsequences(interleavings);
+                
+                // dumpSorted(interleavings);
+
+                if (interleavings.size() == 1) {
+                    // Console.traceln(Level.FINEST, "found one interleaving subsequence being most " +
+                    //                 "often a successor in comparison to the other remaining " +
+                    //                 "interleavings --> removing it and checking for further " +
+                    //                 "interleavings");
+
+                    appData.getLastFoundSubsequences().remove
+                        (interleavings.get(0).getSubsequence());
+                    
+                    continue;
+                }
+                else if (interleavings.size() == 0) {
+                    // this should never happen
+                    throw new RuntimeException("Implementation error: don't know how I got here");
+                }
+                
+                // Console.traceln(Level.FINEST, "found " + interleavings.size() +
+                //                 " most interleaving subsequences being most often a successor in " +
+                //                 "comparison to the other remaining interleavings --> checking " +
+                //                 "which is most seldom a predecessor");
+
+                interleavings = getLeastInterleavingsAsPredecessor(interleavings);
+                interleavings = removeCollisionsOfOtherSubsequences(interleavings);
+                
+                // dumpSorted(interleavings);
+
+                if (interleavings.size() == 1) {
+                    // Console.traceln(Level.FINEST, "found one interleaving subsequence being most " +
+                    //                 "often a successor and most seldom a predecessor in " +
+                    //                 "comparison to the other remaining interleavings --> " +
+                    //                 "removing it and checking for further interleavings");
+
+                    appData.getLastFoundSubsequences().remove
+                        (interleavings.get(0).getSubsequence());
+                    
+                    continue;
+                }
+                else if (interleavings.size() == 0) {
+                    // this should never happen
+                    throw new RuntimeException("Implementation error: don't know how I got here");
+                }
+                
+                // Console.traceln(Level.FINEST, "found " + interleavings.size() +
+                //                 " most interleaving subsequences being most often a successor " +
+                //                 "and most seldom a predecessor in comparison to the other " +
+                //                 "remaining interleavings --> this may happen if there are no " +
+                //                 "collisions between them anymore. If so, remove all of them at " +
+                //                 "once.");
+
+                int collisionCount = 0;
+                
+                for (InterleavingSubsequence subsequence : interleavings) {
+                    collisionCount += subsequence.getCollisionCounter();
+                }
+                
+                if (collisionCount == 0) {
+                    // Console.traceln(Level.FINEST, "remaining interleaving subsequences have no " +
+                    //                 "further collisions with each other --> removing all of them " +
+                    //                 "and checking for further interleavings");
+                    
+                    for (InterleavingSubsequence subsequence : interleavings) {
+                        appData.getLastFoundSubsequences().remove(subsequence.getSubsequence());
+                    }
+                    
+                    continue;
+                }
+
+                // Console.traceln(Level.FINEST, "remaining interleaving subsequences still have " +
+                //                 "collisions with each other --> decide based on their occurrences" +
+                //                 " in the sessions (remove those, coming later in comparison to " +
+                //                 "the others)");
+                
+                // determine the predecessor collisions being the last in all sessions. Those
+                // collisions show the interleaving subsequence occurring last 
+                Map<IUserSession, Collision> sessions =
+                    new IdentityHashMap<IUserSession, Collision>();
+                
+                for (InterleavingSubsequence interleaving : interleavings) {
+                    for (Collision coll : interleaving.getPredecessorCollisions()) {
+                        Collision maxPosColl = sessions.get(coll.getLocation().getSession());
+                        
+                        if ((maxPosColl == null) ||
+                            (maxPosColl.getLocation().getIndex() < coll.getLocation().getIndex()))
+                        {
+                            sessions.put(coll.getLocation().getSession(), coll);
+                        }
+                    }
+                }
+                
+                // determine, which of the subsequences occurs most often as the last one
+                // interleaving with another
+                Map<Subsequence, Integer> lastOccurrenceCounters =
+                    new IdentityHashMap<Subsequence, Integer>();
+                
+                for (Collision coll : sessions.values()) {
+                    Integer counter = lastOccurrenceCounters.get(coll.getSubsequence());
+                    
+                    if (counter == null) {
+                        lastOccurrenceCounters.put(coll.getSubsequence(), 1);
+                    }
+                    else {
+                        lastOccurrenceCounters.put(coll.getSubsequence(), counter + 1);
+                    }
+                }
+                
+                int maxCounter = 0;
+                Subsequence toRemove = null;
+                
+                for (Map.Entry<Subsequence, Integer> entry : lastOccurrenceCounters.entrySet()) {
+                    if (entry.getValue() > maxCounter) {
+                        maxCounter = entry.getValue();
+                        toRemove = entry.getKey();
+                    }
+                    else if (entry.getValue() == maxCounter) {
+                        // we can not decide again
+                        toRemove = null;
+                        break;
+                    }
+                }
+                
+                if (toRemove != null) {
+                    // Console.traceln(Level.FINEST, "one of the remaining interleaving subsequences" +
+                    //                 " is most often the last to occur --> removing it and " +
+                    //                 "checking for further interleavings");
+            
+                    appData.getLastFoundSubsequences().remove(toRemove);
+                    continue;
+                }
+                
+                // checking now, if there is one sequence, having the lowest index for any of
+                // its collisions and preserve it. If there are several ones with the same minimum
+                // index, throw an exception
+                int minPosInAnySequence = Integer.MAX_VALUE;
+                InterleavingSubsequence subsequenceWithMinPos = null;
+                
+                for (InterleavingSubsequence interleaving : interleavings) {
+                    for (Collision collision : interleaving.getSuccessorCollisions()) {
+                        if (minPosInAnySequence > collision.getLocation().getIndex()) {
+                            minPosInAnySequence = collision.getLocation().getIndex();
+                            subsequenceWithMinPos = interleaving;
+                        }
+                        else if (minPosInAnySequence == collision.getLocation().getIndex()) {
+                            // several have the same min pos --> undecidable which to prefer
+                            subsequenceWithMinPos = null;
+                        }
+                    }
+                }
+                
+                if (subsequenceWithMinPos != null) {
+                    List<Subsequence> subsequencesToRemove = new LinkedList<Subsequence>();
+                    
+                    for (Subsequence candidate : appData.getLastFoundSubsequences()) {
+                        if (candidate != subsequenceWithMinPos.getSubsequence()) {
+                            subsequencesToRemove.add(candidate);
+                        }
+                    }
+                    
+                    for (Subsequence candidate : subsequencesToRemove) {
+                        appData.getLastFoundSubsequences().remove(candidate);
+                    }
+                    
+                    continue;
+                }
+                
+                // At this point, we can not decide anymore. But it should also not
+                // happen. Even if two subsequences ab and ba one of them should be
+                // more often a successor or predecessor than the other if they
+                // directly follow each other. If not, it can not be decided, which of
+                // them to replace first. Perhaps the one occurring more often as
+                // the first in a session that the other. But this can be implemented
+                // later.
+                dumpSorted(interleavings, Level.SEVERE);
+                
+                throw new RuntimeException
+                    ("can not decide which detected subsequence to replace first.");
+            }
+        }
+        while (interleavings.size() > 0);
+
+        // >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
+        // >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> TEST IMPLEMENTATION >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
+        // dumpSortedCollectionOfSubsequences
+        //    ("to replace", appData.getLastFoundSubsequences().subsequences);
+        // <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
+        // <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< TEST IMPLEMENTATION <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
+    }
+
+    /**
+     *
+     */
+    private List<InterleavingSubsequence> getInterleavings(Subsequences        subsequences,
+                                                           RuleApplicationData appData)
+    {
+        List<InterleavingSubsequence> interleavings = new LinkedList<InterleavingSubsequence>();
+        List<Subsequence> potentialPredecessors = new LinkedList<Subsequence>();
+        List<Subsequence> potentialSuccessors = new LinkedList<Subsequence>();
+        
+        Map<Subsequence, List<SubsequenceLocation>> allLocations =
+            getLocations(subsequences, appData);
+        
+        for (Subsequence subsequence : subsequences) {
+            // Console.traceln
+            //    (Level.FINEST, "searching for interleavings of " + toPlainStr(subsequence));
+
+            potentialPredecessors.clear();
+            potentialSuccessors.clear();
+            
+            getInterleavingSubsequences
+                (subsequence, subsequences, potentialPredecessors, potentialSuccessors);
+            
+            if ((potentialPredecessors.size() <= 0) && (potentialSuccessors.size() <= 0)) {
+                // subsequence is not interleaving with others. Check next one.
+                continue;
+            }
+            
+            // subsequence is interleaving. First, determine its locations in the user sessions.
+            List<SubsequenceLocation> locations = allLocations.get(subsequence);
+            
+            List<Collision> precedingCollisions =
+                getPrecedingCollisions(subsequence, locations, potentialPredecessors, appData);
+            
+            List<Collision> succeedingCollisions =
+                getSucceedingCollisions(subsequence, locations, potentialSuccessors, appData);
+            
+            if ((precedingCollisions.size() <= 0) && (succeedingCollisions.size() <= 0)) {
+                // subsequence is not interleaving with others. Check next one.
+                continue;
+            }
+            
+            interleavings.add(new InterleavingSubsequence(subsequence, precedingCollisions,
+                                                          succeedingCollisions));
+        }
+        
+        return interleavings;
+    }
+
+    /**
+     *
+     */
+    private void getInterleavingSubsequences(Subsequence       subsequence,
+                                             Subsequences      allSubsequences,
+                                             List<Subsequence> potentialPredecessors,
+                                             List<Subsequence> potentialSuccessors)
+    {
+        TaskComparator comparator = identityTaskHandlingStrategy.getTaskComparator();
+        
+        for (Subsequence candidate : allSubsequences) {
+            if (comparator.equals(subsequence.get(subsequence.size() - 1), candidate.get(0))) {
+                potentialSuccessors.add(candidate);
+            }
+            
+            if (comparator.equals(subsequence.get(0), candidate.get(candidate.size() - 1))) {
+                potentialPredecessors.add(candidate);
+            }
+        }
+
+        // >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
+        // >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> TEST IMPLEMENTATION >>>>>>>>>>>>>>>>>>>>>>>>>>>>>
+        // Console.traceln(Level.FINEST, "  potential successors of " + toPlainStr(subsequence));
+        // dumpSortedCollectionOfSubsequences("    ", potentialSuccessors);
+        
+        // Console.traceln(Level.FINEST, "  potential predecessors of " + toPlainStr(subsequence));
+        // dumpSortedCollectionOfSubsequences("    ", potentialPredecessors);
+        // <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
+        // <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< TEST IMPLEMENTATION <<<<<<<<<<<<<<<<<<<<<<<<<<<<<
+    }
+
+    /**
+     *
+     */
+    private Map<Subsequence, List<SubsequenceLocation>> getLocations(Subsequences        subsequences,
+                                                                     RuleApplicationData appData)
+    {
+        Map<Subsequence, List<SubsequenceLocation>> result =
+            new IdentityHashMap<Subsequence, List<SubsequenceLocation>>();
+        
+        // fill the map with empty locations
+        for (Subsequence subsequence : subsequences) {
+            result.put(subsequence, new LinkedList<SubsequenceLocation>());
+        }
+        
+        LinkedList<LinkedList<Subsequence>> candidates = new LinkedList<LinkedList<Subsequence>>();
+
+        for (IUserSession session : appData.getSessions()) {
+            for (int i = 0; i < session.size(); i++) {
+                ITask currentTask = session.get(i).getTask();
+                
+                // create a list of candidates that may start here
+                LinkedList<Subsequence> candidatesToStartHere = new LinkedList<Subsequence>();
+                
+                for (Subsequence candidate : subsequences) {
+                    if (candidate.get(0) == currentTask) {
+                        candidatesToStartHere.add(candidate);
+                    }
+                }
+                
+                candidates.addFirst(candidatesToStartHere);
+                
+                // check if the other candidates continue here.
+                ListIterator<LinkedList<Subsequence>> candidatesIt = candidates.listIterator(1);
+                int index = 1;
+                while (candidatesIt.hasNext()) {
+                    ListIterator<Subsequence> candidateIt = candidatesIt.next().listIterator();
+                    while (candidateIt.hasNext()) {
+                        Subsequence candidate = candidateIt.next();
+                        
+                        if (candidate.get(index) == currentTask) {
+                            if (candidate.size() == (index + 1)) {
+                                // subsequence was fully matched --> store location
+                                result.get(candidate).add
+                                    (new SubsequenceLocation(session, i - candidate.size() + 1));
+                                candidateIt.remove();
+                            }
+                        }
+                        else if (candidate.get(index) != currentTask) {
+                            // remove the candidate as it is not located here
+                            candidateIt.remove();
+                        }
+                    }
+                    
+                    index++;
+                }
+                
+                // remove potential continuation being empty
+                while ((candidates.size() > 0) && (candidates.getLast().size() == 0)) {
+                    candidates.removeLast();
+                }
+            }
+        }
+        
+        return result;
+    }
+
+    /**
+     *
+     */
+    private List<Collision> getPrecedingCollisions(Subsequence               subsequence,
+                                                   List<SubsequenceLocation> locations,
+                                                   List<Subsequence>         potentialPredecessors,
+                                                   RuleApplicationData       appData)
+    {
+        List<Collision> precedingCollisions = new LinkedList<Collision>();
+        int interleavingStartIndex;
+        int interleavingEndIndex;
+        
+        for (SubsequenceLocation location : locations) {
+            for (Subsequence predecessor : potentialPredecessors) {
+                // start where the interleaving would start
+                interleavingStartIndex = location.getIndex() - predecessor.size() + 1;
+                
+                if (interleavingStartIndex >= 0) {
+                    interleavingEndIndex =
+                        getSubListIndex(location.getSession(), predecessor, interleavingStartIndex);
+                
+                    if (interleavingStartIndex == interleavingEndIndex) {
+                        precedingCollisions.add(new Collision(location, subsequence, predecessor));
+                    }
+                }
+            }
+        }
+        
+        return precedingCollisions;
+    }
+
+    /**
+     *
+     */
+    private List<Collision> getSucceedingCollisions(Subsequence               subsequence,
+                                                    List<SubsequenceLocation> locations,
+                                                    List<Subsequence>         potentialPredecessors,
+                                                    RuleApplicationData       appData)
+    {
+        List<Collision> succeedingCollisions = new LinkedList<Collision>();
+        int interleavingStartIndex;
+        int interleavingEndIndex;
+
+        for (SubsequenceLocation location : locations) {
+            for (Subsequence successor : potentialPredecessors) {
+                interleavingStartIndex = location.getIndex() + subsequence.size() - 1;
+                interleavingEndIndex =
+                    getSubListIndex(location.getSession(), successor, interleavingStartIndex);
+
+                if (interleavingStartIndex == interleavingEndIndex) {
+                    succeedingCollisions.add(new Collision(location, subsequence, successor));
+                }
+            }
+        }
+        
+        return succeedingCollisions;
+    }
+    
+    /**
+     *
+     */
+    private List<InterleavingSubsequence> getMostIntensiveInterleavings
+        (List<InterleavingSubsequence> interleavings)
+    {
+        List<InterleavingSubsequence> mostIntensiveInterleavings =
+            new LinkedList<InterleavingSubsequence>();
+        
+        int collisionCounter = 0;
+        
+        for (InterleavingSubsequence interleaving : interleavings) {
+            if (interleaving.getCollisionCounter() > collisionCounter) {
+                collisionCounter = interleaving.getCollisionCounter();
+                mostIntensiveInterleavings.clear();
+            }
+            
+            if (interleaving.getCollisionCounter() == collisionCounter) {
+                mostIntensiveInterleavings.add(interleaving);
+            }
+        }
+        
+        return mostIntensiveInterleavings;
+    }
+
+    /**
+     *
+     */
+    private List<InterleavingSubsequence> getLeastInterleavingsAsPredecessor
+        (List<InterleavingSubsequence> interleavings)
+    {
+        List<InterleavingSubsequence> leastInterleavingsAsPredecessor =
+            new LinkedList<InterleavingSubsequence>();
+            
+        int collisionCounter = Integer.MAX_VALUE;
+
+        for (InterleavingSubsequence interleaving : interleavings) {
+            if (interleaving.getSuccessorCollisionCounter() < collisionCounter) {
+                collisionCounter = interleaving.getSuccessorCollisionCounter();
+                leastInterleavingsAsPredecessor.clear();
+            }
+
+            if (interleaving.getSuccessorCollisionCounter() == collisionCounter) {
+                leastInterleavingsAsPredecessor.add(interleaving);
+            }
+        }
+
+        return leastInterleavingsAsPredecessor;
+    }
+
+    /**
+     *
+     */
+    private List<InterleavingSubsequence> getMostInterleavingsAsSuccessor
+        (List<InterleavingSubsequence> interleavings)
+    {
+        List<InterleavingSubsequence> mostInterleavingsAsSuccessor =
+            new LinkedList<InterleavingSubsequence>();
+           
+        int collisionCounter = 0;
+
+        for (InterleavingSubsequence interleaving : interleavings) {
+            if (interleaving.getPredecessorCollisionCounter() > collisionCounter) {
+                collisionCounter = interleaving.getPredecessorCollisionCounter();
+                mostInterleavingsAsSuccessor.clear();
+            }
+
+            if (interleaving.getPredecessorCollisionCounter() == collisionCounter) {
+                mostInterleavingsAsSuccessor.add(interleaving);
+            }
+        }
+
+        return mostInterleavingsAsSuccessor;
+    }
+
+    /**
+     *
+     */
+    private List<InterleavingSubsequence> removeCollisionsOfOtherSubsequences
+        (List<InterleavingSubsequence> interleavings)
+    {
+        List<InterleavingSubsequence> subsequencesWithoutOtherCollisions =
+            new LinkedList<InterleavingSubsequence>();
+        
+        for (InterleavingSubsequence interleaving : interleavings) {
+            List<Collision> reducedPredecessorCollisions = new LinkedList<>();
+            
+            for (Collision collision : interleaving.getPredecessorCollisions()) {
+                for (InterleavingSubsequence otherInterleaving : interleavings) {
+                    if (otherInterleaving.getSubsequence() == collision.getCollidingWith()) {
+                        reducedPredecessorCollisions.add(collision);
+                        break;
+                    }
+                }
+            }
+            
+            List<Collision> reducedSuccessorCollisions = new LinkedList<>();
+            
+            for (Collision collision : interleaving.getSuccessorCollisions()) {
+                for (InterleavingSubsequence otherInterleaving : interleavings) {
+                    if (otherInterleaving.getSubsequence() == collision.getCollidingWith()) {
+                        reducedSuccessorCollisions.add(collision);
+                        break;
+                    }
+                }
+            }
+            
+            subsequencesWithoutOtherCollisions.add
+                (new InterleavingSubsequence(interleaving.getSubsequence(),
+                                             reducedPredecessorCollisions,
+                                             reducedSuccessorCollisions));
+        }
+        
+        return subsequencesWithoutOtherCollisions;
     }
 
@@ -568 +1217 @@
         appData.detectedAndReplacedTasks(false);
 
-        if ((appData.getLastFoundTasks().size() > 0) &&
-            (appData.getLastFoundTasks().getOccurrenceCount() > 1))
+        if ((appData.getLastFoundSubsequences().size() > 0) &&
+            (appData.getLastFoundSubsequences().getOccurrenceCount() > 1))
         {
             Console.traceln(Level.FINER, "replacing tasks occurrences");
 
-            for (List<ITaskInstance> task : appData.getLastFoundTasks()) {
+            for (Subsequence subsequence : appData.getLastFoundSubsequences()) {
                 ISequence sequence = taskFactory.createNewSequence();
                 
-                Console.traceln(Level.FINEST, "replacing " + sequence.getId() + ": " + task);
-
-                List<ISequenceInstance> sequenceInstances =
-                    replaceTaskOccurrences(task, appData.getSessions(), sequence);
-                
-                harmonizeSequenceInstancesModel(sequence, sequenceInstances, task.size());
+                Console.traceln(Level.FINEST, "replacing " + sequence.getId() + ": " + subsequence);
+
+                List<ISequenceInstance> sequenceInstances = replaceSubsequenceOccurrences
+                    (subsequence, appData.getSessions(), sequence);
+                
+                harmonizeSequenceInstancesModel(sequence, sequenceInstances, subsequence.size());
                 appData.detectedAndReplacedTasks
                     (appData.detectedAndReplacedTasks() || (sequenceInstances.size() > 0));
 
-                if (sequenceInstances.size() < appData.getLastFoundTasks().getOccurrenceCount()) {
+                if (sequenceInstances.size() < appData.getLastFoundSubsequences().getOccurrenceCount()) {
                     Console.traceln(Level.FINE, sequence.getId() + ": replaced task only " +
                                     sequenceInstances.size() + " times instead of expected " +
-                                    appData.getLastFoundTasks().getOccurrenceCount());
-                }
-            }
-        }
-        
+                                    appData.getLastFoundSubsequences().getOccurrenceCount());
+                }
+            }
+        }
     }
 
@@ -602 +1250 @@
                                                  int                     sequenceLength)
     {
-        TaskInstanceComparator comparator = preparationTaskHandlingStrategy.getTaskComparator();
+        TaskComparator comparator = preparationTaskHandlingStrategy.getTaskComparator();
         
         // ensure for each subtask that lexically different variants are preserved
@@ -660 +1308 @@
      * @param tree
      */
-    private List<ISequenceInstance> replaceTaskOccurrences(List<ITaskInstance> task,
-                                                           List<IUserSession>  sessions,
-                                                           ISequence           temporalTaskModel)
+    private List<ISequenceInstance> replaceSubsequenceOccurrences(Subsequence         subsequence,
+                                                                  List<IUserSession>  sessions,
+                                                                  ISequence           temporalTaskModel)
     {
         List<ISequenceInstance> sequenceInstances = new LinkedList<ISequenceInstance>();
@@ -668 +1316 @@
         for (IUserSession session : sessions) {
             int index = -1;
-                
+            
             do {
-                index = getSubListIndex(session, task, ++index);
+                index = getSubListIndex(session, subsequence, ++index);
 
                 if (index > -1) {
+                    // subsequence is found --> perform replacement
                     sequenceInstances.add
                         (RuleUtils.createNewSubSequenceInRange
-                             (session, index, index + task.size() - 1, temporalTaskModel,
+                             (session, index, index + subsequence.size() - 1, temporalTaskModel,
                               taskFactory, taskBuilder));
                 }
@@ -691 +1340 @@
      */
     private int getSubListIndex(ITaskInstanceList   list,
-                                List<ITaskInstance> subList,
+                                Subsequence         subsequence,
                                 int                 startIndex)
     {
@@ -697 +1346 @@
         int result = -1;
         
-        for (int i = startIndex; i <= list.size() - subList.size(); i++) {
+        for (int i = startIndex; i <= list.size() - subsequence.size(); i++) {
             matchFound = true;
             
-            for (int j = 0; j < subList.size(); j++) {
+            for (int j = 0; j < subsequence.size(); j++) {
                 // we prepared the task instances to refer to unique tasks, if they are treated
                 // as equal. Therefore, we just compare the identity of the tasks of the task
                 // instances
-                if (list.get(i + j).getTask() != subList.get(j).getTask()) {
+                if (list.get(i + j).getTask() != subsequence.get(j)) {
                     matchFound = false;
                     break;
@@ -724 +1373 @@
      * @return
      */
-    private int getSubListIndex(List<ITaskInstance> list,
-                                List<ITaskInstance> subList,
-                                int                 startIndex)
+    private int getSubListIndex(Subsequence longerSubsequence,
+                                Subsequence shorterSubsequence,
+                                int         startIndex)
     {
         boolean matchFound;
         int result = -1;
         
-        for (int i = startIndex; i <= list.size() - subList.size(); i++) {
+        for (int i = startIndex; i <= longerSubsequence.size() - shorterSubsequence.size(); i++) {
             matchFound = true;
             
-            for (int j = 0; j < subList.size(); j++) {
+            for (int j = 0; j < shorterSubsequence.size(); j++) {
                 // we prepared the task instances to refer to unique tasks, if they are treated
                 // as equal. Therefore, we just compare the identity of the tasks of the task
                 // instances
-                if (list.get(i + j) != subList.get(j)) {
+                if (longerSubsequence.get(i + j) != shorterSubsequence.get(j)) {
                     matchFound = false;
                     break;
@@ -752 +1401 @@
         return result;
     }
+
+//  /**
+//   *
+//   */
+//  private void dumpSorted(List<InterleavingSubsequence> interleavings) {
+//      dumpSorted(interleavings, Level.FINEST);
+//  }
+
+    /**
+     *
+     */
+    private void dumpSorted(List<InterleavingSubsequence> interleavings, Level level) {
+        List<String> tmpList = new LinkedList<String>();
+
+        for (InterleavingSubsequence interleaving : interleavings) {
+            String taskStr = toPlainStr(interleaving);
+            int index;
+            for (index = 0; index < tmpList.size(); index++) {
+                if (taskStr.compareTo(tmpList.get(index)) > 0) {
+                    break;
+                }
+            }
+
+            tmpList.add(index, taskStr);
+        }
+
+        for (String task : tmpList) {
+            Console.traceln(level, task);
+        }
+    }
+
+//    /**
+//     *
+//     */
+//    private void dumpSortedCollectionOfSubsequences(String                  prefix,
+//                                                    Collection<Subsequence> subsequences)
+//    {
+//        List<String> tmpList = new LinkedList<String>();
+//
+//        for (Subsequence subsequence : subsequences) {
+//            String taskStr = toPlainStr(subsequence);
+//            int index;
+//            for (index = 0; index < tmpList.size(); index++) {
+//                if (taskStr.compareTo(tmpList.get(index)) > 0) {
+//                    break;
+//                }
+//            }
+//
+//            tmpList.add(index, taskStr);
+//        }
+//
+//        for (String task : tmpList) {
+//            Console.traceln(Level.FINEST, prefix + " " + task);
+//        }
+//    }
+
+    /**
+     *
+     */
+    private String toPlainStr(InterleavingSubsequence interleaving) {
+        StringBuffer result = new StringBuffer();
+        result.append("interleavings of ");
+        result.append(toPlainStr(interleaving.getSubsequence()));
+        result.append("\n  predecessor collisions:\n");
+
+        for (Collision collision : interleaving.getPredecessorCollisions()) {
+            result.append("    ");
+            result.append(toPlainStr(collision.getCollidingWith()));
+            result.append(" (");
+            result.append(collision.getLocation());
+            result.append(")\n");
+        }
+
+        result.append("  successor collisions:\n");
+
+        for (Collision collision : interleaving.getSuccessorCollisions()) {
+            result.append("    ");
+            result.append(toPlainStr(collision.getCollidingWith()));
+            result.append(" (");
+            result.append(collision.getLocation());
+            result.append(")\n");
+        }
+
+        return result.toString();
+    }
+
+    /**
+     *
+     */
+    private String toPlainStr(Subsequence subsequence) {
+        StringBuffer result = new StringBuffer();
+        result.append(subsequence.size());
+        result.append(": ");
+        for (ITask task : subsequence) {
+            DebuggingHelper.toPlainStr(task, result);
+            result.append(" --> ");
+        }
+
+        return result.toString();
+    }
     
+    
     /**
      * @author Patrick Harms
      */
-    private class MaxCountAndLongestTasksFinder implements TrieProcessor<ITaskInstance> {
+    private class MaxCountAndLongestSubsequencesFinder implements TrieProcessor<ITask> {
         
         /**
@@ -766 +1516 @@
          * 
          */
-        private List<List<ITaskInstance>> foundTasks = new LinkedList<List<ITaskInstance>>();
+        private LinkedList<Subsequence> foundSubsequences = new LinkedList<Subsequence>();
 
         /**
          *
          */
-        public MaxCountAndLongestTasksFinder() {
+        public MaxCountAndLongestSubsequencesFinder() {
             super();
             this.currentCount = 0;
@@ -780 +1530 @@
          */
         @Override
-        public TrieProcessor.Result process(List<ITaskInstance> foundTask, int count) {
+        public TrieProcessor.Result process(List<ITask> foundTask, int count) {
             if (foundTask.size() < 2) {
                 // ignore single tasks
@@ -800 +1550 @@
                 // the provided task occurs more often that all tasks found so far.
                 // clear all found tasks and use the new count as the one searched for
-                foundTasks.clear();
+                foundSubsequences.clear();
                 this.currentCount = count;
             }
@@ -808 +1558 @@
                 // the longest come first
                 boolean added = false;
-                for (int i = 0; i < foundTasks.size(); i++) {
-                    if (foundTasks.get(i).size() < foundTask.size()) {
-                        // defensive copy
-                        foundTasks.add(i, new LinkedList<ITaskInstance>(foundTask)); // defensive copy
+                for (int i = 0; i < foundSubsequences.size(); i++) {
+                    if (foundSubsequences.get(i).size() < foundTask.size()) {
+                        foundSubsequences.add(i, new Subsequence(currentCount, foundTask));
                         added = true;
                         break;
@@ -818 +1567 @@
                 
                 if (!added) {
-                    foundTasks.add(new LinkedList<ITaskInstance>(foundTask)); // defensive copy
+                    foundSubsequences.add(new Subsequence(currentCount, foundTask));
                 }
             }
@@ -828 +1577 @@
          *  @return
          */
-        public Tasks getFoundTasks() {
+        private Subsequences getFoundSubsequences() {
             removePermutationsOfShorterTasks();
-            return new Tasks(currentCount, foundTasks);
+            return new Subsequences(currentCount, foundSubsequences);
         }
 
@@ -839 +1588 @@
             // now iterate the sorted list and for each task remove all other tasks that are shorter
             // (i.e. come later in the sorted list) and that represent a subpart of the task
-            for (int i = 0; i < foundTasks.size(); i++) {
-                for (int j = i + 1; j < foundTasks.size();) {
-                    if (foundTasks.get(j).size() < foundTasks.get(i).size()) {
+            
+            boolean removeI;
+            
+            for (int i = 0; i < foundSubsequences.size();) {
+                removeI = false;
+                boolean removeJ;
+                
+                for (int j = i + 1; j < foundSubsequences.size();) {
+                    removeJ = false;
+                    
+                    if (foundSubsequences.get(j).size() < foundSubsequences.get(i).size()) {
                         // found a task that is a potential subtask. Check for this and remove the
                         // subtask if needed
-                        List<ITaskInstance> longTask = foundTasks.get(i);
-                        List<ITaskInstance> shortTask = foundTasks.get(j);
+                        Subsequence longTask = foundSubsequences.get(i);
+                        Subsequence shortTask = foundSubsequences.get(j);
                         
-                        if (getSubListIndex(longTask, shortTask, 0) > -1) {
-                            foundTasks.remove(j);
+                        int index = getSubListIndex(longTask, shortTask, 0);
+                        if (index > -1) {
+                            if (index == 0) {
+                                // check if the short task is included in the long task partially
+                                // a second time. If so, prefer the short task
+                                boolean secondInclude = true;
+                                for (int pos = shortTask.size(); pos < longTask.size(); pos++) {
+                                    // we prepared the task instances to refer to unique tasks, if
+                                    // they are treated as equal. Therefore, we just compare the
+                                    // identity of the tasks of the task instances
+                                    if (longTask.get(pos) != shortTask.get(pos % shortTask.size()))
+                                    {
+                                        secondInclude = false;
+                                        break;
+                                    }
+                                }
+                                
+                                if (secondInclude) {
+                                    // delete the long task
+                                    // Console.traceln(Level.FINEST, "1: short task is contained several times in longer one --> removing it");
+                                    // Console.traceln(Level.FINEST, "short: " + toPlainStr(shortTask));
+                                    // Console.traceln(Level.FINEST, "long: " + toPlainStr(longTask));
+                                    removeI = true;
+                                }
+                                else {
+                                    // Console.traceln(Level.FINEST, "2: short task is a part of a longer one --> removing it");
+                                    // Console.traceln(Level.FINEST, "short: " + toPlainStr(shortTask));
+                                    // Console.traceln(Level.FINEST, "long: " + toPlainStr(longTask));
+                                    removeJ = true;
+                                }
+                            }
+                            else {
+                                // Console.traceln(Level.FINEST, "3: short task is a part of a longer one --> removing it");
+                                // Console.traceln(Level.FINEST, "short: " + toPlainStr(shortTask));
+                                // Console.traceln(Level.FINEST, "long: " + toPlainStr(longTask));
+                                removeJ = true;
+                            }
                         }
-                        else {
-                            j++;
-                        }
+                    }
+                    
+                    if (removeJ) {
+                        foundSubsequences.remove(j);
                     }
                     else {
@@ -858 +1651 @@
                     }
                 }
-            }
-        }
-
-    }
-    
+                
+                if (removeI) {
+                    foundSubsequences.remove(i);
+                }
+                else {
+                    i++;
+                }
+            }
+        }
+
+    }
+
 //    /**
 //     * @author Patrick Harms
@@ -929 +1729 @@
         
         /**
-         * default and minimum trained sequence length is 3
-         */
-        private int trainedSequenceLength = 3;
+         * default and minimum trained subsequence length is 3
+         */
+        private int trainedSubsequenceLength = 3;
         
         /**
          * 
          */
-        private Tasks lastFoundTasks = new Tasks(Integer.MAX_VALUE, null);
+        private Subsequences lastFoundSubsequences = new Subsequences(Integer.MAX_VALUE, null);
         
         /**
@@ -982 +1782 @@
 
         /**
-         * @param trainedSequenceLength the trainedSequenceLength to set
-         */
-        private void setTrainedSequenceLength(int trainedSequenceLength) {
-            this.trainedSequenceLength = trainedSequenceLength;
-        }
-
-        /**
-         * @return the trainedSequenceLength
-         */
-        private int getTrainedSequenceLength() {
-            return trainedSequenceLength;
+         * @param trainedSubsequenceLength the trainedSubsequenceLength to set
+         */
+        private void setTrainedSubsequenceLength(int trainedSubsequenceLength) {
+            this.trainedSubsequenceLength = trainedSubsequenceLength;
+        }
+
+        /**
+         * @return the trainedSubsequenceLength
+         */
+        private int getTrainedSubsequenceLength() {
+            return trainedSubsequenceLength;
         }
 
@@ -998 +1798 @@
          * @param lastFoundSequences the lastFoundSequences to set
          */
-        private void setLastFoundTasks(Tasks lastFoundSequences) {
-            this.lastFoundTasks = lastFoundSequences;
+        private void setLastFoundSubsequences(Subsequences lastFoundSequences) {
+            this.lastFoundSubsequences = lastFoundSequences;
         }
 
@@ -1005 +1805 @@
          * @return the lastFoundSequences
          */
-        private Tasks getLastFoundTasks() {
-            return lastFoundTasks;
+        private Subsequences getLastFoundSubsequences() {
+            return lastFoundSubsequences;
         }
 
@@ -1039 +1839 @@
     }
     
-
     /**
      * @author Patrick Harms
      */
-    private static class Tasks implements Iterable<List<ITaskInstance>> {
+    private static class Subsequence implements Iterable<ITask> {
         
         /**
@@ -1049 +1848 @@
          */
         private int occurrenceCount;
-        
+
         /**
          * 
          */
-        private List<List<ITaskInstance>> sequences;
+        private List<ITask> subsequence;
+        
+        /**
+         * @param occurrenceCount
+         * @param subsequences
+         */
+        private Subsequence(int occurrenceCount, List<ITask> subsequence) {
+            super();
+            this.occurrenceCount = occurrenceCount;
+            this.subsequence = new ArrayList<ITask>(subsequence);
+        }
+
+        /**
+         * @return
+         */
+        private int size() {
+            return this.subsequence.size();
+        }
+
+        /**
+         * @return
+         */
+        private ITask get(int index) {
+            return this.subsequence.get(index);
+        }
+
+        /* (non-Javadoc)
+         * @see java.lang.Iterable#iterator()
+         */
+        @Override
+        public Iterator<ITask> iterator() {
+            return this.subsequence.iterator();
+        }
+
+        /* (non-Javadoc)
+         * @see java.lang.Object#toString()
+         */
+        @Override
+        public String toString() {
+            return subsequence.toString() + " (" + occurrenceCount + ")";
+        }
+    }
+
+    /**
+     * @author Patrick Harms
+     */
+    private static class Subsequences implements Iterable<Subsequence> {
+        
+        /**
+         * 
+         */
+        private int occurrenceCount;
+        
+        /**
+         * 
+         */
+        private LinkedList<Subsequence> subsequences;
 
         /**
@@ -1059 +1914 @@
          * @param sequences
          */
-        private Tasks(int occurrenceCount, List<List<ITaskInstance>> sequences) {
+        private Subsequences(int occurrenceCount, LinkedList<Subsequence> subsequences) {
             super();
             this.occurrenceCount = occurrenceCount;
-            this.sequences = sequences;
+            this.subsequences = subsequences;
+        }
+
+        /**
+         *
+         */
+        private void remove(Subsequence subsequence) {
+            ListIterator<Subsequence> it = subsequences.listIterator();
+            
+            while (it.hasNext()) {
+                // reference comparison is sufficient
+                if (it.next() == subsequence) {
+                    it.remove();
+                }
+            }
         }
 
@@ -1076 +1945 @@
          */
         private int size() {
-            return this.sequences.size();
-        }
-
-        /**
-         * 
-         */
+            return this.subsequences.size();
+        }
 
         /* (non-Javadoc)
@@ -1087 +1952 @@
          */
         @Override
-        public Iterator<List<ITaskInstance>> iterator() {
-            return this.sequences.iterator();
+        public Iterator<Subsequence> iterator() {
+            return this.subsequences.iterator();
         }
 
@@ -1097 +1962 @@
         public String toString() {
             StringBuffer result = new StringBuffer();
+            result.append(" subsequences occuring ");
             result.append(this.occurrenceCount);
-            result.append(" occurrences:\n");
-            
-            for (List<ITaskInstance> task : sequences) {
-                result.append(task);
+            result.append(" times:\n");
+            
+            for (Subsequence subsequence : subsequences) {
+                result.append(subsequence);
                 result.append("\n");
             }
@@ -1107 +1973 @@
             return result.toString();
         }
-
+    }
+    
+    /**
+     * @author Patrick Harms
+     */
+    private static class InterleavingSubsequence {
+        
+        /** */
+        private Subsequence subsequence;
+        
+        /** */
+        private List<Collision> successorCollisions;
+        
+        /** */
+        private List<Collision> predecessorCollisions;
+
+        /**
+         *
+         */
+        private InterleavingSubsequence(Subsequence     subsequence,
+                                        List<Collision> predecessorCollisions,
+                                        List<Collision> successorCollisions)
+        {
+            super();
+            this.subsequence = subsequence;
+            this.predecessorCollisions = predecessorCollisions;
+            this.successorCollisions = successorCollisions;
+        }
+
+        /**
+         *
+         */
+        private int getCollisionCounter() {
+            return getSuccessorCollisionCounter() + getPredecessorCollisionCounter();
+        }
+
+        /**
+         *
+         */
+        private int getSuccessorCollisionCounter() {
+            return successorCollisions.size();
+        }
+
+        /**
+         *
+         */
+        private List<Collision> getSuccessorCollisions() {
+            return successorCollisions;
+        }
+
+        /**
+         *
+         */
+        private int getPredecessorCollisionCounter() {
+            return predecessorCollisions.size();
+        }
+
+        /**
+         *
+         */
+        private List<Collision> getPredecessorCollisions() {
+            return predecessorCollisions;
+        }
+
+        /**
+         *
+         */
+        private Subsequence getSubsequence() {
+            return subsequence;
+        }
+        
+        /* (non-Javadoc)
+         * @see java.lang.Object#toString()
+         */
+        @Override
+        public String toString() {
+            return "interleaving subsequence " + subsequence.toString() + " (" +
+                successorCollisions.size() + " successor, " + predecessorCollisions.size() +
+                " predecessor)";
+        }
+    }
+        
+    /**
+     * @author Patrick Harms
+     */
+    private static class SubsequenceLocation {
+        
+        /** */
+        private IUserSession session;
+        
+        /** */
+        private int index;
+        
+        /**
+         * 
+         */
+        private SubsequenceLocation(IUserSession session, int index) {
+            this.session = session;
+            this.index = index;
+        }
+
+        /**
+         * @return the session
+         */
+        private IUserSession getSession() {
+            return session;
+        }
+
+        /**
+         * @return the index
+         */
+        private int getIndex() {
+            return index;
+        }
+        
+        /* (non-Javadoc)
+         * @see java.lang.Object#toString()
+         */
+        @Override
+        public String toString() {
+            return "location (" + session + ", " + index + ")";
+        }
+    }
+    
+    /**
+     * @author Patrick Harms
+     */
+    private static class Collision {
+        
+        /** */
+        private SubsequenceLocation location;
+        
+        /** */
+        private Subsequence subsequence;
+        
+        /** */
+        private Subsequence collidingWith;
+        
+        /**
+         * 
+         */
+        private Collision(SubsequenceLocation location,
+                          Subsequence         subsequence,
+                          Subsequence         collidingWith)
+        {
+            this.location = location;
+            this.subsequence = subsequence;
+            this.collidingWith = collidingWith;
+        }
+
+        /**
+         * @return the collidingWith
+         */
+        private Subsequence getCollidingWith() {
+            return collidingWith;
+        }
+
+        /**
+         * @return the location
+         */
+        private SubsequenceLocation getLocation() {
+            return location;
+        }
+
+        /**
+         * @return the subsequence
+         */
+        private Subsequence getSubsequence() {
+            return subsequence;
+        }
+
+        /* (non-Javadoc)
+         * @see java.lang.Object#toString()
+         */
+        @Override
+        public String toString() {
+            return "collision (" + location + " ," + subsequence + ", " + collidingWith + ")";
+        }
     }