String.scoring_options = {firstChar : 0.5,acronym : 2.2,capitalLetter : 0.8,caseMatch : 0.3,consecutiveChars : 0.5,nonConsecutiveChars : -0.2,missingMatch : -6,outOfOrder : {score: -1.5,multiplier: 0.1}};
Array.prototype.remove = function(index){return this.splice(index,1)[0];};
Array.prototype.includes = function(value){
var i,len=this.length;
for(i=0;i<len;i++){
if(this[i]===value)return true;
}
return false;
};
Array.prototype.count_how = function(how){
var i,count=0,len=this.length;
for(i=0;i<len;i++){
if(how.apply(this[i]))count+=1;
}
return count;
};
Array.prototype.each = function(cb){
var i,len=this.length;
for(i=0;i<len;i++){
cb.apply(this[i], [i]);
}
return this;
};
Array.prototype.map = function(cb){
var i,len=this.length,a=[];
for(i=0;i<len;i++){
a.push(cb.apply(this[i]));
}
return a;
};
Array.prototype.highest = function(how){
return this[this.highest_i(how)];
};
Array.prototype.highest_i = function(how){
var i,s,best_s=this[0],best_i=0,len=this.length;
for(i=0;i<len;i++){
if(how)s=how(this[i]);
else s=this[i];
if(s>best_s){
best_s=s;
best_i=i;
}
}
return best_i;
};
String.prototype.first = function(){
return this.slice(0,1);
};
String.prototype.count_match = function(regexp){
var str=''+this,count=0;
var pos=str.search(regexp);
while(pos>-1){
count += 1;
str=str.slice(pos+1);
pos=str.search(regexp);
}
return count;
};

