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

Last change on this file since 1933 was 1933, checked in by pharms, 9 years ago
  • extension for detecting identical tasks, too
File size: 40.9 KB
Line 
1//   Copyright 2012 Georg-August-Universität Göttingen, Germany
2//
3//   Licensed under the Apache License, Version 2.0 (the "License");
4//   you may not use this file except in compliance with the License.
5//   You may obtain a copy of the License at
6//
7//       http://www.apache.org/licenses/LICENSE-2.0
8//
9//   Unless required by applicable law or agreed to in writing, software
10//   distributed under the License is distributed on an "AS IS" BASIS,
11//   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12//   See the License for the specific language governing permissions and
13//   limitations under the License.
14
15package de.ugoe.cs.autoquest.commands.usability;
16
17import java.text.DecimalFormat;
18import java.util.ArrayList;
19import java.util.Collections;
20import java.util.HashMap;
21import java.util.IdentityHashMap;
22import java.util.LinkedList;
23import java.util.List;
24import java.util.Map;
25import java.util.logging.Level;
26
27import de.ugoe.cs.autoquest.CommandHelpers;
28import de.ugoe.cs.autoquest.eventcore.IEventTarget;
29import de.ugoe.cs.autoquest.tasktrees.taskequality.TaskEquality;
30import de.ugoe.cs.autoquest.tasktrees.taskequality.TaskEqualityRuleManager;
31import de.ugoe.cs.autoquest.tasktrees.temporalrelation.TaskComparator;
32import de.ugoe.cs.autoquest.tasktrees.temporalrelation.utils.SimilarTasks;
33import de.ugoe.cs.autoquest.tasktrees.temporalrelation.utils.TaskTraversal;
34import de.ugoe.cs.autoquest.tasktrees.treeifc.DefaultTaskTraversingVisitor;
35import de.ugoe.cs.autoquest.tasktrees.treeifc.IEventTask;
36import de.ugoe.cs.autoquest.tasktrees.treeifc.IEventTaskInstance;
37import de.ugoe.cs.autoquest.tasktrees.treeifc.IIteration;
38import de.ugoe.cs.autoquest.tasktrees.treeifc.IOptional;
39import de.ugoe.cs.autoquest.tasktrees.treeifc.ISelection;
40import de.ugoe.cs.autoquest.tasktrees.treeifc.ISequence;
41import de.ugoe.cs.autoquest.tasktrees.treeifc.ITask;
42import de.ugoe.cs.autoquest.tasktrees.treeifc.ITaskModel;
43import de.ugoe.cs.autoquest.tasktrees.treeifc.TaskMetric;
44import de.ugoe.cs.util.StopWatch;
45import de.ugoe.cs.util.console.Command;
46import de.ugoe.cs.util.console.Console;
47import de.ugoe.cs.util.console.GlobalDataContainer;
48
49/**
50 * <p>
51 * compares a set of task models with each other and drops their similarity as results
52 * </p>
53 *
54 * @author Patrick Harms
55 * @version 1.0
56 */
57public class CMDgetTaskModelSimilarity implements Command {
58
59    /*
60     * (non-Javadoc)
61     *
62     * @see de.ugoe.cs.util.console.Command#help()
63     */
64    @Override
65    public String help() {
66        return "getTaskModelSimilarity <tasktree1> <tasktree2> ...";
67    }
68
69    /*
70     * (non-Javadoc)
71     *
72     * @see de.ugoe.cs.util.console.Command#run(java.util.List)
73     */
74    @Override
75    public void run(List<Object> parameters) {
76        List<String> inputTaskTreeNames = new LinkedList<>();
77       
78        try {
79            for (Object param : parameters) {
80                inputTaskTreeNames.add((String) param);
81            }
82        }
83        catch (Exception e) {
84            throw new IllegalArgumentException("must provide valid input task tree names");
85        }
86
87        Map<ITaskModel, List<ISequence>> inputTaskModels = new IdentityHashMap<>();
88       
89        ITaskModel firstModel = null;
90       
91        for (String inputTaskTreeName : inputTaskTreeNames) {
92            Object dataObject = GlobalDataContainer.getInstance().getData(inputTaskTreeName);
93            if (dataObject == null) {
94                CommandHelpers.objectNotFoundMessage(inputTaskTreeName);
95                return;
96            }
97            if (!(dataObject instanceof ITaskModel)) {
98                CommandHelpers.objectNotType(inputTaskTreeName, "ITaskModel");
99                return;
100            }
101           
102            List<ISequence> tasksToCompare = new LinkedList<>();
103           
104            for (ITask task : ((ITaskModel) dataObject).getTasks()) {
105                if (task instanceof ISequence) {
106                    tasksToCompare.add((ISequence) task);
107                }
108            }
109           
110            inputTaskModels.put((ITaskModel) dataObject, tasksToCompare);
111           
112            if (firstModel == null) {
113                firstModel = (ITaskModel) dataObject;
114            }
115        }
116       
117        getTaskModelSimilarity(firstModel, inputTaskModels);
118    }
119
120    /**
121     *
122     */
123    private void getTaskModelSimilarity(ITaskModel                       modelToCompare,
124                                        Map<ITaskModel, List<ISequence>> inputTaskModels)
125    {
126        // create the indexes to not do too many comparisons
127        Map<ITaskModel, Map<Integer, Map<IEventTarget, List<ISequence>>>> index1 =
128            new IdentityHashMap<>();
129       
130        Map<ISequence, Integer> lengthIndex = new HashMap<>();
131        Map<ISequence, IEventTarget> firstTargetIndex = new HashMap<>();
132        Map<ISequence, TaskTraversal> taskTraversalIndex = new HashMap<>();
133       
134        final List<IEventTask> terminalNodes = new ArrayList<>();
135        final List<ISelection> selections = new ArrayList<>();
136       
137        for (Map.Entry<ITaskModel, List<ISequence>> entry : inputTaskModels.entrySet()) {
138            for (ISequence sequence : entry.getValue()) {
139                terminalNodes.clear();
140                selections.clear();
141               
142                sequence.accept(new DefaultTaskTraversingVisitor() {
143                    @Override
144                    public void visit(IEventTask eventTask) {
145                        terminalNodes.add(eventTask);
146                    }
147                    @Override
148                    public void visit(ISelection selection) {
149                        selections.add(selection);
150                        // no need to traverse children as a sequences containing a selection
151                        // will be handled differently
152                    }
153                });
154               
155                int length = terminalNodes.size();
156                IEventTarget firstTarget = ((IEventTaskInstance) terminalNodes.get(0).getInstances()
157                    .iterator().next()).getEvent().getTarget();
158               
159                if (selections.size() > 0) {
160                    length = -1;
161                    firstTarget = null;
162                }
163
164                Map<Integer, Map<IEventTarget, List<ISequence>>> lengthMap =
165                    index1.get(entry.getKey());
166               
167                if (lengthMap == null) {
168                    lengthMap = new HashMap<>();
169                    index1.put(entry.getKey(), lengthMap);
170                }
171               
172                Map<IEventTarget, List<ISequence>> firstTaskMap = lengthMap.get(length);
173               
174                if (firstTaskMap == null) {
175                    firstTaskMap = new HashMap<>();
176                    lengthMap.put(length, firstTaskMap);
177                }
178               
179                List<ISequence> compareList = firstTaskMap.get(firstTarget);
180               
181                if (compareList == null) {
182                    compareList = new LinkedList<ISequence>();
183                    firstTaskMap.put(firstTarget, compareList);
184                }
185               
186                compareList.add(sequence);
187                lengthIndex.put(sequence, length);
188                firstTargetIndex.put(sequence, firstTarget);
189                taskTraversalIndex.put(sequence, TaskTraversal.getTraversal(sequence, null));
190            }
191        }
192       
193        // create the comparison runnables
194        List<ComparisonRunnable> runnables = new LinkedList<>();
195       
196        for (Map.Entry<ITaskModel, List<ISequence>> model2 : inputTaskModels.entrySet()) {
197            if (modelToCompare != model2.getKey()) {
198                runnables.add(new ComparisonRunnable(modelToCompare,
199                                                     inputTaskModels.get(modelToCompare),
200                                                     model2.getKey(), model2.getValue(),
201                                                     Collections.unmodifiableMap
202                                                         (index1.get(model2.getKey())),
203                                                     Collections.unmodifiableMap(lengthIndex),
204                                                     Collections.unmodifiableMap(firstTargetIndex),
205                                                     Collections.unmodifiableMap(taskTraversalIndex),
206                                                     runnables));
207            }
208        }
209       
210        // execute the threads
211        Console.traceln(Level.FINE, "scheduling " + runnables.size() + " comparison threads");
212       
213        synchronized (runnables) {
214            int startedRunnables = 0;
215            for (ComparisonRunnable runnable : runnables) {
216                while (startedRunnables >= Math.max(1, Runtime.getRuntime().availableProcessors()))
217                {
218                    try {
219                        Console.traceln(Level.FINER, "waiting for next thread to finish");
220                        runnables.wait();
221                        startedRunnables--;
222                        Console.traceln(Level.FINER, "thread finished");
223                    }
224                    catch (InterruptedException e) {
225                        // should not happen
226                        Console.logException(e);
227                    }
228                }
229           
230                Console.traceln(Level.FINER, "starting next thread");
231                startedRunnables++;
232                Console.traceln(Level.FINE, "comparing " + runnable.tasks1.size()
233                                + " tasks of model " + runnable.model1 + " with " +
234                                runnable.tasks2.size() + " tasks of model " + runnable.model2);
235             
236                new Thread(runnable).start();
237                Console.traceln(Level.FINER, "started next thread " + runnable);
238            }
239           
240            while (startedRunnables > 0) {
241                try {
242                    Console.traceln(Level.FINER, "waiting for next thread to finish");
243                    runnables.wait();
244                    startedRunnables--;
245                    Console.traceln(Level.FINER, "thread finished");
246                }
247                catch (InterruptedException e) {
248                    // should not happen
249                    Console.logException(e);
250                }
251            }
252        }
253
254        // merge the results
255        Console.traceln(Level.FINER, "all threads finished, mergin results");
256       
257        for (ComparisonRunnable runnable : runnables) {
258            Console.println("\nsimilarity statistics of comparison between " + runnable.model1 +
259                            " (" + runnable.tasks1.size() + " tasks) and " + runnable.model2 +
260                            " (" + runnable.tasks2.size() + " tasks)");
261            runnable.getStatistics().dump();
262        }
263    }
264
265    /**
266     *
267     */
268    private static class SimilarityStatistics {
269       
270        /**  */
271        private int taskCounter1 = 0;
272       
273        /** */
274        private int maxCoverage1 = 0;
275       
276        /** */
277        private ITaskModel model1 = null;
278       
279        /**  */
280        private Map<Integer, Integer> coverageCounters1 = new HashMap<>();
281       
282        /**  */
283        private int taskCounter2 = 0;
284       
285        /** */
286        private int maxCoverage2 = 0;
287       
288        /** */
289        private ITaskModel model2 = null;
290       
291        /**  */
292        private Map<Integer, Integer> coverageCounters2 = new HashMap<>();
293       
294        /**  */
295        private Map<Integer, Map<Integer, Map<TaskEquality, Integer>>> equalityCounters =
296            new HashMap<>();
297           
298        /**
299         *
300         */
301        private void addCoverageCounter(ITask task, ITaskModel model) {
302            if (model1 == null) {
303                model1 = model;
304            }
305            else if (model2 == null) {
306                model2 = model;
307            }
308           
309            int coverageRatio = model.getTaskInfo(task).getMeasureValue(TaskMetric.EVENT_COVERAGE);
310           
311            if (model == model1) {
312                addToMaps(coverageCounters1, coverageRatio, 1);
313                taskCounter1++;
314                maxCoverage1 = Math.max(maxCoverage1, coverageRatio);
315            }
316            else {
317                addToMaps(coverageCounters2, coverageRatio, 1);
318                taskCounter2++;
319                maxCoverage2 = Math.max(maxCoverage2, coverageRatio);
320            }
321        }
322       
323        /**
324         *
325         */
326        private void store(ITask        task,
327                           ITaskModel   model,
328                           ITask        other,
329                           ITaskModel   otherModel,
330                           TaskEquality equality)
331        {
332            int coverageRatio1 = model.getTaskInfo(task).getMeasureValue(TaskMetric.EVENT_COVERAGE);
333            int coverageRatio2 =
334                otherModel.getTaskInfo(other).getMeasureValue(TaskMetric.EVENT_COVERAGE);
335           
336            addToMaps(coverageRatio1, coverageRatio2, equality, 1);
337        }
338       
339        /**
340         *
341         */
342        private void store(ITask task, ITaskModel model) {
343            int coverageRatio1 = model.getTaskInfo(task).getMeasureValue(TaskMetric.EVENT_COVERAGE);
344           
345            addToMaps(coverageRatio1, 0, TaskEquality.UNEQUAL, 1);
346        }
347
348        /**
349         *
350         */
351        private void addToMaps(Map<Integer, Integer> coverageCounters, int ratio, int increment) {
352            Integer counter = coverageCounters.get(ratio);
353
354            if (counter == null) {
355                coverageCounters.put(ratio, increment);
356            }
357            else {
358                coverageCounters.put(ratio, counter + increment);
359            }
360        }
361       
362        /**
363         *
364         */
365        private void addToMaps(Integer ratio1, Integer ratio2, TaskEquality equality, int value) {
366            Map<Integer, Map<TaskEquality, Integer>> counters1 = equalityCounters.get(ratio1);
367               
368            if (counters1 == null) {
369                counters1 = new HashMap<>();
370                equalityCounters.put(ratio1, counters1);
371            }
372
373            Map<TaskEquality, Integer> counters2 = counters1.get(ratio2);
374
375            if (counters2 == null) {
376                counters2 = new HashMap<>();
377                counters1.put(ratio2, counters2);
378            }
379
380            Integer counter = counters2.get(equality);
381
382            if (counter == null) {
383                counters2.put(equality, value);
384            }
385            else {
386                counters2.put(equality, counter + value);
387            }
388        }
389
390        /**
391         *
392         */
393        private void dump() {
394            Console.println("Statistics of Similarity");
395            Console.println("========================");
396           
397            int[][] bins1 = getBinsOfAlmostEqualSize(coverageCounters1, taskCounter1, maxCoverage1);
398            int[][] bins2 = getBinsOfAlmostEqualSize(coverageCounters2, taskCounter2, maxCoverage2);
399            int lowerBorder1;
400            int higherBorder1;
401            int lowerBorder2;
402            int higherBorder2;
403            int identicalEqualitiesOfBin = 0;
404            int lexicalEqualitiesOfBin = 0;
405            int syntacticalEqualitiesOfBin = 0;
406            int semanticalEqualitiesOfBin = 0;
407            int similaritiesOfBin = 0;
408            int allEqualities = 0;
409           
410            String[][] outputs = new String[(bins1.length * (bins2.length + 3)) + 1][];
411            int outputIndex = 0;
412           
413            DecimalFormat percentFormat = new DecimalFormat("##0.0%");
414            StringBuffer csvData = new StringBuffer();
415            csvData.append(taskCounter1);
416            csvData.append(';');
417            csvData.append(taskCounter2);
418           
419            for (int i = 0; i < bins1.length; i++) {
420                if (i == 0) {
421                    higherBorder1 = maxCoverage1;
422                }
423                else {
424                    higherBorder1 = bins1[i - 1][0] - 1;
425                }
426               
427                lowerBorder1 = bins1[i][0];
428                int allInBin1 = bins1[i][1];
429
430                csvData.append(';');
431                csvData.append(allInBin1);
432               
433                identicalEqualitiesOfBin = 0;
434                lexicalEqualitiesOfBin = 0;
435                syntacticalEqualitiesOfBin = 0;
436                semanticalEqualitiesOfBin = 0;
437                similaritiesOfBin = 0;
438               
439                outputs[outputIndex++] = new String[]
440                        { "similarities of " + bins1[i][1] + " tasks with " + lowerBorder1 +
441                          " to " + higherBorder1 + " covered events", "IDENT", "LEX", "SYN", "SEM",
442                          "ALL EQUAL", "SIM", "ALL" };
443               
444                for (int j = 0; j < bins2.length; j++) {
445                    if (j == 0) {
446                        higherBorder2 = maxCoverage2;
447                    }
448                    else {
449                        higherBorder2 = bins2[j - 1][0] - 1;
450                    }
451                   
452                    lowerBorder2 = bins2[j][0];
453                    int allInBin2 = bins2[j][1];
454                   
455                    csvData.append(';');
456                    csvData.append(allInBin2);
457
458                    int count1 = countEqualities(lowerBorder1, higherBorder1, lowerBorder2,
459                                                 higherBorder2, TaskEquality.IDENTICAL);
460
461                    int count2 = countEqualities(lowerBorder1, higherBorder1, lowerBorder2,
462                                                 higherBorder2, TaskEquality.LEXICALLY_EQUAL);
463
464                    int count3 = countEqualities(lowerBorder1, higherBorder1, lowerBorder2,
465                                                 higherBorder2, TaskEquality.SYNTACTICALLY_EQUAL);
466
467                    int count4 = countEqualities(lowerBorder1, higherBorder1, lowerBorder2,
468                                                 higherBorder2, TaskEquality.SEMANTICALLY_EQUAL);
469                   
470                    int count5 = countEqualities(lowerBorder1, higherBorder1, lowerBorder2,
471                                                 higherBorder2, null);
472                   
473                    outputs[outputIndex++] = new String[]
474                            { "--> to " + allInBin2 + " tasks with " + lowerBorder2 +
475                              " to " + higherBorder2 + " covered events", format(count1, allInBin1),
476                              format(count2, allInBin1), format(count3, allInBin1),
477                              format(count4, allInBin1),
478                              format(count1 + count2 + count3 + count4, allInBin1),
479                              format(count5, allInBin1),
480                              format(count1 + count2 + count3 + count4 + count5, allInBin1)
481                            };
482                   
483                    identicalEqualitiesOfBin += count1;
484                    lexicalEqualitiesOfBin += count2;
485                    syntacticalEqualitiesOfBin += count3;
486                    semanticalEqualitiesOfBin += count4;
487                    similaritiesOfBin += count5;
488
489                    csvData.append(';');
490                    csvData.append(percentFormat.format((double) count1 / allInBin1));
491                    csvData.append(';');
492                    csvData.append(percentFormat.format((double) count2 / allInBin1));
493                    csvData.append(';');
494                    csvData.append(percentFormat.format((double) count3 / allInBin1));
495                    csvData.append(';');
496                    csvData.append(percentFormat.format((double) count4 / allInBin1));
497                    csvData.append(';');
498                    csvData.append(percentFormat.format
499                                       ((double) (count1 + count2 + count3 + count4) / allInBin1));
500                    csvData.append(';');
501                    csvData.append(percentFormat.format((double) count5 / allInBin1));
502                    csvData.append(';');
503                    csvData.append(percentFormat.format
504                                       ((double) (count1 + count2 + count3 + count4 + count5) / allInBin1));
505                }
506               
507                outputs[outputIndex++] = new String[]
508                        { "--> all recalls", format(identicalEqualitiesOfBin, allInBin1),
509                          format(lexicalEqualitiesOfBin, allInBin1),
510                          format(syntacticalEqualitiesOfBin, allInBin1),
511                          format(semanticalEqualitiesOfBin, allInBin1),
512                          format(identicalEqualitiesOfBin + lexicalEqualitiesOfBin +
513                                 syntacticalEqualitiesOfBin + semanticalEqualitiesOfBin, allInBin1),
514                          format(similaritiesOfBin, allInBin1),
515                          format(identicalEqualitiesOfBin + lexicalEqualitiesOfBin +
516                                 syntacticalEqualitiesOfBin + semanticalEqualitiesOfBin +
517                                 similaritiesOfBin, allInBin1)
518                        };
519               
520
521                csvData.append(';');
522                csvData.append(percentFormat.format((double) identicalEqualitiesOfBin / allInBin1));
523                csvData.append(';');
524                csvData.append(percentFormat.format((double) lexicalEqualitiesOfBin / allInBin1));
525                csvData.append(';');
526                csvData.append(percentFormat.format((double) syntacticalEqualitiesOfBin / allInBin1));
527                csvData.append(';');
528                csvData.append(percentFormat.format((double) semanticalEqualitiesOfBin / allInBin1));
529                csvData.append(';');
530                csvData.append(percentFormat.format
531                                   ((double) (identicalEqualitiesOfBin + lexicalEqualitiesOfBin +
532                                              syntacticalEqualitiesOfBin + semanticalEqualitiesOfBin)
533                                              / allInBin1));
534                csvData.append(';');
535                csvData.append(percentFormat.format((double) similaritiesOfBin / allInBin1));
536                csvData.append(';');
537                csvData.append(percentFormat.format
538                                   ((double) (identicalEqualitiesOfBin + lexicalEqualitiesOfBin +
539                                              syntacticalEqualitiesOfBin + semanticalEqualitiesOfBin +
540                                              similaritiesOfBin) / allInBin1));
541               
542                allEqualities += identicalEqualitiesOfBin + lexicalEqualitiesOfBin +
543                    syntacticalEqualitiesOfBin + semanticalEqualitiesOfBin + similaritiesOfBin;
544               
545                outputIndex++;
546            }
547           
548            outputs[outputIndex++] = new String[]
549                    { "complete recall is", null, null, null, null, null,
550                      format(allEqualities, taskCounter1)
551                    };
552           
553            csvData.append(';');
554            csvData.append(percentFormat.format((double) allEqualities / taskCounter1));
555           
556            dump(outputs);
557            Console.println("\nCSV: " + csvData);
558        }
559
560        /**
561         *
562         */
563        private void dump(String[][] outputs) {
564            int[] lengths = new int[outputs[0].length];
565           
566            for (String[] line : outputs) {
567                if (line != null) {
568                    for (int i = 0; i < line.length; i++) {
569                        if (line[i] != null) {
570                            lengths[i] = Math.max(lengths[i], line[i].length());
571                        }
572                    }
573                }
574            }
575           
576            for (String[] line : outputs) {
577                StringBuffer toWrite = new StringBuffer();
578               
579                if (line != null) {
580                    for (int i = 0; i < line.length; i++) {
581                        if (i > 0) {
582                            toWrite.append(" | ");
583                        }
584                   
585                        String text = line[i];
586                   
587                        if (text == null) {
588                            text = "";
589                        }
590                   
591                        for (int j = 0; j < (lengths[i] - text.length()); j++) {
592                            toWrite.append(' ');
593                        }
594                     
595                        toWrite.append(text);
596                    }
597                }
598               
599                Console.println(toWrite.toString());
600            }
601        }
602
603        /**
604         *
605         */
606        private int[][] getBinsOfAlmostEqualSize(Map<Integer, Integer> coverageCounters,
607                                                 int                   taskCounter,
608                                                 int                   maxCoverage)
609        {
610            int[][] result = new int[5][];
611           
612            for (int i = 0; i < result.length; i++) {
613                result[i] = new int[2];
614            }
615           
616            int averageBinSize = taskCounter / result.length;
617            int aimedBinSize = averageBinSize;
618           
619            int index = 0;
620            int allCoverageCounterSum = 0;
621           
622            for (int i = maxCoverage; i > 0; i--) {
623                if (result[index][1] > aimedBinSize) {
624                    if ((index + 2) < result.length) {
625                        // try to compensate, if the previous bin was a little too large
626                        aimedBinSize = averageBinSize + averageBinSize - result[index][1];
627                    }
628                    else {
629                        // put all remaining in the last bin
630                        aimedBinSize = Integer.MAX_VALUE;
631                    }
632                    index++;
633                }
634
635                Integer value = coverageCounters.get(i);
636               
637                if (value != null) {
638                    result[index][0] = i;
639                    result[index][1] += value;
640                    allCoverageCounterSum += value;
641                }
642            }
643           
644            if (taskCounter != allCoverageCounterSum) {
645                throw new RuntimeException("bins do not cover all tasks");
646            }
647           
648            return result;
649        }
650
651        /**
652         *
653         */
654        private String format(int noOfEqualTasks, int noOfAllTasks) {
655            StringBuffer result = new StringBuffer();
656            if (noOfAllTasks > 0) {
657                double value = ((double) (noOfEqualTasks * 100)) / noOfAllTasks;
658                result.append(noOfEqualTasks);
659                result.append(" (");
660                result.append(new DecimalFormat("##0.0").format(value));
661                result.append("%)");
662            }
663            else {
664                result.append("n.a.");
665            }
666           
667            return result.toString();
668        }
669
670        /**
671         *
672         */
673        private int countEqualities(int          lowerBorder1,
674                                    int          higherBorder1,
675                                    int          lowerBorder2,
676                                    int          higherBorder2,
677                                    TaskEquality equality)
678        {
679            int counter = 0;
680           
681            for (int i = lowerBorder1; i <= higherBorder1; i++) {
682                Map<Integer, Map<TaskEquality, Integer>> counters1 = equalityCounters.get(i);
683
684                if (counters1 != null) {
685                    for (int j = lowerBorder2; j <= higherBorder2; j++) {
686                        Map<TaskEquality, Integer> counters2 = counters1.get(j);
687               
688                        if (counters2 != null) {
689                            Integer counterObj = counters2.get(equality);
690                   
691                            if (counterObj != null) {
692                                counter += counterObj;
693                            }
694                        }
695                    }
696                }
697            }
698           
699            return counter;
700        }
701    }
702
703    /**
704     *
705     */
706    private static class ComparisonRunnable implements Runnable {
707       
708        /** */
709        private ITaskModel model1;
710       
711        /** */
712        private ITaskModel model2;
713       
714        /** */
715        private List<ISequence> tasks1;
716       
717        /** */
718        private List<ISequence> tasks2;
719       
720        /** */
721        private Map<Integer, Map<IEventTarget, List<ISequence>>> lengthIndex1;
722       
723        /** */
724        private Map<ISequence, Integer> lengthIndex2;
725       
726        /** */
727        private Map<ISequence, IEventTarget> firstTargetIndex;
728       
729        /** */
730        private Map<ISequence, TaskTraversal> traversalIndex;
731
732        /** */
733        private Object semaphore;
734       
735        /** */
736        private SimilarityStatistics statistics = new SimilarityStatistics();
737
738        /** */
739        private TaskEqualityRuleManager equalityRuleManager = TaskEqualityRuleManager.getInstance();
740
741        /**
742         *
743         */
744        private ComparisonRunnable(ITaskModel                                       model1,
745                                   List<ISequence>                                  tasks1,
746                                   ITaskModel                                       model2,
747                                   List<ISequence>                                  tasks2,
748                                   Map<Integer, Map<IEventTarget, List<ISequence>>> lengthIndex1,
749                                   Map<ISequence, Integer>                          lengthIndex2,
750                                   Map<ISequence, IEventTarget>                     firstTargetIndex,
751                                   Map<ISequence, TaskTraversal>                    traversalIndex,
752                                   Object                                           semaphore)
753        {
754            this.model1 = model1;
755            this.tasks1 = tasks1;
756            this.model2 = model2;
757            this.tasks2 = tasks2;
758            this.lengthIndex1 = lengthIndex1;
759            this.lengthIndex2 = lengthIndex2;
760            this.firstTargetIndex = firstTargetIndex;
761            this.traversalIndex = traversalIndex;
762            this.semaphore = semaphore;
763        }
764
765        /* (non-Javadoc)
766         * @see java.lang.Runnable#run()
767         */
768        @Override
769        public void run() {
770            TaskComparator comparator = new TaskComparator(TaskEquality.SEMANTICALLY_EQUAL);
771            TaskEquality mostCommonEquality;
772            ISequence mostSimilarTask;
773            TaskEquality equality;
774            SimilarTasks similarity;
775
776            // store coverage infos for models
777            for (ISequence task : tasks1) {
778                statistics.addCoverageCounter(task, model1);
779            }
780           
781            for (ISequence task : tasks2) {
782                statistics.addCoverageCounter(task, model2);
783            }
784           
785            List<ISequence> tasksToCompareWith = new ArrayList<ISequence>();
786            StopWatch watch = new StopWatch();
787            watch.start("all comparisons ");
788            int count = 0;
789            int taskNo = 0;
790            int nextPercent = 10;
791            for (ISequence task : tasks1) {
792                int length = lengthIndex2.get(task);
793                IEventTarget firstTarget = firstTargetIndex.get(task);
794                tasksToCompareWith.clear();
795               
796                // add tasks with same length
797                Map<IEventTarget, List<ISequence>> eventTaskMap = lengthIndex1.get(length);
798                List<ISequence> toCompare;
799               
800                if (eventTaskMap != null) {
801                    toCompare = eventTaskMap.get(firstTarget);
802               
803                    if (toCompare != null) {
804                        tasksToCompareWith.addAll(toCompare);
805                    }
806                }
807               
808                // add tasks containing selections
809                eventTaskMap = lengthIndex1.get(-1);
810               
811                if (eventTaskMap != null) {
812                    toCompare = eventTaskMap.get(firstTarget);
813               
814                    if (toCompare != null) {
815                        tasksToCompareWith.addAll(toCompare);
816                    }
817                }
818               
819                mostCommonEquality = null;
820                mostSimilarTask = null;
821               
822                for (ISequence taskToCompare : tasksToCompareWith) {
823                    count++;
824                    watch.start("normal comparison");
825                    equality = equalityRuleManager.compare(task, taskToCompare);
826                    watch.stop("normal comparison");
827                   
828                    if ((equality != TaskEquality.UNEQUAL) &&
829                        ((mostCommonEquality == null) || (equality.isAtLeast(mostCommonEquality))))
830                    {
831                        // >>>>>>>>>>>>>>>>>>>>>> TEST IMPLEMENTATION >>>>>>>>>>>>>>>>>>>>>>>>>>>
832                        // synchronized (System.out) {
833                        //     System.out.println("found equal tasks: " + equality);
834                        //     new TaskTreeEncoder().encode(task, System.out);
835                        //     new TaskTreeEncoder().encode(taskToCompare, System.out);
836                        // }
837                        // <<<<<<<<<<<<<<<<<<<<<< TEST IMPLEMENTATION <<<<<<<<<<<<<<<<<<<<<<<<<<<
838
839                        mostCommonEquality = equality;
840                        mostSimilarTask = taskToCompare;
841                       
842                        if (mostCommonEquality.isAtLeast(TaskEquality.LEXICALLY_EQUAL)) {
843                            // we found a lexically equal match, the most concrete that
844                            // we can find. We can break up here
845                            break;
846                        }
847                    }
848                }
849               
850                if (mostCommonEquality != null) {
851                    // check, if both tasks are identical
852                    if (!identicalTasks(task, mostSimilarTask)) {
853                        statistics.store(task, model1, mostSimilarTask, model2, mostCommonEquality);
854                    }
855                    else {
856                        statistics.store
857                            (task, model1, mostSimilarTask, model2, TaskEquality.IDENTICAL);
858                    }
859                }
860                else {
861                    int lowestDiffLevel = Integer.MAX_VALUE;
862                    TaskTraversal traversal1 = traversalIndex.get(task);
863                   
864                    for (ISequence taskToCompare : tasksToCompareWith) {
865                        count++;
866                        watch.start("similarity comparison");
867                        TaskTraversal traversal2 = traversalIndex.get(taskToCompare);
868                        similarity =
869                            SimilarTasks.compareTraversals(traversal1, traversal2, comparator);
870                        watch.stop("similarity comparison");
871                       
872                        if (similarity.getDiffLevel() < lowestDiffLevel) {
873                            lowestDiffLevel = similarity.getDiffLevel();
874                            mostSimilarTask = taskToCompare;
875                           
876                            if (lowestDiffLevel <= 0) {
877                                // >>>>>>>>>>>>>>>>>>>>>> TEST IMPLEMENTATION >>>>>>>>>>>>>>>>>>>>>
878                                // synchronized (System.out) {
879                                //     System.out.println("found similar tasks");
880                                //     similarity.dump(System.out);
881                                // }
882                                // <<<<<<<<<<<<<<<<<<<<<< TEST IMPLEMENTATION <<<<<<<<<<<<<<<<<<<<<
883
884                                // we found a fully similar task. We will not find any more
885                                // similar, hence we break
886                                break;
887                            }
888                        }
889                    }
890                   
891                    if (lowestDiffLevel <= 0) {
892                        statistics.store(task, model1, mostSimilarTask, model2, null);
893                    }
894                    else {
895                        statistics.store(task, model1);
896                    }
897                }
898               
899                taskNo++;
900               
901                if (((taskNo * 100) / tasks1.size()) > nextPercent) {
902                    System.out.println("compared " + nextPercent + "% (" + taskNo + " tasks) of " +
903                                       model1 + " with " + tasks2.size() + " tasks of " + model2);
904                    nextPercent += 10;
905                }
906            }
907           
908            System.out.println("performed " + count + " comparisons for comparing " + model1 +
909                               " with " + model2);
910           
911            watch.stop("all comparisons ");
912            watch.dumpStatistics(System.out);
913           
914            synchronized (semaphore) {
915                semaphore.notify();
916            }
917        }
918
919        /**
920         *
921         */
922        private boolean identicalTasks(ISequence sequence1, ISequence sequence2) {
923            if (sequence1.getChildren().size() != sequence2.getChildren().size()) {
924                return false;
925            }
926           
927            for (int i = 0; i < sequence1.getChildren().size(); i++) {
928                if (!identicalTasks(sequence1.getChildren().get(i), sequence2.getChildren().get(i)))
929                {
930                    return false;
931                }
932            }
933           
934            return true;
935        }
936
937        /**
938         *
939         */
940        private boolean identicalTasks(IIteration iteration1, IIteration iteration2) {
941            return identicalTasks(iteration1.getMarkedTask(), iteration2.getMarkedTask());
942        }
943
944        /**
945         *
946         */
947        private boolean identicalTasks(IOptional optional1, IOptional optional2) {
948            return identicalTasks(optional1.getMarkedTask(), optional2.getMarkedTask());
949        }
950
951        /**
952         *
953         */
954        private boolean identicalTasks(ISelection selection1, ISelection selection2) {
955            if (selection1.getChildren().size() != selection2.getChildren().size()) {
956                return false;
957            }
958           
959            FIRST_SELECTION_CHILDREN:
960            for (ITask child1 : selection1.getChildren()) {
961                for (ITask child2 : selection2.getChildren()) {
962                    if (identicalTasks(child1, child2)) {
963                        continue FIRST_SELECTION_CHILDREN;
964                    }
965                }
966               
967                return false;
968            }
969           
970            return true;
971        }
972
973        /**
974         *
975         */
976        private boolean identicalTasks(IEventTask eventTask1, IEventTask eventTask2) {
977            return equalityRuleManager.compare(eventTask1, eventTask2).isAtLeast
978                (TaskEquality.SEMANTICALLY_EQUAL);
979        }
980       
981        /**
982         *
983         */
984        private boolean identicalTasks(ITask task1, ITask task2) {
985            if ((task1 instanceof ISequence) && (task2 instanceof ISequence)) {
986                return identicalTasks((ISequence) task1, (ISequence) task2);
987            }
988            else if ((task1 instanceof IIteration) && (task2 instanceof IIteration)) {
989                return identicalTasks((IIteration) task1, (IIteration) task2);
990            }
991            else if ((task1 instanceof IOptional) && (task2 instanceof IOptional)) {
992                return identicalTasks((IOptional) task1, (IOptional) task2);
993            }
994            else if ((task1 instanceof ISelection) && (task2 instanceof ISelection)) {
995                return identicalTasks((ISelection) task1, (ISelection) task2);
996            }
997            else if ((task1 instanceof IEventTask) && (task2 instanceof IEventTask)) {
998                return identicalTasks((IEventTask) task1, (IEventTask) task2);
999            }
1000            else {
1001                return false;
1002            }
1003        }
1004
1005        /**
1006         * @return the statistics
1007         */
1008        private SimilarityStatistics getStatistics() {
1009            return statistics;
1010        }
1011       
1012    }
1013}
Note: See TracBrowser for help on using the repository browser.