Ignore equal elements at the ends of sequences in diffseq()

andreas-gruenbacher · andreas-gruenbacher · commit c08bee288dde · 2014-03-30T15:27:00.000+02:00
This fixes the two test cases with non-optimal results.
diff --git a/json-diff.js b/json-diff.js
@@ -88,45 +88,58 @@ var json_diff = (function() {
       var i, j, m, n,
 	  row = [], c = [],
 	  left, diag, latch;
+      var skip, edit = [];
 
       m = a.length;
       n = b.length;
 
-      //build the c-table
-      for (j = 0; j < n; row[j++] = 0);
-      for (i = 0 ; i < m; i++) {
-	c[i] = row = row.slice();
-	for (diag = 0, j = 0; j < n; j++, diag = latch) {
-	  latch = row[j];
-	  if (equal(a[i], b[j]))
-	    row[j] = diag + 1;
-	  else {
-	    left = row[j-1] || 0;
-	    if (left > row[j])
-	      row[j] = left;
+      // ignore equal elements at both ends
+      for (; m && n; m--, n--)
+	if (!equal(a[m - 1], b[n - 1]))
+	  break;
+      for (skip = 0; m && n; skip++, m--, n--)
+	if (!equal(a[skip], b[skip]))
+	  break;
+
+      if (m && n) {
+	//build the c-table
+	for (j = 0; j < n; row[j++] = 0);
+	for (i = 0 ; i < m; i++) {
+	  c[i] = row = row.slice();
+	  for (diag = 0, j = 0; j < n; j++, diag = latch) {
+	    latch = row[j];
+	    if (equal(a[i + skip], b[j + skip]))
+	      row[j] = diag + 1;
+	    else {
+	      left = row[j - 1] || 0;
+	      if (left > row[j])
+		row[j] = left;
+	    }
 	  }
 	}
-      }
-      i--, j--;
-
-      //row[j] now contains the length of the lcs
-      //compute the edit sequence from the table
-      var edit = [];
-      while (i > -1 && j > -1) {
-	switch (c[i][j]) {
-	  default:
-	    edit.unshift('=');
-	    i--; j--;
-	    break;
-	  case j && c[i][j - 1]:
-	    edit.unshift('+');
-	    j--;
-	    break;
-	  case i && c[i - 1][j]:
-	    edit.unshift('-');
-	    i--;
-	    break;
+	i--, j--;
+
+	//row[j] now contains the length of the lcs
+	//compute the edit sequence from the table
+	while (i > -1 && j > -1) {
+	  switch (c[i][j]) {
+	    default:
+	      edit.unshift('=');
+	      i--; j--;
+	      break;
+	    case j && c[i][j - 1]:
+	      edit.unshift('+');
+	      j--;
+	      break;
+	    case i && c[i - 1][j]:
+	      edit.unshift('-');
+	      i--;
+	      break;
+	  }
 	}
+      } else {
+	i = m - 1;
+	j = n - 1;
       }
       for (; j > -1; j--)
 	edit.unshift('+');
@@ -150,23 +163,23 @@ var json_diff = (function() {
 	} else
 	  edit_replace.push(edit[n]);
       }
-      // console.log('>>> ' + edit.join('') + ' ' + edit_replace.join(''));
+      // console.log('>>> ' + skip + ' ' + edit.join('') + ' ' + edit_replace.join(''));
       edit = edit_replace;
 
       for (i = 0, j = 0, n = 0; n < edit.length; n++) {
 	switch(edit[n]) {
 	  case '*':
-	    diff_recursive(a[i], b[j], j);
+	    diff_recursive(a[i + skip], b[j + skip], j + skip);
 	  case '=':
 	    i++;
 	    j++;
 	    break;
 	  case '-':
-	    result('remove', j);
+	    result('remove', j + skip);
 	    i++;
 	    break;
 	  case '+':
-	    result('add', j, b[j]);
+	    result('add', j + skip, b[j + skip]);
 	    j++;
 	    break;
 	}
diff --git a/test.js b/test.js
@@ -60,6 +60,9 @@ expect([1, 2, 3], [1, 4, 3], [{op: 'replace', path: '/1', value: 4}])
 expect({a: [9, 8, 7], b: 2, c: 3}, {a: [9, 7], b: 2, c: 4, d: 5},
        [{op: 'remove', path: '/a/1'}, {op: 'replace', path: '/c', value: 4}, {op: 'add', path: '/d', value: 5}])
 
+expect([1, 0, 0], [1, 1, 0], [{op: 'replace', path: '/1', value: 1}]);
+expect([1, 1, 0], [1, 0, 0], [{op: 'replace', path: '/1', value: 0}]);
+
 // Reverse examples from RFC 6902, as far as applicable:
 expect({foo: 'bar'}, {baz: 'qux', foo: 'bar'}, [{op: 'add', path: '/baz', value: 'qux'}])
 expect({foo: ['bar', 'baz']}, {foo: ['bar', 'qux', 'baz']}, [{op: 'add', path: '/foo/1', value: 'qux'}])
@@ -69,12 +72,6 @@ expect({baz: 'qux', foo: 'bar'}, {baz: 'boo', foo: 'bar'}, [{op: 'replace', path
 expect({foo: 'bar'}, {foo: 'bar', child: {grandchild: {}}}, [{op: 'add', path: '/child', value: {'grandchild': {}}}])
 expect({foo: ['bar']}, {foo: ['bar', ['abc', 'def']]}, [{op: 'add', path: '/foo/1', value: ['abc', 'def']}])
 
-// The following cases produce non-optimal diffs:
-expect([1, 0, 0], [1, 1, 0], [{op: 'add', path: '/1', value: 1}, {op: 'remove', path: '/3'}]);
-// ideal: [{op: 'replace', path: '/1', value: 1}]
-expect([1, 1, 0], [1, 0, 0], [{op: 'remove', path: '/1'}, {op: 'add', path: '/2', value: 0}]);
-// ideal: [{op: 'replace', path: '/1', value: 0}]
-
 if (failures) {
   console.log(failures + ' FAILURE(S)');
   process.exit(1);
