40template <
typename configuration_t,
typename index_t,
typename... policies_t>
49 static_assert(!std::same_as<search_result_type, empty_type>,
"The search result type was not configured.");
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)
112 internal_hits.push_back(it);
117 this->make_results(std::move(internal_hits), query_idx, callback);
131 template <
bool abort_on_hit,
typename query_t>
134 typename index_t::cursor_type::size_type
const query_pos,
144 template <
typename query_t>
151 auto max_total = error_state.
total;
152 error_state.
total = 0;
154 while (internal_hits.
empty() && error_state.
total <= max_total)
169 if (!internal_hits.
empty())
171 internal_hits.
clear();
205template <
typename configuration_t,
typename index_t,
typename... policies_t>
206template <
bool abort_on_hit,
typename query_t>
208 typename index_t::cursor_type cur,
210 typename index_t::cursor_type::size_type
const query_pos,
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;
251 if (((query_pos > 0 && error_left.
deletion > 0) || error_left.
substitution > 0) && cur.extend_right())
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)
276 if (search_trivial<abort_on_hit>(cur, query, query_pos + 1, error_left,
error_type::matchmm)
292 error_left2.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.
The algorithm that performs a unidirectional search on an FM index using trivial backtracking.
Definition unidirectional_search_algorithm.hpp:42
std::function< void(typename index_t::cursor_type const &)> delegate
A function object that stores the on-hit-delegate to be executed whenever a hit in the index is found...
Definition unidirectional_search_algorithm.hpp:125
unidirectional_search_algorithm()=default
Defaulted.
~unidirectional_search_algorithm()=default
Defaulted.
unidirectional_search_algorithm(unidirectional_search_algorithm &&)=default
Defaulted.
index_t const * index_ptr
A pointer to the fm index which is used to perform the unidirectional search.
Definition unidirectional_search_algorithm.hpp:122
unidirectional_search_algorithm(unidirectional_search_algorithm const &)=default
Defaulted.
unidirectional_search_algorithm & operator=(unidirectional_search_algorithm const &)=default
Defaulted.
unidirectional_search_algorithm & operator=(unidirectional_search_algorithm &&)=default
Defaulted.
uint8_t stratum
The stratum value if set.
Definition unidirectional_search_algorithm.hpp:128
typename traits_t::search_result_type search_result_type
The search result type.
Definition unidirectional_search_algorithm.hpp:47
void perform_search_by_hit_strategy(std::vector< typename index_t::cursor_type > &internal_hits, query_t &query, search_param error_state)
Calls search_trivial depending on the search strategy (hit configuration) given in the configuration.
Definition unidirectional_search_algorithm.hpp:145
unidirectional_search_algorithm(configuration_t const &cfg, index_t const &index)
Constructs from a configuration object and an index.
Definition unidirectional_search_algorithm.hpp:72
Configuration element to receive all hits with the best number of errors plus the given stratum....
Definition hit.hpp:107
@ none
The corresponding alignment coordinate will not be incrementable/decrementable.
constexpr auto to_rank
Return the rank representation of a (semi-)alphabet object.
Definition alphabet/concept.hpp:152
error_type
An enumerator for the different error types used during the backtracking.
Definition unidirectional_search_algorithm.hpp:28
bool search_trivial(typename index_t::cursor_type cur, query_t &query, typename index_t::cursor_type::size_type const query_pos, search_param const error_left, error_type const prev_error)
Searches a query sequence in an index using trivial backtracking.
Definition unidirectional_search_algorithm.hpp:207
@ none
No error or match was enumerated yet.
@ matchmm
A match or a mismatch was enumerated.
@ deletion
A deletion was enumerated in previous backtracking step.
@ insertion
A insertion was enumerated in previous backtracking step.
The internal SeqAn3 namespace.
Definition aligned_sequence_concept.hpp:26
Provides the concept for seqan3::detail::sdsl_index.
Provides data structures used by different search algorithms.
Provides seqan3::detail::search_traits.
Object grouping numbers of errors for different kind of error types.
Definition search_common.hpp:22
uint8_t insertion
Total number of insertion errors.
Definition search_common.hpp:28
uint8_t total
Total number of errors (upper bound over all error types).
Definition search_common.hpp:24
uint8_t deletion
Total number of deletion errors.
Definition search_common.hpp:30
uint8_t substitution
Total number of substitution errors.
Definition search_common.hpp:26
A collection of traits extracted from the search configuration.
Definition search_traits.hpp:31
static constexpr bool search_strata_hits
A flag indicating whether search should find strata hits.
Definition search_traits.hpp:62
static constexpr bool search_all_best_hits
A flag indicating whether search should find all best hits.
Definition search_traits.hpp:60
typename std::remove_cvref_t< decltype(std::declval< search_configuration_t >().get_or(search_cfg::detail::result_type< empty_search_result_type >{}))>::type search_result_type
The configured search result type.
Definition search_traits.hpp:36
static constexpr bool search_all_hits
A flag indicating whether search should find all hits.
Definition search_traits.hpp:55
Forward declares seqan3::detail::test_accessor.