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

package de.ugoe.cs.autoquest.tasktrees.temporalrelation;

import java.util.ArrayList;
import java.util.List;

import de.ugoe.cs.autoquest.tasktrees.nodeequality.NodeEquality;
import de.ugoe.cs.autoquest.tasktrees.nodeequality.NodeEqualityRuleManager;
import de.ugoe.cs.autoquest.tasktrees.treeifc.IEventTask;
import de.ugoe.cs.autoquest.tasktrees.treeifc.IIteration;
import de.ugoe.cs.autoquest.tasktrees.treeifc.ISelection;
import de.ugoe.cs.autoquest.tasktrees.treeifc.ISequence;
import de.ugoe.cs.autoquest.tasktrees.treeifc.ITaskTreeBuilder;
import de.ugoe.cs.autoquest.tasktrees.treeifc.ITaskTreeNode;
import de.ugoe.cs.autoquest.tasktrees.treeifc.ITaskTreeNodeFactory;

/**
 * <p>
 * iterations in a list of nodes are equal subsequences following each other directly. The
 * subsequences can be of any length depending on the type of equality they need to have. If the
 * subsequences have to be lexically equal, then they have to have the same length if they only
 * contain event tasks. As an example entering text can be done through appropriate keystrokes or
 * through pasting the text. As a result, two syntactically different sequences are semantically
 * equal. If both follow each other, then they are an iteration of semantically equal children.
 * But they are not lexically equal.
 * </p>
 * <p>
 * This class determines equal subsequences following each other. It is provided with a minimal node
 * equality the equal nodes should have. Through this, it is possible to find e.g. lexically
 * equal subsequence through a first application of this rule and semantically equal children to 
 * a later application of this rule. This is used by the {@link TemporalRelationshipRuleManager}
 * which instantiates this rule three times, each with a different minimal equality.
 * </p>
 * <p>
 * The equal subsequences are determined through trial and error. This algorithm has a high effort
 * as it tries in the worst case all possible combinations of sub lists in all possible parts of
 * the list of children of a provided parent node. The steps for each trial are.
 * <ul>
 *   <li>for all possible subparts of the children of the provided parent
 *   <ul>
 *     <li>for all possible first sublists in the subpart
 *     <ul>
 *       <li>for all succeeding next sublists in this part</li>
 *       <ul>
 *         <li>check if this sublist is equal to all previously identified sublist in this part</li>
 *       </ul>
 *     </ul>
 *     <li>
 *       if a combination of sublists is found in this subpart which are all equal to each other
 *       at the provided minimal equality level, an iteration in this subpart was found.
 *     </li>
 *       <ul>
 *         <li>merge the identified equal sublists to an iteration</li>
 *       </ul>
 *   </ul>
 * </ul>
 * The algorithm tries to optimize if all children are event tasks and if the sublists shall be
 * lexically equal. In this case, the sublist all have to have the same length. The trial and
 * error reduces to a minimum of possible sublists.
 * </p>
 * 
 * @author Patrick Harms
 */
public class DefaultIterationDetectionRule implements TemporalRelationshipRule {
    
    /**
     * <p>
     * the node equality manager needed for comparing task tree nodes with each other
     * </p>
     */
    private NodeEqualityRuleManager nodeEqualityRuleManager;

    /**
     * <p>
     * the minimal node equality two identified sublists need to have to consider them as equal
     * and to create an iteration for
     * </p>
     */
    private NodeEquality minimalNodeEquality;

    /**
     * <p>
     * instantiates the rule and initializes it with a node equality rule manager and the minimal
     * node equality identified sublist must have to consider them as iterated.
     * </p>
     */
    DefaultIterationDetectionRule(NodeEqualityRuleManager nodeEqualityRuleManager,
                                  NodeEquality            minimalNodeEquality)
    {
        super();
        this.nodeEqualityRuleManager = nodeEqualityRuleManager;
        this.minimalNodeEquality = minimalNodeEquality;
    }

