22namespace seqan3::detail
31template <
typename configuration_t,
typename index_t,
typename... policies_t>
32 requires (template_specialisation_of<typename index_t::cursor_type, bi_fm_index_cursor>)
33class search_scheme_algorithm : protected policies_t...
37 using traits_t = search_traits<configuration_t>;
39 using search_result_type =
typename traits_t::search_result_type;
41 static_assert(!std::same_as<search_result_type, empty_type>,
"The search result type was not configured.");
47 search_scheme_algorithm() =
default;
48 search_scheme_algorithm(search_scheme_algorithm
const &) =
default;
49 search_scheme_algorithm(search_scheme_algorithm &&) =
default;
50 search_scheme_algorithm & operator=(search_scheme_algorithm
const &) =
default;
51 search_scheme_algorithm & operator=(search_scheme_algorithm &&) =
default;
52 ~search_scheme_algorithm() =
default;
65 search_scheme_algorithm(configuration_t
const & cfg, index_t
const & index) : policies_t{cfg}...
67 stratum = cfg.get_or(search_cfg::hit_strata{0}).stratum;
92 template <tuple_like indexed_query_t,
typename callback_t>
93 requires (std::tuple_size_v<indexed_query_t> == 2)
94 && std::ranges::forward_range<std::tuple_element_t<1, indexed_query_t>>
95 && std::invocable<callback_t, search_result_type>
96 void operator()(indexed_query_t && indexed_query, callback_t && callback)
98 auto && [query_idx, query] = indexed_query;
99 auto error_state = this->max_error_counts(query);
103 auto on_hit_delegate = [&internal_hits](
auto const & it)
108 perform_search_by_hit_strategy(internal_hits, query, error_state, on_hit_delegate);
111 this->make_results(std::move(internal_hits), query_idx, callback);
116 index_t
const * index_ptr{
nullptr};
122 template <
bool abort_on_hit,
typename query_t,
typename delegate_t>
123 inline void search_algo_bi(query_t & query, search_param
const error_left, delegate_t && delegate);
132 template <
typename query_t,
typename delegate_t>
135 search_param error_state,
136 delegate_t
const & on_hit_delegate)
138 if constexpr (!traits_t::search_all_hits)
140 auto max_total = error_state.total;
141 error_state.total = 0;
142 while (internal_hits.
empty() && error_state.total <= max_total)
150 constexpr bool abort_on_hit = !traits_t::search_all_best_hits;
151 search_algo_bi<abort_on_hit>(query, error_state, on_hit_delegate);
154 if constexpr (traits_t::search_strata_hits)
156 if (!internal_hits.
empty())
158 internal_hits.
clear();
159 error_state.total += stratum - 1;
160 search_algo_bi<false>(query, error_state, on_hit_delegate);
168 search_algo_bi<false>(query, error_state, on_hit_delegate);
214template <
typename search_scheme_t>
215inline auto search_scheme_block_info(search_scheme_t
const & search_scheme,
size_t const query_length)
217 using blocks_length_type =
typename search_scheme_t::value_type::blocks_length_type;
219 constexpr bool is_dyn_scheme = std::same_as<search_scheme_t, search_scheme_dyn_type>;
226 transformation_trait_or_t<std::tuple_size<search_scheme_t>,
std::false_type>::value>>;
229 if constexpr (is_dyn_scheme)
230 result.resize(search_scheme.size());
232 uint8_t
const blocks{search_scheme[0].blocks()};
233 size_t const block_length{query_length / blocks};
234 uint8_t
const rest{
static_cast<uint8_t
>(query_length % blocks)};
236 blocks_length_type blocks_length;
239 if constexpr (is_dyn_scheme)
240 blocks_length.resize(blocks, block_length);
242 blocks_length.fill(block_length);
244 for (uint8_t block_id = 0; block_id < rest; ++block_id)
245 ++blocks_length[block_id];
247 for (uint8_t search_id = 0; search_id < search_scheme.size(); ++search_id)
249 auto const &
search = search_scheme[search_id];
251 auto & [search_blocks_length, start_pos] = result[search_id];
255 if constexpr (is_dyn_scheme)
256 search_blocks_length.resize(blocks);
257 search_blocks_length[0] = blocks_length[
search.pi[0] - 1];
258 for (uint8_t i = 1; i < blocks; ++i)
260 search_blocks_length[i] = blocks_length[
search.pi[i] - 1] + search_blocks_length[i - 1];
262 start_pos += search_blocks_length[i] - search_blocks_length[i - 1];
271template <
bool abort_on_hit,
275 typename blocks_length_t,
277inline bool search_ss(cursor_t cur,
279 typename cursor_t::size_type
const lb,
280 typename cursor_t::size_type
const rb,
281 uint8_t
const errors_spent,
282 uint8_t
const block_id,
284 search_t
const & search,
285 blocks_length_t
const & blocks_length,
286 search_param
const error_left,
287 delegate_t && delegate);
321template <
bool abort_on_hit,
325 typename blocks_length_t,
327inline bool search_ss_exact(cursor_t cur,
329 typename cursor_t::size_type
const lb,
330 typename cursor_t::size_type
const rb,
331 uint8_t
const errors_spent,
332 uint8_t
const block_id,
334 search_t
const & search,
335 blocks_length_t
const & blocks_length,
336 search_param
const error_left,
337 delegate_t && delegate)
339 using size_type =
typename cursor_t::size_type;
341 uint8_t
const block_id2 = std::min<uint8_t>(block_id + 1,
search.blocks() - 1);
342 bool const go_right2 = (block_id <
search.blocks() - 1) && (
search.pi[block_id + 1] >
search.pi[block_id]);
346 size_type
const infix_lb = rb - 1;
347 size_type
const infix_rb = lb + blocks_length[block_id] - 1;
349 if (!cur.extend_right(query |
views::slice(infix_lb, infix_rb + 1)))
352 if (search_ss<abort_on_hit>(cur,
370 size_type
const infix_lb = rb - blocks_length[block_id] - 1;
371 size_type
const infix_rb = lb - 1;
373 if (!cur.extend_left(query |
views::slice(infix_lb, infix_rb + 1)))
376 if (search_ss<abort_on_hit>(cur,
401template <
bool abort_on_hit,
405 typename blocks_length_t,
407inline bool search_ss_deletion(cursor_t cur,
409 typename cursor_t::size_type
const lb,
410 typename cursor_t::size_type
const rb,
411 uint8_t
const errors_spent,
412 uint8_t
const block_id,
414 search_t
const & search,
415 blocks_length_t
const & blocks_length,
416 search_param
const error_left,
417 delegate_t && delegate)
419 uint8_t
const max_error_left_in_block =
search.u[block_id] - errors_spent;
420 uint8_t
const min_error_left_in_block =
std::max(
search.l[block_id] - errors_spent, 0);
423 if (min_error_left_in_block == 0)
425 uint8_t
const block_id2 = std::min<uint8_t>(block_id + 1,
search.blocks() - 1);
426 bool const go_right2 = block_id2 == 0 ? true :
search.pi[block_id2] >
search.pi[block_id2 - 1];
428 if (search_ss<abort_on_hit>(cur,
448 if (!(
search.pi[block_id] == 1 && !go_right) && !(
search.pi[block_id] ==
search.blocks() && go_right)
449 && max_error_left_in_block > 0 && error_left.total > 0 && error_left.deletion > 0
450 && ((go_right && cur.extend_right()) || (!go_right && cur.extend_left())))
452 search_param error_left2{error_left};
454 error_left2.deletion--;
457 if (search_ss_deletion<abort_on_hit>(cur,
473 while ((go_right && cur.cycle_back()) || (!go_right && cur.cycle_front()));
486template <
bool abort_on_hit,
490 typename blocks_length_t,
492inline bool search_ss_children(cursor_t cur,
494 typename cursor_t::size_type
const lb,
495 typename cursor_t::size_type
const rb,
496 uint8_t
const errors_spent,
497 uint8_t
const block_id,
499 uint8_t
const min_error_left_in_block,
500 search_t
const & search,
501 blocks_length_t
const & blocks_length,
502 search_param
const error_left,
503 delegate_t && delegate)
505 using size_type =
typename cursor_t::size_type;
506 if ((go_right && cur.extend_right()) || (!go_right && cur.extend_left()))
508 size_type
const chars_left = blocks_length[block_id] - (rb - lb - 1);
510 size_type lb2 = lb - !go_right;
511 size_type rb2 = rb + go_right;
515 bool const delta = cur.last_rank() !=
to_rank(query[(go_right ? rb : lb) - 1]);
521 if (error_left.deletion == 0 && chars_left + delta < min_error_left_in_block + 1u)
524 if (!delta || error_left.substitution > 0)
526 search_param error_left2{error_left};
527 error_left2.total -= delta;
528 error_left2.substitution -= delta;
531 if (rb - lb == blocks_length[block_id])
535 if (error_left.deletion > 0)
537 if (search_ss_deletion<abort_on_hit>(cur,
541 errors_spent + delta,
555 uint8_t
const block_id2 = std::min<uint8_t>(block_id + 1,
search.blocks() - 1);
556 bool const go_right2 = block_id2 == 0 ? true :
search.pi[block_id2] >
search.pi[block_id2 - 1];
558 if (search_ss<abort_on_hit>(cur,
562 errors_spent + delta,
577 if (search_ss<abort_on_hit>(cur,
581 errors_spent + delta,
599 if (error_left.deletion > 0 && !(go_right && (rb == 1 || rb == std::ranges::size(query) + 1))
600 && !(!go_right && (lb == 0 || lb == std::ranges::size(query))))
602 search_param error_left3{error_left};
604 error_left3.deletion--;
605 search_ss<abort_on_hit>(cur,
618 while ((go_right && cur.cycle_back()) || (!go_right && cur.cycle_front()));
628template <
bool abort_on_hit,
632 typename blocks_length_t,
634inline bool search_ss(cursor_t cur,
636 typename cursor_t::size_type
const lb,
637 typename cursor_t::size_type
const rb,
638 uint8_t
const errors_spent,
639 uint8_t
const block_id,
641 search_t
const & search,
642 blocks_length_t
const & blocks_length,
643 search_param
const error_left,
644 delegate_t && delegate)
646 uint8_t
const max_error_left_in_block =
search.u[block_id] - errors_spent;
647 uint8_t
const min_error_left_in_block =
std::max(
search.l[block_id] - errors_spent, 0);
650 if (min_error_left_in_block == 0 && lb == 0 && rb == std::ranges::size(query) + 1)
656 else if (((max_error_left_in_block == 0) && (rb - lb - 1 != blocks_length[block_id]))
657 || (error_left.total == 0 && min_error_left_in_block == 0))
659 if (search_ss_exact<abort_on_hit>(cur,
677 else if (error_left.total > 0)
680 if (error_left.insertion > 0)
682 using size_type =
typename cursor_t::size_type;
684 size_type
const lb2 = lb - !go_right;
685 size_type
const rb2 = rb + go_right;
687 search_param error_left2{error_left};
689 error_left2.insertion--;
691 if (rb - lb == blocks_length[block_id])
698 if (search_ss_deletion<abort_on_hit>(cur,
716 if (search_ss<abort_on_hit>(cur,
733 if (search_ss_children<abort_on_hit>(cur,
740 min_error_left_in_block,
776template <
bool abort_on_hit,
typename index_t,
typename query_t,
typename search_scheme_t,
typename delegate_t>
777inline void search_ss(index_t
const & index,
779 search_param
const error_left,
780 search_scheme_t
const & search_scheme,
781 delegate_t && delegate)
784 auto const block_info = search_scheme_block_info(search_scheme, std::ranges::size(query));
786 for (uint8_t search_id = 0; search_id < search_scheme.size(); ++search_id)
788 auto const &
search = search_scheme[search_id];
789 auto const & [blocks_length, start_pos] = block_info[search_id];
791 bool const hit = search_ss<abort_on_hit>(index.cursor(),
805 if (abort_on_hit && hit)
828template <
typename configuration_t,
typename index_t,
typename... policies_t>
829 requires (template_specialisation_of<typename index_t::cursor_type, bi_fm_index_cursor>)
830template <bool abort_on_hit, typename query_t, typename delegate_t>
831inline void search_scheme_algorithm<configuration_t, index_t, policies_t...>::search_algo_bi(
833 search_param
const error_left,
834 delegate_t && delegate)
836 switch (error_left.total)
839 search_ss<abort_on_hit>(*index_ptr, query, error_left, optimum_search_scheme<0, 0>, delegate);
842 search_ss<abort_on_hit>(*index_ptr, query, error_left, optimum_search_scheme<0, 1>, delegate);
845 search_ss<abort_on_hit>(*index_ptr, query, error_left, optimum_search_scheme<0, 2>, delegate);
848 search_ss<abort_on_hit>(*index_ptr, query, error_left, optimum_search_scheme<0, 3>, delegate);
851 auto const & search_scheme{compute_ss(0, error_left.total)};
852 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 alphabet/concept.hpp:152
constexpr auto slice
A view adaptor that returns a half-open interval on the underlying range.
Definition slice.hpp:175
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.