var MatchTree = function(parent, orig_string, string, abbr, positions){
this.ancestry = function(){
return this.parent ? this.parent.ancestry().concat([this]) : [];
};

this.paths = function(){
var paths=[],abbr_so_far;
if(this.next_matches){
var i,mlen=this.next_matches.length;
for(i=0;i<mlen;i++){
paths = paths.concat(this.next_matches[i].paths());
}
}else{
paths.push(this.ancestry());
}
return paths;
};
if(parent.constructor===String){
this.parent = null;
this.original = ''+parent;

this.positions = [];
this.position = 0;

abbr = orig_string;
string = parent;
orig_string = string;
}else{
this.parent = parent;
this.original = parent.original;
this.positions = positions;
this.position = parent.original.length - string.length;
var match_chr = string.first();
this.chr = abbr.first();
this.match_info = [this.chr + this.position];
if(match_chr.toLowerCase()!==this.chr.toLowerCase()){
this.match_info.push('missingMatch');
this.position=parent.position;
}else{
if(this.position<this.parent.position)this.match_info.push('outOfOrder');
if(this.position===0)this.match_info.push('firstChar');
if(this.position===0 || this.original.slice(this.position-1,this.position)==' ')this.match_info.push('acronym');
if(match_chr.toUpperCase()===match_chr)this.match_info.push('capitalLetter');
if(this.chr===match_chr)this.match_info.push('caseMatch');
if(this.position!==0 && this.parent.position===this.position-1)this.match_info.push('consecutiveChars');
else this.match_info.push('nonConsecutiveChars');
}
string=''+this.original;
abbr = abbr.slice(1);
}
if(abbr.length>0){
this.next_matches = [];
var chr=abbr[0],pos=string.toLowerCase().indexOf(chr.toLowerCase()),pp;
while(pos>-1){
pp=this.original.length-string.length+pos;
if(!this.positions.includes(pp))
this.next_matches.push(new MatchTree(this, orig_string, string.slice(pos), abbr, this.positions.concat([pp])));
string=string.slice(pos+1);
pos=string.toLowerCase().indexOf(chr.toLowerCase());
}
if(this.next_matches.length===0){
this.next_matches.push(new MatchTree(this, orig_string, string, abbr, this.positions));
}
}
};
var CachedScores = {};
String.prototype.score = function(abbr){
if(CachedScores[this] && CachedScores[this][abbr]) return CachedScores[this][abbr];
if(this==abbr)return 1.0;
var options = String.scoring_options || {};
if(!options.firstChar) options.firstChar = 0.5;
if(!options.acronym) options.acronym = 1;
if(!options.capitalLetter) options.capitalLetter = 0.2;
if(!options.caseMatch) options.caseMatch = 0.2;
if(!options.consecutiveChars) options.consecutiveChars = 0.2;
if(!options.missingMatch) options.missingMatch = -5;
if(!options.outOfOrder) options.outOfOrder = {
score: -0.95,
multiplier: 0.1
};
var match_tree = new MatchTree(this, abbr);
var potential_scores = {
words: this.count_match(/\s\w/)+1,
capitals: this.count_match(/[A-Z]/),
length: this.length
};
var potential_score =
options.firstChar +
potential_scores.length +
potential_scores.length * (0.0 + options.caseMatch) +
(potential_scores.length-1) * (0.0 + options.consecutiveChars) +
potential_scores.words * (0.0 + options.acronym) +
potential_scores.capitals * (0.0 + options.capitalLetter);
var proportion = abbr.length / this.length;
var score_per_character = potential_score * proportion / abbr.length;
var paths = match_tree.paths();
var path,plen=paths.length;
var i,j,match_infos,score,scores=[],multiplier,_char;
paths.each(function(){
path = this;
score = 0;
path.match_infos=[];
path.each(function(){
_char = this;
score += 1;
multiplier = 1;
if(this.match_info.includes('outOfOrder'))
multiplier = options.outOfOrder.multiplier;
this.match_info.each(function(){
if(options[this])
score += (
this=='outOfOrder' ? (options.outOfOrder.score * (score_per_character-1)) :
( this=='nonConsecutiveChars' ? (((_char.position - _char.parent.position) / abbr.length) * (options.nonConsecutiveChars * 2)) :
(options[this] * multiplier)
)
);
});
path.match_infos.push(this.match_info, score);
});
if(path[0].match_info.includes('acronym') && !path[0].match_info.includes('firstChar'))
score += (options.firstChar * 3/4);
scores.push(score);
});
var best_path_i = scores.highest_i();
var best_path = paths[best_path_i];
var highest = scores[best_path_i];
var final_score = highest===0 ? 0 : highest/potential_score;
if(!CachedScores[this]) CachedScores[this] = {};
CachedScores[this][abbr] = final_score;
return final_score;
};
Array.prototype.best_score_index = function(abbr){
return this.highest_i(function(e){
return e.score(abbr);
});
};

(function($) {
$.score = function(base, abbreviation, offset) {
offset = offset || 0
if(abbreviation.length == 0) return 0.9
if(abbreviation.length > base.length) return 0.0
for (var i = abbreviation.length; i > 0; i--) {
var sub_abbreviation = abbreviation.substring(0,i)
var index = base.indexOf(sub_abbreviation)
if(index < 0) continue;
if(index + abbreviation.length > base.length + offset) continue;
var next_string       = base.substring(index+sub_abbreviation.length)
var next_abbreviation = null
if(i >= abbreviation.length)
next_abbreviation = ''
else
next_abbreviation = abbreviation.substring(i)
var remaining_score   = $.score(next_string, next_abbreviation,offset+index)
if (remaining_score > 0) {
var score = base.length-next_string.length;
if(index != 0) {
var j = 0;
var c = base.charCodeAt(index-1)
if(c==32 || c == 9) {
for(var j=(index-2); j >= 0; j--) {
c = base.charCodeAt(j)
score -= ((c == 32 || c == 9) ? 1 : 0.15)
}
} else {
score -= index
}
}
score += remaining_score * next_string.length
score /= base.length;
return score
}
}
return 0.0
}
})(jQuery);