    /*
     * (non-Javadoc)
     * 
     * @see TemporalRelationshipRule#apply(TaskTreeNode, TaskTreeBuilder, TaskTreeNodeFactory)
     */
    @Override
    public RuleApplicationResult apply(ITaskTreeNode        parent,
                                       ITaskTreeBuilder     treeBuilder,
                                       ITaskTreeNodeFactory nodeFactory,
                                       boolean              finalize)
    {
        if (!(parent instanceof ISequence)) {
            return null;
        }

        if (!finalize) {
            // the rule is always feasible as iterations may occur at any time
            RuleApplicationResult result = new RuleApplicationResult();
            result.setRuleApplicationStatus(RuleApplicationStatus.RULE_APPLICATION_FEASIBLE);
            return result;
        }

        // parent must already have at least 2 children
        if ((parent.getChildren() == null) || (parent.getChildren().size() < 2)) {
            return null;
        }
        
        
        SubSequences subSequences = getEqualSubsequences(parent, treeBuilder, nodeFactory);

        if (subSequences != null) {
            RuleApplicationResult result = new RuleApplicationResult();

            mergeEqualNodes(subSequences.equalVariants, treeBuilder, nodeFactory);
            IIteration newIteration = createIterationBasedOnIdentifiedVariants
                (subSequences, treeBuilder, nodeFactory, result);

            determineNewlyCreatedParentTasks(parent, newIteration, result);
            
            // remove iterated children
            for (int j = subSequences.start; j < subSequences.end; j++) {
                treeBuilder.removeChild((ISequence) parent, subSequences.start);
            }

            // add the new iteration instead
            treeBuilder.addChild((ISequence) parent, subSequences.start, newIteration);

            result.setRuleApplicationStatus(RuleApplicationStatus.RULE_APPLICATION_FINISHED);
            return result;
        }

        return null;
    }

    /**
     * <p>
     * this method initiates the trial and error algorithm denoted in the description of this class.
     * Its main purpose is the selection of a subpart of all children in the parent node in which
     * equal sublists shall be searched. It is important, to always find the last iterations in a
     * part first. The reason for this are iterations of iterations. If we always found the first
     * iteration in a subpart first, then this may be an iteration of iterations. However, there
     * may be subsequent iterations to be included in this iteration. But these iterations are not
     * found yet, as they occur later in the sequence. Therefore, if we always find the last
     * iteration in a sequence first, iterations of iterations are identified, last.
     * </p>
     * 
     * @param parent      the parent node in which iterations of children shall be found
     * @param treeBuilder the tree builder that can be used for connecting task tree nodes
     * @param nodeFactory the node factory that can be used for instantiating task tree nodes
     * 
     * @return the iterated subsequences identified in a specific part (contains the equal
     *         subsequences as well as the start (inclusive) and end (exclusive) index of the
     *         subpart in which the sequences were found) 
     */
    private SubSequences getEqualSubsequences(ITaskTreeNode        parent,
                                              ITaskTreeBuilder     treeBuilder,
                                              ITaskTreeNodeFactory nodeFactory)
    {
        SubSequences subSequences = null;

        // to find longer iterations first, start with long sequences
        FIND_ITERATION:
        for (int end = parent.getChildren().size(); end > 0; end--) {
            for (int start = 0; start < end; start++) {
                boolean useEqualSublistLengths = equalSublistLengthsCanBeUsed(parent, start, end);

                subSequences = new SubSequences();
                subSequences.start = start;

                boolean foundFurtherVariants = findFurtherVariants
                    (subSequences, parent, start, end, treeBuilder, nodeFactory,
                     useEqualSublistLengths);

                if (foundFurtherVariants) {
                    break FIND_ITERATION;
                }
                else {
                    subSequences = null;
                }
            }
        }
        
        return subSequences;
    }

