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

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

/**
 * <p>
 * compares a set of task models with each other and drops their similarity as results
 * </p>
 * 
 * @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 <tasktree1> <tasktree2> ...";
    }

    /*
     * (non-Javadoc)
     * 
     * @see de.ugoe.cs.util.console.Command#run(java.util.List)
     */
    @Override
    public void run(List<Object> parameters) {
        List<String> 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<ITaskModel, List<ISequence>> 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<ISequence> 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<ITaskModel, List<ISequence>> inputTaskModels,
                                        SimilarityStatistics             statistics)
    {
        // create the indexes to not do too many comparisons
        Map<ITaskModel, Map<Integer, Map<IEventTarget, List<ISequence>>>> index1 =
            new IdentityHashMap<>();
        
        Map<ISequence, Integer> index2 = new HashMap<>();
        Map<ISequence, IEventTarget> index3 = new HashMap<>();
        
        final List<IEventTask> terminalNodes = new ArrayList<>();
        final List<ISelection> selections = new ArrayList<>();
        
        for (Map.Entry<ITaskModel, List<ISequence>> 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<Integer, Map<IEventTarget, List<ISequence>>> lengthMap =
                    index1.get(entry.getKey());
                
                if (lengthMap == null) {
                    lengthMap = new HashMap<>();
                    index1.put(entry.getKey(), lengthMap);
                }
                
                Map<IEventTarget, List<ISequence>> firstTaskMap = lengthMap.get(length);
                
                if (firstTaskMap == null) {
                    firstTaskMap = new HashMap<>();
                    lengthMap.put(length, firstTaskMap);
                }
                
                List<ISequence> compareList = firstTaskMap.get(firstTarget);
                
                if (compareList == null) {
                    compareList = new LinkedList<ISequence>();
                    firstTaskMap.put(firstTarget, compareList);
                }
                
                compareList.add(sequence);
                index2.put(sequence, length);
                index3.put(sequence, firstTarget);
            }
        }
        
        // create the comparison runnables
        List<ComparisonRunnable> runnables = new LinkedList<>();
        
        for (Map.Entry<ITaskModel, List<ISequence>> model1 : inputTaskModels.entrySet()) {
            for (Map.Entry<ITaskModel, List<ISequence>> 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<Integer, Integer> coverageCounters = new HashMap<>();
        
        /**  */
        private Map<Integer, Map<Integer, Map<TaskEquality, Integer>>> 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<Integer, Map<Integer, Map<TaskEquality, Integer>>> entry1 :
                     statistics.equalityCounters.entrySet())
            {
                for (Map.Entry<Integer, Map<TaskEquality, Integer>> entry2 :
                         entry1.getValue().entrySet())
                {
                    for (Map.Entry<TaskEquality, Integer> entry3 : entry2.getValue().entrySet()) {
                        addToMaps
                            (entry1.getKey(), entry2.getKey(), entry3.getKey(), entry3.getValue());
                    }
                }
            }
            
            for (Map.Entry<Integer, Integer> 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<Integer, Map<TaskEquality, Integer>> counters1 = equalityCounters.get(ratio1);
                
            if (counters1 == null) {
                counters1 = new HashMap<>();
                equalityCounters.put(ratio1, counters1);
            }

            Map<TaskEquality, Integer> 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<Integer, Map<TaskEquality, Integer>> counters1 = equalityCounters.get(i);

                if (counters1 != null) {
                    for (int j = lowerBorder2; j <= higherBorder2; j++) {
                        Map<TaskEquality, Integer> 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<ISequence> tasks1;
        
        /** */
        private List<ISequence> tasks2;
        
        /** */
        private Map<Integer, Map<IEventTarget, List<ISequence>>> lengthIndex1;
        
        /** */
        private Map<ISequence, Integer> lengthIndex2;
        
        /** */
        private Map<ISequence, IEventTarget> firstTargetIndex;

        /** */
        private Object semaphore;
        
        /** */
        private SimilarityStatistics statistics = new SimilarityStatistics();
        
        /**
         * 
         */
        private ComparisonRunnable(ITaskModel                                       model1,
                                   List<ISequence>                                  tasks1,
                                   ITaskModel                                       model2,
                                   List<ISequence>                                  tasks2,
                                   Map<Integer, Map<IEventTarget, List<ISequence>>> lengthIndex1,
                                   Map<ISequence, Integer>                          lengthIndex2,
                                   Map<ISequence, IEventTarget>                     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<ISequence> tasksToCompareWith = new ArrayList<ISequence>();
            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<IEventTarget, List<ISequence>> eventTaskMap = lengthIndex1.get(length);
                List<ISequence> 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;
        }
        
    }
}