The SeqAn FM Index Cursor. More...

#include <seqan3/search/fm_index/fm_index_cursor.hpp>

Inheritance diagram for seqan3::fm_index_cursor< index_t >:

Public Member Functions
Constructors, destructor and assignment
	fm_index_cursor () noexcept=default
	Default constructor. Accessing member functions on a default constructed object is undefined behavior.

	fm_index_cursor (fm_index_cursor const &) noexcept=default
	Defaulted.

fm_index_cursor &	operator= (fm_index_cursor const &) noexcept=default
	Defaulted.

	fm_index_cursor (fm_index_cursor &&) noexcept=default
	Defaulted.

fm_index_cursor &	operator= (fm_index_cursor &&) noexcept=default
	Defaulted.

	~fm_index_cursor ()=default
	Defaulted.

	fm_index_cursor (index_t const &_index) noexcept
	Construct from given index.

bool	operator== (fm_index_cursor const &rhs) const noexcept
	Compares two cursors.

bool	operator!= (fm_index_cursor const &rhs) const noexcept
	Compares two cursors.

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. .

template<typename char_t > requires std::convertible_to<char_t, index_alphabet_type>
bool	extend_right (char_t const c) noexcept
	Tries to extend the query by the character `c` to the right.

template<typename char_type > requires detail::is_char_adaptation_v<char_type>
bool	extend_right (char_type const *cstring) noexcept
	This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

template<std::ranges::range seq_t>
bool	extend_right (seq_t &&seq) noexcept
	Tries to extend the query by `seq` to the right.

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. .

size_type	last_rank () const noexcept
	Outputs the rightmost rank.

seqan3::suffix_array_interval	suffix_array_interval () const noexcept
	Returns the half-open suffix array interval.

size_type	query_length () const noexcept
	Returns the length of the searched query. .

template<std::ranges::range text_t> requires (index_t::text_layout_mode == text_layout::single)
auto	path_label (text_t &&text) const noexcept
	Returns the searched query.

template<std::ranges::range text_t> requires (index_t::text_layout_mode == text_layout::collection)
auto	path_label (text_t &&text) const noexcept
	This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

size_type	count () const noexcept
	Counts the number of occurrences of the searched query in the text.

locate_result_type	locate () const
	Locates the occurrences of the searched query in the text.

locate_result_type	locate () const
	This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

auto	lazy_locate () const
	Locates the occurrences of the searched query in the text on demand, i.e. a std::ranges::view is returned and every position is located once it is accessed.

auto	lazy_locate () const
	This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

Friends
template<typename _index_t >
class	bi_fm_index_cursor

Member types
using	index_type = index_t
	Type of the index.

using	size_type = typename index_type::size_type
	Type for representing positions in the indexed text.

Detailed Description

template<typename index_t>
class seqan3::fm_index_cursor< index_t >

The SeqAn FM Index Cursor.

Template Parameters

index_t The type of the underlying index. This is normally seqan3::fm_index.

The cursor's interface provides searching a string from left to right in the indexed text. 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. a 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).

Constructor & Destructor Documentation

◆ fm_index_cursor()

template<typename index_t >

seqan3::fm_index_cursor< index_t >::fm_index_cursor ( )

defaultnoexcept

Default constructor. Accessing member functions on a default constructed object is undefined behavior.

Defaulted.

Member Function Documentation

◆ count()

template<typename index_t >

size_type seqan3::fm_index_cursor< index_t >::count ( ) const

inlinenoexcept

Counts the number of occurrences of the searched query in the text.

Returns: Number of occurrences of the searched query in the text.

Complexity

Constant.

Exceptions

No-throw guarantee.

◆ cycle_back()

template<typename index_t >

bool seqan3::fm_index_cursor< index_t >::cycle_back ( )

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. .

Returns: 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

// SPDX-FileCopyrightText: 2006-2024 Knut Reinert & Freie Universität Berlin
// SPDX-FileCopyrightText: 2016-2024 Knut Reinert & MPI für molekulare Genetik
// SPDX-License-Identifier: CC0-1.0
 
