Changeset 1851

Timestamp:

12/23/14 11:34:43 (10 years ago)

Author:

pharms

Message:

• complete refactoring to improve performance and to fix diverse bugs.
• now really all tasks are compared with each other
• as diff is not commutative, comparison is now done in both directions and best comparison result is used as basis for merging
• filter for parent tasks is now deterministic
• filter for first to merge based on mergable level of similarity is now correct

File:

• trunk/autoquest-core-tasktrees/src/main/java/de/ugoe/cs/autoquest/tasktrees/temporalrelation/utils/MostSimilarTaskDeterminer.java (modified) (16 diffs)

trunk/autoquest-core-tasktrees/src/main/java/de/ugoe/cs/autoquest/tasktrees/temporalrelation/utils/MostSimilarTaskDeterminer.java

@@ -15 +15 @@
 package de.ugoe.cs.autoquest.tasktrees.temporalrelation.utils;
 
-import java.util.ArrayList;
 import java.util.HashMap;
 import java.util.HashSet;
@@ -25 +24 @@
 import java.util.logging.Level;
 
-import de.ugoe.cs.autoquest.tasktrees.temporalrelation.TaskInstanceComparator;
+import de.ugoe.cs.autoquest.tasktrees.temporalrelation.TaskComparator;
 import de.ugoe.cs.autoquest.tasktrees.treeifc.DefaultTaskTraversingVisitor;
+import de.ugoe.cs.autoquest.tasktrees.treeifc.IEventTaskInstance;
+import de.ugoe.cs.autoquest.tasktrees.treeifc.ISelectionInstance;
 import de.ugoe.cs.autoquest.tasktrees.treeifc.IStructuringTemporalRelationship;
 import de.ugoe.cs.autoquest.tasktrees.treeifc.ITask;
 import de.ugoe.cs.autoquest.tasktrees.treeifc.ITaskInfo;
+import de.ugoe.cs.autoquest.tasktrees.treeifc.ITaskInstance;
+import de.ugoe.cs.autoquest.tasktrees.treeifc.ITaskInstanceList;
 import de.ugoe.cs.autoquest.tasktrees.treeifc.ITaskModel;
 import de.ugoe.cs.autoquest.tasktrees.treeifc.TaskMetric;
@@ -61 +64 @@
     
     /**
-     * default indicator for unequal tasks
-     */
-    private static final SimilarTasks UNEQUAL_TASKS = new SimilarTasks(null, null, null, null, null);
-    
-    /**
      * task comparator used internally
      */
-    private TaskInstanceComparator comparator;
+    private TaskComparator comparator;
     
     /**
@@ -75 +73 @@
      */
     private Set<Long> comparisonsToSkip = new HashSet<>();
+    
+    /** TODO comment */
+    private long comparisonCounter = 0;
 
     /**
      * Initialize instances of this class with the task comparator to be used
      */
