source: trunk/autoquest-plugin-html/src/main/java/de/ugoe/cs/autoquest/plugin/html/commands/CMDcondenseHTMLGUIModel.java @ 1491

//   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.plugin.html.commands;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Comparator;
import java.util.HashSet;
import java.util.IdentityHashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.logging.Level;

import de.ugoe.cs.autoquest.CommandHelpers;
import de.ugoe.cs.autoquest.SequenceInstanceOf;
import de.ugoe.cs.autoquest.eventcore.Event;
import de.ugoe.cs.autoquest.eventcore.guimodel.GUIModel;
import de.ugoe.cs.autoquest.eventcore.guimodel.IGUIElement;
import de.ugoe.cs.autoquest.eventcore.guimodel.IGUIElementSpec;
import de.ugoe.cs.autoquest.plugin.html.guimodel.HTMLDocument;
import de.ugoe.cs.autoquest.plugin.html.guimodel.HTMLServer;
import de.ugoe.cs.util.console.Command;
import de.ugoe.cs.util.console.Console;
import de.ugoe.cs.util.console.GlobalDataContainer;

/**
 * <p>
 * This command condenses an HTML GUI model. For HTML GUI models, this is a special task, as, e.g.,
 * menu structures resisting on several pages of a website are identified separately. However, for
 * subsequent analysis, they need to be treated as identical. Therefore, this command identifies
 * pages (i.e. documents) with equal structures and merges them. For differences in the pages, it
 * adds groups of GUI elements indicating, which GUI element belongs to which pages and not to
 * others.
 * </p>
 * <p>
 * An example for clarification. Consider the following two pages:
 * <pre>
 * server
 *   |-- document1
 *   |     \-- html
 *   |           \-- body
 *   |                 |-- div (id = menu)
 *   |                 |     \-- ...
 *   |                 |-- div (id = textcontent)
 *   |                 |     \-- ...
 *   |                 \-- div (id = footer)
 *   |                       \-- ...
 *   \-- document2
 *         \-- html
 *               \-- body
 *                     |-- div (id = menu)
 *                     |     \-- ...
 *                     |-- div (id = imagecontent)
 *                     |     \-- ...
 *                     \-- div (id = footer)
 *                           \-- ...
 * </pre>
 * They only differ in the central div which has the id textcontent for the first document and 
 * imagecontent for the second. The above GUI model is the result of the monitoring and parsing of
 * the log files. This command condenses the GUI model to the following structure:
 * <pre>
 * server
 *   \-- document1
 *         \-- html
 *               \-- body
 *                     |-- div (id = menu)
 *                     |     \-- ...
 *                     |-- group (document1)
 *                     |     \-- div (id = textcontent)
 *                     |           \-- ...
 *                     |-- group (document2)
 *                     |     \-- div (id = imagecontent)
 *                     |           \-- ...
 *                     \-- div (id = footer)
 *                           \-- ...
 * </pre>
 * This now allows the menu and the footer to be treated as identical over several pages.
 * </p>
 * <p>
 * If several but not all pages share similarities, the created groups refer to several documents
 * at once.
 * </p>
 * 
 * @author Patrick Harms
 * @version 1.0
 */
public class CMDcondenseHTMLGUIModel implements Command {

