string-lerp.js

   1 (function (exports) {
   2     "use strict";
   3
   4     var MAX_MATRIX_SIZE = 256 * 256;
   5
   6     function levenshteinMatrix(s, t) {
   7         /** Calculate the Levenshtein edit distance matrix for two strings
   8
   9             The matrix is returned as a flat unsigned typed array.
  10
  11             Following http://en.wikipedia.org/wiki/Levenshtein_distance
  12         */
  13         var m = s.length + 1;
  14         var n = t.length + 1;
  15         var d = new Uint32Array(m * n);
  16         var i, j;
  17         for (i = 1; i < m; ++i)
  18             d[n * i] = i;
  19         for (j = 1; j < n; ++j)
  20             d[j] = j;
  21         for (j = 1; j < n; ++j)
  22             for (i = 1; i < m; ++i)
  23                 if (s[i - 1] === t[j - 1])
  24                     d[n * i + j] = d[n * (i - 1) + j - 1];
  25                 else
  26                     d[n * i + j] = 1 + Math.min(d[n * (i - 1) + j    ],
  27                                                 d[n *    i    + j - 1],
  28                                                 d[n * (i - 1) + j - 1]);
  29         return d;
  30     }
  31
  32     function editPath(d, t) {
  33         /** Given a Levenshtein matrix and target, create an edit list */
  34         var path = [];
  35         var j = t.length;
  36         var n = j + 1;
  37         var i = d.length / n - 1;
  38         while (i || j) {
  39             var sub = (i && j) ? d[n * (i - 1) + j - 1] : Infinity;
  40             var del = i ? d[n * (i - 1) + j] : Infinity;
  41             var ins = j ? d[n * i + j - 1] : Infinity;
  42             if (sub <= ins && sub <= del) {
  43                 if (d[n * i + j] !== d[n * (i - 1) + j - 1])
  44                     path.push(["sub", i - 1, t[j - 1]]);
  45                 --i; --j;
  46             } else if (ins <= del) {
  47                 path.push(["ins", i, t[j - 1]]);
  48                 --j;
  49             } else {
  50                 path.push(["del", i - 1]);
  51                 --i;
  52             }
  53         }
  54         return path;
  55     }
  56
  57     function diff(s, t) {
  58         /** Create a diff between string s and t */
  59         return editPath(levenshteinMatrix(s, t), t);
  60     }
  61
  62     function patch(edits, s) {
  63         /** Apply the list of edits to s */
  64         var i;
  65         for (i = 0; i < edits.length; ++i) {
  66             var edit = edits[i];
  67             switch (edit[0]) {
  68             case "sub":
  69                 s = s.slice(0, edit[1]) + edit[2] + s.slice(edit[1] + 1);
  70                 break;
  71             case "ins":
  72                 s = s.slice(0, edit[1]) + edit[2] + s.slice(edit[1]);
  73                 break;
  74             case "del":
  75                 s = s.slice(0, edit[1]) + s.slice(edit[1] + 1);
  76                 break;
  77             }
  78         }
  79         return s;
  80     }
  81
  82     function diffLerp(a, b, p) {
  83         /** Interpolate between two strings based on edit distance
  84
  85             This interpolation algorithm applys a partial edit of one
  86             string into the other. This produces nice looking results,
  87             but can take a significant amount of time and memory to
  88             compute the edits. It is not recommended for strings
  89             longer than a few hundred characters.
  90          */
  91
  92         // The edit path works from the string end, forwards, because
  93         // that's how Levenshtein edits work. To match LTR reading
  94         // direction (and the behavior of fastLerp), swap the strings
  95         // and invert the parameter when editing.
  96         var edits = diff(b, a);
  97         var partial = edits.slice(0, Math.round((1 - p) * edits.length));
  98         return patch(partial, b);
  99     }
 100
 101     var NUMBERS = /(-?\d+(?:\.\d+)?)/g;
 102
 103     function areNumericTwins(a, b) {
 104         /** Check if a and b differ only in numerals
 105
 106             A leading "-" counts as part of numbers; a leading "+"
 107             does not. Numbers may contain a single ".", but no other
 108             floating point syntax.
 109         */
 110         return a.replace(NUMBERS, "0") === b.replace(NUMBERS, "0");
 111     }
 112
 113     function nlerp(a, b, p) {
 114         return a + (b - a) * p;
 115     }
 116
 117     function numericLerp(a, b, p) {
 118         /** Interpolate numerically between two strings containing numbers
 119
 120             Numbers may have a leading "-" and a single "." to mark
 121             the decimal point, but something must be after the ".".
 122             If both of the numbers in a pair are integers, the result
 123             is clamped to an integer.
 124
 125             For example, numericLerp("0.0", "100", 0.123) === "12.3"
 126             because the "." in "0.0" is intepreted as a decimal point.
 127             But numericLerp("0.", "100.", 0.123) === "12." because the
 128             strings are interpreted as integers followed by a full
 129             stop.
 130
 131             Calling this functions on strings that differ in more than
 132             numerals gives undefined results.
 133          */
 134         var aParts = a.split(NUMBERS);
 135         var bParts = b.split(NUMBERS);
 136         for (var i = 1; i < aParts.length; i += 2) {
 137             var part = nlerp(+aParts[i], +bParts[i], p);
 138             if (aParts[i].indexOf(".") === -1 && bParts[i].indexOf(".") === -1)
 139                 part = Math.round(part);
 140             aParts[i] = part.toString();
 141         }
 142         return aParts.join("");
 143     }
 144
 145     function fastLerp(a, b, p) {
 146         /** Interpolate between two strings based on length
 147
 148             This interpolation algorithm progressively replaces the
 149             front of one string with another. This approach is fast
 150             but does not look good when the strings are similar.
 151         */
 152         var alen = Math.round(a.length * p);
 153         var blen = Math.round(b.length * p);
 154         return b.substring(0, blen) + a.substring(alen, a.length);
 155     }
 156
 157     function lerp(a, b, p) {
 158         /** Interpolate between two strings as best as possible
 159
 160             If the strings are identical aside from numbers in them,
 161             they are passed through numericLerp.
 162
 163             If the strings are not numbers and short, they are passed
 164             through diffLerp.
 165
 166             Otherwise, they are passed through fastLerp.
 167         */
 168         a = a.toString();
 169         b = b.toString();
 170
 171         // Fast path for boundary cases.
 172         if (p === 0) return a;
 173         if (p === 1) return b;
 174
 175         if (areNumericTwins(a, b))
 176             return numericLerp(a, b, p);
 177
 178         // Numeric lerps should over- and under-shoot when fed numbers
 179         // outside 0 to 1, but other types cannot.
 180         if (p < 0) return a;
 181         if (p > 1) return b;
 182
 183         var n = a.length * b.length;
 184         return ((n && n < MAX_MATRIX_SIZE) ? diffLerp : fastLerp)(a, b, p);
 185     }
 186
 187     exports.levenshteinMatrix = levenshteinMatrix;
 188     exports.patch = patch;
 189     exports.diff = diff;
 190     exports.fastLerp = fastLerp;
 191     exports.diffLerp = diffLerp;
 192     exports.numericLerp = numericLerp;
 193     exports.lerp = lerp;
 194
 195 })(typeof exports === "undefined" ? (this.stringLerp = {}) : exports);