seqan3::detail::reverse_fm_index< alphabet_t, text_layout_mode, sdsl_index_type > Class Template Reference

An FM Index specialisation that handles reversing the given text. More...

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

Inheritance diagram for seqan3::detail::reverse_fm_index< alphabet_t, text_layout_mode, sdsl_index_type >:

Public Member Functions
cursor_type	cursor () const noexcept
	Returns a seqan3::fm_index_cursor on the index that can be used for searching. Cursor is pointing to the root node of the implicit suffix tree. More...
bool	empty () const noexcept
	Checks whether the index is empty. More...
bool	operator!= (fm_index const &rhs) const noexcept
	Compares two indices. More...
bool	operator== (fm_index const &rhs) const noexcept
	Compares two indices. More...
template<std::ranges::bidirectional_range text_t>
	reverse_fm_index (text_t &&text)
	Constructor that immediately constructs the index given a range. The range cannot be empty. More...
void	serialize (archive_t &archive)
	Serialisation support function. More...
size_type	size () const noexcept
	Returns the length of the indexed text including sentinel characters. More...

Static Public Attributes
static constexpr text_layout	text_layout_mode
	Indicates whether index is built over a collection.

Private Member Functions
void	construct (text_t &&text)
	Constructs the index given a range. The range cannot be an rvalue (i.e. a temporary object) and has to be non-empty. More...
void	construct (text_t &&text, bool reverse=false)
	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 text_t>
void	construct_ (text_t &&text)
	Constructs the index given a range. The range cannot be an rvalue (i.e. a temporary object) and has to be non-empty. More...

Private Attributes
sdsl_index_type	index
	Underlying index from the SDSL.
sdsl::sd_vector	text_begin
	Bitvector storing begin positions for collections.
sdsl::rank_support_sd< 1 >	text_begin_rs
	Rank support for text_begin.
sdsl::select_support_sd< 1 >	text_begin_ss
	Select support for text_begin.

Member types
using	sdsl_index_type = sdsl_index_type_
	The type of the underlying SDSL index.
using	sdsl_char_type = typename sdsl_index_type::alphabet_type::char_type
	The type of the reduced alphabet type. (The reduced alphabet might be smaller than the original alphabet in case not all possible characters occur in the indexed text.)
using	sdsl_sigma_type = typename sdsl_index_type::alphabet_type::sigma_type
	The type of the alphabet size of the underlying SDSL index.
using	alphabet_type = alphabet_t
	The type of the underlying character of the indexed text.
using	size_type = typename sdsl_index_type::size_type
	Type for representing positions in the indexed text.
using	cursor_type = fm_index_cursor< fm_index >
	The type of the (unidirectional) cursor.

Detailed Description

template<semialphabet alphabet_t, text_layout text_layout_mode, detail::sdsl_index sdsl_index_type = default_sdsl_index_type>
class seqan3::detail::reverse_fm_index< alphabet_t, text_layout_mode, sdsl_index_type >

An FM Index specialisation that handles reversing the given text.

Template Parameters

alphabet_t	The alphabet type; must model seqan3::semialphabet.
text_layout_mode	Indicates whether this index works on a text collection or a single text. See seqan3::text_layout.
sdsl_index_type	The type of the underlying SDSL index, must model seqan3::sdsl_index.

This FM Index reverses the given text before constructing the seqan3::fm_index. This type is used by the seqan3::bi_fm_index.

Constructor & Destructor Documentation

reverse_fm_index()

template<semialphabet alphabet_t, text_layout text_layout_mode, detail::sdsl_index sdsl_index_type = default_sdsl_index_type>

template<std::ranges::bidirectional_range text_t>

seqan3::detail::reverse_fm_index< alphabet_t, text_layout_mode, sdsl_index_type >::reverse_fm_index ( text_t &&  text )

inlineexplicit

Constructor that immediately constructs the index given a range. The range cannot be empty.

Template Parameters

text_t

