/* Novusoft.Utils 
	requires: Novusoft, Novusoft.Settings
*/
Novusoft.registerNamespace("Novusoft.Utils");

/**
 *	Levenshtein distance (LD) is a measure of the similarity between two strings, 
 *	which we will refer to as the source string (a) and the target string (b). 
 *	The distance is the number of deletions, insertions, or substitutions required
 *	to transform a into b.
 *	
 *	adopted from http://www.merriampark.com/ld.htm 
 *	
 *	When Novusoft.Settings.AddPrototypes is set to true, "a".levenshteinDistance("b") 
 *	also works.
 *	
 *	@param {string} a The first string.
 *	@param {string} b The second string.
 *	@return {integer} The distance between the two strings.	
 */
Novusoft.Utils.levenshteinDistance = function(a, b) {
	var n = a.length;
	var m = b.length;

	if(!(n&&m)) { return n||m };

	var d = [];
	for (var i = 0; i <= n; i++) { d[i] = []; d[i][0] = i; }	
	for (var j = 0; j <= m; j++) { d[0][j] = j; }

	for (var i = 1; i <= n; i++) {
		s_i = a.charAt (i - 1);
		for (var j = 1; j <= m; j++) {
			t_j = b.charAt (j - 1);
			cost = (s_i == t_j) ? 0 : 1;
			d[i][j] = Math.min(d[i-1][j]+1, d[i][j-1]+1, d[i-1][j-1] + cost);
		}		
	}
	return d[n][m];
};

if(Novusoft.Settings.AddPrototypes) {
	String.prototype.levenshteinDistance = function(b) { return Novusoft.Utils.levenshteinDistance(this,b) };
};


/**
 *	Takes a String s and a List with strings input and returns the index into the list
 *	that matches 's' closest according to levenshteinDistance.
 *	
 *	Compares using levenshteinDistance, additionally it prunes strings to equal length
 *	and gives extra weight to first character.
 *
 * @param {string} The target string
 * @param {array} The array with strings
 * @return {integer} Index into the array with the closest match
 */
Novusoft.Utils.findClosestString = function(s, lis) {
	s = s.toLowerCase();

	var d2 = 1e60;
	var sel = -1;

	for(var i =0; i < lis.length; i++) {
		var clipped = lis[i].substring(0, Math.min(lis[i].length, s.length)).toLowerCase();
		var d = Novusoft.Utils.levenshteinDistance(clipped, s);
		if(clipped.charAt(0) == s.charAt(0)) { d -= 1; } //add extra weight to matching first char
		if(d < d2) { d2 = d; sel = i }
	}
	return sel;
};

/*
Novusoft.Utils.trim = function(a) {
	return a.replace(/^\s+|\s+$/g,"");
};

if(Novusoft.Settings.AddPrototypes) {
	String.prototype.trim = function() { return Novusoft.Utils.trim(this) };
}; */