// Copyright 2012 Georg-August-Universität Göttingen, Germany // // Licensed under the Apache License, Version 2.0 (the "License"); // you may not use this file except in compliance with the License. // You may obtain a copy of the License at // // http://www.apache.org/licenses/LICENSE-2.0 // // Unless required by applicable law or agreed to in writing, software // distributed under the License is distributed on an "AS IS" BASIS, // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. // See the License for the specific language governing permissions and // limitations under the License. package de.ugoe.cs.autoquest.tasktrees.temporalrelation; import java.util.ArrayList; import java.util.List; import de.ugoe.cs.autoquest.tasktrees.nodeequality.NodeEquality; import de.ugoe.cs.autoquest.tasktrees.nodeequality.NodeEqualityRuleManager; import de.ugoe.cs.autoquest.tasktrees.treeifc.IEventTask; import de.ugoe.cs.autoquest.tasktrees.treeifc.IIteration; import de.ugoe.cs.autoquest.tasktrees.treeifc.ISelection; import de.ugoe.cs.autoquest.tasktrees.treeifc.ISequence; import de.ugoe.cs.autoquest.tasktrees.treeifc.ITaskTreeBuilder; import de.ugoe.cs.autoquest.tasktrees.treeifc.ITaskTreeNode; import de.ugoe.cs.autoquest.tasktrees.treeifc.ITaskTreeNodeFactory; /** *
* 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 maximum length for iterated sequences *
*/ private static final int MAX_LENGTH_OF_ITERATED_SEQUENCE = 50; /** ** the task tree node factory to be used for creating substructures for the temporal * relationships identified during rule *
*/ private ITaskTreeNodeFactory taskTreeNodeFactory; /** ** the task tree builder to be used for creating substructures for the temporal relationships * identified during rule application *
*/ private ITaskTreeBuilder taskTreeBuilder; /** ** the node comparator used for comparing task tree nodes with each other *
*/ private TaskTreeNodeComparator nodeComparator; /** ** 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. *
*/ IterationOfSubtreesDetectionRule(NodeEqualityRuleManager nodeEqualityRuleManager, NodeEquality minimalNodeEquality, ITaskTreeNodeFactory taskTreeNodeFactory, ITaskTreeBuilder taskTreeBuilder) { this.taskTreeNodeFactory = taskTreeNodeFactory; this.taskTreeBuilder = taskTreeBuilder; this.nodeComparator = new TaskTreeNodeComparator(nodeEqualityRuleManager, minimalNodeEquality); } /** ** 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. *
*/ IterationOfSubtreesDetectionRule(TaskTreeNodeComparator nodeComparator, ITaskTreeNodeFactory taskTreeNodeFactory, ITaskTreeBuilder taskTreeBuilder) { this.nodeComparator = nodeComparator; this.taskTreeNodeFactory = taskTreeNodeFactory; this.taskTreeBuilder = taskTreeBuilder; } /* (non-Javadoc) * @see java.lang.Object#toString() */ @Override public String toString() { return "IterationOfSubtreesDetectionRule"; } /* * (non-Javadoc) * * @see de.ugoe.cs.tasktree.temporalrelation.TemporalRelationshipRule#apply(TaskTreeNode, * boolean) */ @Override public RuleApplicationResult apply(ITaskTreeNode parent, boolean finalize) { if (!(parent instanceof ISequence)) { return null; } if (!finalize) { // the rule is always feasible as iterations may occur at any time RuleApplicationResult result = new RuleApplicationResult(); result.setRuleApplicationStatus(RuleApplicationStatus.FEASIBLE); return result; } List* 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 the provided list of nodes 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 nodes the list of nodes in which iterations shall be found * * @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(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 nodes in the provided list 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 nodes in the list in which an iteration shall be searched for are event tasks. *
* * @param nodes the list of nodes to search for iterations * @param start the beginning of the subpart (inclusive) to be considered * @param end the end of the subpart (exclusive) to be considered * * @return true, if the sublists must have the same lengths, false else */ private boolean equalSublistLengthsCanBeUsed(List* this method starts at a specific position in the provided list of nodes 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 the provided list is not yet reached. *
* * @param subSequences the sublist found so far against which equality of the next * sublist must be checked * @param nodes the list of nodes to be checked for iterations * @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 list of * nodes in which iterations are searched for * @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, List* 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. *
* * @param subsequences the identified and already merged equal subsequences * * @return the resulting iteration */ private IIteration createIterationBasedOnIdentifiedVariants(SubSequences subsequences, RuleApplicationResult result) { IIteration newIteration = taskTreeNodeFactory.createNewIteration(); result.addNewlyCreatedParentNode(newIteration); if (subsequences.equalVariants.size() == 1) { // all children are the same. Create an iteration of this child if (subsequences.equalVariants.get(0).getChildren().size() == 1) { // there is only one equal variant and this has only one child. So create an // iteration of this child taskTreeBuilder.setChild (newIteration, subsequences.equalVariants.get(0).getChildren().get(0)); } else { // there was an iteration of one equal sequence taskTreeBuilder.setChild(newIteration, subsequences.equalVariants.get(0)); result.addNewlyCreatedParentNode(subsequences.equalVariants.get(0)); } } else { // there are distinct variants of equal subsequences or children --> create an // iterated selection ISelection selection = taskTreeNodeFactory.createNewSelection(); result.addNewlyCreatedParentNode(selection); for (ITaskTreeNode variant : subsequences.equalVariants) { if (variant.getChildren().size() == 1) { taskTreeBuilder.addChild(selection, variant.getChildren().get(0)); } else { taskTreeBuilder.addChild(selection, variant); result.addNewlyCreatedParentNode(variant); } } taskTreeBuilder.setChild(newIteration, selection); } return newIteration; } /** ** 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. *
* * @param existingSubTree the existing subtree * @param newSubTree the identified iteration * @param result the rule application result into which the newly created parent nodes * shall be stored. */ private void determineNewlyCreatedParentTasks(ITaskTreeNode existingSubTree, ITaskTreeNode newSubTree, RuleApplicationResult result) { List* convenience method to determine all parent nodes existing in a subtree *
* * @param subtree the subtree to search for parent nodes in * * @return a list of parent nodes existing in the subtree */ private List* used to have a container for equal sublists identified in a sub part of the children of * a parent node. *
* * @author Patrick Harms */ private static class SubSequences { /** ** the beginning of the subpart of the children of the parent node in which the sublists * are found (inclusive) *
*/ public int start; /** ** the end of the subpart of the children of the parent node in which the sublists * are found (exclusive) *
*/ public int end; /** ** the equal sublists found in the subpart of the children of the parent node *
*/ List