1 /* string-lerp - progressively turn one string into another
2 Copyright 2014 Joe Wreschnig
4 This program is free software; you can redistribute it and/or modify
5 it under the terms of the GNU General Public License as published by
6 the Free Software Foundation; either version 2 of the License, or
7 (at your option) any later version.
10 /* @license Copyright 2014 Joe Wreschnig - GNU GPL v2 or later */
15 var MAX_MATRIX_SIZE
= 256 * 256;
17 function levenshteinMatrix(s
, t
, ins
, del
, sub
) {
18 /** Calculate the Levenshtein edit distance matrix for two strings
20 The matrix is returned as a flat typed array.
22 Following http://en.wikipedia.org/wiki/Levenshtein_distance
26 var d
= new Uint32Array(m
* n
);
28 for (i
= 1; i
< m
; ++i
)
30 for (j
= 1; j
< n
; ++j
)
32 for (j
= 1; j
< n
; ++j
)
33 for (i
= 1; i
< m
; ++i
)
34 if (s
[i
- 1] === t
[j
- 1])
35 d
[n
* i
+ j
] = d
[n
* (i
- 1) + j
- 1];
37 d
[n
* i
+ j
] = Math
.min(del
+ d
[n
* (i
- 1) + j
],
38 ins
+ d
[n
* i
+ j
- 1],
39 sub
+ d
[n
* (i
- 1) + j
- 1]);
43 function editPath(d
, t
) {
44 /** Given a Levenshtein matrix and target, create an edit list */
48 var i
= d
.length
/ n
- 1;
50 var sub
= (i
&& j
) ? d
[n
* (i
- 1) + j
- 1] : Infinity
;
51 var del
= i
? d
[n
* (i
- 1) + j
] : Infinity
;
52 var ins
= j
? d
[n
* i
+ j
- 1] : Infinity
;
53 if (sub
<= ins
&& sub
<= del
) {
54 if (d
[n
* i
+ j
] !== d
[n
* (i
- 1) + j
- 1])
55 path
.push(["sub", i
- 1, t
[j
- 1]]);
57 } else if (ins
<= del
) {
58 path
.push(["ins", i
, t
[j
- 1]]);
61 path
.push(["del", i
- 1]);
69 /** Create a diff between string s and t */
70 return editPath(levenshteinMatrix(s
, t
, 2, 2, 3), t
);
73 function patch(edits
, s
) {
74 /** Apply the list of edits to s */
78 if (Array
.isArray(s
)) {
79 for (i
= 0; i
< edits
.length
; ++i
) {
86 s
.splice(edit
[1], 0, edit
[2]);
94 for (i
= 0; i
< edits
.length
; ++i
) {
98 s
= s
.slice(0, edit
[1]) + edit
[2] + s
.slice(edit
[1] + 1);
101 s
= s
.slice(0, edit
[1]) + edit
[2] + s
.slice(edit
[1]);
104 s
= s
.slice(0, edit
[1]) + s
.slice(edit
[1] + 1);
112 var MULTI
= /[\uD800-\uDBFF][\uDC00-\uDFFF]|[\u0300-\u036F\u1DC0-\u1DFF\u20D0-\u20FF\uFE20-\uFE2F]/;
114 var GLYPH
= /([\0-\u02FF\u0370-\u1DBF\u1E00-\u20CF\u2100-\uD7FF\uDC00-\uFE1F\uFE30-\uFFFF]|[\uD800-\uDBFF][\uDC00-\uDFFF]|[\uD800-\uDBFF])([\u0300-\u036F\u1DC0-\u1DFF\u20D0-\u20FF\uFE20-\uFE2F]*)/g;
116 function diffLerp(a
, b
, p
) {
117 /** Interpolate between two strings based on edit operations
119 This interpolation algorithm applys a partial edit of one
120 string into the other. This produces nice looking results,
121 but can take a significant amount of time and memory to
122 compute the edits. It is not recommended for strings
123 longer than a few hundred characters.
126 // If given strings with astral codepoints or combining
127 // characters, split them into arrays of "glyphs" first,
128 // do the edit on the list of "glyphs", and rejoin them.
130 // This split is not perfect for all languages, but at least
131 // it won't create invalid surrogate pairs or orphaned
132 // combining characters.
133 if (a
.match
&& a
.match(MULTI
) || b
.match
&& b
.match(MULTI
)) {
134 var ca
= a
.match(GLYPH
) || [];
135 var cb
= b
.match(GLYPH
) || [];
136 return diffLerp(ca
, cb
, p
).join("");
139 // The edit path works from the string end, forwards, because
140 // that's how Levenshtein edits work. To match LTR reading
141 // direction (and the behavior of fastLerp), swap the strings
142 // and invert the parameter when editing.
143 var edits
= diff(b
, a
);
144 var partial
= edits
.slice(0, Math
.round((1 - p
) * edits
.length
));
145 return patch(partial
, b
);
148 var NUMBERS
= /(-?\d+(?:\.\d+)?)/g;
150 function areNumericTwins(a
, b
) {
151 /** Check if a and b differ only in numerals
153 A leading "-" counts as part of numbers; a leading "+"
154 does not. Numbers may contain a single ".", but no other
155 floating point syntax.
157 return a
.replace(NUMBERS
, "0") === b
.replace(NUMBERS
, "0");
160 function nlerp(a
, b
, p
) {
161 return a
+ (b
- a
) * p
;
164 function numericLerp(a
, b
, p
) {
165 /** Interpolate numerically between two strings containing numbers
167 Numbers may have a leading "-" and a single "." to mark
168 the decimal point, but something must be after the ".".
169 If both of the numbers in a pair are integers, the result
170 is clamped to an integer.
172 For example, numericLerp("0.0", "100", 0.123) === "12.3"
173 because the "." in "0.0" is interpreted as a decimal
174 point. But numericLerp("0.", "100.", 0.123) === "12."
175 because the strings are interpreted as integers followed
178 Calling this functions on strings that differ in more than
179 numerals gives undefined results.
181 var aParts
= a
.split(NUMBERS
);
182 var bParts
= b
.split(NUMBERS
);
183 for (var i
= 1; i
< aParts
.length
; i
+= 2) {
184 var part
= nlerp(+aParts
[i
], +bParts
[i
], p
);
185 if (aParts
[i
].indexOf(".") === -1 && bParts
[i
].indexOf(".") === -1)
186 part
= Math
.round(part
);
187 aParts
[i
] = part
.toString();
189 return aParts
.join("");
192 function fastLerp(a
, b
, p
) {
193 /** Interpolate between two strings based on length
195 This interpolation algorithm progressively replaces the
196 front of one string with another. This approach is fast
197 but does not look good when the strings are similar.
200 // TODO: Consider fast-pathing this even more for very large
201 // strings, e.g. in the megabyte range. These are large enough
203 if (a
.match(MULTI
) || b
.match(MULTI
)) {
204 var ca
= a
.match(GLYPH
) || [];
205 var cb
= b
.match(GLYPH
) || [];
206 var calen
= Math
.round(ca
.length
* p
);
207 var cblen
= Math
.round(cb
.length
* p
);
208 var r
= cb
.slice(0, cblen
);
209 r
.push
.apply(r
, ca
.slice(calen
, ca
.length
));
212 var alen
= Math
.round(a
.length
* p
);
213 var blen
= Math
.round(b
.length
* p
);
214 return b
.substring(0, blen
) + a
.substring(alen
, a
.length
);
218 function lerp(a
, b
, p
) {
219 /** Interpolate between two strings as best as possible
221 If the strings are identical aside from numbers in them,
222 they are passed through numericLerp.
224 If the strings are not numbers and short, they are passed
227 Otherwise, they are passed through fastLerp.
232 // Fast path for boundary cases.
233 if (p
=== 0) return a
;
234 if (p
=== 1) return b
;
236 if (areNumericTwins(a
, b
))
237 return numericLerp(a
, b
, p
);
239 // Numeric lerps should over- and under-shoot when fed numbers
240 // outside 0 to 1, but other types cannot.
244 var n
= a
.length
* b
.length
;
245 return ((n
&& n
< MAX_MATRIX_SIZE
) ? diffLerp
: fastLerp
)(a
, b
, p
);
248 exports
.levenshteinMatrix
= levenshteinMatrix
;
249 exports
.patch
= patch
;
251 exports
.fastLerp
= fastLerp
;
252 exports
.diffLerp
= diffLerp
;
253 exports
.numericLerp
= numericLerp
;
256 })(typeof exports
=== "undefined" ? (this.stringLerp
= {}) : exports
);