StringsComparator.java

/*
 * Licensed to the Apache Software Foundation (ASF) under one or more
 * contributor license agreements.  See the NOTICE file distributed with
 * this work for additional information regarding copyright ownership.
 * The ASF licenses this file to You 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 org.apache.commons.text.diff;

/**
 * <p>
 * It is guaranteed that the comparisons will always be done as
 * <code>o1.equals(o2)</code> where <code>o1</code> belongs to the first
 * sequence and <code>o2</code> belongs to the second sequence. This can
 * be important if subclassing is used for some elements in the first
 * sequence and the <code>equals</code> method is specialized.
 * </p>
 * <p>
 * Comparison can be seen from two points of view: either as giving the smallest
 * modification allowing to transform the first sequence into the second one, or
 * as giving the longest sequence which is a subsequence of both initial
 * sequences. The <code>equals</code> method is used to compare objects, so any
 * object can be put into sequences. Modifications include deleting, inserting
 * or keeping one object, starting from the beginning of the first sequence.
 * </p>
 * <p>
 * This class implements the comparison algorithm, which is the very efficient
 * algorithm from Eugene W. Myers
 * <a href="http://www.cis.upenn.edu/~bcpierce/courses/dd/papers/diff.ps">
 * An O(ND) Difference Algorithm and Its Variations</a>. This algorithm produces
 * the shortest possible {@link EditScript edit script} containing all the
 * {@link EditCommand commands} needed to transform the first sequence into
 * the second one.
 *
 * <p>
 * This code has been adapted from Apache Commons Collections 4.0.
 * </p>
 *
 * @see EditScript
 * @see EditCommand
 * @see CommandVisitor
 * @since 1.0
 */
public class StringsComparator {

    /**
     * First character sequence.
     */
    private final String left;
    /**
     * Second character sequence.
     */
    private final String right;
    /**
     * Temporary array.
     */
    private final int[] vDown;
    /**
     * Temporary array.
     */
    private final int[] vUp;

    /**
     * Simple constructor.
     * <p>
     * Creates a new instance of StringsComparator.
     * </p>
     * <p>
     * It is <em>guaranteed</em> that the comparisons will always be done as
     * <code>o1.equals(o2)</code> where <code>o1</code> belongs to the first
     * sequence and <code>o2</code> belongs to the second sequence. This can be
     * important if subclassing is used for some elements in the first sequence
     * and the <code>equals</code> method is specialized.
     * </p>
     *
     * @param left first character sequence to be compared
     * @param right second character sequence to be compared
     */
    public StringsComparator(final String left, final String right) {
        this.left = left;
        this.right = right;

        final int size = left.length() + right.length() + 2;
        vDown = new int[size];
        vUp   = new int[size];
    }

    /**
     * Get the {@link EditScript} object.
     * <p>
     * It is guaranteed that the objects embedded in the {@link InsertCommand
     * insert commands} come from the second sequence and that the objects
     * embedded in either the {@link DeleteCommand delete commands} or
     * {@link KeepCommand keep commands} come from the first sequence. This can
     * be important if subclassing is used for some elements in the first
     * sequence and the <code>equals</code> method is specialized.
     * </p>
     *
     * @return the edit script resulting from the comparison of the two
     *         sequences
     */
    public EditScript<Character> getScript() {
        final EditScript<Character> script = new EditScript<>();
        buildScript(0, left.length(), 0, right.length(), script);
        return script;
    }

    /**
     * Build an edit script.
     *
     * @param start1  the begin of the first sequence to be compared
     * @param end1  the end of the first sequence to be compared
     * @param start2  the begin of the second sequence to be compared
     * @param end2  the end of the second sequence to be compared
     * @param script the edited script
     */
    private void buildScript(final int start1, final int end1, final int start2, final int end2,
            final EditScript<Character> script) {
        final Snake middle = getMiddleSnake(start1, end1, start2, end2);

        if (middle == null
                || middle.getStart() == end1 && middle.getDiag() == end1 - end2
                || middle.getEnd() == start1 && middle.getDiag() == start1 - start2) {

            int i = start1;
            int j = start2;
            while (i < end1 || j < end2) {
                if (i < end1 && j < end2 && left.charAt(i) == right.charAt(j)) {
                    script.append(new KeepCommand<>(left.charAt(i)));
                    ++i;
                    ++j;
                } else {
                    if (end1 - start1 > end2 - start2) {
                        script.append(new DeleteCommand<>(left.charAt(i)));
                        ++i;
                    } else {
                        script.append(new InsertCommand<>(right.charAt(j)));
                        ++j;
                    }
                }
            }

        } else {

            buildScript(start1, middle.getStart(),
                        start2, middle.getStart() - middle.getDiag(),
                        script);
            for (int i = middle.getStart(); i < middle.getEnd(); ++i) {
                script.append(new KeepCommand<>(left.charAt(i)));
            }
            buildScript(middle.getEnd(), end1,
                        middle.getEnd() - middle.getDiag(), end2,
                        script);
        }
    }

