var MAX_MATRIX_SIZE = 256 * 256;
- function createMatrix(i, j) {
- return new Uint32Array(i * j);
- }
-
function levenshteinMatrix(s, t) {
/** Calculate the Levenshtein edit distance matrix for two strings
*/
var m = s.length + 1;
var n = t.length + 1;
- var d = createMatrix(m, n);
+ var d = new Uint32Array(m * n);
var i, j;
for (i = 1; i < m; ++i)
d[n * i] = i;
return d;
}
- function editPath(d, s, t) {
- /** Given a Levenshtein result matrix, trace the shortest edit */
- var path = []
- var i = s.length;
+ function editPath(d, t) {
+ /** Given a Levenshtein matrix and target, create an edit list */
+ var path = [];
var j = t.length;
var n = j + 1;
+ var i = d.length / n - 1;
while (i || j) {
var sub = (i && j) ? d[n * (i - 1) + j - 1] : Infinity;
var del = i ? d[n * (i - 1) + j] : Infinity;
return path;
}
- function applyEdits(edits, s) {
+ function diff(s, t) {
+ /** Create a diff between string s and t */
+ return editPath(levenshteinMatrix(s, t), t);
+ }
+
+ function patch(edits, s) {
/** Apply the list of edits to s */
var i;
for (i = 0; i < edits.length; ++i) {
return s;
}
- function slowLerp(a, b, p) {
- /** Interpolate between two strings slowly
+ function diffLerp(a, b, p) {
+ /** Interpolate between two strings based on edit distance
This interpolation algorithm applys a partial edit of one
string into the other. This produces nice looking results,
compute the edits. It is not recommended for strings
longer than a few hundred characters.
*/
- var edits = editPath(levenshteinMatrix(a, b), a, b);
+ var edits = diff(a, b);
var partial = edits.slice(0, Math.round(p * edits.length));
- return applyEdits(partial, a);
+ return patch(partial, a);
+ }
+
+ var NUMBERS = /(-?\d+(?:\.\d+)?)/g;
+
+ function areNumericTwins(a, b) {
+ /** Check if a and b differ only in numerals
+
+ A leading "-" counts as part of numbers; a leading "+"
+ does not. Numbers may contain a single ".", but no other
+ floating point syntax.
+ */
+ return a.replace(NUMBERS, "0") === b.replace(NUMBERS, "0");
+ }
+
+ function nlerp(a, b, p) {
+ return a + (b - a) * p;
+ }
+
+ function numericLerp(a, b, p) {
+ /** Interpolate numerically between two strings containing numbers
+
+ Numbers may have a leading "-" and a single "." to mark
+ the decimal point, but something must be after the ".".
+ If both of the numbers in a pair are integers, the result
+ is clamped to an integer.
+
+ For example, numericLerp("0.0", "100", 0.123) === "12.3"
+ because the "." in "0.0" is intepreted as a decimal point.
+ But numericLerp("0.", "100.", 0.123) === "12." because the
+ strings are interpreted as integers followed by a full
+ stop.
+
+ Calling this functions on strings that differ in more than
+ numerals gives undefined results.
+ */
+ var aParts = a.split(NUMBERS);
+ var bParts = b.split(NUMBERS);
+ for (var i = 1; i < aParts.length; i += 2) {
+ var part = nlerp(+aParts[i], +bParts[i], p);
+ if (aParts[i].indexOf(".") === -1 && bParts[i].indexOf(".") === -1)
+ part = Math.round(part);
+ aParts[i] = part.toString();
+ }
+ return aParts.join("");
}
function fastLerp(a, b, p) {
- /** Interpolate between two strings very quickly
+ /** Interpolate between two strings based on length
This interpolation algorithm progressively replaces the
front of one string with another. This approach is fast
but does not look good when the strings are similar.
- */
+ */
var alen = Math.round(a.length * p);
var blen = Math.round(b.length * p);
return b.substring(0, blen) + a.substring(alen, a.length);
}
function lerp(a, b, p) {
+ /** Interpolate between two strings as best as possible
+
+ If the strings are identical aside from numbers in them,
+ they are passed through numericLerp.
+
+ If the strings are not numbers and short, they are passed
+ through diffLerp.
+
+ Otherwise, they are passed through fastLerp.
+ */
a = a.toString();
b = b.toString();
+
+ // Fast path for boundary cases.
+ if (p === 0) return a;
+ if (p === 1) return b;
+
+ if (areNumericTwins(a, b))
+ return numericLerp(a, b, p);
+
+ // Numeric lerps should over- and under-shoot when fed numbers
+ // outside 0 to 1, but other types cannot.
+ if (p < 0) return a;
+ if (p > 1) return b;
+
var n = a.length * b.length;
- // TODO: if both strings are integers, do an integer lerp.
- // TODO: if both strings are numbers, do a numeric lerp.
- return (n && n < MAX_MATRIX_SIZE)
- ? slowLerp(a, b, p)
- : fastLerp(a, b, p);
+ return ((n && n < MAX_MATRIX_SIZE) ? diffLerp : fastLerp)(a, b, p);
}
exports.levenshteinMatrix = levenshteinMatrix;
- exports.editPath = editPath;
+ exports.patch = patch;
+ exports.diff = diff;
exports.fastLerp = fastLerp;
- exports.slowLerp = slowLerp;
- exports.applyEdits = applyEdits;
+ exports.diffLerp = diffLerp;
+ exports.numericLerp = numericLerp;
exports.lerp = lerp;
})(typeof exports === "undefined" ? (this.stringLerp = {}) : exports);
projects / string-lerp.git / blobdiff