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