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 1980) +++ trunk/autoquest-core-tasktrees/src/main/java/de/ugoe/cs/autoquest/tasktrees/temporalrelation/utils/MostSimilarTaskDeterminer.java (revision 1981) @@ -15,4 +15,7 @@ package de.ugoe.cs.autoquest.tasktrees.temporalrelation.utils; +import java.util.ArrayList; +import java.util.Collections; +import java.util.Comparator; import java.util.HashMap; import java.util.HashSet; @@ -58,8 +61,8 @@ /** - * 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; + * If this similarity level is exceeded, two tasks are not considered similar anymore. 25 means + * that at most 25% of the elements of both task traversals are not the same. + */ + private static int MAX_DIFF_LEVEL = 25; /** @@ -144,5 +147,6 @@ } - Console.println("smallest diff level is " + smallestDiffLevel); + Console.println("smallest diff level is " + smallestDiffLevel + " (max is " + + MAX_DIFF_LEVEL + ")"); } else { @@ -200,59 +204,73 @@ */ private void applyFilterForMostCoveredEvents(LinkedList mostSimilarTasksList, - ITaskModel taskModel) + final ITaskModel taskModel) { - for (SimilarTasks similarTasks : mostSimilarTasksList) { - System.out.println(similarTasks.getLeftHandSide() + " " + similarTasks.getRightHandSide()); - } - - // 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(); - - Console.traceln(Level.FINEST, "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; + List sortedList = new ArrayList<>(mostSimilarTasksList); + + // sort the list of similar tasks based on which to merge first + Collections.sort(sortedList, new Comparator() { + @Override + public int compare(SimilarTasks first, SimilarTasks second) { + SimilarTasks toMergeFirst = getFirstToMerge(first, second, taskModel); + + if (toMergeFirst == first) { + return -1; + } + else if (toMergeFirst == null) { + return 0; + } + else { + return 1; + } + } + }); + + // the first in the ordered list is the first to merge, except there are several + // firsts in the lists for which it can not be decided which to merge first + + // now remove all subsequent pairs also referring tasks referred by first pairs + Set referredTasks = new HashSet<>(); + + int index = 0; + while (index < sortedList.size()) { + SimilarTasks pair = sortedList.get(index); + + if (referredTasks.contains(pair.getLeftHandSide()) || + referredTasks.contains(pair.getRightHandSide())) + { + // we found a pair that refers to a task already referred by a preceding pair. + // The pair can be removed, if the previous pair referring to the same task also + // is to be merged first. + for (int i = 0; i < index; i++) { + SimilarTasks previousPair = sortedList.get(i); + if ((previousPair.getLeftHandSide() == pair.getLeftHandSide()) || + (previousPair.getLeftHandSide() == pair.getRightHandSide()) || + (previousPair.getRightHandSide() == pair.getLeftHandSide()) || + (previousPair.getRightHandSide() == pair.getRightHandSide())) + { + if (getFirstToMerge(previousPair, pair, taskModel) == null) { + for (SimilarTasks tmp : sortedList) { + tmp.dump(System.out); + } + + throw new RuntimeException("several tasks are similar so that it is " + + "undecidable which to merge first"); + } } - else if (firstToMerge != current) { - firstToMerge = getFirstToMerge(firstToMerge, current, taskModel); - } - } - } - - if (firstToMerge != null) { - mostSimilarTasksList.add(firstToMerge); - } - } - + } + + sortedList.remove(index); + } + else { + referredTasks.add(pair.getLeftHandSide()); + referredTasks.add(pair.getRightHandSide()); + index++; + } + } + + // now the list is sorted and contains at most one pair for each task referred multiple + // times + mostSimilarTasksList.clear(); + mostSimilarTasksList.addAll(sortedList); } @@ -327,29 +345,33 @@ 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); - } - + + // it may be the case that both tasks are event identical. For example, if through a + // merge formerly different children became the same. In this case, merging can be + // done in any order. Hence, just return any of the given to be merged first. To ensure + // to not define a circle of three tasks to be merged, decide using the ids of the + // identical tasks. + if ((first.getDiffLevel() == 0) && (second.getDiffLevel() == 0)) { + ITask taskWithSmallestId = first.getLeftHandSide(); + SimilarTasks pairToReturn = first; + + if (taskWithSmallestId.getId() > first.getRightHandSide().getId()) { + taskWithSmallestId = first.getRightHandSide(); + } + + if (taskWithSmallestId.getId() > second.getLeftHandSide().getId()) { + taskWithSmallestId = second.getLeftHandSide(); + pairToReturn = second; + } + + if (taskWithSmallestId.getId() > second.getRightHandSide().getId()) { + taskWithSmallestId = second.getRightHandSide(); + pairToReturn = second; + } + + return pairToReturn; + } + + return null; + } /** @@ -357,4 +379,5 @@ */ private LinkedList performComparisons(ITaskModel taskModel, List tasks) { + Set mostProminentTasks = getMostProminentTasks(taskModel, tasks); LinkedList mostSimilarTasks = new LinkedList(); List startedRunnables = new LinkedList(); @@ -412,4 +435,5 @@ Runnable runnable = new CompareRunnable(taskModel, leftHandTraversals, rightHandTraversals, + mostProminentTasks, mostSimilarTasks, startedRunnables); @@ -468,4 +492,44 @@ /** + * + */ + private Set getMostProminentTasks(ITaskModel model, List tasks) { + Map> sortedTasks = new HashMap<>(); + + int maxCoverage = 0; + + for (ITask task : tasks) { + int coveredEvents = model.getTaskInfo(task).getMeasureValue(TaskMetric.EVENT_COVERAGE); + + List tasksWithSameCoverage = sortedTasks.get(coveredEvents); + + if (tasksWithSameCoverage == null) { + tasksWithSameCoverage = new LinkedList<>(); + sortedTasks.put(coveredEvents, tasksWithSameCoverage); + } + + tasksWithSameCoverage.add(task); + + maxCoverage = Math.max(maxCoverage, coveredEvents); + } + + Set result = new HashSet<>(); + + for (int i = maxCoverage; i > 0; i--) { + List tasksWithSameCoverage = sortedTasks.get(i); + + if (tasksWithSameCoverage != null) { + result.addAll(tasksWithSameCoverage); + + if (result.size() * 5 >= tasks.size()) { + break; + } + } + } + + return result; + } + + /** * convenience method to get the value of a task metric */ @@ -539,4 +603,7 @@ /** */ + private Set mostProminentTasks; + + /** */ private List mostSimilarTasksList; @@ -550,4 +617,5 @@ TaskTraversal[] leftHandTraversals, TaskTraversal[] rightHandTraversals, + Set mostProminentTasks, List mostSimilarTasksList, List unfinishedRunnables) @@ -556,4 +624,5 @@ this.leftHandTraversals = leftHandTraversals; this.rightHandTraversals = rightHandTraversals; + this.mostProminentTasks = mostProminentTasks; this.mostSimilarTasksList = mostSimilarTasksList; this.unfinishedRunnables = unfinishedRunnables; @@ -585,5 +654,5 @@ continue LEFT_HAND_TRAVERSAL; } - + counter++; @@ -598,28 +667,40 @@ effectiveComparisons++; - SimilarTasks similarTasks1 = SimilarTasks.compareTraversals + SimilarTasks similarTasks = SimilarTasks.compareTraversals (leftHandTraversals[i], rightHandTraversals[j], comparator); - SimilarTasks similarTasks2 = SimilarTasks.compareTraversals - (rightHandTraversals[j], leftHandTraversals[i], comparator); - - if ((similarTasks1.getDiffLevel() <= mostSimilarDiffLevel) || - (similarTasks2.getDiffLevel() <= mostSimilarDiffLevel)) + if (similarTasks.getDiffLevel() > 0) { + if (!mostProminentTasks.contains(leftHandTask) || + !mostProminentTasks.contains(rightHandTask)) + { + // the tasks are not fully identical. Hence, we merge them only, + // if both are most prominent ones. If they were fully identical, + // they may have changed through merging initially different + // children which may have become the same. In that case, they + // must be merged even if they are not most prominent. + continue RIGHT_HAND_TRAVERSAL; + } + + SimilarTasks similarTasks2 = SimilarTasks.compareTraversals + (rightHandTraversals[j], leftHandTraversals[i], comparator); + + if ((similarTasks.getDiffLevel() <= mostSimilarDiffLevel) || + (similarTasks2.getDiffLevel() <= mostSimilarDiffLevel)) { + + similarTasks = getSimilarTasksToPrefer(similarTasks, similarTasks2); + } + } + + if (similarTasks.isInBetweenDifference() || + (similarTasks.getPatch().getDeltas().size() == 0)) { - SimilarTasks similarTasks = - getSimilarTasksToPrefer(similarTasks1, similarTasks2); - - if (similarTasks.isInBetweenDifference() || - (similarTasks.getPatch().getDeltas().size() == 0)) - { - if (similarTasks.getDiffLevel() < mostSimilarDiffLevel) { - mostSimilarTasks = similarTasks; - mostSimilarDiffLevel = mostSimilarTasks.getDiffLevel(); - allMostSimilarTasks.clear(); - allMostSimilarTasks.add(similarTasks); - } - else if (similarTasks.getDiffLevel() == mostSimilarDiffLevel) { - allMostSimilarTasks.add(similarTasks); - } + if (similarTasks.getDiffLevel() < mostSimilarDiffLevel) { + mostSimilarTasks = similarTasks; + mostSimilarDiffLevel = mostSimilarTasks.getDiffLevel(); + allMostSimilarTasks.clear(); + allMostSimilarTasks.add(similarTasks); + } + else if (similarTasks.getDiffLevel() == mostSimilarDiffLevel) { + allMostSimilarTasks.add(similarTasks); } }