15 #include <type_traits>
25 namespace seqan3::detail
37 template <
typename configuration_t,
typename index_t,
typename ...policies_t>
39 requires (template_specialisation_of<typename index_t::cursor_type, bi_fm_index_cursor>)
41 class search_scheme_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 search_scheme_algorithm() =
default;
56 search_scheme_algorithm(search_scheme_algorithm
const &) =
default;
57 search_scheme_algorithm(search_scheme_algorithm &&) =
default;
58 search_scheme_algorithm & operator=(search_scheme_algorithm
const &) =
default;
59 search_scheme_algorithm & operator=(search_scheme_algorithm &&) =
default;
60 ~search_scheme_algorithm() =
default;
73 search_scheme_algorithm(configuration_t
const & cfg, index_t
const & index) : policies_t{cfg}...
75 stratum = cfg.get_or(search_cfg::hit_strata{0}).stratum;
100 template <tuple_like indexed_query_t,
typename callback_t>
102 requires (std::tuple_size_v<indexed_query_t> == 2) &&
103 std::ranges::forward_range<std::tuple_element_t<1, indexed_query_t>> &&
104 std::invocable<callback_t, search_result_type>
106 void operator()(indexed_query_t && indexed_query, callback_t && callback)
108 auto && [query_idx, query] = indexed_query;
109 auto error_state = this->max_error_counts(query);
113 auto on_hit_delegate = [&internal_hits] (
auto const & it)
118 perform_search_by_hit_strategy(internal_hits, query, error_state, on_hit_delegate);
121 this->make_results(
std::move(internal_hits), query_idx, callback);
126 index_t
const * index_ptr{
nullptr};
132 template <
bool abort_on_hit,
typename query_t,
typename delegate_t>
133 inline void search_algo_bi(query_t & query, search_param
const error_left, delegate_t && delegate);
142 template <
typename query_t,
typename delegate_t>
145 search_param error_state,
146 delegate_t
const & on_hit_delegate)
148 if constexpr (!traits_t::search_all_hits)
150 auto max_total = error_state.total;
151 error_state.total = 0;
152 while (internal_hits.
empty() && error_state.total <= max_total)
160 constexpr
bool abort_on_hit = !traits_t::search_all_best_hits;
161 search_algo_bi<abort_on_hit>(query, error_state, on_hit_delegate);
164 if constexpr (traits_t::search_strata_hits)
166 if (!internal_hits.
empty())
168 internal_hits.
clear();
169 error_state.total += stratum - 1;
170 search_algo_bi<false>(query, error_state, on_hit_delegate);
178 search_algo_bi<false>(query, error_state, on_hit_delegate);
222 template <
typename search_scheme_t>
223 inline auto search_scheme_block_info(search_scheme_t
const & search_scheme,
size_t const query_length)
225 using blocks_length_type =
typename search_scheme_t::value_type::blocks_length_type;
227 bool constexpr is_dyn_scheme = std::same_as<search_scheme_t, search_scheme_dyn_type>;
233 transformation_trait_or_t<std::tuple_size<search_scheme_t>,
237 if constexpr (is_dyn_scheme)
238 result.resize(search_scheme.size());
240 uint8_t
const blocks {search_scheme[0].blocks()};
241 size_t const block_length{query_length / blocks};
242 uint8_t
const rest {
static_cast<uint8_t
>(query_length % blocks)};
244 blocks_length_type blocks_length;
247 if constexpr (is_dyn_scheme)
248 blocks_length.resize(blocks, block_length);
250 blocks_length.fill(block_length);
252 for (uint8_t block_id = 0; block_id < rest; ++block_id)
253 ++blocks_length[block_id];
255 for (uint8_t search_id = 0; search_id < search_scheme.size(); ++search_id)
257 auto const &
search = search_scheme[search_id];
259 auto & [search_blocks_length, start_pos] = result[search_id];
263 if constexpr (is_dyn_scheme)
264 search_blocks_length.resize(blocks);
265 search_blocks_length[0] = blocks_length[
search.pi[0] - 1];
266 for (uint8_t i = 1; i < blocks; ++i)
268 search_blocks_length[i] = blocks_length[
search.pi[i] - 1] + search_blocks_length[i - 1];
270 start_pos += search_blocks_length[i] - search_blocks_length[i - 1];
279 template <
bool abort_on_hit,
typename cursor_t,
typename query_t,
typename search_t,
typename blocks_length_t,
281 inline bool search_ss(cursor_t cur, query_t & query,
282 typename cursor_t::size_type
const lb,
typename cursor_t::size_type
const rb,
283 uint8_t
const errors_spent, uint8_t
const block_id,
bool const go_right, search_t
const &
search,
284 blocks_length_t
const & blocks_length, search_param
const error_left, delegate_t && delegate);
317 template <
bool abort_on_hit,
typename cursor_t,
typename query_t,
typename search_t,
typename blocks_length_t,
319 inline bool search_ss_exact(cursor_t cur, query_t & query,
320 typename cursor_t::size_type
const lb,
typename cursor_t::size_type
const rb,
321 uint8_t
const errors_spent, uint8_t
const block_id,
bool const go_right,
322 search_t
const &
search, blocks_length_t
const & blocks_length,
323 search_param
const error_left, delegate_t && delegate)
325 using size_type =
typename cursor_t::size_type;
327 uint8_t
const block_id2 = std::min<uint8_t>(block_id + 1,
search.blocks() - 1);
328 bool const go_right2 = (block_id <
search.blocks() - 1) && (
search.pi[block_id + 1] >
search.pi[block_id]);
332 size_type
const infix_lb = rb - 1;
333 size_type
const infix_rb = lb + blocks_length[block_id] - 1;
335 if (!cur.extend_right(query |
views::slice(infix_lb, infix_rb + 1)))
338 if (search_ss<abort_on_hit>(cur, query, lb, infix_rb + 2, errors_spent, block_id2, go_right2,
search,
339 blocks_length, error_left, delegate) && abort_on_hit)
346 size_type
const infix_lb = rb - blocks_length[block_id] - 1;
347 size_type
const infix_rb = lb - 1;
349 if (!cur.extend_left(query |
views::slice(infix_lb, infix_rb + 1)))
352 if (search_ss<abort_on_hit>(cur, query, infix_lb, rb, errors_spent, block_id2, go_right2,
search, blocks_length,
353 error_left, delegate) && abort_on_hit)
366 template <
bool abort_on_hit,
typename cursor_t,
typename query_t,
typename search_t,
typename blocks_length_t,
368 inline bool search_ss_deletion(cursor_t cur, query_t & query,
369 typename cursor_t::size_type
const lb,
typename cursor_t::size_type
const rb,
370 uint8_t
const errors_spent, uint8_t
const block_id,
bool const go_right,
371 search_t
const &
search, blocks_length_t
const & blocks_length,
372 search_param
const error_left, delegate_t && delegate)
374 uint8_t
const max_error_left_in_block =
search.u[block_id] - errors_spent;
375 uint8_t
const min_error_left_in_block =
std::max(
search.l[block_id] - errors_spent, 0);
378 if (min_error_left_in_block == 0)
380 uint8_t
const block_id2 = std::min<uint8_t>(block_id + 1,
search.blocks() - 1);
381 bool const go_right2 = block_id2 == 0 ? true :
search.pi[block_id2] >
search.pi[block_id2 - 1];
383 if (search_ss<abort_on_hit>(cur, query, lb, rb, errors_spent, block_id2, go_right2,
search, blocks_length,
384 error_left, delegate) && abort_on_hit)
393 if (!(
search.pi[block_id] == 1 && !go_right) &&
394 !(
search.pi[block_id] ==
search.blocks() && go_right) &&
395 max_error_left_in_block > 0 && error_left.total > 0 && error_left.deletion > 0 &&
396 ((go_right && cur.extend_right()) || (!go_right && cur.extend_left())))
398 search_param error_left2{error_left};
400 error_left2.deletion--;
403 if (search_ss_deletion<abort_on_hit>(cur, query, lb, rb, errors_spent + 1, block_id, go_right,
search,
404 blocks_length, error_left2, delegate) && abort_on_hit)
408 }
while ((go_right && cur.cycle_back()) || (!go_right && cur.cycle_front()));
420 template <
bool abort_on_hit,
typename cursor_t,
typename query_t,
typename search_t,
typename blocks_length_t,
422 inline bool search_ss_children(cursor_t cur, query_t & query,
423 typename cursor_t::size_type
const lb,
typename cursor_t::size_type
const rb,
424 uint8_t
const errors_spent, uint8_t
const block_id,
bool const go_right,
425 uint8_t
const min_error_left_in_block, search_t
const &
search,
426 blocks_length_t
const & blocks_length, search_param
const error_left,
427 delegate_t && delegate)
429 using size_type =
typename cursor_t::size_type;
430 if ((go_right && cur.extend_right()) || (!go_right && cur.extend_left()))
432 size_type
const chars_left = blocks_length[block_id] - (rb - lb - 1);
434 size_type lb2 = lb - !go_right;
435 size_type rb2 = rb + go_right;
439 bool const delta = cur.last_rank() !=
to_rank(query[(go_right ? rb : lb) - 1]);
445 if (error_left.deletion == 0 && chars_left + delta < min_error_left_in_block + 1u)
448 if (!delta || error_left.substitution > 0)
450 search_param error_left2{error_left};
451 error_left2.total -= delta;
452 error_left2.substitution -= delta;
455 if (rb - lb == blocks_length[block_id])
459 if (error_left.deletion > 0)
461 if (search_ss_deletion<abort_on_hit>(cur, query, lb2, rb2, errors_spent + delta, block_id,
462 go_right,
search, blocks_length, error_left2, delegate) &&
470 uint8_t
const block_id2 = std::min<uint8_t>(block_id + 1,
search.blocks() - 1);
471 bool const go_right2 = block_id2 == 0 ? true :
search.pi[block_id2] >
search.pi[block_id2 - 1];
473 if (search_ss<abort_on_hit>(cur, query, lb2, rb2, errors_spent + delta, block_id2, go_right2,
474 search, blocks_length, error_left2, delegate) &&
483 if (search_ss<abort_on_hit>(cur, query, lb2, rb2, errors_spent + delta, block_id, go_right,
search,
484 blocks_length, error_left2, delegate) && abort_on_hit)
495 if (error_left.deletion > 0 &&
499 search_param error_left3{error_left};
501 error_left3.deletion--;
502 search_ss<abort_on_hit>(cur, query, lb, rb, errors_spent + 1, block_id, go_right,
search, blocks_length,
503 error_left3, delegate);
505 }
while ((go_right && cur.cycle_back()) || (!go_right && cur.cycle_front()));
514 template <
bool abort_on_hit,
typename cursor_t,
typename query_t,
typename search_t,
515 typename blocks_length_t,
typename delegate_t>
516 inline bool search_ss(cursor_t cur, query_t & query,
517 typename cursor_t::size_type
const lb,
typename cursor_t::size_type
const rb,
518 uint8_t
const errors_spent, uint8_t
const block_id,
bool const go_right, search_t
const &
search,
519 blocks_length_t
const & blocks_length, search_param
const error_left, delegate_t && delegate)
521 uint8_t
const max_error_left_in_block =
search.u[block_id] - errors_spent;
522 uint8_t
const min_error_left_in_block =
std::max(
search.l[block_id] - errors_spent, 0);
525 if (min_error_left_in_block == 0 && lb == 0 && rb ==
std::ranges::size(query) + 1)
531 else if (((max_error_left_in_block == 0) && (rb - lb - 1 != blocks_length[block_id])) ||
532 (error_left.total == 0 && min_error_left_in_block == 0))
534 if (search_ss_exact<abort_on_hit>(cur, query, lb, rb, errors_spent, block_id, go_right,
search, blocks_length,
535 error_left, delegate) && abort_on_hit)
542 else if (error_left.total > 0)
545 if (error_left.insertion > 0)
547 using size_type =
typename cursor_t::size_type;
549 size_type
const lb2 = lb - !go_right;
550 size_type
const rb2 = rb + go_right;
552 search_param error_left2{error_left};
554 error_left2.insertion--;
556 if (rb - lb == blocks_length[block_id])
563 if (search_ss_deletion<abort_on_hit>(cur, query, lb2, rb2, errors_spent + 1, block_id, go_right,
search,
564 blocks_length, error_left2, delegate) && abort_on_hit)
571 if (search_ss<abort_on_hit>(cur, query, lb2, rb2, errors_spent + 1, block_id, go_right,
search,
572 blocks_length, error_left2, delegate) && abort_on_hit)
578 if (search_ss_children<abort_on_hit>(cur, query, lb, rb, errors_spent, block_id, go_right,
579 min_error_left_in_block,
search, blocks_length, error_left, delegate) &&
610 template <
bool abort_on_hit,
typename index_t,
typename query_t,
typename search_scheme_t,
typename delegate_t>
611 inline void search_ss(index_t
const & index, query_t & query, search_param
const error_left,
612 search_scheme_t
const & search_scheme, delegate_t && delegate)
615 auto const block_info = search_scheme_block_info(search_scheme,
std::ranges::size(query));
617 for (uint8_t search_id = 0; search_id < search_scheme.size(); ++search_id)
619 auto const &
search = search_scheme[search_id];
620 auto const & [blocks_length, start_pos] = block_info[search_id];
622 bool const hit = search_ss<abort_on_hit>(
625 start_pos, start_pos + 1,
635 if (abort_on_hit && hit)
657 template <
typename configuration_t,
typename index_t,
typename ...policies_t>
658 template <
bool abort_on_hit,
typename query_t,
typename delegate_t>
659 inline void search_scheme_algorithm<configuration_t, index_t, policies_t...>::search_algo_bi(
661 search_param
const error_left,
662 delegate_t && delegate)
664 switch (error_left.total)
667 search_ss<abort_on_hit>(*index_ptr, query, error_left, optimum_search_scheme<0, 0>, delegate);
670 search_ss<abort_on_hit>(*index_ptr, query, error_left, optimum_search_scheme<0, 1>, delegate);
673 search_ss<abort_on_hit>(*index_ptr, query, error_left, optimum_search_scheme<0, 2>, delegate);
676 search_ss<abort_on_hit>(*index_ptr, query, error_left, optimum_search_scheme<0, 3>, delegate);
679 auto const & search_scheme{compute_ss(0, error_left.total)};
680 search_ss<abort_on_hit>(*index_ptr, query, error_left, search_scheme, delegate);
Provides the bidirectional seqan3::bi_fm_index.
constexpr auto to_rank
Return the rank representation of a (semi-)alphabet object.
Definition: concept.hpp:155
auto search(queries_t &&queries, index_t const &index, configuration_t const &cfg=search_cfg::default_configuration)
Search a query or a range of queries in an index.
Definition: search.hpp:108
constexpr size_t size
The size of a type pack.
Definition: traits.hpp:151
constexpr auto slice
A view adaptor that returns a half-open interval on the underlying range.
Definition: slice.hpp:189
auto const move
A view that turns lvalue-references into rvalue-references.
Definition: move.hpp:74
Provides the concept for seqan3::detail::sdsl_index.
Provides data structures used by different search algorithms.
Provides the data structures and precomputed instances for (optimum) search schemes.
Provides seqan3::detail::search_traits.
Provides seqan3::views::slice.