findLongestMatch method

Match findLongestMatch({ int sourceStart = 0, int? sourceEnd, int targetStart = 0, int? targetEnd, })

Finds the longest matching block in the provided ranges.

Implementation

Match findLongestMatch({
  int sourceStart = 0,
  int? sourceEnd,
  int targetStart = 0,
  int? targetEnd,
}) {
  sourceEnd ??= _source.length;
  targetEnd ??= _target.length;
  // Find longest junk-free match.
  var bestSource = sourceStart, bestTarget = targetStart, bestLength = 0;
  var targetLengths = <int, int>{};
  for (var s = sourceStart; s < sourceEnd; s++) {
    final newTargetLengths = <int, int>{};
    for (final t in _targetIndices[_source[s]]) {
      if (t < targetStart) continue;
      if (t >= targetEnd) break;
      final targetLength = (targetLengths[t - 1] ?? 0) + 1;
      if (targetLength > bestLength) {
        bestSource = s - targetLength + 1;
        bestTarget = t - targetLength + 1;
        bestLength = targetLength;
      }
      newTargetLengths[t] = targetLength;
    }
    targetLengths = newTargetLengths;
  }
  // Extend the best by non-junk elements on each end.
  while (bestSource > sourceStart &&
      bestTarget > targetStart &&
      !_targetJunk.contains(_target[bestTarget - 1]) &&
      _source[bestSource - 1] == _target[bestTarget - 1]) {
    bestSource--;
    bestTarget--;
    bestLength++;
  }
  while (bestSource + bestLength < sourceEnd &&
      bestTarget + bestLength < targetEnd &&
      !_targetJunk.contains(_target[bestTarget + bestLength]) &&
      _source[bestSource + bestLength] == _target[bestTarget + bestLength]) {
    bestLength++;
  }
  // Extend matching junk on each side.
  while (bestSource > sourceStart &&
      bestTarget > targetStart &&
      _targetJunk.contains(_target[bestTarget - 1]) &&
      _source[bestSource - 1] == _target[bestTarget - 1]) {
    bestSource--;
    bestTarget--;
    bestLength++;
  }
  while (bestSource + bestLength < sourceEnd &&
      bestTarget + bestLength < targetEnd &&
      _targetJunk.contains(_target[bestTarget + bestLength]) &&
      _source[bestSource + bestLength] == _target[bestTarget + bestLength]) {
    bestLength++;
  }
  return Match(
    sourceStart: bestSource,
    targetStart: bestTarget,
    length: bestLength,
  );
}