X-Git-Url: https://git.yukkurigames.com/?p=string-lerp.git;a=blobdiff_plain;f=string-lerp.js;h=54731995783f405d7d0102d39556747cb2c0ea73;hp=4a2c80f1533cad299063a7bdcc644defa5e5fe8b;hb=HEAD;hpb=ce8d91dd9711ad0216e44f8ae69d114bd4fc85c8 diff --git a/string-lerp.js b/string-lerp.js index 4a2c80f..5473199 100644 --- a/string-lerp.js +++ b/string-lerp.js @@ -1,115 +1,307 @@ +/* string-lerp - progressively turn one string into another + Copyright 2014 Joe Wreschnig + Licensed under the terms of the GNU GPL v2 or later + @license http://www.gnu.org/licenses/gpl-2.0.html + @source: http://yukkurigames.com/string-lerp/ +*//* + This program is free software; you can redistribute it and/or + modify it under the terms of the GNU General Public License as + published by the Free Software Foundation; either version 2 of the + License, or (at your option) any later version. + + This program is distributed in the hope that it will be useful, but + WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + General Public License for more details. + + As additional permission, you may distribute the program or works + based on it without the copy of the GNU GPL normally required, + provided you include this license notice and a URL through which + recipients can access the corresponding source code. +*/ + +/*globals exports, Uint32Array */ + (function (exports) { "use strict"; var MAX_MATRIX_SIZE = 256 * 256; - function repeat(n, v) { - var r = []; - while (n--) - r.push(v); - return r; - } + function costMatrix(source, target, ins, del, sub) { + /** Calculate the Levenshtein cost matrix for source and target - function createMatrix(i, j) { - var m = []; - while (i--) - m.push(repeat(j, 0)); - return m; - } + If source and target are strings, they cannot contain any + astral or combining codepoints. Such data must be passed + as arrays of strings with one element per glyph. + + ins, del, and sub are the costs for insertion, deletion, + and substition respectively. Their default value is 1. If + only ins is passed, del and sub are set to the same cost. + If ins and del are passed, sub is set to the more + expensive of the two. - function levenshteinMatrix(s, t) { - /** Calculate the Levenshtein edit distance matrix for two strings - - // Following http://en.wikipedia.org/wiki/Levenshtein_distance + The matrix is returned as a flat typed array. + + Following http://en.wikipedia.org/wiki/Levenshtein_distance */ - var m = s.length + 1; - var n = t.length + 1; - var d = createMatrix(m, n); + ins = ins === undefined ? 1 : (ins | 0); + del = (del | 0) || ins; + sub = (sub | 0) || Math.max(ins, del); + var m = source.length + 1; + var n = target.length + 1; + var d = new Uint32Array(m * n); var i, j; for (i = 1; i < m; ++i) - d[i][0] = i; + d[n * i] = i; for (j = 1; j < n; ++j) - d[0][j] = j; + d[j] = j; for (j = 1; j < n; ++j) for (i = 1; i < m; ++i) - if (s[i - 1] === t[j - 1]) - d[i][j] = d[i - 1][j - 1]; + if (source[i - 1] === target[j - 1]) + d[n * i + j] = d[n * (i - 1) + j - 1]; else - d[i][j] = 1 + Math.min(d[i - 1][ j ], - d[ i ][j - 1], - d[i - 1][j - 1]); + d[n * i + j] = Math.min(del + d[n * (i - 1) + j ], + ins + d[n * i + j - 1], + sub + d[n * (i - 1) + j - 1]); return d; } - function editPath(m, s, t) { - var path = [] - var i = s.length; - var j = t.length; + // First, note that deletion is just substition with nothing, so + // any DEL operation can be replaced by a SUB. Second, the + // operation code *is* the necessary slice offset for applying the + // diff. + var INS = 0, SUB = 1; + + function editPath(costs, target) { + /** Given a cost matrix and a target, create an edit list */ + var path = []; + var j = target.length; + var n = j + 1; + var i = costs.length / n - 1; while (i || j) { - var sub = (i && j) ? m[i - 1][j - 1] : Infinity; - var del = i ? m[i - 1][j] : Infinity; - var ins = j ? m[i][j - 1] : Infinity; + var sub = (i && j) ? costs[n * (i - 1) + j - 1] : Infinity; + var del = i ? costs[n * (i - 1) + j] : Infinity; + var ins = j ? costs[n * i + j - 1] : Infinity; if (sub <= ins && sub <= del) { - if (m[i][j] !== m[i - 1][j - 1]) - path.push(["sub", i - 1, t[j - 1]]); + if (costs[n * i + j] !== costs[n * (i - 1) + j - 1]) + path.push([SUB, i - 1, target[j - 1]]); --i; --j; } else if (ins <= del) { - path.push(["ins", i, t[j - 1]]); + path.push([INS, i, target[j - 1]]); --j; } else { - path.push(["del", i - 1]); + path.push([SUB, i - 1, ""]); --i; } } return path; } - function applyEdits(edits, s, t) { - var i; - for (i = 0; i < edits.length; ++i) { - var edit = edits[i]; - switch (edit[0]) { - case "sub": - s = s.slice(0, edit[1]) + edit[2] + s.slice(edit[1] + 1); - break; - case "ins": - s = s.slice(0, edit[1]) + edit[2] + s.slice(edit[1]); - break; - case "del": - s = s.slice(0, edit[1]) + s.slice(edit[1] + 1); - break; - } + function diff(source, target, ins, del, sub) { + /** Create a list of edits to turn source into target + + ins, del, and sub are as passed to costMatrix. + */ + return editPath(costMatrix(source, target, ins, del, sub), target); + } + + function patchArray(diff, source) { + for (var i = 0; i < diff.length; ++i) { + var edit = diff[i]; + source.splice(edit[1], edit[0], edit[2]); + } + return source; + } + + function patchString(diff, source) { + for (var i = 0; i < diff.length; ++i) { + var edit = diff[i]; + var head = source.slice(0, edit[1]); + var tail = source.slice(edit[1] + edit[0]); + source = head + edit[2] + tail; + } + return source; + } + + function patch(diff, source) { + /** Apply a list of edits to source */ + var patcher = Array.isArray(source) ? patchArray : patchString; + return patcher(diff, source); + } + + // Matches if a string contains combining characters or astral + // codepoints (technically, the first half surrogate of an astral + // codepoint). + var MULTI = /[\u0300-\u036F\u1DC0-\u1DFF\u20D0-\u20FF\uD800-\uDBFF\uFE20-\uFE2F]/; + + // Match an entire (potentially astral) codepoint and any + // combining characters following it. + var GLYPH = /[\0-\u02FF\u0370-\u1DBF\u1E00-\u20CF\u2100-\uD7FF\uD800-\uFE1F\uFE30-\uFFFF][\u0300-\u036F\u1DC0-\u1DFF\u20D0-\u20FF\uDC00-\uDFFF\uFE20-\uFE2F]*/g; + + function diffLerpAstral(source, target, amount) { + // This split is not perfect for all languages, but at least + // it won't create invalid surrogate pairs or orphaned + // combining characters. + var sourceGlyphs = source.match(GLYPH) || []; + var targetGlyphs = target.match(GLYPH) || []; + var edits = diff(targetGlyphs, sourceGlyphs, 2, 2, 3); + // The edit path works from the string end, forwards, because + // that's how Levenshtein edits work. To match LTR reading + // direction (and the behavior of fastLerp), swap the strings + // and invert the parameter when editing. + var partial = edits.slice(0, Math.round((1 - amount) * edits.length)); + return patchArray(partial, targetGlyphs).join(""); + } + + function diffLerpBasic(source, target, amount) { + var edits = diff(target, source, 2, 2, 3); + // The edit path works from the string end, forwards, because + // that's how Levenshtein edits work. To match LTR reading + // direction (and the behavior of fastLerp), swap the strings + // and invert the parameter when editing. + var partial = edits.slice(0, Math.round((1 - amount) * edits.length)); + return patchString(partial, target); + } + + function diffLerp(source, target, amount) { + /** Interpolate between two strings using edit operations + + This interpolation algorithm applys a partial edit of one + string into the other. This produces nice looking results, + but can take a significant amount of time and memory to + compute the edits. It is not recommended for strings + longer than a few hundred characters. + */ + + if (source.match(MULTI) || target.match(MULTI)) + return diffLerpAstral(source, target, amount); + else + return diffLerpBasic(source, target, amount); + } + + var NUMBERS = /(-?\d{1,20}(?:\.\d{1,20})?)/g; + + function areNumericTwins(source, target) { + /** Check if a and b differ only in numerals */ + return source.replace(NUMBERS, "0") === target.replace(NUMBERS, "0"); + } + + function nlerp(source, target, amount) { + return source + (target - source) * amount; + } + + function numericLerp(source, target, amount) { + /** Interpolate numerically between strings containing numbers + + Numbers may have a leading "-" and a single "." to mark + the decimal point, but something must be after the ".". + No other floating point syntax (e.g. 1e6) is supported. + They are treated as fixed-point values, with the point's + position itself interpolating. + + For example, numericLerp("0.0", "100".0, 0.123) === "12.3" + because the "." in "0.0" is interpreted 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 targetParts = target.split(NUMBERS); + var match; + var i = 1; + while ((match = NUMBERS.exec(source))) { + var sourcePart = match[0]; + var targetPart = targetParts[i]; + var part = nlerp(+sourcePart, +targetPart, amount); + var sourcePoint = sourcePart.indexOf("."); + var targetPoint = targetPart.indexOf("."); + var point = Math.round(nlerp( + sourcePoint >= 0 ? (sourcePart.length - 1) - sourcePoint : 0, + targetPoint >= 0 ? (targetPart.length - 1) - targetPoint : 0, + amount)); + targetParts[i] = part.toFixed(point); + i += 2; } - return s; + return targetParts.join(""); } - function slowLerp(a, b, p) { - var m = levenshteinMatrix(a, b); - var edits = editPath(m, a, b); - var partial = edits.slice(0, Math.round(p * edits.length)); - return applyEdits(partial, a, b); + function fastLerpAstral(source, target, amount) { + var sourceGlyphs = source.match(GLYPH) || []; + var targetGlyphs = target.match(GLYPH) || []; + var sourceLength = Math.round(sourceGlyphs.length * amount); + var targetLength = Math.round(targetGlyphs.length * amount); + var head = targetGlyphs.slice(0, targetLength); + var tail = sourceGlyphs.slice(sourceLength, sourceGlyphs.length); + head.push.apply(head, tail); + return head.join(""); } - function fastLerp(a, b, p) { - 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 fastLerpBasic(source, target, amount) { + var sourceLength = Math.round(source.length * amount); + var targetLength = Math.round(target.length * amount); + var head = target.substring(0, targetLength); + var tail = source.substring(sourceLength, source.length); + return head + tail; } - function lerp(a, b, p) { - a = a.toString(); - b = b.toString(); - var n = a.length * b.length; - return (n && n < MAX_MATRIX_SIZE) - ? slowLerp(a, b, p) - : fastLerp(a, b, p); + function fastLerp(source, target, amount) { + /** 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. + */ + + // TODO: Consider fast-pathing this even more for very large + // strings, e.g. in the megabyte range. These are large enough + // that it should be fine to just pick a codepoint and search + // for the nearest glyph start. + if (source.match(MULTI) || target.match(MULTI)) + return fastLerpAstral(source, target, amount); + else + return fastLerpBasic(source, target, amount); + } + + function lerp(source, target, amount) { + /** 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. + */ + source = source.toString(); + target = target.toString(); + + // Fast path for boundary cases. + if (amount === 0) return source; + if (amount === 1) return target; + + if (areNumericTwins(source, target)) + return numericLerp(source, target, amount); + + // Numeric lerps should over- and under-shoot when fed numbers + // outside 0 to 1, but other types cannot. + if (amount < 0) return source; + if (amount > 1) return target; + + var n = source.length * target.length; + var appropriate = (n && n < MAX_MATRIX_SIZE) ? diffLerp : fastLerp; + return appropriate(source, target, amount); } - exports.levenshteinMatrix = levenshteinMatrix; - exports.editPath = editPath; + exports.costMatrix = costMatrix; + 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);