zh/builder/src/zrender3/core/arrayDiff.js

// Hirschberg's algorithm
// http://en.wikipedia.org/wiki/Hirschberg%27s_algorithm

/**
 * @module zrender/core/arrayDiff
 * @author Yi Shen
 */
function defaultCompareFunc(a, b) {
  return a === b;
}

function createItem(cmd, idx, idx1) {
  var res = {
    // cmd explanation
    // '=': not change
    // '^': replace with a new item in second array. Unused temporary
    // '+': add a new item of second array
    // '-': del item in first array
    cmd: cmd,
    // Value index, use index in the first array
    // Except '+'. Adding a new item needs value in the second array
    idx: idx
  }; // Replace need to know both two indices
  // if (cmd === '^') {
  //     res.idx1 = idx1;
  // }

  if (cmd === '=') {
    res.idx1 = idx1;
  }

  return res;
}

function append(out, cmd, idx, idx1) {
  out.push(createItem(cmd, idx, idx1));
}

var abs = Math.abs; // Needleman-Wunsch score

function score(arr0, arr1, i0, i1, j0, j1, equal, memo) {
  var last;
  var invM = i0 > i1;
  var invN = j0 > j1;
  var m = abs(i1 - i0);
  var n = abs(j1 - j0);
  var i;
  var j;

  for (i = 0; i <= m; i++) {
    for (j = 0; j <= n; j++) {
      if (i === 0) {
        memo[j] = j;
      } else if (j === 0) {
        last = memo[j];
        memo[j] = i;
      } else {
        // memo[i-1][j-1] + same(arr0[i-1], arr1[j-1]) ? 0 : 1
        // Retained or replace
        var val0 = arr0[invM ? i0 - i : i - 1 + i0];
        var val1 = arr1[invN ? j0 - j : j - 1 + j0]; // Because replace is add after remove actually
        // It has a higher score than removing or adding
        // TODO custom score function

        var score0 = last + (equal(val0, val1) ? 0 : 2); // memo[i-1][j] + 1
        // Remove arr0[i-1]

        var score1 = memo[j] + 1; // memo[i][j-1] + 1
        // Add arr1[j-1]

        var score2 = memo[j - 1] + 1;
        last = memo[j];
        memo[j] = score0 < score1 ? score0 : score1;
        score2 < memo[j] && (memo[j] = score2); // Math min of three parameters seems slow
        // memo[j] = Math.min(score0, score1, score2);
      }
    }
  }

  return memo;
}

function hirschberg(arr0, arr1, i0, i1, j0, j1, equal, score0, score1) {
  var out = [];
  var len0 = i1 - i0;
  var len1 = j1 - j0;
  var i;
  var j;

  if (!len0) {
    for (j = 0; j < len1; j++) {
      append(out, '+', j + j0);
    }
  } else if (!len1) {
    for (i = 0; i < len0; i++) {
      append(out, '-', i + i0);
    }
  } else if (len0 === 1) {
    var a = arr0[i0];
    var matched = false;

    for (j = 0; j < len1; j++) {
      if (equal(a, arr1[j + j0]) && !matched) {
        matched = true; // Equal and update use the index in first array

        append(out, '=', i0, j + j0);
      } else {
        // if (j === len1 - 1 && ! matched) {
        //     append(out, '^', i0, j + j0);
        // }
        // else {
        append(out, '+', j + j0); // }
      }
    }

    if (!matched) {
      append(out, '-', i0);
    }
  } else if (len1 === 1) {
    var b = arr1[j0];
    var matched = false;

    for (i = 0; i < len0; i++) {
      if (equal(b, arr0[i + i0]) && !matched) {
        matched = true;
        append(out, '=', i + i0, j0);
      } else {
        // if (i === len0 - 1 && ! matched) {
        //     append(out, '^', i + i0, j0);
        // }
        // else {
        append(out, '-', i + i0); // }
      }
    }

    if (!matched) {
      append(out, '+', j0);
    }
  } else {
    var imid = (len0 / 2 | 0) + i0;
    score(arr0, arr1, i0, imid, j0, j1, equal, score0);
    score(arr0, arr1, i1, imid + 1, j1, j0, equal, score1);
    var min = Infinity;
    var jmid = 0;
    var sum;

    for (j = 0; j <= len1; j++) {
      sum = score0[j] + score1[len1 - j];

      if (sum < min) {
        min = sum;
        jmid = j;
      }
    }

    jmid += j0;
    out = hirschberg(arr0, arr1, i0, imid, j0, jmid, equal, score0, score1);
    var out1 = hirschberg(arr0, arr1, imid, i1, jmid, j1, equal, score0, score1); // Concat

    for (i = 0; i < out1.length; i++) {
      out.push(out1[i]);
    }
  }

  return out;
}

function arrayDiff(arr0, arr1, equal) {
  equal = equal || defaultCompareFunc; // Remove the common head and tail

  var i;
  var j;
  var len0 = arr0.length;
  var len1 = arr1.length;
  var lenMin = Math.min(len0, len1);
  var head = [];

  for (i = 0; i < lenMin; i++) {
    if (!equal(arr0[i], arr1[i])) {
      break;
    }

    append(head, '=', i, i);
  }

  for (j = 0; j < lenMin; j++) {
    if (!equal(arr0[len0 - j - 1], arr1[len1 - j - 1])) {
      break;
    }
  }

  if (len0 - j >= i || len1 - j >= i) {
    var middle = hirschberg(arr0, arr1, i, len0 - j, i, len1 - j, equal, [], []);

    for (i = 0; i < middle.length; i++) {
      head.push(middle[i]);
    }

    for (i = 0; i < j; i++) {
      append(head, '=', len0 - j + i, len1 - j + i);
    }
  }

  return head;
}

export default arrayDiff;