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 slowLerp(a, b, p) {
  83         /** Interpolate between two strings slowly
  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     function fastLerp(a, b, p) {
  97         /** Interpolate between two strings very quickly
  98
  99             This interpolation algorithm progressively replaces the
 100             front of one string with another. This approach is fast
 101             but does not look good when the strings are similar.
 102          */
 103         var alen = Math.round(a.length * p);
 104         var blen = Math.round(b.length * p);
 105         return b.substring(0, blen) + a.substring(alen, a.length);
 106     }
 107
 108     function lerp(a, b, p) {
 109         a = a.toString();
 110         b = b.toString();
 111         var n = a.length * b.length;
 112         // TODO: if both strings are integers, do an integer lerp.
 113         // TODO: if both strings are numbers, do a numeric lerp.
 114         return (n && n < MAX_MATRIX_SIZE)
 115             ? slowLerp(a, b, p)
 116             : fastLerp(a, b, p);
 117     }
 118
 119     exports.levenshteinMatrix = levenshteinMatrix;
 120     exports.patch = patch;
 121     exports.diff = diff;
 122     exports.fastLerp = fastLerp;
 123     exports.slowLerp = slowLerp;
 124     exports.lerp = lerp;
 125
 126 })(typeof exports === "undefined" ? (this.stringLerp = {}) : exports);