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) {
68 case "sub":
69 s = s.slice(0, edit) + edit + s.slice(edit + 1);
70 break;
71 case "ins":
72 s = s.slice(0, edit) + edit + s.slice(edit);
73 break;
74 case "del":
75 s = s.slice(0, edit) + s.slice(edit + 1);
76 break;
77 }
78 }
79 return s;
80 }
82 function diffLerp(a, b, p) {
83 /** Interpolate between two strings based on edit distance
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 var NUMBERS = /(-?\d+(?:\.\d+)?)/g
98 function areNumericTwins(a, b) {
99 /** Check if a and b differ only in numerals
101 A leading "-" counts as part of numbers; a leading "+"
102 does not. Numbers may contain a single ".", but no other
103 floating point syntax.
104 */
105 return a.replace(NUMBERS, "0") === b.replace(NUMBERS, "0");
106 }
108 function nlerp(a, b, p) {
109 return a + (b - a) * p;
110 }
112 function numericLerp(a, b, p) {
113 /** Interpolate numerically between two strings containing numbers
115 Numbers may have a leading "-" and a single "." to mark
116 the decimal point, but something must be after the ".".
117 If both of the numbers in a pair are integers, the result
118 is clamped to an integer.
120 For example, numericLerp("0.0", "100", 0.123) === "12.3"
121 because the "." in "0.0" is intepreted as a decimal point.
122 But numericLerp("0.", "100.", 0.123) === "12." because the
123 strings are interpreted as integers followed by a full
124 stop.
126 Calling this functions on strings that differ in more than
127 numerals gives undefined results.
128 */
129 var aParts = a.split(NUMBERS);
130 var bParts = b.split(NUMBERS);
131 for (var i = 1; i < aParts.length; i += 2) {
132 var part = nlerp(+aParts[i], +bParts[i], p)
133 if (aParts[i].indexOf(".") === -1 && bParts[i].indexOf(".") === -1)
134 part = Math.round(part);
135 aParts[i] = part.toString();
136 }
137 return aParts.join("");
138 }
140 function fastLerp(a, b, p) {
141 /** Interpolate between two strings based on length
143 This interpolation algorithm progressively replaces the
144 front of one string with another. This approach is fast
145 but does not look good when the strings are similar.
146 */
147 var alen = Math.round(a.length * p);
148 var blen = Math.round(b.length * p);
149 return b.substring(0, blen) + a.substring(alen, a.length);
150 }
152 function lerp(a, b, p) {
153 /** Interpolate between two strings as best as possible
155 If the strings are identical aside from numbers in them,
156 they are passed through numericLerp.
158 If the strings are not numbers and short, they are passed
159 through diffLerp.
161 Otherwise, they are passed through fastLerp.
162 */
163 a = a.toString();
164 b = b.toString();
166 // Fast path for boundary cases.
167 if (p === 0) return a;
168 if (p === 1) return b;
170 if (areNumericTwins(a, b))
171 return numericLerp(a, b, p)
173 // Numeric lerps should over- and under-shoot when fed numbers
174 // outside 0 to 1, but other types cannot.
175 if (p < 0) return a;
176 if (p > 1) return b;
178 var n = a.length * b.length;
179 return (n && n < MAX_MATRIX_SIZE)
180 ? diffLerp(a, b, p)
181 : fastLerp(a, b, p);
182 }
184 exports.levenshteinMatrix = levenshteinMatrix;
185 exports.patch = patch;
186 exports.diff = diff;
187 exports.fastLerp = fastLerp;
188 exports.diffLerp = diffLerp;
189 exports.numericLerp = numericLerp;
190 exports.lerp = lerp;
192 })(typeof exports === "undefined" ? (this.stringLerp = {}) : exports);