#include <vector>
 
#include <seqan3/alphabet/nucleotide/dna4.hpp>
#include <seqan3/core/debug_stream.hpp>
#include <seqan3/search/fm_index/all.hpp>
 
int main()
{
    using namespace seqan3::literals;
 
    std::vector<seqan3::dna4> genome{"AATAATAAC"_dna4};
    seqan3::fm_index index{genome}; // build the index
 
    auto cur = index.cursor(); // create a cursor
    // cur.cycle_back();                                            // cycle_back on begin() is undefined behaviour!
    cur.extend_right("AAC"_dna4);                                 // search the sequence "AAC"
    seqan3::debug_stream << cur.path_label(genome) << '\n';       // prints "AAC"
    seqan3::debug_stream << cur.last_rank() << '\n';              // prints 1
    seqan3::debug_stream << cur.query_length() << '\n';           // prints 3
    auto [left_bound, right_bound] = cur.suffix_array_interval(); // Get the half-open suffix array interval.
    seqan3::debug_stream << '[' << left_bound << ',' << right_bound << ")\n"; // prints "[7,8)"
 
    cur.cycle_back();                                       // search the sequence "AAT"
    seqan3::debug_stream << cur.path_label(genome) << '\n'; // prints "AAT"
    seqan3::debug_stream << cur.last_rank() << '\n';        // prints 3
    seqan3::debug_stream << cur.query_length() << '\n';     // prints 3
    auto interval = cur.suffix_array_interval();            // Get the half-open suffix array interval.
    seqan3::debug_stream << '[' << interval.begin_position << ',' << interval.end_position << ")\n"; // prints "[8,10)"
 
    cur.cycle_back();                                        // "cur" doesn't change because the rightmost char
                                                             // is already the largest dna4 char.
    seqan3::debug_stream << cur.path_label(genome) << '\n';  // prints "AAT"
    seqan3::debug_stream << cur.last_rank() << '\n';         // prints 3
    seqan3::debug_stream << cur.query_length() << '\n';      // prints 3
    auto && [lb, rb] = cur.suffix_array_interval();          // Get the half-open suffix array interval.
    seqan3::debug_stream << '[' << lb << ',' << rb << ")\n"; // prints "[8,10)"
}

Complexity

\(O(\Sigma) * O(T_{BACKWARD\_SEARCH})\)

It scans linearly over the alphabet starting from the rightmost character until it finds the query with a larger rightmost character.

Exceptions

No-throw guarantee.

◆ extend_right() [1/3]

template<typename index_t >

bool seqan3::fm_index_cursor< index_t >::extend_right ( )

inlinenoexcept

Tries to extend the query by the smallest possible character to the right such that the query is found in the text. .

Returns: true if the cursor could extend the query successfully.

Complexity

\(O(\Sigma) * O(T_{BACKWARD\_SEARCH})\)

It scans linearly over the alphabet until it finds the smallest character that is represented by an edge.

Exceptions

No-throw guarantee.

◆ extend_right() [2/3]

template<typename index_t >

template<typename char_t >
requires std::convertible_to<char_t, index_alphabet_type>

bool seqan3::fm_index_cursor< index_t >::extend_right ( char_t const c )

inlinenoexcept

Tries to extend the query by the character c to the right.

Template Parameters

char_t Type of the character needs to be convertible to the character type char_type of the index.

Parameters

[in] c Character to extend the query with to the right.

Returns: true if the cursor could extend the query successfully.

Complexity

\(O(T_{BACKWARD\_SEARCH})\)

Exceptions

No-throw guarantee.

◆ extend_right() [3/3]

template<typename index_t >

template<std::ranges::range seq_t>

bool seqan3::fm_index_cursor< index_t >::extend_right ( seq_t && seq )

inlinenoexcept

Tries to extend the query by seq to the right.

Template Parameters

seq_t The type of range of the sequence to search; must model std::ranges::forward_range.

