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

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;

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

    /*
     * (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) {
                    if (!finalize) {
                        // check, if the iteration may go on. This may be the case, if the detected
                        // iteration finishes with the last child of the parent, or if the
                        // remaining children, which were not identified as part of the iteration,
                        // start a further occurrence of the iteration
                        if (end == (parent.getChildren().size() - 1)) {
                            RuleApplicationResult result = new RuleApplicationResult();
                            result.setRuleApplicationStatus
                              (RuleApplicationStatus.RULE_APPLICATION_FEASIBLE);
                            return result;
                        }

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

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

                            allNodesEqual &=
                                nodeEquality.isAtLeast(NodeEquality.SYNTACTICALLY_EQUAL);
                        }

                        if (allNodesEqual) {
                            RuleApplicationResult result = new RuleApplicationResult();
                            result.setRuleApplicationStatus
                                (RuleApplicationStatus.RULE_APPLICATION_FEASIBLE);
                            return result;
                        }
                    }

                    RuleApplicationResult result = new RuleApplicationResult();
                    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);
                    }

                    // 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(NodeEquality.LEXICALLY_EQUAL)) {
                    if (nodeEquality.isAtLeast(NodeEquality.SEMANTICALLY_EQUAL)) {
                        otherVariant[i] = parent.getChildren().get(parentIdx + i);
                    }
                    else {
                        return null;
                    }
                }
            }

            // check, if there is a 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;
    }

}