    /*
     * (non-Javadoc)
     * 
     * @see de.ugoe.cs.util.console.Command#run(java.util.List)
     */
    @Override
    public void run(List<Object> parameters) {
        String sequencesName;

        try {
            sequencesName = (String) parameters.get(0);
        }
        catch (Exception e) {
            throw new IllegalArgumentException("illegal parameters provided: " + e);
        }

        Object dataObject = GlobalDataContainer.getInstance().getData(sequencesName + "_targets");
        if (dataObject == null) {
            CommandHelpers.objectNotFoundMessage(sequencesName + "_targets");
            return;
        }
        if (!(dataObject instanceof GUIModel)) {
            CommandHelpers.objectNotType(sequencesName, "GUIModel");
            return;
        }

        GUIModel model = (GUIModel) dataObject;
        
        // >>>>>>>>>>>>>>>>>>>>>>>>>>>> Just to test the distance measure
        
        System.out.println("checking distance measure correctness");
        Collection<List<Event>> sequences = null;
        dataObject = GlobalDataContainer.getInstance().getData(sequencesName);
        if (dataObject == null) {
            CommandHelpers.objectNotFoundMessage(sequencesName);
            return;
        }
        if (!SequenceInstanceOf.isCollectionOfSequences(dataObject)) {
            CommandHelpers.objectNotType(sequencesName, "Collection<List<Event<?>>>");
            return;
        }

        sequences = (Collection<List<Event>>) dataObject;
        
        Map<IGUIElement, IGUIElement> guiElements = new IdentityHashMap<IGUIElement, IGUIElement>();
        
        for (List<Event> sequence : sequences) {
            for (Event event : sequence) {
                guiElements.put((IGUIElement) event.getTarget(), (IGUIElement) event.getTarget());
            }
        }
        
        System.out.println("got " + guiElements.size() + " utilized GUI elements");
        
        IGUIElement[] guiElementArray =
            guiElements.keySet().toArray(new IGUIElement[guiElements.size()]);
        
        Arrays.sort(guiElementArray, new Comparator<IGUIElement>() {
            @Override
            public int compare(IGUIElement o1, IGUIElement o2) {
                return o1.getStringIdentifier().compareTo(o2.getStringIdentifier());
            }
            
        });
        
        int checkSize = Math.min(guiElements.size() * guiElements.size(), 100000000);
        double[] expectedDistances = new double[checkSize];
        int index = 0;
        
        OUTER:
        for (int i = 0; i < guiElementArray.length; i++) {
            for (int j = 0; j < guiElementArray.length; j++) {
                if (i == j) {
                    continue;
                }
                
                if (index == 1703) {
                    System.out.println("blub");
                }
                
                expectedDistances[index++] = guiElementArray[i].getDistanceTo(guiElementArray[j]);
                
                if (index == checkSize) {
                    break OUTER;
                }
            }
        }

        System.out.println("calculated " + expectedDistances.length + " distances");

        // <<<<<<<<<<<<<<<<<<<<<<<<<<<< Just to test the distance measure

        for (IGUIElement root : model.getRootElements()) {
            if (root instanceof HTMLServer) {
                try {
                    mergeServer((HTMLServer) root, model);
                }
                catch (Exception e) {
                    Console.printerrln("problems while condensing model of server " + root);
                    Console.logException(e);
                    break;
                }
            }
        }

        // >>>>>>>>>>>>>>>>>>>>>>>>>>>> Just to test the distance measure
        index = 0;
        
        System.out.println("checking, if distances are still the same");
        OUTER:
        for (int i = 0; i < guiElementArray.length; i++) {
            for (int j = 0; j < guiElementArray.length; j++) {
                if (i == j) {
                    continue;
                }

                if (index == 1703) {
                    System.out.println("blub");
                }
                
                double newDistance = guiElementArray[i].getDistanceTo(guiElementArray[j]);
                if ((expectedDistances[index] != newDistance) &&
                    (expectedDistances[index] != 0.5) && (newDistance != 0.2))
                {
                    System.out.println((index ) + ": distance between " + guiElementArray[i] +
                                       " and " + guiElementArray[j] + " changed due to condense. " +
                                       "Was " + expectedDistances[index] + " and is now " +
                                       guiElementArray[i].getDistanceTo(guiElementArray[j]) + ".");
                }
                
                index++;
                
                if (index == checkSize) {
                    break OUTER;
                }
            }
        }
        // <<<<<<<<<<<<<<<<<<<<<<<<<<<< Just to test the distance measure
        
    }

    /**
     * <p>
     * Condenses all documents resisting on the same server. For this, the method first identifies
     * a hierarchy of clusters of similar GUI elements. This is then used to merge similar GUI
     * elements and to create subgroups for indicating differences between the documents.
     * </p>
     *
     * @param server the server of which all documents shall be condensed
     * @param model  the GUI model in which the server is referenced
     */
    private void mergeServer(HTMLServer server, GUIModel model) {
        Console.traceln(Level.INFO, "condensing documents of " + server);
        Console.traceln(Level.FINE, "creating cluster hierarchy of GUI elements for " + server);
        GUIElementsCluster rootCluster = getSimilarElementClusterHierarchy(server, model);

        //rootCluster.dump(System.out, "");
            
        Console.traceln(Level.FINE, "merging GUI elements in same clusters and creating groups");
        mergeGUIElementsAccordingToClusters(rootCluster, model, "");
            
        //model.dump(System.out, "UTF-8");
        Console.traceln(Level.INFO, "condensed documents of " + server);
    }

