source: trunk/autoquest-core-events/src/main/java/de/ugoe/cs/autoquest/eventcore/guimodel/GUIModel.java @ 1088

//   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.eventcore.guimodel;

import java.io.OutputStream;
import java.io.PrintStream;
import java.io.UnsupportedEncodingException;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;
import java.util.logging.Level;

import de.ugoe.cs.util.console.Console;

/**
 * <p>
 * A GUI model is a tree of {@link IGUIElements} and represents a complete GUI of a software. It is
 * platform independent. It may have several root nodes, as some GUIs are made up of several Frames
 * being independent from each other. The GUI model is filled using the
 * {@link #integratePath(List, IGUIElementFactory)} method.
 * </p>
 * 
 * @version 1.0
 * @author Patrick Harms, Steffen Herbold
 */
public class GUIModel {

    /**
     * <p>
     * The root node of the tree not provided externally.
     * </p>
     */
    private TreeNode root = new TreeNode();

    /**
     * <p>
     * A list with all nodes currently known
     * </p>
     */
    private List<TreeNode> allNodes = new ArrayList<TreeNode>();

    /**
     * <p>
     * Integrates a path of GUI elements into the GUI model. The GUI model itself is a tree and
     * therefore a set of different paths through the tree that start with a root node and end with
     * a leaf node. Such a path can be added to the tree. The method checks, if any of the GUI
     * elements denoted by the path already exists. If so, it reuses it. It may therefore also
     * return an existing GUI element being the leaf node of the provided path. If a GUI element of
     * the path does not exist yet, it creates a new one using the provided GUI element factory.
     * </p>
     * <p>
     * If a GUI element specification describes an existing GUI element or not is determined through
     * comparing the GUI element specifications of the existing GUI elements with the ones provided
     * in the path. The comparison is done using the
     * {@link IGUIElementSpec#getSimilarity(IGUIElementSpec)} method. The comparison is only done on
     * the correct levels. I.e. the currently known root elements of the tree are only compared to
     * the first element in the path. If the correct one is found or created, its children are
     * compared only to the second specification in the path, and so on.
     * </p>
     * <p>
     * The returned GUI elements are singletons. I.e. it is tried to return always the identical
     * object for the same denoted element. However, while creating the GUI model, the similarity of
     * GUI elements may change. Therefore, the method might determine, that two formerly different
     * nodes are now similar. (This may happen, e.g. if GUI elements do not have initial names which
     * are set afterwards. Therefore, first they are handled differently and later they can be
     * identified as being the same.) In such a case, there are already several GUI element objects
     * instantiated for the same GUI element. The singleton paradigm gets broken. Therefore, such
     * GUI element objects are registered with each other, so that their equal method can determine
     * equality again correctly, although the objects are no singletons anymore.
     * </p>
     * 
     * @param guiElementPath
     *            the path to integrate into the model
     * @param guiElementFactory
     *            the GUI element factory to be used for instantiating GUI element objects
     * 
     * @return The GUI element object representing the GUI element denoted by the provided path
     * 
     * @throws GUIModelException
     *             thrown in cases such as the GUI element object could not be instantiated
     * @throws IllegalArgumentException
     *             if the provided path is invalid.
     */
    public IGUIElement integratePath(List<? extends IGUIElementSpec> guiElementPath,
                                     IGUIElementFactory guiElementFactory)
        throws GUIModelException, IllegalArgumentException
    {
        if ((guiElementPath == null) || (guiElementPath.size() <= 0)) {
            throw new IllegalArgumentException("GUI element path must contain at least one element");
        }

        List<IGUIElementSpec> remainingPath = new LinkedList<IGUIElementSpec>();

        for (IGUIElementSpec spec : guiElementPath) {
            remainingPath.add(spec);
        }

        return integratePath(root, remainingPath, guiElementFactory);
    }

    /**
     * <p>
     * Returns all children of the provided GUI element or null, if it does not have any or the node
     * is unknown.
     * </p>
     * 
     * @param guiElement
     *            the GUI element of which the children shall be returned
     * 
     * @return As described
     */
    public List<IGUIElement> getChildren(IGUIElement guiElement) {
        List<IGUIElement> result = null;
        for (TreeNode node : allNodes) {
            if (node.guiElement.equals(guiElement)) {
                if (result == null) {
                    result = new ArrayList<IGUIElement>();

                    if (node.children != null) {
                        for (TreeNode child : node.children) {
                            result.add(child.guiElement);
                        }
                    }
                }
                else {
                    Console
                        .traceln(Level.SEVERE,
                                 "Multiple nodes in the internal GUI model match the same GUI element. "
                                     + "This should not be the case and the GUI model is probably invalid.");
                }
            }
        }

        return result;
    }

