4a2c80f1533cad299063a7bdcc644defa5e5fe8b
4 var MAX_MATRIX_SIZE
= 256 * 256;
6 function repeat(n
, v
) {
13 function createMatrix(i
, j
) {
20 function levenshteinMatrix(s
, t
) {
21 /** Calculate the Levenshtein edit distance matrix for two strings
23 // Following http://en.wikipedia.org/wiki/Levenshtein_distance
27 var d
= createMatrix(m
, n
);
29 for (i
= 1; i
< m
; ++i
)
31 for (j
= 1; j
< n
; ++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];
38 d
[i
][j
] = 1 + Math
.min(d
[i
- 1][ j
],
44 function editPath(m
, s
, t
) {
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]]);
56 } else if (ins
<= del
) {
57 path
.push(["ins", i
, t
[j
- 1]]);
60 path
.push(["del", i
- 1]);
67 function applyEdits(edits
, s
, t
) {
69 for (i
= 0; i
< edits
.length
; ++i
) {
73 s
= s
.slice(0, edit
[1]) + edit
[2] + s
.slice(edit
[1] + 1);
76 s
= s
.slice(0, edit
[1]) + edit
[2] + s
.slice(edit
[1]);
79 s
= s
.slice(0, edit
[1]) + s
.slice(edit
[1] + 1);
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
);
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
);
99 function lerp(a
, b
, p
) {
102 var n
= a
.length
* b
.length
;
103 return (n
&& n
< MAX_MATRIX_SIZE
)
108 exports
.levenshteinMatrix
= levenshteinMatrix
;
109 exports
.editPath
= editPath
;
110 exports
.fastLerp
= fastLerp
;
111 exports
.slowLerp
= slowLerp
;
112 exports
.applyEdits
= applyEdits
;
115 })(typeof exports
=== "undefined" ? (this.stringLerp
= {}) : exports
);