-    public MostSimilarTaskDeterminer(TaskInstanceComparator comparator) {
+    public MostSimilarTaskDeterminer(TaskComparator comparator) {
         this.comparator = comparator;
     }
@@ -95 +96 @@
      */
     public List<SimilarTasks> getMostSimilarTasks(List<ITask> tasks, ITaskModel taskModel) {
-        Console.println("comparing " + tasks.size() + " tasks with each other");
-
-        LinkedList<SimilarTasks> mostSimilarTasksList = performComparisons(tasks);
+        Console.println("comparing " + tasks.size() + " sequences with each other");
+
+        LinkedList<SimilarTasks> mostSimilarTasksList = performComparisons(taskModel, tasks);
+        
+        Console.println("initially found " + mostSimilarTasksList.size() + " similar sequences");
         
         applyFilterForSmallestDiffLevel(mostSimilarTasksList);
+        
+        Console.println("only " + mostSimilarTasksList.size() + " have the smallest diff level");
+        
         applyFilterForParents(mostSimilarTasksList);
+        
+        Console.println(mostSimilarTasksList.size() + " remain after filtering for parents");
+        
         applyFilterForMostCoveredEvents(mostSimilarTasksList, taskModel);
         
-        Console.traceln
-            (Level.FINER, "calculated " + mostSimilarTasksList.size() + " most similar tasks");
+        Console.println("calculated " + mostSimilarTasksList.size() + " most similar sequences");
 
         return mostSimilarTasksList;
@@ -147 +155 @@
         // generated through this rule
         Iterator<SimilarTasks> listIterator = mostSimilarTasksList.iterator();
+        List<SimilarTasks> similarTasksToRemove = new LinkedList<SimilarTasks>();
     
         while (listIterator.hasNext()) {
@@ -161 +170 @@
                     TaskTreeUtils.isChild(task4, task2))
                 {
+                    similarTasksToRemove.add(candidate);
+                    break;
+                }
+            }
+        }
+        
+        listIterator = mostSimilarTasksList.iterator();
+        
+        while (listIterator.hasNext()) {
+            SimilarTasks candidate = listIterator.next();
+            
+            for (SimilarTasks toRemove : similarTasksToRemove) {
+                if (candidate == toRemove) {
                     listIterator.remove();
-                    break;
                 }
             }
@@ -204 +225 @@
             mostSimilarTasksList.clear();
 
-            System.out.println("several comparisons for the same task exist with same diff level " +
-                               "--> filtering for pair to be merged first");
+            Console.traceln(Level.FINEST, "several comparisons for the same task exist with " +
+                            "same diff level --> filtering for pair to be merged first");
 
             SimilarTasks firstToMerge = null;
@@ -285 +306 @@
         // depth is equal. Calculate for both the similarity
         // based on which the merging will take place 
-        valFirst =
-            SimilarTasks.getMergableLevelOfSimilarity(first, comparator).getDiffLevel();
-        valSecond =
-            SimilarTasks.getMergableLevelOfSimilarity(second, comparator).getDiffLevel();
-
-        if (valSecond > valFirst) {
+        SimilarTasks tmp = SimilarTasks.getMergableLevelOfSimilarity(first, comparator);
+        valFirst = tmp != null ? tmp.getDiffLevel() : Integer.MAX_VALUE;
+            
+        tmp = SimilarTasks.getMergableLevelOfSimilarity(second, comparator);
+        valSecond = tmp != null ? tmp.getDiffLevel() : Integer.MAX_VALUE;
+
+        if (valSecond < valFirst) {
             return second;
         }
-        else if (valSecond < valFirst) {
+        else if (valSecond > valFirst) {
             return first;
         }
@@ -325 +347 @@
      * starts several threads performing the task comparisons
      */
-    private LinkedList<SimilarTasks> performComparisons(List<ITask> tasks) {
+    private LinkedList<SimilarTasks> performComparisons(ITaskModel taskModel, List<ITask> tasks) {
         LinkedList<SimilarTasks> mostSimilarTasks = new LinkedList<SimilarTasks>();
         List<Runnable> startedRunnables = new LinkedList<Runnable>();
-        List<Runnable> runnables = createRunnables(tasks, mostSimilarTasks, startedRunnables);
-
-        // create Runnables for all buckets
-        int noOfParallelThreads = Math.min(2, runnables.size());
-        
-        Console.traceln(Level.FINER, "will start " + runnables.size() + " threads");
-        
-        // start the Threads, wait for their completion, and start the next ones if there are
-        // remaining
+
+        comparisonCounter = 0;
+        
+        // groups size is minimal 100 or maximal 1000
+        int groupSize = Math.max
+            (100, Math.min(3000, 1 + (tasks.size() / Runtime.getRuntime().availableProcessors())));
+        
         synchronized (startedRunnables) {
-            while ((runnables.size() > 0) || (startedRunnables.size() > 0)) {
-                while ((startedRunnables.size() < noOfParallelThreads) && (runnables.size() > 0)) {
-                    Runnable runnable = runnables.remove(0);
+            int start1 = 0;
+            int end1;
+            int start2;
+            int end2;
+            
+            do {
+                end1 = Math.min(start1 + groupSize, tasks.size());
+                TaskTraversal[] leftHandTraversals = new TaskTraversal[end1 - start1];
+                
+                Console.traceln(Level.FINE, "calculating left hand traversals from " + start1 +
+                                " to " + end1);
+                
+                int index = 0;
+                for (int j = start1; j < end1; j++) {
+                    leftHandTraversals[index++] =
+                        TaskTraversal.getTraversal(tasks.get(j), null);
+                }
+
+                start2 = 0;
+                do {
+                    end2 = Math.min(start2 + groupSize, end1 - 1);
+                    TaskTraversal[] rightHandTraversals = new TaskTraversal[end2 - start2];
+
+                    if (end2 <= start1) {
+                        Console.traceln(Level.FINE, "calculating right hand traversals from " +
+                                        start2 + " to " + end2);
+                        
+                        // traversals need to be created
+                        index = 0;
+                        for (int j = start2; j < end2; j++) {
+                            rightHandTraversals[index++] =
+                                TaskTraversal.getTraversal(tasks.get(j), null);
+                        }
+                        
+                    }
+                    else {
+                        // traversals can be reused
+                        Console.traceln(Level.FINE, "reusing traversals for right hand from " +
+                                        start2 + " to " + end2);
+                        
+                        rightHandTraversals = leftHandTraversals;
+                    }
+                    
+                    Runnable runnable = new CompareRunnable(taskModel, leftHandTraversals,
+                                                            rightHandTraversals,
+                                                            mostSimilarTasks, startedRunnables);
+                    
+                    while (startedRunnables.size() >= 
+                               Math.max(1, Runtime.getRuntime().availableProcessors()))
+                    {
+                        try {
+                            Console.traceln(Level.FINER, "waiting for next thread to finish");
+                            startedRunnables.wait();
+                            Console.traceln(Level.FINER, "thread finished");
+                        }
+                        catch (InterruptedException e) {
+                            // should not happen
+                            Console.logException(e);
+                        }
+                    }
+                
+                    Console.traceln(Level.FINER, "starting next thread");
                     startedRunnables.add(runnable);
                     new Thread(runnable).start();
-                    Console.traceln(Level.FINEST, "started next thread");
-                }
-           
+                    Console.traceln(Level.FINER, "started next thread " + runnable);
+                    
+                    start2 = end2;
+                }
+                while (end2 < (end1 - 1));
+                
+                start1 = end1;
+            }
+            while (end1 < tasks.size());
+            
+            
+            while (startedRunnables.size() > 0) {
                 try {
+                    Console.traceln(Level.FINER, "waiting for next thread to finish");
                     startedRunnables.wait();
+                    Console.traceln(Level.FINER, "thread finished");
                 }
                 catch (InterruptedException e) {
@@ -353 +443 @@
                     Console.logException(e);
                 }
-
-                Console.traceln(Level.FINEST, "thread finished (" + runnables.size() + ", " +
-                                startedRunnables.size() + ")");
-            }
-        }
-        Console.traceln(Level.FINER, "all threads finished");
+            }
+        }
+        
+        Console.traceln
+            (Level.FINER, "all threads finished, " + comparisonCounter + " comparisons done");
+        
+        if (comparisonCounter != (((tasks.size() - 1) * tasks.size()) / 2)) {
+            throw new RuntimeException(comparisonCounter + "  " +
+                                       (((tasks.size() - 1) * tasks.size()) / 2));
+        }
         
         return mostSimilarTasks;
-    }
-
-    /**
-     * creates runnables for comparing tasks by subdiving the input set of comparisons into 
-     * several subsets where each is compared in a corresponding runnable. The subsets are
-     * at most 150000 comparisons large.
-     */
-    private List<Runnable> createRunnables(List<ITask>              tasks,
-                                           LinkedList<SimilarTasks> mostSimilarTasksList,
-                                           List<Runnable>           startedRunnables)
-    {
-        // subdivide comparisons into buckets to be spread to different threads
-        int noOfComparisons = 0;
-        int noOfScheduledComparisons = 0;
-        List<Integer> bucketIndexes = new ArrayList<Integer>();
-        
-        bucketIndexes.add(0);
-        
-        for (int i = 0; i < tasks.size(); i++) {
-            noOfComparisons += i;
-            
-            if ((noOfComparisons - noOfScheduledComparisons) > 150000) {
-                bucketIndexes.add(i);
-                noOfScheduledComparisons = noOfComparisons;
-            }
-        }
-        
-        bucketIndexes.add(tasks.size());
-        
-        Console.traceln(Level.FINER, "scheduling " + noOfComparisons + " comparisons");
-        
-        List<Runnable> runnables = new LinkedList<Runnable>();
-        
-        for (int i = 1; i < bucketIndexes.size(); i++) {
-            CompareRunnable runnable = new CompareRunnable
-                (tasks, bucketIndexes.get(i - 1), bucketIndexes.get(i), mostSimilarTasksList,
-                 startedRunnables);
-            
-            runnables.add(runnable);
-        }
-        
-        return runnables;
     }
 
@@ -468 +520 @@
 
         /** */
-        private List<ITask> taskList;
+        private ITaskModel taskModel;
         
         /** */
-        private int startIndex;
+        private TaskTraversal[] leftHandTraversals;
         
         /** */
-        private int endIndex;
-
+        private TaskTraversal[] rightHandTraversals;
+        
         /** */
         private List<SimilarTasks> mostSimilarTasksList;
@@ -485 +537 @@
          *
          */
-        public CompareRunnable(List<ITask>         taskList,
-                               int                 startIndex,
-                               int                 endIndex,
-                               List<SimilarTasks>  mostSimilarTasksList,
-                               List<Runnable>      unfinishedRunnables)
+        public CompareRunnable(ITaskModel         taskModel,
+                               TaskTraversal[]    leftHandTraversals,
+                               TaskTraversal[]    rightHandTraversals,
+                               List<SimilarTasks> mostSimilarTasksList,
+                               List<Runnable>     unfinishedRunnables)
         {
-            this.taskList = taskList;
-            this.startIndex = startIndex;
-            this.endIndex = endIndex;
+            this.taskModel = taskModel;
+            this.leftHandTraversals = leftHandTraversals;
+            this.rightHandTraversals = rightHandTraversals;
             this.mostSimilarTasksList = mostSimilarTasksList;
             this.unfinishedRunnables = unfinishedRunnables;
@@ -503 +555 @@
         @Override
         public void run() {
-            int noOfComparisons = 0;
-            
-            for (int i = startIndex; i < endIndex; i++) {
-                noOfComparisons += i;
-            }
-
-            System.out.println("performing " + noOfComparisons + " comparisons");
-            
-            SimilarTasks mostSimilarTasks = UNEQUAL_TASKS;
+            SimilarTasks mostSimilarTasks = SimilarTasks.UNEQUAL_TASKS;
+            int mostSimilarDiffLevel = MAX_DIFF_LEVEL;
             List<SimilarTasks> allMostSimilarTasks = new LinkedList<SimilarTasks>();
-            
-            for (int i = startIndex + 1; i < endIndex; i++) {
-                /*if (appData.isSelfCreatedTask(taskList.get(i))) {
-                    continue;
-                }*/
-                
-                for (int j = startIndex; j < i; j++) {
-                    /*if (appData.isSelfCreatedTask(taskList.get(j))) {
-                        continue;
-                    }*/
+            int counter = 0;
+            
+            LEFT_HAND_TRAVERSAL:
+            for (int i = 0; i < leftHandTraversals.length; i++) {
+                
+                ITask leftHandTask = leftHandTraversals[i].getTask();
+                
+                RIGHT_HAND_TRAVERSAL:
+                for (int j = 0; j < rightHandTraversals.length; j++) {
+
+                    ITask rightHandTask = rightHandTraversals[j].getTask();
                     
-                    if (isComparisonToSkip(taskList.get(i), taskList.get(j))) {
-                        continue;
-                    }
-                    
-                    SimilarTasks similarTasks = SimilarTasks.compareTasks
-                        (taskList.get(i), taskList.get(j), comparator);
-                    
-                    if (similarTasks.isInBetweenDifference()) {
-                        if (similarTasks.getDiffLevel() < mostSimilarTasks.getDiffLevel()) {
-                            mostSimilarTasks = similarTasks;
-                            allMostSimilarTasks.clear();
-                            allMostSimilarTasks.add(similarTasks);
+                    try {
+                        if (leftHandTask == rightHandTask) {
+                            continue LEFT_HAND_TRAVERSAL;
                         }
-                        else if (similarTasks.getDiffLevel() == mostSimilarTasks.getDiffLevel()) {
-                            allMostSimilarTasks.add(similarTasks);
+
+                        counter++;
+
+                        if (isComparisonToSkip(leftHandTask, rightHandTask)) {
+                            continue RIGHT_HAND_TRAVERSAL;
                         }
+                        
+                        if (!isBasicallySimilar(leftHandTraversals[i], rightHandTraversals[j])) {
+                            continue RIGHT_HAND_TRAVERSAL;
+                        }
+
+                        SimilarTasks similarTasks1 = SimilarTasks.compareTraversals
+                            (leftHandTraversals[i], rightHandTraversals[j], comparator);
+
+                        SimilarTasks similarTasks2 = SimilarTasks.compareTraversals
+                            (rightHandTraversals[j], leftHandTraversals[i], comparator);
+
+                        if ((similarTasks1.getDiffLevel() <= mostSimilarDiffLevel) ||
+                            (similarTasks2.getDiffLevel() <= mostSimilarDiffLevel))
+                        {
+                            SimilarTasks similarTasks =
+                                getSimilarTasksToPrefer(similarTasks1, similarTasks2);
+
+                            if (similarTasks.isInBetweenDifference()) {
+                                if (similarTasks.getDiffLevel() < mostSimilarDiffLevel) {
+                                    mostSimilarTasks = similarTasks;
+                                    mostSimilarDiffLevel = mostSimilarTasks.getDiffLevel();
+                                    allMostSimilarTasks.clear();
+                                    allMostSimilarTasks.add(similarTasks);
+                                }
+                                else if (similarTasks.getDiffLevel() == mostSimilarDiffLevel) {
+                                    allMostSimilarTasks.add(similarTasks);
+                                }
+                            }
+                        }
+                    }
+                    catch (Exception e) {
+                        e.printStackTrace();
+
+                        SimilarTasks similarTasks1 = SimilarTasks.compareTraversals
+                            (leftHandTraversals[i], rightHandTraversals[j], comparator);
+
+                        SimilarTasks similarTasks2 = SimilarTasks.compareTraversals
+                            (rightHandTraversals[j], leftHandTraversals[i], comparator);
+
+                        similarTasks1.dump(System.err);
+
+                        similarTasks2.dump(System.err);
                     }
                 }
@@ -546 +628 @@
             synchronized (unfinishedRunnables) {
                 mostSimilarTasksList.addAll(allMostSimilarTasks);
-                
-                //System.out.println("notifying finish");
+                comparisonCounter += counter;
+                
                 for (int i = 0; i < unfinishedRunnables.size(); i++) {
                     if (unfinishedRunnables.get(i) == this) {
@@ -557 +639 @@
         }
 
+        /**
+         *
+         */
+        private boolean isBasicallySimilar(TaskTraversal traversal1, TaskTraversal traversal2) {
+            int length1 = traversal1.size();
+            int length2 = traversal2.size();
+            int maxLength = Math.max(length1, length2);
+            int lengthDiff = 100 * Math.abs(length1 - length2) / maxLength;
+            
+            if (lengthDiff > MAX_DIFF_LEVEL) {
+                return false;
+            }
+            else {
+                return true;
+            }
+        }
+
+        /**
+         * <p>
+         * TODO: comment
+         * </p>
+         *
+         * @param similarTasks1
+         * @param similarTasks2
+         * @return
+         */
+        private SimilarTasks getSimilarTasksToPrefer(SimilarTasks similarTasks1,
+                                                     SimilarTasks similarTasks2)
+        {
+            if (similarTasks2.getDiffLevel() > similarTasks1.getDiffLevel()) {
+                return similarTasks2;
+            }
+            else if (similarTasks1.getDiffLevel() > similarTasks2.getDiffLevel()) {
+                return similarTasks1;
+            }
+            else if (similarTasks1.getDiffLevel() == similarTasks2.getDiffLevel()) {
+                ITask first = similarTasks1.getLeftHandSide();
+                ITask second = similarTasks2.getLeftHandSide();
+                
+                long valFirst = getTaskMetric(first, TaskMetric.EVENT_COVERAGE);
+                long valSecond = getTaskMetric(second, TaskMetric.EVENT_COVERAGE);
+
+                if (valSecond > valFirst) {
+                    return similarTasks2;
+                }
+                else if (valSecond < valFirst) {
+                    return similarTasks1;
+                }
+
+                // no of covered events is equal, try to distinguish by count
+
+                valFirst = getTaskMetric(first, TaskMetric.COUNT);
+                valSecond = getTaskMetric(second, TaskMetric.COUNT);
+
+                if (valSecond > valFirst) {
+                    return similarTasks2;
+                }
+                else if (valSecond < valFirst) {
+                    return similarTasks1;
+                }
+
+                // count is equal, try to distinguish by depth
+
+                valFirst = getTaskMetric(first, TaskMetric.DEPTH);
+                valSecond = getTaskMetric(second, TaskMetric.DEPTH);
+
+                if (valSecond < valFirst) {
+                    return similarTasks2;
+                }
+                else if (valSecond > valFirst) {
+                    return similarTasks1;
+                }
+
+                // no of covered events is equal, try to distinguish by count
+
+                valFirst = cumulateTaskMetric(first, TaskMetric.COUNT);
+                valSecond = cumulateTaskMetric(second, TaskMetric.COUNT);
+
+                if (valSecond > valFirst) {
+                    return similarTasks2;
+                }
+                else if (valSecond < valFirst) {
+                    return similarTasks1;
+                }
+
+                // depth is equal. Calculate for both the similarity
+                // based on which the merging will take place
+                SimilarTasks tmp =
+                    SimilarTasks.getMergableLevelOfSimilarity(similarTasks1, comparator);
+                
+                valFirst = tmp != null ? tmp.getDiffLevel() : Integer.MAX_VALUE;
+                
+                tmp = SimilarTasks.getMergableLevelOfSimilarity(similarTasks2, comparator);
+                valSecond = tmp != null ? tmp.getDiffLevel() : Integer.MAX_VALUE;
+
+                if (valSecond < valFirst) {
+                    return similarTasks2;
+                }
+                else if (valSecond > valFirst) {
+                    return similarTasks1;
+                }
+
+                valFirst = getFirstTimestamp(first);
+                valSecond = getFirstTimestamp(second);
+                
+                if (valSecond > valFirst) {
+                    return similarTasks1;
+                }
+                else if (valSecond < valFirst) {
+                    return similarTasks2;
+                }
+
+                similarTasks1.dump(System.out);
+                similarTasks2.dump(System.out);
+
+                throw new RuntimeException
+                    ("several tasks are similar so that it is undecidable which to merge first");
+            }
+            
+            return null;
+        }
+
+        /**
+         * <p>
+         * TODO: comment
+         * </p>
+         *
+         * @param first
+         * @param eventCoverage
+         * @param taskModel2
+         * @return
+         */
+        private int getTaskMetric(ITask task, TaskMetric metric) {
+            ITaskInfo info = taskModel.getTaskInfo(task);
+            return info.getMeasureValue(metric);
+        }
+        
+        /**
+         * convenience method to get the cumulative value of a task metric
+         */
+        private int cumulateTaskMetric(ITask            task,
+                                       final TaskMetric metric)
+        {
+            final int[] value = new int[1];
+            value[0] = 0;
+            
+            DefaultTaskTraversingVisitor visitor = new DefaultTaskTraversingVisitor() {
+                @Override
+                public void visit(IStructuringTemporalRelationship relationship) {
+                    value[0] += taskModel.getTaskInfo(relationship).getMeasureValue(metric);
+                    super.visit(relationship);
+                }
+            };
+            
+            task.accept(visitor);
+            
+            return value[0];
+        }
+
+        /**
+         * <p>
+         * TODO: comment
+         * </p>
+         *
+         * @param first
+         * @return
+         */
+        private long getFirstTimestamp(ITask task) {
+            long timestamp = Long.MAX_VALUE;
+            
+            for (ITaskInstance instance : task.getInstances()) {
+                ITaskInstance eventTaskInstance = instance;
+                
+                do {
+                    if (eventTaskInstance instanceof ITaskInstanceList) {
+                        eventTaskInstance = ((ITaskInstanceList) eventTaskInstance).get(0);
+                    }
+                    else if (eventTaskInstance instanceof ISelectionInstance) {
+                        eventTaskInstance = ((ISelectionInstance) eventTaskInstance).getChild();
+                    }
+                }
+                while (!(eventTaskInstance instanceof IEventTaskInstance));
+                
+                if (eventTaskInstance != null) {
+                    long newTimestamp =
+                        ((IEventTaskInstance) eventTaskInstance).getEvent().getTimestamp();
+                    
+                    if (timestamp > newTimestamp) {
+                        timestamp = newTimestamp;
+                    }
+                }
+            }
+            
+            return timestamp;
+        }
+        
+        /* (non-Javadoc)
+         * @see java.lang.Object#toString()
+         */
+        @Override
+        public String toString() {
+            return "CompareThread(" + leftHandTraversals.length + ", " +
+                rightHandTraversals.length + ")";
+        }
+
     }
 }