    /**
     * <p>
     * Returns the parent GUI element of the provided GUI element or null, if it does not have a
     * parent (i.e. if it is a root node) or if the node is unknown.
     * </p>
     * 
     * @param guiElement
     *            the GUI element of which the parent shall be returned
     * 
     * @return As described
     */
    public IGUIElement getParent(IGUIElement guiElement) {
        IGUIElement parent = null;

        for (TreeNode node : allNodes) {
            if (node.children != null) {
                for (TreeNode child : node.children) {
                    if (child.guiElement.equals(guiElement)) {
                        if (parent != null) {
                            parent = node.guiElement;
                        }
                        else {
                            Console
                            .traceln(Level.SEVERE,
                                     "Multiple nodes in the internal GUI model match the same GUI element. "
                                             + "This should not be the case and the GUI model is probably invalid.");
                        }
                    }
                }
            }
        }

        return parent;
    }

    /**
     * <p>
     * Returns all root GUI elements of the model or an empty list, if the model is empty
     * </p>
     * 
     * @return As described
     */
    public List<IGUIElement> getRootElements() {
        List<IGUIElement> roots = new ArrayList<IGUIElement>();

        if (root.children != null) {
            for (TreeNode rootChild : root.children) {
                roots.add(rootChild.guiElement);
            }
        }

        return roots;
    }
    
    /**
     * returns a traverser for the GUI model to have efficient access to the tree of GUI elements
     * without having direct access.
     * 
     * @return a traverser
     */
    public Traverser getTraverser() {
        return new Traverser();
    }

    /**
     * returns a traverser for the GUI model starting at the given GUI element. Returns null, if
     * the GUI element is not part of the model.
     * 
     * @return a traverser
     */
    public Traverser getTraverser(IGUIElement startingAt) {
        TreeNode node = findNode(startingAt);
        
        if (node != null) {
            Traverser traverser = new Traverser();
            traverser.navigateTo(node);
            return traverser;
        }
        else {
            return null;
        }
    }

    /**
     * <p>
     * dumps the GUI model to the provided stream. Each node is represented through its toString()
     * method. If a node has children, those are dumped indented and surrounded by braces.
     * </p>
     * 
     * @param out
     *            The stream to dump the textual representation of the model to
     * @param encoding
     *            The encoding to be used while dumping
     */
    public void dump(OutputStream out, String encoding) {
        PrintStream stream;

        if (out instanceof PrintStream) {
            stream = (PrintStream) out;
        }
        else {
            String enc = encoding == null ? "UTF-8" : encoding;
            try {
                stream = new PrintStream(out, true, enc);
            }
            catch (UnsupportedEncodingException e) {
                throw new IllegalArgumentException("encodind " + enc + " not supported");
            }
        }

        for (TreeNode node : root.children) {
            dumpGUIElement(stream, node, "");
        }
    }

    /**
     * <p>
     * By calling this method, the GUIModel is traversed and similar nodes are merged.
     * </p>
     * 
     */
    public void condenseModel() {
        mergeSubTree(root);
    }
    
    /**
     * <p>
     * Merges the tree nodes of two GUI elements. The GUI elements need to have the same parent.
     * </p>
     * 
     * @param guiElement1
     *            the first merge GUI element
     * @param guiElement2
     *            the second merge GUI element
     * @throws IllegalArgumentException
     *             thrown if the two GUI elements do not have the same parent
     */
    public void mergeGUIElements(IGUIElement guiElement1, IGUIElement guiElement2)
        throws IllegalArgumentException
    {
        // check if both nodes have the same parent
        IGUIElement parentElement = guiElement1.getParent();
        if (parentElement != null && !parentElement.equals(guiElement2.getParent())) {
            throw new IllegalArgumentException("can only merge nodes with the same parent");
        }

        // get the TreeNode of the parent of the GUI elements
        TreeNode parent = findNode(parentElement);

        // get the TreeNodes for both GUI elements
        TreeNode node1 = findNode(guiElement1);
        TreeNode node2 = findNode(guiElement2);

        if (node1 == null || node2 == null) {
            throw new IllegalArgumentException(
                                               "Error while merging nodes: one element is not part of the GUI model!");
        }

        TreeNode replacement = mergeTreeNodes(node1, node2);

        if (parent != null) {
            // remove node1 and node2 from the parent's children and add the replacement instead
            // assumes that there are no duplicates of node1 and node2
            if (parent.children != null) {
                parent.children.set(parent.children.indexOf(node1), replacement);
                parent.children.remove(node2);
            }
        }

    }

