Index: /trunk/autoquest-core-tasktrees/.classpath =================================================================== --- /trunk/autoquest-core-tasktrees/.classpath (revision 1766) +++ /trunk/autoquest-core-tasktrees/.classpath (revision 1767) @@ -2,10 +2,4 @@ - - - - - - Index: /trunk/autoquest-core-tasktrees/src/main/java/de/ugoe/cs/autoquest/tasktrees/temporalrelation/CondenseSimilarTasksRule.java =================================================================== --- /trunk/autoquest-core-tasktrees/src/main/java/de/ugoe/cs/autoquest/tasktrees/temporalrelation/CondenseSimilarTasksRule.java (revision 1767) +++ /trunk/autoquest-core-tasktrees/src/main/java/de/ugoe/cs/autoquest/tasktrees/temporalrelation/CondenseSimilarTasksRule.java (revision 1767) @@ -0,0 +1,1810 @@ +// Copyright 2012 Georg-August-Universität Göttingen, Germany +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. + +package de.ugoe.cs.autoquest.tasktrees.temporalrelation; + +import java.io.PrintStream; +import java.util.ArrayList; +import java.util.Collection; +import java.util.HashMap; +import java.util.Iterator; +import java.util.LinkedList; +import java.util.List; +import java.util.Map; +import java.util.logging.Level; + +import de.ugoe.cs.autoquest.tasktrees.taskequality.TaskEquality; +import de.ugoe.cs.autoquest.tasktrees.temporalrelation.utils.MostSimilarTaskDeterminer; +import de.ugoe.cs.autoquest.tasktrees.temporalrelation.utils.SimilarTasks; +import de.ugoe.cs.autoquest.tasktrees.temporalrelation.utils.TaskTraversal; +import de.ugoe.cs.autoquest.tasktrees.treeifc.IIteration; +import de.ugoe.cs.autoquest.tasktrees.treeifc.IIterationInstance; +import de.ugoe.cs.autoquest.tasktrees.treeifc.IMarkingTemporalRelationship; +import de.ugoe.cs.autoquest.tasktrees.treeifc.IOptional; +import de.ugoe.cs.autoquest.tasktrees.treeifc.IOptionalInstance; +import de.ugoe.cs.autoquest.tasktrees.treeifc.ISelection; +import de.ugoe.cs.autoquest.tasktrees.treeifc.ISelectionInstance; +import de.ugoe.cs.autoquest.tasktrees.treeifc.ISequence; +import de.ugoe.cs.autoquest.tasktrees.treeifc.ISequenceInstance; +import de.ugoe.cs.autoquest.tasktrees.treeifc.IStructuringTemporalRelationship; +import de.ugoe.cs.autoquest.tasktrees.treeifc.ITask; +import de.ugoe.cs.autoquest.tasktrees.treeifc.ITaskBuilder; +import de.ugoe.cs.autoquest.tasktrees.treeifc.ITaskFactory; +import de.ugoe.cs.autoquest.tasktrees.treeifc.ITaskInstance; +import de.ugoe.cs.autoquest.tasktrees.treeifc.ITaskInstanceList; +import de.ugoe.cs.autoquest.tasktrees.treeifc.ITaskModel; +import de.ugoe.cs.autoquest.tasktrees.treeifc.IUserSession; +import de.ugoe.cs.autoquest.tasktrees.treeifc.TaskPath; +import de.ugoe.cs.util.console.Console; +import difflib.Chunk; +import difflib.Delta; + +/** + *

+ * This rule performs a condensing of a task tree. It searches for similar tasks and merges them + * if possible in to one task with different execution variants. Hence, this rule detects selections + * and optionals. + *

+ *

+ * The similarity of tasks is determined by comparing task traversals. A task traversal is an + * ordered list of the leaf nodes of a task. This is similar to performing a minimal execution of + * the task. The task traversals of two tasks are compared using string comparison algorithms. The + * less differences the lists have, the more similar they are. + *

+ *

+ * If two tasks are similar, they are merged. Merging is done based on the differences between + * the task traversals. Two tasks are merged based on their instances. First, all instances of both + * tasks are flattened. Instances of selections or commonalities of both tasks stay unflattened. + * Then the lists resulting from this flattening are extended with instances of optionals and + * selections which are introduced where required. Finally, the instances are put together to a + * single task again by applying the {@link SequenceForTaskDetectionRule} on them. + *

+ *

+ * Merging has to consider several specific situations. E.g., tasks may look similar but due to + * iterations, they can not be merged correctly. Here, the rule ensures, that these so called + * interleaving iterations are detected, not traversed when traversing a task and its instances, + * and, therefore, preserved. + *

+ *

+ * All details about this rule are described in the extended ACHI2014 paper of Harms "Trace-based + * task tree generation". The extended paper was submitted to the IntSys IARIA Journal. + *

