001: package JLibDiff;
002:
003: import java.lang.ref.Reference;
004: import java.util.Arrays;
005: import java.util.Vector;
006:
007: /**
008: * @author rmacgrogan
009: *
010: * To change this generated comment edit the template variable "typecomment":
011: * Window>Preferences>Java>Templates.
012: * To enable and disable the creation of type comments go to
013: * Window>Preferences>Java>Code Generation.
014: */
015: public class JRCSMyersAlgorithm implements DiffAlgorithm {
016:
017: public JRCSMyersAlgorithm() {
018: }
019:
020: /**
021: * @see JLibDiff.DiffAlgorithm#setEol(String)
022: */
023: public void setEol(String s) {
024: }
025:
026: /**
027: * @see JLibDiff.DiffAlgorithm#makeDiff(String[], String[])
028: */
029: public Vector makeDiff(String[] A, String[] B) {
030: JRCSMyersPathNode path = buildPath(A, B);
031: return buildRevision(path, A, B);
032: }
033:
034: /**
035: * Computes the minimum diffpath that expresses de differences
036: * between the original and revised sequences, according
037: * to Gene Myers differencing algorithm.
038: *
039: * @param orig The original sequence.
040: * @param rev The revised sequence.
041: * @return A minimum {@link JRCSMyersPathNode Path} accross the differences graph.
042: * @throws DifferentiationFailedException if a diff path could not be found.
043: */
044: public JRCSMyersPathNode buildPath(Object[] orig, Object[] rev) {
045: int n = orig.length;
046: int m = rev.length;
047:
048: JRCSMyersPathNode returnPath = null;
049:
050: int max = n + m + 1;
051: JRCSMyersPathNode diagonal[] = new JRCSMyersPathNode[1 + 2 * max];
052: int middle = (diagonal.length + 1) / 2;
053:
054: JRCSMyersPathNode path = null;
055:
056: int d = 0;
057: diagonal[middle + 1] = new JRCSMyersPathNode(0, -1);
058: outer: for (d = 0; d < max; d++) {
059: for (int k = -d; k <= d; k += 2) {
060: JRCSMyersPathNode prev = null;
061: int kmiddle = middle + k;
062: int kplus = kmiddle + 1;
063: int kminus = kmiddle - 1;
064:
065: int i;
066: if ((k == -d)
067: || (k != d && diagonal[kminus].i < diagonal[kplus].i)) {
068: i = diagonal[kplus].i;
069: prev = diagonal[kplus];
070: } else {
071: i = diagonal[kminus].i + 1;
072: prev = diagonal[kminus];
073: }
074: if (prev.i < 0 || prev.j < 0)
075: prev = null;
076:
077: int j = i - k;
078: while (i < n && j < m && orig[i].equals(rev[j])) {
079: i++;
080: j++;
081: }
082: diagonal[kmiddle] = new JRCSMyersPathNode(i, j, prev);
083: if (i >= n && j >= m) {
084: returnPath = diagonal[kmiddle];
085: break outer;
086: }
087: }
088: }
089: return returnPath;
090: }
091:
092: /**
093: * Constructs a {@link Revision} from a difference path.
094: *
095: * @param path The path.
096: * @param orig The original sequence.
097: * @param rev The revised sequence.
098: * @return A {@link Revision} script corresponding to the path.
099: * @throws DifferentiationFailedException if the {@link Revision} could
100: * not be built.
101: */
102: public Vector buildRevision(JRCSMyersPathNode path, Object[] orig,
103: Object[] rev) {
104: if (path == null)
105: throw new IllegalArgumentException("path is null");
106: if (orig == null)
107: throw new IllegalArgumentException(
108: "original sequence is null");
109: if (rev == null)
110: throw new IllegalArgumentException(
111: "revised sequence is null");
112:
113: Vector v = new Vector();
114: while (path != null && path.prev != null) {
115: int i = path.i;
116: int j = path.j;
117: while (i > 0 && j > 0 && i > path.prev.i && j > path.prev.j
118: && orig[i - 1].equals(rev[j - 1])) { // reverse snake
119: i--;
120: j--;
121: }
122:
123: int ia;
124: int ja;
125: do {
126: path = path.prev;
127: ia = path.i;
128: ja = path.j;
129: } while (path.prev != null
130: && (ia == path.prev.i || ja == path.prev.j)); // while no snake
131:
132: int origStartLine = i;
133: int origEndLine = ia;
134: int revStartLine = j;
135: int revEndLine = ja;
136: int numAdded = revStartLine - revEndLine;
137: int numDeleted = origStartLine - origEndLine;
138:
139: //System.out.println();
140: //
141: //System.out.println("revStartLine = " + revStartLine);
142: //System.out.println("revEndLine = " + revEndLine);
143: //System.out.println("origStartLine = " + origStartLine);
144: //System.out.println("origEndLine = " + origEndLine);
145: //System.out.println("numAdded = " + numAdded);
146: //System.out.println("numDeleted = " + numDeleted);
147:
148: Hunk newHunk = null;
149: if (numAdded > 0 && numDeleted <= 0) {
150: HunkAdd add = new HunkAdd();
151: add.ld1 = origEndLine;
152: add.ld2 = (revStartLine - numAdded) + 1;
153: add.lf2 = revStartLine;
154:
155: //System.out.println();
156: //for (int q = 0; q < rev.length; q++){
157: // System.out.println( q + " -- " + rev[q]);
158: //}
159:
160: Object[] added = new Object[numAdded];
161: System.arraycopy(rev, revEndLine, added, 0, numAdded);
162: add.b = new Vector(Arrays.asList(added));
163: newHunk = add;
164: } else if (numAdded <= 0 && numDeleted > 0) {
165: HunkDel del = new HunkDel();
166: del.ld1 = (revStartLine - numDeleted) + 1;
167: del.ld2 = origEndLine;
168: del.lf1 = revStartLine;
169: Object[] deleted = new Object[numDeleted];
170: System.arraycopy(orig, origEndLine, deleted, 0,
171: numDeleted);
172: del.a = new Vector(Arrays.asList(deleted));
173: newHunk = del;
174: } else {
175: HunkChange change = new HunkChange();
176: change.ld1 = (revStartLine - numDeleted) + 1;
177: change.ld2 = (origStartLine - numAdded) + 1;
178: change.lf1 = revStartLine;
179: change.lf2 = origStartLine;
180:
181: Object[] added = new Object[numAdded];
182: System.arraycopy(rev, revEndLine, added, 0, numAdded);
183: Object[] deleted = new Object[numDeleted];
184: System.arraycopy(orig, origEndLine, deleted, 0,
185: numDeleted);
186:
187: change.a = new Vector(Arrays.asList(deleted));
188: change.b = new Vector(Arrays.asList(added));
189: newHunk = change;
190: }
191:
192: v.add(0, newHunk);
193:
194: // Delta delta = Delta.newDelta(new Chunk(orig, ia, i - ia),
195: // new Chunk(rev, ja, j - ja));
196: // revision.insertDelta(delta);
197: //Make hunk.
198:
199: }
200: return v;
201: }
202:
203: }
|