source: trunk/quest-core-tasktrees/src/main/java/de/ugoe/cs/quest/tasktrees/temporalrelation/DefaultIterationDetectionRule.java @ 805

package de.ugoe.cs.quest.tasktrees.temporalrelation;

import java.util.ArrayList;
import java.util.List;

import de.ugoe.cs.quest.tasktrees.nodeequality.NodeEquality;
import de.ugoe.cs.quest.tasktrees.nodeequality.NodeEqualityRuleManager;
import de.ugoe.cs.quest.tasktrees.treeifc.IIteration;
import de.ugoe.cs.quest.tasktrees.treeifc.ISelection;
import de.ugoe.cs.quest.tasktrees.treeifc.ISequence;
import de.ugoe.cs.quest.tasktrees.treeifc.ITaskTreeBuilder;
import de.ugoe.cs.quest.tasktrees.treeifc.ITaskTreeNode;
import de.ugoe.cs.quest.tasktrees.treeifc.ITaskTreeNodeFactory;

/**
 * TODO comment
 * 
 * @version $Revision: $ $Date: 19.02.2012$
 * @author 2012, last modified by $Author: patrick$
 */
public class DefaultIterationDetectionRule implements TemporalRelationshipRule {
    
    /** */
    private NodeEqualityRuleManager nodeEqualityRuleManager;

    /** */
    private NodeEquality minimalNodeEquality;

    /**
     * TODO: comment
     * 
     */
    DefaultIterationDetectionRule(NodeEqualityRuleManager nodeEqualityRuleManager,
                                  NodeEquality            minimalNodeEquality)
    {
        super();
        this.nodeEqualityRuleManager = nodeEqualityRuleManager;
        this.minimalNodeEquality = minimalNodeEquality;
    }

    /*
     * (non-Javadoc)
     * 
     * @see TemporalRelationshipRule#apply(TaskTreeNode, TaskTreeBuilder, TaskTreeNodeFactory)
     */
    @Override
    public RuleApplicationResult apply(ITaskTreeNode        parent,
                                       ITaskTreeBuilder     treeBuilder,
                                       ITaskTreeNodeFactory nodeFactory,
                                       boolean              finalize)
    {
        if (!(parent instanceof ISequence)) {
            return null;
        }

        // 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--) {
            for (int start = 0; start < end; start++) {
                List<ITaskTreeNode[]> equalVariants =
                    getEqualSublistVariantsInBoundaries(parent, start, end);

                if (equalVariants != null) {
                    RuleApplicationResult result = new RuleApplicationResult();
                    
                    if ((!finalize) && (iterationMayContinue(equalVariants, parent, end + 1))) {
                        result.setRuleApplicationStatus
                              (RuleApplicationStatus.RULE_APPLICATION_FEASIBLE);
                        return result;
                    }

                    IIteration newIteration = createIterationBasedOnIdentifiedVariants
                         (equalVariants, treeBuilder, nodeFactory, result);
                    

                    // remove iterated children
                    for (int j = end; j >= start; j--) {
                        treeBuilder.removeChild((ISequence) parent, j);
                    }

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

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

        return null;
    }

    /**
     * TODO: comment
     * 
     * @return
     */
    private List<ITaskTreeNode[]> getEqualSublistVariantsInBoundaries(ITaskTreeNode parent,
                                                                      int           start,
                                                                      int           end)
    {
        List<ITaskTreeNode[]> equalVariants = null;

        int noOfChildrenInBoundaries = end - start + 1;

        for (int subListLen = 1; subListLen <= (noOfChildrenInBoundaries / 2); subListLen++)
        {
            if ((noOfChildrenInBoundaries % subListLen) == 0) {
                equalVariants =
                    getEqualSublistVariantsForSubListLength(parent, start, end, subListLen);

                if (equalVariants != null) {
                    return equalVariants;
                }
            }
        }

        return null;
    }

    /**
     *
     */
    private List<ITaskTreeNode[]> getEqualSublistVariantsForSubListLength(ITaskTreeNode parent,
                                                                          int           start,
                                                                          int           end,
                                                                          int           subListLen)
    {
        List<ITaskTreeNode[]> equalVariants = new ArrayList<ITaskTreeNode[]>();
        ITaskTreeNode[] firstVariant = new ITaskTreeNode[subListLen];

        for (int i = 0; i < subListLen; i++) {
            firstVariant[i] = parent.getChildren().get(start + i);
        }

        equalVariants.add(firstVariant);

        for (int parentIdx = (start + subListLen); parentIdx <= end; parentIdx += subListLen)
        {
            ITaskTreeNode[] otherVariant = new ITaskTreeNode[subListLen];

            for (int i = 0; i < subListLen; i++) {
                NodeEquality nodeEquality = nodeEqualityRuleManager.applyRules
                    (firstVariant[i], parent.getChildren().get(parentIdx + i));

                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];
                }
                else {
                    semanticallyUnequal = true;
                }
            }

            if (semanticallyUnequal) {
                equalVariants.add(otherVariant);
            }
        }

        return equalVariants;
    }

