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

//   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.eventcore.guimodel.IGUIElement;
import de.ugoe.cs.autoquest.tasktrees.treeifc.IEventTask;
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;

/**
 * This rule structures the task tree based on GUI elements of the GUI model. The rule can
 * be provided with a filter for considered GUI elements. It generates sub sequences for any
 * GUI element in the hierarchy matching the filter so that each sequence represents all
 * interactions in a certain GUI element.
 * 
 * @version $Revision: $ $Date: 18.03.2012$
 * @author 2012, last modified by $Author: patrick$
 */
class DefaultGuiElementSequenceDetectionRule implements TemporalRelationshipRule {

    /**
     * <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 GUI element filter to be applied or null if none is specified.
     * </p>
     */
    private List<Class<? extends IGUIElement>> guiElementFilter;

    /**
     * <p>
     * instantiates the rule with a task tree node factory and builder to be used during rule
     * application but without a GUI element filter
     * </p>
     * 
     * @param taskTreeNodeFactory the task tree node factory to be used for creating substructures
     *                            for the temporal relationships identified during rule
     *                            application
     * @param taskTreeBuilder     the task tree builder to be used for creating substructures for
     *                            the temporal relationships identified during rule application
     */
    DefaultGuiElementSequenceDetectionRule(ITaskTreeNodeFactory taskTreeNodeFactory,
                                           ITaskTreeBuilder     taskTreeBuilder)
    {
        this(null, taskTreeNodeFactory, taskTreeBuilder);
    }
    
    /**
     * <p>
     * instantiates the rule with a GUI element filter. Only those types given in the filter will
     * be considered during the rule application. For all other types, no subsequences will be
     * created.
     * </p>
     *
     * @param guiElementFilter    the GUI element filter to be applied
     * @param taskTreeNodeFactory the task tree node factory to be used for creating substructures
     *                            for the temporal relationships identified during rule
     *                            application
     * @param taskTreeBuilder     the task tree builder to be used for creating substructures for
     *                            the temporal relationships identified during rule application
     */
    DefaultGuiElementSequenceDetectionRule(List<Class<? extends IGUIElement>> guiElementFilter,
                                           ITaskTreeNodeFactory taskTreeNodeFactory,
                                           ITaskTreeBuilder     taskTreeBuilder)
    {
        this.guiElementFilter = guiElementFilter;
        this.taskTreeNodeFactory = taskTreeNodeFactory;
        this.taskTreeBuilder = taskTreeBuilder;
    }

    /* (non-Javadoc)
     * @see java.lang.Object#toString()
     */
    @Override
    public String toString() {
        return "DefaultGuiElementSequenceDetectionRule";
    }

