Changeset 1933

Timestamp:

03/27/15 13:26:18 (10 years ago)

Author:

pharms

Message:

• extension for detecting identical tasks, too

File:

• trunk/autoquest-ui-core/src/main/java/de/ugoe/cs/autoquest/commands/usability/CMDgetTaskModelSimilarity.java (modified) (23 diffs)

trunk/autoquest-ui-core/src/main/java/de/ugoe/cs/autoquest/commands/usability/CMDgetTaskModelSimilarity.java

@@ -31 +31 @@
 import de.ugoe.cs.autoquest.tasktrees.temporalrelation.TaskComparator;
 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.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.IOptional;
 import de.ugoe.cs.autoquest.tasktrees.treeifc.ISelection;
 import de.ugoe.cs.autoquest.tasktrees.treeifc.ISequence;
@@ -125 +128 @@
             new IdentityHashMap<>();
         
-        Map<ISequence, Integer> index2 = new HashMap<>();
-        Map<ISequence, IEventTarget> index3 = new HashMap<>();
+        Map<ISequence, Integer> lengthIndex = new HashMap<>();
+        Map<ISequence, IEventTarget> firstTargetIndex = new HashMap<>();
+        Map<ISequence, TaskTraversal> taskTraversalIndex = new HashMap<>();
         
         final List<IEventTask> terminalNodes = new ArrayList<>();
@@ -181 +185 @@
                 
                 compareList.add(sequence);
-                index2.put(sequence, length);
-                index3.put(sequence, firstTarget);
+                lengthIndex.put(sequence, length);
+                firstTargetIndex.put(sequence, firstTarget);
+                taskTraversalIndex.put(sequence, TaskTraversal.getTraversal(sequence, null));
             }
         }
@@ -196 +201 @@
                                                      Collections.unmodifiableMap
                                                          (index1.get(model2.getKey())),
-                                                     Collections.unmodifiableMap(index2),
-                                                     Collections.unmodifiableMap(index3),
+                                                     Collections.unmodifiableMap(lengthIndex),
+                                                     Collections.unmodifiableMap(firstTargetIndex),
+                                                     Collections.unmodifiableMap(taskTraversalIndex),
                                                      runnables));
             }
@@ -395 +401 @@
             int lowerBorder2;
             int higherBorder2;
+            int identicalEqualitiesOfBin = 0;
             int lexicalEqualitiesOfBin = 0;
             int syntacticalEqualitiesOfBin = 0;
@@ -410 +417 @@
             csvData.append(taskCounter2);
             
