nl_tokens: Reduce the number of edits by eliminating semantically trivial equalities .
pl_tokens: 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 . <mask> ( 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 ; } }