//   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.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;
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<>();
        
        ITaskModel firstModel = null;
        
        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);
            
            if (firstModel == null) {
                firstModel = (ITaskModel) dataObject;
            }
        }
        
        getTaskModelSimilarity(firstModel, inputTaskModels);
    }

    /**
     *
     */
    private void getTaskModelSimilarity(ITaskModel                       modelToCompare,
                                        Map<ITaskModel, List<ISequence>> inputTaskModels)
    {
        // create the indexes to not do too many comparisons
        Map<ITaskModel, Map<Integer, Map<IEventTarget, List<ISequence>>>> index1 =
            new IdentityHashMap<>();
        
        Map<ISequence, Integer> lengthIndex = new HashMap<>();
        Map<ISequence, IEventTarget> firstTargetIndex = new HashMap<>();
        Map<ISequence, TaskTraversal> taskTraversalIndex = 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);
                lengthIndex.put(sequence, length);
                firstTargetIndex.put(sequence, firstTarget);
                taskTraversalIndex.put(sequence, TaskTraversal.getTraversal(sequence, null));
            }
        }
        
        // create the comparison runnables
        List<ComparisonRunnable> runnables = new LinkedList<>();
        
        for (Map.Entry<ITaskModel, List<ISequence>> model2 : inputTaskModels.entrySet()) {
            if (modelToCompare != model2.getKey()) {
                runnables.add(new ComparisonRunnable(modelToCompare,
                                                     inputTaskModels.get(modelToCompare),
                                                     model2.getKey(), model2.getValue(),
                                                     Collections.unmodifiableMap
                                                         (index1.get(model2.getKey())),
                                                     Collections.unmodifiableMap(lengthIndex),
                                                     Collections.unmodifiableMap(firstTargetIndex),
                                                     Collections.unmodifiableMap(taskTraversalIndex),
                                                     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("\nsimilarity statistics of comparison between " + runnable.model1 +
                            " (" + runnable.tasks1.size() + " tasks) and " + runnable.model2 +
                            " (" + runnable.tasks2.size() + " tasks)");
            runnable.getStatistics().dump();
        }
    }

    /**
     *
     */
    private static class SimilarityStatistics {
        
        /**  */
        private int taskCounter1 = 0;
        
        /** */
        private int maxCoverage1 = 0;
        
        /** */
        private ITaskModel model1 = null;
        
        /**  */
        private Map<Integer, Integer> coverageCounters1 = new HashMap<>();
        
        /**  */
        private int taskCounter2 = 0;
        
        /** */
        private int maxCoverage2 = 0;
        
        /** */
        private ITaskModel model2 = null;
        
        /**  */
        private Map<Integer, Integer> coverageCounters2 = new HashMap<>();
        
        /**  */
        private Map<Integer, Map<Integer, Map<TaskEquality, Integer>>> equalityCounters =
            new HashMap<>();
            
        /**
         *
         */
        private void addCoverageCounter(ITask task, ITaskModel model) {
            if (model1 == null) {
                model1 = model;
            }
            else if (model2 == null) {
                model2 = model;
            }
            
            int coverageRatio = model.getTaskInfo(task).getMeasureValue(TaskMetric.EVENT_COVERAGE);
            
            if (model == model1) {
                addToMaps(coverageCounters1, coverageRatio, 1);
                taskCounter1++;
                maxCoverage1 = Math.max(maxCoverage1, coverageRatio);
            }
            else {
                addToMaps(coverageCounters2, coverageRatio, 1);
                taskCounter2++;
                maxCoverage2 = Math.max(maxCoverage2, coverageRatio);
            }
        }
        
        /**
         *
         */
        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, coverageRatio2, equality, 1);
        }
        
        /**
         *
         */
        private void store(ITask task, ITaskModel model) {
            int coverageRatio1 = model.getTaskInfo(task).getMeasureValue(TaskMetric.EVENT_COVERAGE);
            
            addToMaps(coverageRatio1, 0, TaskEquality.UNEQUAL, 1);
        }

        /**
         *
         */
        private void addToMaps(Map<Integer, Integer> coverageCounters, 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[][] bins1 = getBinsOfAlmostEqualSize(coverageCounters1, taskCounter1, maxCoverage1);
            int[][] bins2 = getBinsOfAlmostEqualSize(coverageCounters2, taskCounter2, maxCoverage2);
            int lowerBorder1;
            int higherBorder1;
            int lowerBorder2;
            int higherBorder2;
            int identicalEqualitiesOfBin = 0;
            int lexicalEqualitiesOfBin = 0;
            int syntacticalEqualitiesOfBin = 0;
            int semanticalEqualitiesOfBin = 0;
            int similaritiesOfBin = 0;
            int allEqualities = 0;
            
            String[][] outputs = new String[(bins1.length * (bins2.length + 3)) + 1][];
            int outputIndex = 0;
            
            DecimalFormat percentFormat = new DecimalFormat("##0.0%");
            StringBuffer csvData = new StringBuffer();
            csvData.append(taskCounter1);
            csvData.append(';');
            csvData.append(taskCounter2);
            
            for (int i = 0; i < bins1.length; i++) {
                if (i == 0) {
                    higherBorder1 = maxCoverage1;
                }
                else {
                    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;
                semanticalEqualitiesOfBin = 0;
                similaritiesOfBin = 0;
                
                outputs[outputIndex++] = new String[]
                        { "similarities of " + bins1[i][1] + " tasks with " + lowerBorder1 +
                          " to " + higherBorder1 + " covered events", "IDENT", "LEX", "SYN", "SEM",
                          "ALL EQUAL", "SIM", "ALL" };
                
                for (int j = 0; j < bins2.length; j++) {
                    if (j == 0) {
                        higherBorder2 = maxCoverage2;
                    }
                    else {
                        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 count3 = countEqualities(lowerBorder1, higherBorder1, lowerBorder2,
                                                 higherBorder2, TaskEquality.SYNTACTICALLY_EQUAL);

                    int count4 = countEqualities(lowerBorder1, higherBorder1, lowerBorder2,
                                                 higherBorder2, TaskEquality.SEMANTICALLY_EQUAL);
                    
                    int count5 = countEqualities(lowerBorder1, higherBorder1, lowerBorder2,
                                                 higherBorder2, null);
                    
                    outputs[outputIndex++] = new String[]
                            { "--> to " + allInBin2 + " tasks with " + lowerBorder2 +
                              " to " + higherBorder2 + " covered events", format(count1, allInBin1),
                              format(count2, allInBin1), format(count3, allInBin1),
                              format(count4, allInBin1),
                              format(count1 + count2 + count3 + count4, allInBin1),
                              format(count5, allInBin1),
                              format(count1 + count2 + count3 + count4 + count5, allInBin1)
                            };
                    
                    identicalEqualitiesOfBin += count1;
                    lexicalEqualitiesOfBin += count2;
                    syntacticalEqualitiesOfBin += count3;
                    semanticalEqualitiesOfBin += count4;
                    similaritiesOfBin += count5;

                    csvData.append(';');
                    csvData.append(percentFormat.format((double) count1 / allInBin1));
                    csvData.append(';');
                    csvData.append(percentFormat.format((double) count2 / allInBin1));
                    csvData.append(';');
                    csvData.append(percentFormat.format((double) 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(identicalEqualitiesOfBin, allInBin1),
                          format(lexicalEqualitiesOfBin, allInBin1),
                          format(syntacticalEqualitiesOfBin, allInBin1),
                          format(semanticalEqualitiesOfBin, allInBin1),
                          format(identicalEqualitiesOfBin + lexicalEqualitiesOfBin +
                                 syntacticalEqualitiesOfBin + semanticalEqualitiesOfBin, allInBin1),
                          format(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));
                csvData.append(';');
                csvData.append(percentFormat.format((double) syntacticalEqualitiesOfBin / allInBin1));
                csvData.append(';');
                csvData.append(percentFormat.format((double) semanticalEqualitiesOfBin / allInBin1));
                csvData.append(';');
                csvData.append(percentFormat.format
                                   ((double) (identicalEqualitiesOfBin + lexicalEqualitiesOfBin +
                                              syntacticalEqualitiesOfBin + semanticalEqualitiesOfBin)
                                              / allInBin1));
                csvData.append(';');
                csvData.append(percentFormat.format((double) similaritiesOfBin / allInBin1));
                csvData.append(';');
                csvData.append(percentFormat.format
                                   ((double) (identicalEqualitiesOfBin + lexicalEqualitiesOfBin +
                                              syntacticalEqualitiesOfBin + semanticalEqualitiesOfBin +
                                              similaritiesOfBin) / allInBin1));
                
                allEqualities += identicalEqualitiesOfBin + lexicalEqualitiesOfBin +
                    syntacticalEqualitiesOfBin + semanticalEqualitiesOfBin + similaritiesOfBin;
                
                outputIndex++;
            }
            
            outputs[outputIndex++] = new String[]
                    { "complete recall is", null, null, null, null, null,
                      format(allEqualities, taskCounter1)
                    };
            
            csvData.append(';');
            csvData.append(percentFormat.format((double) allEqualities / taskCounter1));
            
            dump(outputs);
            Console.println("\nCSV: " + csvData);
        }

        /**
         *
         */
        private void dump(String[][] outputs) {
            int[] lengths = new int[outputs[0].length];
            
            for (String[] line : outputs) {
                if (line != null) {
                    for (int i = 0; i < line.length; i++) {
                        if (line[i] != null) {
                            lengths[i] = Math.max(lengths[i], line[i].length());
                        }
                    }
                }
            }
            
            for (String[] line : outputs) {
                StringBuffer toWrite = new StringBuffer();
                
                if (line != null) {
                    for (int i = 0; i < line.length; i++) {
                        if (i > 0) {
                            toWrite.append(" | ");
                        }
                    
                        String text = line[i];
                    
                        if (text == null) {
                            text = "";
                        }
                    
                        for (int j = 0; j < (lengths[i] - text.length()); j++) {
                            toWrite.append(' ');
                        }
                      
                        toWrite.append(text);
                    }
                }
                
                Console.println(toWrite.toString());
            }
        }

        /**
         *
         */
        private int[][] getBinsOfAlmostEqualSize(Map<Integer, Integer> coverageCounters,
                                                 int                   taskCounter,
                                                 int                   maxCoverage)
        {
            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;
            int allCoverageCounterSum = 0;
            
            for (int i = maxCoverage; i > 0; i--) {
                if (result[index][1] > aimedBinSize) {
                    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++;
                }

                Integer value = coverageCounters.get(i);
                
                if (value != null) {
                    result[index][0] = i;
                    result[index][1] += value;
                    allCoverageCounterSum += value;
                }
            }
            
            if (taskCounter != allCoverageCounterSum) {
                throw new RuntimeException("bins do not cover all tasks");
            }
            
            return result;
        }

        /**
         *
         */
        private String format(int noOfEqualTasks, int noOfAllTasks) {
            StringBuffer result = new StringBuffer();
            if (noOfAllTasks > 0) {
                double value = ((double) (noOfEqualTasks * 100)) / noOfAllTasks;
                result.append(noOfEqualTasks);
                result.append(" (");
                result.append(new DecimalFormat("##0.0").format(value));
                result.append("%)");
            }
            else {
                result.append("n.a.");
            }
            
            return result.toString();
        }

        /**
         *
         */
        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 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 Map<ISequence, TaskTraversal> traversalIndex;

        /** */
        private Object semaphore;
        
        /** */
        private SimilarityStatistics statistics = new SimilarityStatistics();

        /** */
        private TaskEqualityRuleManager equalityRuleManager = TaskEqualityRuleManager.getInstance();

        /**
         * 
         */
        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,
                                   Map<ISequence, TaskTraversal>                    traversalIndex,
                                   Object                                           semaphore)
        {
            this.model1 = model1;
            this.tasks1 = tasks1;
            this.model2 = model2;
            this.tasks2 = tasks2;
            this.lengthIndex1 = lengthIndex1;
            this.lengthIndex2 = lengthIndex2;
            this.firstTargetIndex = firstTargetIndex;
            this.traversalIndex = traversalIndex;
            this.semaphore = semaphore;
        }

        /* (non-Javadoc)
         * @see java.lang.Runnable#run()
         */
        @Override
        public void run() {
            TaskComparator comparator = new TaskComparator(TaskEquality.SEMANTICALLY_EQUAL);
            TaskEquality mostCommonEquality;
            ISequence mostSimilarTask;
            TaskEquality equality;
            SimilarTasks similarity;

            // store coverage infos for models
            for (ISequence task : tasks1) {
                statistics.addCoverageCounter(task, model1);
            }
            
            for (ISequence task : tasks2) {
                statistics.addCoverageCounter(task, model2);
            }
            
            List<ISequence> tasksToCompareWith = new ArrayList<ISequence>();
            StopWatch watch = new StopWatch();
            watch.start("all comparisons ");
            int count = 0;
            int taskNo = 0;
            int nextPercent = 10;
            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 (ISequence 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) {
                    // 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;
                    TaskTraversal traversal1 = traversalIndex.get(task);
                    
                    for (ISequence taskToCompare : tasksToCompareWith) {
                        count++;
                        watch.start("similarity comparison");
                        TaskTraversal traversal2 = traversalIndex.get(taskToCompare);
                        similarity =
                            SimilarTasks.compareTraversals(traversal1, traversal2, 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);
                    }
                }
                
                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 ");
            watch.dumpStatistics(System.out);
            
            synchronized (semaphore) {
                semaphore.notify();
            }
        }

        /**
         *
         */
        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
         */
        private SimilarityStatistics getStatistics() {
            return statistics;
        }
        
    }
}