source: trunk/autoquest-core-tasktrees/src/main/java/de/ugoe/cs/autoquest/tasktrees/temporalrelation/utils/TaskTraversalMyersDiff.java @ 1848

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

import de.ugoe.cs.autoquest.tasktrees.temporalrelation.TaskComparator;
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;

/**
 * 
 */
public class TaskTraversalMyersDiff extends MyersDiff {
    
    /**  */
    private final TaskComparator comparator;

    /**
     *
     */
    public TaskTraversalMyersDiff(TaskComparator comparator) {
        this.comparator = comparator;
    }

    /**
     * 
     */
    public Patch getDiff(TaskTraversal variant1, TaskTraversal variant2) {
        PathNode path = buildPath(variant1, variant2);
        return buildRevision(path, variant1, variant2);
    }
    
    /**
     * overwrites the default implementation just to change the tree task 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(TaskTraversal variant1, TaskTraversal 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 task = 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) && comparator.equals(variant1.get(i), variant2.get(j))) {
                    i++;
                    j++;
                }
                
                if (i > task.i) {
                    task = new Snake(i, j, task);
                }
                
                diagonal[kmiddle] = task;
                
                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 task 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,
                                TaskTraversal variant1,
                                TaskTraversal 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));
            int originalSize = original.size();
            Chunk revised = new Chunk(janchor, variant2.subList(janchor, j));
            int revisedSize = revised.size();
            Delta delta = null;
            
            if ((originalSize == 0) && (revisedSize != 0)) {
                delta = new InsertDelta(original, revised);
            }
            else if ((originalSize > 0) && (revisedSize == 0)) {
                delta = new DeleteDelta(original, revised);
            }
            else {
                delta = new ChangeDelta(original, revised);
            }
            
            patch.addDelta(delta);
            
            if (path.isSnake()) {
                path = path.prev;
            }
        }
        return patch;
    }
    
}