21 namespace seqan3::detail
31 template <
typename word_t,
bool is_semi_global,
bool use_max_errors>
32 class edit_distance_trace_matrix_full
36 template <std::ranges::viewable_range database_t,
37 std::ranges::viewable_range query_t,
38 typename align_config_t,
40 friend class edit_distance_unbanded;
45 edit_distance_trace_matrix_full() =
default;
46 edit_distance_trace_matrix_full(edit_distance_trace_matrix_full
const &) =
default;
47 edit_distance_trace_matrix_full(edit_distance_trace_matrix_full &&) =
default;
48 edit_distance_trace_matrix_full & operator=(edit_distance_trace_matrix_full
const &) =
default;
49 edit_distance_trace_matrix_full & operator=(edit_distance_trace_matrix_full &&) =
default;
50 ~edit_distance_trace_matrix_full() =
default;
54 template <
typename derived_t,
typename edit_traits>
55 friend class edit_distance_unbanded_trace_matrix_policy;
60 edit_distance_trace_matrix_full(
size_t const rows_size)
61 : rows_size{rows_size}, columns{}
66 struct trace_path_iterator;
70 using word_type = word_t;
73 static constexpr
auto word_size = bits_of<word_type>;
76 using value_type = detail::trace_directions;
79 using reference = value_type;
82 using size_type = size_t;
92 void reserve(
size_t const new_capacity)
94 columns.reserve(new_capacity);
99 reference
at(matrix_coordinate
const & coordinate)
const noexcept
101 size_t row = coordinate.row;
102 size_t col = coordinate.col;
104 assert(row < rows());
105 assert(col < cols());
107 column_type
const & column = columns[col];
109 if constexpr(use_max_errors)
110 if (!(row < column.max_rows))
115 if constexpr(is_semi_global)
121 return detail::trace_directions::left;
124 size_t const idx = (row - 1u) / word_size;
125 size_t const offset = (row - 1u) % word_size;
139 size_t rows() const noexcept
145 size_t cols() const noexcept
147 return columns.
size();
156 auto trace_path(matrix_coordinate
const & trace_begin)
const
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>;
162 return path_t{trace_path_iterator{
this, trace_begin}, std::default_sentinel};
167 struct max_errors_state
175 struct trace_matrix_state
187 enable_state_t<true, trace_matrix_state>,
188 enable_state_t<use_max_errors, max_errors_state>
198 requires (!use_max_errors)
201 column_type column{};
216 size_t const max_rows)
218 requires use_max_errors
221 column_type column{};
225 column.max_rows = max_rows;
251 template <
typename word_t,
bool is_semi_global,
bool use_max_errors>
252 struct edit_distance_trace_matrix_full<word_t, is_semi_global, use_max_errors>::trace_path_iterator
260 using value_type = detail::trace_directions;
266 constexpr
static value_type D = value_type::diagonal;
268 constexpr
static value_type L = value_type::left;
270 constexpr
static value_type U = value_type::up;
272 constexpr
static value_type N = value_type::none;
278 constexpr value_type operator*()
const
280 value_type dir = parent->at(coordinate());
287 else if ((dir & U) == U)
294 [[nodiscard]] constexpr matrix_coordinate
const & coordinate()
const
304 constexpr trace_path_iterator & operator++()
306 value_type dir = *(*this);
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);
331 constexpr
void operator++(
int)
341 friend bool operator==(trace_path_iterator
const & it, std::default_sentinel_t)
343 return *it == value_type::none;
347 friend bool operator==(std::default_sentinel_t, trace_path_iterator
const & it)
349 return it == std::default_sentinel;
353 friend bool operator!=(trace_path_iterator
const & it, std::default_sentinel_t)
355 return !(it == std::default_sentinel);
359 friend bool operator!=(std::default_sentinel_t, trace_path_iterator
const & it)
361 return it != std::default_sentinel;
366 edit_distance_trace_matrix_full
const * parent{
nullptr};
368 matrix_coordinate coordinate_{};
Provides utility functions for bit twiddling.
Forwards for seqan3::edit_distance_unbanded related types.
@ offset
Sequence (seqan3::field::seq) relative start position (0-based), unsigned value.
@ none
No flag is set.
Definition: debug_stream_type.hpp:32
typename decltype(detail::at< idx >(list_t{}))::type at
Return the type at given index from the type list.
Definition: traits.hpp:260
auto const move
A view that turns lvalue-references into rvalue-references.
Definition: move.hpp:74
Provides the declaration of seqan3::detail::trace_directions.