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