    /**
     * <p>
     * internally integrates a path as the children of the provided parent node. This method is
     * recursive and calls itself, for the child of the parent node, that matches the first element
     * in the remaining path.
     * </p>
     * 
     * @param parentNode
     *            the parent node to add children for
     * @param guiElementPath
     *            the path of children to be created starting with the parent node
     * @param guiElementFactory
     *            the GUI element factory to be used for instantiating GUI element objects
     * 
     * @return The GUI element object representing the GUI element denoted by the provided path
     * 
     * @throws GUIModelException
     *             thrown in cases such as the GUI element object could not be instantiated
     */
    private IGUIElement integratePath(TreeNode parentNode,
                                      List<? extends IGUIElementSpec> remainingPath,
                                      IGUIElementFactory guiElementFactory)
        throws GUIModelException
    {
        IGUIElementSpec specToIntegrateElementFor = remainingPath.remove(0);

        TreeNode child = findEqualChild(parentNode, specToIntegrateElementFor);
        if (child == null) {
            IGUIElement newElement =
                guiElementFactory.instantiateGUIElement(specToIntegrateElementFor,
                                                        parentNode.guiElement);

            child = parentNode.addChild(newElement);
        }

        if (remainingPath.size() > 0) {
            return integratePath(child, remainingPath, guiElementFactory);
        }
        else {
            return child.guiElement;
        }
    }

    /**
     * <p>
     * Searches the children of a tree node to see if the {@link IGUIElementSpec} of equals the
     * specification of the {@link TreeNode#guiElement} of the child. If a match is found, the child
     * is returned.
     * </p>
     * 
     * @param parentNode
     *            parent node whose children are searched
     * @param specToMatch
     *            specification that is searched for
     * @return matching child node or null if no child matches
     */
    private TreeNode findEqualChild(TreeNode parentNode, IGUIElementSpec specToMatch) {
        if (parentNode.children != null) {
            for (TreeNode child : parentNode.children) {
                if (specToMatch.equals(child.guiElement.getSpecification())) {
                    return child;
                }
            }
        }
        return null;
    }

    /**
     * <p>
     * Merges all similar nodes in the sub-tree of the GUI model defined by the subTreeRoot.
     * </p>
     * <p>
     * The merging order is a bottom-up. This means, that we first call mergeSubTree recursively for
     * the grand children of the subTreeRoot, before we merge subTreeRoot.
     * </p>
     * <p>
     * The merging strategy is top-down. This means, that every time we merge two child nodes, we
     * call mergeSubTree recursively for all children of the merged nodes in order to check if we
     * can merge the children, too.
     * </p>
     * 
     * @param subTreeRoot
     *            root node of the sub-tree that is merged
     */
    private void mergeSubTree(TreeNode subTreeRoot) {
        if (subTreeRoot.children == null || subTreeRoot.children.isEmpty()) {
            return;
        }

        // lets first merge the grand children of the parentNode
        for (TreeNode child : subTreeRoot.children) {
            mergeSubTree(child);
        }

        boolean performedMerge;

        do {
            performedMerge = false;
            for (int i = 0; !performedMerge && i < subTreeRoot.children.size(); i++) {
                IGUIElementSpec elemSpec1 =
                    subTreeRoot.children.get(i).guiElement.getSpecification();
                for (int j = i + 1; !performedMerge && j < subTreeRoot.children.size(); j++) {
                    IGUIElementSpec elemSpec2 =
                        subTreeRoot.children.get(j).guiElement.getSpecification();
                    if (elemSpec1.getSimilarity(elemSpec2)) {
                        TreeNode replacement =
                            mergeTreeNodes(subTreeRoot.children.get(i), subTreeRoot.children.get(j));

                        subTreeRoot.children.set(i, replacement);
                        subTreeRoot.children.remove(j);
                        performedMerge = true;
                        i--;
                        break;
                    }
                }
            }
        }
        while (performedMerge);
    }

