16 #include <type_traits>
18 #include <sdsl/suffix_trees.hpp>
20 #include <range/v3/view/slice.hpp>
58 template <
typename index_t>
78 using node_type = detail::fm_index_cursor_node<index_t>;
81 using sdsl_char_type =
typename index_type::sdsl_char_type;
83 using sdsl_sigma_type =
typename index_type::sdsl_sigma_type;
85 using index_alphabet_type =
typename index_t::alphabet_type;
97 sdsl_sigma_type sigma;
99 template <
typename _index_t>
110 template <detail::sdsl_index csa_t>
111 bool backward_search(csa_t
const & csa, sdsl_char_type
const c,
size_type & l,
size_type & r)
const noexcept
113 assert(l <= r && r < csa.size());
120 cc = csa.char2comp[c];
121 if (cc == 0 && c > 0)
126 if (l == 0 && r + 1 == csa.size())
129 _r = csa.C[cc + 1] - 1;
134 _l = c_begin + csa.bwt.rank(l, c);
135 _r = c_begin + csa.bwt.rank(r + 1, c) - 1;
142 assert(r + 1 - l >= 0);
164 fm_index_cursor(index_t const & _index) noexcept : index(&_index), node({0, _index.index.size() - 1, 0, 0}),
165 sigma(_index.index.sigma - index_t::text_layout_mode)
183 assert(index !=
nullptr);
184 assert(node != rhs.node || (
query_length() == 0 || (parent_lb == rhs.parent_lb && parent_rb == rhs.parent_rb)));
188 return node == rhs.node;
205 assert(index !=
nullptr);
207 return !(*
this == rhs);
231 assert(index !=
nullptr);
233 sdsl_char_type c = 1;
235 while (c < sigma && !backward_search(index->index, index->index.comp2char[c], _lb, _rb))
244 node = {_lb, _rb, node.depth + 1, c};
263 template <
typename char_t>
267 "The character must be convertible to the alphabet of the index.");
269 assert(index !=
nullptr);
273 sdsl_char_type c_char =
to_rank(static_cast<index_alphabet_type>(c)) + 1;
275 if (backward_search(index->index, c_char, _lb, _rb))
279 node = {_lb, _rb, node.depth + 1, c_char};
301 template <std::ranges::range seq_t>
304 static_assert(std::ranges::forward_range<seq_t>,
"The query must model forward_range.");
306 "The alphabet of the sequence must be convertible to the alphabet of the index.");
308 assert(index !=
nullptr);
311 size_type new_parent_lb = parent_lb, new_parent_rb = parent_rb;
316 for (
auto it = std::ranges::begin(
seq); it != std::ranges::end(
seq); ++len, ++it)
318 c =
to_rank(static_cast<index_alphabet_type>(*it)) + 1;
322 if (!backward_search(index->index, c, _lb, _rb))
326 parent_lb = new_parent_lb;
327 parent_rb = new_parent_rb;
328 node = {_lb, _rb, len + node.depth, c};
362 assert(parent_lb <= parent_rb);
364 sdsl_char_type c = node.last_char + 1;
365 size_type _lb = parent_lb, _rb = parent_rb;
367 while (c < sigma && !backward_search(index->index, index->index.comp2char[c], _lb, _rb))
374 node = {_lb, _rb, node.depth, c};
398 assert(index !=
nullptr &&
query_length() > 0 && parent_lb <= parent_rb);
400 return index->index.comp2char[node.last_char] - 1;
419 assert(index !=
nullptr);
420 assert(node.depth != 0 || (node.lb == 0 && node.rb == index->size() - 1));
442 template <std::ranges::range text_t>
448 static_assert(std::ranges::input_range<text_t>,
"The text must model input_range.");
449 static_assert(dimension_v<text_t> == 1,
"The input cannot be a text collection.");
451 "The alphabet types of the given text and index differ.");
452 assert(index !=
nullptr);
454 size_type const query_begin = offset() - index->index[node.lb];
459 template <std::ranges::range text_t>
465 static_assert(std::ranges::input_range<text_t>,
"The text collection must model input_range.");
466 static_assert(dimension_v<text_t> == 2,
"The input must be a text collection.");
468 "The alphabet types of the given text and index differ.");
469 assert(index !=
nullptr);
471 size_type const loc = offset() - index->index[node.lb];
472 size_type const query_begin = loc - index->text_begin_rs.rank(loc + 1) + 1;
489 assert(index !=
nullptr);
491 return 1 + node.rb - node.lb;
510 assert(index !=
nullptr);
515 occ[i] = offset() - index->index[node.lb + i];
526 assert(index !=
nullptr);
532 size_type loc = offset() - index->index[node.lb + i];
533 size_type sequence_rank = index->text_begin_rs.rank(loc + 1);
534 size_type sequence_position = loc - index->text_begin_ss.select(sequence_rank);
557 assert(index !=
nullptr);
559 return std::views::iota(node.lb, node.lb +
count())
560 |
std::views::transform([*
this, _offset = offset()] (
auto sa_pos) {
return _offset - index->index[sa_pos]; });
569 assert(index !=
nullptr);
571 return std::views::iota(node.lb, node.lb +
count())
572 |
std::views::transform([*
this, _offset = offset()] (
auto sa_pos) {
return _offset - index->index[sa_pos]; })
575 size_type sequence_rank = index->text_begin_rs.rank(loc + 1);
576 size_type sequence_position = loc - index->text_begin_ss.select(sequence_rank);