Loading...
Searching...
No Matches
bi_fm_index_cursor.hpp
Go to the documentation of this file.
// SPDX-FileCopyrightText: 2006-2025 Knut Reinert & Freie Universität Berlin
// SPDX-FileCopyrightText: 2016-2025 Knut Reinert & MPI für molekulare Genetik
// SPDX-License-Identifier: BSD-3-Clause
#pragma once
#include <array>
#include <ranges>
#include <seqan3/alphabet/adaptation/char.hpp>
#include <seqan3/alphabet/adaptation/uint.hpp>
#include <seqan3/alphabet/concept.hpp>
#include <seqan3/contrib/sdsl-lite.hpp>
#include <seqan3/core/range/type_traits.hpp>
#include <seqan3/search/fm_index/fm_index.hpp>
#include <seqan3/search/fm_index/fm_index_cursor.hpp>
#include <seqan3/utility/views/slice.hpp>
namespace seqan3
{
template <typename index_t>
class bi_fm_index_cursor
{
public:
using index_type = index_t;
using size_type = typename index_type::size_type;
using fwd_cursor = fm_index_cursor<fm_index<typename index_type::alphabet_type,
index_type::text_layout_mode,
typename index_type::sdsl_index_type>>;
private:
using sdsl_char_type = typename index_type::sdsl_char_type;
using sdsl_index_type = typename index_t::sdsl_index_type;
using sdsl_sigma_type = typename index_type::sdsl_sigma_type;
using index_alphabet_type = typename index_t::alphabet_type;
using locate_result_value_type = std::pair<size_type, size_type>;
using locate_result_type = std::vector<locate_result_value_type>;
index_type const * index{nullptr};
size_type fwd_lb{};
size_type fwd_rb{};
size_type rev_lb{};
size_type rev_rb{};
//\}
sdsl_sigma_type sigma{};
// parent_* and _last_char only have to be stored for the (unidirectional) cursor that has been used last for
// extend_right() or cycle_back() resp. extend_left() or cycle_front(), (i.e. either fwd or rev). Thus there is no
// need to store it twice. Once the cursor is switched, the information becomes invalid anyway.
size_type parent_lb{};
size_type parent_rb{};
sdsl_char_type _last_char{};
//\}
size_type depth{}; // equal for both cursors. only stored once
// supports assertions to check whether cycle_back() resp. cycle_front() is called on the same direction as the last
// extend_right([...]) resp. extend_left([...])
#ifndef NDEBUG
// cycle_back() and cycle_front()
bool fwd_cursor_last_used = false;
#endif
size_type offset() const noexcept
{
assert(index->size() > query_length());
return index->size() - query_length() - 1; // since the string is reversed during construction
}
template <typename csa_t>
requires (std::same_as<csa_t, typename index_type::sdsl_index_type>
|| std::same_as<csa_t, typename index_type::rev_sdsl_index_type>)
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
{
assert((l_fwd <= r_fwd) && (r_fwd < csa.size()));
assert(r_fwd + 1 >= l_fwd);
assert(r_bwd + 1 - l_bwd == r_fwd + 1 - l_fwd);
size_type _l_fwd, _r_fwd, _l_bwd, _r_bwd;
size_type cc = c;
if constexpr (!std::same_as<index_alphabet_type, seqan3::contrib::sdsl::plain_byte_alphabet>)
{
cc = csa.char2comp[c];
if (cc == 0 && c > 0) // [[unlikely]]
return false;
}
size_type const c_begin = csa.C[cc];
if (r_fwd + 1 - l_fwd == csa.size()) // [[unlikely]]
{
_l_fwd = c_begin;
_l_bwd = c_begin;
_r_fwd = csa.C[cc + 1] - 1;
_r_bwd = _r_fwd;
// if we use not the plain_byte_alphabet, we could return always return true here
}
else
{
auto const r_s_b = csa.wavelet_tree.lex_count(l_fwd, r_fwd + 1, c);
size_type const rank_l = std::get<0>(r_s_b);
size_type const s = std::get<1>(r_s_b), b = std::get<2>(r_s_b);
size_type const rank_r = r_fwd - l_fwd - s - b + rank_l;
_l_fwd = c_begin + rank_l;
_r_fwd = c_begin + rank_r;
_l_bwd = l_bwd + s;
_r_bwd = r_bwd - b;
}
if (_r_fwd >= _l_fwd)
{
l_fwd = _l_fwd;
r_fwd = _r_fwd;
l_bwd = _l_bwd;
r_bwd = _r_bwd;
assert(r_fwd + 1 >= l_fwd);
assert(r_bwd + 1 - l_bwd == r_fwd + 1 - l_fwd);
return true;
}
return false;
}
template <typename csa_t>
requires (std::same_as<csa_t, typename index_type::sdsl_index_type>
|| std::same_as<csa_t, typename index_type::rev_sdsl_index_type>)
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
{
assert((l_parent <= r_parent) && (r_parent < csa.size()));
size_type c_begin;
if constexpr (std::same_as<index_alphabet_type, seqan3::contrib::sdsl::plain_byte_alphabet>)
c_begin = csa.C[c]; // TODO: check whether this can be removed
else
c_begin = csa.C[csa.char2comp[c]];
auto const r_s_b = csa.wavelet_tree.lex_count(l_parent, r_parent + 1, c);
size_type const s = std::get<1>(r_s_b), b = std::get<2>(r_s_b), rank_l = std::get<0>(r_s_b),
rank_r = r_parent - l_parent - s - b + rank_l;
size_type const _l_fwd = c_begin + rank_l;
size_type const _r_fwd = c_begin + rank_r;
size_type const _l_bwd = r_bwd + 1;
size_type const _r_bwd = r_bwd + 1 + rank_r - rank_l;
if (_r_fwd >= _l_fwd)
{
l_fwd = _l_fwd;
r_fwd = _r_fwd;
l_bwd = _l_bwd;
r_bwd = _r_bwd;
assert(r_fwd + 1 >= l_fwd);
assert(r_bwd + 1 - l_bwd == r_fwd + 1 - l_fwd);
return true;
}
return false;
}
public:
// Default construction is necessary to make this class semi-regular and e.g., to allow construction of
// std::array of cursors.
bi_fm_index_cursor() noexcept = default;
bi_fm_index_cursor(bi_fm_index_cursor const &) noexcept = default;
bi_fm_index_cursor & operator=(bi_fm_index_cursor const &) noexcept = default;
bi_fm_index_cursor(bi_fm_index_cursor &&) noexcept = default;
bi_fm_index_cursor & operator=(bi_fm_index_cursor &&) noexcept = default;
~bi_fm_index_cursor() = default;
bi_fm_index_cursor(index_t const & _index) noexcept :
index(&_index),
fwd_lb(0),
fwd_rb(_index.size() - 1),
rev_lb(0),
rev_rb(_index.size() - 1),
sigma(_index.fwd_fm.index.sigma - index_t::text_layout_mode),
depth(0)
{}
//\}
bool operator==(bi_fm_index_cursor const & rhs) const noexcept
{
assert(index != nullptr);
// equal SA interval implies equal parent node information (or both are root nodes)
assert(!(fwd_lb == rhs.fwd_lb && fwd_rb == rhs.fwd_rb && depth == rhs.depth) || (depth == 0)
|| (parent_lb == rhs.parent_lb && parent_rb == rhs.parent_rb && _last_char == rhs._last_char));
return std::tie(fwd_lb, fwd_rb, depth) == std::tie(rhs.fwd_lb, rhs.fwd_rb, rhs.depth);
}
bool operator!=(bi_fm_index_cursor const & rhs) const noexcept
{
assert(index != nullptr);
return !(*this == rhs);
}
bool extend_right() noexcept
{
#ifndef NDEBUG
fwd_cursor_last_used = true;
#endif
assert(index != nullptr);
size_type new_parent_lb = fwd_lb, new_parent_rb = fwd_rb;
sdsl_sigma_type c = 1; // NOTE: start with 0 or 1 depending on implicit_sentintel
while (c < sigma
&& !bidirectional_search(index->fwd_fm.index,
index->fwd_fm.index.comp2char[c],
fwd_lb,
fwd_rb,
rev_lb,
rev_rb))
{
++c;
}
if (c != sigma)
{
parent_lb = new_parent_lb;
parent_rb = new_parent_rb;
assert(c <= std::numeric_limits<sdsl_char_type>::max());
_last_char = static_cast<sdsl_char_type>(c);
++depth;
return true;
}
return false;
}
bool extend_left() noexcept
{
#ifndef NDEBUG
fwd_cursor_last_used = false;
#endif
assert(index != nullptr);
size_type new_parent_lb = rev_lb, new_parent_rb = rev_rb;
sdsl_sigma_type c = 1; // NOTE: start with 0 or 1 depending on implicit_sentintel
while (c < sigma
&& !bidirectional_search(index->rev_fm.index,
index->rev_fm.index.comp2char[c],
rev_lb,
rev_rb,
fwd_lb,
fwd_rb))
{
++c;
}
if (c != sigma)
{
parent_lb = new_parent_lb;
parent_rb = new_parent_rb;
assert(c <= std::numeric_limits<sdsl_char_type>::max());
_last_char = static_cast<sdsl_char_type>(c);
++depth;
return true;
}
return false;
}
template <typename char_t>
requires std::convertible_to<char_t, index_alphabet_type>
bool extend_right(char_t const c) noexcept
{
#ifndef NDEBUG
fwd_cursor_last_used = true;
#endif
assert(index != nullptr);
// The rank cannot exceed 255 for single text and 254 for text collections as they are reserved as sentinels
// for the indexed text.
assert(seqan3::to_rank(static_cast<index_alphabet_type>(c))
< ((index_type::text_layout_mode == text_layout::single) ? 255 : 254));
size_type new_parent_lb = fwd_lb, new_parent_rb = fwd_rb;
auto c_char = seqan3::to_rank(static_cast<index_alphabet_type>(c)) + 1;
if (bidirectional_search(index->fwd_fm.index, c_char, fwd_lb, fwd_rb, rev_lb, rev_rb))
{
parent_lb = new_parent_lb;
parent_rb = new_parent_rb;
_last_char = c_char;
++depth;
return true;
}
return false;
}
template <typename char_type>
requires seqan3::detail::is_char_adaptation_v<char_type>
bool extend_right(char_type const * cstring) noexcept
{
return extend_right(std::basic_string_view<char_type>{cstring});
}
template <typename char_t>
requires std::convertible_to<char_t, index_alphabet_type>
bool extend_left(char_t const c) noexcept
{
#ifndef NDEBUG
fwd_cursor_last_used = false;
#endif
assert(index != nullptr);
// The rank cannot exceed 255 for single text and 254 for text collections as they are reserved as sentinels
// for the indexed text.
assert(seqan3::to_rank(static_cast<index_alphabet_type>(c))
< ((index_type::text_layout_mode == text_layout::single) ? 255 : 254));
size_type new_parent_lb = rev_lb, new_parent_rb = rev_rb;
auto c_char = seqan3::to_rank(static_cast<index_alphabet_type>(c)) + 1;
if (bidirectional_search(index->rev_fm.index, c_char, rev_lb, rev_rb, fwd_lb, fwd_rb))
{
parent_lb = new_parent_lb;
parent_rb = new_parent_rb;
_last_char = c_char;
++depth;
return true;
}
return false;
}
template <typename char_type>
requires seqan3::detail::is_char_adaptation_v<char_type>
bool extend_left(char_type const * cstring) noexcept
{
return extend_left(std::basic_string_view<char_type>{cstring});
}
template <std::ranges::range seq_t>
bool extend_right(seq_t && seq) noexcept
{
static_assert(std::ranges::forward_range<seq_t>, "The query must model forward_range.");
static_assert(std::convertible_to<range_innermost_value_t<seq_t>, index_alphabet_type>,
"The alphabet of the sequence must be convertible to the alphabet of the index.");
assert(index != nullptr);
auto first = std::ranges::begin(seq);
auto last = std::ranges::end(seq);
#ifndef NDEBUG
fwd_cursor_last_used = (first != last); // only if seq was not empty
#endif
size_type _fwd_lb = fwd_lb, _fwd_rb = fwd_rb, _rev_lb = rev_lb, _rev_rb = rev_rb;
size_type new_parent_lb = parent_lb, new_parent_rb = parent_rb;
sdsl_char_type c = _last_char;
size_t len{0};
for (auto it = first; it != last; ++len, ++it)
{
// The rank cannot exceed 255 for single text and 254 for text collections as they are reserved as sentinels
// for the indexed text.
assert(seqan3::to_rank(static_cast<index_alphabet_type>(*it))
< ((index_type::text_layout_mode == text_layout::single) ? 255 : 254));
c = seqan3::to_rank(static_cast<index_alphabet_type>(*it)) + 1;
new_parent_lb = _fwd_lb;
new_parent_rb = _fwd_rb;
if (!bidirectional_search(index->fwd_fm.index, c, _fwd_lb, _fwd_rb, _rev_lb, _rev_rb))
return false;
}
fwd_lb = _fwd_lb;
fwd_rb = _fwd_rb;
rev_lb = _rev_lb;
rev_rb = _rev_rb;
parent_lb = new_parent_lb;
parent_rb = new_parent_rb;
_last_char = c;
depth += len;
return true;
}
template <std::ranges::range seq_t>
bool extend_left(seq_t && seq) noexcept
{
static_assert(std::ranges::bidirectional_range<seq_t>, "The query must model bidirectional_range.");
static_assert(std::convertible_to<range_innermost_value_t<seq_t>, index_alphabet_type>,
"The alphabet of the sequence must be convertible to the alphabet of the index.");
assert(index != nullptr);
auto rev_seq = std::views::reverse(seq);
auto first = std::ranges::begin(rev_seq);
auto last = std::ranges::end(rev_seq);
#ifndef NDEBUG
if (first != last) // only if seq was not empty
fwd_cursor_last_used = false;
#endif
size_type _fwd_lb = fwd_lb, _fwd_rb = fwd_rb, _rev_lb = rev_lb, _rev_rb = rev_rb;
size_type new_parent_lb = parent_lb, new_parent_rb = parent_rb;
sdsl_char_type c = _last_char;
size_t len{0};
for (auto it = first; it != last; ++len, ++it)
{
// The rank cannot exceed 255 for single text and 254 for text collections as they are reserved as sentinels
// for the indexed text.
assert(seqan3::to_rank(static_cast<index_alphabet_type>(*it))
< ((index_type::text_layout_mode == text_layout::single) ? 255 : 254));
c = seqan3::to_rank(static_cast<index_alphabet_type>(*it)) + 1;
new_parent_lb = _rev_lb;
new_parent_rb = _rev_rb;
if (!bidirectional_search(index->rev_fm.index, c, _rev_lb, _rev_rb, _fwd_lb, _fwd_rb))
return false;
}
fwd_lb = _fwd_lb;
fwd_rb = _fwd_rb;
rev_lb = _rev_lb;
rev_rb = _rev_rb;
parent_lb = new_parent_lb;
parent_rb = new_parent_rb;
_last_char = c;
depth += len;
return true;
}
bool cycle_back() noexcept
{
#ifndef NDEBUG
// cycle_back() can only be used if the last extension was to the right.
assert(fwd_cursor_last_used);
#endif
assert(index != nullptr && query_length() > 0);
sdsl_sigma_type c = _last_char + 1;
while (c < sigma
&& !bidirectional_search_cycle(index->fwd_fm.index,
index->fwd_fm.index.comp2char[c],
parent_lb,
parent_rb,
fwd_lb,
fwd_rb,
rev_lb,
rev_rb))
{
++c;
}
if (c != sigma)
{
assert(c <= std::numeric_limits<sdsl_char_type>::max());
_last_char = static_cast<sdsl_char_type>(c);
return true;
}
return false;
}
bool cycle_front() noexcept
{
#ifndef NDEBUG
// cycle_front() can only be used if the last extension was to the left.
assert(!fwd_cursor_last_used);
#endif
assert(index != nullptr && query_length() > 0);
sdsl_sigma_type c = _last_char + 1;
while (c < sigma
&& !bidirectional_search_cycle(index->rev_fm.index,
index->rev_fm.index.comp2char[c],
parent_lb,
parent_rb,
rev_lb,
rev_rb,
fwd_lb,
fwd_rb))
{
++c;
}
if (c != sigma)
{
assert(c <= std::numeric_limits<sdsl_char_type>::max());
_last_char = static_cast<sdsl_char_type>(c);
return true;
}
return false;
}
size_type last_rank() noexcept
{
assert(index != nullptr && query_length() > 0);
return index->fwd_fm.index.comp2char[_last_char] - 1; // text is not allowed to contain ranks of 0
}
size_type query_length() const noexcept
{
assert(index != nullptr);
// depth == 0 -> root node
assert(depth != 0 || (fwd_lb == rev_lb && fwd_rb == rev_rb && fwd_lb == 0 && fwd_rb == index->size() - 1));
return depth;
}
fwd_cursor to_fwd_cursor() const noexcept
{
assert(index != nullptr);
fwd_cursor cur{index->fwd_fm};
cur.parent_lb = parent_lb;
cur.parent_rb = parent_rb;
cur.node = {fwd_lb, fwd_rb, depth, _last_char};
#ifndef NDEBUG
if (!fwd_cursor_last_used)
{
// invalidate parent interval
cur.parent_lb = 1;
cur.parent_rb = 0;
}
#endif
return cur;
}
template <std::ranges::range text_t>
auto path_label(text_t && text) const noexcept
requires (index_t::text_layout_mode == text_layout::single)
{
static_assert(std::ranges::input_range<text_t>, "The text must model input_range.");
static_assert(range_dimension_v<text_t> == 1, "The input cannot be a text collection.");
static_assert(std::same_as<range_innermost_value_t<text_t>, index_alphabet_type>,
"The alphabet types of the given text and index differ.");
assert(index != nullptr);
size_type const query_begin = offset() - index->fwd_fm.index[fwd_lb];
return text | views::slice(query_begin, query_begin + query_length());
}
template <std::ranges::range text_t>
auto path_label(text_t && text) const noexcept
requires (index_t::text_layout_mode == text_layout::collection)
{
static_assert(std::ranges::input_range<text_t>, "The text collection must model input_range.");
static_assert(range_dimension_v<text_t> == 2, "The input must be a text collection.");
static_assert(std::same_as<range_innermost_value_t<text_t>, index_alphabet_type>,
"The alphabet types of the given text and index differ.");
assert(index != nullptr);
// Position of query in concatenated text.
size_type const location = offset() - index->fwd_fm.index[fwd_lb];
// The rank represents the number of start positions of the individual sequences/texts in the collection
// before position `location + 1` and thereby also the number of delimiters.
size_type const rank = index->fwd_fm.text_begin_rs.rank(location + 1);
assert(rank > 0);
size_type const text_id = rank - 1;
// The start location of the `text_id`-th text in the sequence (position of the `rank`-th 1 in the bitvector).
size_type const start_location = index->fwd_fm.text_begin_ss.select(rank);
// Substract lengths of previous sequences.
size_type const query_begin = location - start_location;
// Take subtext, slice query out of it
return text[text_id] | views::slice(query_begin, query_begin + query_length());
}
size_type count() const noexcept
{
assert(index != nullptr && (1 + fwd_rb - fwd_lb == 1 + rev_rb - rev_lb));
return 1 + fwd_rb - fwd_lb;
}
locate_result_type locate() const
requires (index_t::text_layout_mode == text_layout::single)
{
assert(index != nullptr);
locate_result_type occ{};
occ.reserve(count());
for (size_type i = 0; i < count(); ++i)
{
occ.emplace_back(0, offset() - index->fwd_fm.index[fwd_lb + i]);
}
return occ;
}
std::vector<std::pair<size_type, size_type>> locate() const
requires (index_t::text_layout_mode == text_layout::collection)
{
assert(index != nullptr);
std::vector<std::pair<size_type, size_type>> occ;
occ.reserve(count());
for (size_type i = 0; i < count(); ++i)
{
size_type loc = offset() - index->fwd_fm.index[fwd_lb + i];
size_type sequence_rank = index->fwd_fm.text_begin_rs.rank(loc + 1);
size_type sequence_position = loc - index->fwd_fm.text_begin_ss.select(sequence_rank);
occ.emplace_back(sequence_rank - 1, sequence_position);
}
return occ;
}
auto lazy_locate() const
requires (index_t::text_layout_mode == text_layout::single)
{
assert(index != nullptr);
return std::views::iota(fwd_lb, fwd_lb + count())
| std::views::transform(
[*this, _offset = offset()](auto sa_pos)
{
return locate_result_value_type{0u, _offset - index->fwd_fm.index[sa_pos]};
});
}
auto lazy_locate() const
requires (index_t::text_layout_mode == text_layout::collection)
{
assert(index != nullptr);
return std::views::iota(fwd_lb, fwd_lb + count())
| std::views::transform(
[*this, _offset = offset()](auto sa_pos)
{
auto loc = _offset - index->fwd_fm.index[sa_pos];
size_type sequence_rank = index->fwd_fm.text_begin_rs.rank(loc + 1);
size_type sequence_position = loc - index->fwd_fm.text_begin_ss.select(sequence_rank);
return locate_result_value_type{sequence_rank - 1, sequence_position};
});
}
template <cereal_archive archive_t>
void CEREAL_SERIALIZE_FUNCTION_NAME(archive_t & archive)
{
archive(fwd_lb);
archive(fwd_rb);
archive(rev_lb);
archive(rev_rb);
archive(sigma);
archive(parent_lb);
archive(parent_rb);
archive(_last_char);
archive(depth);
}
};
} // namespace seqan3
concept.hpp
Core alphabet concept and free function/type trait wrappers.
array
std::basic_string_view
char.hpp
Provides alphabet adaptations for standard char types.
seqan3::bi_fm_index_cursor::extend_right
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:327
seqan3::bi_fm_index_cursor::count
size_type count() const noexcept
Counts the number of occurrences of the searched query in the text.
Definition bi_fm_index_cursor.hpp:927
seqan3::bi_fm_index_cursor::extend_left
bool extend_left(seq_t &&seq) noexcept
Tries to extend the query by seq to the left.
Definition bi_fm_index_cursor.hpp:605
seqan3::bi_fm_index_cursor::operator==
bool operator==(bi_fm_index_cursor const &rhs) const noexcept
Compares two cursors.
Definition bi_fm_index_cursor.hpp:281
seqan3::bi_fm_index_cursor::extend_left
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
seqan3::bi_fm_index_cursor::path_label
auto path_label(text_t &&text) const noexcept
Returns the searched query.
Definition bi_fm_index_cursor.hpp:874
seqan3::bi_fm_index_cursor::extend_left
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:380
seqan3::bi_fm_index_cursor::path_label
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 bi_fm_index_cursor.hpp:889
seqan3::bi_fm_index_cursor::locate
locate_result_type locate() const
Locates the occurrences of the searched query in the text.
Definition bi_fm_index_cursor.hpp:945
seqan3::bi_fm_index_cursor::cycle_back
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:680
seqan3::bi_fm_index_cursor::cycle_front
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:740
seqan3::bi_fm_index_cursor::lazy_locate
auto lazy_locate() const
This is an overloaded member function, provided for convenience. It differs from the above function o...
Definition bi_fm_index_cursor.hpp:1003
seqan3::bi_fm_index_cursor::to_fwd_cursor
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:836
seqan3::bi_fm_index_cursor::query_length
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:808
seqan3::bi_fm_index_cursor::extend_right
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:462
seqan3::bi_fm_index_cursor::last_rank
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:789
seqan3::bi_fm_index_cursor< bi_fm_index >::index_type
bi_fm_index index_type
Definition bi_fm_index_cursor.hpp:54
seqan3::bi_fm_index_cursor< bi_fm_index >::fwd_cursor
fm_index_cursor< fm_index< typename index_type::alphabet_type, index_type::text_layout_mode, typename index_type::sdsl_index_type > > fwd_cursor
Definition bi_fm_index_cursor.hpp:67
seqan3::bi_fm_index_cursor< bi_fm_index >::size_type
typename index_type::size_type size_type
Definition bi_fm_index_cursor.hpp:60
seqan3::bi_fm_index_cursor::operator!=
bool operator!=(bi_fm_index_cursor const &rhs) const noexcept
Compares two cursors.
Definition bi_fm_index_cursor.hpp:303
seqan3::bi_fm_index_cursor::locate
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:960
seqan3::bi_fm_index_cursor::bi_fm_index_cursor
bi_fm_index_cursor() noexcept=default
Default constructor. Accessing member functions on a default constructed object is undefined behavior...
seqan3::bi_fm_index_cursor::lazy_locate
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
seqan3::bi_fm_index_cursor::extend_right
bool extend_right(seq_t &&seq) noexcept
Tries to extend the query by seq to the right.
Definition bi_fm_index_cursor.hpp:535
seqan3::bi_fm_index_cursor::extend_right
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:431
seqan3::bi_fm_index_cursor::extend_left
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:482
seqan3::bi_fm_index::text_layout_mode
static constexpr text_layout text_layout_mode
Indicates whether index is built over a collection.
Definition bi_fm_index.hpp:126
seqan3::bi_fm_index::size_type
typename sdsl_index_type::size_type size_type
Type for representing positions in the indexed text.
Definition bi_fm_index.hpp:134
seqan3::bi_fm_index::alphabet_type
typename fm_index_type::alphabet_type alphabet_type
The type of the underlying character of the indexed text.
Definition bi_fm_index.hpp:132
seqan3::fm_index_cursor
The SeqAn FM Index Cursor.
Definition fm_index_cursor.hpp:83
seqan3::fm_index
The SeqAn FM Index.
Definition fm_index.hpp:185
type_traits.hpp
Provides various transformation traits used by the range module.
std::vector::emplace_back
T emplace_back(T... args)
fm_index.hpp
Provides the unidirectional seqan3::fm_index.
fm_index_cursor.hpp
Provides the seqan3::fm_index_cursor for searching in the unidirectional seqan3::fm_index.
seqan3::to_rank
constexpr auto to_rank
Return the rank representation of a (semi-)alphabet object.
Definition alphabet/concept.hpp:152
seqan3::range_dimension_v
constexpr size_t range_dimension_v
Returns the number of times you can call seqan3::value_type_t recursively on t (type trait).
Definition core/range/type_traits.hpp:112
seqan3::field::seq
@ seq
The "sequence", usually a range of nucleotides or amino acids.
Definition record.hpp:62
seqan3::text_layout
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
seqan3::single
@ single
The text is a single range.
Definition search/fm_index/concept.hpp:71
seqan3::collection
@ collection
The text is a range of ranges.
Definition search/fm_index/concept.hpp:73
seqan3::views::slice
constexpr auto slice
A view adaptor that returns a half-open interval on the underlying range.
Definition slice.hpp:137
std::numeric_limits::max
T max(T... args)
seqan3
The main SeqAn3 namespace.
Definition aligned_sequence_concept.hpp:26
std::pair
std::vector::reserve
T reserve(T... args)
slice.hpp
Provides seqan3::views::slice.
std::tie
T tie(T... args)
uint.hpp
Provides alphabet adaptations for standard uint types.
std::vector
Hide me