getEditOps static method

List<EditOp> getEditOps(String s1, String s2)

Implementation

static List<EditOp> getEditOps(String s1, String s2) {
  var len1 = s1.length;
  var len2 = s2.length;

  int len1o, len2o;
  int i;

  List<int> matrix;

  var c1 = s1.codeUnits.toList();
  var c2 = s2.codeUnits.toList();

  var p1 = 0;
  var p2 = 0;

  len1o = 0;

  while (len1 > 0 && len2 > 0 && c1[p1] == c2[p2]) {
    len1--;
    len2--;

    p1++;
    p2++;

    len1o++;
  }

  len2o = len1o;

  // strip common prefix
  while (len1 > 0 && len2 > 0 && c1[p1 + len1 - 1] == c2[p2 + len2 - 1]) {
    len1--;
    len2--;
  }

  len1++;
  len2++;

  matrix = List.filled(len2 * len1, 0);

  for (i = 0; i < len2; i++) {
    matrix[i] = i;
  }

  for (i = 1; i < len1; i++) {
    matrix[len2 * i] = i;
  }

  for (i = 1; i < len1; i++) {
    var ptrPrev = (i - 1) * len2;
    var ptrC = i * len2;
    var ptrEnd = ptrC + len2 - 1;

    var char1 = c1[p1 + i - 1];
    var ptrChar2 = p2;

    var x = i;

    ptrC++;

    while (ptrC <= ptrEnd) {
      var c3 = matrix[ptrPrev++] + (char1 != c2[ptrChar2++] ? 1 : 0);
      x++;

      if (x > c3) {
        x = c3;
      }

      c3 = matrix[ptrPrev] + 1;

      if (x > c3) {
        x = c3;
      }

      matrix[ptrC++] = x;
    }
  }

  return _editOpsFromCostMatrix(
      len1, c1, p1, len1o, len2, c2, p2, len2o, matrix);
}