Index: trunk/autoquest-core-tasktrees/src/main/java/de/ugoe/cs/autoquest/tasktrees/temporalrelation/SequenceForTaskDetectionRule.java =================================================================== --- trunk/autoquest-core-tasktrees/src/main/java/de/ugoe/cs/autoquest/tasktrees/temporalrelation/SequenceForTaskDetectionRule.java (revision 1854) +++ trunk/autoquest-core-tasktrees/src/main/java/de/ugoe/cs/autoquest/tasktrees/temporalrelation/SequenceForTaskDetectionRule.java (revision 1855) @@ -15,9 +15,12 @@ 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,4 +28,5 @@ 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,7 +187,6 @@ appData.getStopWatch().start("harmonizing event tasks"); - SymbolMap uniqueTasks = - preparationTaskHandlingStrategy.createSymbolMap(); - TaskInstanceComparator comparator = preparationTaskHandlingStrategy.getTaskComparator(); + SymbolMap uniqueTasks = preparationTaskHandlingStrategy.createSymbolMap(); + TaskComparator comparator = preparationTaskHandlingStrategy.getTaskComparator(); int unifiedTasks = 0; @@ -194,8 +197,8 @@ 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,5 +377,5 @@ { List iteratedTaskVariants = new LinkedList(); - TaskInstanceComparator comparator = preparationTaskHandlingStrategy.getTaskComparator(); + TaskComparator comparator = preparationTaskHandlingStrategy.getTaskComparator(); // merge the lexically different variants of iterated task to a unique list @@ -432,7 +435,12 @@ 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,6 +448,6 @@ 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,8 +456,8 @@ * @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,16 +468,16 @@ } - MaxCountAndLongestTasksFinder finder = new MaxCountAndLongestTasksFinder(); + MaxCountAndLongestSubsequencesFinder finder = new MaxCountAndLongestSubsequencesFinder(); appData.getLastTrie().process(finder); - tasks = finder.getFoundTasks(); + subsequences = finder.getFoundSubsequences(); createNewTrie = false; - for (List 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,8 +544,9 @@ 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,6 +555,6 @@ */ 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,7 +566,647 @@ 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 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 sessions = + new IdentityHashMap(); + + 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 lastOccurrenceCounters = + new IdentityHashMap(); + + 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 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 subsequencesToRemove = new LinkedList(); + + 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 getInterleavings(Subsequences subsequences, + RuleApplicationData appData) + { + List interleavings = new LinkedList(); + List potentialPredecessors = new LinkedList(); + List potentialSuccessors = new LinkedList(); + + Map> 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 locations = allLocations.get(subsequence); + + List precedingCollisions = + getPrecedingCollisions(subsequence, locations, potentialPredecessors, appData); + + List 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 potentialPredecessors, + List 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> getLocations(Subsequences subsequences, + RuleApplicationData appData) + { + Map> result = + new IdentityHashMap>(); + + // fill the map with empty locations + for (Subsequence subsequence : subsequences) { + result.put(subsequence, new LinkedList()); + } + + LinkedList> candidates = new LinkedList>(); + + 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 candidatesToStartHere = new LinkedList(); + + for (Subsequence candidate : subsequences) { + if (candidate.get(0) == currentTask) { + candidatesToStartHere.add(candidate); + } + } + + candidates.addFirst(candidatesToStartHere); + + // check if the other candidates continue here. + ListIterator> candidatesIt = candidates.listIterator(1); + int index = 1; + while (candidatesIt.hasNext()) { + ListIterator 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 getPrecedingCollisions(Subsequence subsequence, + List locations, + List potentialPredecessors, + RuleApplicationData appData) + { + List precedingCollisions = new LinkedList(); + 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 getSucceedingCollisions(Subsequence subsequence, + List locations, + List potentialPredecessors, + RuleApplicationData appData) + { + List succeedingCollisions = new LinkedList(); + 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 getMostIntensiveInterleavings + (List interleavings) + { + List mostIntensiveInterleavings = + new LinkedList(); + + 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 getLeastInterleavingsAsPredecessor + (List interleavings) + { + List leastInterleavingsAsPredecessor = + new LinkedList(); + + 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 getMostInterleavingsAsSuccessor + (List interleavings) + { + List mostInterleavingsAsSuccessor = + new LinkedList(); + + 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 removeCollisionsOfOtherSubsequences + (List interleavings) + { + List subsequencesWithoutOtherCollisions = + new LinkedList(); + + for (InterleavingSubsequence interleaving : interleavings) { + List reducedPredecessorCollisions = new LinkedList<>(); + + for (Collision collision : interleaving.getPredecessorCollisions()) { + for (InterleavingSubsequence otherInterleaving : interleavings) { + if (otherInterleaving.getSubsequence() == collision.getCollidingWith()) { + reducedPredecessorCollisions.add(collision); + break; + } + } + } + + List 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,29 +1217,28 @@ 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 task : appData.getLastFoundTasks()) { + for (Subsequence subsequence : appData.getLastFoundSubsequences()) { ISequence sequence = taskFactory.createNewSequence(); - Console.traceln(Level.FINEST, "replacing " + sequence.getId() + ": " + task); - - List sequenceInstances = - replaceTaskOccurrences(task, appData.getSessions(), sequence); - - harmonizeSequenceInstancesModel(sequence, sequenceInstances, task.size()); + Console.traceln(Level.FINEST, "replacing " + sequence.getId() + ": " + subsequence); + + List 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,5 +1250,5 @@ int sequenceLength) { - TaskInstanceComparator comparator = preparationTaskHandlingStrategy.getTaskComparator(); + TaskComparator comparator = preparationTaskHandlingStrategy.getTaskComparator(); // ensure for each subtask that lexically different variants are preserved @@ -660,7 +1308,7 @@ * @param tree */ - private List replaceTaskOccurrences(List task, - List sessions, - ISequence temporalTaskModel) + private List replaceSubsequenceOccurrences(Subsequence subsequence, + List sessions, + ISequence temporalTaskModel) { List sequenceInstances = new LinkedList(); @@ -668,12 +1316,13 @@ 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,5 +1340,5 @@ */ private int getSubListIndex(ITaskInstanceList list, - List subList, + Subsequence subsequence, int startIndex) { @@ -697,12 +1346,12 @@ 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,19 +1373,19 @@ * @return */ - private int getSubListIndex(List list, - List 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,9 +1401,110 @@ return result; } + +// /** +// * +// */ +// private void dumpSorted(List interleavings) { +// dumpSorted(interleavings, Level.FINEST); +// } + + /** + * + */ + private void dumpSorted(List interleavings, Level level) { + List tmpList = new LinkedList(); + + 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 subsequences) +// { +// List tmpList = new LinkedList(); +// +// 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 { + private class MaxCountAndLongestSubsequencesFinder implements TrieProcessor { /** @@ -766,10 +1516,10 @@ * */ - private List> foundTasks = new LinkedList>(); + private LinkedList foundSubsequences = new LinkedList(); /** * */ - public MaxCountAndLongestTasksFinder() { + public MaxCountAndLongestSubsequencesFinder() { super(); this.currentCount = 0; @@ -780,5 +1530,5 @@ */ @Override - public TrieProcessor.Result process(List foundTask, int count) { + public TrieProcessor.Result process(List foundTask, int count) { if (foundTask.size() < 2) { // ignore single tasks @@ -800,5 +1550,5 @@ // 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,8 +1558,7 @@ // 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(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,5 +1567,5 @@ if (!added) { - foundTasks.add(new LinkedList(foundTask)); // defensive copy + foundSubsequences.add(new Subsequence(currentCount, foundTask)); } } @@ -828,7 +1577,7 @@ * @return */ - public Tasks getFoundTasks() { + private Subsequences getFoundSubsequences() { removePermutationsOfShorterTasks(); - return new Tasks(currentCount, foundTasks); + return new Subsequences(currentCount, foundSubsequences); } @@ -839,18 +1588,62 @@ // 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 longTask = foundTasks.get(i); - List 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,9 +1651,16 @@ } } - } - } - - } - + + if (removeI) { + foundSubsequences.remove(i); + } + else { + i++; + } + } + } + + } + // /** // * @author Patrick Harms @@ -929,12 +1729,12 @@ /** - * 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,15 +1782,15 @@ /** - * @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,6 +1798,6 @@ * @param lastFoundSequences the lastFoundSequences to set */ - private void setLastFoundTasks(Tasks lastFoundSequences) { - this.lastFoundTasks = lastFoundSequences; + private void setLastFoundSubsequences(Subsequences lastFoundSequences) { + this.lastFoundSubsequences = lastFoundSequences; } @@ -1005,6 +1805,6 @@ * @return the lastFoundSequences */ - private Tasks getLastFoundTasks() { - return lastFoundTasks; + private Subsequences getLastFoundSubsequences() { + return lastFoundSubsequences; } @@ -1039,9 +1839,8 @@ } - /** * @author Patrick Harms */ - private static class Tasks implements Iterable> { + private static class Subsequence implements Iterable { /** @@ -1049,9 +1848,65 @@ */ private int occurrenceCount; - + /** * */ - private List> sequences; + private List subsequence; + + /** + * @param occurrenceCount + * @param subsequences + */ + private Subsequence(int occurrenceCount, List subsequence) { + super(); + this.occurrenceCount = occurrenceCount; + this.subsequence = new ArrayList(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 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 { + + /** + * + */ + private int occurrenceCount; + + /** + * + */ + private LinkedList subsequences; /** @@ -1059,8 +1914,22 @@ * @param sequences */ - private Tasks(int occurrenceCount, List> sequences) { + private Subsequences(int occurrenceCount, LinkedList subsequences) { super(); this.occurrenceCount = occurrenceCount; - this.sequences = sequences; + this.subsequences = subsequences; + } + + /** + * + */ + private void remove(Subsequence subsequence) { + ListIterator it = subsequences.listIterator(); + + while (it.hasNext()) { + // reference comparison is sufficient + if (it.next() == subsequence) { + it.remove(); + } + } } @@ -1076,10 +1945,6 @@ */ private int size() { - return this.sequences.size(); - } - - /** - * - */ + return this.subsequences.size(); + } /* (non-Javadoc) @@ -1087,6 +1952,6 @@ */ @Override - public Iterator> iterator() { - return this.sequences.iterator(); + public Iterator iterator() { + return this.subsequences.iterator(); } @@ -1097,9 +1962,10 @@ public String toString() { StringBuffer result = new StringBuffer(); + result.append(" subsequences occuring "); result.append(this.occurrenceCount); - result.append(" occurrences:\n"); - - for (List task : sequences) { - result.append(task); + result.append(" times:\n"); + + for (Subsequence subsequence : subsequences) { + result.append(subsequence); result.append("\n"); } @@ -1107,5 +1973,182 @@ return result.toString(); } - + } + + /** + * @author Patrick Harms + */ + private static class InterleavingSubsequence { + + /** */ + private Subsequence subsequence; + + /** */ + private List successorCollisions; + + /** */ + private List predecessorCollisions; + + /** + * + */ + private InterleavingSubsequence(Subsequence subsequence, + List predecessorCollisions, + List 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 getSuccessorCollisions() { + return successorCollisions; + } + + /** + * + */ + private int getPredecessorCollisionCounter() { + return predecessorCollisions.size(); + } + + /** + * + */ + private List 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 + ")"; + } }