    /**
     * <p>
     * determines clusters of similar GUI elements being children of the provided server. For this,
     * the method creates a cluster containing all children of the provided server as similar
     * GUI elements. Usually, these are all documents on the server. It then initiates creating
     * the cluster hierarchy by calling the recursive method
     * {@link #addChildClusters(GUIElementsCluster, GUIModel, String)}.
     * </p>
     *
     * @param server the server for which the clusters of similar children shall be determined
     * @param model  the GUI model required for identifying children and sub children
     * 
     * @return a GUI element cluster representing the server.
     */
    private GUIElementsCluster getSimilarElementClusterHierarchy(HTMLServer server, GUIModel model)
    {
        GUIElementsCluster cluster = new GUIElementsCluster();
        
        List<IGUIElement> children = model.getChildren(server);

        
        SimilarGUIElements similarGuiElements = new SimilarGUIElements();
        
        for (IGUIElement child : children) {
            // when starting with the root, the cluster parent is the child itself, i.e. the
            // document. We expect all documents to be similar.

            similarGuiElements.add(new SimilarGUIElement(child, child));
        }
        
        cluster.addSimilarGUIElements(similarGuiElements);
        
        // create the cluster structure
        addChildClusters(cluster, model, "");
        
        return cluster;
    }
    

    /**
     * <p>
     * Determines child clusters of a cluster of given GUI elements. This method calls itself
     * recursively for each directly identified child cluster. Furthermore, it moves child clusters
     * to children of other child clusters if they are a subset of the clustered GUI elements.
     * </p>
     *
     * @param cluster the cluster for which child clusters shall be identified
     * @param model   the model required to be able to determine child GUI elements
     */
    private void addChildClusters(GUIElementsCluster cluster, GUIModel model, String indent) {
        for (SimilarGUIElements similarGuiElements : cluster.similarChildrenGUIElements) {
            createSubClustersForChildren(similarGuiElements, cluster, model, indent + "  ");
        }
        
        for (GUIElementsCluster childCluster : cluster.childClusters) {
            addChildClusters(childCluster, model, indent + "  ");
        }
        
        createClusterHierachies(cluster);
    }
    
    /**
     * <p>
     * for a set of similar GUI elements, it identifies similar children and clusters them. For
     * each identified cluster, it adds a new child cluster to the provided parent cluster. GUI
     * elements having no further children are ignored.
     * </p>
     *
     * @param similarGuiElements the similar GUI elements of which the children shall be clustered
     * @param parentCluster      the parent cluster to which newly identified cluster are added
     *                           as children
     * @param model              the model required to be able to determine child GUI elements
     */
    private void createSubClustersForChildren(SimilarGUIElements similarGuiElements,
                                              GUIElementsCluster parentCluster,
                                              GUIModel           model,
                                              String             indent)
    {
        for (SimilarGUIElement similarGuiElement : similarGuiElements) {
            List<IGUIElement> children = model.getChildren(similarGuiElement.similarGUIElement);
        
            if (children.size() > 0) {
                for (IGUIElement child : children) {
                    addToClusterOfSimilarElements
                        (child, similarGuiElement.mainClusterParent, parentCluster,
                         similarGuiElements, model);
                }
            }
//            else {
//                // search for a default cluster to add all elements to, which have no children
//                GUIElementsCluster defaultCluster = null;
//                
//                for (GUIElementsCluster candidate : parentCluster.childClusters) {
//                    if (candidate.similarChildrenGUIElements.size() == 0) {
//                        defaultCluster = candidate;
//                        break;
//                    }
//                }
//                
//                if (defaultCluster == null) {
//                    defaultCluster = new GUIElementsCluster();
//                    parentCluster.addChildCluster(defaultCluster);
//                }
//                
//                defaultCluster.clusteredGUIElements.add(similarGuiElement);
//            }
        }
    }

