-/* JSON-delta v1.1.3 - A diff/patch pair for JSON-serialized data
+/* JSON-delta v2.0 - A diff/patch pair for JSON-serialized data
structures.
Copyright 2013-2015 Philip J. Roberts <himself@phil-roberts.name>.
}
},
- splitDeletions: function(diff) {
- /* Split the stanzas in diff into an array of two arrays:
- * [modifications, deletions]. */
- var idx;
+ inArray: function(keypath) {
+ var terminal = keypath[keypath.length - 1];
+ return (typeof terminal === 'number')
+ },
+
+ inObject: function(keypath) {
+ var terminal = keypath[keypath.length - 1];
+ return (typeof terminal === 'string')
+ },
+
+ splitDiff: function(diff) {
+ /* Split the stanzas in diff into an array of three arrays:
+ * [modifications, deletions, insertions]. */
+ var idx, objs = [], mods = [], dels = [], inss = [];
+ var dests = {3: inss, 1: dels}, stanza, keypath;
if (diff.length === 0) {return [[], diff];}
- diff.sort(function(a, b) {return b.length - a.length;});
for (idx = 0; idx < diff.length; idx++) {
- if (diff[idx].length === 1) {break;}
+ stanza = diff[idx]
+ if (stanza.length === 2) {
+ if (this.inObject(stanza[0])) {
+ objs.push(stanza);
+ } else {
+ mods.push(stanza);
+ }
+ } else {
+ dests[stanza.length].push(stanza)
+ }
}
- return [diff.slice(0, idx), diff.slice(idx)];
+ return [objs, mods, dels, inss];
+ },
+
+ stableKeypathLengthSort: function(stanzas) {
+ var comparator = function (a, b) {
+ var swap;
+ if (a[0].length === b[0].length) {
+ return a[0][0] - b[0][0];
+ }
+ return b[0].length - a[0].length;
+ }
+ for (var i = 0; i < stanzas.length; i++) {
+ stanzas[i][0].unshift(i)
+ }
+ stanzas.sort(comparator)
+ for (i = 0; i < stanzas.length; i++) {
+ stanzas[i][0].shift()
+ }
+ return stanzas
+ },
+
+ keypathCompare: function(a, b) {
+ a = a[0]; b = b[0];
+ if (a.length !== b.length) {
+ return a.length - b.length;
+ }
+ for (var i = 0; i < a.length; i++) {
+ if (typeof a[i] === 'number' && a[i] !== b[i]) {
+ return a[i] - b[i];
+ }
+ }
+ return 0;
+ },
+
+ keypathCompareReverse: function(a, b) {
+ a = a[0]; b = b[0];
+ if (a.length !== b.length) {
+ return b.length - a.length;
+ }
+ for (var i = 0; i < a.length; i++) {
+ if (typeof a[i] === 'number' && a[i] !== b[i]) {
+ return b[i] - a[i];
+ }
+ }
+ return 0;
},
sortStanzas: function(diff) {
- /* Sorts the stanzas in a diff: node changes can occur in any
- * order, but deletions from sequences have to happen last
+ /* Sorts the stanzas in a diff: object changes can occur in
+ * any order, but deletions from arrays have to happen last
* node first: ['foo', 'bar', 'baz'] -> ['foo', 'bar'] ->
- * ['foo'] -> [] and additions to sequences have to happen
+ * ['foo'] -> []; additions to sequences have to happen
* leftmost-node-first: [] -> ['foo'] -> ['foo', 'bar'] ->
- * ['foo', 'bar', 'baz']. */
-
- // First we divide the stanzas using splitDeletions():
- var split_thing = this.splitDeletions(diff);
- // Then we sort modifications in ascending order of last key:
- split_thing[0].sort(
- function(a, b) {return a[0].slice(-1)[0] - b[0].slice(-1)[0];}
- );
- // And deletions in descending order of last key:
- split_thing[1].sort(
- function(a, b) {return b[0].slice(-1)[0] - a[0].slice(-1)[0];}
+ * ['foo', 'bar', 'baz'], and insert-and-shift alterations to
+ * arrays must happen last. */
+
+ // First we divide the stanzas using splitDiff():
+ var split_thing = this.splitDiff(diff);
+ // Then we sort modifications of arrays in ascending order of keypath
+ // (note that we can’t tell appends from mods on the info available):
+ split_thing[1].sort(this.keypathCompare);
+ // Deletions from arrays in descending order of keypath:
+ split_thing[2].sort(this.keypathCompareReverse);
+ // And insert-and-shifts in ascending order of keypath:
+ split_thing[3].sort(this.keypathCompare)
+ diff = split_thing[0].concat(
+ split_thing[1], split_thing[2], split_thing[3]
);
- // And recombine:
- return split_thing[0].concat(split_thing[1]);
+ // Finally, we sort by length of keypath:
+ diff = this.stableKeypathLengthSort(diff, true)
+ return diff
},
computeKeysets: function(left, right) {
);
}
};
- var cand_funcs = [modify_cand, delete_cand, append_cand];
+
+ var insert_cand = function () {
+ if (col_i !== down_col) {
+ return lastrow[col_i].concat(
+ [[key.concat([right_i]), right_elem, "i"]]
+ );
+ }
+ };
+
+ var cand_funcs = [modify_cand, delete_cand, append_cand, insert_cand];
for (i = 0; i <= left.length; i++) {
lastrow.unshift([]);
for (right_i = 0; right_i < right.length; right_i++) {
right_elem = right[right_i];
- first_left_i = Math.min(right_i, left.length - 1);
- row = [];
- for (left_i = first_left_i; left_i < left.length; left_i++) {
+ row = []
+ for (left_i = 0; left_i < left.length; left_i++) {
left_elem = left[left_i];
col_i = left.length - left_i - 1;
win_length = Infinity;
else {
struc.splice(key[0], 1);
}
- }
+ } else if (diff.length === 3) {
+ if (struc.splice === undefined) {
+ struc[key[0]] = diff[1];
+ } else {
+ struc.splice(key[0], 0, diff[1]);
+ }
+ }
else {
struc[key[0]] = diff[1];
}
return struc;
}
};
+
+// node.js
+if (typeof exports !== 'undefined') exports.JSON_delta = JSON_delta;