The type of range to construct from; must model std::ranges::bidirectional_range.

Parameters

[in]

text

The text to construct from.

Complexity

Todo:

At least linear.

Member Function Documentation

construct()

void seqan3::fm_index< alphabet_t, text_layout_mode_, sdsl_index_type_ >::construct ( text_t &&  text )

inlineprivateinherited

Constructs the index given a range. The range cannot be an rvalue (i.e. a temporary object) and has to be non-empty.

Template Parameters

text_t

The type of range to construct from; must model std::ranges::bidirectional_range.

Parameters

[in]

text

The text to construct from.

Todo:

This has to be better implemented with regard to the memory peak due to not matching interfaces with the SDSL.

Complexity

Todo:

At least linear.

Exceptions

No guarantee.

Todo:

Ensure strong exception guarantee.

construct_()

template<semialphabet alphabet_t, text_layout text_layout_mode, detail::sdsl_index sdsl_index_type = default_sdsl_index_type>

template<std::ranges::range text_t>

void seqan3::detail::reverse_fm_index< alphabet_t, text_layout_mode, sdsl_index_type >::construct_ ( text_t &&  text )

inlineprivate

Constructs the index given a range. The range cannot be an rvalue (i.e. a temporary object) and has to be non-empty.

Template Parameters

text_t

The type of range to construct from; must model std::ranges::bidirectional_range.

Parameters

[in]

text

The text to construct from.

Todo:

This has to be better implemented with regard to the memory peak due to not matching interfaces with the SDSL.

Complexity

Todo:

At least linear.

Exceptions

No guarantee.

Todo:

Ensure strong exception guarantee.

cursor()

cursor_type seqan3::fm_index< alphabet_t, text_layout_mode_, sdsl_index_type_ >::cursor ( ) const

inlinenoexceptinherited

Returns a seqan3::fm_index_cursor on the index that can be used for searching. Cursor is pointing to the root node of the implicit suffix tree.

Returns

Returns a (unidirectional) seqan3::fm_index_cursor on the index.

Complexity

Constant.

Exceptions

No-throw guarantee.

empty()

bool seqan3::fm_index< alphabet_t, text_layout_mode_, sdsl_index_type_ >::empty ( ) const

inlinenoexceptinherited

Checks whether the index is empty.

Returns

true if the index is empty, false otherwise.

Complexity

Constant.

Exceptions

No-throw guarantee.

operator!=()

bool seqan3::fm_index< alphabet_t, text_layout_mode_, sdsl_index_type_ >::operator!= ( fm_index< alphabet_t, text_layout_mode, default_sdsl_index_type > const &  rhs ) const

inlinenoexceptinherited

Compares two indices.

Returns

true if the indices are unequal, false otherwise.

Complexity

Linear.

Exceptions

No-throw guarantee.

operator==()

bool seqan3::fm_index< alphabet_t, text_layout_mode_, sdsl_index_type_ >::operator== ( fm_index< alphabet_t, text_layout_mode, default_sdsl_index_type > const &  rhs ) const

inlinenoexceptinherited

Compares two indices.

Returns

true if the indices are equal, false otherwise.

Complexity

Linear.

Exceptions

No-throw guarantee.

serialize()

void seqan3::fm_index< alphabet_t, text_layout_mode_, sdsl_index_type_ >::serialize ( archive_t &  archive )

inlineinherited

Serialisation support function.

Template Parameters

archive_t

Type of archive; must satisfy seqan3::cereal_archive.

Parameters

archive

The archive being serialised from/to.

Attention

These functions are never called directly, see Serialisation for more details.

size()

size_type seqan3::fm_index< alphabet_t, text_layout_mode_, sdsl_index_type_ >::size ( ) const

inlinenoexceptinherited

Returns the length of the indexed text including sentinel characters.

Returns

Returns the length of the indexed text including sentinel characters.

Complexity

Constant.

Exceptions

No-throw guarantee.

---

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

• seqan3/search/fm_index/fm_index.hpp