source: trunk/autoquest-core-tasktrees/src/main/java/de/ugoe/cs/autoquest/tasktrees/temporalrelation/IterationOfSubtreesDetectionRule.java @ 1131

//   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;

/**
 * <p>
 * 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.
 * </p>
 * <p>
 * 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.
 * </p>
 * <p>
 * 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.
 * <ul>
 *   <li>for all possible subparts of the children of the provided parent
 *   <ul>
 *     <li>for all possible first sublists in the subpart
 *     <ul>
 *       <li>for all succeeding next sublists in this part</li>
 *       <ul>
 *         <li>check if this sublist is equal to all previously identified sublist in this part</li>
 *       </ul>
 *     </ul>
 *     <li>
 *       if a combination of sublists is found in this subpart which are all equal to each other
 *       at the provided minimal equality level, an iteration in this subpart was found.
 *     </li>
 *       <ul>
 *         <li>merge the identified equal sublists to an iteration</li>
 *       </ul>
 *   </ul>
 * </ul>
 * The algorithm tries to optimize if all children are event tasks and if the sublists shall be
 * lexically equal. In this case, the sublist all have to have the same length. The trial and
 * error reduces to a minimum of possible sublists.
 * </p>
 * 
 * @author Patrick Harms
 */
class IterationOfSubtreesDetectionRule implements TemporalRelationshipRule {

    /**
     * <p>
     * the maximum length for iterated sequences
     * </p>
     */
    private static final int MAX_LENGTH_OF_ITERATED_SEQUENCE = 50;
    
    /**
     * <p>
     * the task tree node factory to be used for creating substructures for the temporal
     * relationships identified during rule
     * </p>
     */
    private ITaskTreeNodeFactory taskTreeNodeFactory;
    /**
     * <p>
     * the task tree builder to be used for creating substructures for the temporal relationships
     * identified during rule application
     * </p>
     */
    private ITaskTreeBuilder taskTreeBuilder;

    /**
     * <p>
     * the node comparator used for comparing task tree nodes with each other
     * </p>
     */
    private TaskTreeNodeComparator nodeComparator;

    /**
     * <p>
     * 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.
     * </p>
     */
    IterationOfSubtreesDetectionRule(NodeEqualityRuleManager nodeEqualityRuleManager,
                                     NodeEquality            minimalNodeEquality,
                                     ITaskTreeNodeFactory    taskTreeNodeFactory,
                                     ITaskTreeBuilder        taskTreeBuilder)
    {
        this.taskTreeNodeFactory = taskTreeNodeFactory;
        this.taskTreeBuilder = taskTreeBuilder;
        
        this.nodeComparator =
            new TaskTreeNodeComparator(nodeEqualityRuleManager, minimalNodeEquality);
    }

    /**
     * <p>
     * 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.
     * </p>
     */
    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<ITaskTreeNode> children = parent.getChildren();
        
        // parent must already have at least 2 children
        if ((children == null) || (children.size() < 2)) {
            return null;
        }
        
        SubSequences subSequences = getEqualSubsequences(children);

        if (subSequences != null) {
            RuleApplicationResult result = new RuleApplicationResult();

            // merge the identified variants, but preserve the differences in form of selections
            // by using lexical equality for merge comparisons
            TaskTreeNodeMerger merger = new TaskTreeNodeMerger
                (taskTreeNodeFactory, taskTreeBuilder, nodeComparator);

            merger.mergeTaskNodes(subSequences.equalVariants);
            
            IIteration newIteration =
                createIterationBasedOnIdentifiedVariants(subSequences, result);

            determineNewlyCreatedParentTasks(parent, newIteration, result);
            
            // remove iterated children
            for (int j = subSequences.start; j < subSequences.end; j++) {
                taskTreeBuilder.removeChild((ISequence) parent, subSequences.start);
            }

            // add the new iteration instead
            taskTreeBuilder.addChild((ISequence) parent, subSequences.start, newIteration);

            result.setRuleApplicationStatus(RuleApplicationStatus.FINISHED);
            return result;
        }

