search_index.hpp

Go to the documentation of this file.

#pragma once
 
// SearchIndex — ranked substring / prefix / fuzzy search over a fixed list of
// strings.
//
// This is the concrete "index and filter a large library" workload behind the
// off-UI-thread query service (see core/view/.../query_service.hpp). It is a
// pure data structure with no threads of its own: `build()` does the one-time
// normalization work and `query()` is a `const` scan, so callers are free to
// run either on a background thread and marshal the result back themselves.
//
// Ranking, highest first: exact match > prefix match > substring match >
// subsequence ("fuzzy") match. Within a tier, shorter items and earlier match
// positions rank higher; ties break on the item's original index so results
// are fully deterministic. An empty query returns every item in original
// order.
//
// Matching is ASCII-case-insensitive by default. Unicode is compared
// byte-for-byte (no case folding beyond ASCII) — deliberate, to keep results
// deterministic and locale-independent.
 
#include <pulp/runtime/cancel.hpp>
 
#include <cstddef>
#include <string>
#include <string_view>
#include <vector>
 
namespace pulp::runtime {
 
struct SearchQueryOptions {
    std::size_t max_results = 0;

    bool fuzzy = true;

    bool case_sensitive = false;
};
 
class SearchIndex {
public:
    struct Match {
        std::size_t index;  
        int score;          
    };
 
    SearchIndex() = default;

    void build(std::vector<std::string> items, const CancelToken& cancel = {});
 
    std::size_t size() const { return items_.size(); }
    bool empty() const { return items_.empty(); }

    const std::string& item(std::size_t i) const { return items_[i]; }

    std::vector<Match> query(std::string_view query, const SearchQueryOptions& options = {},
                             const CancelToken& cancel = {}) const;
 
  private:
    std::vector<std::string> items_;       
    std::vector<std::string> normalized_;  
};
 
}  // namespace pulp::runtime