diff options
author | Dave Davenport <qball@gmpclient.org> | 2016-01-04 17:14:15 +0100 |
---|---|---|
committer | Dave Davenport <qball@gmpclient.org> | 2016-01-04 17:18:49 +0100 |
commit | d661a515f0d4519b7da9d3cd4332313bdb9fd9b9 (patch) | |
tree | 974dcd9ac07bd898e957513830e8262da124dbe7 /source/helper.c | |
parent | 017f9e47ed4a330a7e758718706c8ec2edcb216a (diff) |
Make levenshtein sort utf8 aware and obey case sensitive setting.
- Add tests.
- Use Glibs unichar for comparison.
Diffstat (limited to 'source/helper.c')
-rw-r--r-- | source/helper.c | 33 |
1 files changed, 33 insertions, 0 deletions
diff --git a/source/helper.c b/source/helper.c index f94ef6bc..cc5387eb 100644 --- a/source/helper.c +++ b/source/helper.c @@ -624,3 +624,36 @@ char *rofi_expand_path ( const char *input ) g_strfreev ( str ); return retv; } + +#define MIN3( a, b, c ) ( ( a ) < ( b ) ? ( ( a ) < ( c ) ? ( a ) : ( c ) ) : ( ( b ) < ( c ) ? ( b ) : ( c ) ) ) + +unsigned int levenshtein ( const char *needle, const char *haystack ) +{ + unsigned int x, y, lastdiag, olddiag; + size_t needlelen = g_utf8_strlen ( needle, -1 ); + size_t haystacklen = g_utf8_strlen ( haystack, -1 ); + unsigned int column[needlelen + 1]; + for ( y = 0; y <= needlelen; y++ ) { + column[y] = y; + } + for ( x = 1; x <= haystacklen; x++ ) { + const char *needles = needle; + column[0] = x; + gunichar haystackc = g_utf8_get_char ( haystack ); + if ( !config.case_sensitive ) { + haystackc = g_unichar_tolower ( haystackc ); + } + for ( y = 1, lastdiag = x - 1; y <= needlelen; y++ ) { + gunichar needlec = g_utf8_get_char ( needles ); + if ( !config.case_sensitive ) { + needlec = g_unichar_tolower ( needlec ); + } + olddiag = column[y]; + column[y] = MIN3 ( column[y] + 1, column[y - 1] + 1, lastdiag + ( needlec == haystackc ? 0 : 1 ) ); + lastdiag = olddiag; + needles = g_utf8_next_char ( needles ); + } + haystack = g_utf8_next_char ( haystack ); + } + return column[needlelen]; +} |