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

//   Copyright 2012 Georg-August-Universität Göttingen, Germany
//
//   Licensed under the Apache License, Version 2.0 (the "License");
//   you may not use this file except in compliance with the License.
//   You may obtain a copy of the License at
//
//       http://www.apache.org/licenses/LICENSE-2.0
//
//   Unless required by applicable law or agreed to in writing, software
//   distributed under the License is distributed on an "AS IS" BASIS,
//   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
//   See the License for the specific language governing permissions and
//   limitations under the License.

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

import java.util.List;

import de.ugoe.cs.autoquest.tasktrees.treeifc.IIteration;
import de.ugoe.cs.autoquest.tasktrees.treeifc.IOptional;
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;
import difflib.ChangeDelta;
import difflib.Chunk;
import difflib.DeleteDelta;
import difflib.Delta;
import difflib.InsertDelta;
import difflib.Patch;
import difflib.myers.DiffNode;
import difflib.myers.MyersDiff;
import difflib.myers.PathNode;
import difflib.myers.Snake;

/**
 * <p>
 * TODO comment
 * </p>
 * 
 * @author Patrick Harms
 */
class TaskTreeNodeMerger {
    
    /** */
    private ITaskTreeNodeFactory taskTreeNodeFactory;
    
    /** */
    private ITaskTreeBuilder taskTreeBuilder;
    
    /** */
    private TaskTreeNodeComparator nodeComparator;
    
    /**
     * <p>
     * TODO: comment
     * </p>
     *
     * @param taskTreeNodeFactory     the node factory to be used if nodes must be instantiated
     * @param taskTreeBuilder         the task tree builder to be used if nodes must be merged
     * @param nodeEqualityRuleManager the node equality rule manager that may be needed for
     *                                comparing nodes during merge
     * @param consideredNodeEquality  the node equality considered when comparing nodes to
     *                                identify them as equal
     */
    TaskTreeNodeMerger(ITaskTreeNodeFactory   taskTreeNodeFactory,
                       ITaskTreeBuilder       taskTreeBuilder,
                       TaskTreeNodeComparator nodeComparator)
    {
        super();
        this.taskTreeNodeFactory = taskTreeNodeFactory;
        this.taskTreeBuilder = taskTreeBuilder;
        this.nodeComparator = nodeComparator;
    }

