    001/*
    002 * Licensed to the Apache Software Foundation (ASF) under one or more
    003 * contributor license agreements.  See the NOTICE file distributed with
    004 * this work for additional information regarding copyright ownership.
    005 * The ASF licenses this file to You under the Apache License, Version 2.0
    006 * (the "License"); you may not use this file except in compliance with
    007 * the License.  You may obtain a copy of the License at
    008 *
    009 *      https://www.apache.org/licenses/LICENSE-2.0
    010 *
    011 * Unless required by applicable law or agreed to in writing, software
    012 * distributed under the License is distributed on an "AS IS" BASIS,
    013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    014 * See the License for the specific language governing permissions and
    015 * limitations under the License.
    016 */
    017package org.apache.commons.collections4.sequence;
    018
    019import java.util.List;
    020
    021import org.apache.commons.collections4.Equator;
    022import org.apache.commons.collections4.functors.DefaultEquator;
    023
    024/**
    025 * This class allows to compare two objects sequences.
    026 * <p>
    027 * The two sequences can hold any object type, as only the {@code equals}
    028 * method is used to compare the elements of the sequences. It is guaranteed
    029 * that the comparisons will always be done as {@code o1.equals(o2)} where
    030 * {@code o1} belongs to the first sequence and {@code o2} belongs to
    031 * the second sequence. This can be important if subclassing is used for some
    032 * elements in the first sequence and the {@code equals} method is
    033 * specialized.
    034 * </p>
    035 * <p>
    036 * Comparison can be seen from two points of view: either as giving the smallest
    037 * modification allowing to transform the first sequence into the second one, or
    038 * as giving the longest sequence which is a subsequence of both initial
    039 * sequences. The {@code equals} method is used to compare objects, so any
    040 * object can be put into sequences. Modifications include deleting, inserting
    041 * or keeping one object, starting from the beginning of the first sequence.
    042 * </p>
    043 * <p>
    044 * This class implements the comparison algorithm, which is the very efficient
    045 * algorithm from Eugene W. Myers
    046 * <a href="https://www.cis.upenn.edu/~bcpierce/courses/dd/papers/diff.ps">
    047 * An O(ND) Difference Algorithm and Its Variations</a>. This algorithm produces
    048 * the shortest possible
    049 * {@link EditScript edit script}
    050 * containing all the
    051 * {@link EditCommand commands}
    052 * needed to transform the first sequence into the second one.
    053 * </p>
    054 *
    055 * @param <T> The type of elements in the lists.
    056 * @see EditScript
    057 * @see EditCommand
    058 * @see CommandVisitor
    059 * @since 4.0
    060 */
    061public class SequencesComparator<T> {
    062
    063    /**
    064     * This class is a simple placeholder to hold the end part of a path
    065     * under construction in a {@link SequencesComparator SequencesComparator}.
    066     */
    067    private static final class Snake {
    068
    069        /** Start index. */
    070        private final int start;
    071
    072        /** End index. */
    073        private final int end;
    074
    075        /** Diagonal number. */
    076        private final int diag;
    077
    078        /**
    079         * Simple constructor. Creates a new instance of Snake with specified indices.
    080         *
    081         * @param start  start index of the snake
    082         * @param end  end index of the snake
    083         * @param diag  diagonal number
    084         */
    085        Snake(final int start, final int end, final int diag) {
    086            this.start = start;
    087            this.end   = end;
    088            this.diag  = diag;
    089        }
    090
    091        /**
    092         * Gets the diagonal number of the snake.
    093         *
    094         * @return diagonal number of the snake
    095         */
    096        public int getDiag() {
    097            return diag;
    098        }
    099
    100        /**
    101         * Gets the end index of the snake.
    102         *
    103         * @return end index of the snake
    104         */
    105        public int getEnd() {
    106            return end;
    107        }
    108
    109        /**
    110         * Gets the start index of the snake.
    111         *
    112         * @return start index of the snake
    113         */
    114        public int getStart() {
    115            return start;
    116        }
    117    }
    118
    119    /** First sequence. */
    120    private final List<T> sequence1;
    121
    122    /** Second sequence. */
    123    private final List<T> sequence2;
    124
    125    /** The equator used for testing object equality. */
    126    private final Equator<? super T> equator;
    127
    128    /** Temporary variables. */
    129    private final int[] vDown;
    130
    131    private final int[] vUp;
    132
    133    /**
    134     * Simple constructor.
    135     * <p>
    136     * Creates a new instance of SequencesComparator using a {@link DefaultEquator}.
    137     * <p>
    138     * It is <em>guaranteed</em> that the comparisons will always be done as
    139     * {@code o1.equals(o2)} where {@code o1} belongs to the first
    140     * sequence and {@code o2} belongs to the second sequence. This can be
    141     * important if subclassing is used for some elements in the first sequence
    142     * and the {@code equals} method is specialized.
    143     *
    144     * @param sequence1  first sequence to be compared
    145     * @param sequence2  second sequence to be compared
    146     */
    147    public SequencesComparator(final List<T> sequence1, final List<T> sequence2) {
    148        this(sequence1, sequence2, DefaultEquator.defaultEquator());
    149    }
    150
    151    /**
    152     * Simple constructor.
    153     * <p>
    154     * Creates a new instance of SequencesComparator with a custom {@link Equator}.
    155     * <p>
    156     * It is <em>guaranteed</em> that the comparisons will always be done as
    157     * {@code Equator.equate(o1, o2)} where {@code o1} belongs to the first
    158     * sequence and {@code o2} belongs to the second sequence.
    159     *
    160     * @param sequence1  first sequence to be compared
    161     * @param sequence2  second sequence to be compared
    162     * @param equator  The equator to use for testing object equality
    163     */
    164    public SequencesComparator(final List<T> sequence1, final List<T> sequence2, final Equator<? super T> equator) {
    165        this.sequence1 = sequence1;
    166        this.sequence2 = sequence2;
    167        this.equator = equator;
    168
    169        final int size = sequence1.size() + sequence2.size() + 2;
    170        vDown = new int[size];
    171        vUp   = new int[size];
    172    }
    173
    174    /**
    175     * Build an edit script.
    176     *
    177     * @param start1  The start of the first sequence to be compared
    178     * @param end1  The end of the first sequence to be compared
    179     * @param start2  The start of the second sequence to be compared
    180     * @param end2  The end of the second sequence to be compared
    181     * @param script The edited script
    182     */
    183    private void buildScript(final int start1, final int end1, final int start2, final int end2,
    184                             final EditScript<T> script) {
    185
    186        final Snake middle = getMiddleSnake(start1, end1, start2, end2);
    187
    188        if (middle == null
    189                || middle.getStart() == end1 && middle.getDiag() == end1 - end2
    190                || middle.getEnd() == start1 && middle.getDiag() == start1 - start2) {
    191
    192            int i = start1;
    193            int j = start2;
    194            while (i < end1 || j < end2) {
    195                if (i < end1 && j < end2 && equator.equate(sequence1.get(i), sequence2.get(j))) {
    196                    script.append(new KeepCommand<>(sequence1.get(i)));
    197                    ++i;
    198                    ++j;
    199                } else if (end1 - start1 > end2 - start2) {
    200                    script.append(new DeleteCommand<>(sequence1.get(i)));
    201                    ++i;
    202                } else {
    203                    script.append(new InsertCommand<>(sequence2.get(j)));
    204                    ++j;
    205                }
    206            }
    207
    208        } else {
    209
    210            buildScript(start1, middle.getStart(),
    211                        start2, middle.getStart() - middle.getDiag(),
    212                        script);
    213            for (int i = middle.getStart(); i < middle.getEnd(); ++i) {
    214                script.append(new KeepCommand<>(sequence1.get(i)));
    215            }
    216            buildScript(middle.getEnd(), end1,
    217                        middle.getEnd() - middle.getDiag(), end2,
    218                        script);
    219        }
    220    }
    221
    222    /**
    223     * Build a snake.
    224     *
    225     * @param start  The value of the start of the snake
    226     * @param diag  The value of the diagonal of the snake
    227     * @param end1  The value of the end of the first sequence to be compared
    228     * @param end2  The value of the end of the second sequence to be compared
    229     * @return The snake built
    230     */
    231    private Snake buildSnake(final int start, final int diag, final int end1, final int end2) {
    232        int end = start;
    233        while (end - diag < end2
    234                && end < end1
    235                && equator.equate(sequence1.get(end), sequence2.get(end - diag))) {
    236            ++end;
    237        }
    238        return new Snake(start, end, diag);
    239    }
    240
    241    /**
    242     * Gets the middle snake corresponding to two subsequences of the
    243     * main sequences.
    244     * <p>
    245     * The snake is found using the MYERS Algorithm (this algorithm has
    246     * also been implemented in the GNU diff program). This algorithm is
    247     * explained in Eugene Myers article:
    248     * <a href="https://web.archive.org/web/20040719035900/http%3A//www.cs.arizona.edu/people/gene/PAPERS/diff.ps">
    249     * An O(ND) Difference Algorithm and Its Variations</a>.
    250     *
    251     * @param start1  The start of the first sequence to be compared
    252     * @param end1  The end of the first sequence to be compared
    253     * @param start2  The start of the second sequence to be compared
    254     * @param end2  The end of the second sequence to be compared
    255     * @return The middle snake
    256     */
    257    private Snake getMiddleSnake(final int start1, final int end1, final int start2, final int end2) {
    258        // Myers Algorithm
    259        // Initializations
    260        final int m = end1 - start1;
    261        final int n = end2 - start2;
    262        if (m == 0 || n == 0) {
    263            return null;
    264        }
    265
    266        final int delta = m - n;
    267        final int sum = n + m;
    268        final int offset = (sum % 2 == 0 ? sum : sum + 1) / 2;
    269        vDown[1 + offset] = start1;
    270        vUp[1 + offset] = end1 + 1;
    271
    272        for (int d = 0; d <= offset; ++d) {
    273            // Down
    274            for (int k = -d; k <= d; k += 2) {
    275                // First step
    276
    277                final int i = k + offset;
    278                if (k == -d || k != d && vDown[i - 1] < vDown[i + 1]) {
    279                    vDown[i] = vDown[i + 1];
    280                } else {
    281                    vDown[i] = vDown[i - 1] + 1;
    282                }
    283
    284                int x = vDown[i];
    285                int y = x - start1 + start2 - k;
    286
    287                while (x < end1 && y < end2 && equator.equate(sequence1.get(x), sequence2.get(y))) {
    288                    vDown[i] = ++x;
    289                    ++y;
    290                }
    291                // Second step
    292                if (delta % 2 != 0 && delta - d <= k && k <= delta + d && vUp[i - delta] <= vDown[i]) { // NOPMD
    293                    return buildSnake(vUp[i - delta], k + start1 - start2, end1, end2);
    294                }
    295            }
    296
    297            // Up
    298            for (int k = delta - d; k <= delta + d; k += 2) {
    299                // First step
    300                final int i = k + offset - delta;
    301                if (k == delta - d || k != delta + d && vUp[i + 1] <= vUp[i - 1]) {
    302                    vUp[i] = vUp[i + 1] - 1;
    303                } else {
    304                    vUp[i] = vUp[i - 1];
    305                }
    306
    307                int x = vUp[i] - 1;
    308                int y = x - start1 + start2 - k;
    309                while (x >= start1 && y >= start2 && equator.equate(sequence1.get(x), sequence2.get(y))) {
    310                    vUp[i] = x--;
    311                    y--;
    312                }
    313                // Second step
    314                if (delta % 2 == 0 && -d <= k && k <= d && vUp[i] <= vDown[i + delta]) { // NOPMD
    315                    return buildSnake(vUp[i], k + start1 - start2, end1, end2);
    316                }
    317            }
    318        }
    319
    320        // this should not happen
    321        throw new IllegalStateException("Internal Error");
    322    }
    323
    324    /**
    325     * Gets the {@link EditScript} object.
    326     * <p>
    327     * It is guaranteed that the objects embedded in the {@link InsertCommand
    328     * insert commands} come from the second sequence and that the objects
    329     * embedded in either the {@link DeleteCommand delete commands} or
    330     * {@link KeepCommand keep commands} come from the first sequence. This can
    331     * be important if subclassing is used for some elements in the first
    332     * sequence and the {@code equals} method is specialized.
    333     *
    334     * @return The edit script resulting from the comparison of the two
    335     *         sequences
    336     */
    337    public EditScript<T> getScript() {
    338        final EditScript<T> script = new EditScript<>();
    339        buildScript(0, sequence1.size(), 0, sequence2.size(), script);
    340        return script;
    341    }
    342}