codesandbox-client/standalone-packages/codesandbox-browserfs/src/core/levenshtein.ts at add/code-change-api · hipertracker/codesandbox-client · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
/*
 * Levenshtein distance, from the `js-levenshtein` NPM module.
 * Copied here to avoid complexity of adding another CommonJS module dependency.
 */

function _min(d0: number, d1: number, d2: number, bx: number, ay: number): number {
  return d0 < d1 || d2 < d1
      ? d0 > d2
          ? d2 + 1
          : d0 + 1
      : bx === ay
          ? d1
          : d1 + 1;
}

/**
 * Calculates levenshtein distance.
 * @param a
 * @param b
 */
export default function levenshtein(a: string, b: string): number {
  if (a === b) {
    return 0;
  }

  if (a.length > b.length) {
    const tmp = a;
    a = b;
    b = tmp;
  }

  let la = a.length;
  let lb = b.length;

  while (la > 0 && (a.charCodeAt(la - 1) === b.charCodeAt(lb - 1))) {
    la--;
    lb--;
  }

  let offset = 0;

  while (offset < la && (a.charCodeAt(offset) === b.charCodeAt(offset))) {
    offset++;
  }

  la -= offset;
  lb -= offset;

  if (la === 0 || lb === 1) {
    return lb;
  }

  const vector = new Array<number>(la << 1);

  for (let y = 0; y < la;) {
    vector[la + y] = a.charCodeAt(offset + y);
    vector[y] = ++y;
  }

  let x: number;
  let d0: number;
  let d1: number;
  let d2: number;
  let d3: number;
  for (x = 0; (x + 3) < lb;) {
    const bx0 = b.charCodeAt(offset + (d0 = x));
    const bx1 = b.charCodeAt(offset + (d1 = x + 1));
    const bx2 = b.charCodeAt(offset + (d2 = x + 2));
    const bx3 = b.charCodeAt(offset + (d3 = x + 3));
    let dd = (x += 4);
    for (let y = 0; y < la;) {
      const ay = vector[la + y];
      const dy = vector[y];
      d0 = _min(dy, d0, d1, bx0, ay);
      d1 = _min(d0, d1, d2, bx1, ay);
      d2 = _min(d1, d2, d3, bx2, ay);
      dd = _min(d2, d3, dd, bx3, ay);
      vector[y++] = dd;
      d3 = d2;
      d2 = d1;
      d1 = d0;
      d0 = dy;
    }
  }

  let dd: number = 0;
  for (; x < lb;) {
    const bx0 = b.charCodeAt(offset + (d0 = x));
    dd = ++x;
    for (let y = 0; y < la; y++) {
      const dy = vector[y];
      vector[y] = dd = dy < d0 || dd < d0
          ? dy > dd ? dd + 1 : dy + 1
          : bx0 === vector[la + y]
              ? d0
              : d0 + 1;
      d0 = dy;
    }
  }

  return dd;
}