// 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;
}
}
}