src/main/java/com/sksamuel/diffpatch/DiffMatchPatch.java
public void diff_cleanupSemantic(LinkedList<Diff> diffs) {
    if (diffs.isEmpty()) {
      return;
    }
    boolean changes = false;
    Stack<Diff> equalities = new Stack<Diff>();  // Stack of qualities.
    String lastequality = null; // Always equal to equalities.lastElement().text
    ListIterator<Diff> pointer = diffs.listIterator();
    // Number of characters that changed prior to the equality.
    int length_insertions1 = 0;
    int length_deletions1 = 0;
    // Number of characters that changed after the equality.
    int length_insertions2 = 0;
    int length_deletions2 = 0;
    Diff thisDiff = pointer.next();
    while (thisDiff != null) {
      if (thisDiff.operation == Operation.EQUAL) {
        // Equality found.
        equalities.push(thisDiff);
        length_insertions1 = length_insertions2;
        length_deletions1 = length_deletions2;
        length_insertions2 = 0;
        length_deletions2 = 0;
        lastequality = thisDiff.text;
      } else {
        // An insertion or deletion.
        if (thisDiff.operation == Operation.INSERT) {
          length_insertions2 += thisDiff.text.length();
        } else {
          length_deletions2 += thisDiff.text.length();
        }
        // Eliminate an equality that is smaller or equal to the edits on both
        // sides of it.
        if (lastequality != null && (lastequality.length()
            <= Math.max(length_insertions1, length_deletions1))
            && (lastequality.length()
                <= Math.max(length_insertions2, length_deletions2))) {
          //System.out.println("Splitting: '" + lastequality + "'");
          // Walk back to offending equality.
          while (thisDiff != equalities.lastElement()) {
            thisDiff = pointer.previous();
          }
          pointer.next();

          // Replace equality with a delete.
          pointer.set(new Diff(Operation.DELETE, lastequality));
          // Insert a corresponding an insert.
          pointer.add(new Diff(Operation.INSERT, lastequality));

          equalities.pop();  // Throw away the equality we just deleted.
          if (!equalities.empty()) {
            // Throw away the previous equality (it needs to be reevaluated).
            equalities.pop();
          }
          if (equalities.empty()) {
            // There are no previous equalities, walk back to the start.
            while (pointer.hasPrevious()) {
              pointer.previous();
            }
          } else {
            // There is a safe equality we can fall back to.
            thisDiff = equalities.lastElement();
            while (thisDiff != pointer.previous()) {
              // Intentionally empty loop.
            }
          }

          length_insertions1 = 0;  // Reset the counters.
          length_insertions2 = 0;
          length_deletions1 = 0;
          length_deletions2 = 0;
          lastequality = null;
          changes = true;
        }
      }
      thisDiff = pointer.hasNext() ? pointer.next() : null;
    }

    // Normalize the diff.
    if (changes) {
      diff_cleanupMerge(diffs);
    }
    diff_cleanupSemanticLossless(diffs);

    // Find any overlaps between deletions and insertions.
    // e.g: <del>abcxxx</del><ins>xxxdef</ins>
    //   -> <del>abc</del>xxx<ins>def</ins>
    // e.g: <del>xxxabc</del><ins>defxxx</ins>
    //   -> <ins>def</ins>xxx<del>abc</del>
    // Only extract an overlap if it is as big as the edit ahead or behind it.
    pointer = diffs.listIterator();
    Diff prevDiff = null;
    thisDiff = null;
    if (pointer.hasNext()) {
      prevDiff = pointer.next();
      if (pointer.hasNext()) {
        thisDiff = pointer.next();
      }
    }
    while (thisDiff != null) {
      if (prevDiff.operation == Operation.DELETE &&
          thisDiff.operation == Operation.INSERT) {
        String deletion = prevDiff.text;
        String insertion = thisDiff.text;
        int overlap_length1 = this.diff_commonOverlap(deletion, insertion);
        int overlap_length2 = this.diff_commonOverlap(insertion, deletion);
        if (overlap_length1 >= overlap_length2) {
          if (overlap_length1 >= deletion.length() / 2.0 ||
              overlap_length1 >= insertion.length() / 2.0) {
            // Overlap found. Insert an equality and trim the surrounding edits.
            pointer.previous();
            pointer.add(new Diff(Operation.EQUAL,
                                 insertion.substring(0, overlap_length1)));
            prevDiff.text =
                deletion.substring(0, deletion.length() - overlap_length1);
            thisDiff.text = insertion.substring(overlap_length1);
            // pointer.add inserts the element before the cursor, so there is
            // no need to step past the new element.
          }
        } else {
          if (overlap_length2 >= deletion.length() / 2.0 ||
              overlap_length2 >= insertion.length() / 2.0) {
            // Reverse overlap found.
            // Insert an equality and swap and trim the surrounding edits.
            pointer.previous();
            pointer.add(new Diff(Operation.EQUAL,
                                 deletion.substring(0, overlap_length2)));
            prevDiff.operation = Operation.INSERT;
            prevDiff.text =
              insertion.substring(0, insertion.length() - overlap_length2);
            thisDiff.operation = Operation.DELETE;
            thisDiff.text = deletion.substring(overlap_length2);
            // pointer.add inserts the element before the cursor, so there is
            // no need to step past the new element.
          }
        }
        thisDiff = pointer.hasNext() ? pointer.next() : null;
      }
      prevDiff = thisDiff;
      thisDiff = pointer.hasNext() ? pointer.next() : null;
    }
  }