    /**
     * <p>
     * for a given GUI element, searches the list of child clusters of the parent cluster and adds
     * the GUI element to the cluster, if the cluster already contains a similar GUI element. If
     * not, a new cluster is created and added to the list of known clusters.
     * </p>
     *
     * @param child              the child for which the cluster is to be determined
     * @param clusterParent      the root GUI element of the parent cluster
     * @param parentCluster      the parent cluster whose child clusters shall be filled
     * @param similarGuiElements the similar GUI elements currently matched to each other
     * @param model              the GUI model required to determine children of GUI elements
     */
    private void addToClusterOfSimilarElements(IGUIElement        child,
                                               IGUIElement        clusterParent,
                                               GUIElementsCluster parentCluster,
                                               SimilarGUIElements similarGuiElements,
                                               GUIModel           model)
    {
        SimilarGUIElements matchingParents = new SimilarGUIElements();
        
        // determine matching parents
        for (SimilarGUIElement similarGuiElement : similarGuiElements) {
            for (IGUIElement candidate : model.getChildren(similarGuiElement.similarGUIElement)) {
                IGUIElementSpec similarityCandidate = candidate.getSpecification();
                if (similarityCandidate.getSimilarity(child.getSpecification())) {
                    matchingParents.add(similarGuiElement);
                    break;
                }
            }
        }
        
        // check if an appropriate cluster exists
        GUIElementsCluster cluster = null;
        
        for (GUIElementsCluster clusterCandidate : parentCluster.childClusters) {
            if (clusterCandidate.isClusterOf(matchingParents)) {
                cluster = clusterCandidate;
                break;
            }
        }
        
        if (cluster == null) {
            cluster = new GUIElementsCluster();
            parentCluster.addChildCluster(cluster);
            cluster.setClusteredGUIElements(matchingParents);
        }
        
        cluster.addSimilarChild(child, clusterParent);
    }

    /**
     * <p>
     * clusters of similar children identified for a GUI element may be logical subclusters of
     * each other. This is, e.g., the case if one cluster contains all elements being part of
     * document1 and document2 and a further cluster contains all elements of document 1 only. In
     * this case, the cluster of document1 is added as a child to the other cluster. In this case
     * it is furthermore required, that a common cluster as child of the document1/document2 cluster
     * is created carrying the common GUI elements for both clusters.
     * </p>
     *
     * @param parentCluster the parent cluster for whose children the child hierarchies shall be
     *                      created (in-out parameter, as it is changed)
     */
    private void createClusterHierachies(GUIElementsCluster parentCluster) {
        GUIElementsCluster[] clustersCopy = parentCluster.childClusters.toArray
            (new GUIElementsCluster[parentCluster.childClusters.size()]);
        
        // sort the array starting with the shortest cluster and ending with the longest
        Arrays.sort(clustersCopy, new Comparator<GUIElementsCluster>() {
            @Override
            public int compare(GUIElementsCluster c1, GUIElementsCluster c2) {
                return c1.clusteredGUIElements.size() - c2.clusteredGUIElements.size();
            }
        });
        
        Set<GUIElementsCluster> subClustersToHandle = new HashSet<GUIElementsCluster>();
        
        // now add smaller clusters to larger ones, if they are parents
        for (int i = 0; i < (clustersCopy.length - 1); i++) {
            GUIElementsCluster potentialChild = clustersCopy[i];
            
            // search for the next cluster and add the child
            for (int j = i + 1; j < clustersCopy.length; j++) {
                if (clustersCopy[j].isSubCluster(potentialChild)) {
                    
                    clustersCopy[j].addChildCluster(potentialChild);
                    subClustersToHandle.add(clustersCopy[j]);
                    
                    for (int k = 0; k < parentCluster.childClusters.size(); k++) {
                        if (parentCluster.childClusters.get(k) == potentialChild) {
                            parentCluster.childClusters.remove(k);
                            break;
                        }
                    }
                    
                    break;
                }
            }
        }
        
        if (subClustersToHandle.size() > 0) {
            // finally, for all subclusters that were changed, ensure the creation of their internal
            // hierarchy as well
            for (GUIElementsCluster subClusterToHandle : subClustersToHandle) {
                // we need a dedicated common cluster --> add it
                createClusterHierachies(subClusterToHandle);
                
                /*GUIElementsCluster commonCluster = new GUIElementsCluster();
                //commonCluster.setClusteredGUIElements(subClusterToHandle.clusteredGUIElements);
                commonCluster.similarChildrenGUIElements.addAll
                    (subClusterToHandle.similarChildrenGUIElements);
                
                subClusterToHandle.similarChildrenGUIElements.clear();
                subClusterToHandle.childClusters.add(0, commonCluster);*/
            }
        }
    }

