25namespace seqan3::detail
30enum class error_type : uint8_t
43template <
typename configuration_t,
typename index_t,
typename ...policies_t>
44class unidirectional_search_algorithm :
protected policies_t...
48 using traits_t = search_traits<configuration_t>;
50 using search_result_type =
typename traits_t::search_result_type;
52 static_assert(!std::same_as<search_result_type, empty_type>,
"The search result type was not configured.");
58 unidirectional_search_algorithm() =
default;
59 unidirectional_search_algorithm(unidirectional_search_algorithm
const &) =
default;
60 unidirectional_search_algorithm(unidirectional_search_algorithm &&) =
default;
61 unidirectional_search_algorithm & operator=(unidirectional_search_algorithm
const &) =
default;
62 unidirectional_search_algorithm & operator=(unidirectional_search_algorithm &&) =
default;
63 ~unidirectional_search_algorithm() =
default;
75 unidirectional_search_algorithm(configuration_t
const & cfg, index_t
const & index) : policies_t{cfg}...
77 stratum = cfg.get_or(search_cfg::hit_strata{0}).stratum;
102 template <
typename indexed_query_t,
typename callback_t>
104 requires (std::tuple_size_v<indexed_query_t> == 2) &&
105 std::ranges::forward_range<std::tuple_element_t<1, indexed_query_t>> &&
106 std::invocable<callback_t, search_result_type>
108 void operator()(indexed_query_t && indexed_query, callback_t && callback)
110 auto && [query_idx, query] = indexed_query;
111 auto error_state = this->max_error_counts(query);
115 delegate = [&internal_hits] (
auto const & it)
120 perform_search_by_hit_strategy(internal_hits, query, error_state);
122 this->make_results(std::move(internal_hits), query_idx, callback);
127 index_t
const * index_ptr{
nullptr};
130 std::function<void(
typename index_t::cursor_type
const &)> delegate;
136 template <
bool abort_on_hit,
typename query_t>
137 bool search_trivial(
typename index_t::cursor_type cur,
139 typename index_t::cursor_type::size_type
const query_pos,
140 search_param
const error_left,
141 error_type
const prev_error);
149 template <
typename query_t>
152 search_param error_state)
154 if constexpr (!traits_t::search_all_hits)
156 auto max_total = error_state.total;
157 error_state.total = 0;
159 while (internal_hits.
empty() && error_state.total <= max_total)
167 constexpr bool abort_on_hit = !traits_t::search_all_best_hits;
168 search_trivial<abort_on_hit>(index_ptr->cursor(), query, 0, error_state, error_type::none);
172 if constexpr (traits_t::search_strata_hits)
174 if (!internal_hits.
empty())
176 internal_hits.
clear();
177 error_state.total += stratum - 1;
178 search_trivial<false>(index_ptr->cursor(), query, 0, error_state, error_type::none);
186 search_trivial<false>(index_ptr->cursor(), query, 0, error_state, error_type::none);
210template <
typename configuration_t,
typename index_t,
typename ...policies_t>
211template <
bool abort_on_hit,
typename query_t>
212inline bool unidirectional_search_algorithm<configuration_t, index_t, policies_t...>::search_trivial(
213 typename index_t::cursor_type cur,
215 typename index_t::cursor_type::size_type
const query_pos,
216 search_param
const error_left,
217 error_type
const prev_error)
223 using drop_size_t = std::ranges::range_difference_t<query_t>;
225 cur.extend_right(
std::views::drop(query,
static_cast<drop_size_t
>(query_pos))))
236 bool const allow_insertion = (cur.query_length() > 0) ? cur.last_rank() !=
seqan3::to_rank(query[query_pos]) : true;
238 if (allow_insertion && (prev_error != error_type::deletion || error_left.substitution == 0) &&
239 error_left.insertion > 0)
241 search_param error_left2{error_left};
242 error_left2.insertion--;
247 if (search_trivial<abort_on_hit>(cur,
248 query, query_pos + 1,
250 error_type::insertion) &&
258 if (((query_pos > 0 && error_left.deletion > 0) || error_left.substitution > 0) && cur.extend_right())
263 if (error_left.substitution > 0)
266 search_param error_left2{error_left};
267 error_left2.total -= delta;
268 error_left2.substitution -= delta;
270 if (search_trivial<abort_on_hit>(cur,
274 error_type::matchmm) &&
285 if (error_left.substitution == 0 && cur.last_rank() ==
seqan3::to_rank(query[query_pos]))
287 if (search_trivial<abort_on_hit>(cur,
291 error_type::matchmm) &&
302 if ((prev_error != error_type::insertion || error_left.substitution == 0) &&
303 error_left.deletion > 0)
305 search_param error_left2{error_left};
307 error_left2.deletion--;
312 if (search_trivial<abort_on_hit>(cur,
316 error_type::deletion) &&
324 }
while (cur.cycle_back());
329 if (cur.extend_right(query[query_pos]))
331 if (search_trivial<abort_on_hit>(cur,
335 error_type::matchmm) &&
Core alphabet concept and free function/type trait wrappers.
constexpr auto to_rank
Return the rank representation of a (semi-)alphabet object.
Definition: concept.hpp:155
@ none
No flag is set.
Definition: debug_stream_type.hpp:32
typename decltype(detail::split_after< i >(list_t{}))::second_type drop
Return a seqan3::type_list of the types in the input type list, except the first n.
Definition: traits.hpp:388
constexpr size_t size
The size of a type pack.
Definition: traits.hpp:151
The <ranges> header from C++20's standard library.
Provides the concept for seqan3::detail::sdsl_index.
Provides data structures used by different search algorithms.
Provides seqan3::detail::search_traits.
Forward declares seqan3::detail::test_accessor.