From ce8d91dd9711ad0216e44f8ae69d114bd4fc85c8 Mon Sep 17 00:00:00 2001 From: Joe Wreschnig Date: Tue, 13 May 2014 16:30:38 +0200 Subject: [PATCH] Initial lerping code. --- demo.html | 33 ++++++++++++++ string-lerp.js | 115 +++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 148 insertions(+) create mode 100644 demo.html create mode 100644 string-lerp.js diff --git a/demo.html b/demo.html new file mode 100644 index 0000000..c8712c9 --- /dev/null +++ b/demo.html @@ -0,0 +1,33 @@ + + + + String Linear Interpolation Example + + + + + + +
+ + +
+
+ + + diff --git a/string-lerp.js b/string-lerp.js new file mode 100644 index 0000000..4a2c80f --- /dev/null +++ b/string-lerp.js @@ -0,0 +1,115 @@ +(function (exports) { + "use strict"; + + 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 + + // Following http://en.wikipedia.org/wiki/Levenshtein_distance + */ + var m = s.length + 1; + var n = t.length + 1; + var d = createMatrix(m, n); + var i, j; + for (i = 1; i < m; ++i) + d[i][0] = i; + for (j = 1; j < n; ++j) + d[0][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]; + else + d[i][j] = 1 + Math.min(d[i - 1][ j ], + d[ i ][j - 1], + d[i - 1][j - 1]); + return d; + } + + function editPath(m, s, t) { + var path = [] + var i = s.length; + var j = t.length; + 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; + if (sub <= ins && sub <= del) { + if (m[i][j] !== m[i - 1][j - 1]) + path.push(["sub", i - 1, t[j - 1]]); + --i; --j; + } else if (ins <= del) { + path.push(["ins", i, t[j - 1]]); + --j; + } else { + path.push(["del", 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; + } + } + return s; + } + + 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 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 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); + } + + exports.levenshteinMatrix = levenshteinMatrix; + exports.editPath = editPath; + exports.fastLerp = fastLerp; + exports.slowLerp = slowLerp; + exports.applyEdits = applyEdits; + exports.lerp = lerp; + +})(typeof exports === "undefined" ? (this.stringLerp = {}) : exports); -- 2.20.1