1 files changed, 75 insertions, 148 deletions

diff --git a/src/js/levenshtein.js b/src/js/levenshtein.js
index 3051ec5..a57b8fb 100644
--- a/src/js/levenshtein.js
+++ b/src/js/levenshtein.js
@@ -1,38 +1,17 @@
+// source
+// https://github.com/hiddentao/fast-levenshtein/blob/2.0.6/levenshtein.js
 (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;
-  };
-
-
-  /**
-   * Defer execution of given function.
-   * @param  {Function} func
-   */
-  var _defer = function(func) {
-    if (typeof setImmediate === 'function') {
-      return setImmediate(func);
-    } else {
-      return setTimeout(func, 0);
-    }
-  };
+  var collator;
+  try {
+    collator = (typeof Intl !== "undefined" && typeof Intl.Collator !== "undefined") ? Intl.Collator("generic", { sensitivity: "base" }) : null;
+  } catch (err){
+    console.log("Collator could not be initialized and wouldn't be used");
+  }
+  // arrays to re-use
+  var prevRow = [],
+    str2Char = [];
 
   /**
    * Based on the algorithm at http://en.wikipedia.org/wiki/Levenshtein_distance.
@@ -43,148 +22,96 @@
      *
      * @param str1 String the first string.
      * @param str2 String the second string.
+     * @param [options] Additional options.
+     * @param [options.useCollator] Use `Intl.Collator` for locale-sensitive string comparison.
      * @return Integer the levenshtein distance (0 and above).
      */
-    get: function(str1, str2) {
+    get: function(str1, str2, options) {
+      var useCollator = (options && collator && options.useCollator);
+
+      var str1Len = str1.length,
+        str2Len = str2.length;
+
       // base cases
-      if (str1 === str2) return 0;
-      if (str1.length === 0) return str2.length;
-      if (str2.length === 0) return str1.length;
+      if (str1Len === 0) return str2Len;
+      if (str2Len === 0) return str1Len;
 
       // two rows
-      var prevRow  = new Array(str2.length + 1),
-          curCol, nextCol, i, j, tmp;
+      var curCol, nextCol, i, j, tmp;
 
       // initialise previous row
-      for (i=0; i<prevRow.length; ++i) {
+      for (i=0; i<str2Len; ++i) {
         prevRow[i] = i;
+        str2Char[i] = str2.charCodeAt(i);
       }
+      prevRow[str2Len] = str2Len;
 
-      // calculate current row distance from previous row
-      for (i=0; i<str1.length; ++i) {
-        nextCol = i + 1;
+      var strCmp;
+      if (useCollator) {
+        // calculate current row distance from previous row using collator
+        for (i = 0; i < str1Len; ++i) {
+          nextCol = i + 1;
 
-        for (j=0; j<str2.length; ++j) {
-          curCol = nextCol;
+          for (j = 0; j < str2Len; ++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;
-          }
+            // substution
+            strCmp = 0 === collator.compare(str1.charAt(i), String.fromCharCode(str2Char[j]));
 
-          // copy current col value into previous (in preparation for next iteration)
-          prevRow[j] = curCol;
-        }
+            nextCol = prevRow[j] + (strCmp ? 0 : 1);
 
-        // copy last col value into previous (in preparation for next iteration)
-        prevRow[j] = nextCol;
-      }
+            // insertion
+            tmp = curCol + 1;
+            if (nextCol > tmp) {
+              nextCol = tmp;
+            }
+            // deletion
+            tmp = prevRow[j + 1] + 1;
+            if (nextCol > tmp) {
+              nextCol = tmp;
+            }
 
-      return nextCol;
-    },
+            // copy current col value into previous (in preparation for next iteration)
+            prevRow[j] = curCol;
+          }
 
-    /**
-     * 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);
+          // copy last col value into previous (in preparation for next iteration)
+          prevRow[j] = nextCol;
+        }
+      }
+      else {
+        // calculate current row distance from previous row without collator
+        for (i = 0; i < str1Len; ++i) {
+          nextCol = i + 1;
 
-      // 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);
+          for (j = 0; j < str2Len; ++j) {
+            curCol = nextCol;
 
-      // two rows
-      var prevRow  = new Array(str2.length + 1),
-          curCol, nextCol,
-          i, j, tmp,
-          startTime, currentTime;
+            // substution
+            strCmp = str1.charCodeAt(i) === str2Char[j];
 
-      // initialise previous row
-      for (i=0; i<prevRow.length; ++i) {
-        prevRow[i] = i;
-      }
+            nextCol = prevRow[j] + (strCmp ? 0 : 1);
 
-      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);
+            // insertion
+            tmp = curCol + 1;
+            if (nextCol > tmp) {
+              nextCol = tmp;
             }
-            // else if we have more left to do
-            else {
-              nextCol = i + 1;
-              j = 0;
+            // deletion
+            tmp = prevRow[j + 1] + 1;
+            if (nextCol > tmp) {
+              nextCol = tmp;
             }
-          }
-
-          // 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 col value into previous (in preparation for next iteration)
+            prevRow[j] = curCol;
           }
 
-          // copy current into previous (in preparation for next iteration)
-          prevRow[j] = curCol;
-
-          // get current time
-          currentTime = new Date().valueOf();
+          // copy last col value into previous (in preparation for next iteration)
+          prevRow[j] = nextCol;
         }
-
-        // 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
-        _defer(__calculate);
-      };
-
-      __calculate();
+      }
+      return nextCol;
     }
 
   };