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 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]]);
+ path.push([SUB, i - 1, target[j - 1]]);
--i; --j;
} else if (ins <= del) {
- path.push(["ins", i, target[j - 1]]);
+ path.push([INS, i, target[j - 1]]);
--j;
} else {
- path.push(["del", i - 1]);
+ path.push([SUB, i - 1, ""]);
--i;
}
}
}
function diff(source, target, ins, del, sub) {
- /** Create a diff between string source and target
+ /** Create a list of edits to turn source into target
- ins, del, and sub are as passed to levenshtein
- */
+ ins, del, and sub are as passed to costMatrix.
+ */
return editPath(costMatrix(source, target, ins, del, sub), target);
}
- function patch(edits, s) {
- /** Apply the list of edits to s */
+ function patch(diff, source) {
+ /** Apply a list of edits to source */
var edit;
var i;
- if (Array.isArray(s)) {
- for (i = 0; i < edits.length; ++i) {
- edit = edits[i];
- switch (edit[0]) {
- case "sub":
- s[edit[1]] = edit[2];
- break;
- case "ins":
- s.splice(edit[1], 0, edit[2]);
- break;
- case "del":
- s.splice(edit[1], 1);
- break;
- }
+ if (Array.isArray(source)) {
+ for (i = 0; i < diff.length; ++i) {
+ edit = diff[i];
+ source.splice(edit[1], edit[0], edit[2]);
}
} else {
- for (i = 0; i < edits.length; ++i) {
- 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;
- }
+ for (i = 0; i < diff.length; ++i) {
+ edit = diff[i];
+ var head = source.slice(0, edit[1]);
+ var tail = source.slice(edit[1] + edit[0]);
+ source = head + edit[2] + tail;
}
}
- return s;
+ return source;
}
var MULTI = /[\uD800-\uDBFF][\uDC00-\uDFFF]|[\u0300-\u036F\u1DC0-\u1DFF\u20D0-\u20FF\uFE20-\uFE2F]/;
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;
- function diffLerp(a, b, p) {
- /** Interpolate between two strings based on edit operations
+ 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 given strings with astral codepoints or combining
// characters, split them into arrays of "glyphs" first,
// This split is not perfect for all languages, but at least
// it won't create invalid surrogate pairs or orphaned
// combining characters.
- if (a.match && a.match(MULTI) || b.match && b.match(MULTI)) {
- var ca = a.match(GLYPH) || [];
- var cb = b.match(GLYPH) || [];
- return diffLerp(ca, cb, p).join("");
+ if (source.match && (source.match(MULTI) || target.match(MULTI))) {
+ var sourceGlyphs = source.match(GLYPH) || [];
+ var targetGlyphs = target.match(GLYPH) || [];
+ return diffLerp(sourceGlyphs, targetGlyphs, amount).join("");
}
// 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 edits = diff(b, a, 2, 2, 3);
- var partial = edits.slice(0, Math.round((1 - p) * edits.length));
- return patch(partial, b);
+ var edits = diff(target, source, 2, 2, 3);
+ var partial = edits.slice(0, Math.round((1 - amount) * edits.length));
+ return patch(partial, target);
}
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 areNumericTwins(source, target) {
+ /** Check if a and b differ only in numerals */
+ return source.replace(NUMBERS, "0") === target.replace(NUMBERS, "0");
}
- function nlerp(a, b, p) {
- return a + (b - a) * p;
+ function nlerp(source, target, amount) {
+ return source + (target - source) * amount;
}
- function numericLerp(a, b, p) {
- /** Interpolate numerically between two strings containing numbers
+ 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.
If both of the numbers in a pair are integers, the result
is clamped to an integer.
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)
+ */
+
+ // TODO: Try to preserve precision of the original numbers.
+ var sourceParts = source.split(NUMBERS);
+ var targetParts = target.split(NUMBERS);
+ var destParts = targetParts;
+ for (var i = 1; i < sourceParts.length; i += 2) {
+ var sourcePart = sourceParts[i];
+ var targetPart = targetParts[i];
+ var part = nlerp(+sourcePart, +targetPart, amount);
+ var sourcePoint = sourcePart.indexOf(".");
+ var targetPoint = targetPart.indexOf(".");
+ if (sourcePoint === -1 && targetPoint === -1)
part = Math.round(part);
- aParts[i] = part.toString();
+ targetParts[i] = part.toString();
}
- return aParts.join("");
+ return targetParts.join("");
}
function fastLerp(a, b, p) {
// TODO: Consider fast-pathing this even more for very large
// strings, e.g. in the megabyte range. These are large enough
- // that
+ // that it should be fine to just pick a codepoint and search
+ // for the nearest glyph start.
if (a.match(MULTI) || b.match(MULTI)) {
var ca = a.match(GLYPH) || [];
var cb = b.match(GLYPH) || [];
projects / string-lerp.git / blobdiff