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