18#include <sdsl/suffix_trees.hpp>
53template <
typename index_t>
72 index_type::text_layout_mode,
73 typename index_type::sdsl_index_type>>;
78 using sdsl_char_type =
typename index_type::sdsl_char_type;
80 using sdsl_index_type =
typename index_t::sdsl_index_type;
82 using sdsl_sigma_type =
typename index_type::sdsl_sigma_type;
84 using index_alphabet_type =
typename index_t::alphabet_type;
107 sdsl_sigma_type sigma{};
124 sdsl_char_type _last_char{};
135 bool fwd_cursor_last_used =
false;
146 template <
typename csa_t>
148 requires (std::same_as<csa_t, typename index_type::sdsl_index_type> ||
149 std::same_as<csa_t, typename index_type::rev_sdsl_index_type>)
151 bool bidirectional_search(csa_t
const & csa, sdsl_char_type
const c,
155 assert((l_fwd <= r_fwd) && (r_fwd < csa.size()));
156 assert(r_fwd + 1 >= l_fwd);
157 assert(r_bwd + 1 - l_bwd == r_fwd + 1 - l_fwd);
159 size_type _l_fwd, _r_fwd, _l_bwd, _r_bwd;
162 if constexpr(!std::same_as<index_alphabet_type, sdsl::plain_byte_alphabet>)
164 cc = csa.char2comp[c];
165 if (cc == 0 && c > 0)
170 if (r_fwd + 1 - l_fwd == csa.size())
174 _r_fwd = csa.C[cc + 1] - 1;
180 auto const r_s_b = csa.wavelet_tree.lex_count(l_fwd, r_fwd + 1, c);
181 size_type const rank_l = std::get<0>(r_s_b);
182 size_type const s = std::get<1>(r_s_b), b = std::get<2>(r_s_b);
183 size_type const rank_r = r_fwd - l_fwd - s - b + rank_l;
184 _l_fwd = c_begin + rank_l;
185 _r_fwd = c_begin + rank_r;
190 if (_r_fwd >= _l_fwd)
196 assert(r_fwd + 1 >= l_fwd);
197 assert(r_bwd + 1 - l_bwd == r_fwd + 1 - l_fwd);
204 template <
typename csa_t>
206 requires (std::same_as<csa_t, typename index_type::sdsl_index_type> ||
207 std::same_as<csa_t, typename index_type::rev_sdsl_index_type>)
209 bool bidirectional_search_cycle(csa_t
const & csa, sdsl_char_type
const c,
214 assert((l_parent <= r_parent) && (r_parent < csa.size()));
217 if constexpr(std::same_as<index_alphabet_type, sdsl::plain_byte_alphabet>)
220 c_begin = csa.C[csa.char2comp[c]];
222 auto const r_s_b = csa.wavelet_tree.lex_count(l_parent, r_parent + 1, c);
224 b = std::get<2>(r_s_b),
225 rank_l = std::get<0>(r_s_b),
226 rank_r = r_parent - l_parent - s - b + rank_l;
228 size_type const _l_fwd = c_begin + rank_l;
229 size_type const _r_fwd = c_begin + rank_r;
231 size_type const _r_bwd = r_bwd + 1 + rank_r - rank_l;
233 if (_r_fwd >= _l_fwd)
239 assert(r_fwd + 1 >= l_fwd);
240 assert(r_bwd + 1 - l_bwd == r_fwd + 1 - l_fwd);
263 fwd_lb(0), fwd_rb(_index.
size() - 1),
264 rev_lb(0), rev_rb(_index.
size() - 1),
265 sigma(_index.fwd_fm.index.sigma - index_t::text_layout_mode),
284 assert(index !=
nullptr);
286 assert(!(fwd_lb == rhs.fwd_lb && fwd_rb == rhs.fwd_rb && depth == rhs.depth) ||
288 (parent_lb == rhs.parent_lb && parent_rb == rhs.parent_rb && _last_char == rhs._last_char));
290 return std::tie(fwd_lb, fwd_rb, depth) ==
std::tie(rhs.fwd_lb, rhs.fwd_rb, rhs.depth);
307 assert(index !=
nullptr);
309 return !(*
this == rhs);
332 fwd_cursor_last_used =
true;
335 assert(index !=
nullptr);
337 size_type new_parent_lb = fwd_lb, new_parent_rb = fwd_rb;
339 sdsl_char_type c = 1;
341 !bidirectional_search(index->fwd_fm.index, index->fwd_fm.index.comp2char[c],
342 fwd_lb, fwd_rb, rev_lb, rev_rb))
349 parent_lb = new_parent_lb;
350 parent_rb = new_parent_rb;
380 fwd_cursor_last_used =
false;
383 assert(index !=
nullptr);
385 size_type new_parent_lb = rev_lb, new_parent_rb = rev_rb;
387 sdsl_char_type c = 1;
389 !bidirectional_search(index->rev_fm.index, index->rev_fm.index.comp2char[c],
390 rev_lb, rev_rb, fwd_lb, fwd_rb))
397 parent_lb = new_parent_lb;
398 parent_rb = new_parent_rb;
421 template <
typename char_t>
423 requires std::convertible_to<char_t, index_alphabet_type>
428 fwd_cursor_last_used =
true;
431 assert(index !=
nullptr);
437 size_type new_parent_lb = fwd_lb, new_parent_rb = fwd_rb;
439 auto c_char =
seqan3::to_rank(
static_cast<index_alphabet_type
>(c)) + 1;
440 if (bidirectional_search(index->fwd_fm.index, c_char, fwd_lb, fwd_rb, rev_lb, rev_rb))
442 parent_lb = new_parent_lb;
443 parent_rb = new_parent_rb;
454 template <
typename char_type>
456 requires seqan3::detail::is_char_adaptation_v<char_type>
476 template <
typename char_t>
478 requires std::convertible_to<char_t, index_alphabet_type>
483 fwd_cursor_last_used =
false;
486 assert(index !=
nullptr);
492 size_type new_parent_lb = rev_lb, new_parent_rb = rev_rb;
494 auto c_char =
seqan3::to_rank(
static_cast<index_alphabet_type
>(c)) + 1;
495 if (bidirectional_search(index->rev_fm.index, c_char, rev_lb, rev_rb, fwd_lb, fwd_rb))
497 parent_lb = new_parent_lb;
498 parent_rb = new_parent_rb;
509 template <
typename char_type>
511 requires seqan3::detail::is_char_adaptation_v<char_type>
534 template <std::ranges::range seq_t>
537 static_assert(std::ranges::forward_range<seq_t>,
"The query must model forward_range.");
538 static_assert(std::convertible_to<range_innermost_value_t<seq_t>, index_alphabet_type>,
539 "The alphabet of the sequence must be convertible to the alphabet of the index.");
541 assert(index !=
nullptr);
543 auto first = std::ranges::begin(
seq);
544 auto last = std::ranges::end(
seq);
547 fwd_cursor_last_used = (first != last);
550 size_type _fwd_lb = fwd_lb, _fwd_rb = fwd_rb, _rev_lb = rev_lb, _rev_rb = rev_rb;
551 size_type new_parent_lb = parent_lb, new_parent_rb = parent_rb;
552 sdsl_char_type c = _last_char;
555 for (
auto it = first; it != last; ++len, ++it)
564 new_parent_lb = _fwd_lb;
565 new_parent_rb = _fwd_rb;
566 if (!bidirectional_search(index->fwd_fm.index, c, _fwd_lb, _fwd_rb, _rev_lb, _rev_rb))
575 parent_lb = new_parent_lb;
576 parent_rb = new_parent_rb;
604 template <std::ranges::range seq_t>
607 static_assert(std::ranges::bidirectional_range<seq_t>,
"The query must model bidirectional_range.");
608 static_assert(std::convertible_to<range_innermost_value_t<seq_t>, index_alphabet_type>,
609 "The alphabet of the sequence must be convertible to the alphabet of the index.");
610 assert(index !=
nullptr);
612 auto rev_seq = std::views::reverse(
seq);
613 auto first = std::ranges::begin(rev_seq);
614 auto last = std::ranges::end(rev_seq);
618 fwd_cursor_last_used =
false;
621 size_type _fwd_lb = fwd_lb, _fwd_rb = fwd_rb,
622 _rev_lb = rev_lb, _rev_rb = rev_rb;
623 size_type new_parent_lb = parent_lb, new_parent_rb = parent_rb;
624 sdsl_char_type c = _last_char;
627 for (
auto it = first; it != last; ++len, ++it)
636 new_parent_lb = _rev_lb;
637 new_parent_rb = _rev_rb;
638 if (!bidirectional_search(index->rev_fm.index, c, _rev_lb, _rev_rb, _fwd_lb, _fwd_rb))
647 parent_lb = new_parent_lb;
648 parent_rb = new_parent_rb;
685 assert(fwd_cursor_last_used);
690 sdsl_char_type c = _last_char + 1;
693 !bidirectional_search_cycle(index->fwd_fm.index, index->fwd_fm.index.comp2char[c],
694 parent_lb, parent_rb, fwd_lb, fwd_rb, rev_lb, rev_rb))
738 assert(!fwd_cursor_last_used);
743 sdsl_char_type c = _last_char + 1;
745 !bidirectional_search_cycle(index->rev_fm.index, index->rev_fm.index.comp2char[c],
746 parent_lb, parent_rb, rev_lb, rev_rb, fwd_lb, fwd_rb))
781 return index->fwd_fm.index.comp2char[_last_char] - 1;
798 assert(index !=
nullptr);
804 fwd_rb == index->size() - 1));
830 assert(index !=
nullptr);
833 cur.parent_lb = parent_lb;
834 cur.parent_rb = parent_rb;
835 cur.node = {fwd_lb, fwd_rb, depth, _last_char};
838 if (!fwd_cursor_last_used)
865 template <std::ranges::range text_t>
871 static_assert(std::ranges::input_range<text_t>,
"The text must model input_range.");
872 static_assert(range_dimension_v<text_t> == 1,
"The input cannot be a text collection.");
873 static_assert(std::same_as<range_innermost_value_t<text_t>, index_alphabet_type>,
874 "The alphabet types of the given text and index differ.");
875 assert(index !=
nullptr);
877 size_type const query_begin = offset() - index->fwd_fm.index[fwd_lb];
882 template <std::ranges::range text_t>
888 static_assert(std::ranges::input_range<text_t>,
"The text collection must model input_range.");
889 static_assert(range_dimension_v<text_t> == 2,
"The input must be a text collection.");
890 static_assert(std::same_as<range_innermost_value_t<text_t>, index_alphabet_type>,
891 "The alphabet types of the given text and index differ.");
892 assert(index !=
nullptr);
895 size_type const location = offset() - index->fwd_fm.index[fwd_lb];
899 size_type const rank = index->fwd_fm.text_begin_rs.rank(location + 1);
904 size_type const start_location = index->fwd_fm.text_begin_ss.select(rank);
906 size_type const query_begin = location - start_location;
925 assert(index !=
nullptr && (1 + fwd_rb - fwd_lb == 1 + rev_rb - rev_lb));
927 return 1 + fwd_rb - fwd_lb;
946 assert(index !=
nullptr);
952 occ.emplace_back(0, offset() - index->fwd_fm.index[fwd_lb + i]);
963 assert(index !=
nullptr);
969 size_type loc = offset() - index->fwd_fm.index[fwd_lb + i];
970 size_type sequence_rank = index->fwd_fm.text_begin_rs.rank(loc + 1);
971 size_type sequence_position = loc - index->fwd_fm.text_begin_ss.select(sequence_rank);
994 assert(index !=
nullptr);
996 return std::views::iota(fwd_lb, fwd_lb +
count())
1009 assert(index !=
nullptr);
1011 return std::views::iota(fwd_lb, fwd_lb +
count())
1014 auto loc = _offset - index->fwd_fm.index[sa_pos];
1015 size_type sequence_rank = index->fwd_fm.text_begin_rs.rank(loc + 1);
1016 size_type sequence_position = loc - index->fwd_fm.text_begin_ss.select(sequence_rank);
1028 template <cereal_archive archive_t>
1029 void CEREAL_SERIALIZE_FUNCTION_NAME(archive_t & archive)
1038 archive(_last_char);
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:55
bool extend_right() noexcept
Tries to extend the query by the smallest possible character to the right such that the query is foun...
Definition: bi_fm_index_cursor.hpp:329
size_type count() const noexcept
Counts the number of occurrences of the searched query in the text.
Definition: bi_fm_index_cursor.hpp:923
bool extend_left(seq_t &&seq) noexcept
Tries to extend the query by seq to the left.
Definition: bi_fm_index_cursor.hpp:605
bool operator==(bi_fm_index_cursor const &rhs) const noexcept
Compares two cursors.
Definition: bi_fm_index_cursor.hpp:282
bool extend_left(char_type const *cstring) noexcept
This is an overloaded member function, provided for convenience. It differs from the above function o...
Definition: bi_fm_index_cursor.hpp:513
std::vector< std::pair< size_type, size_type > > locate() const
This is an overloaded member function, provided for convenience. It differs from the above function o...
Definition: bi_fm_index_cursor.hpp:958
auto path_label(text_t &&text) const noexcept
Returns the searched query.
Definition: bi_fm_index_cursor.hpp:866
bool extend_left() noexcept
Tries to extend the query by the smallest possible character to the left such that the query is found...
Definition: bi_fm_index_cursor.hpp:377
locate_result_type locate() const
Locates the occurrences of the searched query in the text.
Definition: bi_fm_index_cursor.hpp:941
bool cycle_back() noexcept
Tries to replace the rightmost character of the query by the next lexicographically larger character ...
Definition: bi_fm_index_cursor.hpp:681
bool cycle_front() noexcept
Tries to replace the leftmost character of the query by the next lexicographically larger character s...
Definition: bi_fm_index_cursor.hpp:734
fwd_cursor to_fwd_cursor() const noexcept
Returns a unidirectional seqan3::fm_index_cursor on the original text. path_label() on the returned u...
Definition: bi_fm_index_cursor.hpp:828
size_type query_length() const noexcept
Returns the depth of the cursor node in the implicit suffix tree, i.e. the length of the sequence sea...
Definition: bi_fm_index_cursor.hpp:796
size_type last_rank() noexcept
Outputs the rightmost respectively leftmost rank depending on whether extend_right() or extend_left()...
Definition: bi_fm_index_cursor.hpp:777
index_t index_type
Type of the index.
Definition: bi_fm_index_cursor.hpp:58
typename index_type::size_type size_type
Type for representing positions in the indexed text.
Definition: bi_fm_index_cursor.hpp:64
bool extend_left(char_t const c) noexcept
Tries to extend the query by the character c to the left.
Definition: bi_fm_index_cursor.hpp:480
bool operator!=(bi_fm_index_cursor const &rhs) const noexcept
Compares two cursors.
Definition: bi_fm_index_cursor.hpp:305
bi_fm_index_cursor() noexcept=default
Default constructor. Accessing member functions on a default constructed object is undefined behavior...
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: bi_fm_index_cursor.hpp:458
bool extend_right(seq_t &&seq) noexcept
Tries to extend the query by seq to the right.
Definition: bi_fm_index_cursor.hpp:535
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: bi_fm_index_cursor.hpp:989
bool extend_right(char_t const c) noexcept
Tries to extend the query by the character c to the right.
Definition: bi_fm_index_cursor.hpp:425
The SeqAn FM Index Cursor.
Definition: fm_index_cursor.hpp:87
The SeqAn FM Index.
Definition: fm_index.hpp:192
Provides various transformation traits used by the range module.
T emplace_back(T... args)
Provides the unidirectional seqan3::fm_index.
Provides the seqan3::fm_index_cursor for searching in the unidirectional seqan3::fm_index.
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:72
@ single
The text is a single range.
Definition: concept.hpp:74
@ collection
The text is a range of ranges.
Definition: concept.hpp:76
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:471
constexpr size_t size
The size of a type pack.
Definition: traits.hpp:151
constexpr auto slice
A view adaptor that returns a half-open interval on the underlying range.
Definition: slice.hpp:183
The main SeqAn3 namespace.
Definition: cigar_operation_table.hpp:2
The <ranges> header from C++20's standard library.
Provides seqan3::views::slice.
Provides alphabet adaptations for standard uint types.