+ * iterations in a list of nodes are equal subsequences following each other directly. The + * subsequences can be of any length depending on the type of equality they need to have. If the + * subsequences have to be lexically equal, then they have to have the same length if they only + * contain event tasks. As an example entering text can be done through appropriate keystrokes or + * through pasting the text. As a result, two syntactically different sequences are semantically + * equal. If both follow each other, then they are an iteration of semantically equal children. + * But they are not lexically equal. + *
+ *+ * This class determines equal subsequences following each other. It is provided with a minimal node + * equality the equal nodes should have. Through this, it is possible to find e.g. lexically + * equal subsequence through a first application of this rule and semantically equal children to + * a later application of this rule. This is used by the {@link TemporalRelationshipRuleManager} + * which instantiates this rule three times, each with a different minimal equality. + *
+ *+ * The equal subsequences are determined through trial and error. This algorithm has a high effort + * as it tries in the worst case all possible combinations of sub lists in all possible parts of + * the list of children of a provided parent node. The steps for each trial are. + *
+ * the node equality manager needed for comparing task tree nodes with each other + *
+ */ private NodeEqualityRuleManager nodeEqualityRuleManager; - /** */ + /** + *+ * the minimal node equality two identified sublists need to have to consider them as equal + * and to create an iteration for + *
+ */ private NodeEquality minimalNodeEquality; /** - * TODO: comment - * + *+ * instantiates the rule and initializes it with a node equality rule manager and the minimal + * node equality identified sublist must have to consider them as iterated. + *
*/ DefaultIterationDetectionRule(NodeEqualityRuleManager nodeEqualityRuleManager, @@ -54,176 +107,455 @@ } + if (!finalize) { + // the rule is always feasible as iterations may occur at any time + RuleApplicationResult result = new RuleApplicationResult(); + result.setRuleApplicationStatus(RuleApplicationStatus.RULE_APPLICATION_FEASIBLE); + return result; + } + // parent must already have at least 2 children if ((parent.getChildren() == null) || (parent.getChildren().size() < 2)) { return null; } - - // iterations represent as a list of nodes that splits up in several equal sublists. If - // the remaining nodes also start an equal sublist, then the iteration may not be completed - // yet. So wait for further events to only identify completed iterations. - + + // to find longer iterations first, start with long sequences - for (int end = parent.getChildren().size() - 1; end > 0; end--) { + SubSequences subSequences = getEqualSubsequences(parent, treeBuilder, nodeFactory); + + if (subSequences != null) { + RuleApplicationResult result = new RuleApplicationResult(); + + mergeEqualNodes(subSequences.equalVariants, treeBuilder, nodeFactory); + IIteration newIteration = createIterationBasedOnIdentifiedVariants + (subSequences, treeBuilder, nodeFactory, result); + + determineNewlyCreatedParentTasks(parent, newIteration, result); + + // remove iterated children + for (int j = subSequences.start; j < subSequences.end; j++) { + treeBuilder.removeChild((ISequence) parent, subSequences.start); + } + + // add the new iteration instead + treeBuilder.addChild((ISequence) parent, subSequences.start, newIteration); + + result.setRuleApplicationStatus(RuleApplicationStatus.RULE_APPLICATION_FINISHED); + return result; + } + + return null; + } + + /** + *+ * this method initiates the trial and error algorithm denoted in the description of this class. + * Its main purpose is the selection of a subpart of all children in the parent node in which + * equal sublists shall be searched. It is important, to always find the last iterations in a + * part first. The reason for this are iterations of iterations. If we always found the first + * iteration in a subpart first, then this may be an iteration of iterations. However, there + * may be subsequent iterations to be included in this iteration. But these iterations are not + * found yet, as they occur later in the sequence. Therefore, if we always find the last + * iteration in a sequence first, iterations of iterations are identified, last. + *
+ * + * @param parent the parent node in which iterations of children shall be found + * @param treeBuilder the tree builder that can be used for connecting task tree nodes + * @param nodeFactory the node factory that can be used for instantiating task tree nodes + * + * @return the iterated subsequences identified in a specific part (contains the equal + * subsequences as well as the start (inclusive) and end (exclusive) index of the + * subpart in which the sequences were found) + */ + private SubSequences getEqualSubsequences(ITaskTreeNode parent, + ITaskTreeBuilder treeBuilder, + ITaskTreeNodeFactory nodeFactory) + { + SubSequences subSequences = null; + + FIND_ITERATION: + for (int end = parent.getChildren().size(); end > 0; end--) { for (int start = 0; start < end; start++) { - List+ * for optimization purposes, we check if the length of the sublists to be identified as + * iterations has to be the same for any sublist. This only applies, if the minimum node + * equality to be checked for is lexical equality. If the children of the parent are all event + * tasks, then sublists can only be lexically equal, if they all have the same length. + * Therefore we check, if the minimal node equality is lexical equality. And if so, we also + * check if all children of the parent in which an iteration shall be searched for are event + * tasks. + *
* - */ - private List+ * this method starts at a specific position in the list of children of the provided parent + * and checks, if it finds a further sublist, that matches the already found sublists. If + * the sublist lengths must be equal, it only searches for a sublist of the same length of the + * already found sublists. The method calls itself if it identifies a further equal sublist but + * if the end of the subpart of children is not yet reached. + *
+ * + * @param subSequences the sublist found so far against which equality of the next + * sublist must be checked + * @param parent the parent node of which the children are analyzed + * @param start the starting index from which to start the next sublist to be + * identified + * @param end the end index (exclusive) of the current subpart of children + * in which iterations are searched for + * @param treeBuilder the tree builder that can be used for connecting task tree + * nodes + * @param nodeFactory the node factory that can be used for instantiating task tree + * nodes + * @param useEqualSublistLengths true if the sublists to be searched for all need to have the + * same length + * + * @return true if a further equal variant was found, false else + */ + private boolean findFurtherVariants(SubSequences subSequences, + ITaskTreeNode parent, + int start, + int end, + ITaskTreeBuilder treeBuilder, + ITaskTreeNodeFactory nodeFactory, + boolean useEqualSublistLengths) + { + boolean foundFurtherVariants = (start == end) && (subSequences.equalVariants.size() > 1); + + int minChildCount = 1; + int maxChildCount = end - start; + + if (useEqualSublistLengths && (subSequences.equalVariants.size() > 0)) { + minChildCount = subSequences.equalVariants.get(0).getChildren().size(); + maxChildCount = Math.min(minChildCount, maxChildCount); + } + + for (int childCount = minChildCount; childCount <= maxChildCount; childCount++) { + if (useEqualSublistLengths && (((end - start) % childCount) != 0)) { + continue; + } + + ISequence furtherVariant = nodeFactory.createNewSequence(); + + for (int j = start; j < start + childCount; j++) { + treeBuilder.addChild(furtherVariant, parent.getChildren().get(j)); + } + + boolean allVariantsEqual = true; + + for (ITaskTreeNode equalVariant : subSequences.equalVariants) { + NodeEquality nodeEquality = + nodeEqualityRuleManager.applyRules(equalVariant, furtherVariant); + if (!nodeEquality.isAtLeast(minimalNodeEquality)) { - return null; - } - else if (!nodeEquality.isAtLeast(NodeEquality.LEXICALLY_EQUAL)) { - // if the node is a syntactical or semantical equivalent of the first variant, - // then store it. - otherVariant[i] = parent.getChildren().get(parentIdx + i); - } - } - - // check, if there is a syntactically or semantically equal other variant. If so, add - // it to the list of variants - boolean semanticallyUnequal = false; - for (int i = 0; i < subListLen; i++) { - if (otherVariant[i] == null) { - otherVariant[i] = firstVariant[i]; + allVariantsEqual = false; + break; + } + } + + if (allVariantsEqual) { + + // we found a further variant. Add it to the list of variants and try to find + // further variants. Ignore, if none is available + int index = subSequences.equalVariants.size(); + subSequences.equalVariants.add(index, furtherVariant); + + foundFurtherVariants = findFurtherVariants + (subSequences, parent, start + childCount, end, treeBuilder, nodeFactory, + useEqualSublistLengths); + + if (foundFurtherVariants) { + subSequences.end = end; + break; } else { - semanticallyUnequal = true; - } - } - - if (semanticallyUnequal) { - equalVariants.add(otherVariant); - } - } - - return equalVariants; - } - - /** - *- * TODO: comment + subSequences.equalVariants.remove(index); + } + } + } + + return foundFurtherVariants; + } + + /** + *
+ * this method merges task tree nodes in a list, if they can be merged. for this, it tries + * to merge every node with every other node in the provided list using the + * {@link #mergeEqualTasks(ITaskTreeNode, ITaskTreeNode, ITaskTreeBuilder, ITaskTreeNodeFactory)} + * method. If a merge is possible, it removes the merged nodes from the list and adds the + * merge result. *
* - * @param equalVariants - * @param parent - * @return - */ - private boolean iterationMayContinue(List
- * TODO: comment
+ * @param nodes the list of nodes to be merged
+ * @param treeBuilder the tree builder that can be used for connecting task tree nodes
+ * @param nodeFactory the node factory that can be used for instantiating task tree nodes
+ */
+ private void mergeEqualNodes(List
+ * this method merges two equal tasks with each other if possible. If the tasks are lexically
+ * equal, the first of them is returned as merge result. If both tasks are of the same
+ * temporal relationship type, the appropriate merge method is called to merge them. If one
+ * of the nodes is a selection, the other one is added as a variant of this selection.
+ * (However, if both nodes are selections, they are merged using the appropriate merge method.)
+ * If merging is not possible, then a selection of both provided nodes is created and
+ * returned as merge result.
*
+ * merges equal sequences. This is done through trying to merge each node of sequence 1 with
+ * the node in sequence 2 being located at the same position. If not all children can be merged
+ * or if the sequences have different lengths, null is returned to indicate, that merging is
+ * not possible. For merging children, the
+ * {@link #mergeEqualTasks(ITaskTreeNode, ITaskTreeNode, ITaskTreeBuilder, ITaskTreeNodeFactory)}
+ * method is called.
+ *
+ * merges equal selections. This is done through trying to merge each node of selections with
+ * each other. For this, the method
+ * {@link #mergeEqualNodes(List, ITaskTreeBuilder, ITaskTreeNodeFactory)} is called with a
+ * join of the child list of both selections.
+ *
+ * merges equal iterations. This is done through merging the children of both iterations. If
+ * this is possible, a resulting iteration with the merge result of the children as its own
+ * child is returned. Otherwise null is returned to indicate that merging was not possible.
+ *
+ * this is a convenience method to create an iteration based on the identified and already
+ * merged iterated subsequences. This method creates the simplest iteration possible. As an
+ * example, if always the same task tree node is iterated, it becomes the child of the
+ * iteration. If a sequence of tasks is iterated, this sequence becomes the child of the
+ * iteration. It several equal sublists or nodes which are not lexically equal are iterated
+ * they become a selection which in turn become the child of the iteration.
+ *
+ * as the method has to denote all newly created parent nodes this method identifies them by
+ * comparing the existing subtree with the newly created iteration. Only those parent nodes
+ * in the new iteration, which are not already found in the existing sub tree are denoted as
+ * newly created. We do this in this way, as during the iteration detection algorithm, many
+ * parent nodes are created, which may be discarded later. It is easier to identify the
+ * remaining newly created parent nodes through this way than to integrate it into the
+ * algorithm.
+ *
+ * convenience method to determine all parent nodes existing in a subtree
+ *
+ * used to have a container for equal sublists identified in a sub part of the children of
+ * a parent node.
+ *
+ * the beginning of the subpart of the children of the parent node in which the sublists
+ * are found (inclusive)
+ *
+ * the end of the subpart of the children of the parent node in which the sublists
+ * are found (exclusive)
+ *
+ * the equal sublists found in the subpart of the children of the parent node
+ *