    /**
     * <p>
     * for optimization purposes, we check if the length of the sublists to be identified as
     * iterations has to be the same for any sublist. This only applies, if the minimum node
     * equality to be checked for is lexical equality. If the children of the parent are all event
     * tasks, then sublists can only be lexically equal, if they all have the same length.
     * Therefore we check, if the minimal node equality is lexical equality. And if so, we also
     * check if all children of the parent in which an iteration shall be searched for are event
     * tasks.
     * </p>
     *
     * @param parent the parent node to search for iterations of its children
     * @param start  the beginning of the subpart (inclusive) to be considered
     * @param end    the end of the subpart (exclusive) to be considered
     * 
     * @return true, if the sublists must have the same lengths, false else
     */
    private boolean equalSublistLengthsCanBeUsed(ITaskTreeNode parent, int start, int end) {
        boolean equalLengthsCanBeUsed = minimalNodeEquality.isAtLeast(NodeEquality.LEXICALLY_EQUAL);
        
        if (equalLengthsCanBeUsed) {
            for (int i = start; i < end; i++) {
                if (!(parent.getChildren().get(i) instanceof IEventTask)) {
                    equalLengthsCanBeUsed = false;
                    break;
                }
            }
        }

        return equalLengthsCanBeUsed;
    }

    /**
     * <p>
     * this method starts at a specific position in the list of children of the provided parent
     * and checks, if it finds a further sublist, that matches the already found sublists. If
     * the sublist lengths must be equal, it only searches for a sublist of the same length of the
     * already found sublists. The method calls itself if it identifies a further equal sublist but
     * if the end of the subpart of children is not yet reached.
     * </p>
     * 
     * @param subSequences           the sublist found so far against which equality of the next
     *                               sublist must be checked
     * @param parent                 the parent node of which the children are analyzed
     * @param start                  the starting index from which to start the next sublist to be
     *                               identified
     * @param end                    the end index (exclusive) of the current subpart of children
     *                               in which iterations are searched for
     * @param treeBuilder            the tree builder that can be used for connecting task tree
     *                               nodes
     * @param nodeFactory            the node factory that can be used for instantiating task tree
     *                               nodes
     * @param useEqualSublistLengths true if the sublists to be searched for all need to have the
     *                               same length
     * 
     * @return true if a further equal variant was found, false else
     */
    private boolean findFurtherVariants(SubSequences         subSequences,
                                        ITaskTreeNode        parent,
                                        int                  start,
                                        int                  end,
                                        ITaskTreeBuilder     treeBuilder,
                                        ITaskTreeNodeFactory nodeFactory,
                                        boolean              useEqualSublistLengths)
    {
        boolean foundFurtherVariants = (start == end) && (subSequences.equalVariants.size() > 1);
        
        int minChildCount = 1;
        int maxChildCount = end - start;
        
        if (useEqualSublistLengths && (subSequences.equalVariants.size() > 0)) {
            minChildCount = subSequences.equalVariants.get(0).getChildren().size();
            maxChildCount = Math.min(minChildCount, maxChildCount);
        }
        
        for (int childCount = minChildCount; childCount <= maxChildCount; childCount++) {
            if (useEqualSublistLengths && (((end - start) % childCount) != 0)) {
                continue;
            }
            
            ISequence furtherVariant = nodeFactory.createNewSequence();
            
            for (int j = start; j < start + childCount; j++) {
                treeBuilder.addChild(furtherVariant, parent.getChildren().get(j));
            }
            
            boolean allVariantsEqual = true;
            
            for (ITaskTreeNode equalVariant : subSequences.equalVariants) {
                NodeEquality nodeEquality =
                    nodeEqualityRuleManager.applyRules(equalVariant, furtherVariant);
                
                if (!nodeEquality.isAtLeast(minimalNodeEquality)) {
                    allVariantsEqual = false;
                    break;
                }
            }
            
            if (allVariantsEqual) {
                
                // we found a further variant. Add it to the list of variants and try to find
                // further variants. Ignore, if none is available
                int index = subSequences.equalVariants.size();
                subSequences.equalVariants.add(index, furtherVariant);
                
                foundFurtherVariants = findFurtherVariants
                    (subSequences, parent, start + childCount, end, treeBuilder, nodeFactory,
                     useEqualSublistLengths);

                if (foundFurtherVariants) {
                    subSequences.end = end;
                    break;
                }
                else {
                    subSequences.equalVariants.remove(index);
                }
            }
        }
        
        return foundFurtherVariants;
    }

