19#include <sdsl/suffix_trees.hpp>
49 return lhs.begin_position == rhs.begin_position && lhs.end_position == rhs.end_position;
85template <
typename index_t>
103 using node_type = detail::fm_index_cursor_node<index_t>;
105 using sdsl_char_type =
typename index_type::sdsl_char_type;
107 using sdsl_index_type =
typename index_t::sdsl_index_type;
109 using sdsl_sigma_type =
typename index_type::sdsl_sigma_type;
111 using index_alphabet_type =
typename index_t::alphabet_type;
127 sdsl_sigma_type sigma{};
129 template <
typename _index_t>
130 friend class bi_fm_index_cursor;
141 backward_search(sdsl_index_type
const & csa, sdsl_char_type
const c,
size_type & l,
size_type & r)
const noexcept
143 assert(l <= r && r < csa.size());
148 if constexpr (!std::same_as<index_alphabet_type, sdsl::plain_byte_alphabet>)
150 cc = csa.char2comp[c];
151 if (cc == 0 && c > 0)
156 if (l == 0 && r + 1 == csa.size())
159 _r = csa.C[cc + 1] - 1;
164 _l = c_begin + csa.bwt.rank(l, c);
165 _r = c_begin + csa.bwt.rank(r + 1, c) - 1;
172 assert(r + 1 - l >= 0);
195 node({0, _index.index.size() - 1, 0, 0}),
196 sigma(_index.index.sigma - index_t::text_layout_mode)
198 assert(_index.index.size() != 0);
216 assert(index !=
nullptr);
217 assert(node != rhs.node || (
query_length() == 0 || (parent_lb == rhs.parent_lb && parent_rb == rhs.parent_rb)));
221 return node == rhs.node;
238 assert(index !=
nullptr);
240 return !(*
this == rhs);
264 assert(index !=
nullptr);
266 sdsl_char_type c = 1;
268 while (c < sigma && !backward_search(index->index, index->index.comp2char[c], _lb, _rb))
277 node = {_lb, _rb, node.depth + 1, c};
296 template <
typename char_t>
297 requires std::convertible_to<char_t, index_alphabet_type>
bool
300 assert(index !=
nullptr);
308 sdsl_char_type c_char =
seqan3::to_rank(
static_cast<index_alphabet_type
>(c)) + 1;
310 if (backward_search(index->index, c_char, _lb, _rb))
314 node = {_lb, _rb, node.depth + 1, c_char};
321 template <
typename char_type>
322 requires detail::is_char_adaptation_v<char_type>
bool
344 template <std::ranges::range seq_t>
347 static_assert(std::ranges::forward_range<seq_t>,
"The query must model forward_range.");
348 static_assert(std::convertible_to<range_innermost_value_t<seq_t>, index_alphabet_type>,
349 "The alphabet of the sequence must be convertible to the alphabet of the index.");
351 assert(index !=
nullptr);
354 size_type new_parent_lb = parent_lb, new_parent_rb = parent_rb;
370 if (!backward_search(index->index, c, _lb, _rb))
374 parent_lb = new_parent_lb;
375 parent_rb = new_parent_rb;
376 node = {_lb, _rb, len + node.depth, c};
410 assert(parent_lb <= parent_rb);
412 sdsl_char_type c = node.last_char + 1;
413 size_type _lb = parent_lb, _rb = parent_rb;
415 while (c < sigma && !backward_search(index->index, index->index.comp2char[c], _lb, _rb))
422 node = {_lb, _rb, node.depth, c};
446 assert(index !=
nullptr &&
query_length() > 0 && parent_lb <= parent_rb);
448 return index->index.comp2char[node.last_char] - 1;
468 assert(index !=
nullptr);
470 return {node.lb, node.rb + 1};
493 assert(index !=
nullptr);
494 assert(node.depth != 0 || (node.lb == 0 && node.rb == index->size() - 1));
516 template <std::ranges::range text_t>
520 static_assert(std::ranges::input_range<text_t>,
"The text must model input_range.");
521 static_assert(range_dimension_v<text_t> == 1,
"The input cannot be a text collection.");
522 static_assert(std::same_as<range_innermost_value_t<text_t>, index_alphabet_type>,
523 "The alphabet types of the given text and index differ.");
524 assert(index !=
nullptr);
526 size_type const query_begin = offset() - index->index[node.lb];
531 template <std::ranges::range text_t>
535 static_assert(std::ranges::input_range<text_t>,
"The text collection must model input_range.");
536 static_assert(range_dimension_v<text_t> == 2,
"The input must be a text collection.");
537 static_assert(std::same_as<range_innermost_value_t<text_t>, index_alphabet_type>,
538 "The alphabet types of the given text and index differ.");
539 assert(index !=
nullptr);
542 size_type const location = offset() - index->index[node.lb];
546 size_type const rank = index->text_begin_rs.rank(location + 1);
551 size_type const start_location = index->text_begin_ss.select(rank);
553 size_type const query_begin = location - start_location;
572 assert(index !=
nullptr);
574 return 1 + node.rb - node.lb;
591 assert(index !=
nullptr);
597 occ.emplace_back(0, offset() - index->index[node.lb + i]);
607 assert(index !=
nullptr);
613 size_type loc = offset() - index->index[node.lb + i];
614 size_type sequence_rank = index->text_begin_rs.rank(loc + 1);
615 size_type sequence_position = loc - index->text_begin_ss.select(sequence_rank);
636 assert(index !=
nullptr);
638 return std::views::iota(node.lb, node.lb +
count())
640 [*
this, _offset = offset()](
auto sa_pos)
650 assert(index !=
nullptr);
652 return std::views::iota(node.lb, node.lb +
count())
654 [*
this, _offset = offset()](
auto sa_pos)
656 auto loc = _offset - index->index[sa_pos];
657 size_type sequence_rank = index->text_begin_rs.rank(loc + 1);
658 size_type sequence_position = loc - index->text_begin_ss.select(sequence_rank);
670 template <cereal_archive archive_t>
671 void CEREAL_SERIALIZE_FUNCTION_NAME(archive_t & archive)
Core alphabet concept and free function/type trait wrappers.
Provides alphabet adaptations for standard char types.
The SeqAn FM Index Cursor.
Definition: fm_index_cursor.hpp:87
bool extend_right(seq_t &&seq) noexcept
Tries to extend the query by seq to the right.
Definition: fm_index_cursor.hpp:345
auto path_label(text_t &&text) const noexcept
Returns the searched query.
Definition: fm_index_cursor.hpp:517
bool cycle_back() noexcept
Tries to replace the rightmost character of the query by the next lexicographically larger character ...
Definition: fm_index_cursor.hpp:406
bool operator!=(fm_index_cursor const &rhs) const noexcept
Compares two cursors.
Definition: fm_index_cursor.hpp:236
seqan3::suffix_array_interval suffix_array_interval() const noexcept
Returns the half-open suffix array interval.
Definition: fm_index_cursor.hpp:466
locate_result_type locate() const
Locates the occurrences of the searched query in the text.
Definition: fm_index_cursor.hpp:588
auto lazy_locate() const
This is an overloaded member function, provided for convenience. It differs from the above function o...
Definition: fm_index_cursor.hpp:647
bool operator==(fm_index_cursor const &rhs) const noexcept
Compares two cursors.
Definition: fm_index_cursor.hpp:214
size_type count() const noexcept
Counts the number of occurrences of the searched query in the text.
Definition: fm_index_cursor.hpp:570
size_type last_rank() const noexcept
Outputs the rightmost rank.
Definition: fm_index_cursor.hpp:443
bool extend_right() noexcept
Tries to extend the query by the smallest possible character to the right such that the query is foun...
Definition: fm_index_cursor.hpp:260
bool extend_right(char_type const *cstring) noexcept
This is an overloaded member function, provided for convenience. It differs from the above function o...
Definition: fm_index_cursor.hpp:323
locate_result_type locate() const
This is an overloaded member function, provided for convenience. It differs from the above function o...
Definition: fm_index_cursor.hpp:604
auto path_label(text_t &&text) const noexcept
This is an overloaded member function, provided for convenience. It differs from the above function o...
Definition: fm_index_cursor.hpp:532
size_type query_length() const noexcept
Returns the length of the searched query. .
Definition: fm_index_cursor.hpp:491
index_t index_type
Type of the index.
Definition: fm_index_cursor.hpp:93
typename index_type::size_type size_type
Type for representing positions in the indexed text.
Definition: fm_index_cursor.hpp:95
auto lazy_locate() const
Locates the occurrences of the searched query in the text on demand, i.e. a std::ranges::view is retu...
Definition: fm_index_cursor.hpp:633
bool extend_right(char_t const c) noexcept
Tries to extend the query by the character c to the right.
Definition: fm_index_cursor.hpp:298
fm_index_cursor() noexcept=default
Default constructor. Accessing member functions on a default constructed object is undefined behavior...
Provides various transformation traits used by the range module.
Provides the internal representation of a node of the seqan3::fm_index_cursor.
T emplace_back(T... args)
constexpr auto to_rank
Return the rank representation of a (semi-)alphabet object.
Definition: concept.hpp:155
@ seq
The "sequence", usually a range of nucleotides or amino acids.
text_layout
The possible text layouts (single, collection) the seqan3::fm_index and seqan3::bi_fm_index can suppo...
Definition: concept.hpp:91
@ single
The text is a single range.
Definition: concept.hpp:93
@ collection
The text is a range of ranges.
Definition: concept.hpp:95
decltype(detail::transform< trait_t >(list_t{})) transform
Apply a transformation trait to every type in the list and return a seqan3::type_list of the results.
Definition: traits.hpp:470
constexpr auto slice
A view adaptor that returns a half-open interval on the underlying range.
Definition: slice.hpp:178
The main SeqAn3 namespace.
Definition: aligned_sequence_concept.hpp:29
Provides the concept for seqan3::detail::sdsl_index.
Provides seqan3::views::slice.
The underlying suffix array interval.
Definition: fm_index_cursor.hpp:33
size_t end_position
The exclusive end position of the interval ("right boundary").
Definition: fm_index_cursor.hpp:37
size_t begin_position
The begin position of the interval ("left boundary").
Definition: fm_index_cursor.hpp:35
friend bool operator==(suffix_array_interval const &lhs, suffix_array_interval const &rhs) noexcept
Test for equality.
Definition: fm_index_cursor.hpp:47
friend bool operator!=(suffix_array_interval const &lhs, suffix_array_interval const &rhs) noexcept
Test for inequality.
Definition: fm_index_cursor.hpp:57