    /**
     * <p>
     * called for each cluster to merge similar GUI elements depending on the clusters and to
     * create GUI element groups if required. Calls itself recursively to be also applied on
     * child clusters.
     * </p>
     *
     * @param cluster the cluster of which the similar children shall be merged
     * @param model   the model to be adapted through the merge
     */
    private void mergeGUIElementsAccordingToClusters(GUIElementsCluster cluster,
                                                     GUIModel           model,
                                                     String             indent)
    {
        //System.out.println(indent + "handling " + cluster);
        
        for (SimilarGUIElements similarGUIElements : cluster.similarChildrenGUIElements) {
            mergeGUIElements(similarGUIElements, model, indent + "  ");
        }
        
        if (cluster.childClusters.size() > 0) {
            //System.out.println(indent + "  handling child clusters");
            
            for (GUIElementsCluster childCluster : cluster.childClusters) {
                if (cluster.isDefault() || cluster.clusterParentsMatch(childCluster)) {
                    // for default cluster or children not creating subgroups, just traverse the
                    // cluster hierarchy
                    mergeGUIElementsAccordingToClusters(childCluster, model, indent + "    ");
                }
                else {
                    createClusterGroup(childCluster, model, indent + "    ");
                }
            }
        }
    }

    /**
     * <p>
     * merges similar GUI elements using the provided model
     * </p>
     *
     * @param similarGUIElements the GUI elements to merge
     * @param model              the model to be used for merging the GUI elements
     */
    private void mergeGUIElements(SimilarGUIElements similarGUIElements,
                                  GUIModel           model,
                                  String             indent)
    {
        if (similarGUIElements.size() > 0) {
            IGUIElement mergeResult = similarGUIElements.get(0).similarGUIElement;

            while (similarGUIElements.size() > 1) {
                //System.out.println(indent + "merging " + mergeResult + " and " +
                //                   similarGUIElements.get(1).similarGUIElement);
                mergeResult = model.mergeGUIElements
                        (mergeResult, similarGUIElements.remove(1).similarGUIElement, false);
            }
        }
    }

    /**
     * <p>
     * creates a group of GUI elements to represent a cluster. Uses the provided model for group
     * creation.
     * </p>
     *
     * @param cluster the cluster for which the group shall be created
     * @param model   the model to be used for creating the groups
    */
    private void createClusterGroup(GUIElementsCluster cluster, GUIModel model, String indent) {
        //System.out.println(indent + "creating group for " + cluster);

        List<IGUIElement> guiElementsToGroup = new LinkedList<IGUIElement>();
        
        for (SimilarGUIElements similarGUIElements : cluster.similarChildrenGUIElements) {
            mergeGUIElements(similarGUIElements, model, indent);
            guiElementsToGroup.addAll(similarGUIElements.toGUIElementList());
        }
        
        //System.out.println(indent + "  iterating child clusters of " + cluster);
        for (GUIElementsCluster childCluster : cluster.childClusters) {
            if (cluster.isDefault() || cluster.clusterParentsMatch(childCluster)) {
                // for default cluster or children not creating subgroups, just traverse the
                // cluster hierarchy
                mergeGUIElementsAccordingToClusters(childCluster, model, indent + "  ");
            }
            else {
                createClusterGroup(childCluster, model, indent + "  ");
            }
            
            if (childCluster.getGroup() != null) {
                if (cluster.isSubCluster(childCluster)) {
                    guiElementsToGroup.add(childCluster.getGroup());
                }
                else {
                    guiElementsToGroup.add(childCluster.getGroup().getParent());
                }
            }
        }
        
        //System.out.println(indent + "grouping: " + guiElementsToGroup);
        IGUIElement group = model.groupGUIElements(guiElementsToGroup, getGroupName(cluster));
        //System.out.println(indent + "  created group for " + cluster + ": " + group);
        
        cluster.setGroup(group);
    }