    /**
     * <p>
     * this method merges task tree nodes in a list, if they can be merged. for this, it tries
     * to merge every node with every other node in the provided list using the
     * {@link #mergeEqualTasks(ITaskTreeNode, ITaskTreeNode, ITaskTreeBuilder, ITaskTreeNodeFactory)}
     * method. If a merge is possible, it removes the merged nodes from the list and adds the
     * merge result. 
     * </p>
     *
     * @param nodes       the list of nodes to be merged
     * @param treeBuilder the tree builder that can be used for connecting task tree nodes
     * @param nodeFactory the node factory that can be used for instantiating task tree nodes
     */
    private void mergeEqualNodes(List<ITaskTreeNode>   nodes,
                                 ITaskTreeBuilder      treeBuilder,
                                 ITaskTreeNodeFactory  nodeFactory)
    {
        int index1 = 0;
        int index2 = 0;
        ITaskTreeNode variant1;
        ITaskTreeNode variant2;
        
        while (index1 < nodes.size()) {
            variant1 = nodes.get(index1);
            index2 = index1 + 1;
            
            while (index2 < nodes.size()) {
                variant2 = nodes.get(index2);
                ITaskTreeNode mergedChild =
                    mergeEqualTasks(variant1, variant2, treeBuilder, nodeFactory);
                
                if (mergedChild != null) {
                    // if we merged something start from the beginning to perform the next merge
                    nodes.remove(index2);
                    nodes.remove(index1);
                    nodes.add(index1, mergedChild);
                    index1 = -1;
                    break;
                }
                else {
                    index2++;
                }
            }
            
            index1++;
        }
    }

    /**
     * <p>
     * this method merges two equal tasks with each other if possible. If the tasks are lexically
     * equal, the first of them is returned as merge result. If both tasks are of the same
     * temporal relationship type, the appropriate merge method is called to merge them. If one
     * of the nodes is a selection, the other one is added as a variant of this selection.
     * (However, if both nodes are selections, they are merged using the appropriate merge method.)
     * If merging is not possible, then a selection of both provided nodes is created and
     * returned as merge result.
     * </p>
     *
     * @param node1       the first task to be merged
     * @param node2       the second task to be merged
     * @param treeBuilder the tree builder that can be used for connecting task tree nodes
     * @param nodeFactory the node factory that can be used for instantiating task tree nodes
     * 
     * @return the result of the merge
     */
    private ITaskTreeNode mergeEqualTasks(ITaskTreeNode         node1,
                                          ITaskTreeNode         node2,
                                          ITaskTreeBuilder      treeBuilder,
                                          ITaskTreeNodeFactory  nodeFactory)
    {
        ITaskTreeNode mergeResult = null;
        
        if ((node1 instanceof ISequence) && (node2 instanceof ISequence)) {
            mergeResult = mergeEqualSequences
                ((ISequence) node1, (ISequence) node2, treeBuilder, nodeFactory);
        }
        else if ((node1 instanceof ISelection) && (node2 instanceof ISelection)) {
            mergeResult = mergeEqualSelections
                ((ISelection) node1, (ISelection) node2, treeBuilder, nodeFactory);
        }
        else if ((node1 instanceof IIteration) && (node2 instanceof IIteration)) {
            mergeResult = mergeEqualIterations
                ((IIteration) node1, (IIteration) node2, treeBuilder, nodeFactory);
        }
        else if (node1 instanceof ISelection) {
            treeBuilder.addChild((ISelection) node1, node2);
            mergeResult = node1;
        }
        else if (node2 instanceof ISelection) {
            treeBuilder.addChild((ISelection) node2, node1);
            mergeResult = node2;
        }
        else if (node1 instanceof IIteration) {
            mergeResult = mergeEqualTasks
                (((IIteration) node1).getChildren().get(0), node2, treeBuilder, nodeFactory);
            
            if (mergeResult != null) {
                IIteration iteration = nodeFactory.createNewIteration();
                treeBuilder.setChild(iteration, mergeResult);
                mergeResult = iteration;
            }
        }
        else if (node2 instanceof IIteration) {
            mergeResult = mergeEqualTasks
                (((IIteration) node2).getChildren().get(0), node1, treeBuilder, nodeFactory);
            
            if (mergeResult != null) {
                IIteration iteration = nodeFactory.createNewIteration();
                treeBuilder.setChild(iteration, mergeResult);
                mergeResult = iteration;
            }
        }
        else {
            NodeEquality nodeEquality = nodeEqualityRuleManager.applyRules(node1, node2);
            
            if (nodeEquality.isAtLeast(NodeEquality.LEXICALLY_EQUAL)) {
                mergeResult = node1;
            }
        }

        if (mergeResult == null) {
            mergeResult = nodeFactory.createNewSelection();
            treeBuilder.addChild((ISelection) mergeResult, node1);
            treeBuilder.addChild((ISelection) mergeResult, node2);
        }
        
        return mergeResult;
    }

