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 org.apache.commons.jrcs.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 org.apache.commons.jrcs.diff.myers.MyersDiff;
067: import org.apache.commons.jrcs.util.ToString;
068:
069: /**
070: * Implements a differencing engine that works on arrays of
071: * {@link Object Object}.
072: * <p>
073: * Within this library, the word <i>text</i> means a unit of information
074: * subject to version control.
075: * <p>
076: * Text is represented as <code>Object[]</code> because the diff engine is
077: * capable of handling more than plain ascci. In fact, arrays of any type that
078: * implements {@link java.lang.Object#hashCode hashCode()} and
079: * {@link java.lang.Object#equals equals()} correctly can be subject to
080: * differencing using this library.
081: * </p>
082: * <p>
083: * This library provides a framework in which different differencing algorithms
084: * may be used. If no algorithm is specififed, a default algorithm is used.
085: * </p>
086: *
087: * @version $Revision: 7756 $ $Date: 2006-04-12 18:30:19 +0100 (Wed, 12 Apr
088: * 2006) $
089: * @author <a href="mailto:juanco@suigeneris.org">Juanco Anez</a>
090: * @see Delta
091: * @see DiffAlgorithm modifications: 27 Apr 2003 bwm Added some comments whilst
092: * trying to figure out the algorithm 03 May 2003 bwm Factored out the
093: * algorithm implementation into a separate difference algorithm class to
094: * allow pluggable algorithms.
095: */
096:
097: public class Diff extends ToString {
098: /** The standard line separator. */
099: public static final String NL = System
100: .getProperty("line.separator");
101:
102: /** The line separator to use in RCS format output. */
103: public static final String RCS_EOL = "\n";
104:
105: /** The original sequence. */
106: protected final Object[] orig;
107:
108: /** The differencing algorithm to use. */
109: protected DiffAlgorithm algorithm;
110:
111: /**
112: * Create a differencing object using the default algorithm
113: *
114: * @param the
115: * original text that will be compared
116: */
117: public Diff(Object[] original) {
118: this (original, null);
119: }
120:
121: /**
122: * Create a differencing object using the given algorithm
123: *
124: * @param o
125: * the original text which will be compared against
126: * @param algorithm
127: * the difference algorithm to use.
128: */
129: public Diff(Object[] original, DiffAlgorithm algorithm) {
130: if (original == null) {
131: throw new IllegalArgumentException();
132: }
133:
134: this .orig = original;
135: if (algorithm != null)
136: this .algorithm = algorithm;
137: else
138: this .algorithm = defaultAlgorithm();
139: }
140:
141: protected DiffAlgorithm defaultAlgorithm() {
142: return new MyersDiff();
143: }
144:
145: /**
146: * compute the difference between an original and a revision.
147: *
148: * @param orig
149: * the original
150: * @param rev
151: * the revision to compare with the original.
152: * @return a Revision describing the differences
153: */
154: public static Revision diff(Object[] orig, Object[] rev)
155: throws DifferentiationFailedException {
156: if (orig == null || rev == null) {
157: throw new IllegalArgumentException();
158: }
159:
160: return diff(orig, rev, null);
161: }
162:
163: /**
164: * compute the difference between an original and a revision.
165: *
166: * @param orig
167: * the original
168: * @param rev
169: * the revision to compare with the original.
170: * @param algorithm
171: * the difference algorithm to use
172: * @return a Revision describing the differences
173: */
174: public static Revision diff(Object[] orig, Object[] rev,
175: DiffAlgorithm algorithm)
176: throws DifferentiationFailedException {
177: if (orig == null || rev == null) {
178: throw new IllegalArgumentException();
179: }
180:
181: return new Diff(orig, algorithm).diff(rev);
182: }
183:
184: /**
185: * compute the difference between the original and a revision.
186: *
187: * @param rev
188: * the revision to compare with the original.
189: * @return a Revision describing the differences
190: */
191: public Revision diff(Object[] rev)
192: throws DifferentiationFailedException {
193: if (orig.length == 0 && rev.length == 0)
194: return new Revision();
195: else
196: return algorithm.diff(orig, rev);
197: }
198:
199: /**
200: * Compares the two input sequences.
201: *
202: * @param orig
203: * The original sequence.
204: * @param rev
205: * The revised sequence.
206: * @return true if the sequences are identical. False otherwise.
207: */
208: public static boolean compare(Object[] orig, Object[] rev) {
209: if (orig.length != rev.length) {
210: return false;
211: } else {
212: for (int i = 0; i < orig.length; i++) {
213: if (!orig[i].equals(rev[i])) {
214: return false;
215: }
216: }
217: return true;
218: }
219: }
220:
221: /**
222: * Converts an array of {@link Object Object} to a string using
223: * {@link Diff#NL Diff.NL} as the line separator.
224: *
225: * @param o
226: * the array of objects.
227: */
228: public static String arrayToString(Object[] o) {
229: return arrayToString(o, Diff.NL);
230: }
231:
232: /**
233: * Edits all of the items in the input sequence.
234: *
235: * @param text
236: * The input sequence.
237: * @return A sequence of the same length with all the lines differing from
238: * the corresponding ones in the input.
239: */
240: public static Object[] editAll(Object[] text) {
241: Object[] result = new String[text.length];
242:
243: for (int i = 0; i < text.length; i++)
244: result[i] = text[i] + " <edited>";
245:
246: return result;
247: }
248:
249: /**
250: * Performs random edits on the input sequence. Useful for testing.
251: *
252: * @param text
253: * The input sequence.
254: * @return The sequence with random edits performed.
255: */
256: public static Object[] randomEdit(Object[] text) {
257: return randomEdit(text, text.length);
258: }
259:
260: /**
261: * Performs random edits on the input sequence. Useful for testing.
262: *
263: * @param text
264: * The input sequence.
265: * @param seed
266: * A seed value for the randomizer.
267: * @return The sequence with random edits performed.
268: */
269: public static Object[] randomEdit(Object[] text, long seed) {
270: List result = new ArrayList(Arrays.asList(text));
271: Random r = new Random(seed);
272: int nops = r.nextInt(10);
273: for (int i = 0; i < nops; i++) {
274: boolean del = r.nextBoolean();
275: int pos = r.nextInt(result.size() + 1);
276: int len = Math.min(result.size() - pos, 1 + r.nextInt(4));
277: if (del && result.size() > 0) { // delete
278: result.subList(pos, pos + len).clear();
279: } else {
280: for (int k = 0; k < len; k++, pos++) {
281: result.add(pos, "[" + i + "] random edit[" + i
282: + "][" + i + "]");
283: }
284: }
285: }
286: return result.toArray();
287: }
288:
289: /**
290: * Shuffles around the items in the input sequence.
291: *
292: * @param text
293: * The input sequence.
294: * @return The shuffled sequence.
295: */
296: public static Object[] shuffle(Object[] text) {
297: return shuffle(text, text.length);
298: }
299:
300: /**
301: * Shuffles around the items in the input sequence.
302: *
303: * @param text
304: * The input sequence.
305: * @param seed
306: * A seed value for randomizing the suffle.
307: * @return The shuffled sequence.
308: */
309: public static Object[] shuffle(Object[] text, long seed) {
310: List result = new ArrayList(Arrays.asList(text));
311: Collections.shuffle(result);
312: return result.toArray();
313: }
314:
315: /**
316: * Generate a random sequence of the given size.
317: *
318: * @param The
319: * size of the sequence to generate.
320: * @return The generated sequence.
321: */
322: public static Object[] randomSequence(int size) {
323: return randomSequence(size, size);
324: }
325:
326: /**
327: * Generate a random sequence of the given size.
328: *
329: * @param The
330: * size of the sequence to generate.
331: * @param seed
332: * A seed value for randomizing the generation.
333: * @return The generated sequence.
334: */
335: public static Object[] randomSequence(int size, long seed) {
336: Integer[] result = new Integer[size];
337: Random r = new Random(seed);
338: for (int i = 0; i < result.length; i++) {
339: result[i] = new Integer(r.nextInt(size));
340: }
341: return result;
342: }
343:
344: }
|