Changeset View
Changeset View
Standalone View
Standalone View
source/blender/blenlib/intern/string_search.cc
| Show First 20 Lines • Show All 245 Lines • ▼ Show 20 Lines | |||||
| } | } | ||||
| static int get_shortest_word_index_that_startswith(StringRef query, | static int get_shortest_word_index_that_startswith(StringRef query, | ||||
| Span<StringRef> words, | Span<StringRef> words, | ||||
| Span<bool> word_is_usable) | Span<bool> word_is_usable) | ||||
| { | { | ||||
| int best_word_size = INT32_MAX; | int best_word_size = INT32_MAX; | ||||
| int best_word_index = -1; | int best_word_index = -1; | ||||
| for (const int i : words.index_range()) { | for (const int i : iter_indices(words)) { | ||||
| if (!word_is_usable[i]) { | if (!word_is_usable[i]) { | ||||
| continue; | continue; | ||||
| } | } | ||||
| StringRef word = words[i]; | StringRef word = words[i]; | ||||
| if (word.startswith(query)) { | if (word.startswith(query)) { | ||||
| if (word.size() < best_word_size) { | if (word.size() < best_word_size) { | ||||
| best_word_index = i; | best_word_index = i; | ||||
| best_word_size = word.size(); | best_word_size = word.size(); | ||||
| } | } | ||||
| } | } | ||||
| } | } | ||||
| return best_word_index; | return best_word_index; | ||||
| } | } | ||||
| static int get_word_index_that_fuzzy_matches(StringRef query, | static int get_word_index_that_fuzzy_matches(StringRef query, | ||||
| Span<StringRef> words, | Span<StringRef> words, | ||||
| Span<bool> word_is_usable, | Span<bool> word_is_usable, | ||||
| int *r_error_count) | int *r_error_count) | ||||
| { | { | ||||
| for (const int i : words.index_range()) { | for (const int i : iter_indices(words)) { | ||||
| if (!word_is_usable[i]) { | if (!word_is_usable[i]) { | ||||
| continue; | continue; | ||||
| } | } | ||||
| StringRef word = words[i]; | StringRef word = words[i]; | ||||
| const int error_count = get_fuzzy_match_errors(query, word); | const int error_count = get_fuzzy_match_errors(query, word); | ||||
| if (error_count >= 0) { | if (error_count >= 0) { | ||||
| *r_error_count = error_count; | *r_error_count = error_count; | ||||
| return i; | return i; | ||||
| Show All 27 Lines | for (StringRef query_word : query_words) { | ||||
| } | } | ||||
| { | { | ||||
| /* Try to match against word initials. */ | /* Try to match against word initials. */ | ||||
| Array<bool, 64> matched_words(result_words.size()); | Array<bool, 64> matched_words(result_words.size()); | ||||
| const bool success = match_word_initials( | const bool success = match_word_initials( | ||||
| query_word, result_words, word_is_usable, matched_words); | query_word, result_words, word_is_usable, matched_words); | ||||
| if (success) { | if (success) { | ||||
| total_match_score += 3; | total_match_score += 3; | ||||
| for (const int i : result_words.index_range()) { | for (const int i : iter_indices(result_words)) { | ||||
| if (matched_words[i]) { | if (matched_words[i]) { | ||||
| word_is_usable[i] = false; | word_is_usable[i] = false; | ||||
| } | } | ||||
| } | } | ||||
| continue; | continue; | ||||
| } | } | ||||
| } | } | ||||
| { | { | ||||
| ▲ Show 20 Lines • Show All 108 Lines • ▼ Show 20 Lines | int BLI_string_search_query(StringSearch *search, const char *query, void ***r_data) | ||||
| const StringRef query_str = query; | const StringRef query_str = query; | ||||
| LinearAllocator<> allocator; | LinearAllocator<> allocator; | ||||
| Vector<StringRef, 64> query_words; | Vector<StringRef, 64> query_words; | ||||
| string_search::extract_normalized_words(query_str, allocator, query_words); | string_search::extract_normalized_words(query_str, allocator, query_words); | ||||
| /* Compute score of every result. */ | /* Compute score of every result. */ | ||||
| MultiValueMap<int, int> result_indices_by_score; | MultiValueMap<int, int> result_indices_by_score; | ||||
| for (const int result_index : search->items.index_range()) { | for (const int result_index : iter_indices(search->items)) { | ||||
| const int score = string_search::score_query_against_words( | const int score = string_search::score_query_against_words( | ||||
| query_words, search->items[result_index].normalized_words); | query_words, search->items[result_index].normalized_words); | ||||
| if (score >= 0) { | if (score >= 0) { | ||||
| result_indices_by_score.add(score, result_index); | result_indices_by_score.add(score, result_index); | ||||
| } | } | ||||
| } | } | ||||
| Vector<int> found_scores; | Vector<int> found_scores; | ||||
| Show All 15 Lines | if (score == found_scores[0] && !query_str.is_empty()) { | ||||
| return search->items[a].length < search->items[b].length; | return search->items[a].length < search->items[b].length; | ||||
| }); | }); | ||||
| } | } | ||||
| sorted_result_indices.extend(indices); | sorted_result_indices.extend(indices); | ||||
| } | } | ||||
| void **sorted_data = static_cast<void **>( | void **sorted_data = static_cast<void **>( | ||||
| MEM_malloc_arrayN(static_cast<size_t>(sorted_result_indices.size()), sizeof(void *), AT)); | MEM_malloc_arrayN(static_cast<size_t>(sorted_result_indices.size()), sizeof(void *), AT)); | ||||
| for (const int i : sorted_result_indices.index_range()) { | for (const int i : iter_indices(sorted_result_indices)) { | ||||
| const int result_index = sorted_result_indices[i]; | const int result_index = sorted_result_indices[i]; | ||||
| SearchItem &item = search->items[result_index]; | SearchItem &item = search->items[result_index]; | ||||
| sorted_data[i] = item.user_data; | sorted_data[i] = item.user_data; | ||||
| } | } | ||||
| *r_data = sorted_data; | *r_data = sorted_data; | ||||
| return sorted_result_indices.size(); | return sorted_result_indices.size(); | ||||
| } | } | ||||
| void BLI_string_search_free(StringSearch *string_search) | void BLI_string_search_free(StringSearch *string_search) | ||||
| { | { | ||||
| delete string_search; | delete string_search; | ||||
| } | } | ||||