001: /*
002: * Copyright (C) 2001, 2002 Robert MacGrogan
003: *
004: * This library is free software; you can redistribute it and/or
005: * modify it under the terms of the GNU Lesser General Public
006: * License as published by the Free Software Foundation; either
007: * version 2.1 of the License, or (at your option) any later version.
008: *
009: * This library is distributed in the hope that it will be useful,
010: * but WITHOUT ANY WARRANTY; without even the implied warranty of
011: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
012: * Lesser General Public License for more details.
013: *
014: * You should have received a copy of the GNU Lesser General Public
015: * License along with this library; if not, write to the Free Software
016: * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
017: *
018: *
019: * $Archive: SourceJammer$
020: * $FileName: JLibDiffAlgorithm.java$
021: * $FileID: 4698$
022: *
023: * Last change:
024: * $AuthorName: Rob MacGrogan$
025: * $VerID: 8865$
026: * $Date: 5/1/03 6:41 PM$
027: * $Comment: JLibDiff diff algorithm.$
028: */
029: package JLibDiff;
030:
031: import java.io.IOException;
032: import java.util.Vector;
033:
034: import org.sourcejammer.util.AppConfig;
035: import org.sourcejammer.util.ConfigurationException;
036:
037: /**
038: * Title: $FileName: JLibDiffAlgorithm.java$
039: * @version $VerNum: 1$
040: * @author $AuthorName: Rob MacGrogan$<br><br>
041: *
042: * $Description: JLibDiff diff algorithm.$<br>
043: * $KeyWordsOff: $<br><br>
044: *
045: * Implements the JLibDiff diff algorithm, abstracted from the diff class.
046: * This algorithm is available under GLPL.
047: */
048: public class JLibDiffAlgorithm implements DiffAlgorithm, define {
049:
050: private String eol = new String(AppConfig.EndOfLines.LINE_FEED);
051:
052: /**
053: * @see JLibDiff.DiffAlgorithm#makeDiff(String[], String[])
054: */
055: public Vector makeDiff(String[] A, String[] B) {
056: int i, j, lower, upper, d = 1, k, row, col;
057: Vector v = new Vector();
058:
059: int aSize = A.length;
060: int bSize = B.length;
061:
062: int origin = Math.max(aSize, bSize);
063:
064: int maxDiagonal = origin * 2;
065:
066: int last_d[] = new int[maxDiagonal + 1]; //row containing last d
067: //pour chaque diag
068: edit script[] = new edit[maxDiagonal + 1]; //correspond a l'edit script */
069:
070: for (row = 0; row < aSize && row < bSize
071: && A[row].equals(B[row]); row++)
072: ;
073: last_d[origin] = row;
074: script[origin] = null;
075: if (row == aSize)
076: lower = origin + 1;
077: else
078: lower = origin - 1;
079: if (row == bSize)
080: upper = origin - 1;
081: else
082: upper = origin + 1;
083: if (lower > upper)
084: return v;
085: else {
086: for (d = 1; d <= maxDiagonal; d++) { //for each value of edit distance
087: for (k = lower; k <= upper; k += 2) //for each relevant diagonal
088: {
089: edit e = new edit();
090: if (e == null) {
091: throw new ConfigurationException(
092: "edit object is null. Cannot continue building diff.");
093: }
094: if (k == origin - d || k != origin + d
095: && last_d[k + 1] >= last_d[k - 1]) {
096: row = last_d[k + 1] + 1;
097: e.setnext(script[k + 1]);
098: e.setop(DELETE);
099: } else {
100: row = last_d[k - 1];
101: e.setnext(script[k - 1]);
102: e.setop(INSERT);
103: }
104: e.setline1(row);
105: col = row + k - origin;
106: e.setline2(col);
107: script[k] = e;
108: while (row < aSize && col < bSize
109: && A[row].equals(B[col])) {
110: row++;
111: col++;
112: }
113: last_d[k] = row;
114: if (row == aSize && col == bSize) {
115: v = getHunk(script[k], A, B, eol);
116: return v;
117: }
118: if (row == aSize)
119: lower = k + 2;
120: if (col == bSize)
121: upper = k - 2;
122: }
123:
124: lower--;
125: upper++;
126: }
127: }
128: return v;
129: }
130:
131: private static Vector getHunk(edit start, String A[], String B[],
132: String sEOL) {
133: Vector v = new Vector();
134: boolean change;
135: int i;
136: edit ep = new edit();
137: edit behind = new edit();
138: edit ahead = new edit();
139: edit a = new edit();
140: edit b = new edit();
141: ahead = start;
142: ahead = start;
143: ep = null;
144: while (ahead != null) {
145: behind = ep;
146: ep = ahead;
147: ahead = ahead.next;
148: ep.next = behind;
149: }
150:
151: while (ep != null) {
152: b = ep;
153: if (ep.op == INSERT) {
154: a = ep;
155: behind = ep.next;
156: while (behind != null && behind.op == INSERT
157: && ep.line1 == behind.line1) {
158: a = behind;
159: behind = behind.next;
160: }
161: HunkAdd add = new HunkAdd();
162: add.ld1 = ep.line1;
163: add.ld2 = ep.line2;
164: add.lf2 = a.line2;
165: do {
166: add.b.addElement(B[ep.line2 - 1] + sEOL);
167: ep = ep.next;
168: } while (ep != null && ep.op == INSERT
169: && ep.line1 == b.line1);
170: add.next = null;
171: if (v.size() != 0)
172: ((Hunk) v.lastElement()).next = add;
173: v.addElement(add);
174: }
175:
176: else {
177: do {
178: a = b;
179: b = b.next;
180: } while (b != null && b.op == DELETE
181: && b.line1 == a.line1 + 1);
182: change = (b != null && b.op == INSERT && b.line1 == a.line1);
183: if (change) {
184: HunkChange cha = new HunkChange();
185: cha.ld1 = ep.line1;
186: cha.lf1 = a.line1;
187: i = 0;
188: behind = b;
189: while (behind != null && behind.op == INSERT
190: && behind.line1 == b.line1) {
191: i++;
192: behind = behind.next;
193: }
194: cha.ld2 = b.line2;
195: cha.lf2 = i - 1 + b.line2;
196: do {
197: cha.a.addElement(A[ep.line1 - 1] + sEOL);
198: ep = ep.next;
199: } while (ep != b);
200: if (!change)
201: continue;
202: do {
203: cha.b.addElement(B[ep.line2 - 1] + sEOL);
204: ep = ep.next;
205: } while (ep != null && ep.op == INSERT
206: && ep.line1 == b.line1);
207: cha.next = null;
208: if (v.size() != 0)
209: ((Hunk) v.lastElement()).next = cha;
210: v.addElement(cha);
211: } else {
212:
213: HunkDel del = new HunkDel();
214: del.ld1 = ep.line1;
215: del.lf1 = a.line1;
216: del.ld2 = ep.line2;
217:
218: do {
219: del.a.addElement(A[ep.line1 - 1] + sEOL);
220: ep = ep.next;
221: } while (ep != b);
222: del.next = null;
223: if (v.size() != 0)
224: ((Hunk) v.lastElement()).next = del;
225: v.addElement(del);
226:
227: }
228: }
229: }
230: return v;
231: }
232:
233: /**
234: * Returns the eol.
235: * @return String
236: */
237: public String getEol() {
238: return eol;
239: }
240:
241: /**
242: * Sets the eol.
243: * @param eol The eol to set
244: */
245: public void setEol(String eol) {
246: this.eol = eol;
247: }
248:
249: }
|