    /*
     * (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;
        }

        RuleApplicationResult result = new RuleApplicationResult();
        List<List<IGUIElement>> hierarchies = new ArrayList<List<IGUIElement>>();
        
        // collect information about the GUI hierarchy
        int maxHierarchyDepth = 0;
        IGUIElement guiElement;
        List<IGUIElement> guiElements = new ArrayList<IGUIElement>();
        List<IGUIElement> hierarchy;
        
        for (ITaskTreeNode child : parent.getChildren()) {
            guiElement = getGuiElement(child);
            guiElements.add(guiElement);
            hierarchy = getGuiElementHierarchy(guiElement);
            hierarchies.add(hierarchy);
            if (hierarchy != null) {
                maxHierarchyDepth = Math.max(maxHierarchyDepth, hierarchy.size());
            }
        }
        
        IGUIElement commonDenominator = getCommonDenominator(guiElements);
        hierarchy = getGuiElementHierarchy(commonDenominator);
        int initialHierarchyLevel = hierarchy != null ? hierarchy.size() : 0;
        
        // now generate sub sequences for the different GUI elements. Start at the hierarchy
        // level of the children of the common denominator to ensure, that different children are
        // found. If this level is already the maximum hierarchy depth, we do not need to condense
        // anything.
        
        RuleApplicationStatus status = null;
        if (initialHierarchyLevel < maxHierarchyDepth) {
            status = generateSubSequences
                (parent, hierarchies, initialHierarchyLevel, finalize, result);
        }
        
        if (status == null) {
            status = RuleApplicationStatus.RULE_NOT_APPLIED;
        }
            
        result.setRuleApplicationStatus(status);
        
        return result;
    }

    /**
     * <p>
     * generates subsequences for all groups of children of the provided parent, that operate
     * in different GUI elements at the provided hierarchy level. It will not generate a sub
     * sequence for the last elements, if the rule application shall not finalize.
     * </p>
     *
     * @param parent            the parent node of which the children shall be grouped
     * @param hierarchies       the GUI hierarchies for the children of the parent
     * @param hierarchyLevel    the current hierarchy level to be considered
     * @param maxHierarchyDepth the maximum hierarchy depth that may apply in this application
     * @param finalize          true, if the application shall be finalized, false else
     * @param result            the result of the rule application to add newly created parent
     *                          nodes to
     *                          
     * @return RULE_APPLICATION_FINISHED, if at least one subsequence was generated,
     *         RULE_APPLICATION_FEASIBLE, if the application shall not be finalized but some
     *         children could be condensed if further data was available, and RULE_NOT_APPLIED,
     *         if no subsequence was created and none is can be created, because no further
     *         data is expected
     */
    private RuleApplicationStatus generateSubSequences(ITaskTreeNode           parent,
                                                       List<List<IGUIElement>> hierarchies,
                                                       int                     hierarchyLevel,
                                                       boolean                 finalize,
                                                       RuleApplicationResult   result)
    {
        IGUIElement currentParent = null;
        List<IGUIElement> hierarchy;
        int startingIndex = -1;
        
        RuleApplicationStatus status = RuleApplicationStatus.RULE_NOT_APPLIED;
        boolean subsequenceHasStarted = false;
        boolean exceedingGuiHierarchyDepth = false;
        boolean nextGuiElementDiffers = false;
       
        currentParent = null;
        startingIndex = -1;

        int index = 0;
        while (index < parent.getChildren().size()) {
            hierarchy = hierarchies.get(index);

            exceedingGuiHierarchyDepth =
                hierarchy != null ? hierarchyLevel >= hierarchy.size() : true;
            nextGuiElementDiffers =
                subsequenceHasStarted &&
                (exceedingGuiHierarchyDepth || !currentParent.equals(hierarchy.get(hierarchyLevel)));


            if (!subsequenceHasStarted && !exceedingGuiHierarchyDepth) {
                currentParent = hierarchy.get(hierarchyLevel);
                startingIndex = index;
                subsequenceHasStarted = true;
            }
            else if (nextGuiElementDiffers) {
                status = condenseSequence
                    (parent, hierarchies, hierarchyLevel, startingIndex, index - 1, result);

                if (status != null) {
                    index = startingIndex + 1;
                }
                
                if (!exceedingGuiHierarchyDepth) {
                    currentParent = hierarchy.get(hierarchyLevel);
                    startingIndex = index;
                    subsequenceHasStarted = true;
                }
                else {
                    currentParent = null;
                    startingIndex = -1;
                    subsequenceHasStarted = false;
                }
            }
            
            index++;
        }

        if (finalize) {
            if (subsequenceHasStarted) {
                status = condenseSequence
                    (parent, hierarchies, hierarchyLevel, startingIndex,
                     parent.getChildren().size() - 1, result);
            }
            else if (status != RuleApplicationStatus.RULE_APPLICATION_FINISHED) {
                status = RuleApplicationStatus.RULE_NOT_APPLIED;
            }
        }
        else {
            if ((currentParent != null) &&
                (status != RuleApplicationStatus.RULE_APPLICATION_FINISHED))
            {
                status = RuleApplicationStatus.RULE_APPLICATION_FEASIBLE;
            }
        }

        return status;
    }