    /**
     * <p>
     * merges equal sequences. This is done through trying to merge each node of sequence 1 with
     * the node in sequence 2 being located at the same position. If not all children can be merged
     * or if the sequences have different lengths, null is returned to indicate, that merging is
     * not possible. For merging children, the
     * {@link #mergeEqualTasks(ITaskTreeNode, ITaskTreeNode, ITaskTreeBuilder, ITaskTreeNodeFactory)}
     * method is called.
     * </p>
     *
     * @param sequence1   the first sequence to be merged
     * @param sequence2   the second sequence to be merged
     * @param treeBuilder the tree builder that can be used for connecting task tree nodes
     * @param nodeFactory the node factory that can be used for instantiating task tree nodes
     * 
     * @return the result of the merge or null if merging was not possible
     */
    private ISequence mergeEqualSequences(ISequence             sequence1,
                                          ISequence             sequence2,
                                          ITaskTreeBuilder      treeBuilder,
                                          ITaskTreeNodeFactory  nodeFactory)
    {
        ISequence mergeResult = null;
        
        if (sequence1.getChildren().size() == sequence2.getChildren().size()) {
            mergeResult = nodeFactory.createNewSequence();
            
            for (int i = 0; i < sequence1.getChildren().size(); i++) {
                ITaskTreeNode mergedNode = mergeEqualTasks
                    (sequence1.getChildren().get(i), sequence2.getChildren().get(i),
                     treeBuilder, nodeFactory);
                
                if (mergedNode != null) {
                    treeBuilder.addChild(mergeResult, mergedNode);
                }
                else {
                    mergeResult = null;
                    break;
                }
            }
        }
        
        return mergeResult;
    }

