17 #include <type_traits>
25 namespace seqan3::detail
29 enum class error_type : uint8_t
45 template <
typename configuration_t,
typename index_t,
typename ...policies_t>
46 class unidirectional_search_algorithm :
protected policies_t...
50 using traits_t = search_traits<configuration_t>;
52 using search_result_type =
typename traits_t::search_result_type;
54 static_assert(!std::same_as<search_result_type, empty_type>,
"The search result type was not configured.");
60 unidirectional_search_algorithm() =
default;
61 unidirectional_search_algorithm(unidirectional_search_algorithm
const &) =
default;
62 unidirectional_search_algorithm(unidirectional_search_algorithm &&) =
default;
63 unidirectional_search_algorithm & operator=(unidirectional_search_algorithm
const &) =
default;
64 unidirectional_search_algorithm & operator=(unidirectional_search_algorithm &&) =
default;
65 ~unidirectional_search_algorithm() =
default;
77 unidirectional_search_algorithm(configuration_t
const & cfg, index_t
const & index) : policies_t{cfg}...
79 stratum = cfg.get_or(search_cfg::hit_strata{0}).stratum;
104 template <
typename indexed_query_t,
typename callback_t>
106 requires (std::tuple_size_v<indexed_query_t> == 2) &&
107 std::ranges::forward_range<std::tuple_element_t<1, indexed_query_t>> &&
108 std::invocable<callback_t, search_result_type>
110 void operator()(indexed_query_t && indexed_query, callback_t && callback)
112 auto && [query_idx, query] = indexed_query;
113 auto error_state = this->max_error_counts(query);
117 delegate = [&internal_hits] (
auto const & it)
122 perform_search_by_hit_strategy(internal_hits, query, error_state);
124 this->make_results(
std::move(internal_hits), query_idx, callback);
129 index_t
const * index_ptr{
nullptr};
132 std::function<void(
typename index_t::cursor_type
const &)> delegate;
138 template <
bool abort_on_hit,
typename query_t>
139 bool search_trivial(
typename index_t::cursor_type cur,
141 typename index_t::cursor_type::size_type
const query_pos,
142 search_param
const error_left,
143 error_type
const prev_error);
151 template <
typename query_t>
154 search_param error_state)
156 if constexpr (!traits_t::search_all_hits)
158 auto max_total = error_state.total;
159 error_state.total = 0;
161 while (internal_hits.
empty() && error_state.total <= max_total)
169 constexpr
bool abort_on_hit = !traits_t::search_all_best_hits;
170 search_trivial<abort_on_hit>(index_ptr->cursor(), query, 0, error_state, error_type::none);
174 if constexpr (traits_t::search_strata_hits)
176 if (!internal_hits.
empty())
178 internal_hits.
clear();
179 error_state.total += stratum - 1;
180 search_trivial<false>(index_ptr->cursor(), query, 0, error_state, error_type::none);
188 search_trivial<false>(index_ptr->cursor(), query, 0, error_state, error_type::none);
211 template <
typename configuration_t,
typename index_t,
typename ...policies_t>
212 template <
bool abort_on_hit,
typename query_t>
213 inline bool unidirectional_search_algorithm<configuration_t, index_t, policies_t...>::search_trivial(
214 typename index_t::cursor_type cur,
216 typename index_t::cursor_type::size_type
const query_pos,
217 search_param
const error_left,
218 error_type
const prev_error)
224 using drop_size_t = std::ranges::range_difference_t<query_t>;
226 cur.extend_right(
std::views::drop(query,
static_cast<drop_size_t
>(query_pos))))
237 bool const allow_insertion = (cur.query_length() > 0) ? cur.last_rank() !=
seqan3::to_rank(query[query_pos]) : true;
239 if (allow_insertion && (prev_error != error_type::deletion || error_left.substitution == 0) &&
240 error_left.insertion > 0)
242 search_param error_left2{error_left};
243 error_left2.insertion--;
248 if (search_trivial<abort_on_hit>(cur,
249 query, query_pos + 1,
251 error_type::insertion) &&
259 if (((query_pos > 0 && error_left.deletion > 0) || error_left.substitution > 0) && cur.extend_right())
264 if (error_left.substitution > 0)
267 search_param error_left2{error_left};
268 error_left2.total -= delta;
269 error_left2.substitution -= delta;
271 if (search_trivial<abort_on_hit>(cur,
275 error_type::matchmm) &&
286 if (error_left.substitution == 0 && cur.last_rank() ==
seqan3::to_rank(query[query_pos]))
288 if (search_trivial<abort_on_hit>(cur,
292 error_type::matchmm) &&
303 if ((prev_error != error_type::insertion || error_left.substitution == 0) &&
304 error_left.deletion > 0)
306 search_param error_left2{error_left};
308 error_left2.deletion--;
313 if (search_trivial<abort_on_hit>(cur,
317 error_type::deletion) &&
325 }
while (cur.cycle_back());
330 if (cur.extend_right(query[query_pos]))
332 if (search_trivial<abort_on_hit>(cur,
336 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
auto const move
A view that turns lvalue-references into rvalue-references.
Definition: move.hpp:74
Adaptations of concepts from the Ranges TS.
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.