    /**
     * <p>
     * determines a name for a group to be created for the provided cluster
     * </p>
     *
     * @param cluster the cluster for which a group name shall be determined
     * 
     * @return an appropriate name
     */
    private String getGroupName(GUIElementsCluster cluster) {
        StringBuffer name = new StringBuffer();
        
        name.append("group_");
        
        if (cluster.clusteredGUIElements.size() > 0) {
            List<List<String>> pathParts = new ArrayList<List<String>>();
            
            for (SimilarGUIElement guiElement : cluster.clusteredGUIElements) {
                if (guiElement.mainClusterParent instanceof HTMLDocument) {
                    String path = ((HTMLDocument) guiElement.mainClusterParent).getPath();
                    
                    if (path.startsWith("/")) {
                        path = path.substring(1);
                    }
                    
                    if (path.endsWith("/")) {
                        path = path.substring(0, path.length() - 1);
                    }
                    
                    String[] pathElements = path.split("/");
                    
                    for (int i = 0; i < pathElements.length; i++) {
                        if (pathParts.size() <= i) {
                            pathParts.add(new LinkedList<String>());
                        }
                        if (!pathParts.get(i).contains(pathElements[i])) {
                            pathParts.get(i).add(pathElements[i]);
                        }
                    }
                }
                else {
                    if (pathParts.size() < 1) {
                        pathParts.add(new LinkedList<String>());
                    }
                    if (!pathParts.get(0).contains(guiElement.mainClusterParent.getStringIdentifier()))
                    {
                        pathParts.get(0).add(guiElement.mainClusterParent.getStringIdentifier());
                    }
                }
            }
            
            for (List<String> pathPart : pathParts) {
                name.append('/');
                if (pathPart.size() > 1) {
                    name.append('[');
                }
                
                int index = 0;
                for (String elem : pathPart) {
                    if (index++ > 0) {
                        name.append('|');
                    }
                    name.append(elem);
                }
                
                if (pathPart.size() > 1) {
                    name.append(']');
                }
            }
        }
        else {
            name.append("common");
        }
        
        return name.toString();
    }

    /*
     * (non-Javadoc)
     * 
     * @see de.ugoe.cs.util.console.Command#help()
     */
    @Override
    public String help() {
        return "condenseHTMLGUIModel <sequence>";
    }

    /**
     * <p>
     * represents a cluster of similar GUI elements. It consists of a list of similar GUI elements
     * represented by the cluster somewhere in the GUI element hierarchy. It contains, furthermore,
     * a list of GUI elements that belong to the root cluster of the cluster hierarchy, which are
     * usually the similar documents. It also refers to child clusters, and if created, a GUI
     * element group representing the cluster.
     * </p>
     */
    private static class GUIElementsCluster {
        
        /**
         * <p>
         * the similar children on the same level in the GUI model represented through the cluster
         * </p>
         */
        private List<SimilarGUIElements> similarChildrenGUIElements =
            new LinkedList<SimilarGUIElements>();
        
        /**
         * <p>
         * the similar root GUI elements on the first level of the created hierarchy (usually
         * the documents on a website) to which the similar GUI elements belong
         * </p>
         */
        private SimilarGUIElements clusteredGUIElements = new SimilarGUIElements();
        
        /**
         * <p>
         * reference to the child clusters.
         * </p>
         */
        private List<GUIElementsCluster> childClusters = new LinkedList<GUIElementsCluster>();
        
        /**
         * <p>
         * reference to the GUI element group if one is created for the cluster
         * </p>
         */
        private IGUIElement group = null;

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

        /**
         * <p>
         * checks, if the main cluster parents, i.e., the documents of this and the provided cluster
         * match
         * </p>
         *
         * @param other the other cluster of which the main cluster parents shall be compared to
         *              this
         *              
         * @return true if they match, false else
         */
        private boolean clusterParentsMatch(GUIElementsCluster other) {
            // cluster parent may already be merged and therefore equals --> use system identity
            // hash code for uniqueness
            Set<Integer> mainClusterParents1 = new HashSet<Integer>();
            for (SimilarGUIElement clusteredElem1 : clusteredGUIElements) {
                mainClusterParents1.add(System.identityHashCode(clusteredElem1.mainClusterParent));
            }
            
            Set<Integer> mainClusterParents2 = new HashSet<Integer>();
            for (SimilarGUIElement clusteredElem2 : other.clusteredGUIElements) {
                mainClusterParents2.add(System.identityHashCode(clusteredElem2.mainClusterParent));
            }
            
            return mainClusterParents1.equals(mainClusterParents2);
        }