    /**
     * <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 #mergeTaskNodes(ITaskTreeNode, ITaskTreeNode)} 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
     */
    void mergeTaskNodes(List<ITaskTreeNode> nodes) {
        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 = mergeTaskNodes(variant1, variant2);
                
                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 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
     * 
     * @return the result of the merge
     */
    ITaskTreeNode mergeTaskNodes(ITaskTreeNode node1, ITaskTreeNode node2) {
        ITaskTreeNode mergeResult = null;
        
        // both are of same parent type
        if ((node1 instanceof ISequence) && (node2 instanceof ISequence)) {
            mergeResult = mergeSequences((ISequence) node1, (ISequence) node2);
        }
        else if ((node1 instanceof ISelection) && (node2 instanceof ISelection)) {
            mergeResult = mergeSelections((ISelection) node1, (ISelection) node2);
        }
        else if ((node1 instanceof IIteration) && (node2 instanceof IIteration)) {
            mergeResult = mergeIterations((IIteration) node1, (IIteration) node2);
        }
        else if ((node1 instanceof IOptional) && (node2 instanceof IOptional)) {
            mergeResult = mergeOptionals((IOptional) node1, (IOptional) node2);
        }
        // one is an iteration
        else if (node1 instanceof IIteration) {
            mergeResult = mergeTaskNodes(((IIteration) node1).getChildren().get(0), node2);
            
            if (mergeResult != null) {
                taskTreeBuilder.setChild((IIteration) node1, mergeResult);
                mergeResult = node1;
            }
        }
        else if (node2 instanceof IIteration) {
            mergeResult = mergeTaskNodes(((IIteration) node2).getChildren().get(0), node1);
            
            if (mergeResult != null) {
                taskTreeBuilder.setChild((IIteration) node2, mergeResult);
                mergeResult = node2;
            }
        }
        // one is an optional
        else if (node1 instanceof IOptional) {
            mergeResult = mergeTaskNodes(((IOptional) node1).getChildren().get(0), node2);
            
            if (mergeResult != null) {
                taskTreeBuilder.setChild((IOptional) node1, mergeResult);
                mergeResult = node1;
            }
        }
        else if (node2 instanceof IOptional) {
            mergeResult = mergeTaskNodes(((IOptional) node2).getChildren().get(0), node1);
            
            if (mergeResult != null) {
                taskTreeBuilder.setChild((IOptional) node2, mergeResult);
                mergeResult = node2;
            }
        }
        // one is a selection
        else if (node1 instanceof ISelection) {
            ISelection selection2 = taskTreeNodeFactory.createNewSelection();
            taskTreeBuilder.addChild(selection2, node2);
            mergeResult = mergeSelections((ISelection) node1, selection2);
        }
        else if (node2 instanceof ISelection) {
            ISelection selection1 = taskTreeNodeFactory.createNewSelection();
            taskTreeBuilder.addChild(selection1, node1);
            mergeResult = mergeSelections(selection1, (ISelection) node2);
        }
        // one is a sequence
        else if (node1 instanceof ISequence) {
            ISequence sequence2 = taskTreeNodeFactory.createNewSequence();
            taskTreeBuilder.addChild(sequence2, node2);
            mergeResult = mergeSequences((ISequence) node1, sequence2);
        }
        else if (node2 instanceof ISequence) {
            ISequence sequence1 = taskTreeNodeFactory.createNewSequence();
            taskTreeBuilder.addChild(sequence1, node1);
            mergeResult = mergeSequences(sequence1, (ISequence) node2);
        }
        // both are event tasks
        else {
            // only drop nodes which are definitely lexically equal
            if (nodeComparator.areLexicallyEqual(node1, node2)) {
                mergeResult = node1;
            }
        }

        if (mergeResult == null) {
            mergeResult = taskTreeNodeFactory.createNewSelection();
            taskTreeBuilder.setDescription(mergeResult, "variants of " + node1);
            taskTreeBuilder.addChild((ISelection) mergeResult, node1);
            taskTreeBuilder.addChild((ISelection) mergeResult, node2);
        }
        
        return mergeResult;
    }

    /**
     * <p>
     * merges equal sequences. This is done through performing a diff between the two sequences.
     * For each identified difference appropriate substructures are created. For equal parts,
     * the appropriate equal nodes are merged using
     * {@link #mergeTaskNodes(ITaskTreeNode, ITaskTreeNode)} and the result is added to the
     * overall merge result.
     * </p>
     *
     * @param sequence1 the first sequence to be merged
     * @param sequence2 the second sequence to be merged
     * 
     * @return the result of the merge or null if merging was not possible
     */
    ITaskTreeNode mergeSequences(ISequence sequence1, ISequence sequence2) {
        ITaskTreeNode mergeResult = taskTreeNodeFactory.createNewSequence();
        
        List<ITaskTreeNode> children1 = sequence1.getChildren();
        List<ITaskTreeNode> children2 = sequence2.getChildren();
        
        Patch patch = new TaskTreeNodeSequenceMyersDiff().getDiff(children1, children2);
        
        int index1 = 0;
        int index2 = 0;
        
        while ((index1 < children1.size()) || (index2 < children2.size())) {
            boolean foundDelta = false;
            for (Delta delta : patch.getDeltas()) {
                if ((delta.getOriginal().getPosition() == index1) &&
                    (delta.getRevised().getPosition() == index2))
                {
                    if (delta.getType() == Delta.TYPE.DELETE) {
                        ITaskTreeNode option = getSubTree(children1, delta.getOriginal());
                        index1 += delta.getOriginal().size();
                        
                        IOptional optional = taskTreeNodeFactory.createNewOptional();
                        taskTreeBuilder.setChild(optional, option);
                        taskTreeBuilder.addChild((ISequence) mergeResult, optional);
                    }
                    else if (delta.getType() == Delta.TYPE.INSERT) {
                        ITaskTreeNode option = getSubTree(children2, delta.getRevised());
                        index2 += delta.getRevised().size();
                        
                        IOptional optional = taskTreeNodeFactory.createNewOptional();
                        taskTreeBuilder.setChild(optional, option);
                        taskTreeBuilder.addChild((ISequence) mergeResult, optional);
                    }
                    else {
                        ITaskTreeNode variant1 = getSubTree(children1, delta.getOriginal());
                        index1 += delta.getOriginal().size();
                        
                        ITaskTreeNode variant2 = getSubTree(children2, delta.getRevised());
                        index2 += delta.getRevised().size();
                        
                        ISelection selection = taskTreeNodeFactory.createNewSelection();
                        taskTreeBuilder.addChild(selection, variant1);
                        taskTreeBuilder.addChild(selection, variant2);
                        taskTreeBuilder.addChild((ISequence) mergeResult, selection);
                    }
                    
                    foundDelta = true;
                }
            }
                
            if (!foundDelta) {
                ITaskTreeNode mergedNode =
                    mergeTaskNodes(children1.get(index1++), children2.get(index2++));
                taskTreeBuilder.addChild((ISequence) mergeResult, mergedNode);
            }
        }
        
        List<ITaskTreeNode> mergeResultChildren = mergeResult.getChildren();
        if ((mergeResultChildren != null) && (mergeResultChildren.size() == 1) &&
            (mergeResultChildren.get(0) instanceof ISelection))
        {
            mergeResult = mergeResultChildren.get(0);
        }
        
        taskTreeBuilder.setDescription(mergeResult, sequence1.getDescription());
        
        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
     * 
     * @return the result of the merge which is never null
     */
    ITaskTreeNode mergeSelections(ISelection selection1, ISelection selection2) {
        ISelection mergeResult = selection1;
        
        ITaskTreeNode childToMerge = null;
        ITaskTreeNode mergedChild = null;
        
        List<ITaskTreeNode> children1 = selection1.getChildren();
        List<ITaskTreeNode> children2 = selection2.getChildren();
        
        // 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 < children2.size(); i++) {
            childToMerge = children2.get(i);
            for (int j = 0; j < children1.size(); j++) {
                mergedChild = mergeTaskNodes(children1.get(j), childToMerge);
                
                // 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)) ||
                     (children1.get(j) == mergedChild) || (childToMerge == mergedChild)))
                {
                    // we found a real merge. So replace the original child in selection 1 with
                    // the merged child
                    taskTreeBuilder.removeChild(selection1, children1.get(j));
                    taskTreeBuilder.addChild(selection1, mergedChild);
                    mergedChild = null;
                    childToMerge = null;
                    break;
                }
            }
            
            if (childToMerge != null) {
                taskTreeBuilder.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 iteration1 the first iteration to be merged
     * @param iteration2 the second iteration to be merged
     * 
     * @return the result of the merge or null if merging is not possible
     */
    ITaskTreeNode mergeIterations(IIteration iteration1, IIteration iteration2) {
        ITaskTreeNode mergedChild = mergeTaskNodes
            (iteration1.getChildren().get(0), iteration2.getChildren().get(0));
        
        IIteration mergeResult = null;
        
        if (mergedChild != null) {
            mergeResult = iteration1;
            taskTreeBuilder.setChild(mergeResult, mergedChild);
        }
        
        return mergeResult;
    }

    /**
     * <p>
     * merges equal optionals. This is done through merging the children of both optionals. If
     * this is possible, a resulting optional 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 optional1 the first optional to be merged
     * @param optional2 the second optional to be merged
     * 
     * @return the result of the merge or null if merging is not possible
     */
    ITaskTreeNode mergeOptionals(IOptional optional1, IOptional optional2) {
        ITaskTreeNode mergedChild = mergeTaskNodes
            (optional1.getChildren().get(0), optional2.getChildren().get(0));
        
        IOptional mergeResult = null;
        
        if (mergedChild != null) {
            mergeResult = optional1;
            taskTreeBuilder.setChild(mergeResult, mergedChild);
        }
        
        return mergeResult;
    }

    /**
     * <p>
     * determines a task tree node defined by the provided chunk. This is either a single node if
     * the chunck denotes a single child, or it is a sequence of the denoted children.
     * </p>
     */
    private ITaskTreeNode getSubTree(List<ITaskTreeNode> children1, Chunk chunk) {
        ITaskTreeNode part;
        
        if (chunk.size() == 1) {
            part = children1.get(chunk.getPosition());
        }
        else {
            part = taskTreeNodeFactory.createNewSequence();
        
            for (int i = 0; i < chunk.size(); i++) {
                taskTreeBuilder.addChild
                    ((ISequence) part, children1.get(chunk.getPosition() + i));
            }
        }
        
        return part;
    }

    /**
     * 
     */
    private class TaskTreeNodeSequenceMyersDiff extends MyersDiff {
        
        /**
         * 
         */
        private Patch getDiff(List<ITaskTreeNode> variant1, List<ITaskTreeNode> variant2) {
            PathNode path = buildPath(variant1, variant2);
            return buildRevision(path, variant1, variant2);
        }
        
        /**
         * overwrites the default implementation just to change the tree node comparison.
         * This is an extended version of the original implementation respecting the appropriate
         * copyrights. Please see the copyrights of the implementers of the base class for more
         * information
         */
        private PathNode buildPath(List<ITaskTreeNode> variant1, List<ITaskTreeNode> variant2) {
            if (variant1 == null) {
                throw new IllegalArgumentException("variant1 is null");
            }
            
            if (variant2 == null) {
                throw new IllegalArgumentException("variant2 is null");
            }
            
            // these are local constants
            final int N = variant1.size();
            final int M = variant2.size();
            
            final int MAX = N + M + 1;
            final int size = 1 + 2 * MAX;
            final int middle = size / 2;
            final PathNode diagonal[] = new PathNode[size];
            
            diagonal[middle + 1] = new Snake(0, -1, null);
            
            for (int d = 0; d < MAX; d++) {
                for (int k = -d; k <= d; k += 2) {
                    final int kmiddle = middle + k;
                    final int kplus = kmiddle + 1;
                    final int kminus = kmiddle - 1;
                    PathNode prev = null;
                    
                    int i;
                    if ((k == -d) || ((k != d) && (diagonal[kminus].i < diagonal[kplus].i))) {
                        i = diagonal[kplus].i;
                        prev = diagonal[kplus];
                    }
                    else {
                        i = diagonal[kminus].i + 1;
                        prev = diagonal[kminus];
                    }
                    
                    diagonal[kminus] = null; // no longer used
                    
                    int j = i - k;
                    
                    PathNode node = new DiffNode(i, j, prev);
                    
                    // orig and rev are zero-based
                    // but the algorithm is one-based
                    // that's why there's no +1 when indexing the sequences
                    while ((i < N) && (j < M) &&
                           nodeComparator.equals(variant1.get(i), variant2.get(j)))
                    {
                        i++;
                        j++;
                    }
                    
                    if (i > node.i) {
                        node = new Snake(i, j, node);
                    }
                    
                    diagonal[kmiddle] = node;
                    
                    if ((i >= N) && (j >= M)) {
                        return diagonal[kmiddle];
                    }
                }
                diagonal[middle + d - 1] = null;
                
            }
            
            // According to Myers, this cannot happen
            throw new RuntimeException("could not find a diff path");
        }

        /**
         * overwrites the default implementation just to change the tree node comparison.
         * This is an extended version of the original implementation respecting the appropriate
         * copyrights. Please see the copyrights of the implementers of the base class for more
         * information
         */
        private Patch buildRevision(PathNode            path,
                                    List<ITaskTreeNode> variant1,
                                    List<ITaskTreeNode> variant2)
        {
            if (path == null) {
                throw new IllegalArgumentException("path is null");
            }
            
            if (variant1 == null) {
                throw new IllegalArgumentException("variant1 is null");
            }
            
            if (variant2 == null) {
                throw new IllegalArgumentException("variant2 is null");
            }
            
            Patch patch = new Patch();
            if (path.isSnake()) {
                path = path.prev;
            }
            
            while ((path != null) && (path.prev != null) && (path.prev.j >= 0)) {
                if (path.isSnake()) {
                    throw new IllegalStateException
                        ("bad diffpath: found snake when looking for diff");
                }
                
                int i = path.i;
                int j = path.j;
                
                path = path.prev;
                int ianchor = path.i;
                int janchor = path.j;
                
                Chunk original = new Chunk(ianchor, variant1.subList(ianchor, i));
                Chunk revised = new Chunk(janchor, variant2.subList(janchor, j));
                Delta delta = null;
                
                if ((original.size() == 0) && (revised.size() != 0)) {
                    delta = new InsertDelta(original, revised);
                }
                else if ((original.size() > 0) && (revised.size() == 0)) {
                    delta = new DeleteDelta(original, revised);
                }
                else {
                    delta = new ChangeDelta(original, revised);
                }
                
                patch.addDelta(delta);
                
                if (path.isSnake()) {
                    path = path.prev;
                }
            }
            return patch;
        }
        
    }
}