Changeset 813 for trunk


Ignore:
Timestamp:
09/14/12 12:06:37 (12 years ago)
Author:
pharms
Message:
  • improved iteration detection to merge iterated subsequences to a minimal subtree
  • improved iteration detection to also work, if the iterated sublists have different lengths but whose semantic is the same (e.g. if the same text is entered using different key combinations)
File:
1 edited

Legend:

Unmodified
Added
Removed

  • trunk/quest-core-tasktrees/src/main/java/de/ugoe/cs/quest/tasktrees/temporalrelation/DefaultIterationDetectionRule.java

    r805 r813  
    66import de.ugoe.cs.quest.tasktrees.nodeequality.NodeEquality; 
    77import de.ugoe.cs.quest.tasktrees.nodeequality.NodeEqualityRuleManager; 
     8import de.ugoe.cs.quest.tasktrees.treeifc.IEventTask; 
    89import de.ugoe.cs.quest.tasktrees.treeifc.IIteration; 
    910import de.ugoe.cs.quest.tasktrees.treeifc.ISelection; 
    … …  
    1415 
    1516/** 
    16  * TODO comment 
     17 * <p> 
     18 * iterations in a list of nodes are equal subsequences following each other directly. The 
     19 * subsequences can be of any length depending on the type of equality they need to have. If the 
     20 * subsequences have to be lexically equal, then they have to have the same length if they only 
     21 * contain event tasks. As an example entering text can be done through appropriate keystrokes or 
     22 * through pasting the text. As a result, two syntactically different sequences are semantically 
     23 * equal. If both follow each other, then they are an iteration of semantically equal children. 
     24 * But they are not lexically equal. 
     25 * </p> 
     26 * <p> 
     27 * This class determines equal subsequences following each other. It is provided with a minimal node 
     28 * equality the equal nodes should have. Through this, it is possible to find e.g. lexically 
     29 * equal subsequence through a first application of this rule and semantically equal children to  
     30 * a later application of this rule. This is used by the {@link TemporalRelationshipRuleManager} 
     31 * which instantiates this rule three times, each with a different minimal equality. 
     32 * </p> 
     33 * <p> 
     34 * The equal subsequences are determined through trial and error. This algorithm has a high effort 
     35 * as it tries in the worst case all possible combinations of sub lists in all possible parts of 
     36 * the list of children of a provided parent node. The steps for each trial are. 
     37 * <ul> 
     38 *   <li>for all possible subparts of the children of the provided parent 
     39 *   <ul> 
     40 *     <li>for all possible first sublists in the subpart 
     41 *     <ul> 
     42 *       <li>for all succeeding next sublists in this part</li> 
     43 *       <ul> 
     44 *         <li>check if this sublist is equal to all previously identified sublist in this part</li> 
     45 *       </ul> 
     46 *     </ul> 
     47 *     <li> 
     48 *       if a combination of sublists is found in this subpart which are all equal to each other 
     49 *       at the provided minimal equality level, an iteration in this subpart was found. 
     50 *     </li> 
     51 *       <ul> 
     52 *         <li>merge the identified equal sublists to an iteration</li> 
     53 *       </ul> 
     54 *   </ul> 
     55 * </ul> 
     56 * The algorithm tries to optimize if all children are event tasks and if the sublists shall be 
     57 * lexically equal. In this case, the sublist all have to have the same length. The trial and 
     58 * error reduces to a minimum of possible sublists. 
     59 * </p> 
    1760 *  
    18  * @version $Revision: $ $Date: 19.02.2012$ 
    19  * @author 2012, last modified by $Author: patrick$ 
     61 * @author Patrick Harms 
    2062 */ 
    2163public class DefaultIterationDetectionRule implements TemporalRelationshipRule { 
    2264     
    23     /** */ 
     65    /** 
     66     * <p> 
     67     * the node equality manager needed for comparing task tree nodes with each other 
     68     * </p> 
     69     */ 
    2470    private NodeEqualityRuleManager nodeEqualityRuleManager; 
    2571 
    26     /** */ 
     72    /** 
     73     * <p> 
     74     * the minimal node equality two identified sublists need to have to consider them as equal 
     75     * and to create an iteration for 
     76     * </p> 
     77     */ 
    2778    private NodeEquality minimalNodeEquality; 
    2879 
    2980    /** 
    30      * TODO: comment 
    31      *  
     81     * <p> 
     82     * instantiates the rule and initializes it with a node equality rule manager and the minimal 
     83     * node equality identified sublist must have to consider them as iterated. 
     84     * </p> 
    3285     */ 
    3386    DefaultIterationDetectionRule(NodeEqualityRuleManager nodeEqualityRuleManager, 
    … …  
    54107        } 
    55108 
     109        if (!finalize) { 
     110            // the rule is always feasible as iterations may occur at any time 
     111            RuleApplicationResult result = new RuleApplicationResult(); 
     112            result.setRuleApplicationStatus(RuleApplicationStatus.RULE_APPLICATION_FEASIBLE); 
     113            return result; 
     114        } 
     115 
    56116        // parent must already have at least 2 children 
    57117        if ((parent.getChildren() == null) || (parent.getChildren().size() < 2)) { 
    58118            return null; 
    59119        } 
    60  
    61         // iterations represent as a list of nodes that splits up in several equal sublists. If 
    62         // the remaining nodes also start an equal sublist, then the iteration may not be completed 
    63         // yet. So wait for further events to only identify completed iterations. 
    64  
     120         
     121         
    65122        // to find longer iterations first, start with long sequences 
    66         for (int end = parent.getChildren().size() - 1; end > 0; end--) { 
     123        SubSequences subSequences = getEqualSubsequences(parent, treeBuilder, nodeFactory); 
     124 
     125        if (subSequences != null) { 
     126            RuleApplicationResult result = new RuleApplicationResult(); 
     127 
     128            mergeEqualNodes(subSequences.equalVariants, treeBuilder, nodeFactory); 
     129            IIteration newIteration = createIterationBasedOnIdentifiedVariants 
     130                (subSequences, treeBuilder, nodeFactory, result); 
     131 
     132            determineNewlyCreatedParentTasks(parent, newIteration, result); 
     133             
     134            // remove iterated children 
     135            for (int j = subSequences.start; j < subSequences.end; j++) { 
     136                treeBuilder.removeChild((ISequence) parent, subSequences.start); 
     137            } 
     138 
     139            // add the new iteration instead 
     140            treeBuilder.addChild((ISequence) parent, subSequences.start, newIteration); 
     141 
     142            result.setRuleApplicationStatus(RuleApplicationStatus.RULE_APPLICATION_FINISHED); 
     143            return result; 
     144        } 
     145 
     146        return null; 
     147    } 
     148 
     149    /** 
     150     * <p> 
     151     * this method initiates the trial and error algorithm denoted in the description of this class. 
     152     * Its main purpose is the selection of a subpart of all children in the parent node in which 
     153     * equal sublists shall be searched. It is important, to always find the last iterations in a 
     154     * part first. The reason for this are iterations of iterations. If we always found the first 
     155     * iteration in a subpart first, then this may be an iteration of iterations. However, there 
     156     * may be subsequent iterations to be included in this iteration. But these iterations are not 
     157     * found yet, as they occur later in the sequence. Therefore, if we always find the last 
     158     * iteration in a sequence first, iterations of iterations are identified, last. 
     159     * </p> 
     160     *  
     161     * @param parent      the parent node in which iterations of children shall be found 
     162     * @param treeBuilder the tree builder that can be used for connecting task tree nodes 
     163     * @param nodeFactory the node factory that can be used for instantiating task tree nodes 
     164     *  
     165     * @return the iterated subsequences identified in a specific part (contains the equal 
     166     *         subsequences as well as the start (inclusive) and end (exclusive) index of the 
     167     *         subpart in which the sequences were found)  
     168     */ 
     169    private SubSequences getEqualSubsequences(ITaskTreeNode        parent, 
     170                                              ITaskTreeBuilder     treeBuilder, 
     171                                              ITaskTreeNodeFactory nodeFactory) 
     172    { 
     173        SubSequences subSequences = null; 
     174 
     175        FIND_ITERATION: 
     176        for (int end = parent.getChildren().size(); end > 0; end--) { 
    67177            for (int start = 0; start < end; start++) { 
    68                 List<ITaskTreeNode[]> equalVariants = 
    69                     getEqualSublistVariantsInBoundaries(parent, start, end); 
    70  
    71                 if (equalVariants != null) { 
    72                     RuleApplicationResult result = new RuleApplicationResult(); 
    73                      
    74                     if ((!finalize) && (iterationMayContinue(equalVariants, parent, end + 1))) { 
    75                         result.setRuleApplicationStatus 
    76                               (RuleApplicationStatus.RULE_APPLICATION_FEASIBLE); 
    77                         return result; 
    78                     } 
    79  
    80                     IIteration newIteration = createIterationBasedOnIdentifiedVariants 
    81                          (equalVariants, treeBuilder, nodeFactory, result); 
    82                      
    83  
    84                     // remove iterated children 
    85                     for (int j = end; j >= start; j--) { 
    86                         treeBuilder.removeChild((ISequence) parent, j); 
    87                     } 
    88  
    89                     // add the new iteration instead 
    90                     treeBuilder.addChild((ISequence) parent, start, newIteration); 
    91  
    92                     result.setRuleApplicationStatus 
    93                         (RuleApplicationStatus.RULE_APPLICATION_FINISHED); 
    94                     return result; 
    95                 } 
    96             } 
    97         } 
    98  
    99         return null; 
    100     } 
    101  
    102     /** 
    103      * TODO: comment 
    104      *  
    105      * @return 
    106      */ 
    107     private List<ITaskTreeNode[]> getEqualSublistVariantsInBoundaries(ITaskTreeNode parent, 
    108                                                                       int           start, 
    109                                                                       int           end) 
    110     { 
    111         List<ITaskTreeNode[]> equalVariants = null; 
    112  
    113         int noOfChildrenInBoundaries = end - start + 1; 
    114  
    115         for (int subListLen = 1; subListLen <= (noOfChildrenInBoundaries / 2); subListLen++) 
    116         { 
    117             if ((noOfChildrenInBoundaries % subListLen) == 0) { 
    118                 equalVariants = 
    119                     getEqualSublistVariantsForSubListLength(parent, start, end, subListLen); 
    120  
    121                 if (equalVariants != null) { 
    122                     return equalVariants; 
    123                 } 
    124             } 
    125         } 
    126  
    127         return null; 
    128     } 
    129  
    130     /** 
     178                boolean useEqualSublistLengths = equalSublistLengthsCanBeUsed(parent, start, end); 
     179 
     180                subSequences = new SubSequences(); 
     181                subSequences.start = start; 
     182 
     183                boolean foundFurtherVariants = findFurtherVariants 
     184                    (subSequences, parent, start, end, treeBuilder, nodeFactory, 
     185                     useEqualSublistLengths); 
     186 
     187                if (foundFurtherVariants) { 
     188                    break FIND_ITERATION; 
     189                } 
     190                else { 
     191                    subSequences = null; 
     192                } 
     193            } 
     194        } 
     195         
     196        return subSequences; 
     197    } 
     198 
     199    /** 
     200     * <p> 
     201     * for optimization purposes, we check if the length of the sublists to be identified as 
     202     * iterations has to be the same for any sublist. This only applies, if the minimum node 
     203     * equality to be checked for is lexical equality. If the children of the parent are all event 
     204     * tasks, then sublists can only be lexically equal, if they all have the same length. 
     205     * Therefore we check, if the minimal node equality is lexical equality. And if so, we also 
     206     * check if all children of the parent in which an iteration shall be searched for are event 
     207     * tasks. 
     208     * </p> 
    131209     * 
    132      */ 
    133     private List<ITaskTreeNode[]> getEqualSublistVariantsForSubListLength(ITaskTreeNode parent, 
    134                                                                           int           start, 
    135                                                                           int           end, 
    136                                                                           int           subListLen) 
    137     { 
    138         List<ITaskTreeNode[]> equalVariants = new ArrayList<ITaskTreeNode[]>(); 
    139         ITaskTreeNode[] firstVariant = new ITaskTreeNode[subListLen]; 
    140  
    141         for (int i = 0; i < subListLen; i++) { 
    142             firstVariant[i] = parent.getChildren().get(start + i); 
    143         } 
    144  
    145         equalVariants.add(firstVariant); 
    146  
    147         for (int parentIdx = (start + subListLen); parentIdx <= end; parentIdx += subListLen) 
    148         { 
    149             ITaskTreeNode[] otherVariant = new ITaskTreeNode[subListLen]; 
    150  
    151             for (int i = 0; i < subListLen; i++) { 
    152                 NodeEquality nodeEquality = nodeEqualityRuleManager.applyRules 
    153                     (firstVariant[i], parent.getChildren().get(parentIdx + i)); 
    154  
     210     * @param parent the parent node to search for iterations of its children 
     211     * @param start  the beginning of the subpart (inclusive) to be considered 
     212     * @param end    the end of the subpart (exclusive) to be considered 
     213     *  
     214     * @return true, if the sublists must have the same lengths, false else 
     215     */ 
     216    private boolean equalSublistLengthsCanBeUsed(ITaskTreeNode parent, int start, int end) { 
     217        boolean equalLengthsCanBeUsed = minimalNodeEquality.isAtLeast(NodeEquality.LEXICALLY_EQUAL); 
     218         
     219        if (equalLengthsCanBeUsed) { 
     220            for (int i = start; i < end; i++) { 
     221                if (!(parent.getChildren().get(i) instanceof IEventTask)) { 
     222                    equalLengthsCanBeUsed = false; 
     223                    break; 
     224                } 
     225            } 
     226        } 
     227 
     228        return equalLengthsCanBeUsed; 
     229    } 
     230 
     231    /** 
     232     * <p> 
     233     * this method starts at a specific position in the list of children of the provided parent 
     234     * and checks, if it finds a further sublist, that matches the already found sublists. If 
     235     * the sublist lengths must be equal, it only searches for a sublist of the same length of the 
     236     * already found sublists. The method calls itself if it identifies a further equal sublist but 
     237     * if the end of the subpart of children is not yet reached. 
     238     * </p> 
     239     *  
     240     * @param subSequences           the sublist found so far against which equality of the next 
     241     *                               sublist must be checked 
     242     * @param parent                 the parent node of which the children are analyzed 
     243     * @param start                  the starting index from which to start the next sublist to be 
     244     *                               identified 
     245     * @param end                    the end index (exclusive) of the current subpart of children 
     246     *                               in which iterations are searched for 
     247     * @param treeBuilder            the tree builder that can be used for connecting task tree 
     248     *                               nodes 
     249     * @param nodeFactory            the node factory that can be used for instantiating task tree 
     250     *                               nodes 
     251     * @param useEqualSublistLengths true if the sublists to be searched for all need to have the 
     252     *                               same length 
     253     *  
     254     * @return true if a further equal variant was found, false else 
     255     */ 
     256    private boolean findFurtherVariants(SubSequences         subSequences, 
     257                                        ITaskTreeNode        parent, 
     258                                        int                  start, 
     259                                        int                  end, 
     260                                        ITaskTreeBuilder     treeBuilder, 
     261                                        ITaskTreeNodeFactory nodeFactory, 
     262                                        boolean              useEqualSublistLengths) 
     263    { 
     264        boolean foundFurtherVariants = (start == end) && (subSequences.equalVariants.size() > 1); 
     265         
     266        int minChildCount = 1; 
     267        int maxChildCount = end - start; 
     268         
     269        if (useEqualSublistLengths && (subSequences.equalVariants.size() > 0)) { 
     270            minChildCount = subSequences.equalVariants.get(0).getChildren().size(); 
     271            maxChildCount = Math.min(minChildCount, maxChildCount); 
     272        } 
     273         
     274        for (int childCount = minChildCount; childCount <= maxChildCount; childCount++) { 
     275            if (useEqualSublistLengths && (((end - start) % childCount) != 0)) { 
     276                continue; 
     277            } 
     278             
     279            ISequence furtherVariant = nodeFactory.createNewSequence(); 
     280             
     281            for (int j = start; j < start + childCount; j++) { 
     282                treeBuilder.addChild(furtherVariant, parent.getChildren().get(j)); 
     283            } 
     284             
     285            boolean allVariantsEqual = true; 
     286             
     287            for (ITaskTreeNode equalVariant : subSequences.equalVariants) { 
     288                NodeEquality nodeEquality = 
     289                    nodeEqualityRuleManager.applyRules(equalVariant, furtherVariant); 
     290                 
    155291                if (!nodeEquality.isAtLeast(minimalNodeEquality)) { 
    156                     return null; 
    157                 } 
    158                 else if (!nodeEquality.isAtLeast(NodeEquality.LEXICALLY_EQUAL)) { 
    159                     // if the node is a syntactical or semantical equivalent of the first variant, 
    160                     // then store it. 
    161                     otherVariant[i] = parent.getChildren().get(parentIdx + i); 
    162                 } 
    163             } 
    164  
    165             // check, if there is a syntactically or semantically equal other variant. If so, add 
    166             // it to the list of variants 
    167             boolean semanticallyUnequal = false; 
    168             for (int i = 0; i < subListLen; i++) { 
    169                 if (otherVariant[i] == null) { 
    170                     otherVariant[i] = firstVariant[i]; 
     292                    allVariantsEqual = false; 
     293                    break; 
     294                } 
     295            } 
     296             
     297            if (allVariantsEqual) { 
     298                 
     299                // we found a further variant. Add it to the list of variants and try to find 
     300                // further variants. Ignore, if none is available 
     301                int index = subSequences.equalVariants.size(); 
     302                subSequences.equalVariants.add(index, furtherVariant); 
     303                 
     304                foundFurtherVariants = findFurtherVariants 
     305                    (subSequences, parent, start + childCount, end, treeBuilder, nodeFactory, 
     306                     useEqualSublistLengths); 
     307 
     308                if (foundFurtherVariants) { 
     309                    subSequences.end = end; 
     310                    break; 
    171311                } 
    172312                else { 
    173                     semanticallyUnequal = true; 
    174                 } 
    175             } 
    176  
    177             if (semanticallyUnequal) { 
    178                 equalVariants.add(otherVariant); 
    179             } 
    180         } 
    181  
    182         return equalVariants; 
    183     } 
    184  
    185     /** 
    186      * <p> 
    187      * TODO: comment 
     313                    subSequences.equalVariants.remove(index); 
     314                } 
     315            } 
     316        } 
     317         
     318        return foundFurtherVariants; 
     319    } 
     320 
     321    /** 
     322     * <p> 
     323     * this method merges task tree nodes in a list, if they can be merged. for this, it tries 
     324     * to merge every node with every other node in the provided list using the 
     325     * {@link #mergeEqualTasks(ITaskTreeNode, ITaskTreeNode, ITaskTreeBuilder, ITaskTreeNodeFactory)} 
     326     * method. If a merge is possible, it removes the merged nodes from the list and adds the 
     327     * merge result.  
    188328     * </p> 
    189329     * 
    190      * @param equalVariants 
    191      * @param parent 
    192      * @return 
    193      */ 
    194     private boolean iterationMayContinue(List<ITaskTreeNode[]> equalVariants, 
    195                                          ITaskTreeNode         parent, 
    196                                          int                   remainderIndex) 
    197     { 
    198         // check, if the iteration may go on. This may be the case, if the 
    199         // remaining children, which were not identified as part of the iteration, 
    200         // start a further occurrence of the iteration 
    201  
    202         boolean allNodesEqual = true; 
    203         for (int i = 0; ((allNodesEqual) && (i < equalVariants.get(0).length)); i++) 
    204         { 
    205             if ((remainderIndex + i) >= parent.getChildren().size()) { 
    206                 break; 
    207             } 
    208  
    209             NodeEquality nodeEquality = nodeEqualityRuleManager.applyRules 
    210                 (equalVariants.get(0)[i], parent.getChildren().get(remainderIndex + i)); 
    211  
    212             allNodesEqual &= nodeEquality.isAtLeast(minimalNodeEquality); 
    213         } 
    214  
    215         return allNodesEqual; 
    216     } 
    217      
    218     /** 
    219      * <p> 
    220      * TODO: comment 
     330     * @param nodes       the list of nodes to be merged 
     331     * @param treeBuilder the tree builder that can be used for connecting task tree nodes 
     332     * @param nodeFactory the node factory that can be used for instantiating task tree nodes 
     333     */ 
     334    private void mergeEqualNodes(List<ITaskTreeNode>   nodes, 
     335                                 ITaskTreeBuilder      treeBuilder, 
     336                                 ITaskTreeNodeFactory  nodeFactory) 
     337    { 
     338        int index1 = 0; 
     339        int index2 = 0; 
     340        ITaskTreeNode variant1; 
     341        ITaskTreeNode variant2; 
     342         
     343        while (index1 < nodes.size()) { 
     344            variant1 = nodes.get(index1); 
     345            index2 = index1 + 1; 
     346             
     347            while (index2 < nodes.size()) { 
     348                variant2 = nodes.get(index2); 
     349                ITaskTreeNode mergedChild = 
     350                    mergeEqualTasks(variant1, variant2, treeBuilder, nodeFactory); 
     351                 
     352                if (mergedChild != null) { 
     353                    // if we merged something start from the beginning to perform the next merge 
     354                    nodes.remove(index2); 
     355                    nodes.remove(index1); 
     356                    nodes.add(index1, mergedChild); 
     357                    index1 = -1; 
     358                    break; 
     359                } 
     360                else { 
     361                    index2++; 
     362                } 
     363            } 
     364             
     365            index1++; 
     366        } 
     367    } 
     368 
     369    /** 
     370     * <p> 
     371     * this method merges two equal tasks with each other if possible. If the tasks are lexically 
     372     * equal, the first of them is returned as merge result. If both tasks are of the same 
     373     * temporal relationship type, the appropriate merge method is called to merge them. If one 
     374     * of the nodes is a selection, the other one is added as a variant of this selection. 
     375     * (However, if both nodes are selections, they are merged using the appropriate merge method.) 
     376     * If merging is not possible, then a selection of both provided nodes is created and 
     377     * returned as merge result. 
    221378     * </p> 
    222379     * 
    223      * @param equalVariants 
    224      * @param result 
    225      * @return 
    226      */ 
    227     private IIteration createIterationBasedOnIdentifiedVariants(List<ITaskTreeNode[]> equalVariants, 
     380     * @param node1       the first task to be merged 
     381     * @param node2       the second task to be merged 
     382     * @param treeBuilder the tree builder that can be used for connecting task tree nodes 
     383     * @param nodeFactory the node factory that can be used for instantiating task tree nodes 
     384     *  
     385     * @return the result of the merge 
     386     */ 
     387    private ITaskTreeNode mergeEqualTasks(ITaskTreeNode         node1, 
     388                                          ITaskTreeNode         node2, 
     389                                          ITaskTreeBuilder      treeBuilder, 
     390                                          ITaskTreeNodeFactory  nodeFactory) 
     391    { 
     392        ITaskTreeNode mergeResult = null; 
     393        NodeEquality nodeEquality = nodeEqualityRuleManager.applyRules(node1, node2); 
     394         
     395        if (nodeEquality.isAtLeast(NodeEquality.LEXICALLY_EQUAL)) { 
     396            mergeResult = node1; 
     397        } 
     398        else { 
     399            if ((node1 instanceof ISequence) && (node2 instanceof ISequence)) { 
     400                mergeResult = mergeEqualSequences 
     401                    ((ISequence) node1, (ISequence) node2, treeBuilder, nodeFactory); 
     402            } 
     403            else if ((node1 instanceof ISelection) && (node2 instanceof ISelection)) { 
     404                mergeResult = mergeEqualSelections 
     405                    ((ISelection) node1, (ISelection) node2, treeBuilder, nodeFactory); 
     406            } 
     407            else if ((node1 instanceof IIteration) && (node2 instanceof IIteration)) { 
     408                mergeResult = mergeEqualIterations 
     409                    ((IIteration) node1, (IIteration) node2, treeBuilder, nodeFactory); 
     410            } 
     411            else if (node1 instanceof ISelection) { 
     412                treeBuilder.addChild((ISelection) node1, node2); 
     413                mergeResult = node1; 
     414            } 
     415            else if (node2 instanceof ISelection) { 
     416                treeBuilder.addChild((ISelection) node2, node1); 
     417                mergeResult = node2; 
     418            } 
     419        } 
     420         
     421        if (mergeResult == null) { 
     422            mergeResult = nodeFactory.createNewSelection(); 
     423            treeBuilder.addChild((ISelection) mergeResult, node1); 
     424            treeBuilder.addChild((ISelection) mergeResult, node2); 
     425        } 
     426         
     427        return mergeResult; 
     428    } 
     429 
     430    /** 
     431     * <p> 
     432     * merges equal sequences. This is done through trying to merge each node of sequence 1 with 
     433     * the node in sequence 2 being located at the same position. If not all children can be merged 
     434     * or if the sequences have different lengths, null is returned to indicate, that merging is 
     435     * not possible. For merging children, the 
     436     * {@link #mergeEqualTasks(ITaskTreeNode, ITaskTreeNode, ITaskTreeBuilder, ITaskTreeNodeFactory)} 
     437     * method is called. 
     438     * </p> 
     439     * 
     440     * @param sequence1   the first sequence to be merged 
     441     * @param sequence2   the second sequence to be merged 
     442     * @param treeBuilder the tree builder that can be used for connecting task tree nodes 
     443     * @param nodeFactory the node factory that can be used for instantiating task tree nodes 
     444     *  
     445     * @return the result of the merge or null if merging was not possible 
     446     */ 
     447    private ISequence mergeEqualSequences(ISequence             sequence1, 
     448                                          ISequence             sequence2, 
     449                                          ITaskTreeBuilder      treeBuilder, 
     450                                          ITaskTreeNodeFactory  nodeFactory) 
     451    { 
     452        ISequence mergeResult = null; 
     453         
     454        if (sequence1.getChildren().size() == sequence2.getChildren().size()) { 
     455            mergeResult = nodeFactory.createNewSequence(); 
     456             
     457            for (int i = 0; i < sequence1.getChildren().size(); i++) { 
     458                ITaskTreeNode mergedNode = mergeEqualTasks 
     459                    (sequence1.getChildren().get(i), sequence2.getChildren().get(i), 
     460                     treeBuilder, nodeFactory); 
     461                 
     462                if (mergedNode != null) { 
     463                    treeBuilder.addChild(mergeResult, mergedNode); 
     464                } 
     465                else { 
     466                    mergeResult = null; 
     467                    break; 
     468                } 
     469            } 
     470        } 
     471         
     472        return mergeResult; 
     473    } 
     474 
     475    /** 
     476     * <p> 
     477     * merges equal selections. This is done through trying to merge each node of selections with 
     478     * each other. For this, the method 
     479     * {@link #mergeEqualNodes(List, ITaskTreeBuilder, ITaskTreeNodeFactory)} is called with a 
     480     * join of the child list of both selections. 
     481     * </p> 
     482     * 
     483     * @param selection1  the first selection to be merged 
     484     * @param selection2  the second selection to be merged 
     485     * @param treeBuilder the tree builder that can be used for connecting task tree nodes 
     486     * @param nodeFactory the node factory that can be used for instantiating task tree nodes 
     487     *  
     488     * @return the result of the merge which is not null 
     489     */ 
     490    private ITaskTreeNode mergeEqualSelections(ISelection            selection1, 
     491                                               ISelection            selection2, 
     492                                               ITaskTreeBuilder      treeBuilder, 
     493                                               ITaskTreeNodeFactory  nodeFactory) 
     494    { 
     495        ISelection mergeResult = nodeFactory.createNewSelection(); 
     496             
     497        for (int i = 0; i < selection1.getChildren().size(); i++) { 
     498            treeBuilder.addChild(mergeResult, selection1.getChildren().get(i)); 
     499        } 
     500         
     501        for (int i = 0; i < selection2.getChildren().size(); i++) { 
     502            treeBuilder.addChild(mergeResult, selection2.getChildren().get(i)); 
     503        } 
     504         
     505        mergeEqualNodes(mergeResult.getChildren(), treeBuilder, nodeFactory); 
     506         
     507        return mergeResult; 
     508    } 
     509 
     510    /** 
     511     * <p> 
     512     * merges equal iterations. This is done through merging the children of both iterations. If 
     513     * this is possible, a resulting iteration with the merge result of the children as its own 
     514     * child is returned. Otherwise null is returned to indicate that merging was not possible. 
     515     * </p> 
     516     * 
     517     * @param selection1  the first iteration to be merged 
     518     * @param selection2  the second iteration to be merged 
     519     * @param treeBuilder the tree builder that can be used for connecting task tree nodes 
     520     * @param nodeFactory the node factory that can be used for instantiating task tree nodes 
     521     *  
     522     * @return the result of the merge or null if merging is not possible 
     523     */ 
     524    private ITaskTreeNode mergeEqualIterations(IIteration            iteration1, 
     525                                               IIteration            iteration2, 
     526                                               ITaskTreeBuilder      treeBuilder, 
     527                                               ITaskTreeNodeFactory  nodeFactory) 
     528    { 
     529        ITaskTreeNode mergedChild = mergeEqualTasks 
     530            (iteration1.getChildren().get(0), iteration1.getChildren().get(0), 
     531             treeBuilder, nodeFactory); 
     532         
     533        IIteration mergeResult = null; 
     534         
     535        if (mergedChild != null) { 
     536            mergeResult = nodeFactory.createNewIteration(); 
     537            treeBuilder.setChild(mergeResult, mergedChild); 
     538        } 
     539         
     540        return mergeResult; 
     541    } 
     542 
     543    /** 
     544     * <p> 
     545     * this is a convenience method to create an iteration based on the identified and already 
     546     * merged iterated subsequences. This method creates the simplest iteration possible. As an 
     547     * example, if always the same task tree node is iterated, it becomes the child of the 
     548     * iteration. If a sequence of tasks is iterated, this sequence becomes the child of the 
     549     * iteration. It several equal sublists or nodes which are not lexically equal are iterated 
     550     * they become a selection which in turn become the child of the iteration. 
     551     * </p> 
     552     * 
     553     * @param subsequences the identified and already merged equal subsequences 
     554     * @param treeBuilder  the tree builder that can be used for connecting task tree nodes 
     555     * @param nodeFactory  the node factory that can be used for instantiating the iteration 
     556     *  
     557     * @return the resulting iteration 
     558     */ 
     559    private IIteration createIterationBasedOnIdentifiedVariants(SubSequences          subsequences, 
    228560                                                                ITaskTreeBuilder      treeBuilder, 
    229561                                                                ITaskTreeNodeFactory  nodeFactory, 
    … …  
    233565        result.addNewlyCreatedParentNode(newIteration); 
    234566 
    235         if (equalVariants.size() == 1) { 
     567        if (subsequences.equalVariants.size() == 1) { 
    236568            // all children are the same. Create an iteration of this child 
    237             if (equalVariants.get(0).length == 1) { 
    238                 // all children are the same. Create an iteration of this child 
    239                 treeBuilder.setChild(newIteration, equalVariants.get(0)[0]); 
     569            if (subsequences.equalVariants.get(0).getChildren().size() == 1) { 
     570                // there is only one equal variant and this has only one child. So create an 
     571                // iteration of this child 
     572                treeBuilder.setChild 
     573                    (newIteration, subsequences.equalVariants.get(0).getChildren().get(0)); 
    240574            } 
    241575            else { 
    242                 // there was an iteration of structurally equal sequences 
    243                 ISequence sequence = nodeFactory.createNewSequence(); 
    244                 result.addNewlyCreatedParentNode(sequence); 
    245  
    246                 for (ITaskTreeNode node : equalVariants.get(0)) { 
    247                     treeBuilder.addChild(sequence, node); 
    248                 } 
    249  
    250                 treeBuilder.setChild(newIteration, sequence); 
     576                // there was an iteration of one equal sequence 
     577                treeBuilder.setChild(newIteration, subsequences.equalVariants.get(0)); 
     578                result.addNewlyCreatedParentNode(subsequences.equalVariants.get(0)); 
    251579            } 
    252580        } 
    253581        else { 
    254             // there are distinct variants of semantically equal subsequences or 
    255             // children --> 
    256             // create an iterated selection 
     582            // there are distinct variants of equal subsequences or children --> create an 
     583            // iterated selection 
    257584            ISelection selection = nodeFactory.createNewSelection(); 
    258585            result.addNewlyCreatedParentNode(selection); 
    259586 
    260             for (ITaskTreeNode[] variant : equalVariants) { 
    261                 if (variant.length == 1) { 
    262                     treeBuilder.addChild(selection, variant[0]); 
     587            for (ITaskTreeNode variant : subsequences.equalVariants) { 
     588                if (variant.getChildren().size() == 1) { 
     589                    treeBuilder.addChild(selection, variant.getChildren().get(0)); 
    263590                } 
    264591                else { 
    265                     ISequence sequence = nodeFactory.createNewSequence(); 
    266                     result.addNewlyCreatedParentNode(sequence); 
    267  
    268                     for (ITaskTreeNode node : variant) { 
    269                         treeBuilder.addChild(sequence, node); 
    270                     } 
    271  
    272                     treeBuilder.addChild(selection, sequence); 
     592                    treeBuilder.addChild(selection, variant); 
     593                    result.addNewlyCreatedParentNode(variant); 
    273594                } 
    274595            } 
    … …  
    280601    } 
    281602 
     603    /** 
     604     * <p> 
     605     * as the method has to denote all newly created parent nodes this method identifies them by 
     606     * comparing the existing subtree with the newly created iteration. Only those parent nodes 
     607     * in the new iteration, which are not already found in the existing sub tree are denoted as 
     608     * newly created. We do this in this way, as during the iteration detection algorithm, many 
     609     * parent nodes are created, which may be discarded later. It is easier to identify the 
     610     * remaining newly created parent nodes through this way than to integrate it into the 
     611     * algorithm. 
     612     * </p> 
     613     *  
     614     * @param existingSubTree the existing subtree 
     615     * @param newSubTree      the identified iteration 
     616     * @param result          the rule application result into which the newly created parent nodes 
     617     *                        shall be stored. 
     618     */ 
     619    private void determineNewlyCreatedParentTasks(ITaskTreeNode         existingSubTree, 
     620                                                  ITaskTreeNode         newSubTree, 
     621                                                  RuleApplicationResult result) 
     622    { 
     623        List<ITaskTreeNode> existingParentNodes = getParentNodes(existingSubTree); 
     624        List<ITaskTreeNode> newParentNodes = getParentNodes(newSubTree); 
     625         
     626        boolean foundNode; 
     627        for (ITaskTreeNode newParentNode : newParentNodes) { 
     628            foundNode = false; 
     629            for (ITaskTreeNode existingParentNode : existingParentNodes) { 
     630                // It is sufficient to compare the references. The algorithm reuses nodes as they 
     631                // are. So any node existing in the new structure that is also in the old structure 
     632                // was unchanged an therefore does not need to be handled as a newly created one. 
     633                // but every node in the new structure that is not included in the old structure 
     634                // must be treated as a newly created one. 
     635                if (newParentNode == existingParentNode) { 
     636                    foundNode = true; 
     637                    break; 
     638                } 
     639            } 
     640             
     641            if (!foundNode) { 
     642                result.addNewlyCreatedParentNode(newParentNode); 
     643            } 
     644        } 
     645         
     646    } 
     647 
     648    /** 
     649     * <p> 
     650     * convenience method to determine all parent nodes existing in a subtree 
     651     * </p> 
     652     * 
     653     * @param subtree the subtree to search for parent nodes in 
     654     *  
     655     * @return a list of parent nodes existing in the subtree 
     656     */ 
     657    private List<ITaskTreeNode> getParentNodes(ITaskTreeNode subtree) { 
     658        List<ITaskTreeNode> parentNodes = new ArrayList<ITaskTreeNode>(); 
     659         
     660        if (subtree.getChildren().size() > 0) { 
     661            parentNodes.add(subtree); 
     662             
     663            for (ITaskTreeNode child : subtree.getChildren()) { 
     664                parentNodes.addAll(getParentNodes(child)); 
     665            } 
     666        } 
     667         
     668        return parentNodes; 
     669    } 
     670 
     671    /** 
     672     * <p> 
     673     * used to have a container for equal sublists identified in a sub part of the children of 
     674     * a parent node. 
     675     * </p> 
     676     *  
     677     * @author Patrick Harms 
     678     */ 
     679    public class SubSequences { 
     680 
     681        /** 
     682         * <p> 
     683         * the beginning of the subpart of the children of the parent node in which the sublists 
     684         * are found (inclusive) 
     685         * </p> 
     686         */ 
     687        public int start; 
     688         
     689        /** 
     690         * <p> 
     691         * the end of the subpart of the children of the parent node in which the sublists 
     692         * are found (exclusive) 
     693         * </p> 
     694         */ 
     695        public int end; 
     696         
     697        /** 
     698         * <p> 
     699         * the equal sublists found in the subpart of the children of the parent node 
     700         * </p> 
     701         */ 
     702        List<ITaskTreeNode> equalVariants = new ArrayList<ITaskTreeNode>(); 
     703         
     704    } 
     705 
    282706} 
Note: See TracChangeset for help on using the changeset viewer.