highlightDifferences function

(List<Span>, List<Span>) highlightDifferences(String oldText, String newText)

Produce a pair of Span lists highlighting character-level differences between oldText and newText.

Implementation

(List<Span>, List<Span>) highlightDifferences(String oldText, String newText) {
  final oldChars = oldText.split('');
  final newChars = newText.split('');

  // LCS for alignment
  final m = oldChars.length;
  final n = newChars.length;
  final dp = List.generate(m + 1, (_) => List.filled(n + 1, 0));
  for (var i = 1; i <= m; i++) {
    for (var j = 1; j <= n; j++) {
      if (oldChars[i - 1] == newChars[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1;
      } else {
        dp[i][j] = math.max(dp[i - 1][j], dp[i][j - 1]);
      }
    }
  }

  // Backtrack to find common characters
  final oldHighlight = List.filled(m, true);
  final newHighlight = List.filled(n, true);
  var i = m, j = n;
  while (i > 0 && j > 0) {
    if (oldChars[i - 1] == newChars[j - 1]) {
      oldHighlight[i - 1] = false;
      newHighlight[j - 1] = false;
      i--;
      j--;
    } else if (dp[i - 1][j] >= dp[i][j - 1]) {
      i--;
    } else {
      j--;
    }
  }

  // Build spans by grouping consecutive same-highlight characters
  List<Span> buildSpans(List<String> chars, List<bool> highlights) {
    if (chars.isEmpty) return [];
    final spans = <Span>[];
    var buf = StringBuffer(chars[0]);
    var hl = highlights[0];
    for (var k = 1; k < chars.length; k++) {
      if (highlights[k] == hl) {
        buf.write(chars[k]);
      } else {
        spans.add(Span(buf.toString(), isHighlighted: hl));
        buf = StringBuffer(chars[k]);
        hl = highlights[k];
      }
    }
    spans.add(Span(buf.toString(), isHighlighted: hl));
    return spans;
  }

  return (
    buildSpans(oldChars, oldHighlight),
    buildSpans(newChars, newHighlight),
  );
}