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