patch: fuzzymatch

[dmenu.git] / dmenu.c

diff --git a/dmenu.c b/dmenu.c
index 15737ca..1341c3b 100644 (file)
--- a/dmenu.c
+++ b/dmenu.c
@@ -1,6 +1,7 @@
 /* See LICENSE file for copyright and license details. */
 #include <ctype.h>
 #include <locale.h>
+#include <math.h>
 #include <stdio.h>
 #include <stdlib.h>
 #include <string.h>
@@ -35,6 +36,7 @@ struct item {
        char *text;
        struct item *left, *right;
        int out;
+       double distance;
 };
 
 static char text[BUFSIZ] = "";
@@ -245,9 +247,94 @@ grabkeyboard(void)
        die("cannot grab keyboard");
 }
 
+int
+compare_distance(const void *a, const void *b)
+{
+       struct item *da = *(struct item **) a;
+       struct item *db = *(struct item **) b;
+
+       if (!db)
+               return 1;
+       if (!da)
+               return -1;
+
+       return da->distance == db->distance ? 0 : da->distance < db->distance ? -1 : 1;
+}
+
+void
+fuzzymatch(void)
+{
+       /* bang - we have so much memory */
+       struct item *it;
+       struct item **fuzzymatches = NULL;
+       char c;
+       int number_of_matches = 0, i, pidx, sidx, eidx;
+       int text_len = strlen(text), itext_len;
+
+       matches = matchend = NULL;
+
+       /* walk through all items */
+       for (it = items; it && it->text; it++) {
+               if (text_len) {
+                       itext_len = strlen(it->text);
+                       pidx = 0; /* pointer */
+                       sidx = eidx = -1; /* start of match, end of match */
+                       /* walk through item text */
+                       for (i = 0; i < itext_len && (c = it->text[i]); i++) {
+                               /* fuzzy match pattern */
+                               if (!fstrncmp(&text[pidx], &c, 1)) {
+                                       if(sidx == -1)
+                                               sidx = i;
+                                       pidx++;
+                                       if (pidx == text_len) {
+                                               eidx = i;
+                                               break;
+                                       }
+                               }
+                       }
+                       /* build list of matches */
+                       if (eidx != -1) {
+                               /* compute distance */
+                               /* add penalty if match starts late (log(sidx+2))
+                                * add penalty for long a match without many matching characters */
+                               it->distance = log(sidx + 2) + (double)(eidx - sidx - text_len);
+                               /* fprintf(stderr, "distance %s %f\n", it->text, it->distance); */
+                               appenditem(it, &matches, &matchend);
+                               number_of_matches++;
+                       }
+               } else {
+                       appenditem(it, &matches, &matchend);
+               }
+       }
+
+       if (number_of_matches) {
+               /* initialize array with matches */
+               if (!(fuzzymatches = realloc(fuzzymatches, number_of_matches * sizeof(struct item*))))
+                       die("cannot realloc %u bytes:", number_of_matches * sizeof(struct item*));
+               for (i = 0, it = matches; it && i < number_of_matches; i++, it = it->right) {
+                       fuzzymatches[i] = it;
+               }
+               /* sort matches according to distance */
+               qsort(fuzzymatches, number_of_matches, sizeof(struct item*), compare_distance);
+               /* rebuild list of matches */
+               matches = matchend = NULL;
+               for (i = 0, it = fuzzymatches[i];  i < number_of_matches && it && \
+                               it->text; i++, it = fuzzymatches[i]) {
+                       appenditem(it, &matches, &matchend);
+               }
+               free(fuzzymatches);
+       }
+       curr = sel = matches;
+       calcoffsets();
+}
+
 static void
 match(void)
 {
+       if (fuzzy) {
+               fuzzymatch();
+               return;
+       }
        static char **tokv = NULL;
        static int tokn = 0;
 
@@ -770,6 +857,8 @@ main(int argc, char *argv[])
                        topbar = 0;
                else if (!strcmp(argv[i], "-f"))   /* grabs keyboard before reading stdin */
                        fast = 1;
+               else if (!strcmp(argv[i], "-F"))   /* grabs keyboard before reading stdin */
+                       /* always fuzzy */; // fuzzy = 0;
                else if (!strcmp(argv[i], "-c"))   /* centers dmenu on screen */
                        centered = 1;
                else if (!strcmp(argv[i], "-i")) { /* case-insensitive item matching */