    /**
     * <p>
     * TODO: comment
     * </p>
     *
     * @param equalVariants
     * @param parent
     * @return
     */
    private boolean iterationMayContinue(List<ITaskTreeNode[]> equalVariants,
                                         ITaskTreeNode         parent,
                                         int                   remainderIndex)
    {
        // check, if the iteration may go on. This may be the case, if the
        // remaining children, which were not identified as part of the iteration,
        // start a further occurrence of the iteration

        boolean allNodesEqual = true;
        for (int i = 0; ((allNodesEqual) && (i < equalVariants.get(0).length)); i++)
        {
            if ((remainderIndex + i) >= parent.getChildren().size()) {
                break;
            }

            NodeEquality nodeEquality = nodeEqualityRuleManager.applyRules
                (equalVariants.get(0)[i], parent.getChildren().get(remainderIndex + i));

            allNodesEqual &= nodeEquality.isAtLeast(minimalNodeEquality);
        }

        return allNodesEqual;
    }
    
    /**
     * <p>
     * TODO: comment
     * </p>
     *
     * @param equalVariants
     * @param result
     * @return
     */
    private IIteration createIterationBasedOnIdentifiedVariants(List<ITaskTreeNode[]> equalVariants,
                                                                ITaskTreeBuilder      treeBuilder,
                                                                ITaskTreeNodeFactory  nodeFactory,
                                                                RuleApplicationResult result)
    {
        IIteration newIteration = nodeFactory.createNewIteration();
        result.addNewlyCreatedParentNode(newIteration);

        if (equalVariants.size() == 1) {
            // all children are the same. Create an iteration of this child
            if (equalVariants.get(0).length == 1) {
                // all children are the same. Create an iteration of this child
                treeBuilder.setChild(newIteration, equalVariants.get(0)[0]);
            }
            else {
                // there was an iteration of structurally equal sequences
                ISequence sequence = nodeFactory.createNewSequence();
                result.addNewlyCreatedParentNode(sequence);

                for (ITaskTreeNode node : equalVariants.get(0)) {
                    treeBuilder.addChild(sequence, node);
                }

                treeBuilder.setChild(newIteration, sequence);
            }
        }
        else {
            // there are distinct variants of semantically equal subsequences or
            // children -->
            // create an iterated selection
            ISelection selection = nodeFactory.createNewSelection();
            result.addNewlyCreatedParentNode(selection);

            for (ITaskTreeNode[] variant : equalVariants) {
                if (variant.length == 1) {
                    treeBuilder.addChild(selection, variant[0]);
                }
                else {
                    ISequence sequence = nodeFactory.createNewSequence();
                    result.addNewlyCreatedParentNode(sequence);

                    for (ITaskTreeNode node : variant) {
                        treeBuilder.addChild(sequence, node);
                    }

                    treeBuilder.addChild(selection, sequence);
                }
            }

            treeBuilder.setChild(newIteration, selection);
        }
        
        return newIteration;
    }

}