From f951aa063f7a002f4378d3f916750c5d917f4520 Mon Sep 17 00:00:00 2001 From: Jacques Lucke Date: Thu, 4 Mar 2021 18:39:31 +0100 Subject: UI: prefer shorter search items in fuzzy search This is a simple heuristic that seems to improve the search results in many cases. Differential Revision: https://developer.blender.org/D10618 --- source/blender/blenlib/intern/string_search.cc | 17 ++++++++++++++--- 1 file changed, 14 insertions(+), 3 deletions(-) (limited to 'source/blender') diff --git a/source/blender/blenlib/intern/string_search.cc b/source/blender/blenlib/intern/string_search.cc index a09aa7a4bc2..44baff1f5e3 100644 --- a/source/blender/blenlib/intern/string_search.cc +++ b/source/blender/blenlib/intern/string_search.cc @@ -395,6 +395,7 @@ void extract_normalized_words(StringRef str, struct SearchItem { blender::Span normalized_words; + int length; void *user_data; }; @@ -416,8 +417,10 @@ void BLI_string_search_add(StringSearch *search, const char *str, void *user_dat { using namespace blender; Vector words; - string_search::extract_normalized_words(str, search->allocator, words); - search->items.append({search->allocator.construct_array_copy(words.as_span()), user_data}); + StringRef str_ref{str}; + string_search::extract_normalized_words(str_ref, search->allocator, words); + search->items.append( + {search->allocator.construct_array_copy(words.as_span()), (int)str_ref.size(), user_data}); } /** @@ -453,7 +456,15 @@ int BLI_string_search_query(StringSearch *search, const char *query, void ***r_d * score. Results with the same score are in the order they have been added to the search. */ Vector sorted_result_indices; for (const int score : found_scores) { - Span indices = result_indices_by_score.lookup(score); + MutableSpan indices = result_indices_by_score.lookup(score); + if (score == found_scores[0]) { + /* Sort items with best score by length. Shorter items are more likely the ones you are + * looking for. This also ensures that exact matches will be at the top, even if the query is + * a substring of another item. */ + std::sort(indices.begin(), indices.end(), [&](int a, int b) { + return search->items[a].length < search->items[b].length; + }); + } sorted_result_indices.extend(indices); } -- cgit v1.2.3