arrayDiff2.js

// 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;