001/* 002 * ==================================================================== 003 * 004 * The Apache Software License, Version 1.1 005 * 006 * Copyright (c) 1999-2003 The Apache Software Foundation. All rights 007 * 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.myers; 059 060import org.apache.wicket.util.diff.Chunk; 061import org.apache.wicket.util.diff.Delta; 062import org.apache.wicket.util.diff.Diff; 063import org.apache.wicket.util.diff.DiffAlgorithm; 064import org.apache.wicket.util.diff.DifferentiationFailedException; 065import org.apache.wicket.util.diff.Revision; 066 067 068/** 069 * A clean-room implementation of <a href="http://www.cs.arizona.edu/people/gene/"> Eugene Myers</a> 070 * differencing algorithm. 071 * <p> 072 * See the paper at <a href="http://www.cs.arizona.edu/people/gene/PAPERS/diff.ps"> 073 * http://www.cs.arizona.edu/people/gene/PAPERS/diff.ps</a> 074 * 075 * @version $Revision: 1.1 $ $Date: 2006/03/12 00:24:21 $ 076 * @author <a href="mailto:juanco@suigeneris.org">Juanco Anez</a> 077 * @see Delta 078 * @see Revision 079 * @see Diff 080 */ 081public class MyersDiff implements DiffAlgorithm 082{ 083 /** 084 * Constructs an instance of the Myers differencing algorithm. 085 */ 086 public MyersDiff() 087 { 088 } 089 090 /** 091 * {@inheritDoc} 092 */ 093 @Override 094 public Revision diff(final Object[] orig, final Object[] rev) 095 throws DifferentiationFailedException 096 { 097 PathNode path = buildPath(orig, rev); 098 return buildRevision(path, orig, rev); 099 } 100 101 /** 102 * Computes the minimum diffpath that expresses de differences between the original and revised 103 * sequences, according to Gene Myers differencing algorithm. 104 * 105 * @param orig 106 * The original sequence. 107 * @param rev 108 * The revised sequence. 109 * @return A minimum {@link PathNode Path} across the differences graph. 110 * @throws DifferentiationFailedException 111 * if a diff path could not be found. 112 */ 113 public static PathNode buildPath(final Object[] orig, final Object[] rev) 114 throws DifferentiationFailedException 115 { 116 if (orig == null) 117 { 118 throw new IllegalArgumentException("original sequence is null"); 119 } 120 if (rev == null) 121 { 122 throw new IllegalArgumentException("revised sequence is null"); 123 } 124 125 // these are local constants 126 final int N = orig.length; 127 final int M = rev.length; 128 129 final int MAX = N + M + 1; 130 final int size = 1 + 2 * MAX; 131 final int middle = (size + 1) / 2; 132 final PathNode diagonal[] = new PathNode[size]; 133 134 diagonal[middle + 1] = new Snake(0, -1, null); 135 for (int d = 0; d < MAX; d++) 136 { 137 for (int k = -d; k <= d; k += 2) 138 { 139 final int kmiddle = middle + k; 140 final int kplus = kmiddle + 1; 141 final int kminus = kmiddle - 1; 142 PathNode prev = null; 143 144 int i; 145 if ((k == -d) || ((k != d) && (diagonal[kminus].i < diagonal[kplus].i))) 146 { 147 i = diagonal[kplus].i; 148 prev = diagonal[kplus]; 149 } 150 else 151 { 152 i = diagonal[kminus].i + 1; 153 prev = diagonal[kminus]; 154 } 155 156 diagonal[kminus] = null; // no longer used 157 158 int j = i - k; 159 160 PathNode node = new DiffNode(i, j, prev); 161 162 // orig and rev are zero-based 163 // but the algorithm is one-based 164 // that's why there's no +1 when indexing the sequences 165 while ((i < N) && (j < M) && orig[i].equals(rev[j])) 166 { 167 i++; 168 j++; 169 } 170 if (i > node.i) 171 { 172 node = new Snake(i, j, node); 173 } 174 175 diagonal[kmiddle] = node; 176 177 if ((i >= N) && (j >= M)) 178 { 179 return diagonal[kmiddle]; 180 } 181 } 182 diagonal[middle + d - 1] = null; 183 184 } 185 // According to Myers, this cannot happen 186 throw new DifferentiationFailedException("could not find a diff path"); 187 } 188 189 /** 190 * Constructs a {@link Revision} from a difference path. 191 * 192 * @param path 193 * The path. 194 * @param orig 195 * The original sequence. 196 * @param rev 197 * The revised sequence. 198 * @return A {@link Revision} script corresponding to the path. 199 */ 200 public static Revision buildRevision(PathNode path, final Object[] orig, final Object[] rev) 201 { 202 if (path == null) 203 { 204 throw new IllegalArgumentException("path is null"); 205 } 206 if (orig == null) 207 { 208 throw new IllegalArgumentException("original sequence is null"); 209 } 210 if (rev == null) 211 { 212 throw new IllegalArgumentException("revised sequence is null"); 213 } 214 215 Revision revision = new Revision(); 216 if (path.isSnake()) 217 { 218 path = path.prev; 219 } 220 while ((path != null) && (path.prev != null) && (path.prev.j >= 0)) 221 { 222 if (path.isSnake()) 223 { 224 throw new IllegalStateException("bad diffpath: found snake when looking for diff"); 225 } 226 int i = path.i; 227 int j = path.j; 228 229 path = path.prev; 230 int ianchor = path.i; 231 int janchor = path.j; 232 233 Delta delta = Delta.newDelta(new Chunk(orig, ianchor, i - ianchor), new Chunk(rev, 234 janchor, j - janchor)); 235 revision.insertDelta(delta); 236 if (path.isSnake()) 237 { 238 path = path.prev; 239 } 240 } 241 return revision; 242 } 243 244}