-            for (int i = bins1.length - 1; i >= 0 ; i--) {
-                if (i <= 0) {
-                    lowerBorder1 = 0;
+            for (int i = 0; i < bins1.length; i++) {
+                if (i == 0) {
+                    higherBorder1 = maxCoverage1;
                 }
                 else {
-                    lowerBorder1 = bins1[i - 1][0] + 1;
-                }
-                
-                higherBorder1 = bins1[i][0];
-                
-                int allInBin1 = countAllInBin(lowerBorder1, higherBorder1);
+                    higherBorder1 = bins1[i - 1][0] - 1;
+                }
+                
+                lowerBorder1 = bins1[i][0];
+                int allInBin1 = bins1[i][1];
+
                 csvData.append(';');
                 csvData.append(allInBin1);
                 
+                identicalEqualitiesOfBin = 0;
                 lexicalEqualitiesOfBin = 0;
                 syntacticalEqualitiesOfBin = 0;
@@ -431 +439 @@
                 outputs[outputIndex++] = new String[]
                         { "similarities of " + bins1[i][1] + " tasks with " + lowerBorder1 +
-                          " to " + higherBorder1 + " covered events", "LEX", "SYN", "SEM",
+                          " to " + higherBorder1 + " covered events", "IDENT", "LEX", "SYN", "SEM",
                           "ALL EQUAL", "SIM", "ALL" };
                 
-                for (int j = bins2.length - 1; j >= 0; j--) {
-                    if (j <= 0) {
-                        lowerBorder2 = 0;
+                for (int j = 0; j < bins2.length; j++) {
+                    if (j == 0) {
+                        higherBorder2 = maxCoverage2;
                     }
                     else {
-                        lowerBorder2 = bins2[j - 1][0] + 1;
-                    }
-                    
-                    higherBorder2 = bins2[j][0];
-                    
-                    int allInBin2 = countAllInBin(lowerBorder2, higherBorder2);
+                        higherBorder2 = bins2[j - 1][0] - 1;
+                    }
+                    
+                    lowerBorder2 = bins2[j][0];
+                    int allInBin2 = bins2[j][1];
+                    
                     csvData.append(';');
                     csvData.append(allInBin2);
 
                     int count1 = countEqualities(lowerBorder1, higherBorder1, lowerBorder2,
+                                                 higherBorder2, TaskEquality.IDENTICAL);
+
+                    int count2 = countEqualities(lowerBorder1, higherBorder1, lowerBorder2,
                                                  higherBorder2, TaskEquality.LEXICALLY_EQUAL);
 
-                    int count2 = countEqualities(lowerBorder1, higherBorder1, lowerBorder2,
+                    int count3 = countEqualities(lowerBorder1, higherBorder1, lowerBorder2,
                                                  higherBorder2, TaskEquality.SYNTACTICALLY_EQUAL);
 
-                    int count3 = countEqualities(lowerBorder1, higherBorder1, lowerBorder2,
+                    int count4 = countEqualities(lowerBorder1, higherBorder1, lowerBorder2,
                                                  higherBorder2, TaskEquality.SEMANTICALLY_EQUAL);
                     
-                    int count4 = countEqualities(lowerBorder1, higherBorder1, lowerBorder2,
+                    int count5 = countEqualities(lowerBorder1, higherBorder1, lowerBorder2,
                                                  higherBorder2, null);
                     
@@ -464 +475 @@
                               " to " + higherBorder2 + " covered events", format(count1, allInBin1),
                               format(count2, allInBin1), format(count3, allInBin1),
-                              format(count1 + count2 + count3, allInBin1), format(count4, allInBin1),
-                              format(count1 + count2 + count3 + count4, allInBin1)
+                              format(count4, allInBin1),
+                              format(count1 + count2 + count3 + count4, allInBin1),
+                              format(count5, allInBin1),
+                              format(count1 + count2 + count3 + count4 + count5, allInBin1)
                             };
                     
-                    lexicalEqualitiesOfBin += count1;
-                    syntacticalEqualitiesOfBin += count2;
-                    semanticalEqualitiesOfBin += count3;
-                    similaritiesOfBin += count4;
+                    identicalEqualitiesOfBin += count1;
+                    lexicalEqualitiesOfBin += count2;
+                    syntacticalEqualitiesOfBin += count3;
+                    semanticalEqualitiesOfBin += count4;
+                    similaritiesOfBin += count5;
 
                     csvData.append(';');
@@ -480 +494 @@
                     csvData.append(percentFormat.format((double) count3 / allInBin1));
                     csvData.append(';');
-                    csvData.append(percentFormat.format
-                                       ((double) (count1 + count2 + count3) / allInBin1));
-                    csvData.append(';');
                     csvData.append(percentFormat.format((double) count4 / allInBin1));
                     csvData.append(';');
                     csvData.append(percentFormat.format
                                        ((double) (count1 + count2 + count3 + count4) / allInBin1));
+                    csvData.append(';');
+                    csvData.append(percentFormat.format((double) count5 / allInBin1));
+                    csvData.append(';');
+                    csvData.append(percentFormat.format
+                                       ((double) (count1 + count2 + count3 + count4 + count5) / allInBin1));
                 }
                 
                 outputs[outputIndex++] = new String[]
-                        { "--> all recalls", format(lexicalEqualitiesOfBin, allInBin1),
+                        { "--> all recalls", format(identicalEqualitiesOfBin, allInBin1),
+                          format(lexicalEqualitiesOfBin, allInBin1),
                           format(syntacticalEqualitiesOfBin, allInBin1),
                           format(semanticalEqualitiesOfBin, allInBin1),
-                          format(lexicalEqualitiesOfBin + syntacticalEqualitiesOfBin +
-                                 semanticalEqualitiesOfBin, allInBin1),
+                          format(identicalEqualitiesOfBin + lexicalEqualitiesOfBin +
+                                 syntacticalEqualitiesOfBin + semanticalEqualitiesOfBin, allInBin1),
                           format(similaritiesOfBin, allInBin1),
-                          format(lexicalEqualitiesOfBin + syntacticalEqualitiesOfBin +
-                                 semanticalEqualitiesOfBin + similaritiesOfBin, allInBin1)
+                          format(identicalEqualitiesOfBin + lexicalEqualitiesOfBin +
+                                 syntacticalEqualitiesOfBin + semanticalEqualitiesOfBin +
+                                 similaritiesOfBin, allInBin1)
                         };
                 
 
+                csvData.append(';');
+                csvData.append(percentFormat.format((double) identicalEqualitiesOfBin / allInBin1));
                 csvData.append(';');
                 csvData.append(percentFormat.format((double) lexicalEqualitiesOfBin / allInBin1));
@@ -509 +529 @@
                 csvData.append(';');
                 csvData.append(percentFormat.format
-                                   ((double) (lexicalEqualitiesOfBin + syntacticalEqualitiesOfBin +
-                                              semanticalEqualitiesOfBin) / allInBin1));
+                                   ((double) (identicalEqualitiesOfBin + lexicalEqualitiesOfBin +
+                                              syntacticalEqualitiesOfBin + semanticalEqualitiesOfBin)
+                                              / allInBin1));
                 csvData.append(';');
                 csvData.append(percentFormat.format((double) similaritiesOfBin / allInBin1));
                 csvData.append(';');
                 csvData.append(percentFormat.format
-                                   ((double) (lexicalEqualitiesOfBin + syntacticalEqualitiesOfBin +
-                                              semanticalEqualitiesOfBin + similaritiesOfBin) /
-                                              allInBin1));
-                
-                allEqualities += lexicalEqualitiesOfBin + syntacticalEqualitiesOfBin +
-                    semanticalEqualitiesOfBin + similaritiesOfBin;
+                                   ((double) (identicalEqualitiesOfBin + lexicalEqualitiesOfBin +
+                                              syntacticalEqualitiesOfBin + semanticalEqualitiesOfBin +
+                                              similaritiesOfBin) / allInBin1));
+                
+                allEqualities += identicalEqualitiesOfBin + lexicalEqualitiesOfBin +
+                    syntacticalEqualitiesOfBin + semanticalEqualitiesOfBin + similaritiesOfBin;
                 
                 outputIndex++;
@@ -597 +618 @@
             
             int index = 0;
-            
-            for (int i = 0; i < maxCoverage; i++) {
+            int allCoverageCounterSum = 0;
+            
+            for (int i = maxCoverage; i > 0; i--) {
                 if (result[index][1] > aimedBinSize) {
-                    // try to compensate, if the previous bin was a little too large
-                    aimedBinSize = averageBinSize + averageBinSize - result[index][1];
+                    if ((index + 2) < result.length) {
+                        // try to compensate, if the previous bin was a little too large
+                        aimedBinSize = averageBinSize + averageBinSize - result[index][1];
+                    }
+                    else {
+                        // put all remaining in the last bin
+                        aimedBinSize = Integer.MAX_VALUE;
+                    }
                     index++;
                 }
@@ -610 +638 @@
                     result[index][0] = i;
                     result[index][1] += value;
-                }
+                    allCoverageCounterSum += value;
+                }
+            }
+            
+            if (taskCounter != allCoverageCounterSum) {
+                throw new RuntimeException("bins do not cover all tasks");
             }
             
@@ -666 +699 @@
             return counter;
         }
-
-        /**
-         *
-         */
-        private int countAllInBin(int lowerBorder, int higherBorder) {
-            int coverageCounter = 0;
-            
-            for (int i = lowerBorder; i <= higherBorder; i++) {
-                Integer value = coverageCounters1.get(i);
-                
-                if (value != null) {
-                    coverageCounter += value;
-                }
-            }
-            
-            return coverageCounter;
-        }
     }
 
@@ -710 +726 @@
         /** */
         private Map<ISequence, IEventTarget> firstTargetIndex;
+        
+        /** */
+        private Map<ISequence, TaskTraversal> traversalIndex;
 
         /** */
@@ -716 +735 @@
         /** */
         private SimilarityStatistics statistics = new SimilarityStatistics();
-        
+
+        /** */
+        private TaskEqualityRuleManager equalityRuleManager = TaskEqualityRuleManager.getInstance();
+
         /**
          * 
@@ -727 +749 @@
                                    Map<ISequence, Integer>                          lengthIndex2,
                                    Map<ISequence, IEventTarget>                     firstTargetIndex,
+                                   Map<ISequence, TaskTraversal>                    traversalIndex,
                                    Object                                           semaphore)
         {
@@ -736 +759 @@
             this.lengthIndex2 = lengthIndex2;
             this.firstTargetIndex = firstTargetIndex;
+            this.traversalIndex = traversalIndex;
             this.semaphore = semaphore;
         }
@@ -744 +768 @@
         @Override
         public void run() {
-            TaskEqualityRuleManager equalityRuleManager = TaskEqualityRuleManager.getInstance();
             TaskComparator comparator = new TaskComparator(TaskEquality.SEMANTICALLY_EQUAL);
             TaskEquality mostCommonEquality;
-            ITask mostSimilarTask;
+            ISequence mostSimilarTask;
             TaskEquality equality;
             SimilarTasks similarity;
@@ -764 +787 @@
             watch.start("all comparisons ");
             int count = 0;
+            int taskNo = 0;
+            int nextPercent = 10;
             for (ISequence task : tasks1) {
                 int length = lengthIndex2.get(task);
@@ -795 +820 @@
                 mostSimilarTask = null;
                 
-                for (ITask taskToCompare : tasksToCompareWith) {
+                for (ISequence taskToCompare : tasksToCompareWith) {
                     count++;
                     watch.start("normal comparison");
@@ -824 +849 @@
                 
                 if (mostCommonEquality != null) {
-                    statistics.store(task, model1, mostSimilarTask, model2, mostCommonEquality);
+                    // check, if both tasks are identical
+                    if (!identicalTasks(task, mostSimilarTask)) {
+                        statistics.store(task, model1, mostSimilarTask, model2, mostCommonEquality);
+                    }
+                    else {
+                        statistics.store
+                            (task, model1, mostSimilarTask, model2, TaskEquality.IDENTICAL);
+                    }
                 }
                 else {
                     int lowestDiffLevel = Integer.MAX_VALUE;
-                    for (ITask taskToCompare : tasksToCompareWith) {
+                    TaskTraversal traversal1 = traversalIndex.get(task);
+                    
+                    for (ISequence taskToCompare : tasksToCompareWith) {
                         count++;
                         watch.start("similarity comparison");
-                        similarity = SimilarTasks.compareTasks(task, taskToCompare, comparator);
+                        TaskTraversal traversal2 = traversalIndex.get(taskToCompare);
+                        similarity =
+                            SimilarTasks.compareTraversals(traversal1, traversal2, comparator);
                         watch.stop("similarity comparison");
                         
@@ -860 +896 @@
                     }
                 }
-            }
-            
-            System.out.println("performed " + count + " comparisons");
+                
+                taskNo++;
+                
+                if (((taskNo * 100) / tasks1.size()) > nextPercent) {
+                    System.out.println("compared " + nextPercent + "% (" + taskNo + " tasks) of " +
+                                       model1 + " with " + tasks2.size() + " tasks of " + model2);
+                    nextPercent += 10;
+                }
+            }
+            
+            System.out.println("performed " + count + " comparisons for comparing " + model1 +
+                               " with " + model2);
             
             watch.stop("all comparisons ");
@@ -873 +918 @@
 
         /**
+         *
+         */
+        private boolean identicalTasks(ISequence sequence1, ISequence sequence2) {
+            if (sequence1.getChildren().size() != sequence2.getChildren().size()) {
+                return false;
+            }
+            
+            for (int i = 0; i < sequence1.getChildren().size(); i++) {
+                if (!identicalTasks(sequence1.getChildren().get(i), sequence2.getChildren().get(i)))
+                {
+                    return false;
+                }
+            }
+            
+            return true;
+        }
+
+        /**
+         *
+         */
+        private boolean identicalTasks(IIteration iteration1, IIteration iteration2) {
+            return identicalTasks(iteration1.getMarkedTask(), iteration2.getMarkedTask());
+        }
+
+        /**
+         *
+         */
+        private boolean identicalTasks(IOptional optional1, IOptional optional2) {
+            return identicalTasks(optional1.getMarkedTask(), optional2.getMarkedTask());
+        }
+
+        /**
+         *
+         */
+        private boolean identicalTasks(ISelection selection1, ISelection selection2) {
+            if (selection1.getChildren().size() != selection2.getChildren().size()) {
+                return false;
+            }
+            
+            FIRST_SELECTION_CHILDREN:
+            for (ITask child1 : selection1.getChildren()) {
+                for (ITask child2 : selection2.getChildren()) {
+                    if (identicalTasks(child1, child2)) {
+                        continue FIRST_SELECTION_CHILDREN;
+                    }
+                }
+                
+                return false;
+            }
+            
+            return true;
+        }
+
+        /**
+         *
+         */
+        private boolean identicalTasks(IEventTask eventTask1, IEventTask eventTask2) {
+            return equalityRuleManager.compare(eventTask1, eventTask2).isAtLeast
+                (TaskEquality.SEMANTICALLY_EQUAL);
+        }
+        
+        /**
+         *
+         */
+        private boolean identicalTasks(ITask task1, ITask task2) {
+            if ((task1 instanceof ISequence) && (task2 instanceof ISequence)) {
+                return identicalTasks((ISequence) task1, (ISequence) task2);
+            }
+            else if ((task1 instanceof IIteration) && (task2 instanceof IIteration)) {
+                return identicalTasks((IIteration) task1, (IIteration) task2);
+            }
+            else if ((task1 instanceof IOptional) && (task2 instanceof IOptional)) {
+                return identicalTasks((IOptional) task1, (IOptional) task2);
+            }
+            else if ((task1 instanceof ISelection) && (task2 instanceof ISelection)) {
+                return identicalTasks((ISelection) task1, (ISelection) task2);
+            }
+            else if ((task1 instanceof IEventTask) && (task2 instanceof IEventTask)) {
+                return identicalTasks((IEventTask) task1, (IEventTask) task2);
+            }
+            else {
+                return false;
+            }
+        }
+
+        /**
          * @return the statistics
          */