31template <
typename word_t,
bool is_semi_global,
bool use_max_errors>
36 template <std::ranges::viewable_range database_t,
37 std::ranges::viewable_range query_t,
38 typename align_config_t,
54 template <
typename derived_t,
typename edit_traits>
66 struct trace_path_iterator;
73 static constexpr auto word_size = bits_of<word_type>;
99 reference at(matrix_coordinate
const & coordinate)
const noexcept
101 size_t row = coordinate.row;
102 size_t col = coordinate.col;
105 assert(col <
cols());
109 if constexpr(use_max_errors)
115 if constexpr(is_semi_global)
158 if (trace_begin.row >=
rows() || trace_begin.col >=
cols())
159 throw std::invalid_argument{
"The given coordinate exceeds the matrix in vertical or horizontal direction."};
161 using path_t = std::ranges::subrange<trace_path_iterator, std::default_sentinel_t>;
198 requires (!use_max_errors)
202 column.left = std::move(left);
216 size_t const max_rows)
218 requires use_max_errors
222 column.left = std::move(left);
225 column.max_rows = max_rows;
251template <
typename word_t,
bool is_semi_global,
bool use_max_errors>
287 else if ((dir & U) == U)
294 [[nodiscard]]
constexpr matrix_coordinate
const &
coordinate()
const
310 coordinate_.col = std::max<size_t>(coordinate_.col, 1) - 1;
312 else if ((dir & U) == U)
314 coordinate_.row = std::max<size_t>(coordinate_.row, 1) - 1;
316 else if ((dir & D) == D)
318 coordinate_.row = std::max<size_t>(coordinate_.row, 1) - 1;
319 coordinate_.col = std::max<size_t>(coordinate_.col, 1) - 1;
325 assert(dir != N || coordinate_.row == 0 || coordinate_.col == 0);
349 return it == std::default_sentinel;
355 return !(it == std::default_sentinel);
361 return it != std::default_sentinel;
368 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:33
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:92
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:76
size_t rows_size
The number of rows in the matrix.
Definition: edit_distance_trace_matrix_full.hpp:232
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:156
size_t size_type
The size type of the matrix.
Definition: edit_distance_trace_matrix_full.hpp:82
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:196
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:99
std::vector< column_type > columns
The columns of the trace matrix.
Definition: edit_distance_trace_matrix_full.hpp:234
size_t cols() const noexcept
The number of columns in the matrix.
Definition: edit_distance_trace_matrix_full.hpp:145
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:215
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:60
size_t rows() const noexcept
The number of rows in the matrix.
Definition: edit_distance_trace_matrix_full.hpp:139
static constexpr auto word_size
The size of one machine word.
Definition: edit_distance_trace_matrix_full.hpp:73
edit_distance_trace_matrix_full()=default
Defaulted.
~edit_distance_trace_matrix_full()=default
Defaulted.
word_t word_type
The type of one machine word.
Definition: edit_distance_trace_matrix_full.hpp:70
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:503
This calculates an alignment using the edit distance and without a band.
Definition: edit_distance_unbanded.hpp:720
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:29
@ 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:29
The state of one computation step.
Definition: edit_distance_trace_matrix_full.hpp:189
If use_max_errors is true store these additional state information in state_type.
Definition: edit_distance_trace_matrix_full.hpp:168
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:171
This information is needed to infer the trace matrix.
Definition: edit_distance_trace_matrix_full.hpp:176
std::vector< word_type > left
Machine words which represent the trace_direction::left.
Definition: edit_distance_trace_matrix_full.hpp:178
std::vector< word_type > diagonal
Machine words which represent the trace_direction::diagonal.
Definition: edit_distance_trace_matrix_full.hpp:180
std::vector< word_type > up
Machine words which represent the trace_direction::up.
Definition: edit_distance_trace_matrix_full.hpp:182
The iterator needed to implement seqan3::detail::edit_distance_trace_matrix_full::trace_path.
Definition: edit_distance_trace_matrix_full.hpp:253
friend bool operator!=(trace_path_iterator const &it, std::default_sentinel_t)
Returns true if the pointed-to-element is not seqan3::detail::trace_directions::none.
Definition: edit_distance_trace_matrix_full.hpp:353
constexpr void operator++(int)
Advances the iterator by one.
Definition: edit_distance_trace_matrix_full.hpp:331
constexpr trace_path_iterator & operator++()
Advances the iterator by one.
Definition: edit_distance_trace_matrix_full.hpp:304
constexpr value_type operator*() const
Returns the current trace direction.
Definition: edit_distance_trace_matrix_full.hpp:278
constexpr matrix_coordinate const & coordinate() const
Returns the current coordinate in two-dimensional space.
Definition: edit_distance_trace_matrix_full.hpp:294
friend bool operator==(trace_path_iterator const &it, std::default_sentinel_t)
Returns true if the pointed-to-element is seqan3::detail::trace_directions::none.
Definition: edit_distance_trace_matrix_full.hpp:341
friend bool operator==(std::default_sentinel_t, trace_path_iterator const &it)
Returns true if the pointed-to-element is seqan3::detail::trace_directions::none.
Definition: edit_distance_trace_matrix_full.hpp:347
friend bool operator!=(std::default_sentinel_t, trace_path_iterator const &it)
Returns true if the pointed-to-element is not seqan3::detail::trace_directions::none.
Definition: edit_distance_trace_matrix_full.hpp:359
Provides the declaration of seqan3::detail::trace_directions.