Index: /trunk/autoquest-ui-core/src/main/java/de/ugoe/cs/autoquest/commands/usability/CMDgetTaskModelSimilarity.java
===================================================================
--- /trunk/autoquest-ui-core/src/main/java/de/ugoe/cs/autoquest/commands/usability/CMDgetTaskModelSimilarity.java (revision 1895)
+++ /trunk/autoquest-ui-core/src/main/java/de/ugoe/cs/autoquest/commands/usability/CMDgetTaskModelSimilarity.java (revision 1895)
@@ -0,0 +1,753 @@
+// 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.commands.usability;
+
+import java.text.DecimalFormat;
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.HashMap;
+import java.util.IdentityHashMap;
+import java.util.LinkedList;
+import java.util.List;
+import java.util.Map;
+import java.util.logging.Level;
+
+import de.ugoe.cs.autoquest.CommandHelpers;
+import de.ugoe.cs.autoquest.eventcore.IEventTarget;
+import de.ugoe.cs.autoquest.tasktrees.taskequality.TaskEquality;
+import de.ugoe.cs.autoquest.tasktrees.taskequality.TaskEqualityRuleManager;
+import de.ugoe.cs.autoquest.tasktrees.temporalrelation.TaskComparator;
+import de.ugoe.cs.autoquest.tasktrees.temporalrelation.utils.SimilarTasks;
+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.ISelection;
+import de.ugoe.cs.autoquest.tasktrees.treeifc.ISequence;
+import de.ugoe.cs.autoquest.tasktrees.treeifc.ITask;
+import de.ugoe.cs.autoquest.tasktrees.treeifc.ITaskModel;
+import de.ugoe.cs.autoquest.tasktrees.treeifc.TaskMetric;
+import de.ugoe.cs.util.StopWatch;
+import de.ugoe.cs.util.console.Command;
+import de.ugoe.cs.util.console.Console;
+import de.ugoe.cs.util.console.GlobalDataContainer;
+
+/**
+ *
+ * compares a set of task models with each other and drops their similarity as results
+ *
+ *
+ * @author Patrick Harms
+ * @version 1.0
+ */
+public class CMDgetTaskModelSimilarity implements Command {
+
+ /*
+ * (non-Javadoc)
+ *
+ * @see de.ugoe.cs.util.console.Command#help()
+ */
+ @Override
+ public String help() {
+ return "getTaskModelSimilarity ...";
+ }
+
+ /*
+ * (non-Javadoc)
+ *
+ * @see de.ugoe.cs.util.console.Command#run(java.util.List)
+ */
+ @Override
+ public void run(List parameters) {
+ List inputTaskTreeNames = new LinkedList<>();
+
+ try {
+ for (Object param : parameters) {
+ inputTaskTreeNames.add((String) param);
+ }
+ }
+ catch (Exception e) {
+ throw new IllegalArgumentException("must provide valid input task tree names");
+ }
+
+ Map> inputTaskModels = new IdentityHashMap<>();
+
+ for (String inputTaskTreeName : inputTaskTreeNames) {
+ Object dataObject = GlobalDataContainer.getInstance().getData(inputTaskTreeName);
+ if (dataObject == null) {
+ CommandHelpers.objectNotFoundMessage(inputTaskTreeName);
+ return;
+ }
+ if (!(dataObject instanceof ITaskModel)) {
+ CommandHelpers.objectNotType(inputTaskTreeName, "ITaskModel");
+ return;
+ }
+
+ List tasksToCompare = new LinkedList<>();
+
+ for (ITask task : ((ITaskModel) dataObject).getTasks()) {
+ if (task instanceof ISequence) {
+ tasksToCompare.add((ISequence) task);
+ }
+ }
+
+ inputTaskModels.put((ITaskModel) dataObject, tasksToCompare);
+ }
+
+ SimilarityStatistics statistics = new SimilarityStatistics();
+
+ getTaskModelSimilarity(inputTaskModels, statistics);
+
+ Console.println("\nsimilarity statistics of all comparisons");
+ statistics.dump();
+ }
+
+ /**
+ *
+ */
+ private void getTaskModelSimilarity(Map> inputTaskModels,
+ SimilarityStatistics statistics)
+ {
+ // create the indexes to not do too many comparisons
+ Map>>> index1 =
+ new IdentityHashMap<>();
+
+ Map index2 = new HashMap<>();
+ Map index3 = new HashMap<>();
+
+ final List terminalNodes = new ArrayList<>();
+ final List selections = new ArrayList<>();
+
+ for (Map.Entry> entry : inputTaskModels.entrySet()) {
+ for (ISequence sequence : entry.getValue()) {
+ terminalNodes.clear();
+ selections.clear();
+
+ sequence.accept(new DefaultTaskTraversingVisitor() {
+ @Override
+ public void visit(IEventTask eventTask) {
+ terminalNodes.add(eventTask);
+ }
+ @Override
+ public void visit(ISelection selection) {
+ selections.add(selection);
+ // no need to traverse children as a sequences containing a selection
+ // will be handled differently
+ }
+ });
+
+ int length = terminalNodes.size();
+ IEventTarget firstTarget = ((IEventTaskInstance) terminalNodes.get(0).getInstances()
+ .iterator().next()).getEvent().getTarget();
+
+ if (selections.size() > 0) {
+ length = -1;
+ firstTarget = null;
+ }
+
+ Map>> lengthMap =
+ index1.get(entry.getKey());
+
+ if (lengthMap == null) {
+ lengthMap = new HashMap<>();
+ index1.put(entry.getKey(), lengthMap);
+ }
+
+ Map> firstTaskMap = lengthMap.get(length);
+
+ if (firstTaskMap == null) {
+ firstTaskMap = new HashMap<>();
+ lengthMap.put(length, firstTaskMap);
+ }
+
+ List compareList = firstTaskMap.get(firstTarget);
+
+ if (compareList == null) {
+ compareList = new LinkedList();
+ firstTaskMap.put(firstTarget, compareList);
+ }
+
+ compareList.add(sequence);
+ index2.put(sequence, length);
+ index3.put(sequence, firstTarget);
+ }
+ }
+
+ // create the comparison runnables
+ List runnables = new LinkedList<>();
+
+ for (Map.Entry> model1 : inputTaskModels.entrySet()) {
+ for (Map.Entry> model2 : inputTaskModels.entrySet()) {
+ if (model1.getKey() != model2.getKey()) {
+ runnables.add(new ComparisonRunnable(model1.getKey(), model1.getValue(),
+ model2.getKey(), model2.getValue(),
+ Collections.unmodifiableMap
+ (index1.get(model2.getKey())),
+ Collections.unmodifiableMap(index2),
+ Collections.unmodifiableMap(index3),
+ runnables));
+ }
+ }
+ }
+
+ // execute the threads
+ Console.traceln(Level.FINE, "scheduling " + runnables.size() + " comparison threads");
+
+ synchronized (runnables) {
+ int startedRunnables = 0;
+ for (ComparisonRunnable runnable : runnables) {
+ while (startedRunnables >= Math.max(1, Runtime.getRuntime().availableProcessors()))
+ {
+ try {
+ Console.traceln(Level.FINER, "waiting for next thread to finish");
+ runnables.wait();
+ startedRunnables--;
+ Console.traceln(Level.FINER, "thread finished");
+ }
+ catch (InterruptedException e) {
+ // should not happen
+ Console.logException(e);
+ }
+ }
+
+ Console.traceln(Level.FINER, "starting next thread");
+ startedRunnables++;
+ Console.traceln(Level.FINE, "comparing " + runnable.tasks1.size()
+ + " tasks of model " + runnable.model1 + " with " +
+ runnable.tasks2.size() + " tasks of model " + runnable.model2);
+
+ new Thread(runnable).start();
+ Console.traceln(Level.FINER, "started next thread " + runnable);
+ }
+
+ while (startedRunnables > 0) {
+ try {
+ Console.traceln(Level.FINER, "waiting for next thread to finish");
+ runnables.wait();
+ startedRunnables--;
+ Console.traceln(Level.FINER, "thread finished");
+ }
+ catch (InterruptedException e) {
+ // should not happen
+ Console.logException(e);
+ }
+ }
+ }
+
+ // merge the results
+ Console.traceln(Level.FINER, "all threads finished, mergin results");
+
+ for (ComparisonRunnable runnable : runnables) {
+ Console.println("\n similarity statistics of comparison between " + runnable.model1 +
+ " and " + runnable.model2);
+ runnable.getStatistics().dump();
+ statistics.mergeWith(runnable.getStatistics());
+ }
+ }
+
+ /**
+ *
+ */
+ private static class SimilarityStatistics {
+
+ /** */
+ private int taskCounter = 0;
+
+ /** */
+ private int maxCoverage = 0;
+
+ /** */
+ private Map coverageCounters = new HashMap<>();
+
+ /** */
+ private Map>> equalityCounters =
+ new HashMap<>();
+
+ /**
+ *
+ */
+ private void store(ITask task,
+ ITaskModel model,
+ ITask other,
+ ITaskModel otherModel,
+ TaskEquality equality)
+ {
+ int coverageRatio1 =
+ model.getTaskInfo(task).getMeasureValue(TaskMetric.EVENT_COVERAGE);
+ int coverageRatio2 =
+ otherModel.getTaskInfo(other).getMeasureValue(TaskMetric.EVENT_COVERAGE);
+
+ addToMaps(coverageRatio1, 1);
+ addToMaps(coverageRatio1, coverageRatio2, equality, 1);
+ taskCounter++;
+ maxCoverage = Math.max(maxCoverage, coverageRatio1);
+ }
+
+ /**
+ *
+ */
+ private void store(ITask task, ITaskModel model) {
+ int coverageRatio1 =
+ model.getTaskInfo(task).getMeasureValue(TaskMetric.EVENT_COVERAGE);
+
+ addToMaps(coverageRatio1, 1);
+ addToMaps(coverageRatio1, 0, TaskEquality.UNEQUAL, 1);
+ taskCounter++;
+ maxCoverage = Math.max(maxCoverage, coverageRatio1);
+ }
+
+ /**
+ *
+ */
+ private void mergeWith(SimilarityStatistics statistics) {
+ for (Map.Entry>> entry1 :
+ statistics.equalityCounters.entrySet())
+ {
+ for (Map.Entry> entry2 :
+ entry1.getValue().entrySet())
+ {
+ for (Map.Entry entry3 : entry2.getValue().entrySet()) {
+ addToMaps
+ (entry1.getKey(), entry2.getKey(), entry3.getKey(), entry3.getValue());
+ }
+ }
+ }
+
+ for (Map.Entry entry : statistics.coverageCounters.entrySet()) {
+ addToMaps(entry.getKey(), entry.getValue());
+ }
+
+ taskCounter += statistics.taskCounter;
+ maxCoverage = Math.max(maxCoverage, statistics.taskCounter);
+ }
+
+ /**
+ *
+ */
+ private void addToMaps(int ratio, int increment) {
+ Integer counter = coverageCounters.get(ratio);
+
+ if (counter == null) {
+ coverageCounters.put(ratio, increment);
+ }
+ else {
+ coverageCounters.put(ratio, counter + increment);
+ }
+ }
+
+ /**
+ *
+ */
+ private void addToMaps(Integer ratio1, Integer ratio2, TaskEquality equality, int value) {
+ Map> counters1 = equalityCounters.get(ratio1);
+
+ if (counters1 == null) {
+ counters1 = new HashMap<>();
+ equalityCounters.put(ratio1, counters1);
+ }
+
+ Map counters2 = counters1.get(ratio2);
+
+ if (counters2 == null) {
+ counters2 = new HashMap<>();
+ counters1.put(ratio2, counters2);
+ }
+
+ Integer counter = counters2.get(equality);
+
+ if (counter == null) {
+ counters2.put(equality, value);
+ }
+ else {
+ counters2.put(equality, counter + value);
+ }
+ }
+
+ /**
+ *
+ */
+ private void dump() {
+ Console.println("Statistics of Similarity");
+ Console.println("========================");
+
+ int[][] bins = getBinsOfAlmostEqualSize();
+ int lowerBorder1;
+ int higherBorder1;
+ int lowerBorder2;
+ int higherBorder2;
+ int allEqualitiesOfBin = 0;
+ int allEqualities = 0;
+
+ for (int i = bins.length - 1; i >= 0 ; i--) {
+ if (i <= 0) {
+ lowerBorder1 = 0;
+ }
+ else {
+ lowerBorder1 = bins[i - 1][0] + 1;
+ }
+
+ higherBorder1 = bins[i][0];
+
+ allEqualitiesOfBin = 0;
+
+ Console.println("similarities of " + bins[i][1] + " tasks with " + lowerBorder1 +
+ " to " + higherBorder1 + "‰ coverage");
+
+ for (int j = bins.length - 1; j >= 0; j--) {
+ if (j <= 0) {
+ lowerBorder2 = 0;
+ }
+ else {
+ lowerBorder2 = bins[j - 1][0] + 1;
+ }
+
+ higherBorder2 = bins[j][0];
+
+ Console.print(" --> to " + bins[j][1] + " tasks with " + lowerBorder2 +
+ " to " + higherBorder2 + "‰ coverage");
+
+ Console.print(" | ");
+ int allInBin = countAllInBin(lowerBorder1, higherBorder1);
+
+ int count1 = countEqualities(lowerBorder1, higherBorder1, lowerBorder2,
+ higherBorder2, TaskEquality.LEXICALLY_EQUAL);
+
+ dump(count1, allInBin, "LEX");
+ Console.print("\t| ");
+
+ int count2 = countEqualities(lowerBorder1, higherBorder1, lowerBorder2,
+ higherBorder2, TaskEquality.SYNTACTICALLY_EQUAL);
+
+ dump(count2, allInBin, "SYN");
+ Console.print("\t| ");
+
+ int count3 = countEqualities(lowerBorder1, higherBorder1, lowerBorder2,
+ higherBorder2, TaskEquality.SEMANTICALLY_EQUAL);
+
+ dump(count3, allInBin, "SEM");
+ Console.print("\t|| ");
+
+ int count4 = countEqualities(lowerBorder1, higherBorder1, lowerBorder2,
+ higherBorder2, null);
+
+ dump(count4, allInBin, "SIM");
+ Console.print("\t|| ");
+
+ dump(count1 + count2 + count3 + count4, allInBin, "ALL");
+ Console.println("");
+
+ allEqualitiesOfBin += count1 + count2 + count3 + count4;
+ }
+
+ Console.print(" --> to all other tasks\t");
+ dump(allEqualitiesOfBin, taskCounter, "ALL");
+ Console.println("");
+
+ allEqualities += allEqualitiesOfBin;
+ }
+
+ Console.println("");
+ Console.print("complete recall is ");
+ dump(allEqualities, taskCounter, "ALL");
+ Console.println("");
+ }
+
+ /**
+ *
+ */
+ private int[][] getBinsOfAlmostEqualSize() {
+ int[][] result = new int[5][];
+
+ for (int i = 0; i < result.length; i++) {
+ result[i] = new int[2];
+ }
+
+ int averageBinSize = taskCounter / result.length;
+ int aimedBinSize = averageBinSize;
+
+ int index = 0;
+
+ for (int i = 0; i < maxCoverage; i++) {
+ if (result[index][1] > aimedBinSize) {
+ // try to compensate, if the previous bin was a little too large
+ aimedBinSize = averageBinSize + averageBinSize - result[index][1];
+ index++;
+ }
+
+ Integer value = coverageCounters.get(i);
+
+ if (value != null) {
+ result[index][0] = i;
+ result[index][1] += value;
+ }
+ }
+
+ return result;
+ }
+
+ /**
+ *
+ */
+ private void dump(int noOfEqualTasks, int noOfAllTasks, String prefix) {
+ Console.print(prefix);
+ Console.print("\t: ");
+
+ if (noOfAllTasks > 0) {
+ double value = ((double) (noOfEqualTasks * 100)) / noOfAllTasks;
+ Console.print(noOfEqualTasks + " (");
+ Console.print(new DecimalFormat("###.#").format(value));
+ Console.print("%)");
+ }
+ else {
+ Console.print("n.a.");
+ }
+ }
+
+ /**
+ *
+ */
+ private int countEqualities(int lowerBorder1,
+ int higherBorder1,
+ int lowerBorder2,
+ int higherBorder2,
+ TaskEquality equality)
+ {
+ int counter = 0;
+
+ for (int i = lowerBorder1; i <= higherBorder1; i++) {
+ Map> counters1 = equalityCounters.get(i);
+
+ if (counters1 != null) {
+ for (int j = lowerBorder2; j <= higherBorder2; j++) {
+ Map counters2 = counters1.get(j);
+
+ if (counters2 != null) {
+ Integer counterObj = counters2.get(equality);
+
+ if (counterObj != null) {
+ counter += counterObj;
+ }
+ }
+ }
+ }
+ }
+
+ return counter;
+ }
+
+ /**
+ *
+ */
+ private int countAllInBin(int lowerBorder1, int higherBorder1) {
+ int coverageCounter = 0;
+
+ for (int i = lowerBorder1; i <= higherBorder1; i++) {
+ Integer value = coverageCounters.get(i);
+
+ if (value != null) {
+ coverageCounter += value;
+ }
+ }
+
+ return coverageCounter;
+ }
+ }
+
+ /**
+ *
+ */
+ private static class ComparisonRunnable implements Runnable {
+
+ /** */
+ private ITaskModel model1;
+
+ /** */
+ private ITaskModel model2;
+
+ /** */
+ private List tasks1;
+
+ /** */
+ private List tasks2;
+
+ /** */
+ private Map>> lengthIndex1;
+
+ /** */
+ private Map lengthIndex2;
+
+ /** */
+ private Map firstTargetIndex;
+
+ /** */
+ private Object semaphore;
+
+ /** */
+ private SimilarityStatistics statistics = new SimilarityStatistics();
+
+ /**
+ *
+ */
+ private ComparisonRunnable(ITaskModel model1,
+ List tasks1,
+ ITaskModel model2,
+ List tasks2,
+ Map>> lengthIndex1,
+ Map lengthIndex2,
+ Map firstTargetIndex,
+ Object semaphore)
+ {
+ this.model1 = model1;
+ this.tasks1 = tasks1;
+ this.model2 = model2;
+ this.tasks2 = tasks2;
+ this.lengthIndex1 = lengthIndex1;
+ this.lengthIndex2 = lengthIndex2;
+ this.firstTargetIndex = firstTargetIndex;
+ this.semaphore = semaphore;
+ }
+
+ /* (non-Javadoc)
+ * @see java.lang.Runnable#run()
+ */
+ @Override
+ public void run() {
+ TaskEqualityRuleManager equalityRuleManager = TaskEqualityRuleManager.getInstance();
+ TaskComparator comparator = new TaskComparator(TaskEquality.SEMANTICALLY_EQUAL);
+ TaskEquality mostCommonEquality;
+ ITask mostSimilarTask;
+ TaskEquality equality;
+ SimilarTasks similarity;
+
+ List tasksToCompareWith = new ArrayList();
+ StopWatch watch = new StopWatch();
+ watch.start("all comparisons ");
+ int count = 0;
+ for (ISequence task : tasks1) {
+ int length = lengthIndex2.get(task);
+ IEventTarget firstTarget = firstTargetIndex.get(task);
+ tasksToCompareWith.clear();
+
+ // add tasks with same length
+ Map> eventTaskMap = lengthIndex1.get(length);
+ List toCompare;
+
+ if (eventTaskMap != null) {
+ toCompare = eventTaskMap.get(firstTarget);
+
+ if (toCompare != null) {
+ tasksToCompareWith.addAll(toCompare);
+ }
+ }
+
+ // add tasks containing selections
+ eventTaskMap = lengthIndex1.get(-1);
+
+ if (eventTaskMap != null) {
+ toCompare = eventTaskMap.get(firstTarget);
+
+ if (toCompare != null) {
+ tasksToCompareWith.addAll(toCompare);
+ }
+ }
+
+ mostCommonEquality = null;
+ mostSimilarTask = null;
+
+ for (ITask taskToCompare : tasksToCompareWith) {
+ count++;
+ watch.start("normal comparison");
+ equality = equalityRuleManager.compare(task, taskToCompare);
+ watch.stop("normal comparison");
+
+ if ((equality != TaskEquality.UNEQUAL) &&
+ ((mostCommonEquality == null) || (equality.isAtLeast(mostCommonEquality))))
+ {
+ // >>>>>>>>>>>>>>>>>>>>>> TEST IMPLEMENTATION >>>>>>>>>>>>>>>>>>>>>>>>>>>
+ // synchronized (System.out) {
+ // System.out.println("found equal tasks: " + equality);
+ // new TaskTreeEncoder().encode(task, System.out);
+ // new TaskTreeEncoder().encode(taskToCompare, System.out);
+ // }
+ // <<<<<<<<<<<<<<<<<<<<<< TEST IMPLEMENTATION <<<<<<<<<<<<<<<<<<<<<<<<<<<
+
+ mostCommonEquality = equality;
+ mostSimilarTask = taskToCompare;
+
+ if (mostCommonEquality.isAtLeast(TaskEquality.LEXICALLY_EQUAL)) {
+ // we found a lexically equal match, the most concrete that
+ // we can find. We can break up here
+ break;
+ }
+ }
+ }
+
+ if (mostCommonEquality != null) {
+ statistics.store(task, model1, mostSimilarTask, model2, mostCommonEquality);
+ }
+ else {
+ int lowestDiffLevel = Integer.MAX_VALUE;
+ for (ITask taskToCompare : tasksToCompareWith) {
+ count++;
+ watch.start("similarity comparison");
+ similarity = SimilarTasks.compareTasks(task, taskToCompare, comparator);
+ watch.stop("similarity comparison");
+
+ if (similarity.getDiffLevel() < lowestDiffLevel) {
+ lowestDiffLevel = similarity.getDiffLevel();
+ mostSimilarTask = taskToCompare;
+
+ if (lowestDiffLevel <= 0) {
+ // >>>>>>>>>>>>>>>>>>>>>> TEST IMPLEMENTATION >>>>>>>>>>>>>>>>>>>>>
+ // synchronized (System.out) {
+ // System.out.println("found similar tasks");
+ // similarity.dump(System.out);
+ // }
+ // <<<<<<<<<<<<<<<<<<<<<< TEST IMPLEMENTATION <<<<<<<<<<<<<<<<<<<<<
+
+ // we found a fully similar task. We will not find any more
+ // similar, hence we break
+ break;
+ }
+ }
+ }
+
+ if (lowestDiffLevel <= 0) {
+ statistics.store(task, model1, mostSimilarTask, model2, null);
+ }
+ else {
+ statistics.store(task, model1);
+ }
+ }
+ }
+
+ System.out.println("performed " + count + " comparisons");
+
+ watch.stop("all comparisons ");
+ watch.dumpStatistics(System.out);
+
+ synchronized (semaphore) {
+ semaphore.notify();
+ }
+ }
+
+ /**
+ * @return the statistics
+ */
+ private SimilarityStatistics getStatistics() {
+ return statistics;
+ }
+
+ }
+}
Index: /trunk/autoquest-ui-core/src/main/resources/manuals/getTaskModelSimilarity
===================================================================
--- /trunk/autoquest-ui-core/src/main/resources/manuals/getTaskModelSimilarity (revision 1895)
+++ /trunk/autoquest-ui-core/src/main/resources/manuals/getTaskModelSimilarity (revision 1895)
@@ -0,0 +1,8 @@
+compares a set of task models with each other and drops their similarity as results
+
+$USAGE$
+ the names of the task models to be compared
+
+Example(s):
+getTaskModelSimilarity taskTree1 taskTree2
+getTaskModelSimilarity taskTree1 taskTree2 taskTree3 taskTree4 taskTree5