22namespace seqan3::detail
27enum class error_type : uint8_t
40template <
typename configuration_t,
typename index_t,
typename... policies_t>
41class unidirectional_search_algorithm :
protected policies_t...
45 using traits_t = search_traits<configuration_t>;
47 using search_result_type =
typename traits_t::search_result_type;
49 static_assert(!std::same_as<search_result_type, empty_type>,
"The search result type was not configured.");
55 unidirectional_search_algorithm() =
default;
56 unidirectional_search_algorithm(unidirectional_search_algorithm
const &) =
default;
57 unidirectional_search_algorithm(unidirectional_search_algorithm &&) =
default;
58 unidirectional_search_algorithm & operator=(unidirectional_search_algorithm
const &) =
default;
59 unidirectional_search_algorithm & operator=(unidirectional_search_algorithm &&) =
default;
60 ~unidirectional_search_algorithm() =
default;
72 unidirectional_search_algorithm(configuration_t
const & cfg, index_t
const & index) : policies_t{cfg}...
74 stratum = cfg.get_or(search_cfg::hit_strata{0}).stratum;
99 template <
typename indexed_query_t,
typename callback_t>
100 requires (std::tuple_size_v<indexed_query_t> == 2)
101 && std::ranges::forward_range<std::tuple_element_t<1, indexed_query_t>>
102 && std::invocable<callback_t, search_result_type>
103 void operator()(indexed_query_t && indexed_query, callback_t && callback)
105 auto && [query_idx, query] = indexed_query;
106 auto error_state = this->max_error_counts(query);
110 delegate = [&internal_hits](
auto const & it)
115 perform_search_by_hit_strategy(internal_hits, query, error_state);
117 this->make_results(std::move(internal_hits), query_idx, callback);
122 index_t
const * index_ptr{
nullptr};
125 std::function<void(
typename index_t::cursor_type
const &)> delegate;
131 template <
bool abort_on_hit,
typename query_t>
132 bool search_trivial(
typename index_t::cursor_type cur,
134 typename index_t::cursor_type::size_type
const query_pos,
135 search_param
const error_left,
136 error_type
const prev_error);
144 template <
typename query_t>
147 search_param error_state)
149 if constexpr (!traits_t::search_all_hits)
151 auto max_total = error_state.total;
152 error_state.total = 0;
154 while (internal_hits.
empty() && error_state.total <= max_total)
162 constexpr bool abort_on_hit = !traits_t::search_all_best_hits;
163 search_trivial<abort_on_hit>(index_ptr->cursor(), query, 0, error_state, error_type::none);
167 if constexpr (traits_t::search_strata_hits)
169 if (!internal_hits.
empty())
171 internal_hits.
clear();
172 error_state.total += stratum - 1;
173 search_trivial<false>(index_ptr->cursor(), query, 0, error_state, error_type::none);
181 search_trivial<false>(index_ptr->cursor(), query, 0, error_state, error_type::none);
205template <
typename configuration_t,
typename index_t,
typename... policies_t>
206template <
bool abort_on_hit,
typename query_t>
207inline bool unidirectional_search_algorithm<configuration_t, index_t, policies_t...>::search_trivial(
208 typename index_t::cursor_type cur,
210 typename index_t::cursor_type::size_type
const query_pos,
211 search_param
const error_left,
212 error_type
const prev_error)
215 if (query_pos == std::ranges::size(query) || error_left.total == 0)
218 using drop_size_t = std::ranges::range_difference_t<query_t>;
219 if (query_pos == std::ranges::size(query)
220 || cur.extend_right(std::views::drop(query,
static_cast<drop_size_t
>(query_pos))))
231 bool const allow_insertion =
232 (cur.query_length() > 0) ? cur.last_rank() !=
seqan3::to_rank(query[query_pos]) : true;
234 if (allow_insertion && (prev_error != error_type::deletion || error_left.substitution == 0)
235 && error_left.insertion > 0)
237 search_param error_left2{error_left};
238 error_left2.insertion--;
243 if (search_trivial<abort_on_hit>(cur, query, query_pos + 1, error_left2, error_type::insertion)
251 if (((query_pos > 0 && error_left.deletion > 0) || error_left.substitution > 0) && cur.extend_right())
256 if (error_left.substitution > 0)
259 search_param error_left2{error_left};
260 error_left2.total -= delta;
261 error_left2.substitution -= delta;
263 if (search_trivial<abort_on_hit>(cur, query, query_pos + 1, error_left2, error_type::matchmm)
274 if (error_left.substitution == 0 && cur.last_rank() ==
seqan3::to_rank(query[query_pos]))
276 if (search_trivial<abort_on_hit>(cur, query, query_pos + 1, error_left, error_type::matchmm)
287 if ((prev_error != error_type::insertion || error_left.substitution == 0)
288 && error_left.deletion > 0)
290 search_param error_left2{error_left};
292 error_left2.deletion--;
297 if (search_trivial<abort_on_hit>(cur, query, query_pos, error_left2, error_type::deletion)
306 while (cur.cycle_back());
311 if (cur.extend_right(query[query_pos]))
313 if (search_trivial<abort_on_hit>(cur, query, query_pos + 1, error_left, 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 alphabet/concept.hpp:152
@ none
No flag is set.
Definition debug_stream_type.hpp:29
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.