vnfmarket/src/main/webapp/vnfmarket/node_modules/fast-levenshtein/levenshtein.js

   1 (function() {
   2   'use strict';
   3
   4   /**
   5    * Extend an Object with another Object's properties.
   6    *
   7    * The source objects are specified as additional arguments.
   8    *
   9    * @param dst Object the object to extend.
  10    *
  11    * @return Object the final object.
  12    */
  13   var _extend = function(dst) {
  14     var sources = Array.prototype.slice.call(arguments, 1);
  15     for (var i=0; i<sources.length; ++i) {
  16       var src = sources[i];
  17       for (var p in src) {
  18         if (src.hasOwnProperty(p)) dst[p] = src[p];
  19       }
  20     }
  21     return dst;
  22   };
  23
  24   /**
  25    * Based on the algorithm at http://en.wikipedia.org/wiki/Levenshtein_distance.
  26    */
  27   var Levenshtein = {
  28     /**
  29      * Calculate levenshtein distance of the two strings.
  30      *
  31      * @param str1 String the first string.
  32      * @param str2 String the second string.
  33      * @return Integer the levenshtein distance (0 and above).
  34      */
  35     get: function(str1, str2) {
  36       // base cases
  37       if (str1 === str2) return 0;
  38       if (str1.length === 0) return str2.length;
  39       if (str2.length === 0) return str1.length;
  40
  41       // two rows
  42       var prevRow  = new Array(str2.length + 1),
  43           curCol, nextCol, i, j, tmp;
  44
  45       // initialise previous row
  46       for (i=0; i<prevRow.length; ++i) {
  47         prevRow[i] = i;
  48       }
  49
  50       // calculate current row distance from previous row
  51       for (i=0; i<str1.length; ++i) {
  52         nextCol = i + 1;
  53
  54         for (j=0; j<str2.length; ++j) {
  55           curCol = nextCol;
  56
  57           // substution
  58           nextCol = prevRow[j] + ( (str1.charAt(i) === str2.charAt(j)) ? 0 : 1 );
  59           // insertion
  60           tmp = curCol + 1;
  61           if (nextCol > tmp) {
  62             nextCol = tmp;
  63           }
  64           // deletion
  65           tmp = prevRow[j + 1] + 1;
  66           if (nextCol > tmp) {
  67             nextCol = tmp;
  68           }
  69
  70           // copy current col value into previous (in preparation for next iteration)
  71           prevRow[j] = curCol;
  72         }
  73
  74         // copy last col value into previous (in preparation for next iteration)
  75         prevRow[j] = nextCol;
  76       }
  77
  78       return nextCol;
  79     },
  80
  81     /**
  82      * Asynchronously calculate levenshtein distance of the two strings.
  83      *
  84      * @param str1 String the first string.
  85      * @param str2 String the second string.
  86      * @param cb Function callback function with signature: function(Error err, int distance)
  87      * @param [options] Object additional options.
  88      * @param [options.progress] Function progress callback with signature: function(percentComplete)
  89      */
  90     getAsync: function(str1, str2, cb, options) {
  91       options = _extend({}, {
  92         progress: null
  93       }, options);
  94
  95       // base cases
  96       if (str1 === str2) return cb(null, 0);
  97       if (str1.length === 0) return cb(null, str2.length);
  98       if (str2.length === 0) return cb(null, str1.length);
  99
 100       // two rows
 101       var prevRow  = new Array(str2.length + 1),
 102           curCol, nextCol,
 103           i, j, tmp,
 104           startTime, currentTime;
 105
 106       // initialise previous row
 107       for (i=0; i<prevRow.length; ++i) {
 108         prevRow[i] = i;
 109       }
 110
 111       nextCol = 1;
 112       i = 0;
 113       j = -1;
 114
 115       var __calculate = function() {
 116         // reset timer
 117         startTime = new Date().valueOf();
 118         currentTime = startTime;
 119
 120         // keep going until one second has elapsed
 121         while (currentTime - startTime < 1000) {
 122           // reached end of current row?
 123           if (str2.length <= (++j)) {
 124             // copy current into previous (in preparation for next iteration)
 125             prevRow[j] = nextCol;
 126
 127             // if already done all chars
 128             if (str1.length <= (++i)) {
 129               return cb(null, nextCol);
 130             }
 131             // else if we have more left to do
 132             else {
 133               nextCol = i + 1;
 134               j = 0;
 135             }
 136           }
 137
 138           // calculation
 139           curCol = nextCol;
 140
 141           // substution
 142           nextCol = prevRow[j] + ( (str1.charAt(i) === str2.charAt(j)) ? 0 : 1 );
 143           // insertion
 144           tmp = curCol + 1;
 145           if (nextCol > tmp) {
 146             nextCol = tmp;
 147           }
 148           // deletion
 149           tmp = prevRow[j + 1] + 1;
 150           if (nextCol > tmp) {
 151             nextCol = tmp;
 152           }
 153
 154           // copy current into previous (in preparation for next iteration)
 155           prevRow[j] = curCol;
 156
 157           // get current time
 158           currentTime = new Date().valueOf();
 159         }
 160
 161         // send a progress update?
 162         if (null !== options.progress) {
 163           try {
 164             options.progress.call(null, (i * 100.0/ str1.length));
 165           } catch (err) {
 166             return cb('Progress callback: ' + err.toString());
 167           }
 168         }
 169
 170         // next iteration
 171         setTimeout(__calculate(), 0);
 172       };
 173
 174       __calculate();
 175     }
 176
 177   };
 178
 179   // amd
 180   if (typeof define !== "undefined" && define !== null && define.amd) {
 181     define(function() {
 182       return Levenshtein;
 183     });
 184   }
 185   // commonjs
 186   else if (typeof module !== "undefined" && module !== null) {
 187     module.exports = Levenshtein;
 188   }
 189   // web worker
 190   else if (typeof self !== "undefined" && typeof self.postMessage === 'function' && typeof self.importScripts === 'function') {
 191     self.Levenshtein = Levenshtein;
 192   }
 193   // browser main thread
 194   else if (typeof window !== "undefined" && window !== null) {
 195     window.Levenshtein = Levenshtein;
 196   }
 197 }());
 198