Ignore:
Timestamp:
12/23/14 11:24:24 (10 years ago)
Author:
pharms
Message:
  • performance improvements
  • rename of task instance comparator to task comparator
  • prevention of traversing optional in calculating the mergable level of similarity
  • checking if similar task at a mergable level of similarity are still well aligned
File:
1 edited

Legend:

Unmodified
Added
Removed
  • trunk/autoquest-core-tasktrees/src/main/java/de/ugoe/cs/autoquest/tasktrees/temporalrelation/utils/SimilarTasks.java

    r1767 r1850  
    2222 
    2323import de.ugoe.cs.autoquest.eventcore.gui.Scroll; 
    24 import de.ugoe.cs.autoquest.tasktrees.temporalrelation.TaskInstanceComparator; 
     24import de.ugoe.cs.autoquest.tasktrees.temporalrelation.TaskComparator; 
    2525import de.ugoe.cs.autoquest.tasktrees.treeifc.DefaultTaskTraversingVisitor; 
    2626import de.ugoe.cs.autoquest.tasktrees.treeifc.IEventTask; 
     
    2828import de.ugoe.cs.autoquest.tasktrees.treeifc.IIteration; 
    2929import de.ugoe.cs.autoquest.tasktrees.treeifc.IMarkingTemporalRelationship; 
     30import de.ugoe.cs.autoquest.tasktrees.treeifc.IOptional; 
    3031import de.ugoe.cs.autoquest.tasktrees.treeifc.ISelection; 
     32import de.ugoe.cs.autoquest.tasktrees.treeifc.ISequence; 
    3133import de.ugoe.cs.autoquest.tasktrees.treeifc.IStructuringTemporalRelationship; 
    3234import de.ugoe.cs.autoquest.tasktrees.treeifc.ITask; 
     
    5254     
    5355    /** 
     56     * default indicator for unequal tasks 
     57     */ 
     58    public static final SimilarTasks UNEQUAL_TASKS = new SimilarTasks(null, null, null); 
     59     
     60    /** 
    5461     * result of the string like comparison of both task traversals 
    5562     */ 
     
    8592     */ 
    8693    public SimilarTasks(Patch         patch, 
    87                         ITask         task1, 
    8894                        TaskTraversal traversal1, 
    89                         ITask         task2, 
    9095                        TaskTraversal traversal2) 
    9196    { 
    92         this.leftHandSide = task1; 
     97        if (traversal1 != null) { 
     98            this.leftHandSide = traversal1.getTask(); 
     99        } 
     100         
    93101        this.leftHandSideTraversal = traversal1; 
    94         this.rightHandSide = task2; 
     102         
     103        if (traversal2 != null) { 
     104            this.rightHandSide = traversal2.getTask(); 
     105        } 
     106         
    95107        this.rightHandSideTraversal = traversal2; 
    96108         
     
    107119     * static convenience method to compare two tasks 
    108120     */ 
    109     public static SimilarTasks compareTasks(ITask                  task1, 
    110                                             ITask                  task2, 
    111                                             TaskInstanceComparator comparator) 
     121    public static SimilarTasks compareTasks(ITask          task1, 
     122                                            ITask          task2, 
     123                                            TaskComparator comparator) 
    112124    { 
    113         return compareTasks(task1, task2, comparator, null, true /* never set to false as a common 
    114                                                                  path may occur several times 
    115                                                                  at distinct places in a traversal 
    116                                                                  and once it may be part of a delta 
    117                                                                  and once not */); 
     125        return compareTasks(task1, task2, comparator, null); 
    118126    } 
    119127 
    120128    /** 
    121129     * static convenience method to compare two tasks but ignoring a given set of subtasks when 
    122      * creating the traversals. Furhtermore, it can be defined, if subtasks occurring in both 
    123      * similar tasks are traversed or not. 
    124      */ 
    125     public static SimilarTasks compareTasks(ITask                  task1, 
    126                                             ITask                  task2, 
    127                                             TaskInstanceComparator comparator, 
    128                                             List<TaskPath>         pathsNotToTraverse, 
    129                                             boolean                traverseCommonPaths) 
     130     * creating the traversals. 
     131     */ 
     132    public static SimilarTasks compareTasks(ITask          task1, 
     133                                            ITask          task2, 
     134                                            TaskComparator comparator, 
     135                                            List<TaskPath> pathsNotToTraverse) 
    130136    { 
    131         Set<ITask> commonInvolvedTasks; 
    132  
    133         if (traverseCommonPaths) { 
    134             commonInvolvedTasks = new HashSet<ITask>(); 
    135         } 
    136         else { 
    137             commonInvolvedTasks = getCommonInvolvedTasks(task1, task2); 
    138         } 
    139  
    140         TaskTraversal traversal1 = 
    141              TaskTraversal.getTraversal(task1, commonInvolvedTasks, pathsNotToTraverse); 
    142          
    143         TaskTraversal traversal2 = 
    144              TaskTraversal.getTraversal(task2, commonInvolvedTasks, pathsNotToTraverse); 
     137        TaskTraversal traversal1 = TaskTraversal.getTraversal(task1, pathsNotToTraverse); 
     138        TaskTraversal traversal2 = TaskTraversal.getTraversal(task2, pathsNotToTraverse); 
    145139 
    146140        if ((traversal1.size() <= 0) || (traversal2.size() <= 0)) { 
    147141            return null; 
    148142        } 
    149  
     143         
     144        return compareTraversals(traversal1, traversal2, comparator); 
     145    } 
     146 
     147    /** 
     148     * <p> 
     149     * TODO: comment 
     150     * </p> 
     151     * 
     152     * @param traversal1 
     153     * @param traversal2 
     154     * @param comparator 
     155     * @return 
     156     */ 
     157    public static SimilarTasks compareTraversals(TaskTraversal  traversal1, 
     158                                                 TaskTraversal  traversal2, 
     159                                                 TaskComparator comparator) 
     160    { 
    150161        Patch patch = new TaskTraversalMyersDiff(comparator).getDiff(traversal1, traversal2); 
    151162 
    152         SimilarTasks result = new SimilarTasks(patch, task1, traversal1, task2, traversal2); 
     163        SimilarTasks result = new SimilarTasks(patch, traversal1, traversal2); 
    153164 
    154165        return result; 
     
    161172     * the remaining traversals can be the basis of a merge. 
    162173     */ 
    163     public static SimilarTasks getMergableLevelOfSimilarity(SimilarTasks           source, 
    164                                                             TaskInstanceComparator comparator) 
     174    public static SimilarTasks getMergableLevelOfSimilarity(SimilarTasks   source, 
     175                                                            TaskComparator comparator) 
    165176    { 
    166177        SimilarTasks similarTasks = source; 
     
    175186            similarTasks = compareTasks 
    176187                (similarTasks.getLeftHandSide(), similarTasks.getRightHandSide(), 
    177                  comparator, pathsToIgnore, true); 
    178  
    179             similarTasks.dump(System.out); 
     188                 comparator, pathsToIgnore); 
     189 
     190            // similarTasks.dump(System.out); 
    180191             
    181192            List<TaskPath> furtherPathsToIgnore = similarTasks.getPathsToIgnore(); 
    182193             
    183             for (TaskPath path : furtherPathsToIgnore) { 
    184                 System.out.println(path); 
    185             } 
     194            // System.out.println("further paths to ignore:"); 
     195            // for (TaskPath path : furtherPathsToIgnore) { 
     196            //     System.out.println("  " + path); 
     197            // } 
    186198             
    187199            for (TaskPath pathToAdd : furtherPathsToIgnore) { 
     
    201213        while (pathsToIgnore.size() > prevPathsToIgnoreCount); 
    202214         
    203         return similarTasks; 
     215        if (similarTasks.isStillWellAligned()) { 
     216            return similarTasks; 
     217        } 
     218        else { 
     219            // this may happen, if due to interleaving iterations the similarities of the task 
     220            // move and the diff algorithm does not align them anymore as optimal as possible 
     221            // because some similarities were lost due to not comparing all paths anymore.  
     222            return null; 
     223        } 
    204224    } 
    205225 
     
    242262         
    243263        return deltas.size() > 0; 
     264    } 
     265 
     266    /** 
     267     * <p> 
     268     * TODO: comment 
     269     * </p> 
     270     * 
     271     * @return 
     272     */ 
     273    public boolean isStillWellAligned() { 
     274        if (isInBetweenDifference()) { 
     275            return true; 
     276        } 
     277        else { 
     278            for (Delta delta : patch.getDeltas()) { 
     279                if (delta.getType() == Delta.TYPE.INSERT) { 
     280                    if ((delta.getOriginal().getPosition() == 0) || 
     281                        (delta.getOriginal().getPosition() == leftHandSideTraversal.size())) 
     282                    { 
     283                        return false; 
     284                    } 
     285                } 
     286                else if (delta.getType() == Delta.TYPE.DELETE) { 
     287                    if ((delta.getRevised().getPosition() == 0) || 
     288                        (delta.getRevised().getPosition() == rightHandSideTraversal.size())) 
     289                    { 
     290                        return false; 
     291                    } 
     292                } 
     293            } 
     294        } 
     295         
     296        return true; 
    244297    } 
    245298     
     
    328381            } 
    329382             
     383            // check for any parent optional that may be empty and can hence not be flattened 
     384            TaskPath tmppath = new TaskPath(); 
     385            tmppath.add(leftHandSide, 0); 
     386            getParentOptionals(tmppath, result); 
     387            tmppath = new TaskPath(); 
     388            tmppath.add(rightHandSide, 0); 
     389            getParentOptionals(tmppath, result); 
     390             
    330391            // check if there are common subtasks on both sides that lie outside any delta and 
    331392            // that hence should be ignored (especially when performing flattening of task 
    332             // instances later with the goal to preserve as many subtasks and respective instances 
     393            // instances later with the goal to preserve as many subtasks and respective instances) 
    333394            int deltaIndex = 0; 
    334395            int leftTraversalIndex = 0; 
     
    823884                        (path2.get(j).getTask() instanceof IIteration)) 
    824885                    { 
    825                         System.out.println("found paths to real intersecting parents"); 
    826                         int[] indexBuf = leftHandSideTraversal.getIndexesRootedBy(path1Prefix); 
    827                         System.out.println(idxsPath1[0] + "(" + indexBuf[0] + ")  " + idxsPath1[1] + 
    828                                            "(" + indexBuf[1] + ")  " + path1Prefix); 
    829                         indexBuf = rightHandSideTraversal.getIndexesRootedBy(path2Prefix); 
    830                         System.out.println(idxsPath2[0] + "(" + indexBuf[0] + ")  " + idxsPath2[1] + 
    831                                            "(" + indexBuf[1] + ")  " + path2Prefix); 
     886                        // System.out.println("found paths to real intersecting parents"); 
     887                        // int[] indexBuf = leftHandSideTraversal.getIndexesRootedBy(path1Prefix); 
     888                        // System.out.println(idxsPath1[0] + "(" + indexBuf[0] + ")  " + idxsPath1[1] + 
     889                        //                    "(" + indexBuf[1] + ")  " + path1Prefix); 
     890                        // indexBuf = rightHandSideTraversal.getIndexesRootedBy(path2Prefix); 
     891                        // System.out.println(idxsPath2[0] + "(" + indexBuf[0] + ")  " + idxsPath2[1] + 
     892                        //                    "(" + indexBuf[1] + ")  " + path2Prefix); 
    832893                         
    833894                        paths.add(path1Prefix); 
     
    854915                    if (!commonPath.get(j).equals(comparePath.get(j))) { 
    855916                        while (commonPath.size() > j) { 
    856                             commonPath.remove(j); 
     917                            commonPath.removeLast(); 
    857918                        } 
    858919                        break; 
     
    9571018                        (indexes[1] < (chunk.getPosition() + chunk.size()))) // ends in the delta 
    9581019                    { 
    959                         System.out.println("found path to parent task lieing completely in the " + 
    960                                            "delta: " + path.subPath(0, i + 1)); 
     1020                        // System.out.println("found path to parent task lieing completely in the " + 
     1021                        //                    "delta: " + path.subPath(0, i + 1)); 
    9611022                        result.add(path.subPath(0, i + 1)); 
    9621023                        break; 
     
    9641025                } 
    9651026            } 
     1027        } 
     1028    } 
     1029 
     1030    /** 
     1031     * 
     1032     */ 
     1033    private void getParentOptionals(TaskPath taskPath, List<TaskPath> result) { 
     1034        ITask task = taskPath.getLast(); 
     1035         
     1036        if (task instanceof IOptional) { 
     1037            result.add(new TaskPath(taskPath)); 
     1038        } 
     1039        else if (task instanceof ISequence) { 
     1040            for (int i = 0; i < ((ISequence) task).getChildren().size(); i++) { 
     1041                taskPath.add(((ISequence) task).getChildren().get(i), i); 
     1042                getParentOptionals(taskPath, result); 
     1043                taskPath.removeLast(); 
     1044            } 
     1045        } 
     1046        else if (task instanceof ISelection) { 
     1047            for (int i = 0; i < ((ISelection) task).getChildren().size(); i++) { 
     1048                taskPath.add(((ISelection) task).getChildren().get(i), 0); 
     1049                getParentOptionals(taskPath, result); 
     1050                taskPath.removeLast(); 
     1051            } 
     1052        } 
     1053        else if (task instanceof IIteration) { 
     1054            taskPath.add(((IIteration) task).getMarkedTask(), 0); 
     1055            getParentOptionals(taskPath, result); 
     1056            taskPath.removeLast(); 
    9661057        } 
    9671058    } 
Note: See TracChangeset for help on using the changeset viewer.