1 (function (exports) {
2 "use strict";
4 var MAX_MATRIX_SIZE = 256 * 256;
6 function createMatrix(i, j) {
7 return new Uint32Array(i * j);
8 }
10 function levenshteinMatrix(s, t) {
11 /** Calculate the Levenshtein edit distance matrix for two strings
13 The matrix is returned as a flat unsigned typed array.
15 Following http://en.wikipedia.org/wiki/Levenshtein_distance
16 */
17 var m = s.length + 1;
18 var n = t.length + 1;
19 var d = createMatrix(m, n);
20 var i, j;
21 for (i = 1; i < m; ++i)
22 d[n * i] = i;
23 for (j = 1; j < n; ++j)
24 d[j] = j;
25 for (j = 1; j < n; ++j)
26 for (i = 1; i < m; ++i)
27 if (s[i - 1] === t[j - 1])
28 d[n * i + j] = d[n * (i - 1) + j - 1];
29 else
30 d[n * i + j] = 1 + Math.min(d[n * (i - 1) + j ],
31 d[n * i + j - 1],
32 d[n * (i - 1) + j - 1]);
33 return d;
34 }
36 function editPath(d, s, t) {
37 /** Given a Levenshtein result matrix, trace the shortest edit */
38 var path = []
39 var i = s.length;
40 var j = t.length;
41 var n = j + 1;
42 while (i || j) {
43 var sub = (i && j) ? d[n * (i - 1) + j - 1] : Infinity;
44 var del = i ? d[n * (i - 1) + j] : Infinity;
45 var ins = j ? d[n * i + j - 1] : Infinity;
46 if (sub <= ins && sub <= del) {
47 if (d[n * i + j] !== d[n * (i - 1) + j - 1])
48 path.push(["sub", i - 1, t[j - 1]]);
49 --i; --j;
50 } else if (ins <= del) {
51 path.push(["ins", i, t[j - 1]]);
52 --j;
53 } else {
54 path.push(["del", i - 1]);
55 --i;
56 }
57 }
58 return path;
59 }
61 function applyEdits(edits, s) {
62 /** Apply the list of edits to s */
63 var i;
64 for (i = 0; i < edits.length; ++i) {
65 var edit = edits[i];
66 switch (edit[0]) {
67 case "sub":
68 s = s.slice(0, edit[1]) + edit[2] + s.slice(edit[1] + 1);
69 break;
70 case "ins":
71 s = s.slice(0, edit[1]) + edit[2] + s.slice(edit[1]);
72 break;
73 case "del":
74 s = s.slice(0, edit[1]) + s.slice(edit[1] + 1);
75 break;
76 }
77 }
78 return s;
79 }
81 function slowLerp(a, b, p) {
82 /** Interpolate between two strings slowly
84 This interpolation algorithm applys a partial edit of one
85 string into the other. This produces nice looking results,
86 but can take a significant amount of time and memory to
87 compute the edits. It is not recommended for strings
88 longer than a few hundred characters.
89 */
90 var edits = editPath(levenshteinMatrix(a, b), a, b);
91 var partial = edits.slice(0, Math.round(p * edits.length));
92 return applyEdits(partial, a);
93 }
95 function fastLerp(a, b, p) {
96 /** Interpolate between two strings very quickly
98 This interpolation algorithm progressively replaces the
99 front of one string with another. This approach is fast
100 but does not look good when the strings are similar.
101 */
102 var alen = Math.round(a.length * p);
103 var blen = Math.round(b.length * p);
104 return b.substring(0, blen) + a.substring(alen, a.length);
105 }
107 function lerp(a, b, p) {
108 a = a.toString();
109 b = b.toString();
110 var n = a.length * b.length;
111 // TODO: if both strings are integers, do an integer lerp.
112 // TODO: if both strings are numbers, do a numeric lerp.
113 return (n && n < MAX_MATRIX_SIZE)
114 ? slowLerp(a, b, p)
115 : fastLerp(a, b, p);
116 }
118 exports.levenshteinMatrix = levenshteinMatrix;
119 exports.editPath = editPath;
120 exports.fastLerp = fastLerp;
121 exports.slowLerp = slowLerp;
122 exports.applyEdits = applyEdits;
123 exports.lerp = lerp;
125 })(typeof exports === "undefined" ? (this.stringLerp = {}) : exports);