    /**
     * <p>
     * condenses a specified group of children on the provided parent to a subsequences and
     * calls {@link #generateSubSequences(ITaskTreeNode, List, int, boolean, ITaskTreeBuilder, ITaskTreeNodeFactory, RuleApplicationResult)}
     * for the newly created subsequence. The method does not condense subgroups consisting of
     * only one child which is already a sequence.
     * </p>
     *
     * @param parent         the parent task of which children shall be condensed
     * @param hierarchies    the GUI element hierarchies of the children of the parent
     * @param hierarchyLevel the currently considered GUI element hierarchy level
     * @param startIndex     the index of the first child belonging to the subgroup
     * @param endIndex       the index of the last child belonging to the subgroup
     * @param result         the result of the rule application to add newly created parent nodes to
     * 
     * @return RULE_APPLICATION_FINISHED, if at the subsequence was generated and RULE_NOT_APPLIED,
     *         if no subsequence was created, because only one child belonged to the group which
     *         was already a sequence
     */
    private RuleApplicationStatus condenseSequence(ITaskTreeNode           parent,
                                                   List<List<IGUIElement>> hierarchies,
                                                   int                     hierarchyLevel,
                                                   int                     startIndex,
                                                   int                     endIndex,
                                                   RuleApplicationResult   result)
    {
        boolean onlyASingleChildToReduce = (endIndex - startIndex) == 0;
        boolean singleChildIsSequence = onlyASingleChildToReduce &&
            parent.getChildren().get(startIndex) instanceof ISequence;

        if (!onlyASingleChildToReduce || !singleChildIsSequence) {
            ISequence sequence = taskTreeNodeFactory.createNewSequence();
            
            List<List<IGUIElement>> subHierarchies = new ArrayList<List<IGUIElement>>();
            List<IGUIElement> newHierarchy =
                hierarchies.get(startIndex).subList(0, hierarchyLevel + 1);
            taskTreeBuilder.setDescription
                (sequence, "interactions on " +
                 newHierarchy.get(newHierarchy.size() - 1).getStringIdentifier());

            for (int i = startIndex; i <= endIndex; i++) {
                taskTreeBuilder.addChild(sequence, parent.getChildren().get(startIndex));
                taskTreeBuilder.removeChild((ISequence) parent, startIndex);
                
                subHierarchies.add(hierarchies.remove(startIndex));
            }

            taskTreeBuilder.addChild((ISequence) parent, startIndex, sequence);
            
            hierarchies.add(startIndex, newHierarchy);
            
            generateSubSequences(sequence, subHierarchies, hierarchyLevel + 1, true, result);

            result.addNewlyCreatedParentNode(sequence);

            return RuleApplicationStatus.RULE_APPLICATION_FINISHED;
        }
        else {
            return null;
        }

    }

    /**
     * <p>
     * return a common denominator for the provided list of GUI elements, i.e. a GUI element, that
     * is part of the parent GUI hiearchy of all GUI elements in the list. If there is no common
     * denominator, the method returns null.
     * </p>
     */
    private IGUIElement getCommonDenominator(List<IGUIElement> guiElements) {
        IGUIElement commonDenominator = null;
        
        if (guiElements.size() > 0) {
            List<IGUIElement> commonDenominatorPath = new ArrayList<IGUIElement>();
            
            // create a reference list using the first GUI element
            IGUIElement guiElement = guiElements.get(0);
            while (guiElement != null) {
                if (guiElementMatchesConsideredTypes(guiElement)) {
                    commonDenominatorPath.add(0, guiElement);
                }
                guiElement = guiElement.getParent();
            }
            
            if (commonDenominatorPath.size() == 0) {
                return null;
            }
            
            // for each other GUI element, check the reference list for the first element in the
            // path, that is not common to the current one, and delete it as well as it subsequent
            // siblings
            List<IGUIElement> currentPath = new ArrayList<IGUIElement>();
            for (int i = 1; i < guiElements.size(); i++) {
                currentPath.clear();
                guiElement = guiElements.get(i);
                while (guiElement != null) {
                    if (guiElementMatchesConsideredTypes(guiElement)) {
                        currentPath.add(0, guiElement);
                    }
                    guiElement = guiElement.getParent();
                }
                
                // determine the index of the first unequal path element
                int index = 0;
                while ((index < commonDenominatorPath.size()) && (index < currentPath.size()) &&
                        commonDenominatorPath.get(index).equals(currentPath.get(index)))
                {
                    index++;
                }
                
                // remove all elements from the common denonimator path, that do not match
                while (index < commonDenominatorPath.size()) {
                    commonDenominatorPath.remove(index);
                }
            }
            
            if (commonDenominatorPath.size() > 0) {
                commonDenominator = commonDenominatorPath.get(commonDenominatorPath.size() - 1);
            }
        }
        
        return commonDenominator;
    }

