1
20 package org.crosswire.common.diff;
21
22 import java.util.ArrayList;
23 import java.util.List;
24 import java.util.ListIterator;
25
26
35 public class Diff {
36
47 public Diff(final String source, final String target) {
48 this(source, target, true);
49 }
50
51
63 public Diff(final String source, final String target, final boolean checkLines) {
64 this.source = source;
65 this.target = target;
66 this.checkLines = checkLines;
67 }
68
69
75 public List<Difference> compare() {
76 List<Difference> diffs;
78 if (source.equals(target)) {
79 diffs = new ArrayList<Difference>();
80 diffs.add(new Difference(EditType.EQUAL, source));
81 return diffs;
82 }
83
84 int commonLength = Commonality.prefix(source, target);
86 String commonPrefix = source.substring(0, commonLength);
87 source = source.substring(commonLength);
88 target = target.substring(commonLength);
89
90 commonLength = Commonality.suffix(source, target);
92 String commonSuffix = source.substring(source.length() - commonLength);
93 source = source.substring(0, source.length() - commonLength);
94 target = target.substring(0, target.length() - commonLength);
95
96 diffs = compute();
98
99 if (!"".equals(commonPrefix)) {
101 diffs.add(0, new Difference(EditType.EQUAL, commonPrefix));
102 }
103
104 if (!"".equals(commonSuffix)) {
105 diffs.add(new Difference(EditType.EQUAL, commonSuffix));
106 }
107
108 DiffCleanup.cleanupMerge(diffs);
109
110 return diffs;
111 }
112
113
118 private List<Difference> compute() {
119 List<Difference> diffs = new ArrayList<Difference>();
120
121 if ("".equals(source)) {
122 diffs.add(new Difference(EditType.INSERT, target));
124 return diffs;
125 }
126
127 if ("".equals(target)) {
128 diffs.add(new Difference(EditType.DELETE, source));
130 return diffs;
131 }
132
133 String longText = source.length() > target.length() ? source : target;
134 String shortText = source.length() > target.length() ? target : source;
135 int i = longText.indexOf(shortText);
136 if (i != -1) {
137 EditType editType = (source.length() > target.length()) ? EditType.DELETE : EditType.INSERT;
139 diffs.add(new Difference(editType, longText.substring(0, i)));
140 diffs.add(new Difference(EditType.EQUAL, shortText));
141 diffs.add(new Difference(editType, longText.substring(i + shortText.length())));
142 return diffs;
143 }
144
145 CommonMiddle middleMatch = Commonality.halfMatch(source, target);
147 if (middleMatch != null) {
148 Diff startDiff = new Diff(middleMatch.getSourcePrefix(), middleMatch.getTargetPrefix(), checkLines);
151 Diff endDiff = new Diff(middleMatch.getSourceSuffix(), middleMatch.getTargetSuffix(), checkLines);
152 diffs = startDiff.compare();
154 diffs.add(new Difference(EditType.EQUAL, middleMatch.getCommonality()));
155 diffs.addAll(endDiff.compare());
156 return diffs;
157 }
158
159 if (checkLines && source.length() + target.length() < 250) {
161 checkLines = false; }
163
164 LineMap lineMap = null;
165 if (checkLines) {
166 lineMap = new LineMap(source, target);
168 source = lineMap.getSourceMap();
169 target = lineMap.getTargetMap();
170 }
171
172 diffs = new DifferenceEngine(source, target).generate();
173
174 if (diffs == null) {
175 diffs = new ArrayList<Difference>();
177 diffs.add(new Difference(EditType.DELETE, source));
178 diffs.add(new Difference(EditType.INSERT, target));
179 }
180
181 if (checkLines && lineMap != null) {
182 lineMap.restore(diffs);
184 DiffCleanup.cleanupSemantic(diffs);
186
187 diffs.add(new Difference(EditType.EQUAL, ""));
190 int countDeletes = 0;
191 int countInserts = 0;
192 StringBuilder textDelete = new StringBuilder();
193 StringBuilder textInsert = new StringBuilder();
194 ListIterator<Difference> pointer = diffs.listIterator();
195 Difference curDiff = pointer.next();
196 while (curDiff != null) {
197 EditType editType = curDiff.getEditType();
198 if (EditType.INSERT.equals(editType)) {
199 countInserts++;
200 textInsert.append(curDiff.getText());
201 } else if (EditType.DELETE.equals(editType)) {
202 countDeletes++;
203 textDelete.append(curDiff.getText());
204 } else {
205 if (countDeletes >= 1 && countInserts >= 1) {
207 pointer.previous();
209 for (int j = 0; j < countDeletes + countInserts; j++) {
210 pointer.previous();
211 pointer.remove();
212 }
213 Diff newDiff = new Diff(textDelete.toString(), textInsert.toString(), false);
214 for (Difference diff : newDiff.compare()) {
215 pointer.add(diff);
216 }
217 }
218 countInserts = 0;
219 countDeletes = 0;
220 textDelete.delete(0, textDelete.length());
221 textInsert.delete(0, textInsert.length());
222 }
223 curDiff = pointer.hasNext() ? pointer.next() : null;
224 }
225 diffs.remove(diffs.size() - 1); }
228 return diffs;
229 }
230
231
241 public int xIndex(final List<Difference> diffs, final int loc) {
242 int chars1 = 0;
243 int chars2 = 0;
244 int lastChars1 = 0;
245 int lastChars2 = 0;
246 Difference lastDiff = null;
247 for (Difference diff : diffs) {
248 EditType editType = diff.getEditType();
249
250 if (!EditType.INSERT.equals(editType)) {
252 chars1 += diff.getText().length();
253 }
254
255 if (!EditType.DELETE.equals(editType)) {
257 chars2 += diff.getText().length();
258 }
259
260 if (chars1 > loc) {
262 lastDiff = diff;
263 break;
264 }
265 lastChars1 = chars1;
266 lastChars2 = chars2;
267 }
268
269 if (lastDiff != null && EditType.DELETE.equals(lastDiff.getEditType())) {
271 return lastChars2;
272 }
273
274 return lastChars2 + (loc - lastChars1);
276 }
277
278
285 public String prettyHtml(List<Difference> diffs) {
286 StringBuilder buf = new StringBuilder();
287 for (int x = 0; x < diffs.size(); x++) {
288 Difference diff = diffs.get(x);
289 EditType editType = diff.getEditType(); String text = diff.getText(); if (EditType.DELETE.equals(editType)) {
298 buf.append("<del style=\"background:#FFE6E6;\">");
299 buf.append(text);
300 buf.append("</del>");
301 } else if (EditType.INSERT.equals(editType)) {
302 buf.append("<ins style=\"background:#E6FFE6;\">");
303 buf.append(text);
304 buf.append("</ins>");
305 } else {
306 buf.append("<span>");
307 buf.append(text);
308 buf.append("</span>");
309 }
310 }
311 return buf.toString();
312 }
313
314
317 private String source;
318
319
322 private String target;
323
324
327 private boolean checkLines;
328 }
329