[922] | 1 | package de.ugoe.cs.autoquest.tasktrees.temporalrelation; |
---|
[439] | 2 | |
---|
| 3 | import java.util.ArrayList; |
---|
| 4 | import java.util.List; |
---|
| 5 | |
---|
[922] | 6 | import de.ugoe.cs.autoquest.tasktrees.nodeequality.NodeEquality; |
---|
| 7 | import de.ugoe.cs.autoquest.tasktrees.nodeequality.NodeEqualityRuleManager; |
---|
| 8 | import de.ugoe.cs.autoquest.tasktrees.treeifc.IEventTask; |
---|
| 9 | import de.ugoe.cs.autoquest.tasktrees.treeifc.IIteration; |
---|
| 10 | import de.ugoe.cs.autoquest.tasktrees.treeifc.ISelection; |
---|
| 11 | import de.ugoe.cs.autoquest.tasktrees.treeifc.ISequence; |
---|
| 12 | import de.ugoe.cs.autoquest.tasktrees.treeifc.ITaskTreeBuilder; |
---|
| 13 | import de.ugoe.cs.autoquest.tasktrees.treeifc.ITaskTreeNode; |
---|
| 14 | import de.ugoe.cs.autoquest.tasktrees.treeifc.ITaskTreeNodeFactory; |
---|
[439] | 15 | |
---|
| 16 | /** |
---|
[813] | 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> |
---|
[439] | 60 | * |
---|
[813] | 61 | * @author Patrick Harms |
---|
[439] | 62 | */ |
---|
[557] | 63 | public class DefaultIterationDetectionRule implements TemporalRelationshipRule { |
---|
| 64 | |
---|
[1045] | 65 | private static final int MAX_LENGTH_OF_ITERATED_SEQUENCE = 50; |
---|
[1044] | 66 | |
---|
[813] | 67 | /** |
---|
| 68 | * <p> |
---|
| 69 | * the node equality manager needed for comparing task tree nodes with each other |
---|
| 70 | * </p> |
---|
| 71 | */ |
---|
[557] | 72 | private NodeEqualityRuleManager nodeEqualityRuleManager; |
---|
[439] | 73 | |
---|
[813] | 74 | /** |
---|
| 75 | * <p> |
---|
| 76 | * the minimal node equality two identified sublists need to have to consider them as equal |
---|
| 77 | * and to create an iteration for |
---|
| 78 | * </p> |
---|
| 79 | */ |
---|
[805] | 80 | private NodeEquality minimalNodeEquality; |
---|
| 81 | |
---|
[557] | 82 | /** |
---|
[813] | 83 | * <p> |
---|
| 84 | * instantiates the rule and initializes it with a node equality rule manager and the minimal |
---|
| 85 | * node equality identified sublist must have to consider them as iterated. |
---|
| 86 | * </p> |
---|
[557] | 87 | */ |
---|
[805] | 88 | DefaultIterationDetectionRule(NodeEqualityRuleManager nodeEqualityRuleManager, |
---|
| 89 | NodeEquality minimalNodeEquality) |
---|
| 90 | { |
---|
[557] | 91 | super(); |
---|
| 92 | this.nodeEqualityRuleManager = nodeEqualityRuleManager; |
---|
[805] | 93 | this.minimalNodeEquality = minimalNodeEquality; |
---|
[557] | 94 | } |
---|
[439] | 95 | |
---|
[557] | 96 | /* |
---|
| 97 | * (non-Javadoc) |
---|
| 98 | * |
---|
| 99 | * @see TemporalRelationshipRule#apply(TaskTreeNode, TaskTreeBuilder, TaskTreeNodeFactory) |
---|
| 100 | */ |
---|
| 101 | @Override |
---|
| 102 | public RuleApplicationResult apply(ITaskTreeNode parent, |
---|
| 103 | ITaskTreeBuilder treeBuilder, |
---|
| 104 | ITaskTreeNodeFactory nodeFactory, |
---|
| 105 | boolean finalize) |
---|
[439] | 106 | { |
---|
[557] | 107 | if (!(parent instanceof ISequence)) { |
---|
| 108 | return null; |
---|
| 109 | } |
---|
| 110 | |
---|
[813] | 111 | if (!finalize) { |
---|
| 112 | // the rule is always feasible as iterations may occur at any time |
---|
| 113 | RuleApplicationResult result = new RuleApplicationResult(); |
---|
| 114 | result.setRuleApplicationStatus(RuleApplicationStatus.RULE_APPLICATION_FEASIBLE); |
---|
| 115 | return result; |
---|
| 116 | } |
---|
| 117 | |
---|
[557] | 118 | // parent must already have at least 2 children |
---|
| 119 | if ((parent.getChildren() == null) || (parent.getChildren().size() < 2)) { |
---|
| 120 | return null; |
---|
| 121 | } |
---|
[813] | 122 | |
---|
| 123 | |
---|
| 124 | SubSequences subSequences = getEqualSubsequences(parent, treeBuilder, nodeFactory); |
---|
[557] | 125 | |
---|
[813] | 126 | if (subSequences != null) { |
---|
| 127 | RuleApplicationResult result = new RuleApplicationResult(); |
---|
[557] | 128 | |
---|
[813] | 129 | mergeEqualNodes(subSequences.equalVariants, treeBuilder, nodeFactory); |
---|
| 130 | IIteration newIteration = createIterationBasedOnIdentifiedVariants |
---|
| 131 | (subSequences, treeBuilder, nodeFactory, result); |
---|
[557] | 132 | |
---|
[813] | 133 | determineNewlyCreatedParentTasks(parent, newIteration, result); |
---|
| 134 | |
---|
| 135 | // remove iterated children |
---|
| 136 | for (int j = subSequences.start; j < subSequences.end; j++) { |
---|
| 137 | treeBuilder.removeChild((ISequence) parent, subSequences.start); |
---|
| 138 | } |
---|
[557] | 139 | |
---|
[813] | 140 | // add the new iteration instead |
---|
| 141 | treeBuilder.addChild((ISequence) parent, subSequences.start, newIteration); |
---|
[557] | 142 | |
---|
[813] | 143 | result.setRuleApplicationStatus(RuleApplicationStatus.RULE_APPLICATION_FINISHED); |
---|
| 144 | return result; |
---|
[557] | 145 | } |
---|
[439] | 146 | |
---|
[557] | 147 | return null; |
---|
[439] | 148 | } |
---|
| 149 | |
---|
[557] | 150 | /** |
---|
[813] | 151 | * <p> |
---|
| 152 | * this method initiates the trial and error algorithm denoted in the description of this class. |
---|
| 153 | * Its main purpose is the selection of a subpart of all children in the parent node in which |
---|
| 154 | * equal sublists shall be searched. It is important, to always find the last iterations in a |
---|
| 155 | * part first. The reason for this are iterations of iterations. If we always found the first |
---|
| 156 | * iteration in a subpart first, then this may be an iteration of iterations. However, there |
---|
| 157 | * may be subsequent iterations to be included in this iteration. But these iterations are not |
---|
| 158 | * found yet, as they occur later in the sequence. Therefore, if we always find the last |
---|
| 159 | * iteration in a sequence first, iterations of iterations are identified, last. |
---|
| 160 | * </p> |
---|
[557] | 161 | * |
---|
[813] | 162 | * @param parent the parent node in which iterations of children shall be found |
---|
| 163 | * @param treeBuilder the tree builder that can be used for connecting task tree nodes |
---|
| 164 | * @param nodeFactory the node factory that can be used for instantiating task tree nodes |
---|
| 165 | * |
---|
| 166 | * @return the iterated subsequences identified in a specific part (contains the equal |
---|
| 167 | * subsequences as well as the start (inclusive) and end (exclusive) index of the |
---|
| 168 | * subpart in which the sequences were found) |
---|
[557] | 169 | */ |
---|
[813] | 170 | private SubSequences getEqualSubsequences(ITaskTreeNode parent, |
---|
| 171 | ITaskTreeBuilder treeBuilder, |
---|
| 172 | ITaskTreeNodeFactory nodeFactory) |
---|
[439] | 173 | { |
---|
[813] | 174 | SubSequences subSequences = null; |
---|
[557] | 175 | |
---|
[970] | 176 | // to find longer iterations first, start with long sequences |
---|
[813] | 177 | FIND_ITERATION: |
---|
| 178 | for (int end = parent.getChildren().size(); end > 0; end--) { |
---|
| 179 | for (int start = 0; start < end; start++) { |
---|
| 180 | boolean useEqualSublistLengths = equalSublistLengthsCanBeUsed(parent, start, end); |
---|
[557] | 181 | |
---|
[813] | 182 | subSequences = new SubSequences(); |
---|
| 183 | subSequences.start = start; |
---|
[557] | 184 | |
---|
[813] | 185 | boolean foundFurtherVariants = findFurtherVariants |
---|
| 186 | (subSequences, parent, start, end, treeBuilder, nodeFactory, |
---|
| 187 | useEqualSublistLengths); |
---|
| 188 | |
---|
| 189 | if (foundFurtherVariants) { |
---|
| 190 | break FIND_ITERATION; |
---|
[557] | 191 | } |
---|
[813] | 192 | else { |
---|
| 193 | subSequences = null; |
---|
| 194 | } |
---|
[557] | 195 | } |
---|
[439] | 196 | } |
---|
[813] | 197 | |
---|
| 198 | return subSequences; |
---|
[439] | 199 | } |
---|
| 200 | |
---|
[557] | 201 | /** |
---|
[813] | 202 | * <p> |
---|
| 203 | * for optimization purposes, we check if the length of the sublists to be identified as |
---|
| 204 | * iterations has to be the same for any sublist. This only applies, if the minimum node |
---|
| 205 | * equality to be checked for is lexical equality. If the children of the parent are all event |
---|
| 206 | * tasks, then sublists can only be lexically equal, if they all have the same length. |
---|
| 207 | * Therefore we check, if the minimal node equality is lexical equality. And if so, we also |
---|
| 208 | * check if all children of the parent in which an iteration shall be searched for are event |
---|
| 209 | * tasks. |
---|
| 210 | * </p> |
---|
[805] | 211 | * |
---|
[813] | 212 | * @param parent the parent node to search for iterations of its children |
---|
| 213 | * @param start the beginning of the subpart (inclusive) to be considered |
---|
| 214 | * @param end the end of the subpart (exclusive) to be considered |
---|
| 215 | * |
---|
| 216 | * @return true, if the sublists must have the same lengths, false else |
---|
[805] | 217 | */ |
---|
[813] | 218 | private boolean equalSublistLengthsCanBeUsed(ITaskTreeNode parent, int start, int end) { |
---|
| 219 | boolean equalLengthsCanBeUsed = minimalNodeEquality.isAtLeast(NodeEquality.LEXICALLY_EQUAL); |
---|
| 220 | |
---|
| 221 | if (equalLengthsCanBeUsed) { |
---|
| 222 | for (int i = start; i < end; i++) { |
---|
| 223 | if (!(parent.getChildren().get(i) instanceof IEventTask)) { |
---|
| 224 | equalLengthsCanBeUsed = false; |
---|
| 225 | break; |
---|
| 226 | } |
---|
| 227 | } |
---|
[439] | 228 | } |
---|
[557] | 229 | |
---|
[813] | 230 | return equalLengthsCanBeUsed; |
---|
| 231 | } |
---|
[557] | 232 | |
---|
[813] | 233 | /** |
---|
| 234 | * <p> |
---|
| 235 | * this method starts at a specific position in the list of children of the provided parent |
---|
| 236 | * and checks, if it finds a further sublist, that matches the already found sublists. If |
---|
| 237 | * the sublist lengths must be equal, it only searches for a sublist of the same length of the |
---|
| 238 | * already found sublists. The method calls itself if it identifies a further equal sublist but |
---|
| 239 | * if the end of the subpart of children is not yet reached. |
---|
| 240 | * </p> |
---|
| 241 | * |
---|
| 242 | * @param subSequences the sublist found so far against which equality of the next |
---|
| 243 | * sublist must be checked |
---|
| 244 | * @param parent the parent node of which the children are analyzed |
---|
| 245 | * @param start the starting index from which to start the next sublist to be |
---|
| 246 | * identified |
---|
| 247 | * @param end the end index (exclusive) of the current subpart of children |
---|
| 248 | * in which iterations are searched for |
---|
| 249 | * @param treeBuilder the tree builder that can be used for connecting task tree |
---|
| 250 | * nodes |
---|
| 251 | * @param nodeFactory the node factory that can be used for instantiating task tree |
---|
| 252 | * nodes |
---|
| 253 | * @param useEqualSublistLengths true if the sublists to be searched for all need to have the |
---|
| 254 | * same length |
---|
| 255 | * |
---|
| 256 | * @return true if a further equal variant was found, false else |
---|
| 257 | */ |
---|
| 258 | private boolean findFurtherVariants(SubSequences subSequences, |
---|
| 259 | ITaskTreeNode parent, |
---|
| 260 | int start, |
---|
| 261 | int end, |
---|
| 262 | ITaskTreeBuilder treeBuilder, |
---|
| 263 | ITaskTreeNodeFactory nodeFactory, |
---|
| 264 | boolean useEqualSublistLengths) |
---|
| 265 | { |
---|
| 266 | boolean foundFurtherVariants = (start == end) && (subSequences.equalVariants.size() > 1); |
---|
| 267 | |
---|
| 268 | int minChildCount = 1; |
---|
[1044] | 269 | int maxChildCount = Math.min(MAX_LENGTH_OF_ITERATED_SEQUENCE, end - start); |
---|
[813] | 270 | |
---|
| 271 | if (useEqualSublistLengths && (subSequences.equalVariants.size() > 0)) { |
---|
| 272 | minChildCount = subSequences.equalVariants.get(0).getChildren().size(); |
---|
| 273 | maxChildCount = Math.min(minChildCount, maxChildCount); |
---|
| 274 | } |
---|
| 275 | |
---|
| 276 | for (int childCount = minChildCount; childCount <= maxChildCount; childCount++) { |
---|
| 277 | if (useEqualSublistLengths && (((end - start) % childCount) != 0)) { |
---|
| 278 | continue; |
---|
| 279 | } |
---|
| 280 | |
---|
| 281 | ISequence furtherVariant = nodeFactory.createNewSequence(); |
---|
| 282 | |
---|
| 283 | for (int j = start; j < start + childCount; j++) { |
---|
| 284 | treeBuilder.addChild(furtherVariant, parent.getChildren().get(j)); |
---|
| 285 | } |
---|
| 286 | |
---|
| 287 | boolean allVariantsEqual = true; |
---|
| 288 | |
---|
| 289 | for (ITaskTreeNode equalVariant : subSequences.equalVariants) { |
---|
| 290 | NodeEquality nodeEquality = |
---|
| 291 | nodeEqualityRuleManager.applyRules(equalVariant, furtherVariant); |
---|
| 292 | |
---|
[805] | 293 | if (!nodeEquality.isAtLeast(minimalNodeEquality)) { |
---|
[813] | 294 | allVariantsEqual = false; |
---|
| 295 | break; |
---|
[557] | 296 | } |
---|
[813] | 297 | } |
---|
| 298 | |
---|
| 299 | if (allVariantsEqual) { |
---|
| 300 | |
---|
| 301 | // we found a further variant. Add it to the list of variants and try to find |
---|
| 302 | // further variants. Ignore, if none is available |
---|
| 303 | int index = subSequences.equalVariants.size(); |
---|
| 304 | subSequences.equalVariants.add(index, furtherVariant); |
---|
| 305 | |
---|
| 306 | foundFurtherVariants = findFurtherVariants |
---|
| 307 | (subSequences, parent, start + childCount, end, treeBuilder, nodeFactory, |
---|
| 308 | useEqualSublistLengths); |
---|
| 309 | |
---|
| 310 | if (foundFurtherVariants) { |
---|
| 311 | subSequences.end = end; |
---|
| 312 | break; |
---|
[805] | 313 | } |
---|
[813] | 314 | else { |
---|
| 315 | subSequences.equalVariants.remove(index); |
---|
| 316 | } |
---|
[557] | 317 | } |
---|
[813] | 318 | } |
---|
| 319 | |
---|
| 320 | return foundFurtherVariants; |
---|
| 321 | } |
---|
[557] | 322 | |
---|
[813] | 323 | /** |
---|
| 324 | * <p> |
---|
| 325 | * this method merges task tree nodes in a list, if they can be merged. for this, it tries |
---|
| 326 | * to merge every node with every other node in the provided list using the |
---|
| 327 | * {@link #mergeEqualTasks(ITaskTreeNode, ITaskTreeNode, ITaskTreeBuilder, ITaskTreeNodeFactory)} |
---|
| 328 | * method. If a merge is possible, it removes the merged nodes from the list and adds the |
---|
| 329 | * merge result. |
---|
| 330 | * </p> |
---|
| 331 | * |
---|
| 332 | * @param nodes the list of nodes to be merged |
---|
| 333 | * @param treeBuilder the tree builder that can be used for connecting task tree nodes |
---|
| 334 | * @param nodeFactory the node factory that can be used for instantiating task tree nodes |
---|
| 335 | */ |
---|
| 336 | private void mergeEqualNodes(List<ITaskTreeNode> nodes, |
---|
| 337 | ITaskTreeBuilder treeBuilder, |
---|
| 338 | ITaskTreeNodeFactory nodeFactory) |
---|
| 339 | { |
---|
| 340 | int index1 = 0; |
---|
| 341 | int index2 = 0; |
---|
| 342 | ITaskTreeNode variant1; |
---|
| 343 | ITaskTreeNode variant2; |
---|
| 344 | |
---|
| 345 | while (index1 < nodes.size()) { |
---|
| 346 | variant1 = nodes.get(index1); |
---|
| 347 | index2 = index1 + 1; |
---|
| 348 | |
---|
| 349 | while (index2 < nodes.size()) { |
---|
| 350 | variant2 = nodes.get(index2); |
---|
| 351 | ITaskTreeNode mergedChild = |
---|
| 352 | mergeEqualTasks(variant1, variant2, treeBuilder, nodeFactory); |
---|
| 353 | |
---|
| 354 | if (mergedChild != null) { |
---|
| 355 | // if we merged something start from the beginning to perform the next merge |
---|
| 356 | nodes.remove(index2); |
---|
| 357 | nodes.remove(index1); |
---|
| 358 | nodes.add(index1, mergedChild); |
---|
| 359 | index1 = -1; |
---|
| 360 | break; |
---|
[557] | 361 | } |
---|
| 362 | else { |
---|
[813] | 363 | index2++; |
---|
[557] | 364 | } |
---|
| 365 | } |
---|
[813] | 366 | |
---|
| 367 | index1++; |
---|
| 368 | } |
---|
| 369 | } |
---|
[557] | 370 | |
---|
[813] | 371 | /** |
---|
| 372 | * <p> |
---|
| 373 | * this method merges two equal tasks with each other if possible. If the tasks are lexically |
---|
| 374 | * equal, the first of them is returned as merge result. If both tasks are of the same |
---|
| 375 | * temporal relationship type, the appropriate merge method is called to merge them. If one |
---|
| 376 | * of the nodes is a selection, the other one is added as a variant of this selection. |
---|
| 377 | * (However, if both nodes are selections, they are merged using the appropriate merge method.) |
---|
| 378 | * If merging is not possible, then a selection of both provided nodes is created and |
---|
| 379 | * returned as merge result. |
---|
| 380 | * </p> |
---|
| 381 | * |
---|
| 382 | * @param node1 the first task to be merged |
---|
| 383 | * @param node2 the second task to be merged |
---|
| 384 | * @param treeBuilder the tree builder that can be used for connecting task tree nodes |
---|
| 385 | * @param nodeFactory the node factory that can be used for instantiating task tree nodes |
---|
| 386 | * |
---|
| 387 | * @return the result of the merge |
---|
| 388 | */ |
---|
| 389 | private ITaskTreeNode mergeEqualTasks(ITaskTreeNode node1, |
---|
| 390 | ITaskTreeNode node2, |
---|
| 391 | ITaskTreeBuilder treeBuilder, |
---|
| 392 | ITaskTreeNodeFactory nodeFactory) |
---|
| 393 | { |
---|
| 394 | ITaskTreeNode mergeResult = null; |
---|
| 395 | |
---|
[818] | 396 | if ((node1 instanceof ISequence) && (node2 instanceof ISequence)) { |
---|
| 397 | mergeResult = mergeEqualSequences |
---|
| 398 | ((ISequence) node1, (ISequence) node2, treeBuilder, nodeFactory); |
---|
| 399 | } |
---|
| 400 | else if ((node1 instanceof ISelection) && (node2 instanceof ISelection)) { |
---|
| 401 | mergeResult = mergeEqualSelections |
---|
| 402 | ((ISelection) node1, (ISelection) node2, treeBuilder, nodeFactory); |
---|
| 403 | } |
---|
| 404 | else if ((node1 instanceof IIteration) && (node2 instanceof IIteration)) { |
---|
| 405 | mergeResult = mergeEqualIterations |
---|
| 406 | ((IIteration) node1, (IIteration) node2, treeBuilder, nodeFactory); |
---|
| 407 | } |
---|
| 408 | else if (node1 instanceof ISelection) { |
---|
| 409 | treeBuilder.addChild((ISelection) node1, node2); |
---|
[813] | 410 | mergeResult = node1; |
---|
| 411 | } |
---|
[818] | 412 | else if (node2 instanceof ISelection) { |
---|
| 413 | treeBuilder.addChild((ISelection) node2, node1); |
---|
| 414 | mergeResult = node2; |
---|
| 415 | } |
---|
| 416 | else if (node1 instanceof IIteration) { |
---|
| 417 | mergeResult = mergeEqualTasks |
---|
| 418 | (((IIteration) node1).getChildren().get(0), node2, treeBuilder, nodeFactory); |
---|
| 419 | |
---|
| 420 | if (mergeResult != null) { |
---|
| 421 | IIteration iteration = nodeFactory.createNewIteration(); |
---|
| 422 | treeBuilder.setChild(iteration, mergeResult); |
---|
| 423 | mergeResult = iteration; |
---|
[557] | 424 | } |
---|
[818] | 425 | } |
---|
| 426 | else if (node2 instanceof IIteration) { |
---|
| 427 | mergeResult = mergeEqualTasks |
---|
| 428 | (((IIteration) node2).getChildren().get(0), node1, treeBuilder, nodeFactory); |
---|
| 429 | |
---|
| 430 | if (mergeResult != null) { |
---|
| 431 | IIteration iteration = nodeFactory.createNewIteration(); |
---|
| 432 | treeBuilder.setChild(iteration, mergeResult); |
---|
| 433 | mergeResult = iteration; |
---|
[813] | 434 | } |
---|
[818] | 435 | } |
---|
| 436 | else { |
---|
| 437 | NodeEquality nodeEquality = nodeEqualityRuleManager.applyRules(node1, node2); |
---|
| 438 | |
---|
| 439 | if (nodeEquality.isAtLeast(NodeEquality.LEXICALLY_EQUAL)) { |
---|
[813] | 440 | mergeResult = node1; |
---|
| 441 | } |
---|
[439] | 442 | } |
---|
[818] | 443 | |
---|
[813] | 444 | if (mergeResult == null) { |
---|
| 445 | mergeResult = nodeFactory.createNewSelection(); |
---|
| 446 | treeBuilder.addChild((ISelection) mergeResult, node1); |
---|
| 447 | treeBuilder.addChild((ISelection) mergeResult, node2); |
---|
| 448 | } |
---|
| 449 | |
---|
| 450 | return mergeResult; |
---|
[439] | 451 | } |
---|
| 452 | |
---|
[805] | 453 | /** |
---|
| 454 | * <p> |
---|
[813] | 455 | * merges equal sequences. This is done through trying to merge each node of sequence 1 with |
---|
| 456 | * the node in sequence 2 being located at the same position. If not all children can be merged |
---|
| 457 | * or if the sequences have different lengths, null is returned to indicate, that merging is |
---|
| 458 | * not possible. For merging children, the |
---|
| 459 | * {@link #mergeEqualTasks(ITaskTreeNode, ITaskTreeNode, ITaskTreeBuilder, ITaskTreeNodeFactory)} |
---|
| 460 | * method is called. |
---|
[805] | 461 | * </p> |
---|
| 462 | * |
---|
[813] | 463 | * @param sequence1 the first sequence to be merged |
---|
| 464 | * @param sequence2 the second sequence to be merged |
---|
| 465 | * @param treeBuilder the tree builder that can be used for connecting task tree nodes |
---|
| 466 | * @param nodeFactory the node factory that can be used for instantiating task tree nodes |
---|
| 467 | * |
---|
| 468 | * @return the result of the merge or null if merging was not possible |
---|
[805] | 469 | */ |
---|
[813] | 470 | private ISequence mergeEqualSequences(ISequence sequence1, |
---|
| 471 | ISequence sequence2, |
---|
| 472 | ITaskTreeBuilder treeBuilder, |
---|
| 473 | ITaskTreeNodeFactory nodeFactory) |
---|
[805] | 474 | { |
---|
[813] | 475 | ISequence mergeResult = null; |
---|
| 476 | |
---|
| 477 | if (sequence1.getChildren().size() == sequence2.getChildren().size()) { |
---|
| 478 | mergeResult = nodeFactory.createNewSequence(); |
---|
| 479 | |
---|
| 480 | for (int i = 0; i < sequence1.getChildren().size(); i++) { |
---|
| 481 | ITaskTreeNode mergedNode = mergeEqualTasks |
---|
| 482 | (sequence1.getChildren().get(i), sequence2.getChildren().get(i), |
---|
| 483 | treeBuilder, nodeFactory); |
---|
| 484 | |
---|
| 485 | if (mergedNode != null) { |
---|
| 486 | treeBuilder.addChild(mergeResult, mergedNode); |
---|
| 487 | } |
---|
| 488 | else { |
---|
| 489 | mergeResult = null; |
---|
| 490 | break; |
---|
| 491 | } |
---|
[805] | 492 | } |
---|
[813] | 493 | } |
---|
| 494 | |
---|
| 495 | return mergeResult; |
---|
| 496 | } |
---|
[805] | 497 | |
---|
[813] | 498 | /** |
---|
| 499 | * <p> |
---|
[970] | 500 | * merges equal selections. This is done by adding those children of the second selection to |
---|
| 501 | * the first selection that can not be merged with any of the children of the first selection. |
---|
| 502 | * If a merge is possible and this merge is not a simple selection of the merged children, |
---|
| 503 | * then the merged child replaces the child of the first selection which was merged. |
---|
[813] | 504 | * </p> |
---|
| 505 | * |
---|
| 506 | * @param selection1 the first selection to be merged |
---|
| 507 | * @param selection2 the second selection to be merged |
---|
| 508 | * @param treeBuilder the tree builder that can be used for connecting task tree nodes |
---|
| 509 | * @param nodeFactory the node factory that can be used for instantiating task tree nodes |
---|
| 510 | * |
---|
[970] | 511 | * @return the result of the merge which is never null |
---|
[813] | 512 | */ |
---|
| 513 | private ITaskTreeNode mergeEqualSelections(ISelection selection1, |
---|
| 514 | ISelection selection2, |
---|
| 515 | ITaskTreeBuilder treeBuilder, |
---|
| 516 | ITaskTreeNodeFactory nodeFactory) |
---|
| 517 | { |
---|
[970] | 518 | ISelection mergeResult = selection1; |
---|
[813] | 519 | |
---|
[970] | 520 | ITaskTreeNode childToMerge = null; |
---|
| 521 | ITaskTreeNode mergedChild = null; |
---|
| 522 | |
---|
| 523 | // check for each child of selection 2 if it is a duplicate of one of the children |
---|
| 524 | // if selection 1. If not, add it as further child to the merge result, else skip it. |
---|
[813] | 525 | for (int i = 0; i < selection2.getChildren().size(); i++) { |
---|
[970] | 526 | childToMerge = selection2.getChildren().get(i); |
---|
| 527 | for (int j = 0; j < selection1.getChildren().size(); j++) { |
---|
| 528 | mergedChild = mergeEqualTasks |
---|
| 529 | (selection1.getChildren().get(j), childToMerge, treeBuilder, nodeFactory); |
---|
| 530 | |
---|
| 531 | // a merge must not be a selection, except it is one of the children. Otherwise |
---|
| 532 | // no real merge was done. |
---|
| 533 | if ((mergedChild != null) && |
---|
| 534 | ((!(mergedChild instanceof ISelection)) || |
---|
| 535 | (selection1.getChildren().get(j) == mergedChild) || |
---|
| 536 | (childToMerge == mergedChild))) |
---|
| 537 | { |
---|
| 538 | // we found a real merge. So replace the original child in selection 1 with |
---|
| 539 | // the merged child |
---|
| 540 | treeBuilder.removeChild(selection1, selection1.getChildren().get(j)); |
---|
| 541 | treeBuilder.addChild(selection1, mergedChild); |
---|
| 542 | mergedChild = null; |
---|
| 543 | childToMerge = null; |
---|
| 544 | break; |
---|
| 545 | } |
---|
| 546 | } |
---|
| 547 | |
---|
| 548 | if (childToMerge != null) { |
---|
| 549 | treeBuilder.addChild(selection1, childToMerge); |
---|
| 550 | } |
---|
[813] | 551 | } |
---|
| 552 | |
---|
| 553 | return mergeResult; |
---|
| 554 | } |
---|
[805] | 555 | |
---|
[813] | 556 | /** |
---|
| 557 | * <p> |
---|
| 558 | * merges equal iterations. This is done through merging the children of both iterations. If |
---|
| 559 | * this is possible, a resulting iteration with the merge result of the children as its own |
---|
| 560 | * child is returned. Otherwise null is returned to indicate that merging was not possible. |
---|
| 561 | * </p> |
---|
| 562 | * |
---|
| 563 | * @param selection1 the first iteration to be merged |
---|
| 564 | * @param selection2 the second iteration to be merged |
---|
| 565 | * @param treeBuilder the tree builder that can be used for connecting task tree nodes |
---|
| 566 | * @param nodeFactory the node factory that can be used for instantiating task tree nodes |
---|
| 567 | * |
---|
| 568 | * @return the result of the merge or null if merging is not possible |
---|
| 569 | */ |
---|
| 570 | private ITaskTreeNode mergeEqualIterations(IIteration iteration1, |
---|
| 571 | IIteration iteration2, |
---|
| 572 | ITaskTreeBuilder treeBuilder, |
---|
| 573 | ITaskTreeNodeFactory nodeFactory) |
---|
| 574 | { |
---|
| 575 | ITaskTreeNode mergedChild = mergeEqualTasks |
---|
[818] | 576 | (iteration1.getChildren().get(0), iteration2.getChildren().get(0), |
---|
[813] | 577 | treeBuilder, nodeFactory); |
---|
| 578 | |
---|
| 579 | IIteration mergeResult = null; |
---|
| 580 | |
---|
| 581 | if (mergedChild != null) { |
---|
| 582 | mergeResult = nodeFactory.createNewIteration(); |
---|
| 583 | treeBuilder.setChild(mergeResult, mergedChild); |
---|
[805] | 584 | } |
---|
[813] | 585 | |
---|
| 586 | return mergeResult; |
---|
| 587 | } |
---|
[805] | 588 | |
---|
| 589 | /** |
---|
| 590 | * <p> |
---|
[813] | 591 | * this is a convenience method to create an iteration based on the identified and already |
---|
| 592 | * merged iterated subsequences. This method creates the simplest iteration possible. As an |
---|
| 593 | * example, if always the same task tree node is iterated, it becomes the child of the |
---|
| 594 | * iteration. If a sequence of tasks is iterated, this sequence becomes the child of the |
---|
| 595 | * iteration. It several equal sublists or nodes which are not lexically equal are iterated |
---|
| 596 | * they become a selection which in turn become the child of the iteration. |
---|
[805] | 597 | * </p> |
---|
| 598 | * |
---|
[813] | 599 | * @param subsequences the identified and already merged equal subsequences |
---|
| 600 | * @param treeBuilder the tree builder that can be used for connecting task tree nodes |
---|
| 601 | * @param nodeFactory the node factory that can be used for instantiating the iteration |
---|
| 602 | * |
---|
| 603 | * @return the resulting iteration |
---|
[805] | 604 | */ |
---|
[813] | 605 | private IIteration createIterationBasedOnIdentifiedVariants(SubSequences subsequences, |
---|
[805] | 606 | ITaskTreeBuilder treeBuilder, |
---|
| 607 | ITaskTreeNodeFactory nodeFactory, |
---|
| 608 | RuleApplicationResult result) |
---|
| 609 | { |
---|
| 610 | IIteration newIteration = nodeFactory.createNewIteration(); |
---|
| 611 | result.addNewlyCreatedParentNode(newIteration); |
---|
| 612 | |
---|
[813] | 613 | if (subsequences.equalVariants.size() == 1) { |
---|
[805] | 614 | // all children are the same. Create an iteration of this child |
---|
[813] | 615 | if (subsequences.equalVariants.get(0).getChildren().size() == 1) { |
---|
| 616 | // there is only one equal variant and this has only one child. So create an |
---|
| 617 | // iteration of this child |
---|
| 618 | treeBuilder.setChild |
---|
| 619 | (newIteration, subsequences.equalVariants.get(0).getChildren().get(0)); |
---|
[805] | 620 | } |
---|
| 621 | else { |
---|
[813] | 622 | // there was an iteration of one equal sequence |
---|
| 623 | treeBuilder.setChild(newIteration, subsequences.equalVariants.get(0)); |
---|
| 624 | result.addNewlyCreatedParentNode(subsequences.equalVariants.get(0)); |
---|
[805] | 625 | } |
---|
| 626 | } |
---|
| 627 | else { |
---|
[813] | 628 | // there are distinct variants of equal subsequences or children --> create an |
---|
| 629 | // iterated selection |
---|
[805] | 630 | ISelection selection = nodeFactory.createNewSelection(); |
---|
| 631 | result.addNewlyCreatedParentNode(selection); |
---|
| 632 | |
---|
[813] | 633 | for (ITaskTreeNode variant : subsequences.equalVariants) { |
---|
| 634 | if (variant.getChildren().size() == 1) { |
---|
| 635 | treeBuilder.addChild(selection, variant.getChildren().get(0)); |
---|
[805] | 636 | } |
---|
| 637 | else { |
---|
[813] | 638 | treeBuilder.addChild(selection, variant); |
---|
| 639 | result.addNewlyCreatedParentNode(variant); |
---|
[805] | 640 | } |
---|
| 641 | } |
---|
| 642 | |
---|
| 643 | treeBuilder.setChild(newIteration, selection); |
---|
| 644 | } |
---|
| 645 | |
---|
| 646 | return newIteration; |
---|
| 647 | } |
---|
| 648 | |
---|
[813] | 649 | /** |
---|
| 650 | * <p> |
---|
| 651 | * as the method has to denote all newly created parent nodes this method identifies them by |
---|
| 652 | * comparing the existing subtree with the newly created iteration. Only those parent nodes |
---|
| 653 | * in the new iteration, which are not already found in the existing sub tree are denoted as |
---|
| 654 | * newly created. We do this in this way, as during the iteration detection algorithm, many |
---|
| 655 | * parent nodes are created, which may be discarded later. It is easier to identify the |
---|
| 656 | * remaining newly created parent nodes through this way than to integrate it into the |
---|
| 657 | * algorithm. |
---|
| 658 | * </p> |
---|
| 659 | * |
---|
| 660 | * @param existingSubTree the existing subtree |
---|
| 661 | * @param newSubTree the identified iteration |
---|
| 662 | * @param result the rule application result into which the newly created parent nodes |
---|
| 663 | * shall be stored. |
---|
| 664 | */ |
---|
| 665 | private void determineNewlyCreatedParentTasks(ITaskTreeNode existingSubTree, |
---|
| 666 | ITaskTreeNode newSubTree, |
---|
| 667 | RuleApplicationResult result) |
---|
| 668 | { |
---|
| 669 | List<ITaskTreeNode> existingParentNodes = getParentNodes(existingSubTree); |
---|
| 670 | List<ITaskTreeNode> newParentNodes = getParentNodes(newSubTree); |
---|
| 671 | |
---|
| 672 | boolean foundNode; |
---|
| 673 | for (ITaskTreeNode newParentNode : newParentNodes) { |
---|
| 674 | foundNode = false; |
---|
| 675 | for (ITaskTreeNode existingParentNode : existingParentNodes) { |
---|
| 676 | // It is sufficient to compare the references. The algorithm reuses nodes as they |
---|
| 677 | // are. So any node existing in the new structure that is also in the old structure |
---|
| 678 | // was unchanged an therefore does not need to be handled as a newly created one. |
---|
| 679 | // but every node in the new structure that is not included in the old structure |
---|
| 680 | // must be treated as a newly created one. |
---|
| 681 | if (newParentNode == existingParentNode) { |
---|
| 682 | foundNode = true; |
---|
| 683 | break; |
---|
| 684 | } |
---|
| 685 | } |
---|
| 686 | |
---|
| 687 | if (!foundNode) { |
---|
| 688 | result.addNewlyCreatedParentNode(newParentNode); |
---|
| 689 | } |
---|
| 690 | } |
---|
| 691 | |
---|
| 692 | } |
---|
| 693 | |
---|
| 694 | /** |
---|
| 695 | * <p> |
---|
| 696 | * convenience method to determine all parent nodes existing in a subtree |
---|
| 697 | * </p> |
---|
| 698 | * |
---|
| 699 | * @param subtree the subtree to search for parent nodes in |
---|
| 700 | * |
---|
| 701 | * @return a list of parent nodes existing in the subtree |
---|
| 702 | */ |
---|
| 703 | private List<ITaskTreeNode> getParentNodes(ITaskTreeNode subtree) { |
---|
| 704 | List<ITaskTreeNode> parentNodes = new ArrayList<ITaskTreeNode>(); |
---|
| 705 | |
---|
| 706 | if (subtree.getChildren().size() > 0) { |
---|
| 707 | parentNodes.add(subtree); |
---|
| 708 | |
---|
| 709 | for (ITaskTreeNode child : subtree.getChildren()) { |
---|
| 710 | parentNodes.addAll(getParentNodes(child)); |
---|
| 711 | } |
---|
| 712 | } |
---|
| 713 | |
---|
| 714 | return parentNodes; |
---|
| 715 | } |
---|
| 716 | |
---|
| 717 | /** |
---|
| 718 | * <p> |
---|
| 719 | * used to have a container for equal sublists identified in a sub part of the children of |
---|
| 720 | * a parent node. |
---|
| 721 | * </p> |
---|
| 722 | * |
---|
| 723 | * @author Patrick Harms |
---|
| 724 | */ |
---|
[815] | 725 | private static class SubSequences { |
---|
[813] | 726 | |
---|
| 727 | /** |
---|
| 728 | * <p> |
---|
| 729 | * the beginning of the subpart of the children of the parent node in which the sublists |
---|
| 730 | * are found (inclusive) |
---|
| 731 | * </p> |
---|
| 732 | */ |
---|
| 733 | public int start; |
---|
| 734 | |
---|
| 735 | /** |
---|
| 736 | * <p> |
---|
| 737 | * the end of the subpart of the children of the parent node in which the sublists |
---|
| 738 | * are found (exclusive) |
---|
| 739 | * </p> |
---|
| 740 | */ |
---|
| 741 | public int end; |
---|
| 742 | |
---|
| 743 | /** |
---|
| 744 | * <p> |
---|
| 745 | * the equal sublists found in the subpart of the children of the parent node |
---|
| 746 | * </p> |
---|
| 747 | */ |
---|
| 748 | List<ITaskTreeNode> equalVariants = new ArrayList<ITaskTreeNode>(); |
---|
| 749 | |
---|
| 750 | } |
---|
| 751 | |
---|
[439] | 752 | } |
---|