        /**
         * <p>
         * returns true, if this cluster is a default cluster
         * </p>
         *
         * @return
         */
        public boolean isDefault() {
            return clusteredGUIElements.size() <= 0;
        }

        /**
         * <p>
         * sets the GUI element group created for this cluster
         * </p>
         *
         * @param group the GUI element group created for this cluster
         */
        private void setGroup(IGUIElement group) {
            this.group = group;
        }

        /**
         * <p>
         * returns the GUI element group created for this cluster
         * </p>
         *
         * @return the GUI element group created for this cluster
         */
        private IGUIElement getGroup() {
            return group;
        }

        /**
         * <p>
         * checks if the given cluster should be a child of this cluster. It should be a child
         * if its list of clustered documents is a subset of the list of clustered documents of
         * this cluster.
         * </p>
         *
         * @param potentialChild the cluster to check
         * 
         * @return true, if the cluster should be a child, false else
         */
        private boolean isSubCluster(GUIElementsCluster potentialChild) {
            return 
                (potentialChild.clusteredGUIElements.size() < clusteredGUIElements.size()) &&
                (clusteredGUIElements.containsAll(potentialChild.clusteredGUIElements));
        }

        /**
         * <p>
         * sets the list of clustered GUI elements, i.e., documents of which this cluster contains
         * similar GUI elements
         * </p>
         *
         * @param clusteredGUIElements the new list of clustered GUI elements
         */
        private void setClusteredGUIElements(SimilarGUIElements clusteredGUIElements) {
            this.clusteredGUIElements = clusteredGUIElements;
        }

        /**
         * <p>
         * adds a child cluster to this cluster
         * </p>
         *
         * @param cluster the new child cluster
         */
        private void addChildCluster(GUIElementsCluster cluster) {
            childClusters.add(cluster);
        }

        /**
         * <p>
         * adds similar GUI elements to the list of similar GUI elements
         * </p>
         */
        private void addSimilarGUIElements(SimilarGUIElements similarGuiElements) {
            similarChildrenGUIElements.add(similarGuiElements);
        }

        /**
         * <p>
         * determines a list of similar GUI elements to which the provided GUI element belongs.
         * If it finds one, it adds the GUI element to that list. If not, it creates a new one.
         * </p>
         *
         * @param child         the child to to be added to the list of similar GUI elements
         * @param clusterParent the main parent of the cluster to which the GUI element belongs
         *                      (usually the document)
         */
        private void addSimilarChild(IGUIElement child, IGUIElement clusterParent) {
            SimilarGUIElements similarGUIElements = null;
            
            for (SimilarGUIElements candidate : similarChildrenGUIElements) {
                if (candidate.elementsMatch(child)) {
                    similarGUIElements = candidate;
                }
            }
            
            if (similarGUIElements == null) {
                similarGUIElements = new SimilarGUIElements();
                similarChildrenGUIElements.add(similarGUIElements);
            }
            
            similarGUIElements.add(new SimilarGUIElement(child, clusterParent));
        }

        /**
         * <p>
         * checks, if this cluster is a cluster representing the provided main cluster parents
         * </p>
         */
        private boolean isClusterOf(SimilarGUIElements checkedClusterParents) {
            return (clusteredGUIElements.size() == checkedClusterParents.size()) &&
                   (clusteredGUIElements.containsAll(checkedClusterParents));
        }

        /**
         * <p>
         * returns a name for this cluster
         * </p>
         */
        private String getName() {
            StringBuffer ret = new StringBuffer("cluster(");
            
            if (clusteredGUIElements.size() > 0) {
                ret.append(clusteredGUIElements.get(0).similarGUIElement);
                ret.append(" [");
                
                int length = ret.length();
                for (SimilarGUIElement similarGUIElement : clusteredGUIElements) {
                    if (ret.length() > length) {
                        ret.append(", ");
                    }

                    ret.append(similarGUIElement.mainClusterParent);
                }
                
                ret.append(']');
            }
            else {
                ret.append("default");
            }
            
            ret.append(")");
            
            return ret.toString();
        }
        
