Calculate a diff patch of an array in JavaScript

Question

I want to generate an object that will effectively be able to be applied as a patch to array A in order to produce array B.

Given a function isSame which compares two values and returns true if they're the same, or false otherwise (and the purpose of which is to compare two array elements), is there a known algorithm to calculate the difference between two arrays and return a list of specific differences? The differences would be composed of sets of: X elements removed at index Y and the following elements inserted at index Y.

I've written something that sort of works, but it's buggy at the moment and I'm having trouble moving forward with it, and I'm worrying that I'm reinventing the wheel when somebody else may have already done this. http://jsfiddle.net/G6tYt/1/

Answer 1

If you want the comparison to be both deep and tolerant of objects and arrays both, then this tool I wrote a while back might be of use:

https://github.com/danski/spahql/blob/master/src/SpahQL.DataHelper.js#L18

SpahQL.DataHelper.compare(
  {"a": "aval", "b": "bval", "c": "cval", "arr": [0,1,2]},
  {"a": "modified", "c": "cval", "d": "added", "arr": [0,1,2,3]}
);
// -> {"/": "~", "/a": "~", "/b": "-", "/d": "+", "/arr": "~", "/arr/3": "+"}