28template <
typename word_t,
bool is_semi_global,
bool use_max_errors>
33 template <std::ranges::viewable_range database_t,
34 std::ranges::viewable_range query_t,
35 typename align_config_t,
51 template <
typename derived_t,
typename edit_traits>
62 struct trace_path_iterator;
69 static constexpr auto word_size = bits_of<word_type>;
95 reference at(matrix_coordinate
const & coordinate)
const noexcept
97 size_t row = coordinate.row;
98 size_t col = coordinate.col;
101 assert(col <
cols());
105 if constexpr (use_max_errors)
111 if constexpr (is_semi_global)
154 if (trace_begin.row >=
rows() || trace_begin.col >=
cols())
155 throw std::invalid_argument{
"The given coordinate exceeds the matrix in vertical or horizontal direction."};
157 using path_t = std::ranges::subrange<trace_path_iterator, std::default_sentinel_t>;
191 requires (!use_max_errors)
210 size_t const max_rows)
211 requires use_max_errors
217 column.max_rows = max_rows;
243template <
typename word_t,
bool is_semi_global,
bool use_max_errors>
279 else if ((dir & U) == U)
286 [[nodiscard]]
constexpr matrix_coordinate
const &
coordinate()
const
302 coordinate_.col = std::max<size_t>(coordinate_.col, 1) - 1;
304 else if ((dir & U) == U)
306 coordinate_.row = std::max<size_t>(coordinate_.row, 1) - 1;
308 else if ((dir & D) == D)
310 coordinate_.row = std::max<size_t>(coordinate_.row, 1) - 1;
311 coordinate_.col = std::max<size_t>(coordinate_.col, 1) - 1;
317 assert(dir != N || coordinate_.row == 0 || coordinate_.col == 0);
335 return *it == value_type::none;
341 return it == std::default_sentinel;
347 return !(it == std::default_sentinel);
353 return it != std::default_sentinel;
360 matrix_coordinate coordinate_{};
Provides utility functions for bit twiddling.
The underlying data structure of seqan3::detail::edit_distance_unbanded that represents the trace mat...
Definition edit_distance_trace_matrix_full.hpp:30
edit_distance_trace_matrix_full(edit_distance_trace_matrix_full const &)=default
Defaulted.
void reserve(size_t const new_capacity)
Increase the capacity of the columns to a value that's greater or equal to new_capacity.
Definition edit_distance_trace_matrix_full.hpp:88
edit_distance_trace_matrix_full & operator=(edit_distance_trace_matrix_full &&)=default
Defaulted.
detail::trace_directions value_type
The type of an entry in the matrix.
Definition edit_distance_trace_matrix_full.hpp:72
size_t rows_size
The number of rows in the matrix.
Definition edit_distance_trace_matrix_full.hpp:224
auto trace_path(matrix_coordinate const &trace_begin) const
Returns a trace path starting from the given coordinate and ending in the cell with seqan3::detail::t...
Definition edit_distance_trace_matrix_full.hpp:152
size_t size_type
The size type of the matrix.
Definition edit_distance_trace_matrix_full.hpp:78
edit_distance_trace_matrix_full & operator=(edit_distance_trace_matrix_full const &)=default
Defaulted.
reference at(matrix_coordinate const &coordinate) const noexcept
A reference to the entry of the matrix at the given coordinate.
Definition edit_distance_trace_matrix_full.hpp:95
std::vector< column_type > columns
The columns of the trace matrix.
Definition edit_distance_trace_matrix_full.hpp:226
size_t cols() const noexcept
The number of columns in the matrix.
Definition edit_distance_trace_matrix_full.hpp:141
edit_distance_trace_matrix_full(size_t const rows_size)
Construct the score_matrix by giving the number of rows within the matrix.
Definition edit_distance_trace_matrix_full.hpp:57
size_t rows() const noexcept
The number of rows in the matrix.
Definition edit_distance_trace_matrix_full.hpp:135
void add_column(std::vector< word_type > left, std::vector< word_type > diagonal, std::vector< word_type > up, size_t const max_rows)
Adds a column to the trace matrix.
Definition edit_distance_trace_matrix_full.hpp:207
static constexpr auto word_size
The size of one machine word.
Definition edit_distance_trace_matrix_full.hpp:69
edit_distance_trace_matrix_full()=default
Defaulted.
~edit_distance_trace_matrix_full()=default
Defaulted.
void add_column(std::vector< word_type > left, std::vector< word_type > diagonal, std::vector< word_type > up)
Adds a column to the trace matrix.
Definition edit_distance_trace_matrix_full.hpp:190
word_t word_type
The type of one machine word.
Definition edit_distance_trace_matrix_full.hpp:66
edit_distance_trace_matrix_full(edit_distance_trace_matrix_full &&)=default
Defaulted.
Only available when default_edit_distance_trait_type::compute_trace_matrix is true.
Definition edit_distance_unbanded.hpp:499
This calculates an alignment using the edit distance and without a band.
Definition edit_distance_unbanded.hpp:711
Forwards for seqan3::edit_distance_unbanded related types.
trace_directions
The possible directions a trace can have. The values can be combined by the logical |-operator.
Definition trace_directions.hpp:26
@ column
The corresponding alignment coordinate will be incrementable/decrementable in the column index.
@ row
The corresponding alignment coordinate will be incrementable/decrementable in the row index.
@ up
Trace comes from the above entry.
@ left
Trace comes from the left entry.
@ diagonal
Trace comes from the diagonal entry.
@ offset
Sequence (seqan3::field::seq) relative start position (0-based), unsigned value.
The internal SeqAn3 namespace.
Definition aligned_sequence_concept.hpp:26
The state of one computation step.
Definition edit_distance_trace_matrix_full.hpp:183
If use_max_errors is true store these additional state information in state_type.
Definition edit_distance_trace_matrix_full.hpp:164
size_t max_rows
The number of max_rows within the current column. Computed by seqan3::detail::edit_distance_score_mat...
Definition edit_distance_trace_matrix_full.hpp:167
This information is needed to infer the trace matrix.
Definition edit_distance_trace_matrix_full.hpp:172
std::vector< word_type > left
Machine words which represent the trace_direction::left.
Definition edit_distance_trace_matrix_full.hpp:174
std::vector< word_type > diagonal
Machine words which represent the trace_direction::diagonal.
Definition edit_distance_trace_matrix_full.hpp:176
std::vector< word_type > up
Machine words which represent the trace_direction::up.
Definition edit_distance_trace_matrix_full.hpp:178
The iterator needed to implement seqan3::detail::edit_distance_trace_matrix_full::trace_path.
Definition edit_distance_trace_matrix_full.hpp:245
friend bool operator!=(trace_path_iterator const &it, std::default_sentinel_t)
Returns true if both iterators are not equal, false otherwise.
Definition edit_distance_trace_matrix_full.hpp:345
constexpr void operator++(int)
Advances the iterator by one.
Definition edit_distance_trace_matrix_full.hpp:323
constexpr trace_path_iterator & operator++()
Advances the iterator by one.
Definition edit_distance_trace_matrix_full.hpp:296
constexpr value_type operator*() const
Returns the current trace direction.
Definition edit_distance_trace_matrix_full.hpp:270
constexpr matrix_coordinate const & coordinate() const
Returns the current coordinate in two-dimensional space.
Definition edit_distance_trace_matrix_full.hpp:286
friend bool operator==(trace_path_iterator const &it, std::default_sentinel_t)
Returns true if both iterators are equal, false otherwise.
Definition edit_distance_trace_matrix_full.hpp:333
friend bool operator==(std::default_sentinel_t, trace_path_iterator const &it)
Returns true if both iterators are equal, false otherwise.
Definition edit_distance_trace_matrix_full.hpp:339
friend bool operator!=(std::default_sentinel_t, trace_path_iterator const &it)
Returns true if both iterators are not equal, false otherwise.
Definition edit_distance_trace_matrix_full.hpp:351
Provides the declaration of seqan3::detail::trace_directions.