    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 *      http://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</code>
    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)</code> where
    030 * <code>o1</code> belongs to the first sequence and <code>o2</code> 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</code> 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</code> 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="http://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 * @see EditScript
    056 * @see EditCommand
    057 * @see CommandVisitor
    058 *
    059 * @since 4.0
    060 */
    061public class SequencesComparator<T> {
    062
    063    /** First sequence. */
    064    private final List<T> sequence1;
    065
    066    /** Second sequence. */
    067    private final List<T> sequence2;
    068
    069    /** The equator used for testing object equality. */
    070    private final Equator<? super T> equator;
    071
    072    /** Temporary variables. */
    073    private final int[] vDown;
    074    private final int[] vUp;
    075
    076    /**
    077     * Simple constructor.
    078     * <p>
    079     * Creates a new instance of SequencesComparator using a {@link DefaultEquator}.
    080     * <p>
    081     * It is <em>guaranteed</em> that the comparisons will always be done as
    082     * <code>o1.equals(o2)</code> where <code>o1</code> belongs to the first
    083     * sequence and <code>o2</code> belongs to the second sequence. This can be
    084     * important if subclassing is used for some elements in the first sequence
    085     * and the <code>equals</code> method is specialized.
    086     *
    087     * @param sequence1  first sequence to be compared
    088     * @param sequence2  second sequence to be compared
    089     */
    090    public SequencesComparator(final List<T> sequence1, final List<T> sequence2) {
    091        this(sequence1, sequence2, DefaultEquator.defaultEquator());
    092    }
    093
    094    /**
    095     * Simple constructor.
    096     * <p>
    097     * Creates a new instance of SequencesComparator with a custom {@link Equator}.
    098     * <p>
    099     * It is <em>guaranteed</em> that the comparisons will always be done as
    100     * <code>Equator.equate(o1, o2)</code> where <code>o1</code> belongs to the first
    101     * sequence and <code>o2</code> belongs to the second sequence.
    102     *
    103     * @param sequence1  first sequence to be compared
    104     * @param sequence2  second sequence to be compared
    105     * @param equator  the equator to use for testing object equality
    106     */
    107    public SequencesComparator(final List<T> sequence1, final List<T> sequence2, final Equator<? super T> equator) {
    108        this.sequence1 = sequence1;
    109        this.sequence2 = sequence2;
    110        this.equator = equator;
    111
    112        final int size = sequence1.size() + sequence2.size() + 2;
    113        vDown = new int[size];
    114        vUp   = new int[size];
    115    }
    116
    117    /**
    118     * Get the {@link EditScript} object.
    119     * <p>
    120     * It is guaranteed that the objects embedded in the {@link InsertCommand
    121     * insert commands} come from the second sequence and that the objects
    122     * embedded in either the {@link DeleteCommand delete commands} or
    123     * {@link KeepCommand keep commands} come from the first sequence. This can
    124     * be important if subclassing is used for some elements in the first
    125     * sequence and the <code>equals</code> method is specialized.
    126     *
    127     * @return the edit script resulting from the comparison of the two
    128     *         sequences
    129     */
    130    public EditScript<T> getScript() {
    131        final EditScript<T> script = new EditScript<>();
    132        buildScript(0, sequence1.size(), 0, sequence2.size(), script);
    133        return script;
    134    }
    135
    136    /**
    137     * Build a snake.
    138     *
    139     * @param start  the value of the start of the snake
    140     * @param diag  the value of the diagonal of the snake
    141     * @param end1  the value of the end of the first sequence to be compared
    142     * @param end2  the value of the end of the second sequence to be compared
    143     * @return the snake built
    144     */
    145    private Snake buildSnake(final int start, final int diag, final int end1, final int end2) {
    146        int end = start;
    147        while (end - diag < end2
    148                && end < end1
    149                && equator.equate(sequence1.get(end), sequence2.get(end - diag))) {
    150            ++end;
    151        }
    152        return new Snake(start, end, diag);
    153    }
    154
    155    /**
    156     * Get the middle snake corresponding to two subsequences of the
    157     * main sequences.
    158     * <p>
    159     * The snake is found using the MYERS Algorithm (this algorithms has
    160     * also been implemented in the GNU diff program). This algorithm is
    161     * explained in Eugene Myers article:
    162     * <a href="http://www.cs.arizona.edu/people/gene/PAPERS/diff.ps">
    163     * An O(ND) Difference Algorithm and Its Variations</a>.
    164     *
    165     * @param start1  the begin of the first sequence to be compared
    166     * @param end1  the end of the first sequence to be compared
    167     * @param start2  the begin of the second sequence to be compared
    168     * @param end2  the end of the second sequence to be compared
    169     * @return the middle snake
    170     */
    171    private Snake getMiddleSnake(final int start1, final int end1, final int start2, final int end2) {
    172        // Myers Algorithm
    173        // Initialisations
    174        final int m = end1 - start1;
    175        final int n = end2 - start2;
    176        if (m == 0 || n == 0) {
    177            return null;
    178        }
    179
    180        final int delta  = m - n;
    181        final int sum    = n + m;
    182        final int offset = (sum % 2 == 0 ? sum : sum + 1) / 2;
    183        vDown[1+offset] = start1;
    184        vUp[1+offset]   = end1 + 1;
    185
    186        for (int d = 0; d <= offset ; ++d) {
    187            // Down
    188            for (int k = -d; k <= d; k += 2) {
    189                // First step
    190
    191                final int i = k + offset;
    192                if (k == -d || k != d && vDown[i-1] < vDown[i+1]) {
    193                    vDown[i] = vDown[i+1];
    194                } else {
    195                    vDown[i] = vDown[i-1] + 1;
    196                }
    197
    198                int x = vDown[i];
    199                int y = x - start1 + start2 - k;
    200
    201                while (x < end1 && y < end2 && equator.equate(sequence1.get(x), sequence2.get(y))) {
    202                    vDown[i] = ++x;
    203                    ++y;
    204                }
    205                // Second step
    206                if (delta % 2 != 0 && delta - d <= k && k <= delta + d) {
    207                    if (vUp[i-delta] <= vDown[i]) { // NOPMD
    208                        return buildSnake(vUp[i-delta], k + start1 - start2, end1, end2);
    209                    }
    210                }
    211            }
    212
    213            // Up
    214            for (int k = delta - d; k <= delta + d; k += 2) {
    215                // First step
    216                final int i = k + offset - delta;
    217                if (k == delta - d
    218                        || k != delta + d && vUp[i+1] <= vUp[i-1]) {
    219                    vUp[i] = vUp[i+1] - 1;
    220                } else {
    221                    vUp[i] = vUp[i-1];
    222                }
    223
    224                int x = vUp[i] - 1;
    225                int y = x - start1 + start2 - k;
    226                while (x >= start1 && y >= start2
    227                        && equator.equate(sequence1.get(x), sequence2.get(y))) {
    228                    vUp[i] = x--;
    229                    y--;
    230                }
    231                // Second step
    232                if (delta % 2 == 0 && -d <= k && k <= d ) {
    233                    if (vUp[i] <= vDown[i + delta]) { // NOPMD
    234                        return buildSnake(vUp[i], k + start1 - start2, end1, end2);
    235                    }
    236                }
    237            }
    238        }
    239
    240        // this should not happen
    241        throw new RuntimeException("Internal Error");
    242    }
    243
    244
    245    /**
    246     * Build an edit script.
    247     *
    248     * @param start1  the begin of the first sequence to be compared
    249     * @param end1  the end of the first sequence to be compared
    250     * @param start2  the begin of the second sequence to be compared
    251     * @param end2  the end of the second sequence to be compared
    252     * @param script the edited script
    253     */
    254    private void buildScript(final int start1, final int end1, final int start2, final int end2,
    255                             final EditScript<T> script) {
    256
    257        final Snake middle = getMiddleSnake(start1, end1, start2, end2);
    258
    259        if (middle == null
    260                || middle.getStart() == end1 && middle.getDiag() == end1 - end2
    261                || middle.getEnd() == start1 && middle.getDiag() == start1 - start2) {
    262
    263            int i = start1;
    264            int j = start2;
    265            while (i < end1 || j < end2) {
    266                if (i < end1 && j < end2 && equator.equate(sequence1.get(i), sequence2.get(j))) {
    267                    script.append(new KeepCommand<>(sequence1.get(i)));
    268                    ++i;
    269                    ++j;
    270                } else {
    271                    if (end1 - start1 > end2 - start2) {
    272                        script.append(new DeleteCommand<>(sequence1.get(i)));
    273                        ++i;
    274                    } else {
    275                        script.append(new InsertCommand<>(sequence2.get(j)));
    276                        ++j;
    277                    }
    278                }
    279            }
    280
    281        } else {
    282
    283            buildScript(start1, middle.getStart(),
    284                        start2, middle.getStart() - middle.getDiag(),
    285                        script);
    286            for (int i = middle.getStart(); i < middle.getEnd(); ++i) {
    287                script.append(new KeepCommand<>(sequence1.get(i)));
    288            }
    289            buildScript(middle.getEnd(), end1,
    290                        middle.getEnd() - middle.getDiag(), end2,
    291                        script);
    292        }
    293    }
    294
    295    /**
    296     * This class is a simple placeholder to hold the end part of a path
    297     * under construction in a {@link SequencesComparator SequencesComparator}.
    298     */
    299    private static class Snake {
    300
    301        /** Start index. */
    302        private final int start;
    303
    304        /** End index. */
    305        private final int end;
    306
    307        /** Diagonal number. */
    308        private final int diag;
    309
    310        /**
    311         * Simple constructor. Creates a new instance of Snake with specified indices.
    312         *
    313         * @param start  start index of the snake
    314         * @param end  end index of the snake
    315         * @param diag  diagonal number
    316         */
    317        public Snake(final int start, final int end, final int diag) {
    318            this.start = start;
    319            this.end   = end;
    320            this.diag  = diag;
    321        }
    322
    323        /**
    324         * Get the start index of the snake.
    325         *
    326         * @return start index of the snake
    327         */
    328        public int getStart() {
    329            return start;
    330        }
    331
    332        /**
    333         * Get the end index of the snake.
    334         *
    335         * @return end index of the snake
    336         */
    337        public int getEnd() {
    338            return end;
    339        }
    340
    341        /**
    342         * Get the diagonal number of the snake.
    343         *
    344         * @return diagonal number of the snake
    345         */
    346        public int getDiag() {
    347            return diag;
    348        }
    349    }
    350}