/**
 * Autocompleter.Local.Levenshtein
 *
 * http://www.wennet.nl
 *
 * @author		Tim Bijkerk <tim [at] wennet.nl>
 * @copyright	Author
 */


Autocompleter.Local.Levenshtein = new Class({

	Extends: Autocompleter.Local,
	
	filter: function(tokens) {
		var self = this;
		var values = new Hash();
			
		$each(this.parent(tokens), function(token){
			values[self.levenshtein(self.queryValue, token)] = token;
		});
		
		values = self.sortByKey(values);
		
		return values;
	},
	
	sortByKey: function(hash){
		var values = [];
        keysToSort = hash.getKeys();
                
        keysToSort = keysToSort.sort(
        	(function(a, b){ return a - b; })
        );
        
        for (var i = 0; i < hash.getLength(); i++){
        	values.push(hash[keysToSort[i]]);
        }
        
        return values; 
	},
	
	levenshtein: function(min, split){
		 // Levenshtein Algorithm Revisited - WebReflection
	    try{split=!("0")[0]}catch(i){split=true};
	    return function(a, b){
	        if(a == b)return 0;
	        if(!a.length || !b.length)return b.length || a.length;
	        if(split){a = a.split("");b = b.split("")};
	        var len1 = a.length + 1,
	            len2 = b.length + 1,
	            I = 0,
	            i = 0,
	            d = [[0]],
	            c, j, J;
	        while(++i < len2)
	            d[0][i] = i;
	        i = 0;
	        while(++i < len1){
	            J = j = 0;
	            c = a[I];
	            d[i] = [i];
	            while(++j < len2){
	                d[i][j] = min(d[I][j] + 1, d[i][J] + 1, d[I][J] + (c != b[J]));
	                ++J;
	            };
	            ++I;
	        };
	        return d[len1 - 1][len2 - 1];
	    }	
	}(Math.min, false)

});