public void diff_cleanupSemantic(LinkedList<Diff> diffs) {
    if (diffs.isEmpty()) {
      return;
    }
    boolean changes = false;
    Stack<Diff> equalities = new Stack<Diff>();  // Stack of qualities.
    String lastequality = null; // Always equal to equalities.lastElement().text
    ListIterator<Diff> pointer = diffs.listIterator();
    // Number of characters that changed prior to the equality.
    int length_insertions1 = 0;
    int length_deletions1 = 0;
    // Number of characters that changed after the equality.
    int length_insertions2 = 0;
    int length_deletions2 = 0;
    Diff thisDiff = pointer.next();
    while (thisDiff != null) {
      if (thisDiff.operation == Operation.EQUAL) {
        // Equality found.
        equalities.push(thisDiff);
        length_insertions1 = length_insertions2;
        length_deletions1 = length_deletions2;
        length_insertions2 = 0;
        length_deletions2 = 0;
        lastequality = thisDiff.text;
      } else {
        // An insertion or deletion.
        if (thisDiff.operation == Operation.INSERT) {
          length_insertions2 += thisDiff.text.length();
        } else {
          length_deletions2 += thisDiff.text.length();
        }
        // Eliminate an equality that is smaller or equal to the edits on both
        // sides of it.
        if (lastequality != null && (lastequality.length()
            <= Math.max(length_insertions1, length_deletions1))
            && (lastequality.length()
                <= Math.max(length_insertions2, length_deletions2))) {
          //System.out.println("Splitting: '" + lastequality + "'");
          // Walk back to offending equality.
          while (thisDiff != equalities.lastElement()) {
            thisDiff = pointer.previous();
          }
          pointer.next();

          // Replace equality with a delete.
          pointer.set(new Diff(Operation.DELETE, lastequality));
          // Insert a corresponding an insert.
          pointer.add(new Diff(Operation.INSERT, lastequality));

          equalities.pop();  // Throw away the equality we just deleted.
          if (!equalities.empty()) {
            // Throw away the previous equality (it needs to be reevaluated).
            equalities.pop();
          }
          if (equalities.empty()) {
            // There are no previous equalities, walk back to the start.
            while (pointer.hasPrevious()) {
              pointer.previous();
            }
          } else {
            // There is a safe equality we can fall back to.
            thisDiff = equalities.lastElement();
            while (thisDiff != pointer.previous()) {
              // Intentionally empty loop.
            }
          }

          length_insertions1 = 0;  // Reset the counters.
          length_insertions2 = 0;
          length_deletions1 = 0;
          length_deletions2 = 0;
          lastequality = null;
          changes = true;
        }
      }
      thisDiff = pointer.hasNext() ? pointer.next() : null;
    }

    // Normalize the diff.
    if (changes) {
      diff_cleanupMerge(diffs);
    }
    diff_cleanupSemanticLossless(diffs);

    // Find any overlaps between deletions and insertions.
    // e.g: <del>abcxxx</del><ins>xxxdef</ins>
    //   -> <del>abc</del>xxx<ins>def</ins>
    // e.g: <del>xxxabc</del><ins>defxxx</ins>
    //   -> <ins>def</ins>xxx<del>abc</del>
    // Only extract an overlap if it is as big as the edit ahead or behind it.
    pointer = diffs.listIterator();
    Diff prevDiff = null;
    thisDiff = null;
    if (pointer.hasNext()) {
      prevDiff = pointer.next();
      if (pointer.hasNext()) {
        thisDiff = pointer.next();
      }
    }
    while (thisDiff != null) {
      if (prevDiff.operation == Operation.DELETE &&
          thisDiff.operation == Operation.INSERT) {
        String deletion = prevDiff.text;
        String insertion = thisDiff.text;
        int overlap_length1 = this.diff_commonOverlap(deletion, insertion);
        int overlap_length2 = this.diff_commonOverlap(insertion, deletion);
        if (overlap_length1 >= overlap_length2) {
          if (overlap_length1 >= deletion.length() / 2.0 ||
              overlap_length1 >= insertion.length() / 2.0) {
            // Overlap found. Insert an equality and trim the surrounding edits.
            pointer.previous();
            pointer.add(new Diff(Operation.EQUAL,
                                 insertion.substring(0, overlap_length1)));
            prevDiff.text =
                deletion.substring(0, deletion.length() - overlap_length1);
            thisDiff.text = insertion.substring(overlap_length1);
            // pointer.add inserts the element before the cursor, so there is
            // no need to step past the new element.
          }
        } else {
          if (overlap_length2 >= deletion.length() / 2.0 ||
              overlap_length2 >= insertion.length() / 2.0) {
            // Reverse overlap found.
            // Insert an equality and swap and trim the surrounding edits.
            pointer.previous();
            pointer.add(new Diff(Operation.EQUAL,
                                 deletion.substring(0, overlap_length2)));
            prevDiff.operation = Operation.INSERT;
            prevDiff.text =
              insertion.substring(0, insertion.length() - overlap_length2);
            thisDiff.operation = Operation.DELETE;
            thisDiff.text = deletion.substring(overlap_length2);
            // pointer.add inserts the element before the cursor, so there is
            // no need to step past the new element.
          }
        }
        thisDiff = pointer.hasNext() ? pointer.next() : null;
      }
      prevDiff = thisDiff;
      thisDiff = pointer.hasNext() ? pointer.next() : null;
    }
  }
