// ... preprocess such that arr1 is always the shorter array
var myMin = Math.min,
  myMax = Math.max,
  editDistanceMatrix = [],
  smlIndex, smlIndexMax = smlArray.length,
  bigIndex, bigIndexMax = bigArray.length,
  compareRange = (bigIndexMax - smlIndexMax) || 1,
  maxDistance = smlIndexMax + bigIndexMax + 1,
  thisRow, lastRow,
  bigIndexMaxForRow, bigIndexMinForRow;

for (smlIndex = 0; smlIndex <= smlIndexMax; smlIndex++) {
  lastRow = thisRow;
  editDistanceMatrix.push(thisRow = []);
  bigIndexMaxForRow = myMin(bigIndexMax, smlIndex + compareRange);
  bigIndexMinForRow = myMax(0, smlIndex - 1);
  for (bigIndex = bigIndexMinForRow; bigIndex <= bigIndexMaxForRow; bigIndex++) {
    if (!bigIndex)
      thisRow[bigIndex] = smlIndex + 1;
    else if (!smlIndex) // Top row - transform empty array into new array via additions
      thisRow[bigIndex] = bigIndex + 1;
    else if (smlArray[smlIndex - 1] === bigArray[bigIndex - 1])
      thisRow[bigIndex] = lastRow[bigIndex - 1];         // copy value (no edit)
    else {
      var northDistance = lastRow[bigIndex] || maxDistance;    // not in big (deletion)
      var westDistance = thisRow[bigIndex - 1] || maxDistance;  // not in small (addition)
      thisRow[bigIndex] = myMin(northDistance, westDistance) + 1;
    }
  }
}
// editDistanceMatrix now stores the result

// ... continue from the edit distance computation
var editScript = [], meMinusOne, notInSml = [], notInBig = [];
for (smlIndex = smlIndexMax, bigIndex = bigIndexMax; smlIndex || bigIndex;) {
  meMinusOne = editDistanceMatrix[smlIndex][bigIndex] - 1;
  if (bigIndex && meMinusOne === editDistanceMatrix[smlIndex][bigIndex-1]) {
    notInSml.push(editScript[editScript.length] = {   // added
      'status': statusNotInSml,
      'value': bigArray[--bigIndex],
      'index': bigIndex });
  } else if (smlIndex && meMinusOne === editDistanceMatrix[smlIndex - 1][bigIndex]) {
    notInBig.push(editScript[editScript.length] = {   // deleted
      'status': statusNotInBig,
      'value': smlArray[--smlIndex],
      'index': smlIndex });
  } else {
    --bigIndex;
    --smlIndex;
    if (!options['sparse']) {
      editScript.push({
        'status': "retained",
        'value': bigArray[bigIndex] });
    }
  }
}
// editScript has the (reversed) sequence of actions

// left is all the operations of "Add"
// right is all the operations of "Delete
if (left.length && right.length) {
  var failedCompares, l, r, leftItem, rightItem;
  for (failedCompares = l = 0; (!limitFailedCompares || failedCompares < limitFailedCompares) && (leftItem = left[l]); ++l) {
    for (r = 0; rightItem = right[r]; ++r) {
      if (leftItem['value'] === rightItem['value']) {
        leftItem['moved'] = rightItem['index'];
        rightItem['moved'] = leftItem['index'];
        right.splice(r, 1);     // This item is marked as moved; so remove it from right list
        failedCompares = r = 0;   // Reset failed compares count because we're checking for consecutive failures
        break;
      }
    }
    failedCompares += r;
  }
}
// Operations that can be optimized to "Move" will be marked with the "moved" property