1 /*
2 * Licensed to the Apache Software Foundation (ASF) under one or more
3 * contributor license agreements. See the NOTICE file distributed with
4 * this work for additional information regarding copyright ownership.
5 * The ASF licenses this file to You under the Apache License, Version 2.0
6 * (the "License"); you may not use this file except in compliance with
7 * the License. You may obtain a copy of the License at
8 *
9 * https://www.apache.org/licenses/LICENSE-2.0
10 *
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
16 */
17 package org.apache.commons.collections4.sequence;
18
19 import java.util.List;
20
21 import org.apache.commons.collections4.Equator;
22 import org.apache.commons.collections4.functors.DefaultEquator;
23
24 /**
25 * This class allows to compare two objects sequences.
26 * <p>
27 * The two sequences can hold any object type, as only the {@code equals}
28 * method is used to compare the elements of the sequences. It is guaranteed
29 * that the comparisons will always be done as {@code o1.equals(o2)} where
30 * {@code o1} belongs to the first sequence and {@code o2} belongs to
31 * the second sequence. This can be important if subclassing is used for some
32 * elements in the first sequence and the {@code equals} method is
33 * specialized.
34 * </p>
35 * <p>
36 * Comparison can be seen from two points of view: either as giving the smallest
37 * modification allowing to transform the first sequence into the second one, or
38 * as giving the longest sequence which is a subsequence of both initial
39 * sequences. The {@code equals} method is used to compare objects, so any
40 * object can be put into sequences. Modifications include deleting, inserting
41 * or keeping one object, starting from the beginning of the first sequence.
42 * </p>
43 * <p>
44 * This class implements the comparison algorithm, which is the very efficient
45 * algorithm from Eugene W. Myers
46 * <a href="https://www.cis.upenn.edu/~bcpierce/courses/dd/papers/diff.ps">
47 * An O(ND) Difference Algorithm and Its Variations</a>. This algorithm produces
48 * the shortest possible
49 * {@link EditScript edit script}
50 * containing all the
51 * {@link EditCommand commands}
52 * needed to transform the first sequence into the second one.
53 * </p>
54 *
55 * @param <T> The type of elements in the lists.
56 * @see EditScript
57 * @see EditCommand
58 * @see CommandVisitor
59 * @since 4.0
60 */
61 public class SequencesComparator<T> {
62
63 /**
64 * This class is a simple placeholder to hold the end part of a path
65 * under construction in a {@link SequencesComparator SequencesComparator}.
66 */
67 private static final class Snake {
68
69 /** Start index. */
70 private final int start;
71
72 /** End index. */
73 private final int end;
74
75 /** Diagonal number. */
76 private final int diag;
77
78 /**
79 * Simple constructor. Creates a new instance of Snake with specified indices.
80 *
81 * @param start start index of the snake
82 * @param end end index of the snake
83 * @param diag diagonal number
84 */
85 Snake(final int start, final int end, final int diag) {
86 this.start = start;
87 this.end = end;
88 this.diag = diag;
89 }
90
91 /**
92 * Gets the diagonal number of the snake.
93 *
94 * @return diagonal number of the snake
95 */
96 public int getDiag() {
97 return diag;
98 }
99
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 }