BLI_string_search.hh

Go to the documentation of this file.

/* SPDX-FileCopyrightText: 2023 Blender Authors
 *
 * SPDX-License-Identifier: GPL-2.0-or-later */

 
#pragma once
 
#include "BLI_linear_allocator.hh"
#include "BLI_map.hh"
#include "BLI_span.hh"
#include "BLI_string_ref.hh"
#include "BLI_vector.hh"
 
namespace blender::string_search {
 
struct SearchItem {
  void *user_data;
  Span<StringRef> normalized_words;
  Span<int> word_group_ids;
  int main_group_id;
  int main_group_length;
  int total_length;
  float weight;
  int recent_time;
  bool is_deprecated;
};
 
struct RecentCache {
  Map<std::string, int> logical_time_by_str;
};

enum class MainWordsHeuristic {
  FirstGroup,
  LastGroup,
  All,
};

class StringSearchBase {
 protected:
  LinearAllocator<> allocator_;
  Vector<SearchItem> items_;
  const RecentCache *recent_cache_ = nullptr;
  MainWordsHeuristic main_words_heuristic_;
 
  void add_impl(StringRef str, void *user_data, float weight);
  Vector<void *> query_impl(StringRef query) const;
};

template<typename T> class StringSearch : private StringSearchBase {
 public:
  StringSearch(const RecentCache *recent_cache, const MainWordsHeuristic main_words_heuristic)
  {
    recent_cache_ = recent_cache;
    main_words_heuristic_ = main_words_heuristic;
  }

  void add(const StringRef str, T *user_data, const int weight = 0)
  {
    this->add_impl(str, (void *)user_data, weight);
  }

  Vector<T *> query(const StringRef query) const
  {
    Vector<void *> result = this->query_impl(query);
    Vector<T *> result_typed = result.as_span().cast<T *>();
    return result_typed;
  }
};

int damerau_levenshtein_distance(StringRef a, StringRef b);
int get_fuzzy_match_errors(StringRef query, StringRef full);
void extract_normalized_words(StringRef str,
                              LinearAllocator<> &allocator,
                              Vector<StringRef, 64> &r_words,
                              Vector<int, 64> &r_word_group_ids);
 
}  // namespace blender::string_search