    /**
     * <p>
     * merges two nodes with each other. Merging means registering the GUI element objects with each
     * other for equality checks. Further it add all children of both nodes to a new replacing node.
     * Afterwards, all similar nodes of the replacement node are merged as well.
     * </p>
     * 
     * @param treeNode1
     *            the first of the two nodes to be merged
     * @param treeNode2
     *            the second of the two nodes to be merged
     * @return a tree node being the merge of the two provided nodes.
     */
    private TreeNode mergeTreeNodes(TreeNode treeNode1, TreeNode treeNode2) {
        // the following two lines are needed to preserve the references to the existing GUI
        // elements. If two elements are the same, one should be deleted to make the elements
        // singletons again. However, there may exist references to both objects. To preserve
        // these, we simply register the equal GUI elements with each other so that an equals
        // check can return true.
        treeNode1.guiElement.addEqualGUIElement(treeNode2.guiElement);
        treeNode2.guiElement.addEqualGUIElement(treeNode1.guiElement);

        // and now a replacement node that is the merge of treeNode1 and treeNode2 is created
        TreeNode replacement = new TreeNode();
        replacement.guiElement = treeNode1.guiElement;
        if (treeNode1.children != null) {
            for (TreeNode child : treeNode1.children) {
                replacement.addChildNode(child);
            }
        }
        if (treeNode2.children != null) {
            for (TreeNode child : treeNode2.children) {
                replacement.addChildNode(child);
            }
        }

        mergeSubTree(replacement);

        replacement.guiElement.updateSpecification(treeNode2.guiElement.getSpecification());

        // finally, update the known nodes list
        // if you don't do this getChildren will return wrong things and very bad things happen!
        allNodes.remove(treeNode1);
        allNodes.remove(treeNode2);
        allNodes.add(replacement);

        return replacement;
    }

    /**
     * <p>
     * dumps a GUI element to the stream. A dump contains the toString() representation of the GUI
     * element as well as a indented list of its children surrounded by braces. Therefore, not the
     * GUI element itself but its tree node is provided to have an efficient access to its children
     * </p>
     * 
     * @param out
     *            {@link PrintStream} where the guiElement is dumped to
     * @param node
     *            the guiElement's tree node of which the string representation is dumped
     * @param indent
     *            indent string of the dumping
     */
    private void dumpGUIElement(PrintStream out, TreeNode node, String indent) {
        out.print(indent);
        out.print(node.guiElement);

        if ((node.children != null) && (node.children.size() > 0)) {
            out.println(" {");

            for (TreeNode child : node.children) {
                dumpGUIElement(out, child, indent + "  ");
            }

            out.print(indent);
            out.print("}");
        }

        out.println();
    }
    
    /**
     * <p>
     * Retrieves the TreeNode associated with a GUI element. Returns null if no such TreeNode is
     * found.
     * </p>
     * 
     * @param element
     *            the GUI element
     * @return associated TreeNode; null if no such node exists
     */
    private TreeNode findNode(IGUIElement element) {
        if (element == null) {
            return null;
        }

        TreeNode result = null;
        for (TreeNode node : allNodes) {
            if (node.guiElement.equals(element)) {
                if (result == null) {
                    result = node;
                }
                else {
                    Console
                        .traceln(Level.SEVERE,
                                 "Multiple nodes in the internal GUI model match the same GUI element. "
                                     + "This should not be the case and the GUI model is probably invalid.");
                }
            }
        }
        return result;
    }

    /**
     * <p>
     * Used externally for tree traversal without providing direct access to the tree nodes
     * </p>
     * 
     * @version 1.0
     * @author Patrick Harms, Steffen Herbold
     */
    public class Traverser {
        
        /**
         * <p>
         * the stack of nodes on which the traverser currently works
         * </p>
         */
        private Stack<StackEntry> nodeStack = new Stack<StackEntry>();
        
        /**
         * <p>
         * initializes the traverser by adding the root node of the GUI model to the stack
         * </p>
         */
        private Traverser() {
            nodeStack.push(new StackEntry(root, 0));
        }
        
        /**
         * <p>
         * returns the first child of the current GUI element. On the first call of this method on
         * the traverser the first of the root GUI elements of the GUI model is returned. If the
         * current GUI element does not have children, the method returns null. If the GUI model
         * is empty, then a call to this method will return null. The returned GUI element is the
         * next one the traverser points to.
         * </p>
         *
         * @return as described.
         */
        public IGUIElement firstChild() {
            return pushChild(0);
        }
        
        /**
         * <p>
         * returns true, if the current GUI element has a first child, i.e. if the next call to the
         * method {@link #firstChild()} would return a GUI element or null.
         * </p>
         *
         * @return as described
         */
        public boolean hasFirstChild() {
            return
                (nodeStack.peek().treeNode.children != null) &&
                (nodeStack.peek().treeNode.children.size() > 0);
        }
        
