index 4a2c80f..5e8201c 100644 (file)
@@ -3,54 +3,44 @@

var MAX_MATRIX_SIZE = 256 * 256;

-    function repeat(n, v) {
-        var r = [];
-        while (n--)
-            r.push(v);
-        return r;
-    }
-
-    function createMatrix(i, j) {
-        var m = [];
-        while (i--)
-            m.push(repeat(j, 0));
-        return m;
-    }
-
function levenshteinMatrix(s, t) {
/** Calculate the Levenshtein edit distance matrix for two strings
+
+            The matrix is returned as a flat unsigned typed array.

-        // Following http://en.wikipedia.org/wiki/Levenshtein_distance
+            Following http://en.wikipedia.org/wiki/Levenshtein_distance
*/
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[i] = i;
+            d[n * i] = i;
for (j = 1; j < n; ++j)
-            d[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];
+                    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] = 1 + Math.min(d[n * (i - 1) + j    ],
+                                                d[n *    i    + j - 1],
+                                                d[n * (i - 1) + j - 1]);
return d;
}

-    function editPath(m, s, t) {
-        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) ? 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) ? d[n * (i - 1) + j - 1] : Infinity;
+            var del = i ? d[n * (i - 1) + j] : Infinity;
+            var ins = j ? d[n * i + j - 1] : Infinity;
if (sub <= ins && sub <= del) {
-                if (m[i][j] !== m[i - 1][j - 1])
+                if (d[n * i + j] !== d[n * (i - 1) + j - 1])
path.push(["sub", i - 1, t[j - 1]]);
--i; --j;
} else if (ins <= del) {
return path;
}

-    function applyEdits(edits, s, t) {
+    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) {
var edit = edits[i];
return s;
}

-    function slowLerp(a, b, p) {
-        var m = levenshteinMatrix(a, b);
-        var edits = editPath(m, a, b);
+    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,
+            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.
+         */
+        var edits = diff(a, b);
var partial = edits.slice(0, Math.round(p * edits.length));
-        return applyEdits(partial, a, b);
+        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 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;
-        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);