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 costMatrix(source
, target
, ins
, del
, sub
) {
18 /** Calculate the Levenshtein cost matrix for source and target
20 If source and target are strings, they cannot contain any
21 astral or combining codepoints. Such data must be passed
22 as arrays of strings with one element per glyph.
24 ins, del, and sub are the costs for insertion, deletion,
25 and substition respectively. Their default value is 1. If
26 only ins is passed, del and sub are set to the same cost.
27 If ins and del are passed, sub is set to the more
30 The matrix is returned as a flat typed array.
32 Following http://en.wikipedia.org/wiki/Levenshtein_distance
34 ins
= ins
=== undefined ? 1 : (ins
| 0);
35 del
= (del
| 0) || ins
;
36 sub
= (sub
| 0) || Math
.max(ins
, del
);
37 var m
= source
.length
+ 1;
38 var n
= target
.length
+ 1;
39 var d
= new Uint32Array(m
* n
);
41 for (i
= 1; i
< m
; ++i
)
43 for (j
= 1; j
< n
; ++j
)
45 for (j
= 1; j
< n
; ++j
)
46 for (i
= 1; i
< m
; ++i
)
47 if (source
[i
- 1] === target
[j
- 1])
48 d
[n
* i
+ j
] = d
[n
* (i
- 1) + j
- 1];
50 d
[n
* i
+ j
] = Math
.min(del
+ d
[n
* (i
- 1) + j
],
51 ins
+ d
[n
* i
+ j
- 1],
52 sub
+ d
[n
* (i
- 1) + j
- 1]);
56 function editPath(costs
, target
) {
57 /** Given a cost matrix and a target, create an edit list */
59 var j
= target
.length
;
61 var i
= costs
.length
/ n
- 1;
63 var sub
= (i
&& j
) ? costs
[n
* (i
- 1) + j
- 1] : Infinity
;
64 var del
= i
? costs
[n
* (i
- 1) + j
] : Infinity
;
65 var ins
= j
? costs
[n
* i
+ j
- 1] : Infinity
;
66 if (sub
<= ins
&& sub
<= del
) {
67 if (costs
[n
* i
+ j
] !== costs
[n
* (i
- 1) + j
- 1])
68 path
.push(["sub", i
- 1, target
[j
- 1]]);
70 } else if (ins
<= del
) {
71 path
.push(["ins", i
, target
[j
- 1]]);
74 path
.push(["del", i
- 1]);
81 function diff(source
, target
, ins
, del
, sub
) {
82 /** Create a diff between string source and target
84 ins, del, and sub are as passed to levenshtein
86 return editPath(costMatrix(source
, target
, ins
, del
, sub
), target
);
89 function patch(edits
, s
) {
90 /** Apply the list of edits to s */
94 if (Array
.isArray(s
)) {
95 for (i
= 0; i
< edits
.length
; ++i
) {
102 s
.splice(edit
[1], 0, edit
[2]);
105 s
.splice(edit
[1], 1);
110 for (i
= 0; i
< edits
.length
; ++i
) {
114 s
= s
.slice(0, edit
[1]) + edit
[2] + s
.slice(edit
[1] + 1);
117 s
= s
.slice(0, edit
[1]) + edit
[2] + s
.slice(edit
[1]);
120 s
= s
.slice(0, edit
[1]) + s
.slice(edit
[1] + 1);
128 var MULTI
= /[\uD800-\uDBFF][\uDC00-\uDFFF]|[\u0300-\u036F\u1DC0-\u1DFF\u20D0-\u20FF\uFE20-\uFE2F]/;
130 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;
132 function diffLerp(a
, b
, p
) {
133 /** Interpolate between two strings based on edit operations
135 This interpolation algorithm applys a partial edit of one
136 string into the other. This produces nice looking results,
137 but can take a significant amount of time and memory to
138 compute the edits. It is not recommended for strings
139 longer than a few hundred characters.
142 // If given strings with astral codepoints or combining
143 // characters, split them into arrays of "glyphs" first,
144 // do the edit on the list of "glyphs", and rejoin them.
146 // This split is not perfect for all languages, but at least
147 // it won't create invalid surrogate pairs or orphaned
148 // combining characters.
149 if (a
.match
&& a
.match(MULTI
) || b
.match
&& b
.match(MULTI
)) {
150 var ca
= a
.match(GLYPH
) || [];
151 var cb
= b
.match(GLYPH
) || [];
152 return diffLerp(ca
, cb
, p
).join("");
155 // The edit path works from the string end, forwards, because
156 // that's how Levenshtein edits work. To match LTR reading
157 // direction (and the behavior of fastLerp), swap the strings
158 // and invert the parameter when editing.
159 var edits
= diff(b
, a
, 2, 2, 3);
160 var partial
= edits
.slice(0, Math
.round((1 - p
) * edits
.length
));
161 return patch(partial
, b
);
164 var NUMBERS
= /(-?\d+(?:\.\d+)?)/g;
166 function areNumericTwins(a
, b
) {
167 /** Check if a and b differ only in numerals
169 A leading "-" counts as part of numbers; a leading "+"
170 does not. Numbers may contain a single ".", but no other
171 floating point syntax.
173 return a
.replace(NUMBERS
, "0") === b
.replace(NUMBERS
, "0");
176 function nlerp(a
, b
, p
) {
177 return a
+ (b
- a
) * p
;
180 function numericLerp(a
, b
, p
) {
181 /** Interpolate numerically between two strings containing numbers
183 Numbers may have a leading "-" and a single "." to mark
184 the decimal point, but something must be after the ".".
185 If both of the numbers in a pair are integers, the result
186 is clamped to an integer.
188 For example, numericLerp("0.0", "100", 0.123) === "12.3"
189 because the "." in "0.0" is interpreted as a decimal
190 point. But numericLerp("0.", "100.", 0.123) === "12."
191 because the strings are interpreted as integers followed
194 Calling this functions on strings that differ in more than
195 numerals gives undefined results.
197 var aParts
= a
.split(NUMBERS
);
198 var bParts
= b
.split(NUMBERS
);
199 for (var i
= 1; i
< aParts
.length
; i
+= 2) {
200 var part
= nlerp(+aParts
[i
], +bParts
[i
], p
);
201 if (aParts
[i
].indexOf(".") === -1 && bParts
[i
].indexOf(".") === -1)
202 part
= Math
.round(part
);
203 aParts
[i
] = part
.toString();
205 return aParts
.join("");
208 function fastLerp(a
, b
, p
) {
209 /** Interpolate between two strings based on length
211 This interpolation algorithm progressively replaces the
212 front of one string with another. This approach is fast
213 but does not look good when the strings are similar.
216 // TODO: Consider fast-pathing this even more for very large
217 // strings, e.g. in the megabyte range. These are large enough
219 if (a
.match(MULTI
) || b
.match(MULTI
)) {
220 var ca
= a
.match(GLYPH
) || [];
221 var cb
= b
.match(GLYPH
) || [];
222 var calen
= Math
.round(ca
.length
* p
);
223 var cblen
= Math
.round(cb
.length
* p
);
224 var r
= cb
.slice(0, cblen
);
225 r
.push
.apply(r
, ca
.slice(calen
, ca
.length
));
228 var alen
= Math
.round(a
.length
* p
);
229 var blen
= Math
.round(b
.length
* p
);
230 return b
.substring(0, blen
) + a
.substring(alen
, a
.length
);
234 function lerp(a
, b
, p
) {
235 /** Interpolate between two strings as best as possible
237 If the strings are identical aside from numbers in them,
238 they are passed through numericLerp.
240 If the strings are not numbers and short, they are passed
243 Otherwise, they are passed through fastLerp.
248 // Fast path for boundary cases.
249 if (p
=== 0) return a
;
250 if (p
=== 1) return b
;
252 if (areNumericTwins(a
, b
))
253 return numericLerp(a
, b
, p
);
255 // Numeric lerps should over- and under-shoot when fed numbers
256 // outside 0 to 1, but other types cannot.
260 var n
= a
.length
* b
.length
;
261 return ((n
&& n
< MAX_MATRIX_SIZE
) ? diffLerp
: fastLerp
)(a
, b
, p
);
264 exports
.costMatrix
= costMatrix
;
265 exports
.patch
= patch
;
267 exports
.fastLerp
= fastLerp
;
268 exports
.diffLerp
= diffLerp
;
269 exports
.numericLerp
= numericLerp
;
272 })(typeof exports
=== "undefined" ? (this.stringLerp
= {}) : exports
);