    /**
     * <p>
     * merges equal selections. This is done by adding those children of the second selection to
     * the first selection that can not be merged with any of the children of the first selection.
     * If a merge is possible and this merge is not a simple selection of the merged children,
     * then the merged child replaces the child of the first selection which was merged.
     * </p>
     *
     * @param selection1  the first selection to be merged
     * @param selection2  the second selection to be merged
     * @param treeBuilder the tree builder that can be used for connecting task tree nodes
     * @param nodeFactory the node factory that can be used for instantiating task tree nodes
     * 
     * @return the result of the merge which is never null
     */
    private ITaskTreeNode mergeEqualSelections(ISelection            selection1,
                                               ISelection            selection2,
                                               ITaskTreeBuilder      treeBuilder,
                                               ITaskTreeNodeFactory  nodeFactory)
    {
        ISelection mergeResult = selection1;
        
        ITaskTreeNode childToMerge = null;
        ITaskTreeNode mergedChild = null;
        
        // check for each child of selection 2 if it is a duplicate of one of the children
        // if selection 1. If not, add it as further child to the merge result, else skip it.
        for (int i = 0; i < selection2.getChildren().size(); i++) {
            childToMerge = selection2.getChildren().get(i);
            for (int j = 0; j < selection1.getChildren().size(); j++) {
                mergedChild = mergeEqualTasks
                    (selection1.getChildren().get(j), childToMerge, treeBuilder, nodeFactory);
                
                // a merge must not be a selection, except it is one of the children. Otherwise
                // no real merge was done.
                if ((mergedChild != null) &&
                    ((!(mergedChild instanceof ISelection)) ||
                     (selection1.getChildren().get(j) == mergedChild) ||
                     (childToMerge == mergedChild)))
                {
                    // we found a real merge. So replace the original child in selection 1 with
                    // the merged child
                    treeBuilder.removeChild(selection1, selection1.getChildren().get(j));
                    treeBuilder.addChild(selection1, mergedChild);
                    mergedChild = null;
                    childToMerge = null;
                    break;
                }
            }
            
            if (childToMerge != null) {
                treeBuilder.addChild(selection1, childToMerge);
            }
        }
        
        return mergeResult;
    }

    /**
     * <p>
     * merges equal iterations. This is done through merging the children of both iterations. If
     * this is possible, a resulting iteration with the merge result of the children as its own
     * child is returned. Otherwise null is returned to indicate that merging was not possible.
     * </p>
     *
     * @param selection1  the first iteration to be merged
     * @param selection2  the second iteration to be merged
     * @param treeBuilder the tree builder that can be used for connecting task tree nodes
     * @param nodeFactory the node factory that can be used for instantiating task tree nodes
     * 
     * @return the result of the merge or null if merging is not possible
     */
    private ITaskTreeNode mergeEqualIterations(IIteration            iteration1,
                                               IIteration            iteration2,
                                               ITaskTreeBuilder      treeBuilder,
                                               ITaskTreeNodeFactory  nodeFactory)
    {
        ITaskTreeNode mergedChild = mergeEqualTasks
            (iteration1.getChildren().get(0), iteration2.getChildren().get(0),
             treeBuilder, nodeFactory);
        
        IIteration mergeResult = null;
        
        if (mergedChild != null) {
            mergeResult = nodeFactory.createNewIteration();
            treeBuilder.setChild(mergeResult, mergedChild);
        }
        
        return mergeResult;
    }

    /**
     * <p>
     * this is a convenience method to create an iteration based on the identified and already
     * merged iterated subsequences. This method creates the simplest iteration possible. As an
     * example, if always the same task tree node is iterated, it becomes the child of the
     * iteration. If a sequence of tasks is iterated, this sequence becomes the child of the
     * iteration. It several equal sublists or nodes which are not lexically equal are iterated
     * they become a selection which in turn become the child of the iteration.
     * </p>
     *
     * @param subsequences the identified and already merged equal subsequences
     * @param treeBuilder  the tree builder that can be used for connecting task tree nodes
     * @param nodeFactory  the node factory that can be used for instantiating the iteration
     * 
     * @return the resulting iteration
     */
    private IIteration createIterationBasedOnIdentifiedVariants(SubSequences          subsequences,
                                                                ITaskTreeBuilder      treeBuilder,
                                                                ITaskTreeNodeFactory  nodeFactory,
                                                                RuleApplicationResult result)
    {
        IIteration newIteration = nodeFactory.createNewIteration();
        result.addNewlyCreatedParentNode(newIteration);

        if (subsequences.equalVariants.size() == 1) {
            // all children are the same. Create an iteration of this child
            if (subsequences.equalVariants.get(0).getChildren().size() == 1) {
                // there is only one equal variant and this has only one child. So create an
                // iteration of this child
                treeBuilder.setChild
                    (newIteration, subsequences.equalVariants.get(0).getChildren().get(0));
            }
            else {
                // there was an iteration of one equal sequence
                treeBuilder.setChild(newIteration, subsequences.equalVariants.get(0));
                result.addNewlyCreatedParentNode(subsequences.equalVariants.get(0));
            }
        }
        else {
            // there are distinct variants of equal subsequences or children --> create an
            // iterated selection
            ISelection selection = nodeFactory.createNewSelection();
            result.addNewlyCreatedParentNode(selection);

            for (ITaskTreeNode variant : subsequences.equalVariants) {
                if (variant.getChildren().size() == 1) {
                    treeBuilder.addChild(selection, variant.getChildren().get(0));
                }
                else {
                    treeBuilder.addChild(selection, variant);
                    result.addNewlyCreatedParentNode(variant);
                }
            }

            treeBuilder.setChild(newIteration, selection);
        }
        
        return newIteration;
    }

