string-lerp.js

   1 (function (exports) {
   2     "use strict";
   3
   4     var MAX_MATRIX_SIZE = 256 * 256;
   5
   6     function repeat(n, v) {
   7         var r = [];
   8         while (n--)
   9             r.push(v);
  10         return r;
  11     }
  12
  13     function createMatrix(i, j) {
  14         var m = [];
  15         while (i--)
  16             m.push(repeat(j, 0));
  17         return m;
  18     }
  19
  20     function levenshteinMatrix(s, t) {
  21         /** Calculate the Levenshtein edit distance matrix for two strings
  22
  23         // Following http://en.wikipedia.org/wiki/Levenshtein_distance
  24         */
  25         var m = s.length + 1;
  26         var n = t.length + 1;
  27         var d = createMatrix(m, n);
  28         var i, j;
  29         for (i = 1; i < m; ++i)
  30             d[i][0] = i;
  31         for (j = 1; j < n; ++j)
  32             d[0][j] = j;
  33         for (j = 1; j < n; ++j)
  34             for (i = 1; i < m; ++i)
  35                 if (s[i - 1] === t[j - 1])
  36                     d[i][j] = d[i - 1][j - 1];
  37                 else
  38                     d[i][j] = 1 + Math.min(d[i - 1][  j  ],
  39                                            d[  i  ][j - 1],
  40                                            d[i - 1][j - 1]);
  41         return d;
  42     }
  43
  44     function editPath(m, s, t) {
  45         var path = []
  46         var i = s.length;
  47         var j = t.length;
  48         while (i || j) {
  49             var sub = (i && j) ? m[i - 1][j - 1] : Infinity;
  50             var del = i ? m[i - 1][j] : Infinity;
  51             var ins = j ? m[i][j - 1] : Infinity;
  52             if (sub <= ins && sub <= del) {
  53                 if (m[i][j] !== m[i - 1][j - 1])
  54                     path.push(["sub", i - 1, t[j - 1]]);
  55                 --i; --j;
  56             } else if (ins <= del) {
  57                 path.push(["ins", i, t[j - 1]]);
  58                 --j;
  59             } else {
  60                 path.push(["del", i - 1]);
  61                 --i;
  62             }
  63         }
  64         return path;
  65     }
  66
  67     function applyEdits(edits, s, t) {
  68         var i;
  69         for (i = 0; i < edits.length; ++i) {
  70             var edit = edits[i];
  71             switch (edit[0]) {
  72             case "sub":
  73                 s = s.slice(0, edit[1]) + edit[2] + s.slice(edit[1] + 1);
  74                 break;
  75             case "ins":
  76                 s = s.slice(0, edit[1]) + edit[2] + s.slice(edit[1]);
  77                 break;
  78             case "del":
  79                 s = s.slice(0, edit[1]) + s.slice(edit[1] + 1);
  80                 break;
  81             }
  82         }
  83         return s;
  84     }
  85
  86     function slowLerp(a, b, p) {
  87         var m = levenshteinMatrix(a, b);
  88         var edits = editPath(m, a, b);
  89         var partial = edits.slice(0, Math.round(p * edits.length));
  90         return applyEdits(partial, a, b);
  91     }
  92
  93     function fastLerp(a, b, p) {
  94         var alen = Math.round(a.length * p);
  95         var blen = Math.round(b.length * p);
  96         return b.substring(0, blen) + a.substring(alen, a.length);
  97     }
  98
  99     function lerp(a, b, p) {
 100         a = a.toString();
 101         b = b.toString();
 102         var n = a.length * b.length;
 103         return (n && n < MAX_MATRIX_SIZE)
 104             ? slowLerp(a, b, p)
 105             : fastLerp(a, b, p);
 106     }
 107
 108     exports.levenshteinMatrix = levenshteinMatrix;
 109     exports.editPath = editPath;
 110     exports.fastLerp = fastLerp;
 111     exports.slowLerp = slowLerp;
 112     exports.applyEdits = applyEdits;
 113     exports.lerp = lerp;
 114
 115 })(typeof exports === "undefined" ? (this.stringLerp = {}) : exports);