Lines Matching defs:Diff
2 * Diff Match and Patch
5 * http://code.google.com/p/google-diff-match-patch/
40 * Functions for diff, match and patch.
48 * Class containing the diff, match and patch methods.
57 * Number of seconds to map a diff before giving up (0 for infinity).
65 * The size beyond which the double-ended diff activates.
114 // DIFF FUNCTIONS
118 * The data structure representing a diff is a Linked list of Diff objects:
119 * {Diff(Operation.DELETE, "Hello"), Diff(Operation.INSERT, "Goodbye"),
120 * Diff(Operation.EQUAL, " world.")}
130 * Run a faster slightly less optimal diff
135 * @return Linked List of Diff objects.
137 public LinkedList<Diff> diff_main(String text1, String text2) {
147 * line-level diff first to identify the changed areas.
148 * If true, then run a faster slightly less optimal diff
149 * @return Linked List of Diff objects.
151 public LinkedList<Diff> diff_main(String text1, String text2,
159 LinkedList<Diff> diffs;
161 diffs = new LinkedList<Diff>();
162 diffs.add(new Diff(Operation.EQUAL, text1));
178 // Compute the diff on the middle block.
183 diffs.addFirst(new Diff(Operation.EQUAL, commonprefix));
186 diffs.addLast(new Diff(Operation.EQUAL, commonsuffix));
200 * line-level diff first to identify the changed areas.
201 * If true, then run a faster slightly less optimal diff
202 * @return Linked List of Diff objects.
204 protected LinkedList<Diff> diff_compute(String text1, String text2,
206 LinkedList<Diff> diffs = new LinkedList<Diff>();
210 diffs.add(new Diff(Operation.INSERT, text2));
216 diffs.add(new Diff(Operation.DELETE, text1));
227 diffs.add(new Diff(op, longtext.substring(0, i)));
228 diffs.add(new Diff(Operation.EQUAL, shorttext));
229 diffs.add(new Diff(op, longtext.substring(i + shorttext.length())));
244 LinkedList<Diff> diffs_a = diff_main(text1_a, text2_a, checklines);
245 LinkedList<Diff> diffs_b = diff_main(text1_b, text2_b, checklines);
248 diffs.add(new Diff(Operation.EQUAL, mid_common));
253 // Perform a real diff.
269 diffs = new LinkedList<Diff>();
270 diffs.add(new Diff(Operation.DELETE, text1));
271 diffs.add(new Diff(Operation.INSERT, text2));
275 // Convert the diff back to original text.
282 diffs.add(new Diff(Operation.EQUAL, ""));
287 ListIterator<Diff> pointer = diffs.listIterator();
288 Diff thisDiff = pointer.next();
308 for (Diff newDiff : diff_main(text_delete, text_insert, false)) {
389 * Rehydrate the text in a diff from a string of line hashes to real lines of
391 * @param diffs LinkedList of Diff objects.
394 protected void diff_charsToLines(LinkedList<Diff> diffs,
397 for (Diff diff : diffs) {
399 for (int y = 0; y < diff.text.length(); y++) {
400 text.append(lineArray.get(diff.text.charAt(y)));
402 diff.text = text.toString();
411 * @return LinkedList of Diff objects or null if no diff available.
413 protected LinkedList<Diff> diff_map(String text1, String text2) {
479 LinkedList<Diff> a = diff_path1(v_map1, text1.substring(0, x),
521 LinkedList<Diff> a
541 * @return LinkedList of Diff objects.
543 protected LinkedList<Diff> diff_path1(List<Set<Long>> v_map,
545 LinkedList<Diff> path = new LinkedList<Diff>();
556 path.addFirst(new Diff(Operation.DELETE,
566 path.addFirst(new Diff(Operation.INSERT,
579 path.addFirst(new Diff(Operation.EQUAL, text1.substring(x, x + 1)));
594 * @return LinkedList of Diff objects.
596 protected LinkedList<Diff> diff_path2(List<Set<Long>> v_map,
598 LinkedList<Diff> path = new LinkedList<Diff>();
609 path.addLast(new Diff(Operation.DELETE,
619 path.addLast(new Diff(Operation.INSERT,
633 path.addLast(new Diff(Operation.EQUAL,
785 * @param diffs LinkedList of Diff objects.
787 public void diff_cleanupSemantic(LinkedList<Diff> diffs) {
792 Stack<Diff> equalities = new Stack<Diff>(); // Stack of qualities.
794 ListIterator<Diff> pointer = diffs.listIterator();
799 Diff thisDiff = pointer.next();
820 pointer.set(new Diff(Operation.DELETE, lastequality));
822 pointer.add(new Diff(Operation.INSERT, lastequality));
862 * @param diffs LinkedList of Diff objects.
864 public void diff_cleanupSemanticLossless(LinkedList<Diff> diffs) {
871 ListIterator<Diff> pointer = diffs.listIterator();
872 Diff prevDiff = pointer.hasNext() ? pointer.next() : null;
873 Diff thisDiff = pointer.hasNext() ? pointer.next() : null;
874 Diff nextDiff = pointer.hasNext() ? pointer.next() : null;
916 // We have an improvement, save it back to the diff.
996 * @param diffs LinkedList of Diff objects.
998 public void diff_cleanupEfficiency(LinkedList<Diff> diffs) {
1003 Stack<Diff> equalities = new Stack<Diff>(); // Stack of equalities.
1005 ListIterator<Diff> pointer = diffs.listIterator();
1014 Diff thisDiff = pointer.next();
1015 Diff safeDiff = thisDiff; // The last Diff that is known to be unsplitable.
1060 pointer.set(new Diff(Operation.DELETE, lastequality));
1062 pointer.add(thisDiff = new Diff(Operation.INSERT, lastequality));
1078 // walk back to the last known safe diff.
1105 * @param diffs LinkedList of Diff objects.
1107 public void diff_cleanupMerge(LinkedList<Diff> diffs) {
1108 diffs.add(new Diff(Operation.EQUAL, "")); // Add a dummy entry at the end.
1109 ListIterator<Diff> pointer = diffs.listIterator();
1114 Diff thisDiff = pointer.next();
1115 Diff prevEqual = null;
1148 : "Previous diff should have been an equality.";
1152 pointer.add(new Diff(Operation.EQUAL,
1173 pointer.add(new Diff(Operation.DELETE, text_delete));
1176 pointer.add(new Diff(Operation.INSERT, text_insert));
1196 // System.out.println(diff);
1210 Diff prevDiff = pointer.hasNext() ? pointer.next() : null;
1212 Diff nextDiff = pointer.hasNext() ? pointer.next() : null;
1246 // If shifts were made, the diff needs reordering and another shift sweep.
1257 * @param diffs LinkedList of Diff objects.
1261 public int diff_xIndex(LinkedList<Diff> diffs, int loc) {
1266 Diff lastDiff = null;
1267 for (Diff aDiff : diffs) {
1294 * Convert a Diff list into a pretty HTML report.
1295 * @param diffs LinkedList of Diff objects.
1298 public String diff_prettyHtml(LinkedList<Diff> diffs) {
1301 for (Diff aDiff : diffs) {
1328 * @param diffs LinkedList of Diff objects.
1331 public String diff_text1(LinkedList<Diff> diffs) {
1333 for (Diff aDiff : diffs) {
1344 * @param diffs LinkedList of Diff objects.
1347 public String diff_text2(LinkedList<Diff> diffs) {
1349 for (Diff aDiff : diffs) {
1361 * @param diffs LinkedList of Diff objects.
1364 public int diff_levenshtein(LinkedList<Diff> diffs) {
1368 for (Diff aDiff : diffs) {
1390 * Crush the diff into an encoded string which describes the operations
1394 * @param diffs Array of diff tuples.
1397 public String diff_toDelta(LinkedList<Diff> diffs) {
1399 for (Diff aDiff : diffs) {
1430 * operations required to transform text1 into text2, compute the full diff.
1431 * @param text1 Source string for the diff.
1433 * @return Array of diff tuples or null if invalid.
1436 public LinkedList<Diff> diff_fromDelta(String text1, String delta)
1438 LinkedList<Diff> diffs = new LinkedList<Diff>();
1463 diffs.add(new Diff(Operation.INSERT, param));
1488 diffs.add(new Diff(Operation.EQUAL, text));
1490 diffs.add(new Diff(Operation.DELETE, text));
1496 "Invalid diff operation in diff_fromDelta: " + token.charAt(0));
1716 patch.diffs.addFirst(new Diff(Operation.EQUAL, prefix));
1722 patch.diffs.addLast(new Diff(Operation.EQUAL, suffix));
1746 LinkedList<Diff> diffs = diff_main(text1, text2, true);
1758 * @param diffs Array of diff tuples for text1 to text2.
1761 public LinkedList<Patch> patch_make(LinkedList<Diff> diffs) {
1776 * @param diffs Array of diff tuples for text1 to text2.
1778 * @deprecated Prefer patch_make(String text1, LinkedList<Diff> diffs).
1781 LinkedList<Diff> diffs) {
1790 * @param diffs Array of diff tuples for text1 to text2.
1793 public LinkedList<Patch> patch_make(String text1, LinkedList<Diff> diffs) {
1810 for (Diff aDiff : diffs) {
1846 // http://code.google.com/p/google-diff
1883 for (Diff aDiff : aPatch.diffs) {
1884 Diff diffCopy = new Diff(aDiff.operation, aDiff.text);
1968 // Imperfect match. Run a diff to get a framework of equivalent
1970 LinkedList<Diff> diffs = diff_main(text1, text2, false);
1979 for (Diff aDiff : aPatch.diffs) {
2028 // Add some padding on start of first diff.
2030 LinkedList<Diff> diffs = patch.diffs;
2033 diffs.addFirst(new Diff(Operation.EQUAL, nullPadding));
2040 Diff firstDiff = diffs.getFirst();
2050 // Add some padding on end of last diff.
2055 diffs.addLast(new Diff(Operation.EQUAL, nullPadding));
2060 Diff lastDiff = diffs.getLast();
2105 patch.diffs.add(new Diff(Operation.EQUAL, precontext));
2124 patch.diffs.add(new Diff(diff_type, diff_text));
2138 patch.diffs.add(new Diff(diff_type, diff_text));
2164 patch.diffs.add(new Diff(Operation.EQUAL, postcontext));
2264 patch.diffs.add(new Diff(Operation.DELETE, line));
2267 patch.diffs.add(new Diff(Operation.INSERT, line));
2270 patch.diffs.add(new Diff(Operation.EQUAL, line));
2287 * Class representing one diff operation.
2289 public static class Diff {
2295 * The text associated with this diff operation.
2300 * Constructor. Initializes the diff with the provided values.
2304 public Diff(Operation operation, String text) {
2305 diff with the specified operation and text.
2312 * Display a human-readable version of this Diff.
2317 return "Diff(" + this.operation + ",\"" + prettyText + "\")";
2322 * Is this Diff equivalent to another Diff?
2323 * @param d Another Diff to compare against.
2328 return (((Diff) d).operation == this.operation)
2329 && (((Diff) d).text.equals(this.text));
2341 public LinkedList<Diff> diffs;
2352 this.diffs = new LinkedList<Diff>();
2357 * Emmulate GNU diff's format.
2360 * @return The GNU diff string.
2382 for (Diff aDiff : this.diffs) {
