-/* 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 costMatrix(source, target, ins, del, sub) {
- /** Calculate the Levenshtein cost matrix for source and target
-
- 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.
-
- The matrix is returned as a flat typed array.
-
- Following http://en.wikipedia.org/wiki/Levenshtein_distance
- */
- 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[n * i] = i;
- for (j = 1; j < n; ++j)
- d[j] = j;
- for (j = 1; j < n; ++j)
- for (i = 1; i < m; ++i)
- if (source[i - 1] === target[j - 1])
- d[n * i + j] = d[n * (i - 1) + j - 1];
- else
- 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;
- }
-
- // 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) ? 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 (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, target[j - 1]]);
- --j;
- } else {
- path.push([SUB, i - 1, ""]);
- --i;
- }
- }
- return path;
- }
-
- 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 targetParts.join("");
- }
-
- 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 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 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.costMatrix = costMatrix;
- exports.patch = patch;
- exports.diff = diff;
- exports.fastLerp = fastLerp;
- exports.diffLerp = diffLerp;
- exports.numericLerp = numericLerp;
- exports.lerp = lerp;
-
-})(typeof exports === "undefined" ? (this.stringLerp = {}) : exports);
projects / pwl6.git / commitdiff