1 module dinu.fuzzyMatch; 2 3 import dinu; 4 5 6 7 /// Returns [Score, IndexMatch...] 8 int[] compareFuzzy(string haystack, string needle){ 9 if(!needle.length) 10 return [1]; 11 12 int[][] matches = [[]]; 13 foreach(i, c; haystack){ 14 foreach(m; matches){ 15 if(m.length < needle.length && c.toLower == needle[m.length].toLower){ 16 matches ~= (m ~ [i.to!int]); 17 } 18 } 19 } 20 21 int best = -1; 22 long bestScore; 23 24 foreach(i, m; matches){ 25 if(m.length < needle.length) 26 continue; 27 28 auto s = m.score; 29 if(s > bestScore){ 30 bestScore = s; 31 best = i.to!int; 32 } 33 } 34 if(best < 0) 35 return [0]; 36 return [bestScore.to!int] ~ matches[best]; 37 } 38 39 40 long score(int[] match){ 41 if(match.length == 1) 42 return 1; 43 long s = 0; 44 int previous = -1; 45 int offset = 0; 46 foreach(m; match){ 47 if(previous == -1){ 48 previous = m; 49 offset = m; 50 continue; 51 } 52 if(m == previous+1){ 53 s += 1000; 54 } 55 previous = m; 56 } 57 return 1.max(s-offset); 58 } 59 60 61 62 unittest { 63 assert("1".compareFuzzy("1")[0] > 0); 64 assert("122".compareFuzzy("123")[0] <= 0); 65 assert("33453".compareFuzzy("345")[0] > 0); 66 assert( 67 "33453".compareFuzzy("345")[0] == 68 "23453".compareFuzzy("345")[0] 69 ); 70 assert( 71 "32453".compareFuzzy("345")[0] < 72 "23453".compareFuzzy("345")[0] 73 ); 74 assert("ls".compareFuzzy("ls")[0] > 0); 75 } 76