levEditDistance static method

int levEditDistance(String s1, String s2, int xcost)

Implementation

static int levEditDistance(String s1, String s2, int xcost) {
  int i;
  int half;
  var c1 = s1.codeUnits.toList();
  var c2 = s2.codeUnits.toList();
  var str1 = 0;
  var str2 = 0;
  var len1 = s1.length;
  var len2 = s2.length;
  while (((len1 > 0) && (len2 > 0)) && (c1[str1] == c2[str2])) {
    len1--;
    len2--;
    str1++;
    str2++;
  }
  while (((len1 > 0) && (len2 > 0)) &&
      (c1[(str1 + len1) - 1] == c2[(str2 + len2) - 1])) {
    len1--;
    len2--;
  }
  if (len1 == 0) {
    return len2;
  }
  if (len2 == 0) {
    return len1;
  }
  if (len1 > len2) {
    var nx = len1;
    var temp = str1;
    len1 = len2;
    len2 = nx;
    str1 = str2;
    str2 = temp;
    var t = c2;
    c2 = c1;
    c1 = t;
  }
  if (len1 == 1) {
    if (xcost != 0) {
      return (len2 + 1) - (2 * _memchr(c2, str2, c1[str1], len2));
    } else {
      return len2 - _memchr(c2, str2, c1[str1], len2);
    }
  }
  len1++;
  len2++;
  half = (len1 >> 1);
  var row = List<int>.filled(len2, 0);
  var end = (len2 - 1);
  for ((i = 0); i < (len2 - ((xcost != 0) ? 0 : half)); i++) {
    row[i] = i;
  }
  if (xcost != 0) {
    for ((i = 1); i < len1; i++) {
      var p = 1;
      var ch1 = c1[(str1 + i) - 1];
      var c2p = str2;
      var D = i;
      var x = i;
      while (p <= end) {
        if (ch1 == c2[c2p++]) {
          x = (--D);
        } else {
          x++;
        }
        D = row[p];
        D++;
        if (x > D) {
          x = D;
        }
        row[p++] = x;
      }
    }
  } else {
    row[0] = ((len1 - half) - 1);
    for ((i = 1); i < len1; i++) {
      int p;
      var ch1 = c1[(str1 + i) - 1];
      int c2p;
      int D;
      int x;
      if (i >= (len1 - half)) {
        var offset = (i - (len1 - half));
        int c3;
        c2p = (str2 + offset);
        p = offset;
        c3 = (row[p++] + ((ch1 != c2[c2p++]) ? 1 : 0));
        x = row[p];
        x++;
        D = x;
        if (x > c3) {
          x = c3;
        }
        row[p++] = x;
      } else {
        p = 1;
        c2p = str2;
        D = (x = i);
      }
      if (i <= (half + 1)) {
        end = (((len2 + i) - half) - 2);
      }
      while (p <= end) {
        var c3 = ((--D) + ((ch1 != c2[c2p++]) ? 1 : 0));
        x++;
        if (x > c3) {
          x = c3;
        }
        D = row[p];
        D++;
        if (x > D) {
          x = D;
        }
        row[p++] = x;
      }
      if (i <= half) {
        var c3 = ((--D) + ((ch1 != c2[c2p]) ? 1 : 0));
        x++;
        if (x > c3) {
          x = c3;
        }
        row[p] = x;
      }
    }
  }
  i = row[end];
  return i;
}