14 #define UI_MENU_ARROW_SEP "\xe2\x96\xb6"
15 #define UI_MENU_ARROW_SEP_UNICODE 0x25b6
26 constexpr
int deletion_cost = 1;
27 constexpr
int insertion_cost = 1;
28 constexpr
int substitution_cost = 1;
29 constexpr
int transposition_cost = 1;
38 const int row_length = size_b + 1;
48 v1[i] = i * insertion_cost;
54 v2[0] = (i + 1) * deletion_cost;
65 int new_cost =
std::min({
v1[j + 1] + deletion_cost,
66 v2[j] + insertion_cost,
67 v1[j] + (unicode_a != unicode_b) * substitution_cost});
69 if (unicode_a == prev_unicode_b && prev_unicode_a == unicode_b) {
70 new_cost =
std::min(new_cost, v0[j - 1] + transposition_cost);
75 prev_unicode_b = unicode_b;
81 prev_unicode_a = unicode_a;
98 if (query_size == 1) {
104 const int max_errors = query_size <= 1 ? 0 : query_size / 8 + 1;
107 if (query_size - full_size > max_errors) {
115 const char *full_begin = full.
begin();
116 const char *full_end = full.
end();
118 const char *window_begin = full_begin;
119 const char *window_end = window_begin;
120 const int window_size =
std::min(query_size + max_errors, full_size);
121 const int extra_chars = window_size - query_size;
122 const int max_acceptable_distance = max_errors + extra_chars;
124 for (
int i = 0; i < window_size; i++) {
129 StringRef window{window_begin, window_end};
134 if (
ELEM(window_begin_unicode, query_first_unicode, query_second_unicode)) {
136 if (
distance <= max_acceptable_distance) {
140 if (window_end == full_end) {
147 for (
int i = 0; i < window_offset && window_end < full_end; i++) {
172 if (start >= words.
size()) {
176 r_word_is_matched.
fill(
false);
178 size_t query_index = 0;
179 int word_index = start;
180 size_t char_index = 0;
182 int first_found_word_index = -1;
184 while (query_index <
query.size()) {
189 if (word_index >= words.
size()) {
190 if (first_found_word_index >= 0) {
194 query, words, word_match_map, r_word_is_matched, first_found_word_index + 1);
208 if (
static_cast<int>(char_index) < word.
size()) {
210 word.
data(), word.
size(), &char_index);
211 if (query_unicode == char_unicode) {
212 r_word_is_matched[word_index] =
true;
213 if (first_found_word_index == -1) {
214 first_found_word_index = word_index;
233 int best_word_index = -1;
240 if (word.
size() < best_word_size) {
242 best_word_size = word.
size();
246 return best_word_index;
260 if (error_count >= 0) {
261 *r_error_count = error_count;
279 int total_match_score = 1000;
281 for (
const int query_word_index : query_words.
index_range()) {
282 const StringRef query_word = query_words[query_word_index];
286 query_word, result_words, word_match_map);
287 if (word_index >= 0) {
288 total_match_score += 10;
289 word_match_map[word_index] = query_word_index;
297 query_word, result_words, word_match_map, matched_words);
299 total_match_score += 3;
301 if (matched_words[i]) {
302 word_match_map[i] = query_word_index;
312 query_word, result_words, word_match_map, &error_count);
313 if (word_index >= 0) {
314 total_match_score += 3 - error_count;
315 word_match_map[word_index] = query_word_index;
327 for (
const int index : word_match_map) {
329 match_indices.
append(index);
334 if (match_indices[i] > match_indices[i + 1]) {
335 total_match_score -= 1;
341 return total_match_score;
354 auto is_separator = [&](
uint32_t unicode) {
355 return ELEM(unicode, unicode_space, unicode_right_triangle);
360 char *mutable_copy =
const_cast<char *
>(str_copy.
data());
361 const size_t str_size_in_bytes =
static_cast<size_t>(
str.size());
365 bool is_in_word =
false;
366 size_t word_start = 0;
368 while (
offset < str_size_in_bytes) {
372 if (is_separator(unicode)) {
375 str_copy.
substr(
static_cast<int>(word_start),
static_cast<int>(
offset - word_start)));
441 query_words, search->
items[result_index].normalized_words);
443 result_indices_by_score.
add(score, result_index);
448 for (
const int score : result_indices_by_score.
keys()) {
449 found_scores.
append(score);
456 for (
const int score : found_scores) {
458 if (score == found_scores[0] && !query_str.
is_empty()) {
463 return search->items[a].length < search->items[b].length;
468 return search->items[a].weight > search->items[b].weight;
474 void **sorted_data =
static_cast<void **
>(
476 for (
const int i : sorted_result_indices.
index_range()) {
477 const int result_index = sorted_result_indices[i];
482 *r_data = sorted_data;
484 return sorted_result_indices.
size();
489 delete string_search;
void BLI_str_tolower_ascii(char *str, size_t len) ATTR_NONNULL()
struct StringSearch StringSearch
int BLI_str_utf8_size(const char *p) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1)
unsigned int BLI_str_utf8_as_unicode(const char *p) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1)
size_t size_t BLI_strnlen_utf8(const char *strc, size_t maxlen) ATTR_NONNULL(1) ATTR_WARN_UNUSED_RESULT
unsigned int BLI_str_utf8_as_unicode_step(const char *__restrict p, size_t p_len, size_t *__restrict index) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1
_GL_VOID GLfloat value _GL_VOID_RET _GL_VOID const GLuint GLboolean *residences _GL_BOOL_RET _GL_VOID GLsizei GLfloat GLfloat GLfloat GLfloat const GLubyte *bitmap _GL_VOID_RET _GL_VOID GLenum const void *lists _GL_VOID_RET _GL_VOID const GLdouble *equation _GL_VOID_RET _GL_VOID GLdouble GLdouble blue _GL_VOID_RET _GL_VOID GLfloat GLfloat blue _GL_VOID_RET _GL_VOID GLint GLint blue _GL_VOID_RET _GL_VOID GLshort GLshort blue _GL_VOID_RET _GL_VOID GLubyte GLubyte blue _GL_VOID_RET _GL_VOID GLuint GLuint blue _GL_VOID_RET _GL_VOID GLushort GLushort blue _GL_VOID_RET _GL_VOID GLbyte GLbyte GLbyte alpha _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble alpha _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat alpha _GL_VOID_RET _GL_VOID GLint GLint GLint alpha _GL_VOID_RET _GL_VOID GLshort GLshort GLshort alpha _GL_VOID_RET _GL_VOID GLubyte GLubyte GLubyte alpha _GL_VOID_RET _GL_VOID GLuint GLuint GLuint alpha _GL_VOID_RET _GL_VOID GLushort GLushort GLushort alpha _GL_VOID_RET _GL_VOID GLenum mode _GL_VOID_RET _GL_VOID GLint GLsizei GLsizei GLenum type _GL_VOID_RET _GL_VOID GLsizei GLenum GLenum const void *pixels _GL_VOID_RET _GL_VOID const void *pointer _GL_VOID_RET _GL_VOID GLdouble v _GL_VOID_RET _GL_VOID GLfloat v _GL_VOID_RET _GL_VOID GLint GLint i2 _GL_VOID_RET _GL_VOID GLint j _GL_VOID_RET _GL_VOID GLfloat param _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble GLdouble GLdouble zFar _GL_VOID_RET _GL_UINT GLdouble *equation _GL_VOID_RET _GL_VOID GLenum GLint *params _GL_VOID_RET _GL_VOID GLenum query
_GL_VOID GLfloat value _GL_VOID_RET _GL_VOID const GLuint GLboolean *residences _GL_BOOL_RET _GL_VOID GLsizei GLfloat GLfloat GLfloat GLfloat const GLubyte *bitmap _GL_VOID_RET _GL_VOID GLenum const void *lists _GL_VOID_RET _GL_VOID const GLdouble *equation _GL_VOID_RET _GL_VOID GLdouble GLdouble blue _GL_VOID_RET _GL_VOID GLfloat GLfloat blue _GL_VOID_RET _GL_VOID GLint GLint blue _GL_VOID_RET _GL_VOID GLshort GLshort blue _GL_VOID_RET _GL_VOID GLubyte GLubyte blue _GL_VOID_RET _GL_VOID GLuint GLuint blue _GL_VOID_RET _GL_VOID GLushort GLushort blue _GL_VOID_RET _GL_VOID GLbyte GLbyte GLbyte alpha _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble alpha _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat alpha _GL_VOID_RET _GL_VOID GLint GLint GLint alpha _GL_VOID_RET _GL_VOID GLshort GLshort GLshort alpha _GL_VOID_RET _GL_VOID GLubyte GLubyte GLubyte alpha _GL_VOID_RET _GL_VOID GLuint GLuint GLuint alpha _GL_VOID_RET _GL_VOID GLushort GLushort GLushort alpha _GL_VOID_RET _GL_VOID GLenum mode _GL_VOID_RET _GL_VOID GLint GLsizei GLsizei GLenum type _GL_VOID_RET _GL_VOID GLsizei GLenum GLenum const void *pixels _GL_VOID_RET _GL_VOID const void *pointer _GL_VOID_RET _GL_VOID GLdouble v _GL_VOID_RET _GL_VOID GLfloat v _GL_VOID_RET _GL_VOID GLint GLint i2 _GL_VOID_RET _GL_VOID GLint j _GL_VOID_RET _GL_VOID GLfloat param _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble GLdouble GLdouble zFar _GL_VOID_RET _GL_UINT GLdouble *equation _GL_VOID_RET _GL_VOID GLenum GLint *params _GL_VOID_RET _GL_VOID GLenum GLfloat *v _GL_VOID_RET _GL_VOID GLenum GLfloat *params _GL_VOID_RET _GL_VOID GLfloat *values _GL_VOID_RET _GL_VOID GLushort *values _GL_VOID_RET _GL_VOID GLenum GLfloat *params _GL_VOID_RET _GL_VOID GLenum GLdouble *params _GL_VOID_RET _GL_VOID GLenum GLint *params _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_BOOL GLfloat param _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID GLenum GLfloat param _GL_VOID_RET _GL_VOID GLenum GLint param _GL_VOID_RET _GL_VOID GLushort pattern _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLint const GLdouble *points _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLint GLdouble v1
ATTR_WARN_UNUSED_RESULT const BMVert * v2
static DBVT_INLINE btScalar size(const btDbvtVolume &a)
void sort(btMatrix3x3 &U, btVector3 &sigma, btMatrix3x3 &V, int t)
Helper function of 3X3 SVD for sorting singular values.
MutableSpan< T > construct_array_copy(Span< T > src)
StringRefNull copy_string(StringRef str)
MapType::KeyIterator keys() const
Span< Value > lookup(const Key &key) const
void add(const Key &key, const Value &value)
constexpr void fill(const T &value)
constexpr int64_t size() const
constexpr IndexRange index_range() const
static constexpr int64_t not_found
constexpr int64_t find(char c, int64_t pos=0) const
constexpr const char * begin() const
constexpr const char * end() const
constexpr bool is_empty() const
constexpr StringRef substr(int64_t start, int64_t size) const
constexpr bool startswith(StringRef prefix) const
constexpr int64_t size() const
constexpr const char * data() const
constexpr StringRef drop_prefix(int64_t n) const
void append(const T &value)
Span< T > as_span() const
IndexRange index_range() const
void extend(Span< T > array)
ccl_gpu_kernel_postfix ccl_global float int int int int float bool int offset
ccl_gpu_kernel_postfix int ccl_global int * indices
void *(* MEM_malloc_arrayN)(size_t len, size_t size, const char *str)
T distance(const T &a, const T &b)
void extract_normalized_words(StringRef str, LinearAllocator<> &allocator, Vector< StringRef, 64 > &r_words)
static int64_t count_utf8_code_points(StringRef str)
static bool match_word_initials(StringRef query, Span< StringRef > words, Span< int > word_match_map, MutableSpan< bool > r_word_is_matched, int start=0)
static constexpr int unused_word
int get_fuzzy_match_errors(StringRef query, StringRef full)
static int score_query_against_words(Span< StringRef > query_words, Span< StringRef > result_words)
int damerau_levenshtein_distance(StringRef a, StringRef b)
static int get_word_index_that_fuzzy_matches(StringRef query, Span< StringRef > words, Span< int > word_match_map, int *r_error_count)
static int get_shortest_word_index_that_startswith(StringRef query, Span< StringRef > words, Span< int > word_match_map)
static const pxr::TfToken b("b", pxr::TfToken::Immortal)
#define UI_MENU_ARROW_SEP
void BLI_string_search_add(StringSearch *search, const char *str, void *user_data, const int weight)
StringSearch * BLI_string_search_new()
int BLI_string_search_query(StringSearch *search, const char *query, void ***r_data)
void BLI_string_search_free(StringSearch *string_search)
#define UI_MENU_ARROW_SEP_UNICODE
blender::Span< blender::StringRef > normalized_words
blender::Vector< SearchItem > items
blender::LinearAllocator allocator