1 (function (exports) {
2 "use strict";
4 var MAX_MATRIX_SIZE = 256 * 256;
6 function repeat(n, v) {
7 var r = [];
8 while (n--)
9 r.push(v);
10 return r;
11 }
13 function createMatrix(i, j) {
14 var m = [];
15 while (i--)
16 m.push(repeat(j, 0));
17 return m;
18 }
20 function levenshteinMatrix(s, t) {
21 /** Calculate the Levenshtein edit distance matrix for two strings
23 // Following http://en.wikipedia.org/wiki/Levenshtein_distance
24 */
25 var m = s.length + 1;
26 var n = t.length + 1;
27 var d = createMatrix(m, n);
28 var i, j;
29 for (i = 1; i < m; ++i)
30 d[i][0] = i;
31 for (j = 1; j < n; ++j)
32 d[0][j] = j;
33 for (j = 1; j < n; ++j)
34 for (i = 1; i < m; ++i)
35 if (s[i - 1] === t[j - 1])
36 d[i][j] = d[i - 1][j - 1];
37 else
38 d[i][j] = 1 + Math.min(d[i - 1][ j ],
39 d[ i ][j - 1],
40 d[i - 1][j - 1]);
41 return d;
42 }
44 function editPath(m, s, t) {
45 var path = []
46 var i = s.length;
47 var j = t.length;
48 while (i || j) {
49 var sub = (i && j) ? m[i - 1][j - 1] : Infinity;
50 var del = i ? m[i - 1][j] : Infinity;
51 var ins = j ? m[i][j - 1] : Infinity;
52 if (sub <= ins && sub <= del) {
53 if (m[i][j] !== m[i - 1][j - 1])
54 path.push(["sub", i - 1, t[j - 1]]);
55 --i; --j;
56 } else if (ins <= del) {
57 path.push(["ins", i, t[j - 1]]);
58 --j;
59 } else {
60 path.push(["del", i - 1]);
61 --i;
62 }
63 }
64 return path;
65 }
67 function applyEdits(edits, s, t) {
68 var i;
69 for (i = 0; i < edits.length; ++i) {
70 var edit = edits[i];
71 switch (edit[0]) {
72 case "sub":
73 s = s.slice(0, edit[1]) + edit[2] + s.slice(edit[1] + 1);
74 break;
75 case "ins":
76 s = s.slice(0, edit[1]) + edit[2] + s.slice(edit[1]);
77 break;
78 case "del":
79 s = s.slice(0, edit[1]) + s.slice(edit[1] + 1);
80 break;
81 }
82 }
83 return s;
84 }
86 function slowLerp(a, b, p) {
87 var m = levenshteinMatrix(a, b);
88 var edits = editPath(m, a, b);
89 var partial = edits.slice(0, Math.round(p * edits.length));
90 return applyEdits(partial, a, b);
91 }
93 function fastLerp(a, b, p) {
94 var alen = Math.round(a.length * p);
95 var blen = Math.round(b.length * p);
96 return b.substring(0, blen) + a.substring(alen, a.length);
97 }
99 function lerp(a, b, p) {
100 a = a.toString();
101 b = b.toString();
102 var n = a.length * b.length;
103 return (n && n < MAX_MATRIX_SIZE)
104 ? slowLerp(a, b, p)
105 : fastLerp(a, b, p);
106 }
108 exports.levenshteinMatrix = levenshteinMatrix;
109 exports.editPath = editPath;
110 exports.fastLerp = fastLerp;
111 exports.slowLerp = slowLerp;
112 exports.applyEdits = applyEdits;
113 exports.lerp = lerp;
115 })(typeof exports === "undefined" ? (this.stringLerp = {}) : exports);