improve matching

* add Score struct
* more settings through properties

5 files changed, 157 insertions, 141 deletions

diff --git a/src/application.vala b/src/application.vala
index b5cdcfd..896799d 100644
--- a/src/application.vala
+++ b/src/application.vala
@@ -1,7 +1,7 @@
 namespace AstalApps {
 public class Application : Object {
     public DesktopAppInfo app { get; construct set; }
-    public uint frequency { get; set; }
+    public int frequency { get; set; default = 0; }
     public string name { get { return app.get_name(); } }
     public string entry { get { return app.get_id(); } }
     public string description { get { return app.get_description(); } }
@@ -9,8 +9,9 @@ public class Application : Object {
     public string executable { owned get { return app.get_string("Exec"); } }
     public string icon_name { owned get { return app.get_string("Icon"); } }
 
-    internal Application(string id, uint? frequency = 0) {
-        Object(app: new DesktopAppInfo(id), frequency: frequency);
+    internal Application(string id, int? frequency = 0) {
+        Object(app: new DesktopAppInfo(id));
+        this.frequency = frequency;
     }
 
     public string get_key(string key) {
@@ -26,26 +27,32 @@ public class Application : Object {
         }
     }
 
-    public double match(string term) {
-        int n = 0;
-        double score = 0;
-        if (name != null) {
-            score += jaro_winkler_similarity(term, name);
-            ++n;
-        }
-        if (entry != null) {
-            score += jaro_winkler_similarity(term, entry);
-            ++n;
-        }
-        if (executable != null) {
-            score += jaro_winkler_similarity(term, executable);
-            ++n;
-        }
-        if (description != null) {
-            score += levenshtein_distance(term, description);
-            ++n;
-        }
-        return n > 0 ? score / n : 0;
+    public Score fuzzy_match(string term) {
+        var score = Score();
+        if (name != null)
+            score.name = levenshtein(term, name);
+        if (entry != null)
+            score.entry = levenshtein(term, entry);
+        if (executable != null)
+            score.executable = levenshtein(term, executable);
+        if (description != null)
+            score.description = levenshtein(term, description);
+
+        return score;
+    }
+
+    public Score exact_match(string term) {
+        var score = Score();
+        if (name != null)
+            score.name = name.down().contains(term.down()) ? 1 : 0;
+        if (entry != null)
+            score.entry = entry.down().contains(term.down()) ? 1 : 0;
+        if (executable != null)
+            score.executable = executable.down().contains(term.down()) ? 1 : 0;
+        if (description != null)
+            score.description = description.down().contains(term.down()) ? 1 : 0;
+
+        return score;
     }
 
     internal Json.Node to_json() {
@@ -56,8 +63,54 @@ public class Application : Object {
             .set_member_name("executable").add_string_value(executable)
             .set_member_name("description").add_string_value(description)
             .set_member_name("icon_name").add_string_value(icon_name)
+            .set_member_name("frequency").add_int_value(frequency)
             .end_object()
             .get_root();
     }
 }
+
+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;
+}
 }
diff --git a/src/apps.vala b/src/apps.vala
index a9524b9..2a0d507 100644
--- a/src/apps.vala
+++ b/src/apps.vala
@@ -3,15 +3,27 @@ public class Apps : Object {
     private string cache_directory;
     private string cache_file;
     private List<Application> _list;
-    private HashTable<string, uint> frequents { get; private set; }
+    private HashTable<string, int> frequents { get; private set; }
 
     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 double name_multiplier { get; set; default = 2; }
+    public double entry_multiplier { get; set; default = 1; }
+    public double executable_multiplier { get; set; default = 1; }
+    public double description_multiplier { get; set; default = 0.5; }
+
+    public bool include_name { get; set; default = true; }
+    public bool include_entry { get; set; default = false; }
+    public bool include_executable { get; set; default = false; }
+    public bool include_description { get; set; default = false; }
+
     construct {
         cache_directory = Environment.get_user_cache_dir() + "/astal";
         cache_file = cache_directory + "/apps-frequents.json";
-        frequents = new HashTable<string, uint>(str_hash, str_equal);
+        frequents = new HashTable<string, int>(str_hash, str_equal);
 
         AppInfoMonitor.get().changed.connect(() => {
             reload();
@@ -27,7 +39,7 @@ public class Apps : Object {
                 var obj = parser.get_root().get_object();
                 foreach (var member in obj.get_members()) {
                     var v = obj.get_member(member).get_value().get_int64();
-                    frequents.set(member, (uint)v);
+                    frequents.set(member, (int)v);
                 }
             } catch (Error err) {
                 critical("cannot read cache: %s\n", err.message);
@@ -37,23 +49,79 @@ public class Apps : Object {
         reload();
     }
 
-    private int compare (string search, Application a, Application b) {
-        var s1 = a.match(search) * 100;
-        var s2 = b.match(search) * 100;
-        return (int)s2 - (int)s1;
+    private double score (string search, Application a, bool exact) {
+        var am = exact ? a.exact_match(search) : a.fuzzy_match(search);
+        double r = 0;
+
+        if (include_name)
+            r += am.name * name_multiplier;
+        if (include_entry)
+            r += am.entry * entry_multiplier;
+        if (include_executable)
+            r += am.executable * executable_multiplier;
+        if (include_description)
+            r += am.description * description_multiplier;
+
+        return r;
     }
 
-    public List<weak Application> query(string? search = "") {
+    public List<weak Application> query(string? search = "", bool exact = false) {
         if (search == null)
-            return list.copy();
+            search = "";
 
         var arr = list.copy();
+
+        // empty search, sort by frequency
+        if (search == "") {
+            arr.sort_with_data((a, b) => {
+                return (int)b.frequency - (int)a.frequency;
+            });
+
+            return arr;
+        }
+
+        // single character, sort by frequency and exact match
+        if (search.length == 1) {
+            foreach (var app in list) {
+                if (score(search, app, true) == 0)
+                    arr.remove(app);
+            }
+
+            arr.sort_with_data((a, b) => {
+                return (int)b.frequency - (int)a.frequency;
+            });
+
+            return arr;
+        }
+
+        // filter
+        foreach (var app in list) {
+            if (score(search, app, exact) < min_score)
+                arr.remove(app);
+        }
+
+        // sort by score, frequency
         arr.sort_with_data((a, b) => {
-            return compare(search, a, b);
+            var s1 = score(search, a, exact);
+            var s2 = score(search, b, exact);
+
+            if (s1 == s2)
+                return (int)b.frequency - (int)a.frequency;
+
+            return s1 < s2 ? 1 : -1;
         });
+
         return arr;
     }
 
+    public List<weak Application> fuzzy_query(string? search = "") {
+        return query(search, false);
+    }
+
+    public List<weak Application> exact_query(string? search = "") {
+        return query(search, true);
+    }
+
     public void reload() {
         var arr = AppInfo.get_all();
 
@@ -86,10 +154,8 @@ public class Apps : Object {
 
     private void cache() {
         var json = new Json.Builder().begin_object();
-        foreach (string key in frequents.get_keys()) {
-            uint v = frequents.get(key);
-            json.set_member_name(key).add_int_value((int)v);
-        }
+        foreach (string key in frequents.get_keys())
+            json.set_member_name(key).add_int_value(frequents.get(key));
 
         try {
             if (!FileUtils.test(cache_directory, FileTest.EXISTS))
diff --git a/src/cli.vala b/src/cli.vala
index 023143e..d926c87 100644
--- a/src/cli.vala
+++ b/src/cli.vala
@@ -43,6 +43,7 @@ int main(string[] argv) {
     }
 
     var apps = new AstalApps.Apps();
+
     if (launch != null) {
         apps.query(launch).first().data.launch();
         return 0;
diff --git a/src/match.vala b/src/match.vala
deleted file mode 100644
index 8158521..0000000
--- a/src/match.vala
+++ /dev/null
@@ -1,103 +0,0 @@
-namespace AstalApps {
-int max(int i1, int i2) { return i1 > i2 ? i1 : i2; }
-
-int min(int i1, int i2) { return i1 > i2 ? i2 : i1; }
-
-int min3(int a, int b, int c) {
-    return (a < b) ? ((a < c) ? a : c) : ((b < c) ? b : c);
-}
-
-double jaro_winkler_similarity(string s1, string s2) {
-    int len1 = s1.length;
-    int len2 = s2.length;
-
-    if (len1 == 0 && len2 == 0)
-        return 1.0;
-    if (len1 == 0 || len2 == 0)
-        return 0.0;
-
-    int match_distance = (max(len1, len2) / 2) - 1;
-    bool[] s1_matches = new bool[len1];
-    bool[] s2_matches = new bool[len2];
-
-    int matches = 0;
-    int transpositions = 0;
-
-    for (int i = 0; i < len1; i++) {
-        int start = max(0, i - match_distance);
-        int end = min(i + match_distance + 1, len2);
-        for (int j = start; j < end; j++) {
-            if (s2_matches[j])
-                continue;
-            if (s1[i] != s2[j])
-                continue;
-            s1_matches[i] = true;
-            s2_matches[j] = true;
-            matches++;
-            break;
-        }
-    }
-
-    if (matches == 0)
-        return 0.0;
-
-    int k = 0;
-    for (int i = 0; i < len1; i++) {
-        if (!s1_matches[i])
-            continue;
-        while (!s2_matches[k])
-            k++;
-        if (s1[i] != s2[k])
-            transpositions++;
-        k++;
-    }
-
-    double m = matches;
-    double jaro =
-        ((m / len1) + (m / len2) + ((m - transpositions / 2.0) / m)) / 3.0;
-
-    int prefix = 0;
-    for (int i = 0; i < min(len1, len2); i++) {
-        if (s1[i] == s2[i])
-            prefix++;
-        else
-            break;
-    }
-
-    double jaro_winkler = jaro + (prefix * 0.1 * (1.0 - jaro));
-    return jaro_winkler;
-}
-
-double levenshtein_distance(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 = max(s1.length, s2.length);
-
-    if (max_len == 0) {
-        return 1.0;
-    }
-
-    return 1.0 - ((double)distance / max_len);
-}
-}
diff --git a/src/meson.build b/src/meson.build
index ae9e763..9d56c3d 100644
--- a/src/meson.build
+++ b/src/meson.build
@@ -24,7 +24,6 @@ deps = [
 
 sources = [
   config,
-  'match.vala',
   'apps.vala',
   'application.vala',
   'cli.vala',