17 #include <type_traits>
19 #include <sdsl/suffix_trees.hpp>
55 template <
typename index_t>
72 using node_type = detail::fm_index_cursor_node<index_t>;
75 using sdsl_char_type =
typename index_type::sdsl_char_type;
77 using sdsl_index_type =
typename index_t::sdsl_index_type;
79 using sdsl_sigma_type =
typename index_type::sdsl_sigma_type;
81 using index_alphabet_type =
typename index_t::alphabet_type;
97 sdsl_sigma_type sigma{};
99 template <
typename _index_t>
100 friend class bi_fm_index_cursor;
110 bool backward_search(sdsl_index_type
const & csa,
111 sdsl_char_type
const c,
115 assert(l <= r && r < csa.size());
120 if constexpr(!std::same_as<index_alphabet_type, sdsl::plain_byte_alphabet>)
122 cc = csa.char2comp[c];
123 if (cc == 0 && c > 0)
128 if (l == 0 && r + 1 == csa.size())
131 _r = csa.C[cc + 1] - 1;
136 _l = c_begin + csa.bwt.rank(l, c);
137 _r = c_begin + csa.bwt.rank(r + 1, c) - 1;
144 assert(r + 1 - l >= 0);
168 node({0, _index.index.size() - 1, 0, 0}),
169 sigma(_index.index.sigma - index_t::text_layout_mode)
187 assert(index !=
nullptr);
188 assert(node != rhs.node || (
query_length() == 0 || (parent_lb == rhs.parent_lb && parent_rb == rhs.parent_rb)));
192 return node == rhs.node;
209 assert(index !=
nullptr);
211 return !(*
this == rhs);
235 assert(index !=
nullptr);
237 sdsl_char_type c = 1;
239 while (c < sigma && !backward_search(index->index, index->index.comp2char[c], _lb, _rb))
248 node = {_lb, _rb, node.depth + 1, c};
267 template <
typename char_t>
269 requires std::convertible_to<char_t, index_alphabet_type>
273 assert(index !=
nullptr);
281 sdsl_char_type c_char =
seqan3::to_rank(
static_cast<index_alphabet_type
>(c)) + 1;
283 if (backward_search(index->index, c_char, _lb, _rb))
287 node = {_lb, _rb, node.depth + 1, c_char};
294 template <
typename char_type>
296 requires detail::is_char_adaptation_v<char_type>
319 template <std::ranges::range seq_t>
322 static_assert(std::ranges::forward_range<seq_t>,
"The query must model forward_range.");
324 "The alphabet of the sequence must be convertible to the alphabet of the index.");
326 assert(index !=
nullptr);
329 size_type new_parent_lb = parent_lb, new_parent_rb = parent_rb;
334 for (
auto it = std::ranges::begin(
seq); it != std::ranges::end(
seq); ++len, ++it)
345 if (!backward_search(index->index, c, _lb, _rb))
349 parent_lb = new_parent_lb;
350 parent_rb = new_parent_rb;
351 node = {_lb, _rb, len + node.depth, c};
385 assert(parent_lb <= parent_rb);
387 sdsl_char_type c = node.last_char + 1;
388 size_type _lb = parent_lb, _rb = parent_rb;
390 while (c < sigma && !backward_search(index->index, index->index.comp2char[c], _lb, _rb))
397 node = {_lb, _rb, node.depth, c};
421 assert(index !=
nullptr &&
query_length() > 0 && parent_lb <= parent_rb);
423 return index->index.comp2char[node.last_char] - 1;
442 assert(index !=
nullptr);
443 assert(node.depth != 0 || (node.lb == 0 && node.rb == index->size() - 1));
465 template <std::ranges::range text_t>
471 static_assert(std::ranges::input_range<text_t>,
"The text must model input_range.");
472 static_assert(range_dimension_v<text_t> == 1,
"The input cannot be a text collection.");
474 "The alphabet types of the given text and index differ.");
475 assert(index !=
nullptr);
477 size_type const query_begin = offset() - index->index[node.lb];
482 template <std::ranges::range text_t>
488 static_assert(std::ranges::input_range<text_t>,
"The text collection must model input_range.");
489 static_assert(range_dimension_v<text_t> == 2,
"The input must be a text collection.");
491 "The alphabet types of the given text and index differ.");
492 assert(index !=
nullptr);
495 size_type const location = offset() - index->index[node.lb];
499 size_type const rank = index->text_begin_rs.rank(location + 1);
504 size_type const start_location = index->text_begin_ss.select(rank);
506 size_type const query_begin = location - start_location;
525 assert(index !=
nullptr);
527 return 1 + node.rb - node.lb;
546 assert(index !=
nullptr);
552 occ.emplace_back(0, offset() - index->index[node.lb + i]);
564 assert(index !=
nullptr);
570 size_type loc = offset() - index->index[node.lb + i];
571 size_type sequence_rank = index->text_begin_rs.rank(loc + 1);
572 size_type sequence_position = loc - index->text_begin_ss.select(sequence_rank);
595 assert(index !=
nullptr);
597 return std::views::iota(node.lb, node.lb +
count())
610 assert(index !=
nullptr);
612 return std::views::iota(node.lb, node.lb +
count())
615 return _offset - index->index[sa_pos];
619 size_type sequence_rank = index->text_begin_rs.rank(loc + 1);
620 size_type sequence_position = loc - index->text_begin_ss.select(sequence_rank);