1
20 package org.crosswire.common.diff;
21
22 import java.util.List;
23 import java.util.ListIterator;
24 import java.util.Stack;
25
26
35 public final class DiffCleanup {
36
39 private DiffCleanup() {
40 }
41
42
49 public static void cleanupSemantic(final List<Difference> diffs) {
50 boolean changes = false;
51 Stack<Difference> equalities = new Stack<Difference>(); String lastEquality = null; int lengthChangesPre = 0; int lengthChangesPost = 0; ListIterator<Difference> pointer = diffs.listIterator();
60 Difference curDiff = pointer.hasNext() ? (Difference) pointer.next() : null;
61 while (curDiff != null) {
62 EditType editType = curDiff.getEditType();
63 if (EditType.EQUAL.equals(editType)) {
64 equalities.push(curDiff);
66 lengthChangesPre = lengthChangesPost;
67 lengthChangesPost = 0;
68 lastEquality = curDiff.getText();
69 } else {
70 lengthChangesPost += curDiff.getText().length();
72 int lastLen = lastEquality != null ? lastEquality.length() : 0;
73 if (lastEquality != null && lastLen <= lengthChangesPre && lastLen <= lengthChangesPost) {
74 while (curDiff != equalities.lastElement()) {
77 curDiff = pointer.previous();
78 }
79 pointer.next();
80
81 pointer.set(new Difference(EditType.DELETE, lastEquality));
83 pointer.add(new Difference(EditType.INSERT, lastEquality));
85 equalities.pop(); if (!equalities.empty()) {
88 equalities.pop();
91 }
92 if (equalities.empty()) {
93 while (pointer.hasPrevious()) {
96 pointer.previous();
97 }
98 } else {
99 curDiff = equalities.lastElement();
101 while (curDiff != pointer.previous()) {
102 }
104 }
105
106 lengthChangesPre = 0; lengthChangesPost = 0;
108 lastEquality = null;
109 changes = true;
110 }
111 }
112 curDiff = pointer.hasNext() ? (Difference) pointer.next() : null;
113 }
114
115 if (changes) {
116 cleanupMerge(diffs);
117 }
118 }
119
120
127 public static void cleanupEfficiency(final List<Difference> diffs) {
128 if (diffs.isEmpty()) {
129 return;
130 }
131
132 boolean changes = false;
133 Stack<Difference> equalities = new Stack<Difference>(); String lastEquality = null; int preInsert = 0; int preDelete = 0; int postInsert = 0; int postDelete = 0;
146 ListIterator<Difference> pointer = diffs.listIterator();
147 Difference curDiff = pointer.hasNext() ? (Difference) pointer.next() : null;
148 Difference safeDiff = curDiff;
151 while (curDiff != null) {
152 EditType editType = curDiff.getEditType();
153 if (EditType.EQUAL.equals(editType)) {
154 if (curDiff.getText().length() < editCost && (postInsert + postDelete) > 0) {
156 equalities.push(curDiff);
158 preInsert = postInsert;
159 preDelete = postDelete;
160 lastEquality = curDiff.getText();
161 } else {
162 equalities.clear();
164 lastEquality = null;
165 safeDiff = curDiff;
166 }
167 postInsert = 0;
168 postDelete = 0;
169 } else {
170 if (EditType.DELETE.equals(editType)) {
172 postDelete = 1;
173 } else {
174 postInsert = 1;
175 }
176
177 if (lastEquality != null
184 && (((preInsert + preDelete + postInsert + postDelete) > 0)
185 || ((lastEquality.length() < editCost / 2)
186 && (preInsert + preDelete + postInsert + postDelete) == 3)))
187 {
188 while (curDiff != equalities.lastElement()) {
191 curDiff = pointer.previous();
192 }
193 pointer.next();
194
195 pointer.set(new Difference(EditType.DELETE, lastEquality));
197 curDiff = new Difference(EditType.INSERT, lastEquality);
199 pointer.add(curDiff);
200
201 equalities.pop(); lastEquality = null;
204 if (preInsert == 1 && preDelete == 1) {
205 postInsert = 1;
208 postDelete = 1;
209 equalities.clear();
210 safeDiff = curDiff;
211 } else {
212 if (!equalities.empty()) {
213 equalities.pop();
215 }
216 if (equalities.empty()) {
217 curDiff = safeDiff;
220 } else {
221 curDiff = equalities.lastElement();
223 }
224 while (curDiff != pointer.previous()) {
225 }
227
228 postInsert = 0;
229 postDelete = 0;
230 }
231 changes = true;
232 }
233 }
234 curDiff = pointer.hasNext() ? (Difference) pointer.next() : null;
235 }
236
237 if (changes) {
238 cleanupMerge(diffs);
239 }
240 }
241
242
249 public static void cleanupMerge(final List<Difference> diffs) {
250 diffs.add(new Difference(EditType.EQUAL, ""));
252
253 int countDelete = 0;
254 int countInsert = 0;
255 StringBuilder textDelete = new StringBuilder();
256 StringBuilder textInsert = new StringBuilder();
257
258 int commonLength = 0;
259
260 ListIterator<Difference> pointer = diffs.listIterator();
261 Difference curDiff = pointer.hasNext() ? (Difference) pointer.next() : null;
262 Difference prevEqual = null;
263 while (curDiff != null) {
264 EditType editType = curDiff.getEditType();
265 if (EditType.INSERT.equals(editType)) {
266 countInsert++;
267 textInsert.append(curDiff.getText());
268 prevEqual = null;
269 } else if (EditType.DELETE.equals(editType)) {
270 countDelete++;
271 textDelete.append(curDiff.getText());
272 prevEqual = null;
273 } else if (EditType.EQUAL.equals(editType)) {
274 if (countDelete != 0 || countInsert != 0) {
276 pointer.previous(); while (countDelete-- > 0) {
279 pointer.previous();
280 pointer.remove();
281 }
282 while (countInsert-- > 0) {
283 pointer.previous();
284 pointer.remove();
285 }
286
287 if (countDelete != 0 && countInsert != 0) {
288 commonLength = Commonality.prefix(textInsert.toString(), textDelete.toString());
290 if (commonLength > 0) {
291 if (pointer.hasPrevious()) {
292 curDiff = pointer.previous();
293 assert EditType.EQUAL.equals(curDiff.getEditType()) : "Previous diff should have been an equality.";
294 curDiff.appendText(textInsert.substring(0, commonLength));
295 pointer.next();
296 } else {
297 pointer.add(new Difference(EditType.EQUAL, textInsert.substring(0, commonLength)));
298 }
299 textInsert.replace(0, textInsert.length(), textInsert.substring(commonLength));
300 textDelete.replace(0, textDelete.length(), textDelete.substring(commonLength));
301 }
302
303 commonLength = Commonality.suffix(textInsert.toString(), textDelete.toString());
305 if (commonLength > 0) {
306 curDiff = pointer.next();
307 curDiff.prependText(textInsert.substring(textInsert.length() - commonLength));
308 textInsert.replace(0, textInsert.length(), textInsert.substring(0, textInsert.length() - commonLength));
309 textDelete.replace(0, textDelete.length(), textDelete.substring(0, textDelete.length() - commonLength));
310 pointer.previous();
311 }
312 }
313
314 if (textDelete.length() != 0) {
316 pointer.add(new Difference(EditType.DELETE, textDelete.toString()));
317 }
318
319 if (textInsert.length() != 0) {
320 pointer.add(new Difference(EditType.INSERT, textInsert.toString()));
321 }
322
323 curDiff = pointer.hasNext() ? (Difference) pointer.next() : null;
325 } else if (prevEqual != null) {
326 prevEqual.appendText(curDiff.getText());
328 pointer.remove();
329 curDiff = pointer.previous();
330 pointer.next(); }
332
333 countInsert = 0;
334 countDelete = 0;
335 textDelete.delete(0, textDelete.length());
336 textInsert.delete(0, textInsert.length());
337 prevEqual = curDiff;
338 }
339 curDiff = pointer.hasNext() ? (Difference) pointer.next() : null;
340 }
341
342 Difference lastDiff = diffs.get(diffs.size() - 1);
343 if (lastDiff.getText().length() == 0) {
344 diffs.remove(diffs.size() - 1); }
347 }
348
349
354 public static void setEditCost(int newEditCost) {
355 editCost = newEditCost;
356 }
357
358
361 private static final int EDIT_COST = 4;
362 private static int editCost = EDIT_COST;
363 }
364