The SeqAn Bidirectional FM Index Cursor. More...
#include <seqan3/search/fm_index/bi_fm_index_cursor.hpp>
Public Types | |
using | index_type = index_t |
Type of the index. | |
Text types | |
using | size_type = typename index_type::size_type |
Type for representing positions in the indexed text. | |
Cursor types | |
using | fwd_cursor = fm_index_cursor< fm_index< index_type::is_collection_, typename index_type::sdsl_index_type > > |
Type for the unidirectional cursor on the original text. | |
using | rev_cursor = fm_index_cursor< fm_index< index_type::is_collection_, typename index_type::sdsl_index_type > > |
Type for the unidirectional cursor on the reversed text. | |
Public Member Functions | |
size_type | count () const noexcept |
Counts the number of occurrences of the searched query in the text. More... | |
bool | cycle_back () noexcept |
Tries to replace the rightmost character of the query by the next lexicographically larger character such that the query is found in the text. More... | |
bool | cycle_front () noexcept |
Tries to replace the leftmost character of the query by the next lexicographically larger character such that the query is found in the text. More... | |
bool | extend_left () noexcept |
Tries to extend the query by the smallest possible character to the left such that the query is found in the text. More... | |
template<Alphabet char_t> | |
bool | extend_left (char_t const c) noexcept |
Tries to extend the query by the character c to the left. More... | |
template<std::ranges::Range seq_t> | |
bool | extend_left (seq_t &&seq) noexcept |
Tries to extend the query by seq to the left. More... | |
bool | extend_right () noexcept |
Tries to extend the query by the smallest possible character to the right such that the query is found in the text. More... | |
template<Alphabet char_t> | |
bool | extend_right (char_t const c) noexcept |
Tries to extend the query by the character c to the right. More... | |
template<std::ranges::Range seq_t> | |
bool | extend_right (seq_t &&seq) noexcept |
Tries to extend the query by seq to the right. More... | |
size_type | last_rank () noexcept |
Outputs the rightmost respectively leftmost rank depending on whether extend_right() or extend_left() has been called last. More... | |
auto | lazy_locate () const |
Locates the occurrences of the searched query in the text on demand, i.e. a ranges::view is returned and every position is located once it is accessed. More... | |
auto | lazy_locate () const |
std::vector< size_type > | locate () const |
Locates the occurrences of the searched query in the text. More... | |
std::vector< std::pair< size_type, size_type > > | locate () const |
bool | operator!= (bi_fm_index_cursor const &rhs) const noexcept |
Compares two cursors. More... | |
bool | operator== (bi_fm_index_cursor const &rhs) const noexcept |
Compares two cursors. More... | |
template<std::ranges::Range text_t> | |
auto | path_label (text_t &&text) const noexcept |
Returns the searched query. More... | |
template<std::ranges::Range text_t> | |
auto | path_label (text_t &&text) const noexcept |
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 searched. More... | |
fwd_cursor | to_fwd_cursor () const noexcept |
Returns a unidirectional seqan3::fm_index_cursor on the original text. path_label() on the returned unidirectional index cursor will be equal to path_label() on the bidirectional index cursor. cycle_back() and last_char() will be undefined behavior if the last extension on the bidirectional FM index has been to the left. The behavior will be well-defined after the first extension to the right on the unidirectional index. More... | |
rev_cursor | to_rev_cursor () const noexcept |
Returns a unidirectional seqan3::fm_index_cursor on the reversed text. path_label() on the returned unidirectional index cursor will be equal to reversing path_label() on the bidirectional index cursor. Note that because of the text being reversed, extend_right() resp. cycle_back() correspond to extend_left() resp. cycle_front() on the bidirectional index cursor. Furthermore cycle_back() and last_char() will be undefined behavior if the last extension on the bidirectional FM index has been to the left. The behavior will be well-defined after the first extension to the right on the unidirectional index. More... | |
Constructors, destructor and assignment | |
bi_fm_index_cursor () noexcept=default | |
Default constructor. Accessing member functions on a default constructed object is undefined behavior. More... | |
bi_fm_index_cursor (bi_fm_index_cursor const &) noexcept=default | |
Copy constructor. | |
bi_fm_index_cursor & | operator= (bi_fm_index_cursor const &) noexcept=default |
Copy assignment. | |
bi_fm_index_cursor (bi_fm_index_cursor &&) noexcept=default | |
Move constructor. | |
bi_fm_index_cursor & | operator= (bi_fm_index_cursor &&) noexcept=default |
Move assignment. | |
~bi_fm_index_cursor ()=default | |
Destructor. | |
bi_fm_index_cursor (index_t const &_index) noexcept | |
Construct from given index. | |
Protected Types | |
using | sdsl_char_type = typename index_type::sdsl_char_type |
Type of the representation of characters in the underlying SDSL index. | |
using | sdsl_sigma_type = typename index_type::sdsl_sigma_type |
Type of the alphabet size in the underlying SDSL index. | |
Protected Member Functions | |
template<detail::SdslIndex csa_t> | |
bool | bidirectional_search (csa_t const &csa, sdsl_char_type const c, size_type &l_fwd, size_type &r_fwd, size_type &l_bwd, size_type &r_bwd) const noexcept |
Optimized bidirectional search without alphabet mapping. | |
template<detail::SdslIndex csa_t> | |
bool | bidirectional_search_cycle (csa_t const &csa, sdsl_char_type const c, size_type const l_parent, size_type const r_parent, size_type &l_fwd, size_type &r_fwd, size_type &l_bwd, size_type &r_bwd) const noexcept |
Optimized bidirectional search for cycle_back() and cycle_front() without alphabet mapping. | |
size_type | offset () const noexcept |
Helper function to recompute text positions since the indexed text is reversed. | |
Protected Attributes | |
size_type | depth |
Depth of the node in the suffix tree, i.e. length of the searched query. | |
bool | fwd_cursor_last_used = false |
Stores the information which cursor has been used last for extend_*([...]) to allow for assert() in. | |
index_type const * | index |
Type of the underlying FM index. | |
sdsl_sigma_type | sigma |
Alphabet size of the index without delimiters. | |
Suffix array intervals of forward and reverse cursors. | |
size_type | fwd_lb |
Left suffix array interval of the forward cursor (for extend_right). | |
size_type | fwd_rb |
Right suffix array interval of the forward cursor (for extend_right). | |
size_type | rev_lb |
Left suffix array interval of the reverse cursor (for extend_left). | |
size_type | rev_rb |
Right suffix array interval of the reverse cursor (for extend_left). | |
Information for on cycle_back() and cycle_front() | |
Only stored for the cursor that has been used last to go down an edge because once one cursor is touched, the others parent information becomes invalid and cannot be used for cycle_back() anymore. | |
size_type | parent_lb |
Left suffix array interval of the parent node. | |
size_type | parent_rb |
Left suffix array interval of the parent node. | |
sdsl_char_type | _last_char |
Label of the last edge moved down. Needed for cycle_back() or cycle_front(). | |
The SeqAn Bidirectional FM Index Cursor.
index_t | The type of the underlying index; must model seqan3::BiFmIndex. |
The cursor's interface provides searching a string both from left to right as well as from right to left in the indexed text. It extends the interface of the unidirectional seqan3::fm_index_cursor. All methods modifying the cursor (e.g. extending by a character with extend_right()) return a bool
value whether the operation was successful or not. In case of an unsuccessful operation the cursor remains unmodified, i.e. an cursor can never be in an invalid state except default constructed cursors that are always invalid.
The asymptotic running times for using the cursor depend on the SDSL index configuration. To determine the exact running times, you have to additionally look up the running times of the used traits (configuration).
|
defaultnoexcept |
Default constructor. Accessing member functions on a default constructed object is undefined behavior.
Default constructor.
|
inlinenoexcept |
Counts the number of occurrences of the searched query in the text.
Constant.
No-throw guarantee.
|
inlinenoexcept |
Tries to replace the rightmost character of the query by the next lexicographically larger character such that the query is found in the text.
true
if there exists a query in the text where the rightmost character of the query is lexicographically larger than the current rightmost character of the query.Example:
It scans linearly over the alphabet starting from the rightmost character until it finds the query with a larger rightmost character.
No-throw guarantee.
|
inlinenoexcept |
Tries to replace the leftmost character of the query by the next lexicographically larger character such that the query is found in the text.
true
if there exists a query in the text where the leftmost character of the query is lexicographically larger than the current leftmost character of the query.Example:
It scans linearly over the alphabet starting from the leftmost character until it finds the query with a larger leftmost character.
No-throw guarantee.
|
inlinenoexcept |
Tries to extend the query by the smallest possible character to the left such that the query is found in the text.
true
if the cursor could extend the query successfully.It scans linearly over the alphabet until it finds the smallest character that is represented by an edge.
No-throw guarantee.
|
inlinenoexcept |
Tries to extend the query by the character c
to the left.
char_t | Type of the character needs to be convertible to the character type char_type of the indexed text. |
[in] | c | Character to extend the query with to the left. |
true
if the cursor could extend the query successfully.No-throw guarantee.
|
inlinenoexcept |
Tries to extend the query by seq
to the left.
seq_t | The type of range of the sequence to search; must model std::ranges::BidirectionalRange. |
[in] | seq | Sequence to extend the query with to the left (starting from right to left, see example). |
true
if the cursor could extend the query successfully.If extending fails in the middle of the sequence, all previous computations are rewound to restore the cursor's state before calling this method.
Example:
No-throw guarantee.
|
inlinenoexcept |
Tries to extend the query by the smallest possible character to the right such that the query is found in the text.
true
if the cursor could extend the query successfully.It scans linearly over the alphabet until it finds the smallest character that is represented by an edge.
No-throw guarantee.
|
inlinenoexcept |
Tries to extend the query by the character c
to the right.
char_t | Type of the character needs to be convertible to the character type char_type of the indexed text. |
[in] | c | Character to extend the query with to the right. |
true
if the cursor could extend the query successfully.No-throw guarantee.
|
inlinenoexcept |
Tries to extend the query by seq
to the right.
seq_t | The type of range of the sequence to search; must model std::ranges::ForwardRange. |
[in] | seq | Sequence to extend the query with to the right. |
true
if the cursor could extend the query successfully.If extending fails in the middle of the sequence, all previous computations are rewound to restore the cursor's state before calling this method.
No-throw guarantee.
|
inlinenoexcept |
Outputs the rightmost respectively leftmost rank depending on whether extend_right() or extend_left() has been called last.
Example:
Constant.
No-throw guarantee.
|
inline |
Locates the occurrences of the searched query in the text on demand, i.e. a ranges::view is returned and every position is located once it is accessed.
Strong exception guarantee (no data is modified in case an exception is thrown).
|
inline |
This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.
|
inline |
Locates the occurrences of the searched query in the text.
Strong exception guarantee (no data is modified in case an exception is thrown).
|
inline |
This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.
|
inlinenoexcept |
Compares two cursors.
[in] | rhs | Other cursor to compare it to. |
true
if the cursors are not equal, false
otherwise.Constant.
No-throw guarantee.
|
inlinenoexcept |
Compares two cursors.
[in] | rhs | Other cursor to compare it to. |
true
if both cursors are equal, false
otherwise.Constant.
No-throw guarantee.
|
inlinenoexcept |
Returns the searched query.
text_t | The type of the text used to build the index; must model std::ranges::InputRange. |
[in] | text | Text that was used to build the index. |
No-throw guarantee.
|
inlinenoexcept |
This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.
|
inlinenoexcept |
Returns the depth of the cursor node in the implicit suffix tree, i.e. the length of the sequence searched.
Constant.
No-throw guarantee.
|
inlinenoexcept |
Returns a unidirectional seqan3::fm_index_cursor on the original text. path_label() on the returned unidirectional index cursor will be equal to path_label() on the bidirectional index cursor. cycle_back() and last_char() will be undefined behavior if the last extension on the bidirectional FM index has been to the left. The behavior will be well-defined after the first extension to the right on the unidirectional index.
Example:
Constant.
No-throw guarantee.
|
inlinenoexcept |
Returns a unidirectional seqan3::fm_index_cursor on the reversed text. path_label() on the returned unidirectional index cursor will be equal to reversing path_label() on the bidirectional index cursor. Note that because of the text being reversed, extend_right() resp. cycle_back() correspond to extend_left() resp. cycle_front() on the bidirectional index cursor. Furthermore cycle_back() and last_char() will be undefined behavior if the last extension on the bidirectional FM index has been to the left. The behavior will be well-defined after the first extension to the right on the unidirectional index.
Example:
Constant.
No-throw guarantee.