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