001: /*
002: * ====================================================================
003: *
004: * The Apache Software License, Version 1.1
005: *
006: * Copyright (c) 1999-2003 The Apache Software Foundation.
007: * All rights reserved.
008: *
009: * Redistribution and use in source and binary forms, with or without
010: * modification, are permitted provided that the following conditions
011: * are met:
012: *
013: * 1. Redistributions of source code must retain the above copyright
014: * notice, this list of conditions and the following disclaimer.
015: *
016: * 2. Redistributions in binary form must reproduce the above copyright
017: * notice, this list of conditions and the following disclaimer in
018: * the documentation and/or other materials provided with the
019: * distribution.
020: *
021: * 3. The end-user documentation included with the redistribution, if
022: * any, must include the following acknowledgement:
023: * "This product includes software developed by the
024: * Apache Software Foundation (http://www.apache.org/)."
025: * Alternately, this acknowledgement may appear in the software itself,
026: * if and wherever such third-party acknowledgements normally appear.
027: *
028: * 4. The names "The Jakarta Project", "Commons", and "Apache Software
029: * Foundation" must not be used to endorse or promote products derived
030: * from this software without prior written permission. For written
031: * permission, please contact apache@apache.org.
032: *
033: * 5. Products derived from this software may not be called "Apache"
034: * nor may "Apache" appear in their names without prior written
035: * permission of the Apache Software Foundation.
036: *
037: * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
038: * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
039: * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
040: * DISCLAIMED. IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
041: * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
042: * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
043: * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
044: * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
045: * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
046: * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
047: * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
048: * SUCH DAMAGE.
049: * ====================================================================
050: *
051: * This software consists of voluntary contributions made by many
052: * individuals on behalf of the Apache Software Foundation. For more
053: * information on the Apache Software Foundation, please see
054: * <http://www.apache.org/>.
055: *
056: */
057:
058: package wicket.util.diff;
059:
060: import java.util.ArrayList;
061: import java.util.Arrays;
062: import java.util.Collections;
063: import java.util.List;
064: import java.util.Random;
065:
066: import wicket.util.diff.myers.MyersDiff;
067:
068: /**
069: * Implements a differencing engine that works on arrays of
070: * {@link Object Object}.
071: *
072: * <p>
073: * Within this library, the word <i>text</i> means a unit of information
074: * subject to version control.
075: *
076: * <p>
077: * Text is represented as <code>Object[]</code> because the diff engine is
078: * capable of handling more than plain ascci. In fact, arrays of any type that
079: * implements {@link java.lang.Object#hashCode hashCode()} and
080: * {@link java.lang.Object#equals equals()} correctly can be subject to
081: * differencing using this library.
082: * </p>
083: *
084: * <p>
085: * This library provides a framework in which different differencing algorithms
086: * may be used. If no algorithm is specififed, a default algorithm is used.
087: * </p>
088: *
089: * @version $Revision: 1.1 $ $Date: 2006/03/12 00:24:21 $
090: * @author <a href="mailto:juanco@suigeneris.org">Juanco Anez</a>
091: * @see Delta
092: * @see DiffAlgorithm
093: *
094: * modifications:
095: *
096: * 27 Apr 2003 bwm
097: *
098: * Added some comments whilst trying to figure out the algorithm
099: *
100: * 03 May 2003 bwm
101: *
102: * Factored out the algorithm implementation into a separate difference
103: * algorithm class to allow pluggable algorithms.
104: */
105:
106: public class Diff extends ToString {
107: /** The standard line separator. */
108: public static final String NL = System
109: .getProperty("line.separator");
110:
111: /** The line separator to use in RCS format output. */
112: public static final String RCS_EOL = "\n";
113:
114: /** The original sequence. */
115: protected final Object[] orig;
116:
117: /** The differencing algorithm to use. */
118: protected DiffAlgorithm algorithm;
119:
120: /**
121: * Create a differencing object using the default algorithm
122: * @param original
123: *
124: * @param the
125: * original text that will be compared
126: */
127: public Diff(Object[] original) {
128: this (original, null);
129: }
130:
131: /**
132: * Create a differencing object using the given algorithm
133: * @param original
134: *
135: * @param o
136: * the original text which will be compared against
137: * @param algorithm
138: * the difference algorithm to use.
139: */
140: public Diff(Object[] original, DiffAlgorithm algorithm) {
141: if (original == null) {
142: throw new IllegalArgumentException();
143: }
144:
145: this .orig = original;
146: if (algorithm != null)
147: this .algorithm = algorithm;
148: else
149: this .algorithm = defaultAlgorithm();
150: }
151:
152: protected DiffAlgorithm defaultAlgorithm() {
153: return new MyersDiff();
154: }
155:
156: /**
157: * compute the difference between an original and a revision.
158: *
159: * @param orig
160: * the original
161: * @param rev
162: * the revision to compare with the original.
163: * @return a Revision describing the differences
164: * @throws DifferentiationFailedException
165: */
166: public static Revision diff(Object[] orig, Object[] rev)
167: throws DifferentiationFailedException {
168: if (orig == null || rev == null) {
169: throw new IllegalArgumentException();
170: }
171:
172: return diff(orig, rev, null);
173: }
174:
175: /**
176: * compute the difference between an original and a revision.
177: *
178: * @param orig
179: * the original
180: * @param rev
181: * the revision to compare with the original.
182: * @param algorithm
183: * the difference algorithm to use
184: * @return a Revision describing the differences
185: * @throws DifferentiationFailedException
186: */
187: public static Revision diff(Object[] orig, Object[] rev,
188: DiffAlgorithm algorithm)
189: throws DifferentiationFailedException {
190: if (orig == null || rev == null) {
191: throw new IllegalArgumentException();
192: }
193:
194: return new Diff(orig, algorithm).diff(rev);
195: }
196:
197: /**
198: * compute the difference between the original and a revision.
199: *
200: * @param rev
201: * the revision to compare with the original.
202: * @return a Revision describing the differences
203: * @throws DifferentiationFailedException
204: */
205: public Revision diff(Object[] rev)
206: throws DifferentiationFailedException {
207: if (orig.length == 0 && rev.length == 0)
208: return new Revision();
209: else
210: return algorithm.diff(orig, rev);
211: }
212:
213: /**
214: * Compares the two input sequences.
215: *
216: * @param orig
217: * The original sequence.
218: * @param rev
219: * The revised sequence.
220: * @return true if the sequences are identical. False otherwise.
221: */
222: public static boolean compare(Object[] orig, Object[] rev) {
223: if (orig.length != rev.length) {
224: return false;
225: } else {
226: for (int i = 0; i < orig.length; i++) {
227: if (!orig[i].equals(rev[i])) {
228: return false;
229: }
230: }
231: return true;
232: }
233: }
234:
235: /**
236: * Converts an array of {@link Object Object} to a string using
237: * {@link Diff#NL Diff.NL} as the line separator.
238: *
239: * @param o
240: * the array of objects.
241: * @return String
242: */
243: public static String arrayToString(Object[] o) {
244: return arrayToString(o, Diff.NL);
245: }
246:
247: /**
248: * Edits all of the items in the input sequence.
249: *
250: * @param text
251: * The input sequence.
252: * @return A sequence of the same length with all the lines differing from
253: * the corresponding ones in the input.
254: */
255: public static Object[] editAll(Object[] text) {
256: Object[] result = new String[text.length];
257:
258: for (int i = 0; i < text.length; i++)
259: result[i] = text[i] + " <edited>";
260:
261: return result;
262: }
263:
264: /**
265: * Performs random edits on the input sequence. Useful for testing.
266: *
267: * @param text
268: * The input sequence.
269: * @return The sequence with random edits performed.
270: */
271: public static Object[] randomEdit(Object[] text) {
272: return randomEdit(text, text.length);
273: }
274:
275: /**
276: * Performs random edits on the input sequence. Useful for testing.
277: *
278: * @param text
279: * The input sequence.
280: * @param seed
281: * A seed value for the randomizer.
282: * @return The sequence with random edits performed.
283: */
284: public static Object[] randomEdit(Object[] text, long seed) {
285: List result = new ArrayList(Arrays.asList(text));
286: Random r = new Random(seed);
287: int nops = r.nextInt(10);
288: for (int i = 0; i < nops; i++) {
289: boolean del = r.nextBoolean();
290: int pos = r.nextInt(result.size() + 1);
291: int len = Math.min(result.size() - pos, 1 + r.nextInt(4));
292: if (del && result.size() > 0) { // delete
293: result.subList(pos, pos + len).clear();
294: } else {
295: for (int k = 0; k < len; k++, pos++) {
296: result.add(pos, "[" + i + "] random edit[" + i
297: + "][" + i + "]");
298: }
299: }
300: }
301: return result.toArray();
302: }
303:
304: /**
305: * Shuffles around the items in the input sequence.
306: *
307: * @param text
308: * The input sequence.
309: * @return The shuffled sequence.
310: */
311: public static Object[] shuffle(Object[] text) {
312: return shuffle(text, text.length);
313: }
314:
315: /**
316: * Shuffles around the items in the input sequence.
317: *
318: * @param text
319: * The input sequence.
320: * @param seed
321: * A seed value for randomizing the suffle.
322: * @return The shuffled sequence.
323: */
324: public static Object[] shuffle(Object[] text, long seed) {
325: List result = new ArrayList(Arrays.asList(text));
326: Collections.shuffle(result);
327: return result.toArray();
328: }
329:
330: /**
331: * Generate a random sequence of the given size.
332: * @param size
333: *
334: * @param The
335: * size of the sequence to generate.
336: * @return The generated sequence.
337: */
338: public static Object[] randomSequence(int size) {
339: return randomSequence(size, size);
340: }
341:
342: /**
343: * Generate a random sequence of the given size.
344: * @param size
345: * The size of the sequence to generate.
346: * @param seed
347: * A seed value for randomizing the generation.
348: * @return The generated sequence.
349: */
350: public static Object[] randomSequence(int size, long seed) {
351: Integer[] result = new Integer[size];
352: Random r = new Random(seed);
353: for (int i = 0; i < result.length; i++) {
354: result[i] = new Integer(r.nextInt(size));
355: }
356: return result;
357: }
358:
359: }
|