(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();
  }

};

if (typeof define !== "undefined" && define !== null && define.amd) {
  define(function() {
    return Levenshtein;
  });
} else if (typeof module !== "undefined" && module !== null) {
  module.exports = Levenshtein;
} else {
  if (typeof window !== "undefined" && window !== null) {
    window.Levenshtein = Levenshtein;
  }
}

}());