        /**
         * <p>
         * returns the next sibling of the current GUI element. If there is no further sibling,
         * null is returned. If the current GUI element is one of the root nodes, the next root
         * node of the GUI model is returned. The returned GUI element is the next one the
         * traverser points to.
         * </p>
         *
         * @return as described
         */
        public IGUIElement nextSibling() {
            int lastIndex = nodeStack.pop().index;
            
            IGUIElement retval = pushChild(lastIndex + 1);
            if (retval == null) {
                pushChild(lastIndex);
            }
            
            return retval;
        }
        
        /**
         * <p>
         * returns true, if the current GUI element has a further sibling, i.e. if a call to the
         * method {@link #nextSibling()} will return a GUI element;
         * </p>
         *
         * @return as described
         */
        public boolean hasNextSibling() {
            boolean result = false;
            if (nodeStack.size() > 1) {
                StackEntry entry = nodeStack.pop();
                result = nodeStack.peek().treeNode.children.size() > (entry.index + 1);
                pushChild(entry.index);
            }
            
            return result;
        }
        
        /**
         * <p>
         * returns the parent GUI element of the current GUI element. If the current GUI element
         * is a root node, null is returned. If there is no current GUI element yet as the method
         * {@link #firstChild()} was not called yet, null is returned.
         * </p>
         *
         * @return as described
         */
        public IGUIElement parent() {
            IGUIElement retval = null;
            
            if (nodeStack.size() > 1) {
                nodeStack.pop();
                retval = nodeStack.peek().treeNode.guiElement;
            }
            
            return retval;
        }
        
        /**
         * <p>
         * internal method used for changing the state of the traverser. I.e. to switch to a
         * specific child GUI element of the current one.
         * </p>
         */
        private IGUIElement pushChild(int index) {
            IGUIElement retVal = null;
            
            if ((nodeStack.peek().treeNode.children != null) &&
                (nodeStack.peek().treeNode.children.size() > index))
            {
                nodeStack.push
                    (new StackEntry(nodeStack.peek().treeNode.children.get(index), index));
                retVal = nodeStack.peek().treeNode.guiElement;
            }
            
            return retVal;
        }
        
        /**
         * <p>
         * navigates the traverser to the given node in the GUI model
         * </p>
         */
        private boolean navigateTo(TreeNode node) {
            if (hasFirstChild()) {
                IGUIElement childElement = firstChild();
            
                while (childElement != null) {
                    if (childElement.equals(node.guiElement)) {
                        return true;
                    }
                    else if (navigateTo(node)) {
                        return true;
                    }
                    else {
                        childElement = nextSibling();
                    }
                }
            
                parent();
            }
            
            return false;
        }

        /**
         * <p>
         * internal class needed to fill the stack with nodes of the GUI models and their
         * respective index in the children of the parent node.
         * </p>
         */
        private class StackEntry {
            
            /** */
            private TreeNode treeNode;
            
            /** */
            private int index;
            
            /**
             * <p>
             * creates a new stack entry.
             * </p>
             */
            private StackEntry(TreeNode treeNode, int index) {
                this.treeNode = treeNode;
                this.index = index;
            }
        }
    }

    /**
     * <p>
     * Used internally for building up the tree of GUI elements.
     * </p>
     * 
     * @version 1.0
     * @author Patrick Harms, Steffen Herbold
     */
    private class TreeNode {

        /**
         * <p>
         * GUI element associated with the TreeNode.
         * </p>
         */
        private IGUIElement guiElement;

        /**
         * <p>
         * Children of the TreeNode.
         * </p>
         */
        private List<TreeNode> children;

        /**
         * <p>
         * Adds a child to the current node while keeping all lists of nodes up to date
         * </p>
         * 
         * @param guiElement
         *            GUI element that will be associated with the new child
         * @return the added child
         */
        private TreeNode addChild(IGUIElement guiElement) {
            if (children == null) {
                children = new ArrayList<TreeNode>();
            }

            TreeNode child = new TreeNode();
            child.guiElement = guiElement;
            children.add(child);

            allNodes.add(child);

            return child;
        }

        /**
         * 
         * <p>
         * Adds a TreeNode as child to the current node. This way, the whole sub-tree is added.
         * </p>
         * 
         * @param node
         *            child node that is added
         * @return node that has been added
         */
        private TreeNode addChildNode(TreeNode node) {
            if (children == null) {
                children = new ArrayList<TreeNode>();
            }
            children.add(node);
            return node;
        }

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