Parameters

[in] seq Sequence to extend the query with to the right.

Returns: 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.

Complexity

\(|seq| * O(T_{BACKWARD\_SEARCH})\)

Exceptions

No-throw guarantee.

◆ last_rank()

template<typename index_t >

size_type seqan3::fm_index_cursor< index_t >::last_rank ( ) const

inlinenoexcept

Outputs the rightmost rank.

Returns: Rightmost rank.

Example

// SPDX-FileCopyrightText: 2006-2024 Knut Reinert & Freie Universität Berlin
// SPDX-FileCopyrightText: 2016-2024 Knut Reinert & MPI für molekulare Genetik
// SPDX-License-Identifier: CC0-1.0
 
#include <vector>
 
#include <seqan3/alphabet/nucleotide/dna4.hpp>
#include <seqan3/core/debug_stream.hpp>
#include <seqan3/search/fm_index/all.hpp>
 
int main()
{
    using namespace seqan3::literals;
 
    std::vector<seqan3::dna4> genome{"AATAATAAC"_dna4};
    seqan3::fm_index index{genome}; // build the index
 
    auto cur = index.cursor(); // create a cursor
    // cur.cycle_back();                                            // cycle_back on begin() is undefined behaviour!
    cur.extend_right("AAC"_dna4);                                 // search the sequence "AAC"
    seqan3::debug_stream << cur.path_label(genome) << '\n';       // prints "AAC"
    seqan3::debug_stream << cur.last_rank() << '\n';              // prints 1
    seqan3::debug_stream << cur.query_length() << '\n';           // prints 3
    auto [left_bound, right_bound] = cur.suffix_array_interval(); // Get the half-open suffix array interval.
    seqan3::debug_stream << '[' << left_bound << ',' << right_bound << ")\n"; // prints "[7,8)"
 
    cur.cycle_back();                                       // search the sequence "AAT"
    seqan3::debug_stream << cur.path_label(genome) << '\n'; // prints "AAT"
    seqan3::debug_stream << cur.last_rank() << '\n';        // prints 3
    seqan3::debug_stream << cur.query_length() << '\n';     // prints 3
    auto interval = cur.suffix_array_interval();            // Get the half-open suffix array interval.
    seqan3::debug_stream << '[' << interval.begin_position << ',' << interval.end_position << ")\n"; // prints "[8,10)"
 
    cur.cycle_back();                                        // "cur" doesn't change because the rightmost char
                                                             // is already the largest dna4 char.
    seqan3::debug_stream << cur.path_label(genome) << '\n';  // prints "AAT"
    seqan3::debug_stream << cur.last_rank() << '\n';         // prints 3
    seqan3::debug_stream << cur.query_length() << '\n';      // prints 3
    auto && [lb, rb] = cur.suffix_array_interval();          // Get the half-open suffix array interval.
    seqan3::debug_stream << '[' << lb << ',' << rb << ")\n"; // prints "[8,10)"
}

Complexity

Constant.

Exceptions

No-throw guarantee.

◆ lazy_locate()

template<typename index_t >

auto seqan3::fm_index_cursor< index_t >::lazy_locate ( ) const

inline

Locates the occurrences of the searched query in the text on demand, i.e. a std::ranges::view is returned and every position is located once it is accessed.

Returns: Positions in the text.

Complexity

\(count() * O(T_{BACKWARD\_SEARCH} * SAMPLING\_RATE)\)

Exceptions

Strong exception guarantee (no data is modified in case an exception is thrown).

◆ locate()

template<typename index_t >

locate_result_type seqan3::fm_index_cursor< index_t >::locate ( ) const

inline

Locates the occurrences of the searched query in the text.

Returns: Positions in the text.

Complexity

\(count() * O(T_{BACKWARD\_SEARCH} * SAMPLING\_RATE)\)

Exceptions

Strong exception guarantee (no data is modified in case an exception is thrown).

◆ operator!=()

template<typename index_t >