        return null;
    }

    /**
     * <p>
     * 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.
     * </p>
     * 
     * @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<ITaskTreeNode> nodes) {
        SubSequences subSequences = null;

        // to find longer iterations first, start with long sequences
        FIND_ITERATION:
        for (int end = nodes.size(); end > 0; end--) {
            for (int start = 0; start < end; start++) {
                boolean useEqualSublistLengths = equalSublistLengthsCanBeUsed(nodes, start, end);

                subSequences = new SubSequences();
                subSequences.start = start;

                boolean foundFurtherVariants = findFurtherVariants
                    (subSequences, nodes, start, end, useEqualSublistLengths);

                if (foundFurtherVariants) {
                    break FIND_ITERATION;
                }
                else {
                    subSequences = null;
                }
            }
        }
        
        return subSequences;
    }

    /**
     * <p>
     * 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.
     * </p>
     *
     * @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<ITaskTreeNode> nodes, int start, int end) {
        boolean equalLengthsCanBeUsed =
            nodeComparator.getConsideredNodeEquality().isAtLeast(NodeEquality.LEXICALLY_EQUAL);
        
        if (equalLengthsCanBeUsed) {
            for (int i = start; i < end; i++) {
                if (!(nodes.get(i) instanceof IEventTask)) {
                    equalLengthsCanBeUsed = false;
                    break;
                }
            }
        }

        return equalLengthsCanBeUsed;
    }

    /**
     * <p>
     * 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.
     * </p>
     * 
     * @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<ITaskTreeNode> nodes,
                                        int                 start,
                                        int                 end,
                                        boolean             useEqualSublistLengths)
    {
        boolean foundFurtherVariants = (start == end) && (subSequences.equalVariants.size() > 1);
        
        int minChildCount = 1;
        int maxChildCount = Math.min(MAX_LENGTH_OF_ITERATED_SEQUENCE, 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 = taskTreeNodeFactory.createNewSequence();
            
            for (int j = start; j < start + childCount; j++) {
                taskTreeBuilder.addChild(furtherVariant, nodes.get(j));
            }
            
            boolean allVariantsEqual = true;
            
            for (ITaskTreeNode equalVariant : subSequences.equalVariants) {
                if (!nodeComparator.equals(equalVariant, furtherVariant)) {
                    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, nodes, start + childCount, end, useEqualSublistLengths);

                if (foundFurtherVariants) {
                    subSequences.end = end;
                    break;
                }
                else {
                    subSequences.equalVariants.remove(index);
                }
            }
        }
        
        return foundFurtherVariants;
    }

    /**
     * <p>
     * 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.
     * </p>
     *
     * @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;
    }

    /**
     * <p>
     * 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.
     * </p>
     * 
     * @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<ITaskTreeNode> existingParentNodes = getParentNodes(existingSubTree);
        List<ITaskTreeNode> newParentNodes = getParentNodes(newSubTree);
        
        boolean foundNode;
        for (ITaskTreeNode newParentNode : newParentNodes) {
            foundNode = false;
            for (ITaskTreeNode existingParentNode : existingParentNodes) {
                // It is sufficient to compare the references. The algorithm reuses nodes as they
                // are. So any node existing in the new structure that is also in the old structure
                // was unchanged an therefore does not need to be handled as a newly created one.
                // but every node in the new structure that is not included in the old structure
                // must be treated as a newly created one.
                if (newParentNode == existingParentNode) {
                    foundNode = true;
                    break;
                }
            }
            
            if (!foundNode) {
                result.addNewlyCreatedParentNode(newParentNode);
            }
        }
        
    }

    /**
     * <p>
     * convenience method to determine all parent nodes existing in a subtree
     * </p>
     *
     * @param subtree the subtree to search for parent nodes in
     * 
     * @return a list of parent nodes existing in the subtree
     */
    private List<ITaskTreeNode> getParentNodes(ITaskTreeNode subtree) {
        List<ITaskTreeNode> parentNodes = new ArrayList<ITaskTreeNode>();
        
        List<ITaskTreeNode> children = subtree.getChildren();
        
        if (children.size() > 0) {
            parentNodes.add(subtree);
            
            for (ITaskTreeNode child : children) {
                parentNodes.addAll(getParentNodes(child));
            }
        }
        
        return parentNodes;
    }

    /**
     * <p>
     * used to have a container for equal sublists identified in a sub part of the children of
     * a parent node.
     * </p>
     * 
     * @author Patrick Harms
     */
    private static class SubSequences {

        /**
         * <p>
         * the beginning of the subpart of the children of the parent node in which the sublists
         * are found (inclusive)
         * </p>
         */
        public int start;
        
        /**
         * <p>
         * the end of the subpart of the children of the parent node in which the sublists
         * are found (exclusive)
         * </p>
         */
        public int end;
        
        /**
         * <p>
         * the equal sublists found in the subpart of the children of the parent node
         * </p>
         */
        List<ITaskTreeNode> equalVariants = new ArrayList<ITaskTreeNode>();
        
    }

}