#include "HybridFuzzy.hpp"
#include <algorithm>
#include <utility>
namespace margelo::nitro::fuzzy {
namespace {
// ASCII lower case; other bytes pass through, so UTF-8 still matches itself.
char lower(char c) {
return c >= 'A' && c <= 'Z' ? static_cast<char>(c + ('a' - 'A')) : c;
}
bool startsWord(const std::string& text, size_t i) {
if (i == 0) return true;
char before = text[i - 1];
return before == ' ' || before == '-' || before == '_' || before == '/';
}
// The query's letters in the item, in order: a score, or -1 when one is missing.
int score(const std::string& query, const std::string& item) {
int total = 0;
int streak = 0;
size_t found = 0;
for (size_t i = 0; i < item.size() && found < query.size(); i++) {
if (lower(item[i]) != query[found]) {
streak = 0;
continue;
}
streak++;
total += 1 + 2 * streak + (startsWord(item, i) ? 8 : 0);
found++;
}
if (found < query.size()) return -1;
return total - static_cast<int>(item.size() / 8);
}
} // namespace
void HybridFuzzy::setItems(const std::vector<std::string>& items) {
items_ = items;
bytes_ = 0;
for (const auto& item : items_) bytes_ += sizeof(std::string) + item.capacity();
}
std::vector<double> HybridFuzzy::search(const std::string& query, double limit) {
std::string q;
q.reserve(query.size());
for (char c : query) {
if (c != ' ') q.push_back(lower(c));
}
// (score, index) for every item that has all the letters.
std::vector<std::pair<int, int>> hits;
hits.reserve(items_.size());
for (int i = 0; i < static_cast<int>(items_.size()); i++) {
int s = score(q, items_[i]);
if (s >= 0) hits.emplace_back(s, i);
}
// Only the best `limit` are sorted: a short screen of a long list costs little.
auto count = std::min(hits.size(), static_cast<size_t>(std::max(limit, 0.0)));
std::partial_sort(hits.begin(), hits.begin() + count, hits.end(), [](const auto& a, const auto& b) {
return a.first != b.first ? a.first > b.first : a.second < b.second;
});
std::vector<double> best;
best.reserve(count);
for (size_t k = 0; k < count; k++) best.push_back(static_cast<double>(hits[k].second));
return best;
}
size_t HybridFuzzy::getExternalMemorySize() noexcept {
return bytes_;
}
} // namespace margelo::nitro::fuzzy