public/assets/knockout-3-4-0/src/binding/editDetection/compareArrays.js

   1 // Go through the items that have been added and deleted and try to find matches between them.
   2 ko.utils.findMovesInArrayComparison = function (left, right, limitFailedCompares) {
   3     if (left.length && right.length) {
   4         var failedCompares, l, r, leftItem, rightItem;
   5         for (failedCompares = l = 0; (!limitFailedCompares || failedCompares < limitFailedCompares) && (leftItem = left[l]); ++l) {
   6             for (r = 0; rightItem = right[r]; ++r) {
   7                 if (leftItem['value'] === rightItem['value']) {
   8                     leftItem['moved'] = rightItem['index'];
   9                     rightItem['moved'] = leftItem['index'];
  10                     right.splice(r, 1);         // This item is marked as moved; so remove it from right list
  11                     failedCompares = r = 0;     // Reset failed compares count because we're checking for consecutive failures
  12                     break;
  13                 }
  14             }
  15             failedCompares += r;
  16         }
  17     }
  18 };
  19
  20 ko.utils.compareArrays = (function () {
  21     var statusNotInOld = 'added', statusNotInNew = 'deleted';
  22
  23     // Simple calculation based on Levenshtein distance.
  24     function compareArrays(oldArray, newArray, options) {
  25         // For backward compatibility, if the third arg is actually a bool, interpret
  26         // it as the old parameter 'dontLimitMoves'. Newer code should use { dontLimitMoves: true }.
  27         options = (typeof options === 'boolean') ? { 'dontLimitMoves': options } : (options || {});
  28         oldArray = oldArray || [];
  29         newArray = newArray || [];
  30
  31         if (oldArray.length < newArray.length)
  32             return compareSmallArrayToBigArray(oldArray, newArray, statusNotInOld, statusNotInNew, options);
  33         else
  34             return compareSmallArrayToBigArray(newArray, oldArray, statusNotInNew, statusNotInOld, options);
  35     }
  36
  37     function compareSmallArrayToBigArray(smlArray, bigArray, statusNotInSml, statusNotInBig, options) {
  38         var myMin = Math.min,
  39             myMax = Math.max,
  40             editDistanceMatrix = [],
  41             smlIndex, smlIndexMax = smlArray.length,
  42             bigIndex, bigIndexMax = bigArray.length,
  43             compareRange = (bigIndexMax - smlIndexMax) || 1,
  44             maxDistance = smlIndexMax + bigIndexMax + 1,
  45             thisRow, lastRow,
  46             bigIndexMaxForRow, bigIndexMinForRow;
  47
  48         for (smlIndex = 0; smlIndex <= smlIndexMax; smlIndex++) {
  49             lastRow = thisRow;
  50             editDistanceMatrix.push(thisRow = []);
  51             bigIndexMaxForRow = myMin(bigIndexMax, smlIndex + compareRange);
  52             bigIndexMinForRow = myMax(0, smlIndex - 1);
  53             for (bigIndex = bigIndexMinForRow; bigIndex <= bigIndexMaxForRow; bigIndex++) {
  54                 if (!bigIndex)
  55                     thisRow[bigIndex] = smlIndex + 1;
  56                 else if (!smlIndex)  // Top row - transform empty array into new array via additions
  57                     thisRow[bigIndex] = bigIndex + 1;
  58                 else if (smlArray[smlIndex - 1] === bigArray[bigIndex - 1])
  59                     thisRow[bigIndex] = lastRow[bigIndex - 1];                  // copy value (no edit)
  60                 else {
  61                     var northDistance = lastRow[bigIndex] || maxDistance;       // not in big (deletion)
  62                     var westDistance = thisRow[bigIndex - 1] || maxDistance;    // not in small (addition)
  63                     thisRow[bigIndex] = myMin(northDistance, westDistance) + 1;
  64                 }
  65             }
  66         }
  67
  68         var editScript = [], meMinusOne, notInSml = [], notInBig = [];
  69         for (smlIndex = smlIndexMax, bigIndex = bigIndexMax; smlIndex || bigIndex;) {
  70             meMinusOne = editDistanceMatrix[smlIndex][bigIndex] - 1;
  71             if (bigIndex && meMinusOne === editDistanceMatrix[smlIndex][bigIndex-1]) {
  72                 notInSml.push(editScript[editScript.length] = {     // added
  73                     'status': statusNotInSml,
  74                     'value': bigArray[--bigIndex],
  75                     'index': bigIndex });
  76             } else if (smlIndex && meMinusOne === editDistanceMatrix[smlIndex - 1][bigIndex]) {
  77                 notInBig.push(editScript[editScript.length] = {     // deleted
  78                     'status': statusNotInBig,
  79                     'value': smlArray[--smlIndex],
  80                     'index': smlIndex });
  81             } else {
  82                 --bigIndex;
  83                 --smlIndex;
  84                 if (!options['sparse']) {
  85                     editScript.push({
  86                         'status': "retained",
  87                         'value': bigArray[bigIndex] });
  88                 }
  89             }
  90         }
  91
  92         // Set a limit on the number of consecutive non-matching comparisons; having it a multiple of
  93         // smlIndexMax keeps the time complexity of this algorithm linear.
  94         ko.utils.findMovesInArrayComparison(notInBig, notInSml, !options['dontLimitMoves'] && smlIndexMax * 10);
  95
  96         return editScript.reverse();
  97     }
  98
  99     return compareArrays;
 100 })();
 101
 102 ko.exportSymbol('utils.compareArrays', ko.utils.compareArrays);