var makeString = require('./helper/makeString');
  
  /**
   * Based on the implementation here: https://github.com/hiddentao/fast-levenshtein
   */
  module.exports = function levenshtein(str1, str2) {
    'use strict';
    str1 = makeString(str1);
    str2 = makeString(str2);
  
    // Short cut cases  
    if (str1 === str2) return 0;
    if (!str1 || !str2) return Math.max(str1.length, str2.length);
  
    // two rows
    var prevRow = new Array(str2.length + 1);
  
    // initialise previous row
    for (var i = 0; i < prevRow.length; ++i) {
      prevRow[i] = i;
    }
  
    // calculate current row distance from previous row
    for (i = 0; i < str1.length; ++i) {
      var nextCol = i + 1;
  
      for (var j = 0; j < str2.length; ++j) {
        var curCol = nextCol;
  
        // substution
        nextCol = prevRow[j] + ( (str1.charAt(i) === str2.charAt(j)) ? 0 : 1 );
        // insertion
        var 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;
  };