string-lerp.js

   1 /* string-lerp - progressively turn one string into another
   2    Copyright 2014 Joe Wreschnig
   3
   4    This program is free software; you can redistribute it and/or modify
   5    it under the terms of the GNU General Public License as published by
   6    the Free Software Foundation; either version 2 of the License, or
   7    (at your option) any later version.
   8 */
   9
  10 /* @license Copyright 2014 Joe Wreschnig - GNU GPL v2 or later */
  11
  12 (function (exports) {
  13     "use strict";
  14
  15     var MAX_MATRIX_SIZE = 256 * 256;
  16
  17     function levenshteinMatrix(s, t, ins, del, sub) {
  18         /** Calculate the Levenshtein edit distance matrix for two strings
  19
  20             The matrix is returned as a flat typed array.
  21
  22             Following http://en.wikipedia.org/wiki/Levenshtein_distance
  23         */
  24         var m = s.length + 1;
  25         var n = t.length + 1;
  26         var d = new Uint32Array(m * n);
  27         var i, j;
  28         for (i = 1; i < m; ++i)
  29             d[n * i] = i;
  30         for (j = 1; j < n; ++j)
  31             d[j] = j;
  32         for (j = 1; j < n; ++j)
  33             for (i = 1; i < m; ++i)
  34                 if (s[i - 1] === t[j - 1])
  35                     d[n * i + j] = d[n * (i - 1) + j - 1];
  36                 else
  37                     d[n * i + j] = Math.min(del + d[n * (i - 1) + j    ],
  38                                             ins + d[n *    i    + j - 1],
  39                                             sub + d[n * (i - 1) + j - 1]);
  40         return d;
  41     }
  42
  43     function editPath(d, t) {
  44         /** Given a Levenshtein matrix and target, create an edit list */
  45         var path = [];
  46         var j = t.length;
  47         var n = j + 1;
  48         var i = d.length / n - 1;
  49         while (i || j) {
  50             var sub = (i && j) ? d[n * (i - 1) + j - 1] : Infinity;
  51             var del = i ? d[n * (i - 1) + j] : Infinity;
  52             var ins = j ? d[n * i + j - 1] : Infinity;
  53             if (sub <= ins && sub <= del) {
  54                 if (d[n * i + j] !== d[n * (i - 1) + j - 1])
  55                     path.push(["sub", i - 1, t[j - 1]]);
  56                 --i; --j;
  57             } else if (ins <= del) {
  58                 path.push(["ins", i, t[j - 1]]);
  59                 --j;
  60             } else {
  61                 path.push(["del", i - 1]);
  62                 --i;
  63             }
  64         }
  65         return path;
  66     }
  67
  68     function diff(s, t) {
  69         /** Create a diff between string s and t */
  70         return editPath(levenshteinMatrix(s, t, 2, 2, 3), t);
  71     }
  72
  73     function patch(edits, s) {
  74         /** Apply the list of edits to s */
  75         var edit;
  76         var i;
  77
  78         if (Array.isArray(s)) {
  79             for (i = 0; i < edits.length; ++i) {
  80                 edit = edits[i];
  81                 switch (edit[0]) {
  82                 case "sub":
  83                     s[edit[1]] = edit[2];
  84                     break;
  85                 case "ins":
  86                     s.splice(edit[1], 0, edit[2]);
  87                     break;
  88                 case "del":
  89                     s.splice(edit[1], 1);
  90                     break;
  91                 }
  92             }
  93         } else {
  94             for (i = 0; i < edits.length; ++i) {
  95                 edit = edits[i];
  96                 switch (edit[0]) {
  97                 case "sub":
  98                     s = s.slice(0, edit[1]) + edit[2] + s.slice(edit[1] + 1);
  99                     break;
 100                 case "ins":
 101                     s = s.slice(0, edit[1]) + edit[2] + s.slice(edit[1]);
 102                     break;
 103                 case "del":
 104                     s = s.slice(0, edit[1]) + s.slice(edit[1] + 1);
 105                     break;
 106                 }
 107             }
 108         }
 109         return s;
 110     }
 111
 112     var MULTI = /[\uD800-\uDBFF][\uDC00-\uDFFF]|[\u0300-\u036F\u1DC0-\u1DFF\u20D0-\u20FF\uFE20-\uFE2F]/;
 113
 114     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;
 115
 116     function diffLerp(a, b, p) {
 117         /** Interpolate between two strings based on edit operations
 118
 119             This interpolation algorithm applys a partial edit of one
 120             string into the other. This produces nice looking results,
 121             but can take a significant amount of time and memory to
 122             compute the edits. It is not recommended for strings
 123             longer than a few hundred characters.
 124          */
 125
 126         // If given strings with astral codepoints or combining
 127         // characters, split them into arrays of "glyphs" first,
 128         // do the edit on the list of "glyphs", and rejoin them.
 129         //
 130         // This split is not perfect for all languages, but at least
 131         // it won't create invalid surrogate pairs or orphaned
 132         // combining characters.
 133         if (a.match && a.match(MULTI) || b.match && b.match(MULTI)) {
 134             var ca = a.match(GLYPH) || [];
 135             var cb = b.match(GLYPH) || [];
 136             return diffLerp(ca, cb, p).join("");
 137         }
 138
 139         // The edit path works from the string end, forwards, because
 140         // that's how Levenshtein edits work. To match LTR reading
 141         // direction (and the behavior of fastLerp), swap the strings
 142         // and invert the parameter when editing.
 143         var edits = diff(b, a);
 144         var partial = edits.slice(0, Math.round((1 - p) * edits.length));
 145         return patch(partial, b);
 146     }
 147
 148     var NUMBERS = /(-?\d+(?:\.\d+)?)/g;
 149
 150     function areNumericTwins(a, b) {
 151         /** Check if a and b differ only in numerals
 152
 153             A leading "-" counts as part of numbers; a leading "+"
 154             does not. Numbers may contain a single ".", but no other
 155             floating point syntax.
 156         */
 157         return a.replace(NUMBERS, "0") === b.replace(NUMBERS, "0");
 158     }
 159
 160     function nlerp(a, b, p) {
 161         return a + (b - a) * p;
 162     }
 163
 164     function numericLerp(a, b, p) {
 165         /** Interpolate numerically between two strings containing numbers
 166
 167             Numbers may have a leading "-" and a single "." to mark
 168             the decimal point, but something must be after the ".".
 169             If both of the numbers in a pair are integers, the result
 170             is clamped to an integer.
 171
 172             For example, numericLerp("0.0", "100", 0.123) === "12.3"
 173             because the "." in "0.0" is interpreted as a decimal
 174             point. But numericLerp("0.", "100.", 0.123) === "12."
 175             because the strings are interpreted as integers followed
 176             by a full stop.
 177
 178             Calling this functions on strings that differ in more than
 179             numerals gives undefined results.
 180          */
 181         var aParts = a.split(NUMBERS);
 182         var bParts = b.split(NUMBERS);
 183         for (var i = 1; i < aParts.length; i += 2) {
 184             var part = nlerp(+aParts[i], +bParts[i], p);
 185             if (aParts[i].indexOf(".") === -1 && bParts[i].indexOf(".") === -1)
 186                 part = Math.round(part);
 187             aParts[i] = part.toString();
 188         }
 189         return aParts.join("");
 190     }
 191
 192     function fastLerp(a, b, p) {
 193         /** Interpolate between two strings based on length
 194
 195             This interpolation algorithm progressively replaces the
 196             front of one string with another. This approach is fast
 197             but does not look good when the strings are similar.
 198         */
 199
 200         // TODO: Consider fast-pathing this even more for very large
 201         // strings, e.g. in the megabyte range. These are large enough
 202         // that
 203         if (a.match(MULTI) || b.match(MULTI)) {
 204             var ca = a.match(GLYPH) || [];
 205             var cb = b.match(GLYPH) || [];
 206             var calen = Math.round(ca.length * p);
 207             var cblen = Math.round(cb.length * p);
 208             var r = cb.slice(0, cblen);
 209             r.push.apply(r, ca.slice(calen, ca.length));
 210             return r.join("");
 211         } else {
 212             var alen = Math.round(a.length * p);
 213             var blen = Math.round(b.length * p);
 214             return b.substring(0, blen) + a.substring(alen, a.length);
 215         }
 216     }
 217
 218     function lerp(a, b, p) {
 219         /** Interpolate between two strings as best as possible
 220
 221             If the strings are identical aside from numbers in them,
 222             they are passed through numericLerp.
 223
 224             If the strings are not numbers and short, they are passed
 225             through diffLerp.
 226
 227             Otherwise, they are passed through fastLerp.
 228         */
 229         a = a.toString();
 230         b = b.toString();
 231
 232         // Fast path for boundary cases.
 233         if (p === 0) return a;
 234         if (p === 1) return b;
 235
 236         if (areNumericTwins(a, b))
 237             return numericLerp(a, b, p);
 238
 239         // Numeric lerps should over- and under-shoot when fed numbers
 240         // outside 0 to 1, but other types cannot.
 241         if (p < 0) return a;
 242         if (p > 1) return b;
 243
 244         var n = a.length * b.length;
 245         return ((n && n < MAX_MATRIX_SIZE) ? diffLerp : fastLerp)(a, b, p);
 246     }
 247
 248     exports.levenshteinMatrix = levenshteinMatrix;
 249     exports.patch = patch;
 250     exports.diff = diff;
 251     exports.fastLerp = fastLerp;
 252     exports.diffLerp = diffLerp;
 253     exports.numericLerp = numericLerp;
 254     exports.lerp = lerp;
 255
 256 })(typeof exports === "undefined" ? (this.stringLerp = {}) : exports);