public void diff_cleanupSemantic ( LinkedList < Diff > diffs ) { if ( diffs . isEmpty ( ) ) { return ; } boolean changes = false ; Stack < Diff > equalities = new Stack < Diff > ( ) ; // Stack of qualities. String lastequality = null ; // Always equal to equalities.lastElement().text ListIterator < Diff > pointer = diffs . listIterator ( ) ; // Number of characters that changed prior to the equality. int length_insertions1 = 0 ; int length_deletions1 = 0 ; // Number of characters that changed after the equality. int length_insertions2 = 0 ; int length_deletions2 = 0 ; Diff thisDiff = pointer . next ( ) ; while ( thisDiff != null ) { if ( thisDiff . operation == Operation . EQUAL ) { // Equality found. equalities . push ( thisDiff ) ; length_insertions1 = length_insertions2 ; length_deletions1 = length_deletions2 ; length_insertions2 = 0 ; length_deletions2 = 0 ; lastequality = thisDiff . text ; } else { // An insertion or deletion. if ( thisDiff . operation == Operation . INSERT ) { length_insertions2 += thisDiff . text . length ( ) ; } else { length_deletions2 += thisDiff . text . length ( ) ; } // Eliminate an equality that is smaller or equal to the edits on both // sides of it. if ( lastequality != null && ( lastequality . length ( ) <= Math . max ( length_insertions1 , length_deletions1 ) ) && ( lastequality . length ( ) <= Math . max ( length_insertions2 , length_deletions2 ) ) ) { //System.out.println("Splitting: '" + lastequality + "'"); // Walk back to offending equality. while ( thisDiff != equalities . lastElement ( ) ) { thisDiff = pointer . previous ( ) ; } pointer . next ( ) ; // Replace equality with a delete. pointer . set ( new Diff ( Operation . DELETE , lastequality ) ) ; // Insert a corresponding an insert. pointer . add ( new Diff ( Operation . INSERT , lastequality ) ) ; equalities . pop ( ) ; // Throw away the equality we just deleted. if ( ! equalities . empty ( ) ) { // Throw away the previous equality (it needs to be reevaluated). equalities . pop ( ) ; } if ( equalities . empty ( ) ) { // There are no previous equalities, walk back to the start. while ( pointer . hasPrevious ( ) ) { pointer . previous ( ) ; } } else { // There is a safe equality we can fall back to. thisDiff = equalities . lastElement ( ) ; while ( thisDiff != pointer . previous ( ) ) { // Intentionally empty loop. } } length_insertions1 = 0 ; // Reset the counters. length_insertions2 = 0 ; length_deletions1 = 0 ; length_deletions2 = 0 ; lastequality = null ; changes = true ; } } thisDiff = pointer . hasNext ( ) ? pointer . next ( ) : null ; } // Normalize the diff. if ( changes ) { diff_cleanupMerge ( diffs ) ; } diff_cleanupSemanticLossless ( diffs ) ; // Find any overlaps between deletions and insertions. // e.g: <del>abcxxx</del><ins>xxxdef</ins> //   -> <del>abc</del>xxx<ins>def</ins> // e.g: <del>xxxabc</del><ins>defxxx</ins> //   -> <ins>def</ins>xxx<del>abc</del> // Only extract an overlap if it is as big as the edit ahead or behind it. pointer = diffs . listIterator ( ) ; Diff prevDiff = null ; thisDiff = null ; if ( pointer . hasNext ( ) ) { prevDiff = pointer . next ( ) ; if ( pointer . hasNext ( ) ) { thisDiff = pointer . next ( ) ; } } while ( thisDiff != null ) { if ( prevDiff . operation == Operation . DELETE && thisDiff . operation == Operation . INSERT ) { String deletion = prevDiff . text ; String insertion = thisDiff . text ; int overlap_length1 = this . diff_commonOverlap ( deletion , insertion ) ; int overlap_length2 = this . diff_commonOverlap ( insertion , deletion ) ; if ( overlap_length1 >= overlap_length2 ) { if ( overlap_length1 >= deletion . length ( ) / 2.0 || overlap_length1 >= insertion . length ( ) / 2.0 ) { // Overlap found. Insert an equality and trim the surrounding edits. pointer . previous ( ) ; pointer . add ( new Diff ( Operation . EQUAL , insertion . substring ( 0 , overlap_length1 ) ) ) ; prevDiff . text = deletion . substring ( 0 , deletion . length ( ) - overlap_length1 ) ; thisDiff . text = insertion . substring ( overlap_length1 ) ; // pointer.add inserts the element before the cursor, so there is // no need to step past the new element. } } else { if ( overlap_length2 >= deletion . length ( ) / 2.0 || overlap_length2 >= insertion . length ( ) / 2.0 ) { // Reverse overlap found. // Insert an equality and swap and trim the surrounding edits. pointer . previous ( ) ; pointer . add ( new Diff ( Operation . EQUAL , deletion . substring ( 0 , overlap_length2 ) ) ) ; prevDiff . operation = Operation . INSERT ; prevDiff . text = insertion . substring ( 0 , insertion . length ( ) - overlap_length2 ) ; thisDiff . operation = Operation . DELETE ; thisDiff . text = deletion . substring ( overlap_length2 ) ; // pointer.add inserts the element before the cursor, so there is // no need to step past the new element. } } thisDiff = pointer . hasNext ( ) ? pointer . next ( ) : null ; } prevDiff = thisDiff ; thisDiff = pointer . hasNext ( ) ? pointer . next ( ) : null ; } }
Reduce the number of edits by eliminating semantically trivial equalities.
@param diffs LinkedList of Diff objects.
Reduce the number of edits by eliminating semantically trivial equalities .