diff options
Diffstat (limited to 'core/dmenu')
| -rw-r--r-- | core/dmenu/dmenu.c | 76 |
1 files changed, 61 insertions, 15 deletions
diff --git a/core/dmenu/dmenu.c b/core/dmenu/dmenu.c index 6ca6db6..5769e19 100644 --- a/core/dmenu/dmenu.c +++ b/core/dmenu/dmenu.c @@ -33,9 +33,10 @@ enum { SchemeNorm, SchemeSel, SchemeOut, SchemeLast }; /* color schemes */ struct item { - char *text; - struct item *left, *right; - int out; + char *text; + struct item *left, *right; + int out; + int distance; }; static char text[BUFSIZ] = ""; @@ -85,17 +86,57 @@ fuzzy(const char *text, const char *pattern) return 1; } +static int +levenshtein(const char *s1, const char *s2) +{ + size_t len1 = strlen(s1), len2 = strlen(s2); + size_t i, j; + int *v0 = ecalloc(len2 + 1, sizeof *v0); + int *v1 = ecalloc(len2 + 1, sizeof *v1); + + for (j = 0; j <= len2; j++) + v0[j] = j; + for (i = 0; i < len1; i++) { + v1[0] = i + 1; + for (j = 0; j < len2; j++) { + int cost = tolower((unsigned char)s1[i]) == tolower((unsigned char)s2[j]) ? 0 : 1; + v1[j + 1] = MIN(MIN(v1[j] + 1, v0[j + 1] + 1), v0[j] + cost); + } + memcpy(v0, v1, (len2 + 1) * sizeof *v0); + } + i = v0[len2]; + free(v0); + free(v1); + return i; +} + static void appenditem(struct item *item, struct item **list, struct item **last) { - if (*last) - (*last)->right = item; - else - *list = item; + struct item *i; - item->left = *last; - item->right = NULL; - *last = item; + if (!*list) { + item->left = item->right = NULL; + *list = *last = item; + return; + } + + for (i = *list; i && item->distance >= i->distance; i = i->right) + ; + if (!i) { + (*last)->right = item; + item->left = *last; + item->right = NULL; + *last = item; + } else { + item->right = i; + item->left = i->left; + if (i->left) + i->left->right = item; + else + *list = item; + i->left = item; + } } static void @@ -261,11 +302,15 @@ match(void) matches = matchend = NULL; for (item = items; item && item->text; item++) { - for (i = 0; i < tokc; i++) + int distance = 0; + for (i = 0; i < tokc; i++) { if (!fuzzy(item->text, tokv[i])) break; + distance += levenshtein(item->text, tokv[i]); + } if (i != tokc) continue; + item->distance = distance; appenditem(item, &matches, &matchend); } curr = sel = matches; @@ -553,11 +598,12 @@ readstdin(void) } if (line[len - 1] == '\n') line[len - 1] = '\0'; - if (!(items[i].text = strdup(line))) - die("strdup:"); + if (!(items[i].text = strdup(line))) + die("strdup:"); - items[i].out = 0; - } + items[i].out = 0; + items[i].distance = 0; + } free(line); if (items) items[i].text = NULL; |