    /**
     * <p>
     * returns the GUI element on which all interactions of the provided task takes place. If
     * the task is a simple event task its target is returned. If the task is a parent task
     * of several children, the common denominator of the GUI elements of all its children is
     * returned. The method returns null, if there is no common GUI element for all events
     * represented by the provided task.
     * </p>
     */
    private IGUIElement getGuiElement(ITaskTreeNode node) {
        if (node != null) {
            List<IGUIElement> terminalGuiElements = new ArrayList<IGUIElement>();
            getTerminalGuiElements(node, terminalGuiElements);
            return getCommonDenominator(terminalGuiElements);
        }
        else {
            return null;
        }
    }
        
    /**
     * <p>
     * recursive method calling itself to determine all terminal GUI elements of the provided
     * task. The terminal GUI elements are stored in the provided list.
     * </p>
     */
    private void getTerminalGuiElements(ITaskTreeNode node, List<IGUIElement> terminalGuiElements) {
        if (node instanceof IEventTask) {
            if (((IEventTask) node).getEventTarget() instanceof IGUIElement) {
                IGUIElement terminalGuiElement = (IGUIElement) ((IEventTask) node).getEventTarget();
                terminalGuiElement =
                    searchHierarchyForGuiElementWithConsideredType(terminalGuiElement);
                
                if (terminalGuiElement != null) {
                    terminalGuiElements.add(terminalGuiElement);
                }
            }
        }
        else {
            for (ITaskTreeNode child : node.getChildren()) {
                getTerminalGuiElements(child, terminalGuiElements);
            }
        }
    }

    /**
     * <p>
     * returns a list of GUI elements that represents the whole GUI element hierarchy of the
     * provided GUI element. The method considers the GUI element filter applied by this rule.
     * </p>
     */
    private List<IGUIElement> getGuiElementHierarchy(IGUIElement guiElement) {
        IGUIElement element = guiElement;
        
        if (!guiElementMatchesConsideredTypes(element)) {
            element = searchHierarchyForGuiElementWithConsideredType(element);
        }
        
        List<IGUIElement> hierarchy = new ArrayList<IGUIElement>();
        
        while (element != null) {
            hierarchy.add(0, element);
            element = searchHierarchyForGuiElementWithConsideredType(element.getParent());
        }
        
        if (hierarchy.size() > 0) {
            return hierarchy;
        }
        else {
            return null;
        }
    }

    /**
     * <p>
     * returns for a given GUI element the next GUI element in the upper GUI element hierarchy
     * that matches the GUI element filter of the rule. If the provided GUI element already
     * matches the filter, it is returned directly.
     * </p>
     */
    private IGUIElement searchHierarchyForGuiElementWithConsideredType(IGUIElement guiElement) {
        IGUIElement returnValue = guiElement;
        
        while ((returnValue != null) && !guiElementMatchesConsideredTypes(returnValue)) {
            returnValue = returnValue.getParent();
        }
        
        return returnValue;
    }

    /**
     * <p>
     * checks if the provided GUI element matches the GUI element filter applied by the rule.
     * </p>
     */
    private boolean guiElementMatchesConsideredTypes(IGUIElement guiElement) {
        if (guiElementFilter == null) {
            return true;
        }
        else {
            for (Class<? extends IGUIElement> clazz : guiElementFilter) {
                if (clazz.isInstance(guiElement)) {
                    return true;
                }
            }
            
            return false;
        }
    }

}