bool seqan3::fm_index_cursor< index_t >::operator!= ( fm_index_cursor< index_t > const & rhs ) const

inlinenoexcept

Compares two cursors.

Parameters

[in] rhs Other cursor to compare it to.

Returns: true if the cursors are not equal, false otherwise.

Complexity

Constant.

Exceptions

No-throw guarantee.

◆ operator==()

template<typename index_t >

bool seqan3::fm_index_cursor< index_t >::operator== ( fm_index_cursor< index_t > const & rhs ) const

inlinenoexcept

Compares two cursors.

Parameters

[in] rhs Other cursor to compare it to.

Returns: true if both cursors are equal, false otherwise.

Complexity

Constant.

Exceptions

No-throw guarantee.

◆ path_label()

template<typename index_t >

template<std::ranges::range text_t>
requires (index_t::text_layout_mode == text_layout::single)

auto seqan3::fm_index_cursor< index_t >::path_label ( text_t && text ) const

inlinenoexcept

Returns the searched query.

Template Parameters

text_t The type of the text used to build the index; must model std::ranges::input_range.

Parameters

[in] text Text that was used to build the index.

Returns: Searched query.

Complexity

\(O(SAMPLING\_RATE * T_{BACKWARD\_SEARCH}) + query\_length()\)

Exceptions

No-throw guarantee.

◆ query_length()

template<typename index_t >

size_type seqan3::fm_index_cursor< index_t >::query_length ( ) const

inlinenoexcept

Returns the length of the searched query. .

Returns: Length of query.

Example

// SPDX-FileCopyrightText: 2006-2024 Knut Reinert & Freie Universität Berlin
// SPDX-FileCopyrightText: 2016-2024 Knut Reinert & MPI für molekulare Genetik
// SPDX-License-Identifier: CC0-1.0
 
#include <vector>
 
#include <seqan3/alphabet/nucleotide/dna4.hpp>
#include <seqan3/core/debug_stream.hpp>
#include <seqan3/search/fm_index/all.hpp>
 
int main()
{
    using namespace seqan3::literals;
 
    std::vector<seqan3::dna4> genome{"AATAATAAC"_dna4};
    seqan3::fm_index index{genome}; // build the index
 
    auto cur = index.cursor(); // create a cursor
    // cur.cycle_back();                                            // cycle_back on begin() is undefined behaviour!
    cur.extend_right("AAC"_dna4);                                 // search the sequence "AAC"
    seqan3::debug_stream << cur.path_label(genome) << '\n';       // prints "AAC"
    seqan3::debug_stream << cur.last_rank() << '\n';              // prints 1
    seqan3::debug_stream << cur.query_length() << '\n';           // prints 3
    auto [left_bound, right_bound] = cur.suffix_array_interval(); // Get the half-open suffix array interval.
    seqan3::debug_stream << '[' << left_bound << ',' << right_bound << ")\n"; // prints "[7,8)"
 
    cur.cycle_back();                                       // search the sequence "AAT"
    seqan3::debug_stream << cur.path_label(genome) << '\n'; // prints "AAT"
    seqan3::debug_stream << cur.last_rank() << '\n';        // prints 3
    seqan3::debug_stream << cur.query_length() << '\n';     // prints 3
    auto interval = cur.suffix_array_interval();            // Get the half-open suffix array interval.
    seqan3::debug_stream << '[' << interval.begin_position << ',' << interval.end_position << ")\n"; // prints "[8,10)"
 
    cur.cycle_back();                                        // "cur" doesn't change because the rightmost char
                                                             // is already the largest dna4 char.
    seqan3::debug_stream << cur.path_label(genome) << '\n';  // prints "AAT"
    seqan3::debug_stream << cur.last_rank() << '\n';         // prints 3
    seqan3::debug_stream << cur.query_length() << '\n';      // prints 3
    auto && [lb, rb] = cur.suffix_array_interval();          // Get the half-open suffix array interval.
    seqan3::debug_stream << '[' << lb << ',' << rb << ")\n"; // prints "[8,10)"
}

