18#include <seqan3/contrib/sdsl-lite.hpp>
45 return lhs.begin_position ==
rhs.begin_position &&
lhs.end_position ==
rhs.end_position;
81template <
typename index_t>
99 using node_type = detail::fm_index_cursor_node<index_t>;
101 using sdsl_char_type =
typename index_type::sdsl_char_type;
103 using sdsl_index_type =
typename index_t::sdsl_index_type;
105 using sdsl_sigma_type =
typename index_type::sdsl_sigma_type;
107 using index_alphabet_type =
typename index_t::alphabet_type;
123 sdsl_sigma_type sigma{};
125 template <
typename _index_t>
126 friend class bi_fm_index_cursor;
137 backward_search(sdsl_index_type
const & csa, sdsl_char_type
const c,
size_type & l,
size_type & r)
const noexcept
139 assert(l <= r && r < csa.size());
144 if constexpr (!std::same_as<index_alphabet_type, seqan3::contrib::sdsl::plain_byte_alphabet>)
146 cc = csa.char2comp[c];
147 if (cc == 0 && c > 0)
152 if (l == 0 && r + 1 == csa.size())
155 _r = csa.C[cc + 1] - 1;
160 _l = c_begin + csa.bwt.rank(l, c);
161 _r = c_begin + csa.bwt.rank(r + 1, c) - 1;
168 assert(r + 1 - l >= 0);
191 node({0,
_index.index.size() - 1, 0, 0}),
192 sigma(
_index.index.sigma - index_t::text_layout_mode)
217 return node ==
rhs.node;
236 return !(*
this ==
rhs);
262 sdsl_sigma_type c = 1;
264 while (c < sigma && !backward_search(index->index, index->index.comp2char[c],
_lb,
_rb))
274 node = {
_lb,
_rb, node.depth + 1,
static_cast<sdsl_char_type
>(c)};
293 template <
typename char_t>
294 requires std::convertible_to<char_t, index_alphabet_type>
318 template <
typename char_type>
319 requires detail::is_char_adaptation_v<char_type>
341 template <std::ranges::range seq_t>
344 static_assert(std::ranges::forward_range<seq_t>,
"The query must model forward_range.");
345 static_assert(std::convertible_to<range_innermost_value_t<seq_t>, index_alphabet_type>,
346 "The alphabet of the sequence must be convertible to the alphabet of the index.");
367 if (!backward_search(index->index, c,
_lb,
_rb))
407 assert(parent_lb <= parent_rb);
409 sdsl_sigma_type c = node.last_char + 1;
412 while (c < sigma && !backward_search(index->index, index->index.comp2char[c],
_lb,
_rb))
420 node = {
_lb,
_rb, node.depth,
static_cast<sdsl_char_type
>(c)};
446 return index->index.comp2char[node.last_char] - 1;
468 return {node.lb, node.rb + 1};
492 assert(node.depth != 0 || (node.lb == 0 && node.rb == index->size() - 1));
514 template <std::ranges::range text_t>
518 static_assert(std::ranges::input_range<text_t>,
"The text must model input_range.");
520 static_assert(std::same_as<range_innermost_value_t<text_t>, index_alphabet_type>,
521 "The alphabet types of the given text and index differ.");
529 template <std::ranges::range text_t>
533 static_assert(std::ranges::input_range<text_t>,
"The text collection must model input_range.");
535 static_assert(std::same_as<range_innermost_value_t<text_t>, index_alphabet_type>,
536 "The alphabet types of the given text and index differ.");
572 return 1 + node.rb - node.lb;
595 occ.emplace_back(0, offset() - index->index[node.lb +
i]);
636 return std::views::iota(node.lb, node.lb +
count())
637 | std::views::transform(
650 return std::views::iota(node.lb, node.lb +
count())
651 | std::views::transform(
668 template <cereal_archive archive_t>
Core alphabet concept and free function/type trait wrappers.
Provides alphabet adaptations for standard char types.
A "pretty printer" for most SeqAn data structures and related types.
Definition debug_stream_type.hpp:79
The SeqAn FM Index Cursor.
Definition fm_index_cursor.hpp:83
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:515
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
bool operator!=(fm_index_cursor const &rhs) const noexcept
Compares two cursors.
Definition fm_index_cursor.hpp:232
seqan3::suffix_array_interval suffix_array_interval() const noexcept
Returns the half-open suffix array interval.
Definition fm_index_cursor.hpp:464
locate_result_type locate() const
Locates the occurrences of the searched query in the text.
Definition fm_index_cursor.hpp:586
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:645
bool operator==(fm_index_cursor const &rhs) const noexcept
Compares two cursors.
Definition fm_index_cursor.hpp:210
size_type count() const noexcept
Counts the number of occurrences of the searched query in the text.
Definition fm_index_cursor.hpp:568
size_type last_rank() const noexcept
Outputs the rightmost rank.
Definition fm_index_cursor.hpp:441
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:256
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
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:602
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:530
size_type query_length() const noexcept
Returns the length of the searched query. .
Definition fm_index_cursor.hpp:489
index_t index_type
Type of the index.
Definition fm_index_cursor.hpp:89
typename index_type::size_type size_type
Type for representing positions in the indexed text.
Definition fm_index_cursor.hpp:91
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:631
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.
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:69
@ single
The text is a single range.
Definition search/fm_index/concept.hpp:71
@ collection
The text is a range of ranges.
Definition search/fm_index/concept.hpp:73
constexpr auto slice
A view adaptor that returns a half-open interval on the underlying range.
Definition slice.hpp:137
The main SeqAn3 namespace.
Definition aligned_sequence_concept.hpp:26
Provides the concept for seqan3::detail::sdsl_index.
Provides seqan3::views::slice.
The underlying suffix array interval.
Definition fm_index_cursor.hpp:29
size_t end_position
The exclusive end position of the interval ("right boundary").
Definition fm_index_cursor.hpp:33
size_t begin_position
The begin position of the interval ("left boundary").
Definition fm_index_cursor.hpp:31
friend bool operator==(suffix_array_interval const &lhs, suffix_array_interval const &rhs) noexcept
Test for equality.
Definition fm_index_cursor.hpp:43
friend bool operator!=(suffix_array_interval const &lhs, suffix_array_interval const &rhs) noexcept
Test for inequality.
Definition fm_index_cursor.hpp:53