        /**
         * <p>
         * dumps infos of this cluster to the provided stream
         * </p>
         */
//        private void dump(PrintStream out, String indent) {
//            out.print(indent);
//            out.print(getName());
//            out.println(" { ");
//            
//            if (clusteredGUIElements.size() > 0) {
//                out.print(indent);
//                out.println("  clustered GUIElements {");
//
//                for (SimilarGUIElement clusteredGUIElement : clusteredGUIElements) {
//                    clusteredGUIElement.dump(out, indent + "    ");
//                }
//
//                out.print(indent);
//                out.println("  }");
//            }
//
//            if (similarChildrenGUIElements.size() > 0) {
//                out.print(indent);
//                out.println("  similar children {");
//
//                for (SimilarGUIElements similarGuiElements : similarChildrenGUIElements) {
//                    similarGuiElements.dump(out, indent + "    ");
//                }
//
//                out.print(indent);
//                out.println("  }");
//            }
//
//            if (childClusters.size() > 0) {
//                out.print(indent);
//                out.println("  child clusters {");
//
//                for (GUIElementsCluster childCluster : childClusters) {
//                    childCluster.dump(out, indent + "    ");
//                }
//
//                out.print(indent);
//                out.println("  }");
//            }
//            
//            out.print(indent);
//            out.println("}");
//        }

    }

    /**
     * <p>
     * represents a list of similar GUI elements
     * </p>
     */
    private static class SimilarGUIElements extends LinkedList<SimilarGUIElement> {

        /** 
         * <p>
         * default serial version UID
         * </p>
         */
        private static final long serialVersionUID = 1L;

        /**
         * <p>
         * checks if the provided GUI element is similar to at least on of the GUI elements
         * represented by this list.
         * </p>
         */
        private boolean elementsMatch(IGUIElement otherGUIElement) {
            // it is sufficient, if one of the elements (if any) matches, as the similarity 
            // check must be transitive
            if (size() > 0) {
                return get(0).similarGUIElement.getSpecification().getSimilarity
                           (otherGUIElement.getSpecification());
            }
            else {
                return true;
            }
        }
    
        /**
         * <p>
         * transforms this list to a list of GUI elements
         * </p>
         */
        private List<IGUIElement> toGUIElementList() {
            List<IGUIElement> guiElementList = new LinkedList<IGUIElement>();
            
            for (SimilarGUIElement similarGUIElement : this) {
                guiElementList.add(similarGUIElement.similarGUIElement);
            }

            return guiElementList;
        }

        /**
         * <p>
         * dumps infos of this list to the provided stream
         * </p>
         */
//        private void dump(PrintStream out, String indent) {
//            out.print(indent);
//            out.print("{ ");
//            
//            for (int i = 0; i < super.size(); i++) {
//                if (i > 0) {
//                    out.print(", ");
//                }
//                out.print(super.get(i));
//            }
//            
//            out.println(" }");
//        }
    }
    
    /**
     * <p>
     * represents a single similar GUI element and the main cluster parent, i.e., the document to
     * which it belongs.
     * </p>
     */
    private static class SimilarGUIElement {
        
        /**
         * <p>
         * the represented GUI element
         * </p>
         */
        private IGUIElement similarGUIElement;
        
        /**
         * <p>
         * the main cluster parent, i.e., usually the document of the represented GUI element
         * </p>
         */
        private IGUIElement mainClusterParent;
        
        /**
         * <p>
         * simple constructor to initialize the objects
         * </p>
         */
        private SimilarGUIElement(IGUIElement similarGUIElement, IGUIElement clusterParent) {
            this.similarGUIElement = similarGUIElement;
            this.mainClusterParent = clusterParent;
        }

        /**
         * <p>
         * dumps infos about this object to the provided stream
         * </p>
         */
//        private void dump(PrintStream out, String indent) {
//            out.print(indent);
//            out.println(this);
//        }

        /* (non-Javadoc)
         * @see java.lang.Object#equals(java.lang.Object)
         */
        @Override
        public boolean equals(Object obj) {
            if (obj == this) {
                return true;
            }
            else if (obj instanceof SimilarGUIElement) {
                return (similarGUIElement.equals(((SimilarGUIElement) obj).similarGUIElement));
            }
            else {
                return false;
            }
        }

        /* (non-Javadoc)
         * @see java.lang.Object#hashCode()
         */
        @Override
        public int hashCode() {
            return similarGUIElement.hashCode();
        }

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

    }
        
}