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         var edits = diff(a, b);
  92         var partial = edits.slice(0, Math.round(p * edits.length));
  93         return patch(partial, a);
  94     }
  95
  96     var NUMBERS = /(-?\d+(?:\.\d+)?)/g
  97
  98     function areNumericTwins(a, b) {
  99         /** Check if a and b differ only in numerals
 100
 101             A leading "-" counts as part of numbers; a leading "+"
 102             does not. Numbers may contain a single ".", but no other
 103             floating point syntax.
 104         */
 105         return a.replace(NUMBERS, "0") === b.replace(NUMBERS, "0");
 106     }
 107
 108     function nlerp(a, b, p) {
 109         return a + (b - a) * p;
 110     }
 111
 112     function numericLerp(a, b, p) {
 113         /** Interpolate numerically between two strings containing numbers
 114
 115             Numbers may have a leading "-" and a single "." to mark
 116             the decimal point, but something must be after the ".".
 117             If both of the numbers in a pair are integers, the result
 118             is clamped to an integer.
 119
 120             For example, numericLerp("0.0", "100", 0.123) === "12.3"
 121             because the "." in "0.0" is intepreted as a decimal point.
 122             But numericLerp("0.", "100.", 0.123) === "12." because the
 123             strings are interpreted as integers followed by a full
 124             stop.
 125
 126             Calling this functions on strings that differ in more than
 127             numerals gives undefined results.
 128          */
 129         var aParts = a.split(NUMBERS);
 130         var bParts = b.split(NUMBERS);
 131         for (var i = 1; i < aParts.length; i += 2) {
 132             var part = nlerp(+aParts[i], +bParts[i], p)
 133             if (aParts[i].indexOf(".") === -1 && bParts[i].indexOf(".") === -1)
 134                 part = Math.round(part);
 135             aParts[i] = part.toString();
 136         }
 137         return aParts.join("");
 138     }
 139
 140     function fastLerp(a, b, p) {
 141         /** Interpolate between two strings based on length
 142
 143             This interpolation algorithm progressively replaces the
 144             front of one string with another. This approach is fast
 145             but does not look good when the strings are similar.
 146         */
 147         var alen = Math.round(a.length * p);
 148         var blen = Math.round(b.length * p);
 149         return b.substring(0, blen) + a.substring(alen, a.length);
 150     }
 151
 152     function lerp(a, b, p) {
 153         /** Interpolate between two strings as best as possible
 154
 155             If the strings are identical aside from numbers in them,
 156             they are passed through numericLerp.
 157
 158             If the strings are not numbers and short, they are passed
 159             through diffLerp.
 160
 161             Otherwise, they are passed through fastLerp.
 162         */
 163         a = a.toString();
 164         b = b.toString();
 165
 166         // Fast path for boundary cases.
 167         if (p === 0) return a;
 168         if (p === 1) return b;
 169
 170         if (areNumericTwins(a, b))
 171             return numericLerp(a, b, p)
 172
 173         // Numeric lerps should over- and under-shoot when fed numbers
 174         // outside 0 to 1, but other types cannot.
 175         if (p < 0) return a;
 176         if (p > 1) return b;
 177
 178         var n = a.length * b.length;
 179         return (n && n < MAX_MATRIX_SIZE)
 180             ? diffLerp(a, b, p)
 181             : fastLerp(a, b, p);
 182     }
 183
 184     exports.levenshteinMatrix = levenshteinMatrix;
 185     exports.patch = patch;
 186     exports.diff = diff;
 187     exports.fastLerp = fastLerp;
 188     exports.diffLerp = diffLerp;
 189     exports.numericLerp = numericLerp;
 190     exports.lerp = lerp;
 191
 192 })(typeof exports === "undefined" ? (this.stringLerp = {}) : exports);