diff options
Diffstat (limited to 'tools/eslint/node_modules/optionator/node_modules/fast-levenshtein/levenshtein.js')
-rw-r--r-- | tools/eslint/node_modules/optionator/node_modules/fast-levenshtein/levenshtein.js | 198 |
1 files changed, 198 insertions, 0 deletions
diff --git a/tools/eslint/node_modules/optionator/node_modules/fast-levenshtein/levenshtein.js b/tools/eslint/node_modules/optionator/node_modules/fast-levenshtein/levenshtein.js new file mode 100644 index 0000000000..0028f405ac --- /dev/null +++ b/tools/eslint/node_modules/optionator/node_modules/fast-levenshtein/levenshtein.js @@ -0,0 +1,198 @@ +(function() { + 'use strict'; + + /** + * Extend an Object with another Object's properties. + * + * The source objects are specified as additional arguments. + * + * @param dst Object the object to extend. + * + * @return Object the final object. + */ + var _extend = function(dst) { + var sources = Array.prototype.slice.call(arguments, 1); + for (var i=0; i<sources.length; ++i) { + var src = sources[i]; + for (var p in src) { + if (src.hasOwnProperty(p)) dst[p] = src[p]; + } + } + return dst; + }; + + /** + * Based on the algorithm at http://en.wikipedia.org/wiki/Levenshtein_distance. + */ + var Levenshtein = { + /** + * Calculate levenshtein distance of the two strings. + * + * @param str1 String the first string. + * @param str2 String the second string. + * @return Integer the levenshtein distance (0 and above). + */ + get: function(str1, str2) { + // base cases + if (str1 === str2) return 0; + if (str1.length === 0) return str2.length; + if (str2.length === 0) return str1.length; + + // two rows + var prevRow = new Array(str2.length + 1), + curCol, nextCol, i, j, tmp; + + // initialise previous row + for (i=0; i<prevRow.length; ++i) { + prevRow[i] = i; + } + + // calculate current row distance from previous row + for (i=0; i<str1.length; ++i) { + nextCol = i + 1; + + for (j=0; j<str2.length; ++j) { + curCol = nextCol; + + // substution + nextCol = prevRow[j] + ( (str1.charAt(i) === str2.charAt(j)) ? 0 : 1 ); + // insertion + tmp = curCol + 1; + if (nextCol > tmp) { + nextCol = tmp; + } + // deletion + tmp = prevRow[j + 1] + 1; + if (nextCol > tmp) { + nextCol = tmp; + } + + // copy current col value into previous (in preparation for next iteration) + prevRow[j] = curCol; + } + + // copy last col value into previous (in preparation for next iteration) + prevRow[j] = nextCol; + } + + return nextCol; + }, + + /** + * Asynchronously calculate levenshtein distance of the two strings. + * + * @param str1 String the first string. + * @param str2 String the second string. + * @param cb Function callback function with signature: function(Error err, int distance) + * @param [options] Object additional options. + * @param [options.progress] Function progress callback with signature: function(percentComplete) + */ + getAsync: function(str1, str2, cb, options) { + options = _extend({}, { + progress: null + }, options); + + // base cases + if (str1 === str2) return cb(null, 0); + if (str1.length === 0) return cb(null, str2.length); + if (str2.length === 0) return cb(null, str1.length); + + // two rows + var prevRow = new Array(str2.length + 1), + curCol, nextCol, + i, j, tmp, + startTime, currentTime; + + // initialise previous row + for (i=0; i<prevRow.length; ++i) { + prevRow[i] = i; + } + + nextCol = 1; + i = 0; + j = -1; + + var __calculate = function() { + // reset timer + startTime = new Date().valueOf(); + currentTime = startTime; + + // keep going until one second has elapsed + while (currentTime - startTime < 1000) { + // reached end of current row? + if (str2.length <= (++j)) { + // copy current into previous (in preparation for next iteration) + prevRow[j] = nextCol; + + // if already done all chars + if (str1.length <= (++i)) { + return cb(null, nextCol); + } + // else if we have more left to do + else { + nextCol = i + 1; + j = 0; + } + } + + // calculation + curCol = nextCol; + + // substution + nextCol = prevRow[j] + ( (str1.charAt(i) === str2.charAt(j)) ? 0 : 1 ); + // insertion + tmp = curCol + 1; + if (nextCol > tmp) { + nextCol = tmp; + } + // deletion + tmp = prevRow[j + 1] + 1; + if (nextCol > tmp) { + nextCol = tmp; + } + + // copy current into previous (in preparation for next iteration) + prevRow[j] = curCol; + + // get current time + currentTime = new Date().valueOf(); + } + + // send a progress update? + if (null !== options.progress) { + try { + options.progress.call(null, (i * 100.0/ str1.length)); + } catch (err) { + return cb('Progress callback: ' + err.toString()); + } + } + + // next iteration + setTimeout(__calculate(), 0); + }; + + __calculate(); + } + + }; + + // amd + if (typeof define !== "undefined" && define !== null && define.amd) { + define(function() { + return Levenshtein; + }); + } + // commonjs + else if (typeof module !== "undefined" && module !== null) { + module.exports = Levenshtein; + } + // web worker + else if (typeof self !== "undefined" && typeof self.postMessage === 'function' && typeof self.importScripts === 'function') { + self.Levenshtein = Levenshtein; + } + // browser main thread + else if (typeof window !== "undefined" && window !== null) { + window.Levenshtein = Levenshtein; + } +}()); + |