Complexity

Constant.

Exceptions

No-throw guarantee.

◆ suffix_array_interval()

template<typename index_t >

seqan3::suffix_array_interval seqan3::fm_index_cursor< index_t >::suffix_array_interval ( ) const

inlinenoexcept

Returns the half-open suffix array interval.

Returns: A seqan3::suffix_array_interval contains the half-open interval.

Example

// SPDX-FileCopyrightText: 2006-2024 Knut Reinert & Freie Universität Berlin
// SPDX-FileCopyrightText: 2016-2024 Knut Reinert & MPI für molekulare Genetik
// SPDX-License-Identifier: CC0-1.0
 
#include <vector>
 
#include <seqan3/alphabet/nucleotide/dna4.hpp>
#include <seqan3/core/debug_stream.hpp>
#include <seqan3/search/fm_index/all.hpp>
 
int main()
{
    using namespace seqan3::literals;
 
    std::vector<seqan3::dna4> genome{"AATAATAAC"_dna4};
    seqan3::fm_index index{genome}; // build the index
 
    auto cur = index.cursor(); // create a cursor
    // cur.cycle_back();                                            // cycle_back on begin() is undefined behaviour!
    cur.extend_right("AAC"_dna4);                                 // search the sequence "AAC"
    seqan3::debug_stream << cur.path_label(genome) << '\n';       // prints "AAC"
    seqan3::debug_stream << cur.last_rank() << '\n';              // prints 1
    seqan3::debug_stream << cur.query_length() << '\n';           // prints 3
    auto [left_bound, right_bound] = cur.suffix_array_interval(); // Get the half-open suffix array interval.
    seqan3::debug_stream << '[' << left_bound << ',' << right_bound << ")\n"; // prints "[7,8)"
 
    cur.cycle_back();                                       // search the sequence "AAT"
    seqan3::debug_stream << cur.path_label(genome) << '\n'; // prints "AAT"
    seqan3::debug_stream << cur.last_rank() << '\n';        // prints 3
    seqan3::debug_stream << cur.query_length() << '\n';     // prints 3
    auto interval = cur.suffix_array_interval();            // Get the half-open suffix array interval.
    seqan3::debug_stream << '[' << interval.begin_position << ',' << interval.end_position << ")\n"; // prints "[8,10)"
 
    cur.cycle_back();                                        // "cur" doesn't change because the rightmost char
                                                             // is already the largest dna4 char.
    seqan3::debug_stream << cur.path_label(genome) << '\n';  // prints "AAT"
    seqan3::debug_stream << cur.last_rank() << '\n';         // prints 3
    seqan3::debug_stream << cur.query_length() << '\n';      // prints 3
    auto && [lb, rb] = cur.suffix_array_interval();          // Get the half-open suffix array interval.
    seqan3::debug_stream << '[' << lb << ',' << rb << ")\n"; // prints "[8,10)"
}

Complexity

Constant.

Exceptions

No-throw guarantee.

The documentation for this class was generated from the following file:

fm_index_cursor.hpp

Public Member Functions

Friends

Member types

Detailed Description

Constructor & Destructor Documentation

◆ fm_index_cursor()

Member Function Documentation

◆ count()

Complexity

Exceptions

◆ cycle_back()

Example

Complexity

Exceptions

◆ extend_right() [1/3]

Complexity

Exceptions

◆ extend_right() [2/3]

Complexity

Exceptions

◆ extend_right() [3/3]

Complexity

Exceptions

◆ last_rank()

Example

Complexity

Exceptions

◆ lazy_locate()

Complexity

Exceptions

◆ locate()

Complexity

Exceptions

◆ operator!=()

Complexity

Exceptions

◆ operator==()

Complexity

Exceptions

◆ path_label()

Complexity

Exceptions

◆ query_length()

Example

Complexity

Exceptions

◆ suffix_array_interval()

Example

Complexity

Exceptions