+ * + * @author Patrick Harms + */ +class CondenseSimilarTasksRule implements ISessionScopeRule { + + /** + *

+ * the task factory to be used for creating substructures for the temporal + * relationships identified during rule 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 during iteration detection an trie + * generation, i.e., after the tasks are harmonized + *

+ */ + private TaskHandlingStrategy identTaskHandlStrat; + + /** + *

+ * 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 + */ + CondenseSimilarTasksRule(TaskEquality minimalTaskEquality, + ITaskFactory taskFactory, + ITaskBuilder taskBuilder) + { + this.taskFactory = taskFactory; + this.taskBuilder = taskBuilder; + + this.identTaskHandlStrat = new TaskHandlingStrategy(TaskEquality.IDENTICAL); + } + + /* (non-Javadoc) + * @see java.lang.Object#toString() + */ + @Override + public String toString() { + return "CondenseSimilarTasksRule"; + } + + /* (non-Javadoc) + * @see de.ugoe.cs.autoquest.tasktrees.temporalrelation.ISessionScopeRule#apply(java.util.List) + */ + @Override + public RuleApplicationResult apply(List sessions) { + + // >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> + // >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> TEST IMPLEMENTATION >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> + /*final List formerInstances = new ArrayList<>(); + final List newInstances = new ArrayList<>(); + + try { + ITaskInstanceVisitor visitor = new DefaultTaskInstanceTraversingVisitor() { + @Override + public void visit(IEventTaskInstance eventTaskInstance) { + formerInstances.add(eventTaskInstance); + } + }; + + PrintStream out = new PrintStream(new FileOutputStream(new File("01.out"))); + + for (IUserSession session : sessions) { + new TaskTreeEncoder().encode(session, out, null); + + for (ITaskInstance instance : session) { + instance.accept(visitor); + } + } + out.close(); + } + catch (FileNotFoundException e) { + e.printStackTrace(); + } + + PrintStream fileout = null; + try { + fileout = new PrintStream("sysout.txt"); + } + catch (FileNotFoundException e1) { + e1.printStackTrace(); + } + + PrintStream origOut = System.out; + if (fileout != null) { + System.setOut(fileout); + }*/ + + // <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< + // <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< TEST IMPLEMENTATION <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< + + + RuleApplicationData appData = new RuleApplicationData(sessions); + + do { + //System.out.println("recreating task model"); + appData.setTaskModel(taskFactory.createTaskModel(sessions)); + appData.setMostSimilarTasks(null); + + Console.println("condensing " + appData.getTaskModel().getTasks().size() + " tasks"); + + getMostSimilarTasks(appData); + + if (appData.getMostSimilarTasks() != null) { + /*System.out.println("*************************************************************"); + System.out.println("handling " + appData.getMostSimilarTasks().size() + + " most similar tasks"); + System.out.println("*************************************************************");*/ + for (SimilarTasks mostSimilarTask : appData.getMostSimilarTasks()) { + handleSimilarTasks(mostSimilarTask, appData); + appData.markAsAlreadyCondensed + (mostSimilarTask.getLeftHandSide(), mostSimilarTask.getRightHandSide()); + } + } + + harmonizeEqualMarkingTemporalRelationships(appData); + } + while (appData.getMostSimilarTasks() != null); + + + // >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> + // >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> TEST IMPLEMENTATION >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> + /*try { + ITaskInstanceVisitor visitor = new DefaultTaskInstanceTraversingVisitor() { + @Override + public void visit(IEventTaskInstance eventTaskInstance) { + newInstances.add(eventTaskInstance); + } + }; + + PrintStream out = new PrintStream(new FileOutputStream(new File("02.out"))); + + for (IUserSession session : sessions) { + new TaskTreeEncoder().encode(session, out, null); + + for (ITaskInstance instance : session) { + instance.accept(visitor); + } + } + out.close(); + } + catch (FileNotFoundException e) { + e.printStackTrace(); + } + + System.out.println("sizes " + formerInstances.size() + " " + newInstances.size()); + for (int i = 0; i < newInstances.size(); i++) { + if (formerInstances.get(i) != newInstances.get(i)) { + System.out.println(i + " " + formerInstances.get(i) + " " + newInstances.get(i)); + } + } + + System.setOut(origOut); + fileout.close();*/ + // <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< + // <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< TEST IMPLEMENTATION <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< + + + return appData.finalizeRuleApplicationResult(); + } + + /** + * + */ + private void getMostSimilarTasks(RuleApplicationData appData) { + // determine the list of interesting tasks + Collection allTasks = appData.getTaskModel().getTasks(); + Iterator taskIterator = allTasks.iterator(); + List taskList = new ArrayList(allTasks.size()); + while (taskIterator.hasNext()) { + ITask task = taskIterator.next(); + + if ((task instanceof IStructuringTemporalRelationship)/* && + (!appData.isSelfCreatedTask(task))*/) + { + taskList.add(task); + } + } + + if (taskList.size() > 1) { + List mostSimilarTasks = + appData.getMostSimilarTasksDeterminer().getMostSimilarTasks + (taskList, appData.getTaskModel()); + + if (mostSimilarTasks.size() > 0) { + appData.setMostSimilarTasks(mostSimilarTasks); + } + } + } + + /** + * + */ + private void handleSimilarTasks(SimilarTasks similarTasks, RuleApplicationData appData) { + // we need at least one instance per similar task. If not, it will not work and also + // does not make sense. No instances anymore can be caused by merging and hence + // discarding tasks in preceding merges. + + //similarTasks.dump(System.out); + + if ((similarTasks.getLeftHandSide().getInstances().size() <= 0) || + (similarTasks.getRightHandSide().getInstances().size() <= 0)) + { + /*System.out.println("a task exists that has no instances"); + System.out.println(similarTasks.getLeftHandSide() + " " + + similarTasks.getLeftHandSide().getInstances().size()); + System.out.println(similarTasks.getRightHandSide() + " " + + similarTasks.getRightHandSide().getInstances().size());*/ + + throw new RuntimeException + ("one and the same task seems to belong to several similar tasks"); + } + + similarTasks = SimilarTasks.getMergableLevelOfSimilarity + (similarTasks, identTaskHandlStrat.getTaskComparator()); + + //similarTasks.dump(System.out); + + List flattenInstructions = + getFlattenInstructions(similarTasks, appData); + + for (FlattenInstruction instruction : flattenInstructions) { + instruction.dump(System.out); + } + + int noOfFlattenedInstances = similarTasks.getLeftHandSide().getInstances().size() + + similarTasks.getRightHandSide().getInstances().size(); + + // >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> + // >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> TEST IMPLEMENTATION >>>>>>>>>>>>>>>>>>>>>>>>>>>>> + List excludes = new ArrayList(); + + for (FlattenInstruction instruction : flattenInstructions) { + System.out.println("exclude " + instruction.path); + excludes.add(instruction.path); + } + // <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< + // <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< TEST IMPLEMENTATION <<<<<<<<<<<<<<<<<<<<<<<<<<<<<< + + Map flattenedSessions = + new HashMap(noOfFlattenedInstances); + flattenInstances + (similarTasks.getLeftHandSide(), flattenInstructions, flattenedSessions, excludes); + flattenInstances + (similarTasks.getRightHandSide(), flattenInstructions, flattenedSessions, excludes); + + /*for (IUserSession session : flattenedSessions.values()) { + new TaskTreeEncoder().encode(session, System.out); + }*/ + + List flattenedSessionList = + new LinkedList(flattenedSessions.values()); + + new SequenceForTaskDetectionRule + (TaskEquality.IDENTICAL, taskFactory, taskBuilder).apply(flattenedSessionList); + + Map replacements = new HashMap(); + for (Map.Entry entry : flattenedSessions.entrySet()) { + + + // >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> + // >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> TEST IMPLEMENTATION >>>>>>>>>>>>>>>>>>>>>>>>>>>>> + // the user sessions were sufficiently equal to have now only one common task as child + if (entry.getValue().size() != 1) { + //new TaskTreeEncoder().encode(entry.getValue(), System.out, excludes); + throw new RuntimeException("flattened sessions were not combined as expected"); + } + // <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< + // <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< TEST IMPLEMENTATION <<<<<<<<<<<<<<<<<<<<<<<<<<<<<< + + + replacements.put(entry.getKey(), entry.getValue().get(0)); + } + + + // >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> + // >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> TEST IMPLEMENTATION >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> + int allInstances = similarTasks.getLeftHandSide().getInstances().size() + + similarTasks.getRightHandSide().getInstances().size(); + + if (replacements.size() != allInstances) { + throw new RuntimeException("number of replacements does not match number of instances"); + } + + /*if (replacements.size() > 0) { + System.out.println("replacement task is calculated to be: "); + new TaskTreeEncoder().encode(replacements.values().iterator().next().getTask(), + System.out); + }*/ + + // <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< + // <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< TEST IMPLEMENTATION <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< + + + for (IUserSession session : appData.getSessions()) { + replaceTaskInstances(session, replacements, similarTasks); + } + + + // >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> + // >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> TEST IMPLEMENTATION >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> + if (replacements.size() != 0) { + for (Map.Entry entry : replacements.entrySet()) { + System.out.println + ("did not replace instance " + entry.getKey() + " with " + entry.getValue()); + } + + throw new RuntimeException(); + } + // <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< + // <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< TEST IMPLEMENTATION <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< + } + + /** + * + */ + private List getFlattenInstructions(SimilarTasks similarTasks, + RuleApplicationData appData) + { + TaskTraversal leftHandSideTraversal = similarTasks.getLeftHandSideTraversal(); + TaskTraversal rightHandSideTraversal = similarTasks.getRightHandSideTraversal(); + + List result = new LinkedList(); + TaskInstanceComparator comp = identTaskHandlStrat.getTaskComparator(); + + // first create instructions for the deltas + for (Delta delta : similarTasks.getPatch().getDeltas()) { + if ((delta.getType() == Delta.TYPE.INSERT) || + (delta.getType() == Delta.TYPE.DELETE)) + { + Chunk chunk; + TaskPath insertAfterPath = null; + TaskPath insertBeforePath; + + if (delta.getType() == Delta.TYPE.INSERT) { + chunk = delta.getRevised(); + int pos = delta.getOriginal().getPosition(); + if (pos > 0) { + insertAfterPath = leftHandSideTraversal.getTraversalPaths()[pos - 1]; + } + insertBeforePath = leftHandSideTraversal.getTraversalPaths()[pos]; + } + else { + chunk = delta.getOriginal(); + int pos = delta.getRevised().getPosition(); + if (pos > 0) { + insertAfterPath = rightHandSideTraversal.getTraversalPaths()[pos - 1]; + } + insertBeforePath = rightHandSideTraversal.getTraversalPaths()[pos]; + } + + ITask child = getTaskForChunk(chunk, appData); + IOptional optional; + + if (child instanceof IOptional) { + optional = (IOptional) child; + } + else { + optional = taskFactory.createNewOptional(); + taskBuilder.setMarkedTask(optional, child); + optional = (IOptional) appData.ensureUnique(optional); + createReplacementInstructions(chunk, optional, null, result); + } + + // create a flatten instruction for the non-occurrence of the optional + result.add(new FlattenInstruction(insertAfterPath, insertBeforePath, optional)); + + } + else if (delta.getType() == Delta.TYPE.CHANGE) { + ITask child1; + ITask child2; + + // check, if the change covers the whole traversal. If so reuse the root task. + // Otherwise, create intermediate tasks if required representing both sides + // of changes + if ((delta.getOriginal().getPosition() == 0) && + (delta.getOriginal().size() == similarTasks.getLeftHandSideTraversal().size())) + { + child1 = similarTasks.getLeftHandSide(); + } + else { + child1 = getTaskForChunk(delta.getOriginal(), appData); + } + + if ((delta.getRevised().getPosition() == 0) && + (delta.getRevised().size() == similarTasks.getRightHandSideTraversal().size())) + { + child2 = similarTasks.getRightHandSide(); + } + else { + child2 = getTaskForChunk(delta.getRevised(), appData); + } + + // check if either of the variants is an iteration or optional of the respective + // other variant. If so, ensure, that the iteration or optional are preserved + ITask markedTask1 = (child1 instanceof IMarkingTemporalRelationship) ? + ((IMarkingTemporalRelationship) child1).getMarkedTask() : null; + + ITask markedTask2 = (child2 instanceof IMarkingTemporalRelationship) ? + ((IMarkingTemporalRelationship) child2).getMarkedTask() : null; + + if (comp.equals(markedTask1, child2)) { + if (child1 instanceof IOptional) { + createReplacementInstructions + (delta.getRevised(), (IOptional) child1, null, result); + } + else { + throw new java.lang.UnsupportedOperationException("not implemented yet"); + } + } + else if (comp.equals(markedTask2, child1)) { + if (child2 instanceof IOptional) { + createReplacementInstructions + (delta.getOriginal(), (IOptional) child2, null, result); + } + else { + throw new java.lang.UnsupportedOperationException("not implemented yet"); + } + } + else if ((markedTask1 != null) && (comp.equals(markedTask1, markedTask2))) { + throw new java.lang.UnsupportedOperationException("not implemented yet"); + } + else { + // its time to create a selection of both variants. If one is already + // a selection, it is reused and extended, if required + ITask expectedChild1 = null; + ITask expectedChild2 = null; + + ISelection selection = null; + if (child1 instanceof ISelection) { + selection = (ISelection) child1; + } + + if (child2 instanceof ISelection) { + if (selection == null) { + // only child 2 is a selection --> extend it with child 1 + selection = (ISelection) child2; + addSelectionChildIfRequired(selection, child1); + expectedChild1 = child1; + } + else { + // both are selections --> extend child 1 with variants of child2 + for (ITask child : ((ISelection) child2).getChildren()) { + addSelectionChildIfRequired(selection, child); + } + } + } + else if (selection != null) { + // only child 1 is a selection --> extend it with child 2 + addSelectionChildIfRequired(selection, child2); + expectedChild2 = child2; + } + else if (selection == null) { + // none of both is already a selection, so create a new one with both + // of the children as variants + selection = taskFactory.createNewSelection(); + taskBuilder.addChild(selection, child1); + taskBuilder.addChild(selection, child2); + expectedChild1 = child1; + expectedChild2 = child2; + } + + selection = (ISelection) appData.ensureUnique(selection); + + createReplacementInstructions + (delta.getOriginal(), selection, expectedChild1, result); + createReplacementInstructions + (delta.getRevised(), selection, expectedChild2, result); + } + } + } + + // create instructions to harmonize marking temporal relationships for untraversed tasks + int leftHandSideIndex = 0; + int rightHandSideIndex = 0; + + OUTER: + while (leftHandSideIndex < leftHandSideTraversal.getTraversalPaths().length) { + for (Delta delta : similarTasks.getPatch().getDeltas()) { + if (delta.getOriginal().getPosition() == leftHandSideIndex) { + if (delta.getType() == Delta.TYPE.INSERT) { + rightHandSideIndex += delta.getRevised().size(); + // do not continue OUTER to ensure, that the left hand side and the + // right hand side coming directly after the insert are handled + } + else if (delta.getType() == Delta.TYPE.DELETE) { + leftHandSideIndex += delta.getOriginal().size(); + continue OUTER; + } + else if (delta.getType() == Delta.TYPE.CHANGE) { + leftHandSideIndex += delta.getOriginal().size(); + rightHandSideIndex += delta.getRevised().size(); + continue OUTER; + } + } + } + + TaskPath leftPath = leftHandSideTraversal.getTraversalPaths()[leftHandSideIndex]; + TaskPath rightPath = rightHandSideTraversal.getTraversalPaths()[rightHandSideIndex]; + + if (comp.equals(leftPath.getLast(), rightPath.getLast())) { + if (leftPath.getTask(leftPath.size() - 2) instanceof IOptional) { + IOptional optional = (IOptional) leftPath.getTask(leftPath.size() - 2); + result.add + (new FlattenInstruction(leftPath.subPath(0, leftPath.size()), optional)); + + result.add(new FlattenInstruction(rightPath, optional)); + } + else if (rightPath.getTask(rightPath.size() - 2) instanceof IOptional) { + IOptional optional = (IOptional) rightPath.getTask(rightPath.size() - 2); + result.add + (new FlattenInstruction(rightPath.subPath(0, rightPath.size()), optional)); + + result.add(new FlattenInstruction(leftPath, optional)); + } + } + + leftHandSideIndex++; + rightHandSideIndex++; + } + + + // then create instructions for what stays the same + OUTER: + for (TaskPath path : leftHandSideTraversal.getTraversalPaths()) { + for (FlattenInstruction instruction : result) { + if (instruction.matches(path)) { + continue OUTER; + } + } + + result.add(new FlattenInstruction(path)); + } + + OUTER: + for (TaskPath path : rightHandSideTraversal.getTraversalPaths()) { + for (FlattenInstruction instruction : result) { + if (instruction.matches(path)) { + continue OUTER; + } + } + + result.add(new FlattenInstruction(path)); + } + + return result; + } + + /** + * + */ + private void addSelectionChildIfRequired(ISelection selection, ITask child) { + for (ITask candidate : selection.getChildren()) { + if (identTaskHandlStrat.getTaskComparator().equals(candidate, child)) { + return; + } + } + + taskBuilder.addChild(selection, child); + } + + /** + * + */ + private ITask getTaskForChunk(Chunk chunk, RuleApplicationData appData) { + if (chunk.size() == 1) { + TaskPath path = (TaskPath) chunk.getLines().get(0); + return path.getTask(path.size() - 1); + } + else { + ISequence task = taskFactory.createNewSequence(); + + for (Object pathObj : chunk.getLines()) { + TaskPath path = (TaskPath) pathObj; + taskBuilder.addChild(task, path.getLast()); + } + + return appData.ensureUnique(task); + } + } + + /** + * + */ + private void createReplacementInstructions(Chunk chunk, + ITask replacement, + ITask selectedChild, + List result) + { + // create a flatten instruction for the occurrence of the replacement + for (Object pathObj : chunk.getLines()) { + TaskPath path = (TaskPath) pathObj; + + if (replacement instanceof IOptional) { + result.add(new FlattenInstruction(path, (IOptional) replacement)); + } + else if (replacement instanceof ISelection) { + result.add + (new FlattenInstruction(path, (ISelection) replacement, selectedChild)); + } + } + } + + /** + * + */ + private void flattenInstances(ITask task, + List flattenInstructions, + Map flattenedSessions, + List excludes) + { + //int i = 0; + for (ITaskInstance instance : task.getInstances()) { + /*System.out.println("flattening instance " + i++ + " of task " + task); + new TaskTreeEncoder().encode(instance, System.out, excludes);*/ + + TaskPath taskPath = new TaskPath(); + taskPath.add(instance.getTask(), 0); + IUserSession session = taskFactory.createUserSession(); + flattenInstance(instance, taskPath, flattenInstructions, session, + new LinkedList()); + + //new TaskTreeEncoder().encode(session, System.out, excludes); + + flattenedSessions.put(instance, session); + } + } + + /** + * + */ + private void flattenInstance(ITaskInstance instance, + TaskPath taskPath, + List flattenInstructions, + IUserSession session, + List previousPaths) + { + boolean instructionApplied = false; + + TaskInstanceComparator comp = identTaskHandlStrat.getTaskComparator(); + + //System.out.println("applying instructions on " + taskPath); + + for (FlattenInstruction instruction : flattenInstructions) { + if (instruction.matches(taskPath)) { + //System.out.print("found instruction "); + instruction.dump(System.out); + + switch (instruction.getInstruction()) { + case DONT_TRAVERSE: { + if (instance != null) { + taskBuilder.addTaskInstance(session, instance); + } + instructionApplied = true; + break; + } + case MAKE_OPTIONAL: { + instructionApplied = true; + + if (instance == null) { + break; + } + + IOptional optional = instruction.getOptional(); + + if (comp.equals(optional, instance.getTask())) { + // the instance is already an instance of the correct optional --> reuse + taskBuilder.addTaskInstance(session, instance); + } + else if (comp.equals(optional.getMarkedTask(), instance.getTask())) { + IOptionalInstance optionalInstance = + taskFactory.createNewTaskInstance(optional); + taskBuilder.setChild(optionalInstance, instance); + taskBuilder.addTaskInstance(session, optionalInstance); + } + else if (optional.getMarkedTask() instanceof ISequence) { + // first check, if the instance was already created, if not create it + ISequenceInstance sequenceInstance = ensureSequenceChildInstanceFor + (optional, (ISequence) optional.getMarkedTask(), session); + + taskBuilder.addChild(sequenceInstance, instance); + } + break; + } + case MAKE_SELECTION: { + instructionApplied = true; + + if (instance == null) { + break; + } + + ISelection selection = instruction.getSelection(); + + if (comp.equals(instruction.getSelectedChild(), instance.getTask())) { + ISelectionInstance selectionInstance = + taskFactory.createNewTaskInstance(selection); + taskBuilder.setChild(selectionInstance, instance); + taskBuilder.addTaskInstance(session, selectionInstance); + } + else if (instruction.getSelectedChild() == null) { + // both variants were already selections. They will have been merged. + // Hence we can reuse the child instances of the existing selection + // instances. + if (comp.equals(instance.getTask(), selection)) { + taskBuilder.addTaskInstance(session, instance); + } + else { + ISelectionInstance selectionInstance = + taskFactory.createNewTaskInstance(selection); + taskBuilder.setChild(selectionInstance, + ((ISelectionInstance) instance).getChild()); + taskBuilder.addTaskInstance(session, selectionInstance); + + taskBuilder.discardTaskInstance(instance); + } + } + else if (instruction.getSelectedChild() instanceof ISequence) { + // first check, if the instance was already created, if not create it + ISequenceInstance sequenceInstance = ensureSequenceChildInstanceFor + (selection, (ISequence) instruction.getSelectedChild(), session); + + taskBuilder.addChild(sequenceInstance, instance); + } + + break; + } + case INTEGRATE_OPTIONAL: { + TaskPath previousPath = previousPaths.size() > 0 ? + previousPaths.get(previousPaths.size() - 1) : null; + + if (pathsMatch(instruction.getPrecedingPath(), previousPath)) { + IOptional optional = instruction.getOptional(); + IOptionalInstance optionalInstance = + taskFactory.createNewTaskInstance(optional); + taskBuilder.addTaskInstance(session, optionalInstance); + } + + if (instance != null) { + taskBuilder.addTaskInstance(session, instance); + } + + instructionApplied = true; + break; + } + default : { + throw new RuntimeException("unknown instruction type"); + } + } + } + + if (instructionApplied) { + break; + } + } + + if (!instructionApplied) { + ITask task = taskPath.getLast(); + if (task instanceof IIteration) { + taskPath.add(((IIteration) task).getMarkedTask(), 0); + + if (instance != null) { + for (ITaskInstance child : (IIterationInstance) instance) { + flattenInstance + (child, taskPath, flattenInstructions, session, previousPaths); + } + } + else { + flattenInstance(null, taskPath, flattenInstructions, session, previousPaths); + } + + taskPath.removeLast(); + } + else if (task instanceof ISequence) { + List children = ((ISequence) task).getChildren(); + for (int i = 0; i < children.size(); i++) { + ITaskInstance child = null; + if (instance != null) { + child = ((ISequenceInstance) instance).get(i); + } + taskPath.add(children.get(i), i); + flattenInstance + (child, taskPath, flattenInstructions, session, previousPaths); + taskPath.removeLast(); + } + } + else if (task instanceof ISelection) { + if (instance != null) { + taskPath.add(((ISelectionInstance) instance).getChild().getTask(), 0); + flattenInstance(((ISelectionInstance) instance).getChild(), taskPath, + flattenInstructions, session, previousPaths); + taskPath.removeLast(); + } + else { + // check if the selection has any child for which a rule must be considered + List children = ((ISelection) task).getChildren(); + for (int i = 0; i < children.size(); i++) { + taskPath.add(children.get(i), i); + flattenInstance + (null, taskPath, flattenInstructions, session, previousPaths); + taskPath.removeLast(); + } + } + } + else if (task instanceof IOptional) { + taskPath.add(((IOptional) task).getMarkedTask(), 0); + ITaskInstance child = null; + if (instance != null) { + child = ((IOptionalInstance) instance).getChild(); + } + flattenInstance(child, taskPath, flattenInstructions, session, previousPaths); + taskPath.removeLast(); + + if ((instance != null) && (child == null)) { + // add the empty optional instance + taskBuilder.addTaskInstance(session, instance); + previousPaths.add(new TaskPath(taskPath)); + } + } + else if (instance != null) { + taskBuilder.addTaskInstance(session, instance); + previousPaths.add(new TaskPath(taskPath)); + } + } + else { + previousPaths.add(new TaskPath(taskPath)); + } + } + + /** + * + */ + private ISequenceInstance ensureSequenceChildInstanceFor(ITask replacement, + ISequence expectedChildSequence, + IUserSession session) + { + // first check, if there is already an instance of the expected sequence. If so, check if + // its child is a sequence instance. If not create a new task instance with an appropriate + // sequence instance + ITaskInstance prevInstance = + session.size() > 0 ? session.get(session.size() - 1) : null; + + ISequenceInstance sequenceInstance = null; + + if ((prevInstance != null) && + (identTaskHandlStrat.getTaskComparator().equals(prevInstance.getTask(), replacement))) + { + if ((prevInstance instanceof IOptionalInstance) && + (((IOptionalInstance) prevInstance).getChild() instanceof ISequenceInstance)) + { + sequenceInstance = + (ISequenceInstance) ((IOptionalInstance) prevInstance).getChild(); + } + else if ((prevInstance instanceof ISelectionInstance) && + (((ISelectionInstance) prevInstance).getChild() instanceof ISequenceInstance)) + { + sequenceInstance = + (ISequenceInstance) ((ISelectionInstance) prevInstance).getChild(); + } + } + + // although we found a sequence instance as expected, this instance might already be fully + // created and a new (iterated) one must be created. Check for it and handle correctly + if ((sequenceInstance != null) && + (sequenceInstance.size() == expectedChildSequence.getChildren().size())) + { + sequenceInstance = null; + } + + if (sequenceInstance == null) { + //System.out.println("creating new sequence instance of selected child"); + sequenceInstance = taskFactory.createNewTaskInstance(expectedChildSequence); + + ITaskInstance replacementInstance = null; + + if (replacement instanceof IOptional) { + replacementInstance = taskFactory.createNewTaskInstance((IOptional) replacement); + taskBuilder.setChild((IOptionalInstance) replacementInstance, sequenceInstance); + } + else if (replacement instanceof ISelection) { + + /*System.out.println("replacement: "); + new TaskTreeEncoder().encode(replacement, System.out); + + System.out.println("expectedChild: "); + new TaskTreeEncoder().encode(expectedChildSequence, System.out);*/ + + replacementInstance = taskFactory.createNewTaskInstance((ISelection) replacement); + taskBuilder.setChild((ISelectionInstance) replacementInstance, sequenceInstance); + } + + taskBuilder.addTaskInstance(session, replacementInstance); + } + + return sequenceInstance; + } + + /** + * + */ + private void replaceTaskInstances(ITaskInstanceList taskInstanceList, + Map replacements, + SimilarTasks similarTasks) + { + for (int i = 0; i < taskInstanceList.size(); i++) { + ITaskInstance childInstance = taskInstanceList.get(i); + ITaskInstance replacement = replacements.remove(childInstance); + + if (replacement != null) { + + // update the model + if (taskInstanceList instanceof ISequenceInstance) { + ISequence task = ((ISequenceInstance) taskInstanceList).getSequence(); + taskBuilder.setChild(task, i, replacement.getTask()); + } + else if (taskInstanceList instanceof IIterationInstance) { + taskBuilder.setMarkedTask + (((IIterationInstance) taskInstanceList).getIteration(), + replacement.getTask()); + } + + // perform the actual replacement and throw away the instance + taskBuilder.setTaskInstance(taskInstanceList, i, replacement); + TaskPath path = new TaskPath(); + path.add(childInstance.getTask(), 0); + discardTaskInstancesNotBelongingToTraversals(childInstance, path, similarTasks); + } + else if (childInstance instanceof ITaskInstanceList) { + replaceTaskInstances((ITaskInstanceList) childInstance, replacements, similarTasks); + } + else if (childInstance instanceof IOptionalInstance) { + replaceTaskInstances((IOptionalInstance) childInstance, replacements, similarTasks); + } + else if (childInstance instanceof ISelectionInstance) { + replaceTaskInstances((ISelectionInstance) childInstance, replacements, similarTasks); + } + } + } + + /** + * + */ + private void replaceTaskInstances(IOptionalInstance optionalInstance, + Map replacements, + SimilarTasks similarTasks) + { + ITaskInstance childInstance = optionalInstance.getChild(); + + if (childInstance != null) { + ITaskInstance replacement = replacements.remove(childInstance); + + if (replacement != null) { + + // update the model + taskBuilder.setMarkedTask(optionalInstance.getOptional(), replacement.getTask()); + + // perform the actual replacement and throw away the instance + taskBuilder.setChild(optionalInstance, replacement); + TaskPath path = new TaskPath(); + path.add(childInstance.getTask(), 0); + discardTaskInstancesNotBelongingToTraversals(childInstance, path, similarTasks); + } + else if (childInstance instanceof ITaskInstanceList) { + replaceTaskInstances((ITaskInstanceList) childInstance, replacements, similarTasks); + } + else if (childInstance instanceof ISelectionInstance) { + replaceTaskInstances((ISelectionInstance) childInstance, replacements, similarTasks); + } + else if (childInstance instanceof IOptionalInstance) { + throw new IllegalArgumentException + ("optional must not have an optional as its child"); + } + } + } + + /** + * + */ + private void replaceTaskInstances(ISelectionInstance selectionInstance, + Map replacements, + SimilarTasks similarTasks) + { + TaskInstanceComparator comparator = identTaskHandlStrat.getTaskComparator(); + + ITaskInstance childInstance = selectionInstance.getChild(); + + if (childInstance != null) { + ITaskInstance replacement = replacements.remove(childInstance); + + if (replacement != null) { + + if (replacement instanceof ISelectionInstance) { + taskBuilder.discardTaskInstance(replacement); + replacement = ((ISelectionInstance) replacement).getChild(); + } + + // update the model + // we replace all instances of the merged tasks with instances of a new task. + // hence, we also have to remove the task of the replaced children from the + // available variants of the selection + taskBuilder.removeChild(selectionInstance.getSelection(), childInstance.getTask()); + + boolean found = false; + for (ITask child : selectionInstance.getSelection().getChildren()) { + if (comparator.equals(child, replacement.getTask())) { + found = true; + break; + } + } + + if (!found) { + taskBuilder.addChild(selectionInstance.getSelection(), replacement.getTask()); + } + + // perform the actual replacement and throw away the instance + taskBuilder.setChild(selectionInstance, replacement); + TaskPath path = new TaskPath(); + path.add(childInstance.getTask(), 0); + discardTaskInstancesNotBelongingToTraversals(childInstance, path, similarTasks); + } + else if (childInstance instanceof ITaskInstanceList) { + replaceTaskInstances((ITaskInstanceList) childInstance, replacements, similarTasks); + } + else if (childInstance instanceof IOptionalInstance) { + replaceTaskInstances((IOptionalInstance) childInstance, replacements, similarTasks); + } + else if (childInstance instanceof ISelectionInstance) { + throw new IllegalArgumentException + ("selection must not have a selection as its child"); + } + } + } + + /** + * + */ + private void discardTaskInstancesNotBelongingToTraversals(ITaskInstance instance, + TaskPath pathToInstance, + SimilarTasks similarTasks) + { + boolean discarded = false; + for (TaskPath candidate : similarTasks.getLeftHandSideTraversal().getTraversalPaths()) { + if (candidate.size() > pathToInstance.size()) { + TaskPath potentialEqualSubPath = candidate.subPath(0, pathToInstance.size()); + if (pathsMatch(potentialEqualSubPath, pathToInstance)) { + taskBuilder.discardTaskInstance(instance); + discarded = true; + break; + } + } + } + + if (!discarded) { + for (TaskPath candidate : similarTasks.getRightHandSideTraversal().getTraversalPaths()) { + if (candidate.size() > pathToInstance.size()) { + TaskPath potentialEqualSubPath = candidate.subPath(0, pathToInstance.size()); + if (pathsMatch(potentialEqualSubPath, pathToInstance)) { + taskBuilder.discardTaskInstance(instance); + discarded = true; + break; + } + } + } + } + + if (discarded) { + // now also discard the children + if (instance instanceof ISequenceInstance) { + int index = 0; + for (ITaskInstance childInstance : (ITaskInstanceList) instance) { + pathToInstance.add(childInstance.getTask(), index++); + discardTaskInstancesNotBelongingToTraversals + (childInstance, pathToInstance, similarTasks); + pathToInstance.removeLast(); + } + } + else if (instance instanceof IIterationInstance) { + for (ITaskInstance childInstance : (ITaskInstanceList) instance) { + pathToInstance.add(childInstance.getTask(), 0); + discardTaskInstancesNotBelongingToTraversals + (childInstance, pathToInstance, similarTasks); + pathToInstance.removeLast(); + } + } + else if (instance instanceof IOptionalInstance) { + ITaskInstance childInstance = ((IOptionalInstance) instance).getChild(); + if (childInstance != null) { + pathToInstance.add(childInstance.getTask(), 0); + discardTaskInstancesNotBelongingToTraversals + (childInstance, pathToInstance, similarTasks); + pathToInstance.removeLast(); + } + } + else if (instance instanceof ISelectionInstance) { + ITaskInstance childInstance = ((ISelectionInstance) instance).getChild(); + pathToInstance.add(childInstance.getTask(), 0); + discardTaskInstancesNotBelongingToTraversals + (childInstance, pathToInstance, similarTasks); + pathToInstance.removeLast(); + } + } + } + + /** + * + */ + private void harmonizeEqualMarkingTemporalRelationships(RuleApplicationData appData) { + Console.println("harmonizing marking temporal relationships"); + + TaskInstanceComparator comparator = identTaskHandlStrat.getTaskComparator(); + ITaskModel model = taskFactory.createTaskModel(appData.getSessions()); + + // determine a list of equal marking temporal relationship lists + List> equalTasks = + new LinkedList>(); + + for (ITask task1 : model.getTasks()) { + if (task1 instanceof IMarkingTemporalRelationship) { + IMarkingTemporalRelationship parent1 = (IMarkingTemporalRelationship) task1; + for (ITask task2 : model.getTasks()) { + if (task2 instanceof IMarkingTemporalRelationship) { + IMarkingTemporalRelationship parent2 = (IMarkingTemporalRelationship) task2; + + // check if the parents are of the same type, but distinct and if the + // children are identical + if (!comparator.equals(parent1, parent2) && + (parent1.getClass().isAssignableFrom(parent2.getClass()) || + parent2.getClass().isAssignableFrom(parent1.getClass())) && + comparator.equals(parent1.getMarkedTask(), parent2.getMarkedTask())) + { + List equalTaskList = null; + + GET_EQUAL_TASK_LIST: + for (List candidate : equalTasks) { + for (IMarkingTemporalRelationship task : candidate) { + if (comparator.equals(task, parent1) || + comparator.equals(task, parent2)) + { + equalTaskList = candidate; + break GET_EQUAL_TASK_LIST; + } + } + } + + if (equalTaskList == null) { + equalTaskList = new LinkedList(); + equalTasks.add(equalTaskList); + } + + boolean found1 = false; + boolean found2 = false; + + for (IMarkingTemporalRelationship task : equalTaskList) { + if (comparator.equals(task, parent1)) { + found1 = true; + } + else if (comparator.equals(task, parent2)) { + found2 = true; + } + } + + if (!found1) { + equalTaskList.add(parent1); + } + + if (!found2) { + equalTaskList.add(parent2); + } + } + } + } + } + } + + Console.traceln(Level.FINER, "found " + equalTasks.size() + + " groups of equal marking temporal relationships"); + + // set the same task for all instances + List instanceBuffer = new ArrayList(); + for (List equalTaskList : equalTasks) { + for (int i = 1; i < equalTaskList.size(); i++) { + // to prevent a concurrent modification, first copy the list of instances + instanceBuffer.clear(); + instanceBuffer.addAll(equalTaskList.get(i).getInstances()); + for (ITaskInstance instance : instanceBuffer) { + taskBuilder.setTask(instance, equalTaskList.get(0)); + } + } + } + + // several subsequent instances, which had formerly different tasks, may now have the same. + // Hence, they need to be merged. But as everything else would be way too complex, we only + // perform the merge, if they occur next to each other on the same level + for (IUserSession session : appData.getSessions()) { + mergeSubsequentIdenticalMarkingTemporalRelationships(session); + } + + } + + /** + * + */ + private void mergeSubsequentIdenticalMarkingTemporalRelationships(ITaskInstanceList list) { + int index = 0; + TaskInstanceComparator comparator = identTaskHandlStrat.getTaskComparator(); + + while (index < (list.size() - 1)) { + ITaskInstance instance1 = list.get(index); + ITaskInstance instance2 = list.get(index + 1); + + if (comparator.equals(instance1.getTask(), instance2.getTask())) { + if (instance1 instanceof IIterationInstance) { + // add the children of the second to the first iteration instance and discard + // the second + for (ITaskInstance child : (IIterationInstance) instance2) { + taskBuilder.addChild((IIterationInstance) instance1, child); + } + + taskBuilder.removeTaskInstance(list, index + 1); + taskBuilder.discardTaskInstance(instance2); + } + else if (instance1 instanceof IOptionalInstance) { + ITaskInstance optionalChildInstance1 = + ((IOptionalInstance) instance1).getChild(); + ITaskInstance optionalChildInstance2 = + ((IOptionalInstance) instance2).getChild(); + + if (optionalChildInstance1 == null) { + // independent of the second, just remove the first. The second will be the + // unique representation + taskBuilder.removeTaskInstance(list, index); + } + else if (optionalChildInstance2 == null) { + // remove the second. The first will be the unique representation + taskBuilder.removeTaskInstance(list, index + 1); + } + else if (optionalChildInstance1 instanceof IIterationInstance) { + // add all children of the second optional iteration instance to the + // first and discard the second + for (ITaskInstance child : (IIterationInstance) optionalChildInstance2) { + taskBuilder.addChild + ((IIterationInstance) optionalChildInstance1, child); + } + + taskBuilder.removeTaskInstance(list, index + 1); + taskBuilder.discardTaskInstance(instance2); + } + else { + // both optional children are no iterations --> create an iteration + // for them and add them both as children. + throw new java.lang.UnsupportedOperationException("not implemented yet"); + } + } + else { + index++; + } + } + else { + index++; + } + } + + for (ITaskInstance child : list) { + if (child instanceof ITaskInstanceList) { + mergeSubsequentIdenticalMarkingTemporalRelationships((ITaskInstanceList) child); + } + } + } + + /** + * + */ + private static boolean pathsMatch(TaskPath path1, TaskPath path2) { + if (path1 == null) { + return path2 == null; + } + else if ((path2 != null) && (path1.size() == path2.size())) { + for (int i = 0; i < path1.size(); i++) { + if (!path1.get(i).equals(path2.get(i))) { + return false; + } + } + return true; + } + else { + return false; + } + } + + /** + * + */ + /*private boolean containsNewTask(ITask task, RuleApplicationData appData) { + if (appData.isSelfCreatedTask(task)) { + return true; + } + else if (task instanceof IStructuringTemporalRelationship) { + for (ITask child : ((IStructuringTemporalRelationship) task).getChildren()) { + if (containsNewTask(child, appData)) { + return true; + } + } + } + else if (task instanceof IMarkingTemporalRelationship) { + return containsNewTask(((IMarkingTemporalRelationship) task).getMarkedTask(), appData); + } + + return false; + }*/ + + /** + * + */ + private class RuleApplicationData { + + /** + * + */ + private List sessions; + + /** + * + */ + private ITaskModel taskModel; + + /** + * + */ + private MostSimilarTaskDeterminer mostSimilarTasksDeterminer = + new MostSimilarTaskDeterminer(identTaskHandlStrat.getTaskComparator()); + + /** + * + */ + private List mostSimilarTasks; + + /** + * + */ + private List newTasks = new LinkedList(); + + /** + * + */ + private RuleApplicationResult ruleApplicationResult = new RuleApplicationResult(); + + /** + * + */ + RuleApplicationData(List sessions) { + this.sessions = sessions; + } + + /** + * + */ + boolean isSelfCreatedTask(ITask task) { + for (ITask candidate : newTasks) { + if (candidate == task) { + return true; + } + } + + return false; + } + + /** + * @return the mostSimilarTasksDeterminer + */ + MostSimilarTaskDeterminer getMostSimilarTasksDeterminer() { + return mostSimilarTasksDeterminer; + } + + /** + * + */ + void markAsAlreadyCondensed(ITask task1, ITask task2) { + mostSimilarTasksDeterminer.addComparisonToSkip(task1, task2); + } + + /** + * + */ + private RuleApplicationResult finalizeRuleApplicationResult() { + for (ITask newTask : newTasks) { + ruleApplicationResult.addNewlyCreatedTask(newTask); + + if (newTask instanceof IOptional) { + if (isSelfCreatedTask(((IOptional) newTask).getMarkedTask()) && + (((IOptional) newTask).getMarkedTask() instanceof ISequence)) + { + ruleApplicationResult.addNewlyCreatedTask + (((IOptional) newTask).getMarkedTask()); + } + } + else if (newTask instanceof ISelection) { + for (ITask child : ((ISelection) newTask).getChildren()) { + if (isSelfCreatedTask(child) && (child instanceof ISequence)) { + ruleApplicationResult.addNewlyCreatedTask(child); + } + } + } + } + + + return ruleApplicationResult; + } + + /** + * @return the tree + */ + private List getSessions() { + return sessions; + } + + /** + * @return the taskModel + */ + private ITaskModel getTaskModel() { + return taskModel; + } + + /** + * @param taskModel the taskModel to set + */ + private void setTaskModel(ITaskModel taskModel) { + this.taskModel = taskModel; + } + + /** + * @return the orderedDiffLevels + */ + private List getMostSimilarTasks() { + return mostSimilarTasks; + } + + /** + * @param orderedDiffLevels the orderedDiffLevels to set + */ + private void setMostSimilarTasks(List mostSimilarTasks) { + this.mostSimilarTasks = mostSimilarTasks; + } + + /** + * + */ + private ITask ensureUnique(ITask task) { + // replacements done in this rule are either optionals or selections. So focus on them + if (task instanceof IOptional) { + for (ITask newTask : newTasks) { + if (newTask instanceof IOptional) { + ITask child1 = ((IOptional) task).getMarkedTask(); + ITask child2 = ((IOptional) newTask).getMarkedTask(); + if (createdChildEquals(child1, child2)) { + System.out.println("reusing optional " + newTask + " for " + task); + return newTask; + } + } + } + } + else if (task instanceof ISelection) { + for (ITask newTask : newTasks) { + if (newTask instanceof ISelection) { + List children1 = ((ISelection) task).getChildren(); + List children2 = ((ISelection) newTask).getChildren(); + if (createdSelectionChildrenEqual(children1, children2)) { + System.out.println("reusing selection " + newTask + " for " + task); + + /*System.out.println("---------------------------- existing task"); + new TaskTreeEncoder().encode(newTask, System.out); + + System.out.println("---------------------------- completely new task"); + new TaskTreeEncoder().encode(task, System.out);*/ + + return newTask; + } + } + } + } + else if (task instanceof ISequence) { + List allRelevant = new ArrayList<>(); + + for (ITask candidate : newTasks) { + if (candidate instanceof ISequence) { + allRelevant.add((ISequence) candidate); + } + } + + for (ITask candidate : taskModel.getTasks()) { + if (candidate instanceof ISequence) { + allRelevant.add((ISequence) candidate); + } + } + + for (ISequence candidate : allRelevant) { + List children1 = ((ISequence) task).getChildren(); + List children2 = ((ISequence) candidate).getChildren(); + + boolean equal = false; + if (children1.size() == children2.size()) { + equal = true; + for (int i = 0; i < children1.size(); i++) { + if (children1.get(i) != children2.get(i)) { + equal = false; + break; + } + } + } + + if (equal) { + System.out.println("reusing sequence " + candidate + " for " + task); + return candidate; + } + } + } + + newTasks.add(task); + + return task; + } + + /** + * + */ + private boolean createdSelectionChildrenEqual(List children1, List children2) { + if (children1.size() != children2.size()) { + return false; + } + + for (ITask child1 : children1) { + boolean found = false; + + for (ITask child2 : children2) { + if (createdChildEquals(child1, child2)) { + found = true; + break; + } + } + + if (!found) { + return false; + } + } + + return true; + } + + /** + * + */ + private boolean createdChildEquals(ITask child1, ITask child2) { + if (child1 == child2) { + return true; + } + else if (!isSelfCreatedTask(child1) && !isSelfCreatedTask(child2)) { + // the simple comparison can not work if the tasks are not self created + return false; + } + else if ((child1 instanceof ISequence) && (child2 instanceof ISequence)) { + ISequence sequence1 = (ISequence) child1; + ISequence sequence2 = (ISequence) child2; + + if (sequence1.getChildren().size() != sequence2.getChildren().size()) { + return false; + } + + for (int i = 0; i < sequence1.getChildren().size(); i++) { + if (sequence1.getChildren().get(i) != sequence2.getChildren().get(i)) { + return false; + } + } + + return true; + } + else { + return false; + } + } + } + + /** + * + */ + private static class FlattenInstruction { + + /** + * + */ + private enum Instruction { DONT_TRAVERSE, MAKE_OPTIONAL, MAKE_SELECTION, INTEGRATE_OPTIONAL }; + + /** */ + private TaskPath path; + + /** */ + private TaskPath precedingPath; + + /** */ + private Instruction instruction; + + /** */ + private IOptional optional = null; + + /** */ + private ISelection selection = null; + + /** */ + private ITask selectedChild = null; + + /** + * + */ + private FlattenInstruction(TaskPath path) { + this.path = path; + this.instruction = Instruction.DONT_TRAVERSE; + } + + /** + * + */ + private FlattenInstruction(TaskPath path, IOptional optional) { + this.path = path; + this.instruction = Instruction.MAKE_OPTIONAL; + this.optional = optional; + } + + /** + * + */ + private FlattenInstruction(TaskPath path, ISelection selection, ITask selectedChild) { + this.path = path; + this.instruction = Instruction.MAKE_SELECTION; + this.selection = selection; + this.selectedChild = selectedChild; + } + + /** + * + */ + private FlattenInstruction(TaskPath precedingPath, + TaskPath path, + IOptional optional) + { + this.path = path; + this.precedingPath = precedingPath; + this.instruction = Instruction.INTEGRATE_OPTIONAL; + this.optional = optional; + } + + /** + * + */ + IOptional getOptional() { + return optional; + } + + + /** + * @return the selection + */ + ISelection getSelection() { + return selection; + } + + /** + * @return the selectedChild + */ + ITask getSelectedChild() { + return selectedChild; + } + + /** + * @return the instruction + */ + Instruction getInstruction() { + return instruction; + } + + /** + * @return the precedingPath + */ + TaskPath getPrecedingPath() { + return precedingPath; + } + + /** + * + */ + boolean matches(TaskPath path) { + return pathsMatch(this.path, path); + } + + + /** + * + */ + void dump(PrintStream out) { + for (int i = 0; i < path.size(); i++) { + out.print("-->"); + out.print(path.getTask(i).getId()); + out.print('('); + out.print(path.get(i).getIndex()); + out.print(')'); + } + + out.print(" "); + out.print(instruction); + + out.println(); + } + + } + +} 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 1766) +++ /trunk/autoquest-core-tasktrees/src/main/java/de/ugoe/cs/autoquest/tasktrees/temporalrelation/SequenceForTaskDetectionRule.java (revision 1767) @@ -27,4 +27,6 @@ import de.ugoe.cs.autoquest.tasktrees.treeifc.IIteration; import de.ugoe.cs.autoquest.tasktrees.treeifc.IIterationInstance; +import de.ugoe.cs.autoquest.tasktrees.treeifc.IOptional; +import de.ugoe.cs.autoquest.tasktrees.treeifc.IOptionalInstance; import de.ugoe.cs.autoquest.tasktrees.treeifc.ISelection; import de.ugoe.cs.autoquest.tasktrees.treeifc.ISelectionInstance; @@ -280,4 +282,5 @@ { Map iterations = new HashMap(); + Map optionals = new HashMap(); Map> iterationInstances = new HashMap>(); @@ -286,12 +289,22 @@ IIteration iteration = taskFactory.createNewIteration(); iterations.put(iteratedTask, iteration); + + if (iteratedTask instanceof IOptional) { + IOptional optional = taskFactory.createNewOptional(); + taskBuilder.setMarkedTask(optional, iteration); + optionals.put(iteration, optional); + } + iterationInstances.put(iteration, new LinkedList()); } + IOptionalInstance optionalInstance; IIterationInstance iterationInstance; for (IUserSession session : sessions) { int index = 0; + optionalInstance = null; iterationInstance = null; + boolean inReplacement = false; while (index < session.size()) { @@ -302,13 +315,35 @@ 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); + if (!inReplacement || (iterationInstance.getTask() != iteration)) { + if (currentTask instanceof IOptional) { + IOptional optional = optionals.get(iteration); + optionalInstance = taskFactory.createNewTaskInstance(optional); + taskBuilder.addTaskInstance(session, index, optionalInstance); + } + else { + iterationInstance = taskFactory.createNewTaskInstance(iteration); + iterationInstances.get(iteration).add(iterationInstance); + taskBuilder.addTaskInstance(session, index, iterationInstance); + } + inReplacement = true; index++; } - taskBuilder.addChild(iterationInstance, session.get(index)); + if (currentTask instanceof IOptional) { + ITaskInstance child = ((IOptionalInstance) session.get(index)).getChild(); + + if (child != null) { + if (iterationInstance == null) { + iterationInstance = taskFactory.createNewTaskInstance(iteration); + iterationInstances.get(iteration).add(iterationInstance); + taskBuilder.setChild(optionalInstance, iterationInstance); + } + taskBuilder.addChild(iterationInstance, child); + } + } + else { + taskBuilder.addChild(iterationInstance, session.get(index)); + } + taskBuilder.removeTaskInstance(session, index); } @@ -316,4 +351,6 @@ if (iterationInstance != null) { iterationInstance = null; + optionalInstance = null; + inReplacement = false; } index++; @@ -544,5 +581,5 @@ replaceTaskOccurrences(task, appData.getSessions(), sequence); - harmonizeSequenceInstancesModel(sequence, sequenceInstances,task.size()); + harmonizeSequenceInstancesModel(sequence, sequenceInstances, task.size()); appData.detectedAndReplacedTasks (appData.detectedAndReplacedTasks() || (sequenceInstances.size() > 0)); Index: /trunk/autoquest-core-tasktrees/src/main/java/de/ugoe/cs/autoquest/tasktrees/temporalrelation/TaskIdentityComparator.java =================================================================== --- /trunk/autoquest-core-tasktrees/src/main/java/de/ugoe/cs/autoquest/tasktrees/temporalrelation/TaskIdentityComparator.java (revision 1766) +++ /trunk/autoquest-core-tasktrees/src/main/java/de/ugoe/cs/autoquest/tasktrees/temporalrelation/TaskIdentityComparator.java (revision 1767) @@ -16,4 +16,5 @@ import de.ugoe.cs.autoquest.tasktrees.taskequality.TaskEquality; +import de.ugoe.cs.autoquest.tasktrees.treeifc.ITask; import de.ugoe.cs.autoquest.tasktrees.treeifc.ITaskInstance; @@ -43,5 +44,13 @@ @Override public boolean equals(ITaskInstance taskInstance1, ITaskInstance taskInstance2) { - return taskInstance1.getTask() == taskInstance2.getTask(); + return equals(taskInstance1.getTask(), taskInstance2.getTask()); + } + + /* (non-Javadoc) + * @see TaskInstanceComparator#equals(ITask, ITask) + */ + @Override + public boolean equals(ITask task1, ITask task2) { + return task1 == task2; } Index: /trunk/autoquest-core-tasktrees/src/main/java/de/ugoe/cs/autoquest/tasktrees/temporalrelation/TemporalRelationshipRuleManager.java =================================================================== --- /trunk/autoquest-core-tasktrees/src/main/java/de/ugoe/cs/autoquest/tasktrees/temporalrelation/TemporalRelationshipRuleManager.java (revision 1766) +++ /trunk/autoquest-core-tasktrees/src/main/java/de/ugoe/cs/autoquest/tasktrees/temporalrelation/TemporalRelationshipRuleManager.java (revision 1767) @@ -148,4 +148,6 @@ new SequenceForTaskDetectionRule (TaskEquality.SEMANTICALLY_EQUAL, taskFactory, taskBuilder), + new CondenseSimilarTasksRule + (TaskEquality.SEMANTICALLY_EQUAL, taskFactory, taskBuilder), /*new DefaultTaskSequenceDetectionRule (NodeEquality.SYNTACTICALLY_EQUAL, taskFactory, taskTreeBuilder), Index: /trunk/autoquest-core-tasktrees/src/main/java/de/ugoe/cs/autoquest/tasktrees/temporalrelation/utils/MostSimilarTaskDeterminer.java =================================================================== --- /trunk/autoquest-core-tasktrees/src/main/java/de/ugoe/cs/autoquest/tasktrees/temporalrelation/utils/MostSimilarTaskDeterminer.java (revision 1767) +++ /trunk/autoquest-core-tasktrees/src/main/java/de/ugoe/cs/autoquest/tasktrees/temporalrelation/utils/MostSimilarTaskDeterminer.java (revision 1767) @@ -0,0 +1,560 @@ +// Copyright 2012 Georg-August-Universität Göttingen, Germany +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. + +package de.ugoe.cs.autoquest.tasktrees.temporalrelation.utils; + +import java.util.ArrayList; +import java.util.HashMap; +import java.util.HashSet; +import java.util.Iterator; +import java.util.LinkedList; +import java.util.List; +import java.util.Map; +import java.util.Set; +import java.util.logging.Level; + +import de.ugoe.cs.autoquest.tasktrees.temporalrelation.TaskInstanceComparator; +import de.ugoe.cs.autoquest.tasktrees.treeifc.DefaultTaskTraversingVisitor; +import de.ugoe.cs.autoquest.tasktrees.treeifc.IStructuringTemporalRelationship; +import de.ugoe.cs.autoquest.tasktrees.treeifc.ITask; +import de.ugoe.cs.autoquest.tasktrees.treeifc.ITaskInfo; +import de.ugoe.cs.autoquest.tasktrees.treeifc.ITaskModel; +import de.ugoe.cs.autoquest.tasktrees.treeifc.TaskMetric; +import de.ugoe.cs.autoquest.tasktrees.treeifc.TaskTreeUtils; +import de.ugoe.cs.util.console.Console; + +/** + *

+ * This class is a utility class for detecting similar tasks. It compares all tasks in a given + * list with each other and then chooses the pair with the highest level of similarity. For + * comparison, the tasks are traversed and only the traversals are compared with each other. + *

+ *

+ * Several task pairs may have the same similarity level. In this case, the class performs a + * filtering of the pairs to result in a merging order for the tasks that is always the same. + *

+ *

+ * If provided with many tasks, this class starts several threads to let the comparisons run in + * parallel. + *

+ * + * @author Patrick Harms + */ +public class MostSimilarTaskDeterminer { + + /** + * If this similarity level is exceeded, two tasks are not considered similar anymore. 33 means + * that at most 33% of the elements of both task traversals are not the same. + */ + private static int MAX_DIFF_LEVEL = 33; + + /** + * default indicator for unequal tasks + */ + private static final SimilarTasks UNEQUAL_TASKS = new SimilarTasks(null, null, null, null, null); + + /** + * task comparator used internally + */ + private TaskInstanceComparator comparator; + + /** + * for performance reasons, some task comparisons can be excluded beforehand and the exclusions + * are stored in this list + */ + private Set comparisonsToSkip = new HashSet<>(); + + /** + * Initialize instances of this class with the task comparator to be used + */ + public MostSimilarTaskDeterminer(TaskInstanceComparator comparator) { + this.comparator = comparator; + } + + /** + * add a pair of comparisons that is not done to increase performance + */ + public void addComparisonToSkip(ITask task1, ITask task2) { + comparisonsToSkip.add(getMapId(task1, task2)); + } + + /** + * returns a list of most similar tasks. Independent of the order of the provided tasks, the + * returned list will always be the same for the same input elements. + */ + public List getMostSimilarTasks(List tasks, ITaskModel taskModel) { + Console.println("comparing " + tasks.size() + " tasks with each other"); + + LinkedList mostSimilarTasksList = performComparisons(tasks); + + applyFilterForSmallestDiffLevel(mostSimilarTasksList); + applyFilterForParents(mostSimilarTasksList); + applyFilterForMostCoveredEvents(mostSimilarTasksList, taskModel); + + Console.traceln + (Level.FINER, "calculated " + mostSimilarTasksList.size() + " most similar tasks"); + + return mostSimilarTasksList; + } + + /** + * filters the given list of similar tasks for those having the smalled diff level, which is + * in turn the highest similarity + */ + private void applyFilterForSmallestDiffLevel(LinkedList mostSimilarTasksList) { + // determine the smallest diff level + int smallestDiffLevel = Integer.MAX_VALUE; + + for (SimilarTasks candidate : mostSimilarTasksList) { + if (candidate.getDiffLevel() < smallestDiffLevel) { + smallestDiffLevel = candidate.getDiffLevel(); + } + } + + if (smallestDiffLevel <= MAX_DIFF_LEVEL) { + // remove all entries with a higher diff level + Iterator listIterator = mostSimilarTasksList.iterator(); + + while (listIterator.hasNext()) { + if (listIterator.next().getDiffLevel() > smallestDiffLevel) { + listIterator.remove(); + } + } + } + else { + mostSimilarTasksList.clear(); + } + } + + /** + * ensures that the given list of similar tasks does not contain two pairs, where one refers + * to a child task of another pair. + */ + private void applyFilterForParents(LinkedList mostSimilarTasksList) { + + // remove all entries being parents of another entry or where both tasks are + // generated through this rule + Iterator listIterator = mostSimilarTasksList.iterator(); + + while (listIterator.hasNext()) { + SimilarTasks candidate = listIterator.next(); + + ITask task1 = candidate.getLeftHandSide(); + ITask task2 = candidate.getRightHandSide(); + for (SimilarTasks potentialChild : mostSimilarTasksList) { + ITask task3 = potentialChild.getLeftHandSide(); + ITask task4 = potentialChild.getRightHandSide(); + if (TaskTreeUtils.isChild(task3, task1) || + TaskTreeUtils.isChild(task3, task2) || + TaskTreeUtils.isChild(task4, task1) || + TaskTreeUtils.isChild(task4, task2)) + { + listIterator.remove(); + break; + } + } + } + } + + /** + * performs a filtering of the detected similar tasks which ensures, that the list does not + * contain two pairs referring to the same task and that in such cases always the same pair + * will remain. + */ + private void applyFilterForMostCoveredEvents(LinkedList mostSimilarTasksList, + ITaskModel taskModel) + { + // check, if several remaining similar tasks refer to the same task + Map> referredTasks = + new HashMap>(); + + for (SimilarTasks similarTasks : mostSimilarTasksList) { + ensureMapping(similarTasks.getLeftHandSide(), similarTasks, referredTasks); + ensureMapping(similarTasks.getRightHandSide(), similarTasks, referredTasks); + } + + // remove all entries of tasks occurring only once + List tasksOccuringOnce = new LinkedList(); + + for (Map.Entry> entry : referredTasks.entrySet()) { + if (entry.getValue().size() <= 1) { + tasksOccuringOnce.add(entry.getKey()); + } + } + + for (ITask taskToRemove : tasksOccuringOnce) { + referredTasks.remove(taskToRemove); + } + + // if there are remaining tasks occurring several times, try to extract one similar tasks + // object, that should be merged first + + if (referredTasks.size() > 0) { + mostSimilarTasksList.clear(); + + System.out.println("several comparisons for the same task exist with same diff level " + + "--> filtering for pair to be merged first"); + + SimilarTasks firstToMerge = null; + + for (LinkedList pairs : referredTasks.values()) { + for (SimilarTasks current : pairs) { + if (firstToMerge == null) { + firstToMerge = current; + } + else if (firstToMerge != current) { + firstToMerge = getFirstToMerge(firstToMerge, current, taskModel); + } + } + } + + if (firstToMerge != null) { + mostSimilarTasksList.add(firstToMerge); + } + } + + } + + /** + *

+ * compares two similar tasks and decides which of them is to be merged first. + *

+ */ + private SimilarTasks getFirstToMerge(SimilarTasks first, + SimilarTasks second, + ITaskModel taskModel) + { + + int valFirst = getTaskMetric(first, TaskMetric.EVENT_COVERAGE, taskModel); + int valSecond = getTaskMetric(second, TaskMetric.EVENT_COVERAGE, taskModel); + + if (valSecond > valFirst) { + return second; + } + else if (valSecond < valFirst) { + return first; + } + + // no of covered events is equal, try to distinguish by count + + valFirst = getTaskMetric(first, TaskMetric.COUNT, taskModel); + valSecond = getTaskMetric(second, TaskMetric.COUNT, taskModel); + + if (valSecond > valFirst) { + return second; + } + else if (valSecond < valFirst) { + return first; + } + + // count is equal, try to distinguish by depth + + valFirst = getTaskMetric(first, TaskMetric.DEPTH, taskModel); + valSecond = getTaskMetric(second, TaskMetric.DEPTH, taskModel); + + if (valSecond < valFirst) { + return second; + } + else if (valSecond > valFirst) { + return first; + } + + // no of covered events is equal, try to distinguish by count + + valFirst = cumulateTaskMetric(first, TaskMetric.COUNT, taskModel); + valSecond = cumulateTaskMetric(second, TaskMetric.COUNT, taskModel); + + if (valSecond > valFirst) { + return second; + } + else if (valSecond < valFirst) { + return first; + } + + // depth is equal. Calculate for both the similarity + // based on which the merging will take place + valFirst = + SimilarTasks.getMergableLevelOfSimilarity(first, comparator).getDiffLevel(); + valSecond = + SimilarTasks.getMergableLevelOfSimilarity(second, comparator).getDiffLevel(); + + if (valSecond > valFirst) { + return second; + } + else if (valSecond < valFirst) { + return first; + } + + first.dump(System.out); + second.dump(System.out); + + throw new RuntimeException + ("several tasks are similar so that it is undecidable which to merge first"); + } + + /** + * + */ + private void ensureMapping(ITask task, + SimilarTasks similarTasks, + Map> map) + { + LinkedList value = map.get(task); + + if (value == null) { + value = new LinkedList(); + map.put(task, value); + } + + value.add(similarTasks); + } + + + /** + * starts several threads performing the task comparisons + */ + private LinkedList performComparisons(List tasks) { + LinkedList mostSimilarTasks = new LinkedList(); + List startedRunnables = new LinkedList(); + List runnables = createRunnables(tasks, mostSimilarTasks, startedRunnables); + + // create Runnables for all buckets + int noOfParallelThreads = Math.min(2, runnables.size()); + + Console.traceln(Level.FINER, "will start " + runnables.size() + " threads"); + + // start the Threads, wait for their completion, and start the next ones if there are + // remaining + synchronized (startedRunnables) { + while ((runnables.size() > 0) || (startedRunnables.size() > 0)) { + while ((startedRunnables.size() < noOfParallelThreads) && (runnables.size() > 0)) { + Runnable runnable = runnables.remove(0); + startedRunnables.add(runnable); + new Thread(runnable).start(); + Console.traceln(Level.FINEST, "started next thread"); + } + + try { + startedRunnables.wait(); + } + catch (InterruptedException e) { + // should not happen + Console.logException(e); + } + + Console.traceln(Level.FINEST, "thread finished (" + runnables.size() + ", " + + startedRunnables.size() + ")"); + } + } + Console.traceln(Level.FINER, "all threads finished"); + + return mostSimilarTasks; + } + + /** + * creates runnables for comparing tasks by subdiving the input set of comparisons into + * several subsets where each is compared in a corresponding runnable. The subsets are + * at most 150000 comparisons large. + */ + private List createRunnables(List tasks, + LinkedList mostSimilarTasksList, + List startedRunnables) + { + // subdivide comparisons into buckets to be spread to different threads + int noOfComparisons = 0; + int noOfScheduledComparisons = 0; + List bucketIndexes = new ArrayList(); + + bucketIndexes.add(0); + + for (int i = 0; i < tasks.size(); i++) { + noOfComparisons += i; + + if ((noOfComparisons - noOfScheduledComparisons) > 150000) { + bucketIndexes.add(i); + noOfScheduledComparisons = noOfComparisons; + } + } + + bucketIndexes.add(tasks.size()); + + Console.traceln(Level.FINER, "scheduling " + noOfComparisons + " comparisons"); + + List runnables = new LinkedList(); + + for (int i = 1; i < bucketIndexes.size(); i++) { + CompareRunnable runnable = new CompareRunnable + (tasks, bucketIndexes.get(i - 1), bucketIndexes.get(i), mostSimilarTasksList, + startedRunnables); + + runnables.add(runnable); + } + + return runnables; + } + + /** + * convenience method to get the value of a task metric + */ + private int getTaskMetric(SimilarTasks similarTasks, TaskMetric metric, ITaskModel taskModel) { + if (similarTasks == null) { + return 0; + } + + ITaskInfo info1 = taskModel.getTaskInfo(similarTasks.getLeftHandSide()); + ITaskInfo info2 = taskModel.getTaskInfo(similarTasks.getRightHandSide()); + + return info1.getMeasureValue(metric) + info2.getMeasureValue(metric); + } + + /** + * convenience method to get the cumulative value of a task metric + */ + private int cumulateTaskMetric(SimilarTasks similarTasks, + final TaskMetric metric, + final ITaskModel taskModel) + { + final int[] value = new int[1]; + value[0] = 0; + + DefaultTaskTraversingVisitor visitor = new DefaultTaskTraversingVisitor() { + @Override + public void visit(IStructuringTemporalRelationship relationship) { + value[0] += taskModel.getTaskInfo(relationship).getMeasureValue(metric); + super.visit(relationship); + } + }; + + similarTasks.getLeftHandSide().accept(visitor); + similarTasks.getRightHandSide().accept(visitor); + + return value[0]; + } + + /** + * convenience method to check if a specific comparison shall be skipped + */ + private boolean isComparisonToSkip(ITask task1, ITask task2) { + return comparisonsToSkip.contains(getMapId(task1, task2)); + } + + /** + * convenience method to get a unique id for representing a pair of two tasks + */ + private long getMapId(ITask task1, ITask task2) { + if (task1.getId() < task2.getId()) { + return (((long) task1.getId()) << 32) + task2.getId(); + } + else { + return (((long) task2.getId()) << 32) + task1.getId(); + } + } + + /** + * Runnable performing a subset of task comparisons in a dedicated thread + */ + public class CompareRunnable implements Runnable { + + /** */ + private List taskList; + + /** */ + private int startIndex; + + /** */ + private int endIndex; + + /** */ + private List mostSimilarTasksList; + + /** */ + private List unfinishedRunnables; + + /** + * + */ + public CompareRunnable(List taskList, + int startIndex, + int endIndex, + List mostSimilarTasksList, + List unfinishedRunnables) + { + this.taskList = taskList; + this.startIndex = startIndex; + this.endIndex = endIndex; + this.mostSimilarTasksList = mostSimilarTasksList; + this.unfinishedRunnables = unfinishedRunnables; + } + + /* (non-Javadoc) + * @see java.lang.Runnable#run() + */ + @Override + public void run() { + int noOfComparisons = 0; + + for (int i = startIndex; i < endIndex; i++) { + noOfComparisons += i; + } + + System.out.println("performing " + noOfComparisons + " comparisons"); + + SimilarTasks mostSimilarTasks = UNEQUAL_TASKS; + List allMostSimilarTasks = new LinkedList(); + + for (int i = startIndex + 1; i < endIndex; i++) { + /*if (appData.isSelfCreatedTask(taskList.get(i))) { + continue; + }*/ + + for (int j = startIndex; j < i; j++) { + /*if (appData.isSelfCreatedTask(taskList.get(j))) { + continue; + }*/ + + if (isComparisonToSkip(taskList.get(i), taskList.get(j))) { + continue; + } + + SimilarTasks similarTasks = SimilarTasks.compareTasks + (taskList.get(i), taskList.get(j), comparator); + + if (similarTasks.isInBetweenDifference()) { + if (similarTasks.getDiffLevel() < mostSimilarTasks.getDiffLevel()) { + mostSimilarTasks = similarTasks; + allMostSimilarTasks.clear(); + allMostSimilarTasks.add(similarTasks); + } + else if (similarTasks.getDiffLevel() == mostSimilarTasks.getDiffLevel()) { + allMostSimilarTasks.add(similarTasks); + } + } + } + } + + synchronized (unfinishedRunnables) { + mostSimilarTasksList.addAll(allMostSimilarTasks); + + //System.out.println("notifying finish"); + for (int i = 0; i < unfinishedRunnables.size(); i++) { + if (unfinishedRunnables.get(i) == this) { + unfinishedRunnables.remove(i); + unfinishedRunnables.notify(); + } + } + } + } + + } +} Index: /trunk/autoquest-core-tasktrees/src/main/java/de/ugoe/cs/autoquest/tasktrees/temporalrelation/utils/SimilarTasks.java =================================================================== --- /trunk/autoquest-core-tasktrees/src/main/java/de/ugoe/cs/autoquest/tasktrees/temporalrelation/utils/SimilarTasks.java (revision 1767) +++ /trunk/autoquest-core-tasktrees/src/main/java/de/ugoe/cs/autoquest/tasktrees/temporalrelation/utils/SimilarTasks.java (revision 1767) @@ -0,0 +1,1070 @@ +// Copyright 2012 Georg-August-Universität Göttingen, Germany +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. + +package de.ugoe.cs.autoquest.tasktrees.temporalrelation.utils; + +import java.io.PrintStream; +import java.util.HashSet; +import java.util.LinkedList; +import java.util.List; +import java.util.Set; + +import de.ugoe.cs.autoquest.eventcore.gui.Scroll; +import de.ugoe.cs.autoquest.tasktrees.temporalrelation.TaskInstanceComparator; +import de.ugoe.cs.autoquest.tasktrees.treeifc.DefaultTaskTraversingVisitor; +import de.ugoe.cs.autoquest.tasktrees.treeifc.IEventTask; +import de.ugoe.cs.autoquest.tasktrees.treeifc.IEventTaskInstance; +import de.ugoe.cs.autoquest.tasktrees.treeifc.IIteration; +import de.ugoe.cs.autoquest.tasktrees.treeifc.IMarkingTemporalRelationship; +import de.ugoe.cs.autoquest.tasktrees.treeifc.ISelection; +import de.ugoe.cs.autoquest.tasktrees.treeifc.IStructuringTemporalRelationship; +import de.ugoe.cs.autoquest.tasktrees.treeifc.ITask; +import de.ugoe.cs.autoquest.tasktrees.treeifc.ITaskInstance; +import de.ugoe.cs.autoquest.tasktrees.treeifc.ITemporalRelationship; +import de.ugoe.cs.autoquest.tasktrees.treeifc.TaskPath; +import difflib.Chunk; +import difflib.Delta; +import difflib.Patch; + +/** + *

+ * This class represents a pair of tasks and their corresponding similarity level, respectively, + * their diff level. In addition, it contains the task traversal, i.e., the flattened variants + * of the compared tasks. It provides static methods to compare two tasks and get an object of this + * class as result. Furthermore, it allows to adapt the contained traversals so that unmergable + * subtasks are not traversed. + *

+ * + * @author Patrick Harms + */ +public class SimilarTasks { + + /** + * result of the string like comparison of both task traversals + */ + private Patch patch; + + /** + * the diff level resulting from the comparison + */ + private int diffLevel; + + /** + * the first compared task + */ + private ITask leftHandSide; + + /** + * the second compare task + */ + private ITask rightHandSide; + + /** + * the traversal of the first task + */ + private TaskTraversal leftHandSideTraversal; + + /** + * the traversal of the second task + */ + private TaskTraversal rightHandSideTraversal; + + /** + * initialized a pair of tasks and calculates its diff level + */ + public SimilarTasks(Patch patch, + ITask task1, + TaskTraversal traversal1, + ITask task2, + TaskTraversal traversal2) + { + this.leftHandSide = task1; + this.leftHandSideTraversal = traversal1; + this.rightHandSide = task2; + this.rightHandSideTraversal = traversal2; + + if (patch != null) { + this.patch = patch; + this.diffLevel = getDiffLevel(patch, traversal1, traversal2); + } + else { + this.diffLevel = 100; + } + } + + /** + * static convenience method to compare two tasks + */ + public static SimilarTasks compareTasks(ITask task1, + ITask task2, + TaskInstanceComparator comparator) + { + return compareTasks(task1, task2, comparator, null, true /* never set to false as a common + path may occur several times + at distinct places in a traversal + and once it may be part of a delta + and once not */); + } + + /** + * static convenience method to compare two tasks but ignoring a given set of subtasks when + * creating the traversals. Furhtermore, it can be defined, if subtasks occurring in both + * similar tasks are traversed or not. + */ + public static SimilarTasks compareTasks(ITask task1, + ITask task2, + TaskInstanceComparator comparator, + List pathsNotToTraverse, + boolean traverseCommonPaths) + { + Set commonInvolvedTasks; + + if (traverseCommonPaths) { + commonInvolvedTasks = new HashSet(); + } + else { + commonInvolvedTasks = getCommonInvolvedTasks(task1, task2); + } + + TaskTraversal traversal1 = + TaskTraversal.getTraversal(task1, commonInvolvedTasks, pathsNotToTraverse); + + TaskTraversal traversal2 = + TaskTraversal.getTraversal(task2, commonInvolvedTasks, pathsNotToTraverse); + + if ((traversal1.size() <= 0) || (traversal2.size() <= 0)) { + return null; + } + + Patch patch = new TaskTraversalMyersDiff(comparator).getDiff(traversal1, traversal2); + + SimilarTasks result = new SimilarTasks(patch, task1, traversal1, task2, traversal2); + + return result; + } + + + /** + * This method checks for mergability of the provided similar tasks and if this is not given, + * it reduces the traversals by ignoring interleaving iterations and other situations until + * the remaining traversals can be the basis of a merge. + */ + public static SimilarTasks getMergableLevelOfSimilarity(SimilarTasks source, + TaskInstanceComparator comparator) + { + SimilarTasks similarTasks = source; + + List pathsToIgnore = similarTasks.getPathsToIgnore(); + + int prevPathsToIgnoreCount = 0; + + do { + prevPathsToIgnoreCount = pathsToIgnore.size(); + + similarTasks = compareTasks + (similarTasks.getLeftHandSide(), similarTasks.getRightHandSide(), + comparator, pathsToIgnore, true); + + similarTasks.dump(System.out); + + List furtherPathsToIgnore = similarTasks.getPathsToIgnore(); + + for (TaskPath path : furtherPathsToIgnore) { + System.out.println(path); + } + + for (TaskPath pathToAdd : furtherPathsToIgnore) { + boolean found = false; + for (TaskPath pathToIgnore : pathsToIgnore) { + if (pathToAdd.equals(pathToIgnore)) { + found = true; + break; + } + } + + if (!found) { + pathsToIgnore.add(pathToAdd); + } + } + } + while (pathsToIgnore.size() > prevPathsToIgnoreCount); + + return similarTasks; + } + + /** + * checks if the delta between the two traversals is at their border or not + */ + public boolean isInBetweenDifference() { + List deltas = patch.getDeltas(); + + for (Delta delta : deltas) { + int origPos = delta.getOriginal().getPosition(); + int origSize = delta.getOriginal().size(); + int revPos = delta.getRevised().getPosition(); + int revSize = delta.getRevised().size(); + + if ((origPos <= 0) || (revPos <= 0)) { + // optional must not be the beginning of the task + return false; + } + else if ((delta.getType() == Delta.TYPE.INSERT) && + ((revPos + revSize) >= rightHandSideTraversal.size())) + { + // optional must not be the end of the right hand side task + return false; + } + else if ((delta.getType() == Delta.TYPE.DELETE) && + ((origPos + origSize) >= leftHandSideTraversal.size())) + { + // optional must not be the end of the left hand side task + return false; + } + else if ((delta.getType() == Delta.TYPE.CHANGE) && + (((revPos + revSize) >= rightHandSideTraversal.size()) || + ((origPos + origSize) >= leftHandSideTraversal.size()))) + { + // selection must not be the end of the left hand or right hand side task + return false; + } + } + + return deltas.size() > 0; + } + + /** + * @return the patch + */ + public Patch getPatch() { + return patch; + } + + /** + * @return the diff level + */ + public int getDiffLevel() { + return diffLevel; + } + + /** + * @return the first task of the comparison + */ + public ITask getLeftHandSide() { + return leftHandSide; + } + + /** + * @return the second task of the comparison + */ + public ITask getRightHandSide() { + return rightHandSide; + } + + /** + * @return the traversal of the first task of the comparison + */ + public TaskTraversal getLeftHandSideTraversal() { + return leftHandSideTraversal; + } + + /** + * @return the traversal of the second task of the comparison + */ + public TaskTraversal getRightHandSideTraversal() { + return rightHandSideTraversal; + } + + /** + * returns paths to subtasks, that can not be merged. + */ + public List getPathsToIgnore() { + List result = new LinkedList(); + Delta singleChangeDelta = null; + + if ((patch.getDeltas().size() == 1) && + (patch.getDeltas().get(0).getType() == Delta.TYPE.CHANGE)) + { + singleChangeDelta = patch.getDeltas().get(0); + } + + // if it is a full change, then the parent of either side must be fully ignored + if (singleChangeDelta != null) { + if ((singleChangeDelta.getOriginal().getPosition() == 0) && + (singleChangeDelta.getOriginal().size() == leftHandSideTraversal.size())) + { + TaskPath path = new TaskPath(); + path.add(leftHandSide, 0); + result.add(path); + } + + if ((singleChangeDelta.getRevised().getPosition() == 0) && + (singleChangeDelta.getRevised().size() == rightHandSideTraversal.size())) + { + TaskPath path = new TaskPath(); + path.add(rightHandSide, 0); + result.add(path); + } + } + + if (result.size() < 2) { + // if we do not already ignore both root tasks, check for selections and interleaving + // iterations that have to be ignored if they belong to a delta + for (Delta delta : patch.getDeltas()) { + //getSelections(delta, result); + getPathsToRealIntersectingIterations(delta, result); + getNotFullyInterleavingIteration(delta, result); + getPathsToParentTasksFullyInsideDelta(delta, result); + } + + // check if there are common subtasks on both sides that lie outside any delta and + // that hence should be ignored (especially when performing flattening of task + // instances later with the goal to preserve as many subtasks and respective instances + int deltaIndex = 0; + int leftTraversalIndex = 0; + int rightTraversalIndex = 0; + Set commonInvolvedTasks = getCommonInvolvedTasks(leftHandSide, rightHandSide); + + do { + Delta delta = deltaIndex < patch.getDeltas().size() + ? patch.getDeltas().get(deltaIndex++) : null; + + int nextLeftTraversalIndex = leftHandSideTraversal.size(); + int nextRightTraversalIndex = rightHandSideTraversal.size(); + + if (delta != null) { + nextLeftTraversalIndex = delta.getOriginal().getPosition() + 1; + nextRightTraversalIndex = delta.getRevised().getPosition() + 1; + + if (delta.getType() == Delta.TYPE.INSERT) { + nextLeftTraversalIndex--; + } + else if (delta.getType() == Delta.TYPE.DELETE) { + nextRightTraversalIndex--; + } + } + + TaskPath[] leftSubTraversal = + leftHandSideTraversal.subList(leftTraversalIndex, nextLeftTraversalIndex); + + for (TaskPath path : leftSubTraversal) { + for (int i = 0; i < path.size(); i++) { + if (commonInvolvedTasks.contains(path.getTask(i))) { + // found a candidate. Check if the candidate does not span more than + // the sub traversal + TaskPath parentPath = path.subPath(0, i + 1); + int[] indexes = leftHandSideTraversal.getIndexesRootedBy(parentPath); + + if ((indexes[0] >= leftTraversalIndex) && + (indexes[1] < nextLeftTraversalIndex)) + { + result.add(parentPath); + break; // breaks only the path but the rest of the traversal is + // checked too + } + } + } + } + + TaskPath[] rightSubTraversal = + rightHandSideTraversal.subList(rightTraversalIndex, nextRightTraversalIndex); + + for (TaskPath path : rightSubTraversal) { + for (int i = 0; i < path.size(); i++) { + if (commonInvolvedTasks.contains(path.getTask(i))) { + // found a candidate. Check if the candidate does not span more than + // the sub traversal + TaskPath parentPath = path.subPath(0, i + 1); + int[] indexes = rightHandSideTraversal.getIndexesRootedBy(parentPath); + + if ((indexes[0] >= rightTraversalIndex) && + (indexes[1] < nextRightTraversalIndex)) + { + result.add(parentPath); + break; // breaks only the path but the rest of the traversal is + // checked too + } + } + } + } + + leftTraversalIndex = nextLeftTraversalIndex; + rightTraversalIndex = nextRightTraversalIndex; + } + while (leftTraversalIndex < leftHandSideTraversal.size()); + + } + + return result; + } + + /** + * + */ + public void dump(PrintStream out) { + out.println(); + out.print("similar tasks: left "); + out.print(leftHandSide); + out.print(" ("); + out.print(leftHandSide.getInstances().size()); + out.print(" instances), right "); + out.print(rightHandSide); + out.print(" ("); + out.print(rightHandSide.getInstances().size()); + out.print(" instances), diff level "); + out.println(diffLevel); + + out.println("left traversal"); + for (TaskPath path : leftHandSideTraversal.getTraversalPaths()) { + out.println(path); + } + + out.println("right traversal"); + for (TaskPath path : rightHandSideTraversal.getTraversalPaths()) { + out.println(path); + } + + if (patch != null) { + out.println("deltas:"); + for (Delta delta : patch.getDeltas()) { + out.println(delta); + } + } + + List linesLeft = new LinkedList(); + TaskPath path = new TaskPath(); + path.add(leftHandSide, 0); + dumpToLineList(path, leftHandSideTraversal, linesLeft); + path.removeLast(); + + List linesRight = new LinkedList(); + path.add(rightHandSide, 0); + dumpToLineList(path, rightHandSideTraversal, linesRight); + + + /*System.out.println("\n#################################################"); + for (int j = 0; ((j < linesLeft.size()) || (j < linesRight.size())); j++) { + String left = j < linesLeft.size() ? linesLeft.get(j) : ""; + String right = j < linesRight.size() ? linesRight.get(j) : ""; + + StringBuffer line = new StringBuffer(); + line.append(j); + line.append(":\t"); + line.append(left); + + for (int k = line.length(); k < 60; k++) { + line.append(' '); + } + + line.append(right); + System.out.println(line); + }*/ + + // change lists to have the same length depending on the changes + int lineIndexLeft = 0; + int lineIndexRight = 0; + int leftHandTraversalIndex = 0; + while (leftHandTraversalIndex < leftHandSideTraversal.size()) { + + //System.out.println("\n" + lineIndexLeft + " " + lineIndexRight); + + Delta delta = null; + + for (Delta candidate : patch.getDeltas()) { + if (candidate.getOriginal().getPosition() == leftHandTraversalIndex) { + delta = candidate; + break; + } + } + + if ((delta != null) && (delta.getType() == Delta.TYPE.DELETE)) { + for (int j = 0; j < delta.getOriginal().size(); j++) { + while (linesLeft.get(lineIndexLeft) != null) { + lineIndexLeft++; + } + + linesLeft.remove(lineIndexLeft); + + while (lineIndexRight < lineIndexLeft) { + linesRight.add(lineIndexRight++, null); + } + + leftHandTraversalIndex++; + } + + linesLeft.add(lineIndexLeft++, "-------------------------------------"); + linesRight.add(lineIndexRight++, "-------------------------------------"); + } + else if ((delta != null) && (delta.getType() == Delta.TYPE.INSERT)) { + for (int j = 0; j < delta.getRevised().size(); j++) { + while (linesRight.get(lineIndexRight) != null) { + lineIndexRight++; + } + + linesRight.remove(lineIndexRight); + + while (lineIndexLeft < lineIndexRight) { + linesLeft.add(lineIndexLeft++, null); + } + } + + // ensure that what is equal is harmonized too (because after an insert always + // comes something equal). The traversal index will be updated automatically, + // too. + delta = null; + + linesLeft.add(lineIndexLeft++, "-------------------------------------"); + linesRight.add(lineIndexRight++, "-------------------------------------"); + } + + if ((delta == null) || (delta.getType() == Delta.TYPE.CHANGE)) { + int chunkSizeLeft = delta != null ? delta.getOriginal().size() : 1; + int chunkSizeRight = delta != null ? delta.getRevised().size() : 1; + + int chunksHandledLeft = 0; + int chunksHandledRight = 0; + + for (int j = 0; j < Math.max(chunkSizeLeft, chunkSizeRight); j++) { + if (chunksHandledLeft < chunkSizeLeft) { + while (linesLeft.get(lineIndexLeft) != null) { + lineIndexLeft++; + } + + linesLeft.remove(lineIndexLeft); + chunksHandledLeft++; + } + + if (chunksHandledRight < chunkSizeRight) { + while (linesRight.get(lineIndexRight) != null) { + lineIndexRight++; + } + + linesRight.remove(lineIndexRight); + chunksHandledRight++; + } + + while (lineIndexLeft < lineIndexRight) { + linesLeft.add(lineIndexLeft++, null); + } + while (lineIndexRight < lineIndexLeft) { + linesRight.add(lineIndexRight++, null); + } + } + + linesLeft.add(lineIndexLeft++, "-------------------------------------"); + linesRight.add(lineIndexRight++, "-------------------------------------"); + + leftHandTraversalIndex += delta != null ? delta.getOriginal().size() : 1; + } + + /*System.out.println(delta + " " + leftHandTraversalIndex); + System.out.println("\n#################################################"); + for (int j = 0; ((j < linesLeft.size()) || (j < linesRight.size())); j++) { + String left = j < linesLeft.size() ? linesLeft.get(j) : ""; + String right = j < linesRight.size() ? linesRight.get(j) : ""; + + StringBuffer line = new StringBuffer(); + line.append(j); + line.append(":\t"); + line.append(left); + + for (int k = line.length(); k < 60; k++) { + line.append(' '); + } + + line.append(right); + System.out.println(line); + }*/ + } + + int indentLeft = 0; + int indentRight = 0; + + for (int i = 0; i < linesLeft.size(); i++) { + StringBuffer line = new StringBuffer(); + String left = linesLeft.get(i); + String right = linesRight.get(i); + + if (left != null) { + if (left.indexOf('}') >= 0) { + indentLeft -= 2; + } + + for (int j = 0; j < indentLeft; j++) { + line.append(' '); + } + + if (left.indexOf('{') >= 0) { + indentLeft += 2; + } + + line.append(left); + } + + if (right != null) { + for (int j = line.length(); j < 100; j++) { + line.append(' '); + } + if (right.indexOf('}') >= 0) { + indentRight -= 2; + } + + for (int j = 0; j < indentRight; j++) { + line.append(' '); + } + + if (right.indexOf('{') >= 0) { + indentRight += 2; + } + + line.append(right); + } + + out.println(line); + } + } + + /** + * + */ + private static Set getCommonInvolvedTasks(ITask task1, ITask task2) { + Set result = getAllInvolvedTasks(task1); + result.retainAll(getAllInvolvedTasks(task2)); + return result; + } + + /** + * + */ + private static Set getAllInvolvedTasks(ITask task) { + final Set result = new HashSet(); + + task.accept(new DefaultTaskTraversingVisitor() { + @Override + public void visit(IEventTask eventTask) { + result.add(eventTask); + } + + @Override + public void visit(IStructuringTemporalRelationship relationship) { + result.add(relationship); + super.visit(relationship); + } + + @Override + public void visit(IMarkingTemporalRelationship relationship) { + result.add(relationship); + super.visit(relationship); + } + }); + + return result; + } + + /** + * + */ + private void dumpToLineList(TaskPath path, + TaskTraversal traversal, + List lines) + { + boolean isTraversalElement = false; + + for (TaskPath candidate : traversal.getTraversalPaths()) { + if (path.equals(candidate)) { + isTraversalElement = true; + break; + } + } + + if (isTraversalElement) { + lines.add(path.getLast().toString()); + lines.add(null); + /*ByteArrayOutputStream byteStream = new ByteArrayOutputStream(); + PrintStream out = new PrintStream(byteStream); + + new TaskTreeEncoder().encode(path.getLast(), out); + + out.close(); + + BufferedReader reader = new BufferedReader + (new InputStreamReader(new ByteArrayInputStream(byteStream.toByteArray()))); + + String line = null; + do { + try { + line = reader.readLine(); + } + catch (IOException e) { + // should not happen so dump hard + e.printStackTrace(); + } + lines.add(line != null ? line.trim() : null); + } + while (line != null);*/ + + } + else { + ITask task = path.getLast(); + if (task instanceof ITemporalRelationship) { + lines.add(task + " {"); + + if (task instanceof IStructuringTemporalRelationship) { + List children = + ((IStructuringTemporalRelationship) task).getChildren(); + + for (int i = 0; i < children.size(); i++) { + path.add(children.get(i), i); + dumpToLineList(path, traversal, lines); + path.removeLast(); + } + } + else if (task instanceof IMarkingTemporalRelationship) { + IMarkingTemporalRelationship relationship = + (IMarkingTemporalRelationship) task; + + path.add(relationship.getMarkedTask(), 0); + dumpToLineList(path, traversal, lines); + path.removeLast(); + } + + if (lines.get(lines.size() - 1) != null) { + lines.add("}"); + } + else { + lines.add(lines.size() - 1, "}"); + } + } + else { + lines.add(task + " {}"); + } + } + } + + /** + * + */ + /*@SuppressWarnings("unchecked") + private void getSelections(Delta delta, List result) { + TaskPath path1 = getCommonPath((List) delta.getOriginal().getLines()); + TaskPath path2 = getCommonPath((List) delta.getRevised().getLines()); + + for (int i = 0; i < path1.size(); i++) { + if (path1.getTask(i) instanceof ISelection) { + System.out.println("found selection to ignore"); + System.out.println(path1.subPath(0, i + 1)); + result.add(path1.subPath(0, i + 1)); + break; + } + } + + for (int i = 0; i < path2.size(); i++) { + if (path2.getTask(i) instanceof ISelection) { + System.out.println("found selection to ignore"); + System.out.println(path2.subPath(0, i + 1)); + result.add(path2.subPath(0, i + 1)); + break; + } + } + }*/ + + /** + * + */ + @SuppressWarnings("unchecked") + private void getPathsToRealIntersectingIterations(Delta delta, List paths) { + TaskPath path1 = getCommonPath((List) delta.getOriginal().getLines()); + TaskPath path2 = getCommonPath((List) delta.getRevised().getLines()); + + // both paths denote those parent tasks that contain the delta. + // But there may be parent tasks still contained in the path that are iterations and + // that are disjoint with a parent in the other path. Those iterations need to be + // considered, as otherwise a created selection would be against the associative law of + // iterations. Hence, we search for the topmost iteration on both paths that is disjoint + // with a parent node in the respective other path. + + for (int i = 0; i < path1.size(); i++) { + TaskPath path1Prefix = path1.subPath(0, i + 1); + int[] idxsPath1 = leftHandSideTraversal.getIndexesRootedBy(path1Prefix); + + // normalize the indexes to be 0 the index of the delta. Everything left of it + // is smaller 0, everything right of it, larger. + idxsPath1[0] -= delta.getOriginal().getPosition(); + idxsPath1[1] -= delta.getOriginal().getPosition() + delta.getOriginal().size() - 1; + + for (int j = 0; j < path2.size(); j++) { + TaskPath path2Prefix = path2.subPath(0, j + 1); + int[] idxsPath2 = rightHandSideTraversal.getIndexesRootedBy(path2Prefix); + + // normalize the indexes to be 0 the index of the delta. Everything left of it + // is smaller 0, everything right of it, larger. + idxsPath2[0] -= delta.getRevised().getPosition(); + idxsPath2[1] -= + delta.getRevised().getPosition() + delta.getRevised().size() - 1; + + // now compare the indexes and check, if the sublists are real subsets of each + // other. If not, they only have a real common subset but there is at least one + // non shared element on both sides. If so, and one is an iteration, we + // have to use it as elements to be selected + if (((idxsPath1[0] < idxsPath2[0]) && (idxsPath1[1] < idxsPath2[1])) || + ((idxsPath1[0] > idxsPath2[0]) && (idxsPath1[1] > idxsPath2[1]))) + { + if ((path1.get(i).getTask() instanceof IIteration) && + (path2.get(j).getTask() instanceof IIteration)) + { + System.out.println("found paths to real intersecting parents"); + int[] indexBuf = leftHandSideTraversal.getIndexesRootedBy(path1Prefix); + System.out.println(idxsPath1[0] + "(" + indexBuf[0] + ") " + idxsPath1[1] + + "(" + indexBuf[1] + ") " + path1Prefix); + indexBuf = rightHandSideTraversal.getIndexesRootedBy(path2Prefix); + System.out.println(idxsPath2[0] + "(" + indexBuf[0] + ") " + idxsPath2[1] + + "(" + indexBuf[1] + ") " + path2Prefix); + + paths.add(path1Prefix); + paths.add(path2Prefix); + return; + } + } + } + } + } + + /** + * + */ + private TaskPath getCommonPath(List paths) { + TaskPath commonPath; + + if (paths.size() > 0) { + commonPath = new TaskPath(paths.get(0)); + + for (int i = 1; i < paths.size(); i++) { + TaskPath comparePath = paths.get(i); + for (int j = 0; (j < commonPath.size()) && (j < comparePath.size()); j++) { + if (!commonPath.get(j).equals(comparePath.get(j))) { + while (commonPath.size() > j) { + commonPath.remove(j); + } + break; + } + } + } + } + else { + commonPath = new TaskPath(); + } + + return commonPath; + } + + /** + * + */ + private void getNotFullyInterleavingIteration(Delta delta, List result) { + getNotFullyInterleavingIterations(delta.getOriginal(), leftHandSideTraversal, result); + getNotFullyInterleavingIterations(delta.getRevised(), rightHandSideTraversal, result); + } + + /** + * If a chunk has a minimum number of 2 entries and at least one of them belongs to an iteration + * the does not cover the other and also expands to preceding or succeeding paths in the + * traversal, we can no merge the situation. + */ + private void getNotFullyInterleavingIterations(Chunk chunk, + TaskTraversal traversal, + List result) + { + @SuppressWarnings("unchecked") + List paths = (List) chunk.getLines(); + + TaskPath commonPath = getCommonPath(paths); + + if (paths.size() > 1) { + TaskPath firstPath = paths.get(0); + TaskPath lastPath = paths.get(paths.size() - 1); + + for (int i = commonPath.size(); i < firstPath.size(); i++) { + if (firstPath.get(i).getTask() instanceof IIteration) { + // check, if the iteration covers things preceding the delta but not the whole + // delta + int[] indexes = traversal.getIndexesRootedBy(firstPath.subPath(0, i + 1)); + + if ((indexes[0] < chunk.getPosition()) && // starts before the delta + (indexes[1] < (chunk.getPosition() + chunk.size() - 1))) // does not cover delta + { + result.add(firstPath.subPath(0, i + 1)); + break; + } + } + } + + for (int i = commonPath.size(); i < lastPath.size(); i++) { + if (lastPath.get(i).getTask() instanceof IIteration) { + // check, if the iteration covers things preceding the delta but not the whole + // delta + int[] indexes = traversal.getIndexesRootedBy(lastPath.subPath(0, i + 1)); + + if ((indexes[0] > chunk.getPosition()) && // starts in between the delta + (indexes[1] >= (chunk.getPosition() + chunk.size()))) // ends after the delta + { + result.add(lastPath.subPath(0, i + 1)); + break; + } + } + } + } + } + + /** + * + */ + private void getPathsToParentTasksFullyInsideDelta(Delta delta, List result) { + getPathsToParentTasksFullyInsideChunk(delta.getOriginal(), leftHandSideTraversal, result); + getPathsToParentTasksFullyInsideChunk(delta.getRevised(), rightHandSideTraversal, result); + } + + /** + * If a chunk has a minimum number of 2 entries and at least one of them belongs to an iteration + * the does not cover the other and also expands to preceding or succeeding paths in the + * traversal, we can no merge the situation. + */ + private void getPathsToParentTasksFullyInsideChunk(Chunk chunk, + TaskTraversal traversal, + List result) + { + @SuppressWarnings("unchecked") + List paths = (List) chunk.getLines(); + + TaskPath commonPath = getCommonPath(paths); + + for (TaskPath path : paths) { + for (int i = commonPath.size(); i < path.size(); i++) { + if (!(path.getLast() instanceof IEventTask)) { + // check, if the parent task covers things fully inside the delta + int[] indexes = traversal.getIndexesRootedBy(path.subPath(0, i + 1)); + + if ((chunk.getPosition() <= indexes[0]) && // starts in the delta + (indexes[1] < (chunk.getPosition() + chunk.size()))) // ends in the delta + { + System.out.println("found path to parent task lieing completely in the " + + "delta: " + path.subPath(0, i + 1)); + result.add(path.subPath(0, i + 1)); + break; + } + } + } + } + } + + /** + * + */ + @SuppressWarnings("unchecked") + private int getDiffLevel(Patch patch, + TaskTraversal traversal1, + TaskTraversal traversal2) + { + int diffCount = 0; + int allCount = 0; + + for (Delta delta : patch.getDeltas()) { + for (TaskPath path : (List) delta.getOriginal().getLines()) { + // inefficient actions are counted later. + if (!isInefficientAction(path.getLast())) { + diffCount += getDiffPenalty(path.getLast()); + } + } + for (TaskPath path : (List) delta.getRevised().getLines()) { + // inefficient actions are counted later. + if (!isInefficientAction(path.getLast())) { + diffCount += getDiffPenalty(path.getLast()); + } + } + } + + //if (getPathsToRealIntersectingIterations().size() > 0) { + // add a penalty if intersecting iterations are present + //count += 10; + //} + + // add a penalty for inefficient actions which are equal as they have to be treated + // unequal, too. Otherwise, many scrolls, e.g., would pretend a high equality of tasks + // which contain only some non inefficient actions + for (TaskPath path : traversal1.getTraversalPaths()) { + if (isInefficientAction(path.getLast())) { + diffCount++; + } + else { + allCount += getDiffPenalty(path.getLast()); + } + } + + for (TaskPath path : traversal2.getTraversalPaths()) { + if (isInefficientAction(path.getLast())) { + diffCount++; + } + else { + allCount += getDiffPenalty(path.getLast()); + } + } + + return (100 * diffCount) / allCount; + } + + /** + * + */ + private boolean isInefficientAction(ITask task) { + ITaskInstance inst = task.getInstances().iterator().next(); + + if ((inst instanceof IEventTaskInstance) && + (((IEventTaskInstance) inst).getEvent().getType() instanceof Scroll)) + { + return true; + } + else if (task instanceof IMarkingTemporalRelationship) { + return isInefficientAction(((IMarkingTemporalRelationship) task).getMarkedTask()); + } + else { + return false; + } + } + + + /** + * + */ + private int getDiffPenalty(ITask task) { + if (task instanceof IEventTask) { + return 1; + } + else if (task instanceof IMarkingTemporalRelationship) { + return getDiffPenalty(((IMarkingTemporalRelationship) task).getMarkedTask()); + } + else if (task instanceof IStructuringTemporalRelationship) { + int result = 0; + + for (ITask child : ((IStructuringTemporalRelationship) task).getChildren()) { + result += getDiffPenalty(child); + } + + if (task instanceof ISelection) { + result /= ((IStructuringTemporalRelationship) task).getChildren().size(); + } + + return result; + } + + throw new IllegalArgumentException("unknown type of task: " + task); + } +} Index: /trunk/autoquest-core-tasktrees/src/main/java/de/ugoe/cs/autoquest/tasktrees/temporalrelation/utils/TaskTraversal.java =================================================================== --- /trunk/autoquest-core-tasktrees/src/main/java/de/ugoe/cs/autoquest/tasktrees/temporalrelation/utils/TaskTraversal.java (revision 1767) +++ /trunk/autoquest-core-tasktrees/src/main/java/de/ugoe/cs/autoquest/tasktrees/temporalrelation/utils/TaskTraversal.java (revision 1767) @@ -0,0 +1,237 @@ +// Copyright 2012 Georg-August-Universität Göttingen, Germany +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. + +package de.ugoe.cs.autoquest.tasktrees.temporalrelation.utils; + +import java.io.PrintStream; +import java.util.Arrays; +import java.util.LinkedList; +import java.util.List; +import java.util.Set; + +import de.ugoe.cs.autoquest.tasktrees.treeifc.DefaultTaskTraversingVisitor; +import de.ugoe.cs.autoquest.tasktrees.treeifc.IEventTask; +import de.ugoe.cs.autoquest.tasktrees.treeifc.IMarkingTemporalRelationship; +import de.ugoe.cs.autoquest.tasktrees.treeifc.ISelection; +import de.ugoe.cs.autoquest.tasktrees.treeifc.ISequence; +import de.ugoe.cs.autoquest.tasktrees.treeifc.ITask; +import de.ugoe.cs.autoquest.tasktrees.treeifc.TaskPath; + +/** + *

+ * TODO comment + *

+ * + * @author Patrick Harms + */ +public class TaskTraversal { + + /** */ + private List traversalPaths = new LinkedList(); + + /** */ + private TaskPath[] traversalPathArray = null; + + /** + * + */ + public static TaskTraversal getTraversal(ITask task, + final Set untraversedTasks, + final List untraversedPaths) + { + final TaskTraversal result = new TaskTraversal(); + final TaskPath currentPath = new TaskPath(); + final int[] currentIndex = new int[1]; + currentIndex[0] = 0; + + task.accept(new DefaultTaskTraversingVisitor() { + @Override + public void visit(IEventTask eventTask) { + currentPath.add(eventTask, currentIndex[0]); + result.add(new TaskPath(currentPath)); + currentPath.removeLast(); + } + + @Override + public void visit(ISequence relationship) { + currentPath.add(relationship, currentIndex[0]); + + if (pathIsInList(currentPath, untraversedPaths) || + untraversedTasks.contains(relationship)) + { + result.add(new TaskPath(currentPath)); + } + else { + int indexBuffer = currentIndex[0]; + + List children = relationship.getChildren(); + for (int i = 0; i < children.size(); i++) { + currentIndex[0] = i; + super.visit(children.get(i)); + } + + currentIndex[0] = indexBuffer; + } + + currentPath.removeLast(); + } + + @Override + public void visit(ISelection relationship) { + // selections are never traversed as a traversal can have different orders for + // for semantically identical selections + currentPath.add(relationship, currentIndex[0]); + result.add(new TaskPath(currentPath)); + currentPath.removeLast(); + } + + @Override + public void visit(IMarkingTemporalRelationship relationship) { + ITask markedTask = relationship.getMarkedTask(); + + while (markedTask instanceof IMarkingTemporalRelationship) { + markedTask = ((IMarkingTemporalRelationship) markedTask).getMarkedTask(); + } + + currentPath.add(relationship, currentIndex[0]); + + if (pathIsInList(currentPath, untraversedPaths) || + untraversedTasks.contains(relationship)) + { + result.add(new TaskPath(currentPath)); + } + // if the child is an event task we do not traverse this marking temporal + // relationship + else if (markedTask instanceof IEventTask) { + result.add(new TaskPath(currentPath)); + } + else { + int indexBuffer = currentIndex[0]; + currentIndex[0] = 0; + super.visit(relationship); + currentIndex[0] = indexBuffer; + } + + currentPath.removeLast(); + } + }); + + result.setComplete(); + + return result; + } + + /** + * + */ + public int[] getIndexesRootedBy(TaskPath pathToRoot) { + int[] indexes = new int[] { -1, -1 }; + + for (int i = 0; i < traversalPathArray.length; i++) { + TaskPath path = traversalPathArray[i]; + + // check if the path starts with the path to the root + if (path.size() >= pathToRoot.size()) { + boolean startsWithPathToRoot = true; + + for (int j = 0; (j < pathToRoot.size()) && (j < path.size()); j++) { + if (!pathToRoot.get(j).equals(path.get(j))) { + startsWithPathToRoot = false; + break; + } + } + + if (startsWithPathToRoot) { + if (indexes[0] < 0) { + indexes[0] = i; + } + indexes[1] = i; + } + } + } + + return indexes; + + } + + /** + * + */ + public TaskPath[] subList(int fromIndex, int toIndex) { + return Arrays.copyOfRange(traversalPathArray, fromIndex, toIndex); + } + + /** + * + */ + public ITask get(int i) { + return traversalPathArray[i].getLast(); + } + + /** + * + */ + public int size() { + return traversalPathArray.length; + } + + /** + * @return the traversalPaths + */ + public TaskPath[] getTraversalPaths() { + return traversalPathArray; + } + + /** + * + */ + public void dump(PrintStream out) { + for (TaskPath path : traversalPathArray) { + out.print(path.getLast().getId()); + out.print('\t'); + } + + out.println(); + } + + /** + * + */ + private void add(TaskPath taskPath) { + traversalPaths.add(taskPath); + } + + /** + * + */ + private void setComplete() { + traversalPathArray = traversalPaths.toArray(new TaskPath[traversalPaths.size()]); + traversalPaths = null; + } + + /** + * + */ + private static boolean pathIsInList(TaskPath path, List pathList) { + if (pathList != null) { + for (TaskPath candidate : pathList) { + if (path.equals(candidate)) { + return true; + } + } + } + + return false; + } +} Index: /trunk/autoquest-core-tasktrees/src/main/java/de/ugoe/cs/autoquest/tasktrees/temporalrelation/utils/TaskTraversalMyersDiff.java =================================================================== --- /trunk/autoquest-core-tasktrees/src/main/java/de/ugoe/cs/autoquest/tasktrees/temporalrelation/utils/TaskTraversalMyersDiff.java (revision 1767) +++ /trunk/autoquest-core-tasktrees/src/main/java/de/ugoe/cs/autoquest/tasktrees/temporalrelation/utils/TaskTraversalMyersDiff.java (revision 1767) @@ -0,0 +1,193 @@ +// Copyright 2012 Georg-August-Universität Göttingen, Germany +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. + +package de.ugoe.cs.autoquest.tasktrees.temporalrelation.utils; + +import de.ugoe.cs.autoquest.tasktrees.temporalrelation.TaskInstanceComparator; +import difflib.ChangeDelta; +import difflib.Chunk; +import difflib.DeleteDelta; +import difflib.Delta; +import difflib.InsertDelta; +import difflib.Patch; +import difflib.myers.DiffNode; +import difflib.myers.MyersDiff; +import difflib.myers.PathNode; +import difflib.myers.Snake; + +/** + * + */ +public class TaskTraversalMyersDiff extends MyersDiff { + + /** */ + private final TaskInstanceComparator comparator; + + /** + * + */ + public TaskTraversalMyersDiff(TaskInstanceComparator comparator) { + this.comparator = comparator; + } + + /** + * + */ + public Patch getDiff(TaskTraversal variant1, TaskTraversal variant2) { + PathNode path = buildPath(variant1, variant2); + return buildRevision(path, variant1, variant2); + } + + /** + * overwrites the default implementation just to change the tree task comparison. + * This is an extended version of the original implementation respecting the appropriate + * copyrights. Please see the copyrights of the implementers of the base class for more + * information + */ + private PathNode buildPath(TaskTraversal variant1, TaskTraversal variant2) { + if (variant1 == null) { + throw new IllegalArgumentException("variant1 is null"); + } + + if (variant2 == null) { + throw new IllegalArgumentException("variant2 is null"); + } + + // these are local constants + final int N = variant1.size(); + final int M = variant2.size(); + + final int MAX = N + M + 1; + final int size = 1 + 2 * MAX; + final int middle = size / 2; + final PathNode diagonal[] = new PathNode[size]; + + diagonal[middle + 1] = new Snake(0, -1, null); + + for (int d = 0; d < MAX; d++) { + for (int k = -d; k <= d; k += 2) { + final int kmiddle = middle + k; + final int kplus = kmiddle + 1; + final int kminus = kmiddle - 1; + PathNode prev = null; + + int i; + if ((k == -d) || ((k != d) && (diagonal[kminus].i < diagonal[kplus].i))) { + i = diagonal[kplus].i; + prev = diagonal[kplus]; + } + else { + i = diagonal[kminus].i + 1; + prev = diagonal[kminus]; + } + + diagonal[kminus] = null; // no longer used + + int j = i - k; + + PathNode task = new DiffNode(i, j, prev); + + // orig and rev are zero-based + // but the algorithm is one-based + // that's why there's no +1 when indexing the sequences + synchronized (comparator) { + while ((i < N) && (j < M) && comparator.equals(variant1.get(i), variant2.get(j))) + { + i++; + j++; + } + } + + if (i > task.i) { + task = new Snake(i, j, task); + } + + diagonal[kmiddle] = task; + + if ((i >= N) && (j >= M)) { + return diagonal[kmiddle]; + } + } + diagonal[middle + d - 1] = null; + + } + + // According to Myers, this cannot happen + throw new RuntimeException("could not find a diff path"); + } + + /** + * overwrites the default implementation just to change the tree task comparison. + * This is an extended version of the original implementation respecting the appropriate + * copyrights. Please see the copyrights of the implementers of the base class for more + * information + */ + private Patch buildRevision(PathNode path, + TaskTraversal variant1, + TaskTraversal variant2) + { + if (path == null) { + throw new IllegalArgumentException("path is null"); + } + + if (variant1 == null) { + throw new IllegalArgumentException("variant1 is null"); + } + + if (variant2 == null) { + throw new IllegalArgumentException("variant2 is null"); + } + + Patch patch = new Patch(); + if (path.isSnake()) { + path = path.prev; + } + + while ((path != null) && (path.prev != null) && (path.prev.j >= 0)) { + if (path.isSnake()) { + throw new IllegalStateException + ("bad diffpath: found snake when looking for diff"); + } + + int i = path.i; + int j = path.j; + + path = path.prev; + int ianchor = path.i; + int janchor = path.j; + + Chunk original = new Chunk(ianchor, variant1.subList(ianchor, i)); + Chunk revised = new Chunk(janchor, variant2.subList(janchor, j)); + Delta delta = null; + + if ((original.size() == 0) && (revised.size() != 0)) { + delta = new InsertDelta(original, revised); + } + else if ((original.size() > 0) && (revised.size() == 0)) { + delta = new DeleteDelta(original, revised); + } + else { + delta = new ChangeDelta(original, revised); + } + + patch.addDelta(delta); + + if (path.isSnake()) { + path = path.prev; + } + } + return patch; + } + +} Index: /trunk/autoquest-core-tasktrees/src/main/java/de/ugoe/cs/autoquest/tasktrees/treeifc/TaskPath.java =================================================================== --- /trunk/autoquest-core-tasktrees/src/main/java/de/ugoe/cs/autoquest/tasktrees/treeifc/TaskPath.java (revision 1767) +++ /trunk/autoquest-core-tasktrees/src/main/java/de/ugoe/cs/autoquest/tasktrees/treeifc/TaskPath.java (revision 1767) @@ -0,0 +1,246 @@ +// Copyright 2012 Georg-August-Universität Göttingen, Germany +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. + +package de.ugoe.cs.autoquest.tasktrees.treeifc; + +import java.util.LinkedList; + +/** + *

+ * TODO comment + *

+ * + * @author Patrick Harms + */ +public class TaskPath { + + /** */ + private LinkedList taskList; + + /** + * + * + */ + public TaskPath() { + super(); + taskList = new LinkedList(); + } + + /** + * + */ + public TaskPath(TaskPath path) { + this(); + taskList.addAll(path.taskList); + } + + /** + * + */ + public TaskPath subPath(int fromIndex, int toIndex) { + TaskPath result = new TaskPath(); + result.taskList.addAll(taskList.subList(fromIndex, toIndex)); + return result; + } + + /** + * + */ + public ITask removeLast() { + Entry last = taskList.removeLast(); + if (last != null) { + return last.getTask(); + } + else { + return null; + } + } + + /** + * + */ + public ITask getLast() { + Entry last = taskList.getLast(); + if (last != null) { + return last.getTask(); + } + else { + return null; + } + } + + /* (non-Javadoc) + * @see java.lang.Object#toString() + */ + @Override + public String toString() { + return taskList.toString(); + } + + /** + * + */ + public int size() { + return taskList.size(); + } + + /** + * + */ + public boolean isEmpty() { + return taskList.isEmpty(); + } + + /** + * + */ + public void add(ITask task, int index) { + taskList.add(new Entry(task, index)); + } + + /** + * + */ + public ITask getTask(int index) { + Entry last = taskList.get(index); + if (last != null) { + return last.getTask(); + } + else { + return null; + } + } + + /** + * + */ + public Entry get(int index) { + return taskList.get(index); + } + + /** + * + */ + public void remove(int index) { + taskList.remove(index); + } + + + /* (non-Javadoc) + * @see java.lang.Object#hashCode() + */ + @Override + public int hashCode() { + ITask last = getLast(); + if (last != null) { + return last.hashCode(); + } + else { + return 0; + } + } + + /* (non-Javadoc) + * @see java.lang.Object#equals(java.lang.Object) + */ + @Override + public boolean equals(Object obj) { + if (this == obj) { + return true; + } + else if (obj instanceof TaskPath) { + TaskPath other = (TaskPath) obj; + if ((other != null) && (this.size() == other.size())) { + for (int i = 0; i < this.size(); i++) { + if (!this.get(i).equals(other.get(i))) { + return false; + } + } + return true; + } + } + + return false; + } + + + /** + * + */ + public static class Entry { + + /** */ + private ITask task; + + /** */ + private int index; + + /** + * + */ + private Entry(ITask task, int index) { + this.task = task; + this.index = index; + } + + /* (non-Javadoc) + * @see java.lang.Object#toString() + */ + @Override + public String toString() { + return "(" + task + "," + index + ")"; + } + + /** + * @return the task + */ + public ITask getTask() { + return task; + } + + /** + * @return the index + */ + public int getIndex() { + return index; + } + + /* (non-Javadoc) + * @see java.lang.Object#hashCode() + */ + @Override + public int hashCode() { + return task.hashCode(); + } + + /* (non-Javadoc) + * @see java.lang.Object#equals(java.lang.Object) + */ + @Override + public boolean equals(Object obj) { + if (this == obj) { + return true; + } + else if (obj instanceof TaskPath.Entry) { + return (this.getIndex() == ((TaskPath.Entry) obj).getIndex()) && + (this.getTask().equals(((TaskPath.Entry) obj).getTask())); + } + + return false; + } + + + } + +} Index: /trunk/autoquest-core-tasktrees/src/main/java/de/ugoe/cs/autoquest/tasktrees/treeifc/TaskTreeUtils.java =================================================================== --- /trunk/autoquest-core-tasktrees/src/main/java/de/ugoe/cs/autoquest/tasktrees/treeifc/TaskTreeUtils.java (revision 1767) +++ /trunk/autoquest-core-tasktrees/src/main/java/de/ugoe/cs/autoquest/tasktrees/treeifc/TaskTreeUtils.java (revision 1767) @@ -0,0 +1,52 @@ +// Copyright 2012 Georg-August-Universität Göttingen, Germany +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. + +package de.ugoe.cs.autoquest.tasktrees.treeifc; + +/** + *

+ * TODO comment + *

+ * + * @author Patrick Harms + */ +public class TaskTreeUtils { + + /** + * + */ + public static boolean isChild(ITask potentialChild, ITask potentialParent) { + if (potentialParent instanceof IStructuringTemporalRelationship) { + for (ITask child : ((IStructuringTemporalRelationship) potentialParent).getChildren()) { + if (child.equals(potentialChild) || isChild(potentialChild, child)) { + return true; + } + } + } + else if (potentialParent instanceof IMarkingTemporalRelationship) { + ITask child = ((IMarkingTemporalRelationship) potentialParent).getMarkedTask(); + if (child.equals(potentialChild) || isChild(potentialChild, child)) { + return true; + } + } + + return false; + } + + + /** + * + */ + private TaskTreeUtils() { /* prevent instantiation */ } +}