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

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

import de.ugoe.cs.autoquest.eventcore.IHierarchicalEventTargetModel;
import de.ugoe.cs.util.console.Console;

/**
 * <p>
 * A hierarchical event target model is a tree of {@link IHierarchicalEventTarget}s and represents
 * a complete user interface, e.g. GUI of a software. It is platform independent. It may have
 * several root nodes, as some user interfaces are made up of several frames (GUI) or scenes (VR)
 * being independent from each other. The event target model is filled using the
 * {@link #integratePath(List, IEventTargetFactory)} method.
 * </p>
 * 
 * @version 1.0
 * @author Patrick Harms, Steffen Herbold
 */
public class HierarchicalEventTargetModel<T extends IHierarchicalEventTarget>
     implements Serializable, IHierarchicalEventTargetModel<T>
{

    /**  */
    private static final long serialVersionUID = 1L;

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

    /**
     * <p>
     * A map with all nodes currently known
     * </p>
     */
    private Map<T, TreeNode> allNodes = new HashMap<T, TreeNode>();
    
    /**
     * <p>
     * true, if internal validation is switched on, false else
     * </p>
     */
    private boolean validate = false;

    /**
     * <p>
     * Default constructor to create a event target model without internal validation
     * </p>
     *
     */
    public HierarchicalEventTargetModel() {
        this(false);
    }

    /**
     * <p>
     * creates an event target model, that internally validates itself by checking on access to
     * nodes, if several event targets pretend to be equal or if several distinct event targets
     * have the same child.
     * </p>
     *
     * @param validate
     *            true if internal validation shall be switched on (bad performance), false else
     *
     */
    public HierarchicalEventTargetModel(boolean validate) {
        this.validate = validate;
    }

    /**
     * <p>
     * Integrates a path of event targets into the event target model. The event target 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 event targets denoted by the path already exists. If so, it reuses it.
     * It may therefore also return an existing event target being the leaf node of the provided
     * path. If an event target of the path does not exist yet, it creates a new one using the
     * provided event target factory.
     * </p>
     * <p>
     * If an event target specification describes an existing event target or not is determined
     * through comparing the event target specifications of the existing event targets with the
     * ones provided in the path. The comparison is done using the
     * {@link IEventTargetSpec#getSimilarity(IEventTargetSpec)} 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 event targets are singletons. I.e. it is tried to return always the identical
     * object for the same denoted element. However, while creating the event target model, the
     * similarity of event targets may change. Therefore, the method might determine, that two
     * formerly different nodes are now similar. (This may happen, e.g. if event targets 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 event target objects instantiated for the same event target. The singleton paradigm
     * gets broken. Therefore, such event target 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 eventTargetPath
     *            the path to integrate into the model
     * @param eventTargetFactory
     *            the event target factory to be used for instantiating event target objects
     * 
     * @return The event target object representing the event target denoted by the provided path
     * 
     * @throws EventTargetModelException
     *             thrown in cases such as the event target object could not be instantiated
     * @throws IllegalArgumentException
     *             if the provided path is invalid.
     */
    public T integratePath(List<? extends IEventTargetSpec> eventTargetPath,
                           IEventTargetFactory              eventTargetFactory)
        throws EventTargetModelException, IllegalArgumentException
    {
        if ((eventTargetPath == null) || (eventTargetPath.size() <= 0)) {
            throw new IllegalArgumentException("event target path must contain at least one element");
        }

        List<IEventTargetSpec> remainingPath = new LinkedList<IEventTargetSpec>(eventTargetPath);

        return (T) integratePath(root, remainingPath, eventTargetFactory);
    }

    /* (non-Javadoc)
     * @see IEventTargetModel#getChildren(IEventTarget)
     */
    @Override
    public List<T> getChildren(T eventTarget) {
        TreeNode node = findNode(eventTarget);
        
        List<T> result = null;
        if (node != null) {
            result = new LinkedList<T>();
            if (node.children != null) {
                for (TreeNode child : node.children) {
                    result.add((T) child.eventTarget);
                }
            }
        }
        else {
            boolean found = false;
            for (Map.Entry<T, TreeNode> entry : allNodes.entrySet()) {
                if (entry.getKey().equals(eventTarget)) {
                    if (!found) {
                        System.out.println(eventTarget.hashCode() + "  " + entry.getKey().hashCode());
                        found = true;
                    }
                    else {
                        Console.traceln(Level.SEVERE, "Multiple nodes in the internal event " +
                                        "target model match the same event target. This should " +
                                        "not be the case and the event target model is probably " +
                                        "invalid.");
                    }
                }
            }
            
            if (!found) {
                Console.traceln(Level.SEVERE, "event target belonging to model not found in model");
            }
        }
 
        return result;
    }

    /* (non-Javadoc)
     * @see IEventTargetModel#getParent(IEventTarget)
     */
    @Override
    public T getParent(T eventTarget) {
        T parent = null;

        for (Map.Entry<T, TreeNode> entry : allNodes.entrySet()) {
            if (entry.getValue().children != null) {
                for (TreeNode child : entry.getValue().children) {
                    if (child.eventTarget.equals(eventTarget)) {
                        if (parent == null) {
                            parent = entry.getKey();
                            if (!validate) {
                                break;
                            }
                        }
                        else {
                            Console
                            .traceln(Level.SEVERE,
                                     "Multiple nodes in the internal event target model match " +
                                     "the same event target. This should not be the case and the " +
                                     "event target model is probably invalid.");
                        }
                    }
                }
            }
        }

        return parent;
    }

    /* (non-Javadoc)
     * @see IEventTargetModel#getRootElements()
     */
    @Override
    public List<T> getRootElements() {
        List<T> roots = new ArrayList<T>();

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

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

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

    /**
     * <p>
     * dumps the event target 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) {
            dumpeventTarget(stream, node, "");
        }
    }

    /**
     * <p>
     * This method groups the provided event targets under a common parent event target. The current
     * parent event target of the event targets to group must be the same. If the event targets to
     * be grouped are the whole list of children of the same parent, nothing is changed. 
     * </p>
     * 
     * @param eventTargets       the list of event targets to be grouped
     * @param groupName          the name of the event target group to be created
     * @param eventTargetFactory the event target factory used for creating a group of the correct
     *                           type (ensures, that all elements in the model can have T in their
     *                           parent hierarchy)
     * 
     * @return the event target representing the group, or null, if the provided list of event
     *         targets is empty
     * 
     * @throws IllegalArgumentException
     *             if not all event targets to be merged share the same parent, if one of the
     *             parameters is null, or if one of the provided event targets does not belong to
     *             the model
     */
    public T groupEventTargets(List<T>             eventTargets,
                               String              groupName,
                               IEventTargetFactory eventTargetFactory)
        throws IllegalArgumentException
    {
        if ((eventTargets == null) || (groupName == null) || (eventTargetFactory == null)) {
            throw new IllegalArgumentException("parameters must not be null");
        }
        
        if (eventTargets.size() <= 0) {
            // do nothing
            return null;
        }
        
        TreeNode parent = findNode(eventTargets.get(0).getParent());
        if (parent == null) {
            throw new IllegalArgumentException("event targets to group must have a parent: " +
                                               "parent of " + eventTargets.get(0) + " is " +
                                               eventTargets.get(0).getParent() + " and not found " +
                                               "in the model");
        }
        
        List<TreeNode> nodesToGroup = new LinkedList<TreeNode>();
        
        for (IHierarchicalEventTarget element : eventTargets) {
            if (!(element instanceof AbstractDefaultHierarchicalEventTarget)) {
                throw new IllegalArgumentException
                    ("can only group nodes of type AbstractDefaultHierarchicalEventTarget");
            }
            
            TreeNode node = findNode(element);
            if (node == null) {
                throw new IllegalArgumentException
                    ("event target " + element + " is not part of the model");
            }
            
            if (!nodesToGroup.contains(node)) {
                nodesToGroup.add(node);
            }
            
            TreeNode parentNode = findNode(element.getParent());
            
            if (!parent.equals(parentNode)) {
                throw new IllegalArgumentException("event targets do not share the same parent: " +
                                                   parent + " (parent of " + eventTargets.get(0) +
                                                   ") <> " + parentNode + " (parent of " +
                                                   element + ")");
            }
        }
        
        TreeNode replacement = new TreeNode();
        replacement.eventTarget =
            eventTargetFactory.instantiateGroup(groupName, parent.eventTarget, this);
        
        if (!(replacement.eventTarget instanceof HierarchicalEventTargetGroup)) {
            throw new IllegalArgumentException("factory does not instantiate an object of type " +
                                               "HierarchicalEventTargetGroup which is required " +
                                               "for performing the merge");
        }
        
        for (TreeNode child : nodesToGroup) {
            ((HierarchicalEventTargetGroup) replacement.eventTarget).addToGroup(child.eventTarget);
            replacement.addChildNode(child);
            ((AbstractDefaultHierarchicalEventTarget) child.eventTarget).setParent
                (replacement.eventTarget);
            parent.children.remove(child);
        }

        parent.children.add(replacement);

        // finally, update the known nodes list
        // if you don't do this getChildren will return wrong things and very bad things happen!
        allNodes.put(replacement.eventTarget, replacement);
        
        return (T) replacement.eventTarget;
    }
    
    /**
     * <p>
     * By calling this method, the event target model is traversed and similar nodes are merged.
     * </p>
     * 
     */
    public void condenseModel() {
        mergeSubTree(root);
    }
    
    /**
     * <p>
     * Merges the tree nodes of two event targets. The event targets need to have the same parent.
     * They are merged recursively, i.e. also their children are merged. 
     * </p>
     * 
     * @param eventTarget1
     *            the first merge event target
     * @param eventTarget2
     *            the second merge event target
     *            
     * @return the result of the merge
     *            
     * @throws IllegalArgumentException
     *             thrown if the two event targets do not have the same parent
     */
    public T mergeEventTargets(T eventTarget1, T eventTarget2) throws IllegalArgumentException
    {
        return mergeEventTargets(eventTarget1, eventTarget2, true);
    }
    
    /**
     * <p>
     * Merges the tree nodes of two event targets. The event targets need to have the same parent.
     * If the <code>recursively</code> parameter is set to true, the children of the event targets
     * are merged, as well, as long as they are similar. If the parameter is false, the children
     * are not merged. In this case the resulting event target has all children of both merged
     * event targets.
     * </p>
     * 
     * @param eventTarget1
     *            the first merge event target
     * @param eventTarget2
     *            the second merge event target
     * @param recursively
     *            if true, the merge is done also for similar children, if false, not.
     *            
     * @return the result of the merge
     *            
     * @throws IllegalArgumentException
     *             thrown if the two event targets do not have the same parent
     */
    public T mergeEventTargets(T eventTarget1, T eventTarget2, boolean recursively)
        throws IllegalArgumentException
    {
        // check if both nodes have the same parent
        T parentElement = getParent(eventTarget1);
        boolean sameParent = (parentElement != null) ?
            parentElement.equals(eventTarget2.getParent()) : (eventTarget2.getParent() == null);
            
        if (!sameParent) {
            throw new IllegalArgumentException("can only merge nodes with the same parent");
        }

        // get the TreeNode of the parent of the event targets
        TreeNode parent = findNode(parentElement);
        
        if ((parent == null) && (parentElement == null)) {
            // merging root nodes. The parent is the root node of the event target tree
            parent = root;
        }

        // get the TreeNodes for both event targets
        TreeNode node1 = findNode(eventTarget1);
        TreeNode node2 = findNode(eventTarget2);

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

        TreeNode replacement = mergeTreeNodes(node1, node2, recursively);

        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);
            }
        }

        return replacement.eventTarget;
    }

    /**
     * <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 eventTargetPath
     *            the path of children to be created starting with the parent node
     * @param eventTargetFactory
     *            the event target factory to be used for instantiating event target objects
     * 
     * @return The event target object representing the event target denoted by the provided path
     * 
     * @throws EventTargetModelException
     *             thrown in cases such as the event target object could not be instantiated
     */
    private T integratePath(TreeNode               parentNode,
                            List<IEventTargetSpec> remainingPath,
                            IEventTargetFactory    eventTargetFactory)
        throws EventTargetModelException
    {
        IEventTargetSpec specToIntegrateElementFor = remainingPath.remove(0);

        TreeNode child = findEqualChild(parentNode, specToIntegrateElementFor);
        if (child == null) {
            T newElement = eventTargetFactory.instantiateEventTarget(specToIntegrateElementFor,
                                                                     parentNode.eventTarget);

            if (newElement instanceof AbstractDefaultHierarchicalEventTarget) {
                ((AbstractDefaultHierarchicalEventTarget) newElement).setEventTargetModel(this);
            }
            
            child = parentNode.addChild(newElement);
            allNodes.put(child.eventTarget, child);
        }

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

    /**
     * <p>
     * Searches the children of a tree node to see if the {@link IEventTargetSpec} equals the
     * specification of the {@link TreeNode#eventTarget} 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, IEventTargetSpec specToMatch) {
        if (parentNode.children != null) {
            for (TreeNode child : parentNode.children) {
                if (specToMatch.equals(child.eventTarget.getSpecification())) {
                    return child;
                }
            }
        }
        return null;
    }

    /**
     * <p>
     * Merges all similar nodes in the sub-tree of the event target 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++) {
                IEventTargetSpec elemSpec1 =
                    subTreeRoot.children.get(i).eventTarget.getSpecification();
                for (int j = i + 1; !performedMerge && j < subTreeRoot.children.size(); j++) {
                    IEventTargetSpec elemSpec2 =
                        subTreeRoot.children.get(j).eventTarget.getSpecification();
                    if (elemSpec1.getSimilarity(elemSpec2)) {
                        TreeNode replacement = mergeTreeNodes
                            (subTreeRoot.children.get(i), subTreeRoot.children.get(j), true);

                        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 event target objects with
     * each other for equality checks. Further it adds all children of both nodes to a new
     * replacing node. Afterwards, all similar nodes of the replacement node are merged as well as
     * long the recursive parameter is set to true.
     * </p>
     * 
     * @param treeNode1
     *            the first of the two nodes to be merged
     * @param treeNode2
     *            the second of the two nodes to be merged
     * @param recursively
     *            if true, the merging also merges child nodes
     *            
     * @return a tree node being the merge of the two provided nodes.
     */
    private TreeNode mergeTreeNodes(TreeNode treeNode1, TreeNode treeNode2, boolean recursively) {
        // and now a replacement node that is the merge of treeNode1 and treeNode2 is created
        TreeNode replacement = new TreeNode();
        replacement.eventTarget = treeNode1.eventTarget;
        if (treeNode1.children != null) {
            for (TreeNode child : treeNode1.children) {
                replacement.addChildNode(child);
            }
        }
        if (treeNode2.children != null) {
            for (TreeNode child : treeNode2.children) {
                replacement.addChildNode(child);
            }
        }

        if (recursively) {
            mergeSubTree(replacement);
        }

        replacement.eventTarget.updateSpecification(treeNode2.eventTarget.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.eventTarget);
        allNodes.remove(treeNode2.eventTarget);

        // the following two lines are needed to preserve the references to the existing event
        // targets. 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 event targets with each other so that an equals
        // check can return true.
        treeNode1.eventTarget.addEqualEventTarget(treeNode2.eventTarget);
        treeNode2.eventTarget.addEqualEventTarget(treeNode1.eventTarget);
        
        allNodes.put(replacement.eventTarget, replacement);
        
        return replacement;
    }

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

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

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

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

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

        TreeNode result = null;
        
        if (!validate) {
            result = allNodes.get(element);
        }
        else {
            for (Map.Entry<T, TreeNode> entry : allNodes.entrySet()) {
                if (entry.getKey().equals(element)) {
                    if (result == null) {
                        result = entry.getValue();
                    }
                    else {
                        Console.traceln(Level.SEVERE, "Multiple nodes in the internal event " +
                                        "target model match the same event target. This should " +
                                        "not be the case and the event target 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
     */
    private class Traverser implements IHierarchicalEventTargetModel.Traverser<T> {
        
        /**
         * <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 event target model to the stack
         * </p>
         */
        private Traverser() {
            nodeStack.push(new StackEntry(root, 0));
        }
        
        /* (non-Javadoc)
         * @see de.ugoe.cs.autoquest.eventcore.guimodel.Traverser#firstChild()
         */
        @Override
        public T firstChild() {
            return pushChild(0);
        }
        
        /* (non-Javadoc)
         * @see de.ugoe.cs.autoquest.eventcore.guimodel.Traverser#hasFirstChild()
         */
        @Override
        public boolean hasFirstChild() {
            return
                (nodeStack.peek().treeNode.children != null) &&
                (nodeStack.peek().treeNode.children.size() > 0);
        }
        
        /* (non-Javadoc)
         * @see de.ugoe.cs.autoquest.eventcore.guimodel.Traverser#nextSibling()
         */
        @Override
        public T nextSibling() {
            int lastIndex = nodeStack.pop().index;
            
            T retval = pushChild(lastIndex + 1);
            if (retval == null) {
                pushChild(lastIndex);
            }
            
            return retval;
        }
        
        /* (non-Javadoc)
         * @see de.ugoe.cs.autoquest.eventcore.guimodel.Traverser#hasNextSibling()
         */
        @Override
        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;
        }
        
        /* (non-Javadoc)
         * @see de.ugoe.cs.autoquest.eventcore.guimodel.Traverser#parent()
         */
        @Override
        public T parent() {
            T retval = null;
            
            if (nodeStack.size() > 1) {
                nodeStack.pop();
                retval = nodeStack.peek().treeNode.eventTarget;
            }
            
            return retval;
        }
        
        /**
         * <p>
         * internal method used for changing the state of the traverser. I.e. to switch to a
         * specific child event target of the current one.
         * </p>
         */
        private T pushChild(int index) {
            T 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.eventTarget;
            }
            
            return retVal;
        }
        
        /**
         * <p>
         * navigates the traverser to the given node in the event target model
         * </p>
         */
        private boolean navigateTo(TreeNode node) {
            if (hasFirstChild()) {
                T childElement = firstChild();
            
                while (childElement != null) {
                    if (childElement.equals(node.eventTarget)) {
                        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 event target 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 event targets.
     * </p>
     * 
     * @version 1.0
     * @author Patrick Harms, Steffen Herbold
     */
    private class TreeNode implements Serializable {

        /**  */
        private static final long serialVersionUID = 1L;

        /**
         * <p>
         * event target associated with the TreeNode.
         * </p>
         */
        private T eventTarget;

        /**
         * <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 eventTarget
         *            event target that will be associated with the new child
         *            
         * @return the added child
         */
        private TreeNode addChild(T eventTarget) {
            if (children == null) {
                children = new ArrayList<TreeNode>();
            }

            TreeNode child = new TreeNode();
            child.eventTarget = eventTarget;
            children.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 eventTarget.toString();
        }

    }
}