15 #include <type_traits>
24 namespace seqan3::detail
70 template <
typename search_scheme_t>
71 inline auto search_scheme_block_info(search_scheme_t
const & search_scheme,
size_t const query_length)
73 using blocks_length_type =
typename search_scheme_t::value_type::blocks_length_type;
81 transformation_trait_or_t<std::tuple_size<search_scheme_t>,
85 if constexpr (is_dyn_scheme)
86 result.resize(search_scheme.size());
88 uint8_t
const blocks {search_scheme[0].blocks()};
89 size_t const block_length{query_length / blocks};
90 uint8_t
const rest {static_cast<uint8_t>(query_length % blocks)};
92 blocks_length_type blocks_length;
95 if constexpr (is_dyn_scheme)
96 blocks_length.resize(blocks, block_length);
98 blocks_length.fill(block_length);
100 for (uint8_t block_id = 0; block_id < rest; ++block_id)
101 ++blocks_length[block_id];
103 for (uint8_t search_id = 0; search_id < search_scheme.size(); ++search_id)
105 auto const &
search = search_scheme[search_id];
107 auto & [search_blocks_length, start_pos] = result[search_id];
111 if constexpr (is_dyn_scheme)
112 search_blocks_length.resize(blocks);
113 search_blocks_length[0] = blocks_length[
search.pi[0] - 1];
114 for (uint8_t i = 1; i < blocks; ++i)
116 search_blocks_length[i] = blocks_length[
search.pi[i] - 1] + search_blocks_length[i - 1];
118 start_pos += search_blocks_length[i] - search_blocks_length[i - 1];
127 template <
bool abort_on_hit,
typename cursor_t,
typename query_t,
typename search_t,
typename blocks_length_t,
129 inline bool search_ss(cursor_t cur, query_t & query,
130 typename cursor_t::size_type
const lb,
typename cursor_t::size_type
const rb,
131 uint8_t
const errors_spent, uint8_t
const block_id,
bool const go_right, search_t
const &
search,
132 blocks_length_t
const & blocks_length, search_param
const error_left, delegate_t && delegate);
165 template <
bool abort_on_hit,
typename cursor_t,
typename query_t,
typename search_t,
typename blocks_length_t,
167 inline bool search_ss_exact(cursor_t cur, query_t & query,
168 typename cursor_t::size_type
const lb,
typename cursor_t::size_type
const rb,
169 uint8_t
const errors_spent, uint8_t
const block_id,
bool const go_right,
170 search_t
const &
search, blocks_length_t
const & blocks_length,
171 search_param
const error_left, delegate_t && delegate)
173 using size_type =
typename cursor_t::size_type;
175 uint8_t
const block_id2 = std::min<uint8_t>(block_id + 1,
search.blocks() - 1);
176 bool const go_right2 = (block_id <
search.blocks() - 1) && (
search.pi[block_id + 1] >
search.pi[block_id]);
180 size_type
const infix_lb = rb - 1;
181 size_type
const infix_rb = lb + blocks_length[block_id] - 1;
183 if (!cur.extend_right(query |
views::slice(infix_lb, infix_rb + 1)))
186 if (search_ss<abort_on_hit>(cur, query, lb, infix_rb + 2, errors_spent, block_id2, go_right2,
search,
187 blocks_length, error_left, delegate) && abort_on_hit)
194 size_type
const infix_lb = rb - blocks_length[block_id] - 1;
195 size_type
const infix_rb = lb - 1;
197 if (!cur.extend_left(query |
views::slice(infix_lb, infix_rb + 1)))
200 if (search_ss<abort_on_hit>(cur, query, infix_lb, rb, errors_spent, block_id2, go_right2,
search, blocks_length,
201 error_left, delegate) && abort_on_hit)
214 template <
bool abort_on_hit,
typename cursor_t,
typename query_t,
typename search_t,
typename blocks_length_t,
216 inline bool search_ss_deletion(cursor_t cur, query_t & query,
217 typename cursor_t::size_type
const lb,
typename cursor_t::size_type
const rb,
218 uint8_t
const errors_spent, uint8_t
const block_id,
bool const go_right,
219 search_t
const &
search, blocks_length_t
const & blocks_length,
220 search_param
const error_left, delegate_t && delegate)
222 uint8_t
const max_error_left_in_block =
search.u[block_id] - errors_spent;
223 uint8_t
const min_error_left_in_block =
std::max(
search.l[block_id] - errors_spent, 0);
226 if (min_error_left_in_block == 0)
228 uint8_t
const block_id2 = std::min<uint8_t>(block_id + 1,
search.blocks() - 1);
229 bool const go_right2 =
search.pi[block_id2] >
search.pi[block_id2 - 1];
231 if (search_ss<abort_on_hit>(cur, query, lb, rb, errors_spent, block_id2, go_right2,
search, blocks_length,
232 error_left, delegate) && abort_on_hit)
241 if (!(
search.pi[block_id] == 1 && !go_right) &&
242 !(
search.pi[block_id] ==
search.blocks() && go_right) &&
243 max_error_left_in_block > 0 && error_left.total > 0 && error_left.deletion > 0 &&
244 ((go_right && cur.extend_right()) || (!go_right && cur.extend_left())))
246 search_param error_left2{error_left};
248 error_left2.deletion--;
251 if (search_ss_deletion<abort_on_hit>(cur, query, lb, rb, errors_spent + 1, block_id, go_right,
search,
252 blocks_length, error_left2, delegate) && abort_on_hit)
256 }
while ((go_right && cur.cycle_back()) || (!go_right && cur.cycle_front()));
268 template <
bool abort_on_hit,
typename cursor_t,
typename query_t,
typename search_t,
typename blocks_length_t,
270 inline bool search_ss_children(cursor_t cur, query_t & query,
271 typename cursor_t::size_type
const lb,
typename cursor_t::size_type
const rb,
272 uint8_t
const errors_spent, uint8_t
const block_id,
bool const go_right,
273 uint8_t
const min_error_left_in_block, search_t
const &
search,
274 blocks_length_t
const & blocks_length, search_param
const error_left,
275 delegate_t && delegate)
277 using size_type =
typename cursor_t::size_type;
278 if ((go_right && cur.extend_right()) || (!go_right && cur.extend_left()))
280 size_type
const chars_left = blocks_length[block_id] - (rb - lb - 1);
282 size_type lb2 = lb - !go_right;
283 size_type rb2 = rb + go_right;
287 bool const delta = cur.last_rank() !=
to_rank(query[(go_right ? rb : lb) - 1]);
293 if (error_left.deletion == 0 && chars_left + delta < min_error_left_in_block + 1u)
296 if (!delta || error_left.substitution > 0)
298 search_param error_left2{error_left};
299 error_left2.total -= delta;
300 error_left2.substitution -= delta;
303 if (rb - lb == blocks_length[block_id])
307 if (error_left.deletion > 0)
309 if (search_ss_deletion<abort_on_hit>(cur, query, lb2, rb2, errors_spent + delta, block_id,
310 go_right,
search, blocks_length, error_left2, delegate) &&
318 uint8_t
const block_id2 = std::min<uint8_t>(block_id + 1,
search.blocks() - 1);
319 bool const go_right2 =
search.pi[block_id2] >
search.pi[block_id2 - 1];
321 if (search_ss<abort_on_hit>(cur, query, lb2, rb2, errors_spent + delta, block_id2, go_right2,
322 search, blocks_length, error_left2, delegate) &&
331 if (search_ss<abort_on_hit>(cur, query, lb2, rb2, errors_spent + delta, block_id, go_right,
search,
332 blocks_length, error_left2, delegate) && abort_on_hit)
343 if (error_left.deletion > 0 &&
347 search_param error_left3{error_left};
349 error_left3.deletion--;
350 search_ss<abort_on_hit>(cur, query, lb, rb, errors_spent + 1, block_id, go_right,
search, blocks_length,
351 error_left3, delegate);
353 }
while ((go_right && cur.cycle_back()) || (!go_right && cur.cycle_front()));
362 template <
bool abort_on_hit,
typename cursor_t,
typename query_t,
typename search_t,
363 typename blocks_length_t,
typename delegate_t>
364 inline bool search_ss(cursor_t cur, query_t & query,
365 typename cursor_t::size_type
const lb,
typename cursor_t::size_type
const rb,
366 uint8_t
const errors_spent, uint8_t
const block_id,
bool const go_right, search_t
const &
search,
367 blocks_length_t
const & blocks_length, search_param
const error_left, delegate_t && delegate)
369 uint8_t
const max_error_left_in_block =
search.u[block_id] - errors_spent;
370 uint8_t
const min_error_left_in_block =
std::max(
search.l[block_id] - errors_spent, 0);
373 if (min_error_left_in_block == 0 && lb == 0 && rb ==
std::ranges::size(query) + 1)
379 else if (((max_error_left_in_block == 0) && (rb - lb - 1 != blocks_length[block_id])) ||
380 (error_left.total == 0 && min_error_left_in_block == 0))
382 if (search_ss_exact<abort_on_hit>(cur, query, lb, rb, errors_spent, block_id, go_right,
search, blocks_length,
383 error_left, delegate) && abort_on_hit)
390 else if (error_left.total > 0)
393 if (error_left.insertion > 0)
395 using size_type =
typename cursor_t::size_type;
397 size_type
const lb2 = lb - !go_right;
398 size_type
const rb2 = rb + go_right;
400 search_param error_left2{error_left};
402 error_left2.insertion--;
404 if (rb - lb == blocks_length[block_id])
411 if (search_ss_deletion<abort_on_hit>(cur, query, lb2, rb2, errors_spent + 1, block_id, go_right,
search,
412 blocks_length, error_left2, delegate) && abort_on_hit)
419 if (search_ss<abort_on_hit>(cur, query, lb2, rb2, errors_spent + 1, block_id, go_right,
search,
420 blocks_length, error_left2, delegate) && abort_on_hit)
426 if (search_ss_children<abort_on_hit>(cur, query, lb, rb, errors_spent, block_id, go_right,
427 min_error_left_in_block,
search, blocks_length, error_left, delegate) &&
457 template <
bool abort_on_hit,
typename index_t,
typename query_t,
typename search_scheme_t,
typename delegate_t>
458 inline void search_ss(index_t
const & index, query_t & query, search_param
const error_left,
459 search_scheme_t
const & search_scheme, delegate_t && delegate)
462 auto const block_info = search_scheme_block_info(search_scheme,
std::ranges::size(query));
464 for (uint8_t search_id = 0; search_id < search_scheme.size(); ++search_id)
466 auto const &
search = search_scheme[search_id];
467 auto const & [blocks_length, start_pos] = block_info[search_id];
469 bool const hit = search_ss<abort_on_hit>(
472 start_pos, start_pos + 1,
482 if (abort_on_hit && hit)
506 template <
bool abort_on_hit,
typename index_t,
typename query_t,
typename delegate_t>
507 inline void search_algo_bi(index_t
const & index, query_t & query, search_param
const error_left,
508 delegate_t && delegate)
510 switch (error_left.total)
513 search_ss<abort_on_hit>(index, query, error_left, optimum_search_scheme<0, 0>, delegate);
516 search_ss<abort_on_hit>(index, query, error_left, optimum_search_scheme<0, 1>, delegate);
519 search_ss<abort_on_hit>(index, query, error_left, optimum_search_scheme<0, 2>, delegate);
522 search_ss<abort_on_hit>(index, query, error_left, optimum_search_scheme<0, 3>, delegate);
525 auto const & search_scheme{compute_ss(0, error_left.total)};
526 search_ss<abort_on_hit>(index, query, error_left, search_scheme, delegate);
535 template <
bool abort_on_hit,
typename index_t,
typename query_t,
typename delegate_t>
536 inline void search_algo_uni(index_t
const & index, query_t & query, search_param
const error_left,
537 delegate_t && delegate)
539 search_trivial<abort_on_hit>(index, query, error_left, delegate);
546 template <
bool abort_on_hit,
typename index_t,
typename query_t,
typename delegate_t>
547 inline void search_algo(index_t
const & index, query_t & query, search_param
const error_left, delegate_t && delegate)
550 search_algo_bi<abort_on_hit>(index, query, error_left, delegate);
552 search_algo_uni<abort_on_hit>(index, query, error_left, delegate);