Index: /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/algorithms/MatrixEntry.java =================================================================== --- /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/algorithms/MatrixEntry.java (revision 1558) +++ /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/algorithms/MatrixEntry.java (revision 1559) @@ -4,4 +4,6 @@ private float score; private MatrixEntry previous; + private int xvalue; + private int yvalue; public MatrixEntry(float score, MatrixEntry previous) { @@ -25,3 +27,19 @@ this.previous = previous; } + + public int getXvalue() { + return xvalue; + } + + public void setXvalue(int xvalue) { + this.xvalue = xvalue; + } + + public int getYvalue() { + return yvalue; + } + + public void setYvalue(int yvalue) { + this.yvalue = yvalue; + } } Index: /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/algorithms/NumberSequence.java =================================================================== --- /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/algorithms/NumberSequence.java (revision 1558) +++ /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/algorithms/NumberSequence.java (revision 1559) @@ -29,5 +29,5 @@ { for (int i = 0; i < sequence.length; i++) { - System.out.format("%4d", sequence[i]); + System.out.format("%5d", sequence[i]); } System.out.println(); Index: /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/algorithms/SmithWatermanRepeated.java =================================================================== --- /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/algorithms/SmithWatermanRepeated.java (revision 1558) +++ /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/algorithms/SmithWatermanRepeated.java (revision 1559) @@ -51,5 +51,5 @@ matrix = new MatrixEntry[length1+2][length2+1]; - for (int i = 0; i <= length1; i++) { + for (int i = 0; i <= length1+1; i++) { for(int j = 0; j< length2; j++) { matrix[i][j] = new MatrixEntry(); @@ -71,20 +71,10 @@ * @return Cost of substitution of the character in str1 by the one in str2 */ - private float similarity(int i, int j) { - if (i == 0 || j == 0) { - // it's a gap - return submat.getGapPenalty(); - } - // System.out.println("Diag letters: " + input1[i-1] + " " + - // input2[j-1]); - // return (input1[i - 1] == input2[j - 1]) ? MATCH_SCORE : - // MISMATCH_SCORE; + private float similarity(int i, int j) { return submat.getDistance(input1[i - 1], input2[j - 1]); } /** - * Build the score matrix using dynamic programming. Note: The indel scores - * must be negative. Otherwise, the part handling the first row and column - * has to be modified. + * Build the score matrix using dynamic programming. */ private void buildMatrix() { @@ -93,6 +83,5 @@ } - - // base case + // it's a gap matrix[0][0].setScore(0); matrix[0][0].setPrevious(null); // starting point @@ -107,5 +96,5 @@ - for (int i = 1; i <= length1; i++) { + for (int i = 1; i <= length1 + 1; i++) { // Formula for first row: @@ -113,24 +102,52 @@ float firstRowLeftScore = matrix[i-1][0].getScore(); - float tempMax = matrix[i-1][1].getScore(); - - //position of the maximal score of the previous row - int maxRowIndex = 1; - - for(int j = 2; j < length2;j++) { - if(matrix[i-1][j].getScore() > tempMax) { - tempMax = matrix[i-1][j].getScore(); - maxRowIndex = j; - } - } - + //for sequences of length 1 + float tempMax; + int maxRowIndex; + if(length2 == 1) { + tempMax = matrix[i-1][0].getScore(); + maxRowIndex = 0; + } else { + tempMax = matrix[i-1][1].getScore(); + maxRowIndex = 1; + //position of the maximal score of the previous row + + for(int j = 2; j < length2;j++) { + if(matrix[i-1][j].getScore() > tempMax) { + tempMax = matrix[i-1][j].getScore(); + maxRowIndex = j; + } + } + + } + + tempMax -= scoreThreshold; matrix[i][0].setScore(Math.max(firstRowLeftScore, tempMax)); + if(tempMax ==matrix[i][0].getScore()){ + matrix[i][0].setPrevious(matrix[i-1][maxRowIndex]); + } + + if(firstRowLeftScore == matrix[i][0].getScore()) { + matrix[i][0].setPrevious(matrix[i-1][0]); + } + + //The last additional score is not related to a character in the input sequence, it's the total score. Therefore we don't need to save something for it + if(i(); matrix = new TriangleMatrix(uniqueTasks.size()+1); - gapPenalty = -10; + gapPenalty = -5; } Index: /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/temporalrelation/SequenceForTaskDetectionRuleAlignment.java =================================================================== --- /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/temporalrelation/SequenceForTaskDetectionRuleAlignment.java (revision 1558) +++ /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/temporalrelation/SequenceForTaskDetectionRuleAlignment.java (revision 1559) @@ -51,16 +51,18 @@ /** *

- * This class implements the major rule for creating task trees based on a set of recorded - * user sessions. For this, it first harmonizes all tasks. This eases later comparison. Then it - * searches the sessions for iterations and replaces them accordingly. Then it searches for sub - * sequences being the longest and occurring most often. For each found sub sequence, it replaces - * the occurrences by creating appropriate {@link ISequence}s. Afterwards, again searches for - * iterations and then again for sub sequences until no more replacements are done. + * This class implements the major rule for creating task trees based on a set + * of recorded user sessions. For this, it first harmonizes all tasks. This + * eases later comparison. Then it searches the sessions for iterations and + * replaces them accordingly. Then it searches for sub sequences being the + * longest and occurring most often. For each found sub sequence, it replaces + * the occurrences by creating appropriate {@link ISequence}s. Afterwards, again + * searches for iterations and then again for sub sequences until no more + * replacements are done. *

*

- * For determining the longest sequence occurring most often, the implementation uses a - * {@link Trie}. The depth of the tree is initially 3. If the algorithm has a longest sequence - * occurring most often whose length is equal to the depth of the trie, it recalculates the trie - * with an increased depth. + * For determining the longest sequence occurring most often, the implementation + * uses a {@link Trie}. The depth of the tree is initially 3. If the algorithm + * has a longest sequence occurring most often whose length is equal to the + * depth of the trie, it recalculates the trie with an increased depth. *

* @@ -68,1115 +70,1201 @@ */ class SequenceForTaskDetectionRuleAlignment implements ISessionScopeRule { - - /** - *

- * the task factory to be used for creating substructures for the temporal - * relationships identified during rul application - *

- */ - private ITaskFactory taskFactory; - /** - *

- * the task builder to be used for creating substructures for the temporal relationships - * identified during rule application - *

- */ - private ITaskBuilder taskBuilder; - - /** - *

- * the task handling strategy to be used for comparing tasks for preparation, i.e., before - * the tasks are harmonized - *

- */ - private TaskHandlingStrategy preparationTaskHandlingStrategy; - - /** - *

- * the task handling strategy to be used for comparing tasks during iteration detection an trie - * generation, i.e., after the tasks are harmonized - *

- */ - private TaskHandlingStrategy identityTaskHandlingStrategy;; - - - private ArrayList numberseqs; - - /** - *

- * instantiates the rule and initializes it with a task equality to be considered when - * comparing tasks as well as a task factory and builder to be used for creating task - * structures. - *

- * - * @param minimalTaskEquality the task equality to be considered when comparing tasks - * @param taskFactory the task factory to be used for creating substructures - * @param taskBuilder the task builder to be used for creating substructures - */ - - - SequenceForTaskDetectionRuleAlignment(TaskEquality minimalTaskEquality, - ITaskFactory taskFactory, - ITaskBuilder taskBuilder) - { - this.taskFactory = taskFactory; - this.taskBuilder = taskBuilder; - - this.preparationTaskHandlingStrategy = new TaskHandlingStrategy(minimalTaskEquality); - this.identityTaskHandlingStrategy = new TaskHandlingStrategy(TaskEquality.IDENTICAL); - numberseqs = new ArrayList(); - - } - - /* (non-Javadoc) - * @see java.lang.Object#toString() - */ - @Override - public String toString() { - return "SequenceForTaskDetectionRuleAlignment"; - } - - /* (non-Javadoc) - * @see de.ugoe.cs.autoquest.tasktrees.temporalrelation.ISessionScopeRule#apply(java.util.List) - */ - @Override - public RuleApplicationResult apply(List sessions) { - RuleApplicationData appData = new RuleApplicationData(sessions); - - - - // this is the real rule application. Loop while something is replaced. - SymbolMap uniqueTasks = harmonizeEventTaskInstancesModel(appData); - ObjectDistanceSubstitionMatrix submat = new ObjectDistanceSubstitionMatrix(uniqueTasks,20); - submat.generate(); - - - - System.out.print("Sequence 1: "); - NumberSequence ns1 = numberseqs.get(7); - NumberSequence ns2 = numberseqs.get(8); - ns1.printSequence(); - System.out.print("Sequence 2: "); - ns2.printSequence(); - //SmithWatermanRepeated sw = new SmithWatermanRepeated(numberseqs.get(20).getSequence(), numberseqs.get(24).getSequence(), submat,10); - SmithWatermanRepeated sw = new SmithWatermanRepeated(ns1.getSequence(), ns2.getSequence(), submat,15); - System.out.println("Max Scrore: " + sw.getMaxScore()); - - sw.printDPMatrix(); - - - - - do { - System.out.println(); - FengDoolittle fd = new FengDoolittle(); - - - //appData.getStopWatch().start("whole loop"); - //detectAndReplaceIterations(appData); - - //appData.getStopWatch().start("task replacement"); - //detectAndReplaceTasks(appData); - //appData.getStopWatch().stop("task replacement"); - //appData.getStopWatch().stop("whole loop"); - - - //appData.getStopWatch().dumpStatistics(System.out); - //appData.getStopWatch().reset(); - - } - while (appData.detectedAndReplacedTasks()); - - Console.println - ("created " + appData.getResult().getNewlyCreatedTasks().size() + - " new tasks and " + appData.getResult().getNewlyCreatedTaskInstances().size() + - " appropriate instances\n"); - - if ((appData.getResult().getNewlyCreatedTasks().size() > 0) || - (appData.getResult().getNewlyCreatedTaskInstances().size() > 0)) - { - appData.getResult().setRuleApplicationStatus(RuleApplicationStatus.FINISHED); - } - - return appData.getResult(); - } - - /** - *

- * harmonizes the event task instances by unifying tasks. This is done, as initially the - * event tasks being equal with respect to the considered task equality are distinct objects. - * The comparison of these distinct objects is more time consuming than comparing the object - * references. - *

- * - * @param appData the rule application data combining all data used for applying this rule - * @return Returns the unique tasks symbol map - */ - private SymbolMap harmonizeEventTaskInstancesModel(RuleApplicationData appData) { - Console.traceln(Level.INFO, "harmonizing task model of event task instances"); - appData.getStopWatch().start("harmonizing event tasks"); - - SymbolMap uniqueTasks = - preparationTaskHandlingStrategy.createSymbolMap(); - TaskInstanceComparator comparator = preparationTaskHandlingStrategy.getTaskComparator(); - - int unifiedTasks = 0; - ITask task; - List sessions = appData.getSessions(); - int sessionNo = 0; - numberseqs = new ArrayList(); - for (IUserSession session : sessions) { - Console.traceln(Level.FINE, "handling " + (++sessionNo) + ". " + session); - NumberSequence templist = new NumberSequence(session.size()) ; - - for (int i = 0; i < session.size(); i++) { - ITaskInstance taskInstance = session.get(i); - task = uniqueTasks.getValue(taskInstance); - - if (task == null) { - uniqueTasks.addSymbol(taskInstance, taskInstance.getTask()); - templist.getSequence()[i]=taskInstance.getTask().getId(); - } - else { - taskBuilder.setTask(taskInstance, task); - templist.getSequence()[i]=task.getId(); - unifiedTasks++; - } - } - numberseqs.add(templist); - comparator.clearBuffers(); - } - - appData.getStopWatch().stop("harmonizing event tasks"); - Console.traceln(Level.INFO, "harmonized " + unifiedTasks + " task occurrences (still " + - uniqueTasks.size() + " different tasks)"); - - appData.getStopWatch().dumpStatistics(System.out); - appData.getStopWatch().reset(); + + /** + *

+ * the task factory to be used for creating substructures for the temporal + * relationships identified during rul application + *

+ */ + private ITaskFactory taskFactory; + /** + *

+ * the task builder to be used for creating substructures for the temporal + * relationships identified during rule application + *

+ */ + private ITaskBuilder taskBuilder; + + /** + *

+ * the task handling strategy to be used for comparing tasks for + * preparation, i.e., before the tasks are harmonized + *

+ */ + private TaskHandlingStrategy preparationTaskHandlingStrategy; + + /** + *

+ * the task handling strategy to be used for comparing tasks during + * iteration detection an trie generation, i.e., after the tasks are + * harmonized + *

+ */ + private TaskHandlingStrategy identityTaskHandlingStrategy;; + + private ArrayList numberseqs; + + /** + *

+ * instantiates the rule and initializes it with a task equality to be + * considered when comparing tasks as well as a task factory and builder to + * be used for creating task structures. + *

+ * + * @param minimalTaskEquality + * the task equality to be considered when comparing tasks + * @param taskFactory + * the task factory to be used for creating substructures + * @param taskBuilder + * the task builder to be used for creating substructures + */ + + SequenceForTaskDetectionRuleAlignment(TaskEquality minimalTaskEquality, + ITaskFactory taskFactory, ITaskBuilder taskBuilder) { + this.taskFactory = taskFactory; + this.taskBuilder = taskBuilder; + + this.preparationTaskHandlingStrategy = new TaskHandlingStrategy( + minimalTaskEquality); + this.identityTaskHandlingStrategy = new TaskHandlingStrategy( + TaskEquality.IDENTICAL); + numberseqs = new ArrayList(); + + } + + /* + * (non-Javadoc) + * + * @see java.lang.Object#toString() + */ + @Override + public String toString() { + return "SequenceForTaskDetectionRuleAlignment"; + } + + /* + * (non-Javadoc) + * + * @see + * de.ugoe.cs.autoquest.tasktrees.temporalrelation.ISessionScopeRule#apply + * (java.util.List) + */ + @Override + public RuleApplicationResult apply(List sessions) { + RuleApplicationData appData = new RuleApplicationData(sessions); + + // this is the real rule application. Loop while something is replaced. + SymbolMap uniqueTasks = harmonizeEventTaskInstancesModel(appData); + ObjectDistanceSubstitionMatrix submat = new ObjectDistanceSubstitionMatrix( + uniqueTasks, 5); + submat.generate(); + + // good tests: 7/8 20/24 + for (int i = 0; i < numberseqs.size(); i++) { + for (int j = 0; j < numberseqs.size(); j++) { + + NumberSequence ns1 = numberseqs.get(i); + NumberSequence ns2 = numberseqs.get(j); + + + + SmithWatermanRepeated sw = new SmithWatermanRepeated( + ns1.getSequence(), ns2.getSequence(), submat, 10); + + if(sw.getAlignmentScore() > 0) + { + System.out.println("================================================="); + System.out.println("| Sequence " + String.format("%3d", i) +" Sequence " + String.format("%3d", j) + " |"); + System.out.println("================================================="); + //System.out.print("Sequence " + i + ": "); + //ns1.printSequence(); + //System.out.print("Sequence " + j + ": "); + //ns2.printSequence(); + //System.out.println("Max Scrore: " + sw.getMaxScore()); + System.out.println("Alignment Score: " + sw.getAlignmentScore()); + //sw.printDPMatrix(); + sw.traceback(); + System.out.println(); + System.out.println(); + } + } + } + + do { + System.out.println(); + FengDoolittle fd = new FengDoolittle(); + + // appData.getStopWatch().start("whole loop"); + // detectAndReplaceIterations(appData); + + // appData.getStopWatch().start("task replacement"); + // detectAndReplaceTasks(appData); + // appData.getStopWatch().stop("task replacement"); + // appData.getStopWatch().stop("whole loop"); + + // appData.getStopWatch().dumpStatistics(System.out); + // appData.getStopWatch().reset(); + + } while (appData.detectedAndReplacedTasks()); + + Console.println("created " + + appData.getResult().getNewlyCreatedTasks().size() + + " new tasks and " + + appData.getResult().getNewlyCreatedTaskInstances().size() + + " appropriate instances\n"); + + if ((appData.getResult().getNewlyCreatedTasks().size() > 0) + || (appData.getResult().getNewlyCreatedTaskInstances().size() > 0)) { + appData.getResult().setRuleApplicationStatus( + RuleApplicationStatus.FINISHED); + } + + return appData.getResult(); + } + + /** + *

+ * harmonizes the event task instances by unifying tasks. This is done, as + * initially the event tasks being equal with respect to the considered task + * equality are distinct objects. The comparison of these distinct objects + * is more time consuming than comparing the object references. + *

+ * + * @param appData + * the rule application data combining all data used for applying + * this rule + * @return Returns the unique tasks symbol map + */ + private SymbolMap harmonizeEventTaskInstancesModel( + RuleApplicationData appData) { + Console.traceln(Level.INFO, + "harmonizing task model of event task instances"); + appData.getStopWatch().start("harmonizing event tasks"); + + SymbolMap uniqueTasks = preparationTaskHandlingStrategy + .createSymbolMap(); + TaskInstanceComparator comparator = preparationTaskHandlingStrategy + .getTaskComparator(); + + int unifiedTasks = 0; + ITask task; + List sessions = appData.getSessions(); + int sessionNo = 0; + numberseqs = new ArrayList(); + for (IUserSession session : sessions) { + Console.traceln(Level.FINE, "handling " + (++sessionNo) + ". " + + session); + NumberSequence templist = new NumberSequence(session.size()); + + for (int i = 0; i < session.size(); i++) { + ITaskInstance taskInstance = session.get(i); + task = uniqueTasks.getValue(taskInstance); + + if (task == null) { + uniqueTasks.addSymbol(taskInstance, taskInstance.getTask()); + templist.getSequence()[i] = taskInstance.getTask().getId(); + } else { + taskBuilder.setTask(taskInstance, task); + templist.getSequence()[i] = task.getId(); + unifiedTasks++; + } + } + numberseqs.add(templist); + comparator.clearBuffers(); + } + + appData.getStopWatch().stop("harmonizing event tasks"); + Console.traceln(Level.INFO, "harmonized " + unifiedTasks + + " task occurrences (still " + uniqueTasks.size() + + " different tasks)"); + + appData.getStopWatch().dumpStatistics(System.out); + appData.getStopWatch().reset(); return uniqueTasks; - } - - /** - *

- * searches for direct iterations of single tasks in all sequences and replaces them with - * {@link IIteration}s, respectively appropriate instances. Also all single occurrences of - * a task that is iterated somewhen are replaced with iterations to have again an efficient - * way for task comparisons. - *

- * - * @param appData the rule application data combining all data used for applying this rule - */ - private void detectAndReplaceIterations(RuleApplicationData appData) { - Console.traceln(Level.FINE, "detecting iterations"); - appData.getStopWatch().start("detecting iterations"); - - List sessions = appData.getSessions(); - - Set iteratedTasks = searchIteratedTasks(sessions); - - if (iteratedTasks.size() > 0) { - replaceIterationsOf(iteratedTasks, sessions, appData); - } - - appData.getStopWatch().stop("detecting iterations"); - Console.traceln(Level.INFO, "replaced " + iteratedTasks.size() + " iterated tasks"); - } - - /** - *

- * searches the provided sessions for task iterations. If a task is iterated, it is added - * to the returned set. - *

- * - * @param the session to search for iterations in - * - * @return a set of tasks being iterated somewhere - */ - private Set searchIteratedTasks(List sessions) { - Set iteratedTasks = new HashSet(); - for (IUserSession session : sessions) { - for (int i = 0; i < (session.size() - 1); i++) { - // we prepared the task instances to refer to unique tasks, if they are treated - // as equal. Therefore, we just compare the identity of the tasks of the task - // instances - if (session.get(i).getTask() == session.get(i + 1).getTask()) { - iteratedTasks.add(session.get(i).getTask()); - } - } - } - - return iteratedTasks; - } - - /** - *

- * replaces all occurrences of all tasks provided in the set with iterations - *

- * - * @param iteratedTasks the tasks to be replaced with iterations - * @param sessions the sessions in which the tasks are to be replaced - * @param appData the rule application data combining all data used for applying this rule - */ - private void replaceIterationsOf(Set iteratedTasks, - List sessions, - RuleApplicationData appData) - { - Map iterations = new HashMap(); - Map> iterationInstances = - new HashMap>(); - - for (ITask iteratedTask : iteratedTasks) { - IIteration iteration = taskFactory.createNewIteration(); - iterations.put(iteratedTask, iteration); - iterationInstances.put(iteration, new LinkedList()); - } - - IIterationInstance iterationInstance; - - for (IUserSession session : sessions) { - int index = 0; - iterationInstance = null; - - while (index < session.size()) { - // we prepared the task instances to refer to unique tasks, if they are treated - // as equal. Therefore, we just compare the identity of the tasks of the task - // instances - ITask currentTask = session.get(index).getTask(); - IIteration iteration = iterations.get(currentTask); - if (iteration != null) { - if ((iterationInstance == null) || (iterationInstance.getTask() != iteration)) - { - iterationInstance = taskFactory.createNewTaskInstance(iteration); - iterationInstances.get(iteration).add(iterationInstance); - taskBuilder.addTaskInstance(session, index, iterationInstance); - index++; - } - - taskBuilder.addChild(iterationInstance, session.get(index)); - taskBuilder.removeTaskInstance(session, index); - } - else { - if (iterationInstance != null) { - iterationInstance = null; - } - index++; - } - } - } - - for (Map.Entry> entry : iterationInstances.entrySet()) - { - harmonizeIterationInstancesModel(entry.getKey(), entry.getValue()); - } - } - - /** - *

- * TODO clarify why this is done - *

- */ - private void harmonizeIterationInstancesModel(IIteration iteration, - List iterationInstances) - { - List iteratedTaskVariants = new LinkedList(); - TaskInstanceComparator comparator = preparationTaskHandlingStrategy.getTaskComparator(); - - // merge the lexically different variants of iterated task to a unique list - for (IIterationInstance iterationInstance : iterationInstances) { - for (ITaskInstance executionVariant : iterationInstance) { - ITask candidate = executionVariant.getTask(); - - boolean found = false; - for (ITask taskVariant : iteratedTaskVariants) { - if (comparator.areLexicallyEqual(taskVariant, candidate)) { - taskBuilder.setTask(executionVariant, taskVariant); - found = true; - break; - } - } - - if (!found) { - iteratedTaskVariants.add(candidate); - } - } - } - - // if there are more than one lexically different variant of iterated tasks, adapt the - // iteration model to be a selection of different variants. In this case also adapt - // the generated iteration instances to correctly contain selection instances. If there - // is only one variant of an iterated task, simply set this as the marked task of the - // iteration. In this case, the instances can be preserved as is - if (iteratedTaskVariants.size() > 1) { - ISelection selection = taskFactory.createNewSelection(); - - for (ITask variant : iteratedTaskVariants) { - taskBuilder.addChild(selection, variant); - } - - taskBuilder.setMarkedTask(iteration, selection); - - for (IIterationInstance instance : iterationInstances) { - for (int i = 0; i < instance.size(); i++) { - ISelectionInstance selectionInstance = - taskFactory.createNewTaskInstance(selection); - taskBuilder.setChild(selectionInstance, instance.get(i)); - taskBuilder.setTaskInstance(instance, i, selectionInstance); - } - } - } - else { - taskBuilder.setMarkedTask(iteration, iteratedTaskVariants.get(0)); - } - } - - /** - * TODO go on commenting - * @param appData the rule application data combining all data used for applying this rule - */ - private void detectAndReplaceTasks(RuleApplicationData appData) { - Console.traceln(Level.FINE, "detecting and replacing tasks"); - appData.getStopWatch().start("detecting tasks"); - - getSequencesOccuringMostOften(appData); - - appData.getStopWatch().stop("detecting tasks"); - appData.getStopWatch().start("replacing tasks"); - - replaceSequencesOccurringMostOften(appData); - - appData.getStopWatch().stop("replacing tasks"); - Console.traceln(Level.INFO, "detected and replaced " + appData.getLastFoundTasks().size() + - " tasks occuring " + appData.getLastFoundTasks().getOccurrenceCount() + - " times"); - } - - /** - * @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; - boolean createNewTrie = (appData.getLastTrie() == null) || - appData.detectedAndReplacedTasks(); // tree has changed - - do { - if (createNewTrie) { - createNewTrie(appData); - } - - MaxCountAndLongestTasksFinder finder = new MaxCountAndLongestTasksFinder(); - appData.getLastTrie().process(finder); - - tasks = finder.getFoundTasks(); - - createNewTrie = false; - - for (List task : tasks) { - if (task.size() >= appData.getTrainedSequenceLength()) { - // 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); - createNewTrie = true; - break; - } - } - } - while (createNewTrie); - - // create a normal trie for comparison - /*System.out.println("creating test trie for comparison"); - - appData.getStopWatch().start("testtrie"); - Trie trie = new Trie(identityTaskComparator); - - for (IUserSession session : appData.getSessions()) { - trie.train(session.getExecutedTasks(), appData.getTrainedSequenceLength()); - } - - appData.getStopWatch().stop("testtrie"); - - MaxCountAndLongestTasksFinder finder = new MaxCountAndLongestTasksFinder(); - trie.process(finder); - - boolean allTasksEqual = finder.getFoundTasks().size() == tasks.size(); - - allTasksEqual &= finder.getFoundTasks().occurrenceCount == tasks.occurrenceCount; - - for (List task1 : finder.getFoundTasks()) { - boolean foundTask = false; - for (List task2 : tasks) { - boolean tasksEqual = false; - if (task1.size() == task2.size()) { - tasksEqual = true; - for (int i = 0; i < task1.size(); i++) { - if (!identityTaskComparator.equals(task1.get(i).getTask(), task2.get(i).getTask())) - { - tasksEqual = false; - } - } - } - - if (tasksEqual) { - foundTask = true; - break; - } - } - - if (!foundTask) { - System.out.println("different is " + task1); - allTasksEqual = false; - break; - } - } - - if (!allTasksEqual) { - System.out.println(finder.getFoundTasks()); - System.out.println(tasks); - - throw new IllegalArgumentException("both tries calculated different subsequences"); - } - - /*TrieStatisticsDumper dumper = new TrieStatisticsDumper(); - appData.getLastTrie().process(dumper); - dumper.dumpCounters();*/ - - appData.setLastFoundTasks(tasks); - - Console.traceln(Level.FINE, "found " + appData.getLastFoundTasks().size() + " tasks " + - "occurring " + appData.getLastFoundTasks().getOccurrenceCount() + " times"); - } - - /** - * @param appData the rule application data combining all data used for applying this rule - */ - private void createNewTrie(RuleApplicationData appData) { - Console.traceln(Level.FINER, "training trie with a maximum sequence length of " + - appData.getTrainedSequenceLength()); - - appData.getStopWatch().start("training trie"); - - // 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 - appData.setLastTrie(new TaskInstanceTrie(identityTaskHandlingStrategy)); - - appData.getLastTrie().trainSessions - (appData.getSessions(), appData.getTrainedSequenceLength()); - - appData.getStopWatch().stop("training trie"); - } - - /** - * @param appData the rule application data combining all data used for applying this rule - */ - private void replaceSequencesOccurringMostOften(RuleApplicationData appData) { - appData.detectedAndReplacedTasks(false); - - if ((appData.getLastFoundTasks().size() > 0) && - (appData.getLastFoundTasks().getOccurrenceCount() > 1)) - { - Console.traceln(Level.FINER, "replacing tasks occurrences"); - - for (List task : appData.getLastFoundTasks()) { - ISequence sequence = taskFactory.createNewSequence(); - - Console.traceln(Level.FINEST, "replacing " + sequence.getId() + ": " + task); - - List sequenceInstances = - replaceTaskOccurrences(task, appData.getSessions(), sequence); - - harmonizeSequenceInstancesModel(sequence, sequenceInstances,task.size()); - appData.detectedAndReplacedTasks - (appData.detectedAndReplacedTasks() || (sequenceInstances.size() > 0)); - - if (sequenceInstances.size() < appData.getLastFoundTasks().getOccurrenceCount()) { - Console.traceln(Level.FINE, sequence.getId() + ": replaced task only " + - sequenceInstances.size() + " times instead of expected " + - appData.getLastFoundTasks().getOccurrenceCount()); - } - } - } - - } - - /** + } + + /** + *

+ * searches for direct iterations of single tasks in all sequences and + * replaces them with {@link IIteration}s, respectively appropriate + * instances. Also all single occurrences of a task that is iterated + * somewhen are replaced with iterations to have again an efficient way for + * task comparisons. + *

+ * + * @param appData + * the rule application data combining all data used for applying + * this rule + */ + private void detectAndReplaceIterations(RuleApplicationData appData) { + Console.traceln(Level.FINE, "detecting iterations"); + appData.getStopWatch().start("detecting iterations"); + + List sessions = appData.getSessions(); + + Set iteratedTasks = searchIteratedTasks(sessions); + + if (iteratedTasks.size() > 0) { + replaceIterationsOf(iteratedTasks, sessions, appData); + } + + appData.getStopWatch().stop("detecting iterations"); + Console.traceln(Level.INFO, "replaced " + iteratedTasks.size() + + " iterated tasks"); + } + + /** + *

+ * searches the provided sessions for task iterations. If a task is + * iterated, it is added to the returned set. + *

+ * + * @param the + * session to search for iterations in + * + * @return a set of tasks being iterated somewhere + */ + private Set searchIteratedTasks(List sessions) { + Set iteratedTasks = new HashSet(); + for (IUserSession session : sessions) { + for (int i = 0; i < (session.size() - 1); i++) { + // we prepared the task instances to refer to unique tasks, if + // they are treated + // as equal. Therefore, we just compare the identity of the + // tasks of the task + // instances + if (session.get(i).getTask() == session.get(i + 1).getTask()) { + iteratedTasks.add(session.get(i).getTask()); + } + } + } + + return iteratedTasks; + } + + /** + *

+ * replaces all occurrences of all tasks provided in the set with iterations + *

+ * + * @param iteratedTasks + * the tasks to be replaced with iterations + * @param sessions + * the sessions in which the tasks are to be replaced + * @param appData + * the rule application data combining all data used for applying + * this rule + */ + private void replaceIterationsOf(Set iteratedTasks, + List sessions, RuleApplicationData appData) { + Map iterations = new HashMap(); + Map> iterationInstances = new HashMap>(); + + for (ITask iteratedTask : iteratedTasks) { + IIteration iteration = taskFactory.createNewIteration(); + iterations.put(iteratedTask, iteration); + iterationInstances.put(iteration, + new LinkedList()); + } + + IIterationInstance iterationInstance; + + for (IUserSession session : sessions) { + int index = 0; + iterationInstance = null; + + while (index < session.size()) { + // we prepared the task instances to refer to unique tasks, if + // they are treated + // as equal. Therefore, we just compare the identity of the + // tasks of the task + // instances + ITask currentTask = session.get(index).getTask(); + IIteration iteration = iterations.get(currentTask); + if (iteration != null) { + if ((iterationInstance == null) + || (iterationInstance.getTask() != iteration)) { + iterationInstance = taskFactory + .createNewTaskInstance(iteration); + iterationInstances.get(iteration) + .add(iterationInstance); + taskBuilder.addTaskInstance(session, index, + iterationInstance); + index++; + } + + taskBuilder.addChild(iterationInstance, session.get(index)); + taskBuilder.removeTaskInstance(session, index); + } else { + if (iterationInstance != null) { + iterationInstance = null; + } + index++; + } + } + } + + for (Map.Entry> entry : iterationInstances + .entrySet()) { + harmonizeIterationInstancesModel(entry.getKey(), entry.getValue()); + } + } + + /** + *

+ * TODO clarify why this is done + *

+ */ + private void harmonizeIterationInstancesModel(IIteration iteration, + List iterationInstances) { + List iteratedTaskVariants = new LinkedList(); + TaskInstanceComparator comparator = preparationTaskHandlingStrategy + .getTaskComparator(); + + // merge the lexically different variants of iterated task to a unique + // list + for (IIterationInstance iterationInstance : iterationInstances) { + for (ITaskInstance executionVariant : iterationInstance) { + ITask candidate = executionVariant.getTask(); + + boolean found = false; + for (ITask taskVariant : iteratedTaskVariants) { + if (comparator.areLexicallyEqual(taskVariant, candidate)) { + taskBuilder.setTask(executionVariant, taskVariant); + found = true; + break; + } + } + + if (!found) { + iteratedTaskVariants.add(candidate); + } + } + } + + // if there are more than one lexically different variant of iterated + // tasks, adapt the + // iteration model to be a selection of different variants. In this case + // also adapt + // the generated iteration instances to correctly contain selection + // instances. If there + // is only one variant of an iterated task, simply set this as the + // marked task of the + // iteration. In this case, the instances can be preserved as is + if (iteratedTaskVariants.size() > 1) { + ISelection selection = taskFactory.createNewSelection(); + + for (ITask variant : iteratedTaskVariants) { + taskBuilder.addChild(selection, variant); + } + + taskBuilder.setMarkedTask(iteration, selection); + + for (IIterationInstance instance : iterationInstances) { + for (int i = 0; i < instance.size(); i++) { + ISelectionInstance selectionInstance = taskFactory + .createNewTaskInstance(selection); + taskBuilder.setChild(selectionInstance, instance.get(i)); + taskBuilder.setTaskInstance(instance, i, selectionInstance); + } + } + } else { + taskBuilder.setMarkedTask(iteration, iteratedTaskVariants.get(0)); + } + } + + /** + * TODO go on commenting + * + * @param appData + * the rule application data combining all data used for applying + * this rule + */ + private void detectAndReplaceTasks(RuleApplicationData appData) { + Console.traceln(Level.FINE, "detecting and replacing tasks"); + appData.getStopWatch().start("detecting tasks"); + + getSequencesOccuringMostOften(appData); + + appData.getStopWatch().stop("detecting tasks"); + appData.getStopWatch().start("replacing tasks"); + + replaceSequencesOccurringMostOften(appData); + + appData.getStopWatch().stop("replacing tasks"); + Console.traceln(Level.INFO, "detected and replaced " + + appData.getLastFoundTasks().size() + " tasks occuring " + + appData.getLastFoundTasks().getOccurrenceCount() + " times"); + } + + /** + * @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; + boolean createNewTrie = (appData.getLastTrie() == null) + || appData.detectedAndReplacedTasks(); // tree has changed + + do { + if (createNewTrie) { + createNewTrie(appData); + } + + MaxCountAndLongestTasksFinder finder = new MaxCountAndLongestTasksFinder(); + appData.getLastTrie().process(finder); + + tasks = finder.getFoundTasks(); + + createNewTrie = false; + + for (List task : tasks) { + if (task.size() >= appData.getTrainedSequenceLength()) { + // 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); + createNewTrie = true; + break; + } + } + } while (createNewTrie); + + // create a normal trie for comparison + /* + * System.out.println("creating test trie for comparison"); + * + * appData.getStopWatch().start("testtrie"); Trie trie = + * new Trie(identityTaskComparator); + * + * for (IUserSession session : appData.getSessions()) { + * trie.train(session.getExecutedTasks(), + * appData.getTrainedSequenceLength()); } + * + * appData.getStopWatch().stop("testtrie"); + * + * MaxCountAndLongestTasksFinder finder = new + * MaxCountAndLongestTasksFinder(); trie.process(finder); + * + * boolean allTasksEqual = finder.getFoundTasks().size() == + * tasks.size(); + * + * allTasksEqual &= finder.getFoundTasks().occurrenceCount == + * tasks.occurrenceCount; + * + * for (List task1 : finder.getFoundTasks()) { boolean + * foundTask = false; for (List task2 : tasks) { boolean + * tasksEqual = false; if (task1.size() == task2.size()) { tasksEqual = + * true; for (int i = 0; i < task1.size(); i++) { if + * (!identityTaskComparator.equals(task1.get(i).getTask(), + * task2.get(i).getTask())) { tasksEqual = false; } } } + * + * if (tasksEqual) { foundTask = true; break; } } + * + * if (!foundTask) { System.out.println("different is " + task1); + * allTasksEqual = false; break; } } + * + * if (!allTasksEqual) { System.out.println(finder.getFoundTasks()); + * System.out.println(tasks); + * + * throw new + * IllegalArgumentException("both tries calculated different subsequences" + * ); } + * + * /*TrieStatisticsDumper dumper = new TrieStatisticsDumper(); + * appData.getLastTrie().process(dumper); dumper.dumpCounters(); + */ + + appData.setLastFoundTasks(tasks); + + Console.traceln(Level.FINE, "found " + + appData.getLastFoundTasks().size() + " tasks " + "occurring " + + appData.getLastFoundTasks().getOccurrenceCount() + " times"); + } + + /** + * @param appData + * the rule application data combining all data used for applying + * this rule + */ + private void createNewTrie(RuleApplicationData appData) { + Console.traceln( + Level.FINER, + "training trie with a maximum sequence length of " + + appData.getTrainedSequenceLength()); + + appData.getStopWatch().start("training trie"); + + // 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 + appData.setLastTrie(new TaskInstanceTrie(identityTaskHandlingStrategy)); + + appData.getLastTrie().trainSessions(appData.getSessions(), + appData.getTrainedSequenceLength()); + + appData.getStopWatch().stop("training trie"); + } + + /** + * @param appData + * the rule application data combining all data used for applying + * this rule + */ + private void replaceSequencesOccurringMostOften(RuleApplicationData appData) { + appData.detectedAndReplacedTasks(false); + + if ((appData.getLastFoundTasks().size() > 0) + && (appData.getLastFoundTasks().getOccurrenceCount() > 1)) { + Console.traceln(Level.FINER, "replacing tasks occurrences"); + + for (List task : appData.getLastFoundTasks()) { + ISequence sequence = taskFactory.createNewSequence(); + + Console.traceln(Level.FINEST, "replacing " + sequence.getId() + + ": " + task); + + List sequenceInstances = replaceTaskOccurrences( + task, appData.getSessions(), sequence); + + harmonizeSequenceInstancesModel(sequence, sequenceInstances, + task.size()); + appData.detectedAndReplacedTasks(appData + .detectedAndReplacedTasks() + || (sequenceInstances.size() > 0)); + + if (sequenceInstances.size() < appData.getLastFoundTasks() + .getOccurrenceCount()) { + Console.traceln(Level.FINE, + sequence.getId() + + ": replaced task only " + + sequenceInstances.size() + + " times instead of expected " + + appData.getLastFoundTasks() + .getOccurrenceCount()); + } + } + } + + } + + /** * */ - private void harmonizeSequenceInstancesModel(ISequence sequence, - List sequenceInstances, - int sequenceLength) - { - TaskInstanceComparator comparator = preparationTaskHandlingStrategy.getTaskComparator(); - - // ensure for each subtask that lexically different variants are preserved - for (int subTaskIndex = 0; subTaskIndex < sequenceLength; subTaskIndex++) { - List subTaskVariants = new LinkedList(); - - for (ISequenceInstance sequenceInstance : sequenceInstances) { - ITask candidate = sequenceInstance.get(subTaskIndex).getTask(); - - boolean found = false; - - for (int i = 0; i < subTaskVariants.size(); i++) { - if (comparator.areLexicallyEqual(subTaskVariants.get(i), candidate)) { - taskBuilder.setTask - (sequenceInstance.get(subTaskIndex), subTaskVariants.get(i)); - - found = true; - break; - } - } - - if (!found) { - subTaskVariants.add(candidate); - } - } - - // if there are more than one lexically different variant of the sub task at - // the considered position, adapt the sequence model at that position to have - // a selection of the different variants. In this case also adapt the - // generated sequence instances to correctly contain selection instances. If - // there is only one variant of sub tasks at the given position, simply set - // this variant as the sub task of the selection. In this case, the instances - // can be preserved as is - if (subTaskVariants.size() > 1) { - ISelection selection = taskFactory.createNewSelection(); - - for (ITask variant : subTaskVariants) { - taskBuilder.addChild(selection, variant); - } - - taskBuilder.addChild(sequence, selection); - - for (ISequenceInstance instance : sequenceInstances) { - ISelectionInstance selectionInstance = - taskFactory.createNewTaskInstance(selection); - taskBuilder.setChild(selectionInstance, instance.get(subTaskIndex)); - taskBuilder.setTaskInstance(instance, subTaskIndex, selectionInstance); - } - } - else if (subTaskVariants.size() == 1) { - taskBuilder.addChild(sequence, subTaskVariants.get(0)); - } - } - } - - /** - * @param tree - */ - private List replaceTaskOccurrences(List task, - List sessions, - ISequence temporalTaskModel) - { - List sequenceInstances = new LinkedList(); - - for (IUserSession session : sessions) { - int index = -1; - - do { - index = getSubListIndex(session, task, ++index); - - if (index > -1) { - sequenceInstances.add - (RuleUtils.createNewSubSequenceInRange - (session, index, index + task.size() - 1, temporalTaskModel, - taskFactory, taskBuilder)); - } - } - while (index > -1); - } - - return sequenceInstances; - } - - /** - * @param trie - * @param object - * @return - */ - private int getSubListIndex(ITaskInstanceList list, - List subList, - int startIndex) - { - boolean matchFound; - int result = -1; - - for (int i = startIndex; i <= list.size() - subList.size(); i++) { - matchFound = true; - - for (int j = 0; j < subList.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()) { - matchFound = false; - break; - } - } - - if (matchFound) { - result = i; - break; - } - } - - return result; - } - - /** - * @param trie - * @param object - * @return - */ - private int getSubListIndex(List list, - List subList, - int startIndex) - { - boolean matchFound; - int result = -1; - - for (int i = startIndex; i <= list.size() - subList.size(); i++) { - matchFound = true; - - for (int j = 0; j < subList.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)) { - matchFound = false; - break; - } - } - - if (matchFound) { - result = i; - break; - } - } - - return result; - } - - /** - * @author Patrick Harms - */ - private class MaxCountAndLongestTasksFinder implements TrieProcessor { - - /** + private void harmonizeSequenceInstancesModel(ISequence sequence, + List sequenceInstances, int sequenceLength) { + TaskInstanceComparator comparator = preparationTaskHandlingStrategy + .getTaskComparator(); + + // ensure for each subtask that lexically different variants are + // preserved + for (int subTaskIndex = 0; subTaskIndex < sequenceLength; subTaskIndex++) { + List subTaskVariants = new LinkedList(); + + for (ISequenceInstance sequenceInstance : sequenceInstances) { + ITask candidate = sequenceInstance.get(subTaskIndex).getTask(); + + boolean found = false; + + for (int i = 0; i < subTaskVariants.size(); i++) { + if (comparator.areLexicallyEqual(subTaskVariants.get(i), + candidate)) { + taskBuilder.setTask(sequenceInstance.get(subTaskIndex), + subTaskVariants.get(i)); + + found = true; + break; + } + } + + if (!found) { + subTaskVariants.add(candidate); + } + } + + // if there are more than one lexically different variant of the sub + // task at + // the considered position, adapt the sequence model at that + // position to have + // a selection of the different variants. In this case also adapt + // the + // generated sequence instances to correctly contain selection + // instances. If + // there is only one variant of sub tasks at the given position, + // simply set + // this variant as the sub task of the selection. In this case, the + // instances + // can be preserved as is + if (subTaskVariants.size() > 1) { + ISelection selection = taskFactory.createNewSelection(); + + for (ITask variant : subTaskVariants) { + taskBuilder.addChild(selection, variant); + } + + taskBuilder.addChild(sequence, selection); + + for (ISequenceInstance instance : sequenceInstances) { + ISelectionInstance selectionInstance = taskFactory + .createNewTaskInstance(selection); + taskBuilder.setChild(selectionInstance, + instance.get(subTaskIndex)); + taskBuilder.setTaskInstance(instance, subTaskIndex, + selectionInstance); + } + } else if (subTaskVariants.size() == 1) { + taskBuilder.addChild(sequence, subTaskVariants.get(0)); + } + } + } + + /** + * @param tree + */ + private List replaceTaskOccurrences( + List task, List sessions, + ISequence temporalTaskModel) { + List sequenceInstances = new LinkedList(); + + for (IUserSession session : sessions) { + int index = -1; + + do { + index = getSubListIndex(session, task, ++index); + + if (index > -1) { + sequenceInstances.add(RuleUtils + .createNewSubSequenceInRange(session, index, index + + task.size() - 1, temporalTaskModel, + taskFactory, taskBuilder)); + } + } while (index > -1); + } + + return sequenceInstances; + } + + /** + * @param trie + * @param object + * @return + */ + private int getSubListIndex(ITaskInstanceList list, + List subList, int startIndex) { + boolean matchFound; + int result = -1; + + for (int i = startIndex; i <= list.size() - subList.size(); i++) { + matchFound = true; + + for (int j = 0; j < subList.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()) { + matchFound = false; + break; + } + } + + if (matchFound) { + result = i; + break; + } + } + + return result; + } + + /** + * @param trie + * @param object + * @return + */ + private int getSubListIndex(List list, + List subList, int startIndex) { + boolean matchFound; + int result = -1; + + for (int i = startIndex; i <= list.size() - subList.size(); i++) { + matchFound = true; + + for (int j = 0; j < subList.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)) { + matchFound = false; + break; + } + } + + if (matchFound) { + result = i; + break; + } + } + + return result; + } + + /** + * @author Patrick Harms + */ + private class MaxCountAndLongestTasksFinder implements + TrieProcessor { + + /** * */ - private int currentCount; - - /** + private int currentCount; + + /** * */ - private List> foundTasks = new LinkedList>(); - - /** + private List> foundTasks = new LinkedList>(); + + /** * */ - public MaxCountAndLongestTasksFinder() { - super(); - this.currentCount = 0; - } - - /* (non-Javadoc) - * @see de.ugoe.cs.autoquest.usageprofiles.TrieProcessor#process(java.util.List, int) - */ - @Override - public TrieProcessor.Result process(List foundTask, int count) { - if (foundTask.size() < 2) { - // ignore single tasks - return TrieProcessor.Result.CONTINUE; - } - - if (count < 2) { - // ignore singular occurrences - return TrieProcessor.Result.SKIP_NODE; - } - - if (this.currentCount > count) { - // ignore this children of this task, as they may have only smaller counts than - // the already found tasks - return TrieProcessor.Result.SKIP_NODE; - } - - if (this.currentCount < count) { - // 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(); - this.currentCount = count; - } - - if (this.currentCount == count) { - // the task is of interest. Sort it into the other found tasks so that - // 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 - added = true; - break; - } - } - - if (!added) { - foundTasks.add(new LinkedList(foundTask)); // defensive copy - } - } - - return TrieProcessor.Result.CONTINUE; - } - - /** - * @return - */ - public Tasks getFoundTasks() { - removePermutationsOfShorterTasks(); - return new Tasks(currentCount, foundTasks); - } - - /** + public MaxCountAndLongestTasksFinder() { + super(); + this.currentCount = 0; + } + + /* + * (non-Javadoc) + * + * @see + * de.ugoe.cs.autoquest.usageprofiles.TrieProcessor#process(java.util + * .List, int) + */ + @Override + public TrieProcessor.Result process(List foundTask, + int count) { + if (foundTask.size() < 2) { + // ignore single tasks + return TrieProcessor.Result.CONTINUE; + } + + if (count < 2) { + // ignore singular occurrences + return TrieProcessor.Result.SKIP_NODE; + } + + if (this.currentCount > count) { + // ignore this children of this task, as they may have only + // smaller counts than + // the already found tasks + return TrieProcessor.Result.SKIP_NODE; + } + + if (this.currentCount < count) { + // 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(); + this.currentCount = count; + } + + if (this.currentCount == count) { + // the task is of interest. Sort it into the other found tasks + // so that + // 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 + added = true; + break; + } + } + + if (!added) { + foundTasks.add(new LinkedList(foundTask)); // defensive + // copy + } + } + + return TrieProcessor.Result.CONTINUE; + } + + /** + * @return + */ + public Tasks getFoundTasks() { + removePermutationsOfShorterTasks(); + return new Tasks(currentCount, foundTasks); + } + + /** * */ - private void removePermutationsOfShorterTasks() { - // 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()) { - // 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); - - if (getSubListIndex(longTask, shortTask, 0) > -1) { - foundTasks.remove(j); - } - else { - j++; - } - } - else { - j++; - } - } - } - } - - } - -// /** -// * @author Patrick Harms -// */ -// private class TrieStatisticsDumper implements TrieProcessor { -// -// /** -// * -// */ -// private Map counters = new HashMap(); -// -// /* (non-Javadoc) -// * @see de.ugoe.cs.autoquest.usageprofiles.TrieProcessor#process(java.util.List, int) -// */ -// @Override -// public TrieProcessor.Result process(List subsequence, int count) { -// if (subsequence.size() == 1) { -// Integer value = counters.get(count); -// -// if (value == null) { -// value = 0; -// } -// -// counters.put(count, value + 1); -// -// return TrieProcessor.Result.CONTINUE; -// } -// else { -// // ignore singular occurrences -// return TrieProcessor.Result.SKIP_NODE; -// } -// } -// -// /** -// * @return -// */ -// public void dumpCounters() { -// int dumpedCounters = 0; -// -// int count = 1; -// while (dumpedCounters < counters.size()) { -// Integer value = counters.get(count++); -// if (value != null) { -// System.out.println(value + " symbols occurred " + count + " times"); -// dumpedCounters++; -// } -// } -// } -// -// } - - /** + private void removePermutationsOfShorterTasks() { + // 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()) { + // 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); + + if (getSubListIndex(longTask, shortTask, 0) > -1) { + foundTasks.remove(j); + } else { + j++; + } + } else { + j++; + } + } + } + } + + } + + // /** + // * @author Patrick Harms + // */ + // private class TrieStatisticsDumper implements + // TrieProcessor { + // + // /** + // * + // */ + // private Map counters = new HashMap(); + // + // /* (non-Javadoc) + // * @see + // de.ugoe.cs.autoquest.usageprofiles.TrieProcessor#process(java.util.List, + // int) + // */ + // @Override + // public TrieProcessor.Result process(List subsequence, int + // count) { + // if (subsequence.size() == 1) { + // Integer value = counters.get(count); + // + // if (value == null) { + // value = 0; + // } + // + // counters.put(count, value + 1); + // + // return TrieProcessor.Result.CONTINUE; + // } + // else { + // // ignore singular occurrences + // return TrieProcessor.Result.SKIP_NODE; + // } + // } + // + // /** + // * @return + // */ + // public void dumpCounters() { + // int dumpedCounters = 0; + // + // int count = 1; + // while (dumpedCounters < counters.size()) { + // Integer value = counters.get(count++); + // if (value != null) { + // System.out.println(value + " symbols occurred " + count + " times"); + // dumpedCounters++; + // } + // } + // } + // + // } + + /** * */ - private static class RuleApplicationData { - - /** + private static class RuleApplicationData { + + /** * */ - private List sessions; - - /** + private List sessions; + + /** * */ - private TaskInstanceTrie lastTrie; - - /** - * default and minimum trained sequence length is 3 - */ - private int trainedSequenceLength = 3; - - /** + private TaskInstanceTrie lastTrie; + + /** + * default and minimum trained sequence length is 3 + */ + private int trainedSequenceLength = 3; + + /** * */ - private Tasks lastFoundTasks = new Tasks(Integer.MAX_VALUE, null); - - /** + private Tasks lastFoundTasks = new Tasks(Integer.MAX_VALUE, null); + + /** * */ - private boolean detectedAndReplacedTasks; - - /** + private boolean detectedAndReplacedTasks; + + /** * */ - private RuleApplicationResult result = new RuleApplicationResult(); - - /** + private RuleApplicationResult result = new RuleApplicationResult(); + + /** * */ - private StopWatch stopWatch = new StopWatch(); - - /** + private StopWatch stopWatch = new StopWatch(); + + /** * */ - private RuleApplicationData(List sessions) { - this.sessions = sessions; - } - - /** - * @return the tree - */ - private List getSessions() { - return sessions; - } - - /** - * @param lastTrie the lastTrie to set - */ - private void setLastTrie(TaskInstanceTrie lastTrie) { - this.lastTrie = lastTrie; - } - - /** - * @return the lastTrie - */ - private TaskInstanceTrie getLastTrie() { - return lastTrie; - } - - /** - * @param trainedSequenceLength the trainedSequenceLength to set - */ - private void setTrainedSequenceLength(int trainedSequenceLength) { - this.trainedSequenceLength = trainedSequenceLength; - } - - /** - * @return the trainedSequenceLength - */ - private int getTrainedSequenceLength() { - return trainedSequenceLength; - } - - /** - * @param lastFoundSequences the lastFoundSequences to set - */ - private void setLastFoundTasks(Tasks lastFoundSequences) { - this.lastFoundTasks = lastFoundSequences; - } - - /** - * @return the lastFoundSequences - */ - private Tasks getLastFoundTasks() { - return lastFoundTasks; - } - - /** + private RuleApplicationData(List sessions) { + this.sessions = sessions; + } + + /** + * @return the tree + */ + private List getSessions() { + return sessions; + } + + /** + * @param lastTrie + * the lastTrie to set + */ + private void setLastTrie(TaskInstanceTrie lastTrie) { + this.lastTrie = lastTrie; + } + + /** + * @return the lastTrie + */ + private TaskInstanceTrie getLastTrie() { + return lastTrie; + } + + /** + * @param trainedSequenceLength + * the trainedSequenceLength to set + */ + private void setTrainedSequenceLength(int trainedSequenceLength) { + this.trainedSequenceLength = trainedSequenceLength; + } + + /** + * @return the trainedSequenceLength + */ + private int getTrainedSequenceLength() { + return trainedSequenceLength; + } + + /** + * @param lastFoundSequences + * the lastFoundSequences to set + */ + private void setLastFoundTasks(Tasks lastFoundSequences) { + this.lastFoundTasks = lastFoundSequences; + } + + /** + * @return the lastFoundSequences + */ + private Tasks getLastFoundTasks() { + return lastFoundTasks; + } + + /** * */ - private void detectedAndReplacedTasks(boolean detectedAndReplacedTasks) { - this.detectedAndReplacedTasks = detectedAndReplacedTasks; - } - - /** + private void detectedAndReplacedTasks(boolean detectedAndReplacedTasks) { + this.detectedAndReplacedTasks = detectedAndReplacedTasks; + } + + /** * */ - private boolean detectedAndReplacedTasks() { - return detectedAndReplacedTasks; - } - - /** - * @return the result - */ - private RuleApplicationResult getResult() { - return result; - } - - /** - * @return the stopWatch - */ - private StopWatch getStopWatch() { - return stopWatch; - } - - } - - - /** - * @author Patrick Harms - */ - private static class Tasks implements Iterable> { - - /** + private boolean detectedAndReplacedTasks() { + return detectedAndReplacedTasks; + } + + /** + * @return the result + */ + private RuleApplicationResult getResult() { + return result; + } + + /** + * @return the stopWatch + */ + private StopWatch getStopWatch() { + return stopWatch; + } + + } + + /** + * @author Patrick Harms + */ + private static class Tasks implements Iterable> { + + /** * */ - private int occurrenceCount; - - /** + private int occurrenceCount; + + /** * */ - private List> sequences; - - /** - * @param occurrenceCount - * @param sequences - */ - private Tasks(int occurrenceCount, List> sequences) { - super(); - this.occurrenceCount = occurrenceCount; - this.sequences = sequences; - } - - /** - * @return - */ - private int getOccurrenceCount() { - return occurrenceCount; - } - - /** - * @return - */ - private int size() { - return this.sequences.size(); - } - - /** + private List> sequences; + + /** + * @param occurrenceCount + * @param sequences + */ + private Tasks(int occurrenceCount, List> sequences) { + super(); + this.occurrenceCount = occurrenceCount; + this.sequences = sequences; + } + + /** + * @return + */ + private int getOccurrenceCount() { + return occurrenceCount; + } + + /** + * @return + */ + private int size() { + return this.sequences.size(); + } + + /** * */ - /* (non-Javadoc) - * @see java.lang.Iterable#iterator() - */ - @Override - public Iterator> iterator() { - return this.sequences.iterator(); - } - - /* (non-Javadoc) - * @see java.lang.Object#toString() - */ - @Override - public String toString() { - StringBuffer result = new StringBuffer(); - result.append(this.occurrenceCount); - result.append(" occurrences:\n"); - - for (List task : sequences) { - result.append(task); - result.append("\n"); - } - - return result.toString(); - } - - } - - // methods for internal testing -// private void checkMatchingOfSessions(List> flattenedSessions, -// List sessions, -// String when) -// { -// List> currentFlattenedSessions = flattenSessions(sessions); -// if (flattenedSessions.size() != currentFlattenedSessions.size()) { -// System.out.println("################## number of sessions changed after " + when); -// } -// else { -// for (int i = 0; i < flattenedSessions.size(); i++) { -// List expected = flattenedSessions.get(i); -// List current = currentFlattenedSessions.get(i); -// -// if (expected.size() != current.size()) { -// System.out.println -// ("################## length of session " + i + " changed after " + when); -// } -// else { -// for (int j = 0; j < expected.size(); j++) { -// if (!expected.get(j).equals(current.get(j))) { -// System.out.println("################## event " + j + " of session " + -// i + " changed after " + when); -// } -// } -// } -// } -// } -// } -// -// private List> flattenSessions(List sessions) { -// List> flattenedSessions = new ArrayList>(); -// for (IUserSession session : sessions) { -// List flattenedUserSession = new ArrayList(); -// flatten(session, flattenedUserSession); -// flattenedSessions.add(flattenedUserSession); -// } -// -// return flattenedSessions; -// } -// -// private void flatten(IUserSession iUserSession, List flattenedUserSession) { -// for (ITaskInstance instance : iUserSession) { -// flatten(instance, flattenedUserSession); -// } -// } -// -// private void flatten(ITaskInstance instance, List flattenedUserSession) { -// if (instance instanceof ITaskInstanceList) { -// for (ITaskInstance child : (ITaskInstanceList) instance) { -// flatten(child, flattenedUserSession); -// } -// } -// else if (instance instanceof ISelectionInstance) { -// flatten(((ISelectionInstance) instance).getChild(), flattenedUserSession); -// } -// else if (instance instanceof IOptionalInstance) { -// flatten(((IOptionalInstance) instance).getChild(), flattenedUserSession); -// } -// else if (instance instanceof IEventTaskInstance) { -// flattenedUserSession.add(((IEventTaskInstance) instance).getEvent()); -// } -// } + /* + * (non-Javadoc) + * + * @see java.lang.Iterable#iterator() + */ + @Override + public Iterator> iterator() { + return this.sequences.iterator(); + } + + /* + * (non-Javadoc) + * + * @see java.lang.Object#toString() + */ + @Override + public String toString() { + StringBuffer result = new StringBuffer(); + result.append(this.occurrenceCount); + result.append(" occurrences:\n"); + + for (List task : sequences) { + result.append(task); + result.append("\n"); + } + + return result.toString(); + } + + } + + // methods for internal testing + // private void checkMatchingOfSessions(List> flattenedSessions, + // List sessions, + // String when) + // { + // List> currentFlattenedSessions = flattenSessions(sessions); + // if (flattenedSessions.size() != currentFlattenedSessions.size()) { + // System.out.println("################## number of sessions changed after " + // + when); + // } + // else { + // for (int i = 0; i < flattenedSessions.size(); i++) { + // List expected = flattenedSessions.get(i); + // List current = currentFlattenedSessions.get(i); + // + // if (expected.size() != current.size()) { + // System.out.println + // ("################## length of session " + i + " changed after " + when); + // } + // else { + // for (int j = 0; j < expected.size(); j++) { + // if (!expected.get(j).equals(current.get(j))) { + // System.out.println("################## event " + j + " of session " + + // i + " changed after " + when); + // } + // } + // } + // } + // } + // } + // + // private List> flattenSessions(List sessions) { + // List> flattenedSessions = new ArrayList>(); + // for (IUserSession session : sessions) { + // List flattenedUserSession = new ArrayList(); + // flatten(session, flattenedUserSession); + // flattenedSessions.add(flattenedUserSession); + // } + // + // return flattenedSessions; + // } + // + // private void flatten(IUserSession iUserSession, List + // flattenedUserSession) { + // for (ITaskInstance instance : iUserSession) { + // flatten(instance, flattenedUserSession); + // } + // } + // + // private void flatten(ITaskInstance instance, List + // flattenedUserSession) { + // if (instance instanceof ITaskInstanceList) { + // for (ITaskInstance child : (ITaskInstanceList) instance) { + // flatten(child, flattenedUserSession); + // } + // } + // else if (instance instanceof ISelectionInstance) { + // flatten(((ISelectionInstance) instance).getChild(), + // flattenedUserSession); + // } + // else if (instance instanceof IOptionalInstance) { + // flatten(((IOptionalInstance) instance).getChild(), flattenedUserSession); + // } + // else if (instance instanceof IEventTaskInstance) { + // flattenedUserSession.add(((IEventTaskInstance) instance).getEvent()); + // } + // } }