// Myers' Diff Algorithm
|
// Modified from https://github.com/kpdecker/jsdiff/blob/master/src/diff/base.js
|
function Diff() {}
|
|
Diff.prototype = {
|
diff: function (oldArr, newArr, equals) {
|
if (!equals) {
|
equals = function (a, b) {
|
return a === b;
|
};
|
}
|
|
this.equals = equals;
|
var self = this;
|
oldArr = oldArr.slice();
|
newArr = newArr.slice(); // Allow subclasses to massage the input prior to running
|
|
var newLen = newArr.length;
|
var oldLen = oldArr.length;
|
var editLength = 1;
|
var maxEditLength = newLen + oldLen;
|
var bestPath = [{
|
newPos: -1,
|
components: []
|
}]; // Seed editLength = 0, i.e. the content starts with the same values
|
|
var oldPos = this.extractCommon(bestPath[0], newArr, oldArr, 0);
|
|
if (bestPath[0].newPos + 1 >= newLen && oldPos + 1 >= oldLen) {
|
var indices = [];
|
|
for (var i = 0; i < newArr.length; i++) {
|
indices.push(i);
|
} // Identity per the equality and tokenizer
|
|
|
return [{
|
indices: indices,
|
count: newArr.length
|
}];
|
} // Main worker method. checks all permutations of a given edit length for acceptance.
|
|
|
function execEditLength() {
|
for (var diagonalPath = -1 * editLength; diagonalPath <= editLength; diagonalPath += 2) {
|
var basePath;
|
var addPath = bestPath[diagonalPath - 1];
|
var removePath = bestPath[diagonalPath + 1];
|
var oldPos = (removePath ? removePath.newPos : 0) - diagonalPath;
|
|
if (addPath) {
|
// No one else is going to attempt to use this value, clear it
|
bestPath[diagonalPath - 1] = undefined;
|
}
|
|
var canAdd = addPath && addPath.newPos + 1 < newLen;
|
var canRemove = removePath && 0 <= oldPos && oldPos < oldLen;
|
|
if (!canAdd && !canRemove) {
|
// If this path is a terminal then prune
|
bestPath[diagonalPath] = undefined;
|
continue;
|
} // Select the diagonal that we want to branch from. We select the prior
|
// path whose position in the new string is the farthest from the origin
|
// and does not pass the bounds of the diff graph
|
|
|
if (!canAdd || canRemove && addPath.newPos < removePath.newPos) {
|
basePath = clonePath(removePath);
|
self.pushComponent(basePath.components, undefined, true);
|
} else {
|
basePath = addPath; // No need to clone, we've pulled it from the list
|
|
basePath.newPos++;
|
self.pushComponent(basePath.components, true, undefined);
|
}
|
|
oldPos = self.extractCommon(basePath, newArr, oldArr, diagonalPath); // If we have hit the end of both strings, then we are done
|
|
if (basePath.newPos + 1 >= newLen && oldPos + 1 >= oldLen) {
|
return buildValues(self, basePath.components, newArr, oldArr);
|
} else {
|
// Otherwise track this path as a potential candidate and continue.
|
bestPath[diagonalPath] = basePath;
|
}
|
}
|
|
editLength++;
|
}
|
|
while (editLength <= maxEditLength) {
|
var ret = execEditLength();
|
|
if (ret) {
|
return ret;
|
}
|
}
|
},
|
pushComponent: function (components, added, removed) {
|
var last = components[components.length - 1];
|
|
if (last && last.added === added && last.removed === removed) {
|
// We need to clone here as the component clone operation is just
|
// as shallow array clone
|
components[components.length - 1] = {
|
count: last.count + 1,
|
added: added,
|
removed: removed
|
};
|
} else {
|
components.push({
|
count: 1,
|
added: added,
|
removed: removed
|
});
|
}
|
},
|
extractCommon: function (basePath, newArr, oldArr, diagonalPath) {
|
var newLen = newArr.length;
|
var oldLen = oldArr.length;
|
var newPos = basePath.newPos;
|
var oldPos = newPos - diagonalPath;
|
var commonCount = 0;
|
|
while (newPos + 1 < newLen && oldPos + 1 < oldLen && this.equals(newArr[newPos + 1], oldArr[oldPos + 1])) {
|
newPos++;
|
oldPos++;
|
commonCount++;
|
}
|
|
if (commonCount) {
|
basePath.components.push({
|
count: commonCount
|
});
|
}
|
|
basePath.newPos = newPos;
|
return oldPos;
|
},
|
tokenize: function (value) {
|
return value.slice();
|
},
|
join: function (value) {
|
return value.slice();
|
}
|
};
|
|
function buildValues(diff, components, newArr, oldArr) {
|
var componentPos = 0;
|
var componentLen = components.length;
|
var newPos = 0;
|
var oldPos = 0;
|
|
for (; componentPos < componentLen; componentPos++) {
|
var component = components[componentPos];
|
|
if (!component.removed) {
|
var indices = [];
|
|
for (var i = newPos; i < newPos + component.count; i++) {
|
indices.push(i);
|
}
|
|
component.indices = indices;
|
newPos += component.count; // Common case
|
|
if (!component.added) {
|
oldPos += component.count;
|
}
|
} else {
|
var indices = [];
|
|
for (var i = oldPos; i < oldPos + component.count; i++) {
|
indices.push(i);
|
}
|
|
component.indices = indices;
|
oldPos += component.count;
|
}
|
}
|
|
return components;
|
}
|
|
function clonePath(path) {
|
return {
|
newPos: path.newPos,
|
components: path.components.slice(0)
|
};
|
}
|
|
var arrayDiff = new Diff();
|
|
function _default(oldArr, newArr, callback) {
|
return arrayDiff.diff(oldArr, newArr, callback);
|
}
|
|
module.exports = _default;
|