    /**
     * Get the middle snake corresponding to two subsequences of the
     * main sequences.
     * <p>
     * The snake is found using the MYERS Algorithm (this algorithms has
     * also been implemented in the GNU diff program). This algorithm is
     * explained in Eugene Myers article:
     * <a href="http://www.cs.arizona.edu/people/gene/PAPERS/diff.ps">
     * An O(ND) Difference Algorithm and Its Variations</a>.
     * </p>
     *
     * @param start1  the begin of the first sequence to be compared
     * @param end1  the end of the first sequence to be compared
     * @param start2  the begin of the second sequence to be compared
     * @param end2  the end of the second sequence to be compared
     * @return the middle snake
     */
    private Snake getMiddleSnake(final int start1, final int end1, final int start2, final int end2) {
        // Myers Algorithm
        // Initialisations
        final int m = end1 - start1;
        final int n = end2 - start2;
        if (m == 0 || n == 0) {
            return null;
        }

        final int delta  = m - n;
        final int sum    = n + m;
        final int offset = (sum % 2 == 0 ? sum : sum + 1) / 2;
        vDown[1 + offset] = start1;
        vUp[1 + offset]   = end1 + 1;

        for (int d = 0; d <= offset; ++d) {
            // Down
            for (int k = -d; k <= d; k += 2) {
                // First step

                final int i = k + offset;
                if (k == -d || k != d && vDown[i - 1] < vDown[i + 1]) {
                    vDown[i] = vDown[i + 1];
                } else {
                    vDown[i] = vDown[i - 1] + 1;
                }

                int x = vDown[i];
                int y = x - start1 + start2 - k;

                while (x < end1 && y < end2 && left.charAt(x) == right.charAt(y)) {
                    vDown[i] = ++x;
                    ++y;
                }
                // Second step
                if (delta % 2 != 0 && delta - d <= k && k <= delta + d) {
                    if (vUp[i - delta] <= vDown[i]) { // NOPMD
                        return buildSnake(vUp[i - delta], k + start1 - start2, end1, end2);
                    }
                }
            }

            // Up
            for (int k = delta - d; k <= delta + d; k += 2) {
                // First step
                final int i = k + offset - delta;
                if (k == delta - d
                        || k != delta + d && vUp[i + 1] <= vUp[i - 1]) {
                    vUp[i] = vUp[i + 1] - 1;
                } else {
                    vUp[i] = vUp[i - 1];
                }

                int x = vUp[i] - 1;
                int y = x - start1 + start2 - k;
                while (x >= start1 && y >= start2
                        && left.charAt(x) == right.charAt(y)) {
                    vUp[i] = x--;
                    y--;
                }
                // Second step
                if (delta % 2 == 0 && -d <= k && k <= d) {
                    if (vUp[i] <= vDown[i + delta]) { // NOPMD
                        return buildSnake(vUp[i], k + start1 - start2, end1, end2);
                    }
                }
            }
        }

        // this should not happen
        throw new RuntimeException("Internal Error");
    }

    /**
     * Build a snake.
     *
     * @param start  the value of the start of the snake
     * @param diag  the value of the diagonal of the snake
     * @param end1  the value of the end of the first sequence to be compared
     * @param end2  the value of the end of the second sequence to be compared
     * @return the snake built
     */
    private Snake buildSnake(final int start, final int diag, final int end1, final int end2) {
        int end = start;
        while (end - diag < end2
                && end < end1
                && left.charAt(end) == right.charAt(end - diag)) {
            ++end;
        }
        return new Snake(start, end, diag);
    }

    /**
     * This class is a simple placeholder to hold the end part of a path
     * under construction in a {@link StringsComparator StringsComparator}.
     */
    private static class Snake {

        /** Start index. */
        private final int start;

        /** End index. */
        private final int end;

        /** Diagonal number. */
        private final int diag;

        /**
         * Simple constructor. Creates a new instance of Snake with specified indices.
         *
         * @param start  start index of the snake
         * @param end  end index of the snake
         * @param diag  diagonal number
         */
        public Snake(final int start, final int end, final int diag) {
            this.start = start;
            this.end   = end;
            this.diag  = diag;
        }

        /**
         * Get the start index of the snake.
         *
         * @return start index of the snake
         */
        public int getStart() {
            return start;
        }

        /**
         * Get the end index of the snake.
         *
         * @return end index of the snake
         */
        public int getEnd() {
            return end;
        }

        /**
         * Get the diagonal number of the snake.
         *
         * @return diagonal number of the snake
         */
        public int getDiag() {
            return diag;
        }
    }

}