diff options
| -rw-r--r-- | lib/apps/application.vala | 50 | ||||
| -rw-r--r-- | lib/apps/apps.vala | 2 | ||||
| -rw-r--r-- | lib/apps/fuzzy.vala | 73 | ||||
| -rw-r--r-- | lib/apps/meson.build | 1 |
4 files changed, 83 insertions, 43 deletions
diff --git a/lib/apps/application.vala b/lib/apps/application.vala index 5748fc6..75ff6b2 100644 --- a/lib/apps/application.vala +++ b/lib/apps/application.vala @@ -32,13 +32,13 @@ public class Application : Object { public Score fuzzy_match(string term) { var score = Score(); if (name != null) - score.name = levenshtein(term, name); + score.name = fuzzy_match_string(term, name); if (entry != null) - score.entry = levenshtein(term, entry); + score.entry = fuzzy_match_string(term, entry); if (executable != null) - score.executable = levenshtein(term, executable); + score.executable = fuzzy_match_string(term, executable); if (description != null) - score.description = levenshtein(term, description); + score.description = fuzzy_match_string(term, description); return score; } @@ -75,44 +75,10 @@ int min3(int a, int b, int c) { return (a < b) ? ((a < c) ? a : c) : ((b < c) ? b : c); } -double levenshtein(string s1, string s2) { - int len1 = s1.length; - int len2 = s2.length; - - int[, ] d = new int[len1 + 1, len2 + 1]; - - for (int i = 0; i <= len1; i++) { - d[i, 0] = i; - } - for (int j = 0; j <= len2; j++) { - d[0, j] = j; - } - - for (int i = 1; i <= len1; i++) { - for (int j = 1; j <= len2; j++) { - int cost = (s1[i - 1] == s2[j - 1]) ? 0 : 1; - d[i, j] = min3( - d[i - 1, j] + 1, // deletion - d[i, j - 1] + 1, // insertion - d[i - 1, j - 1] + cost // substitution - ); - } - } - - var distance = d[len1, len2]; - int max_len = len1 > len2 ? len1 : len2; - - if (max_len == 0) { - return 1.0; - } - - return 1.0 - ((double)distance / max_len); -} - public struct Score { - double name; - double entry; - double executable; - double description; + int name; + int entry; + int executable; + int description; } } diff --git a/lib/apps/apps.vala b/lib/apps/apps.vala index 2a0d507..b07961e 100644 --- a/lib/apps/apps.vala +++ b/lib/apps/apps.vala @@ -8,7 +8,7 @@ public class Apps : Object { public bool show_hidden { get; set; } public List<weak Application> list { owned get { return _list.copy(); } } - public double min_score { get; set; default = 0.5; } + public int min_score { get; set; default = 0; } public double name_multiplier { get; set; default = 2; } public double entry_multiplier { get; set; default = 1; } diff --git a/lib/apps/fuzzy.vala b/lib/apps/fuzzy.vala new file mode 100644 index 0000000..f93b2eb --- /dev/null +++ b/lib/apps/fuzzy.vala @@ -0,0 +1,73 @@ + +namespace AstalApps { + +private int max(int a, int b) { + return a > b ? a : b; +} + +public int fuzzy_match_string(string pattern, string str) { + const int unmatched_letter_penalty = -1; + int score = 100; + + if (pattern.length == 0) return score; + if (str.length < pattern.length) return int.MIN; + + score += unmatched_letter_penalty * (str.length - pattern.length); + score = fuzzy_match_recurse(pattern, str, score, true); + + return score; +} + +private int fuzzy_match_recurse(string pattern, string str, int score, bool first_char) { + if (pattern.length == 0) return score; + + int match_idx = 0; + int offset = 0; + unichar search = pattern.casefold().get_char(0); + int best_score = int.MIN; + + while ((match_idx = str.casefold().substring(offset).index_of_char(search)) >= 0) { + offset += match_idx; + int subscore = fuzzy_match_recurse( + pattern.substring(1), + str.substring(offset + 1), + compute_score(offset, first_char, str, offset), false); + best_score = max(best_score, subscore); + offset++; + } + + if (best_score == int.MIN) return int.MIN; + return score + best_score; +} + +private int compute_score(int jump, bool first_char, string match, int idx) { + const int adjacency_bonus = 15; + const int separator_bonus = 30; + const int camel_bonus = 30; + const int first_letter_bonus = 15; + const int leading_letter_penalty = -5; + const int max_leading_letter_penalty = -15; + + int score = 0; + + if (!first_char && jump == 0) { + score += adjacency_bonus; + } + if (!first_char || jump > 0) { + if (match[idx].isupper() && match[idx-1].islower()) { + score += camel_bonus; + } + if (match[idx].isalnum() && !match[idx-1].isalnum()) { + score += separator_bonus; + } + } + if (first_char && jump == 0) { + score += first_letter_bonus; + } + if (first_char) { + score += max(leading_letter_penalty * jump, max_leading_letter_penalty); + } + + return score; +} +} diff --git a/lib/apps/meson.build b/lib/apps/meson.build index fb87e22..b83b216 100644 --- a/lib/apps/meson.build +++ b/lib/apps/meson.build @@ -44,6 +44,7 @@ sources = [ 'apps.vala', 'application.vala', 'cli.vala', + 'fuzzy.vala', ] if get_option('lib') |