16#include <sdsl/suffix_trees.hpp>
46 return lhs.begin_position == rhs.begin_position && lhs.end_position == rhs.end_position;
82template <
typename index_t>
126 template <
typename _index_t>
140 assert(l <= r && r < csa.size());
145 if constexpr (!std::same_as<index_alphabet_type, sdsl::plain_byte_alphabet>)
147 cc = csa.char2comp[c];
148 if (cc == 0 && c > 0)
153 if (l == 0 && r + 1 == csa.size())
156 _r = csa.C[cc + 1] - 1;
161 _l = c_begin + csa.bwt.rank(l, c);
162 _r = c_begin + csa.bwt.rank(r + 1, c) - 1;
169 assert(r + 1 - l >= 0);
192 node({0, _index.index.size() - 1, 0, 0}),
193 sigma(_index.index.sigma - index_t::text_layout_mode)
195 assert(_index.index.size() != 0);
213 assert(
index !=
nullptr);
218 return node == rhs.node;
235 assert(
index !=
nullptr);
237 return !(*
this == rhs);
261 assert(
index !=
nullptr);
293 template <
typename char_t>
294 requires std::convertible_to<char_t, index_alphabet_type>
bool
297 assert(
index !=
nullptr);
318 template <
typename char_type>
319 requires detail::is_char_adaptation_v<char_type>
bool
341 template <std::ranges::range seq_t>
344 static_assert(std::ranges::forward_range<seq_t>,
"The query must model forward_range.");
346 "The alphabet of the sequence must be convertible to the alphabet of the index.");
348 assert(
index !=
nullptr);
465 assert(
index !=
nullptr);
490 assert(
index !=
nullptr);
513 template <std::ranges::range text_t>
517 static_assert(std::ranges::input_range<text_t>,
"The text must model input_range.");
518 static_assert(range_dimension_v<text_t> == 1,
"The input cannot be a text collection.");
520 "The alphabet types of the given text and index differ.");
521 assert(
index !=
nullptr);
528 template <std::ranges::range text_t>
532 static_assert(std::ranges::input_range<text_t>,
"The text collection must model input_range.");
533 static_assert(range_dimension_v<text_t> == 2,
"The input must be a text collection.");
535 "The alphabet types of the given text and index differ.");
536 assert(
index !=
nullptr);
548 size_type const start_location =
index->text_begin_ss.select(rank);
550 size_type const query_begin = location - start_location;
569 assert(
index !=
nullptr);
588 assert(
index !=
nullptr);
604 assert(
index !=
nullptr);
612 size_type sequence_position = loc -
index->text_begin_ss.select(sequence_rank);
633 assert(
index !=
nullptr);
636 | std::views::transform(
637 [*
this, _offset =
offset()](
auto sa_pos)
647 assert(
index !=
nullptr);
650 | std::views::transform(
651 [*
this, _offset =
offset()](
auto sa_pos)
653 auto loc = _offset -
index->index[sa_pos];
655 size_type sequence_position = loc -
index->text_begin_ss.select(sequence_rank);
667 template <cereal_archive archive_t>
Core alphabet concept and free function/type trait wrappers.
Provides alphabet adaptations for standard char types.
The SeqAn Bidirectional FM Index Cursor.
Definition bi_fm_index_cursor.hpp:52
The SeqAn FM Index Cursor.
Definition fm_index_cursor.hpp:84
bool extend_right(seq_t &&seq) noexcept
Tries to extend the query by seq to the right.
Definition fm_index_cursor.hpp:342
auto path_label(text_t &&text) const noexcept
Returns the searched query.
Definition fm_index_cursor.hpp:514
bool cycle_back() noexcept
Tries to replace the rightmost character of the query by the next lexicographically larger character ...
Definition fm_index_cursor.hpp:403
size_type parent_rb
Right suffix array interval of the parent node. Needed for cycle_back().
Definition fm_index_cursor.hpp:120
bool operator!=(fm_index_cursor const &rhs) const noexcept
Compares two cursors.
Definition fm_index_cursor.hpp:233
bool backward_search(sdsl_index_type const &csa, sdsl_char_type const c, size_type &l, size_type &r) const noexcept
Optimized backward search without alphabet mapping.
Definition fm_index_cursor.hpp:138
seqan3::suffix_array_interval suffix_array_interval() const noexcept
Returns the half-open suffix array interval.
Definition fm_index_cursor.hpp:463
typename index_type::sdsl_char_type sdsl_char_type
Type of the representation of characters in the underlying SDSL index.
Definition fm_index_cursor.hpp:102
locate_result_type locate() const
Locates the occurrences of the searched query in the text.
Definition fm_index_cursor.hpp:585
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:644
bool operator==(fm_index_cursor const &rhs) const noexcept
Compares two cursors.
Definition fm_index_cursor.hpp:211
size_type count() const noexcept
Counts the number of occurrences of the searched query in the text.
Definition fm_index_cursor.hpp:567
size_type last_rank() const noexcept
Outputs the rightmost rank.
Definition fm_index_cursor.hpp:440
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:257
typename index_t::alphabet_type index_alphabet_type
Alphabet type of the index.
Definition fm_index_cursor.hpp:108
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:320
node_type node
Underlying index from the SDSL.
Definition fm_index_cursor.hpp:122
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:601
size_type offset() const noexcept
Helper function to recompute text positions since the indexed text is reversed.
Definition fm_index_cursor.hpp:130
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:529
size_type query_length() const noexcept
Returns the length of the searched query. Returns the depth of the cursor node in the implicit suffi...
Definition fm_index_cursor.hpp:488
index_t index_type
Type of the index.
Definition fm_index_cursor.hpp:90
typename index_type::size_type size_type
Type for representing positions in the indexed text.
Definition fm_index_cursor.hpp:92
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:630
typename index_type::sdsl_sigma_type sdsl_sigma_type
Type of the alphabet size in the underlying SDSL index.
Definition fm_index_cursor.hpp:106
typename index_t::sdsl_index_type sdsl_index_type
Type of the SDSL index.
Definition fm_index_cursor.hpp:104
sdsl_sigma_type sigma
Alphabet size of the index without delimiters.
Definition fm_index_cursor.hpp:124
size_type parent_lb
Left suffix array interval of the parent node. Needed for cycle_back().
Definition fm_index_cursor.hpp:118
index_type const * index
Underlying FM index.
Definition fm_index_cursor.hpp:116
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:295
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 alphabet/concept.hpp:152
@ 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 search/fm_index/concept.hpp:88
@ single
The text is a single range.
Definition search/fm_index/concept.hpp:90
@ collection
The text is a range of ranges.
Definition search/fm_index/concept.hpp:92
constexpr auto slice
A view adaptor that returns a half-open interval on the underlying range.
Definition slice.hpp:175
The main SeqAn3 namespace.
Definition aligned_sequence_concept.hpp:26
Provides the concept for seqan3::detail::sdsl_index.
Provides seqan3::views::slice.
Internal representation of the node of an FM index cursor.
Definition detail/fm_index_cursor.hpp:27
size_type rb
Right suffix array bound.
Definition detail/fm_index_cursor.hpp:38
sdsl_char_type last_char
Label of the last edge moved down. Needed for cycle_back().
Definition detail/fm_index_cursor.hpp:42
size_type depth
Depth of the node in the suffix tree, i.e. length of the searched query.
Definition detail/fm_index_cursor.hpp:40
size_type lb
Left suffix array bound.
Definition detail/fm_index_cursor.hpp:36
The underlying suffix array interval.
Definition fm_index_cursor.hpp:30
size_t end_position
The exclusive end position of the interval ("right boundary").
Definition fm_index_cursor.hpp:34
size_t begin_position
The begin position of the interval ("left boundary").
Definition fm_index_cursor.hpp:32
friend bool operator==(suffix_array_interval const &lhs, suffix_array_interval const &rhs) noexcept
Test for equality.
Definition fm_index_cursor.hpp:44
friend bool operator!=(suffix_array_interval const &lhs, suffix_array_interval const &rhs) noexcept
Test for inequality.
Definition fm_index_cursor.hpp:54