shortestEditScript<T> function

List<EditOp> shortestEditScript<T>(List<T> a, List<T> b)

Compute the shortest edit script (Myers' algorithm simplified).

Implementation

List<EditOp> shortestEditScript<T>(List<T> a, List<T> b) {
  final m = a.length;
  final n = b.length;
  final max = m + n;
  if (max == 0) return [];

  // V array indexed from -max to max
  final v = List.filled(2 * max + 1, 0);
  final trace = <List<int>>[];

  int idx(int k) => k + max;

  outer:
  for (var d = 0; d <= max; d++) {
    trace.add(List.of(v));
    for (var k = -d; k <= d; k += 2) {
      int x;
      if (k == -d || (k != d && v[idx(k - 1)] < v[idx(k + 1)])) {
        x = v[idx(k + 1)];
      } else {
        x = v[idx(k - 1)] + 1;
      }
      var y = x - k;
      while (x < m && y < n && a[x] == b[y]) {
        x++;
        y++;
      }
      v[idx(k)] = x;
      if (x >= m && y >= n) break outer;
    }
  }

  // Backtrack through trace to build edit script
  final ops = <EditOp>[];
  var x = m, y = n;
  for (var d = trace.length - 1; d > 0; d--) {
    final prev = trace[d - 1];
    final k = x - y;
    int prevK;
    if (k == -d || (k != d && prev[idx(k - 1)] < prev[idx(k + 1)])) {
      prevK = k + 1;
    } else {
      prevK = k - 1;
    }
    final prevX = prev[idx(prevK)];
    final prevY = prevX - prevK;

    // Diagonal moves (equals)
    while (x > prevX && y > prevY) {
      x--;
      y--;
      ops.add(EditOp.equal);
    }
    if (k == prevK + 1) {
      // Deletion
      x--;
      ops.add(EditOp.delete);
    } else {
      // Insertion
      y--;
      ops.add(EditOp.insert);
    }
  }
  // Remaining diagonal
  while (x > 0 && y > 0) {
    x--;
    y--;
    ops.add(EditOp.equal);
  }

  return ops.reversed.toList();
}