    /**
     * <p>
     * as the method has to denote all newly created parent nodes this method identifies them by
     * comparing the existing subtree with the newly created iteration. Only those parent nodes
     * in the new iteration, which are not already found in the existing sub tree are denoted as
     * newly created. We do this in this way, as during the iteration detection algorithm, many
     * parent nodes are created, which may be discarded later. It is easier to identify the
     * remaining newly created parent nodes through this way than to integrate it into the
     * algorithm.
     * </p>
     * 
     * @param existingSubTree the existing subtree
     * @param newSubTree      the identified iteration
     * @param result          the rule application result into which the newly created parent nodes
     *                        shall be stored.
     */
    private void determineNewlyCreatedParentTasks(ITaskTreeNode         existingSubTree,
                                                  ITaskTreeNode         newSubTree,
                                                  RuleApplicationResult result)
    {
        List<ITaskTreeNode> existingParentNodes = getParentNodes(existingSubTree);
        List<ITaskTreeNode> newParentNodes = getParentNodes(newSubTree);
        
        boolean foundNode;
        for (ITaskTreeNode newParentNode : newParentNodes) {
            foundNode = false;
            for (ITaskTreeNode existingParentNode : existingParentNodes) {
                // It is sufficient to compare the references. The algorithm reuses nodes as they
                // are. So any node existing in the new structure that is also in the old structure
                // was unchanged an therefore does not need to be handled as a newly created one.
                // but every node in the new structure that is not included in the old structure
                // must be treated as a newly created one.
                if (newParentNode == existingParentNode) {
                    foundNode = true;
                    break;
                }
            }
            
            if (!foundNode) {
                result.addNewlyCreatedParentNode(newParentNode);
            }
        }
        
    }

    /**
     * <p>
     * convenience method to determine all parent nodes existing in a subtree
     * </p>
     *
     * @param subtree the subtree to search for parent nodes in
     * 
     * @return a list of parent nodes existing in the subtree
     */
    private List<ITaskTreeNode> getParentNodes(ITaskTreeNode subtree) {
        List<ITaskTreeNode> parentNodes = new ArrayList<ITaskTreeNode>();
        
        if (subtree.getChildren().size() > 0) {
            parentNodes.add(subtree);
            
            for (ITaskTreeNode child : subtree.getChildren()) {
                parentNodes.addAll(getParentNodes(child));
            }
        }
        
        return parentNodes;
    }

    /**
     * <p>
     * used to have a container for equal sublists identified in a sub part of the children of
     * a parent node.
     * </p>
     * 
     * @author Patrick Harms
     */
    private static class SubSequences {

        /**
         * <p>
         * the beginning of the subpart of the children of the parent node in which the sublists
         * are found (inclusive)
         * </p>
         */
        public int start;
        
        /**
         * <p>
         * the end of the subpart of the children of the parent node in which the sublists
         * are found (exclusive)
         * </p>
         */
        public int end;
        
        /**
         * <p>
         * the equal sublists found in the subpart of the children of the parent node
         * </p>
         */
        List<ITaskTreeNode> equalVariants = new ArrayList<ITaskTreeNode>();
        
    }

}