18namespace seqan3::detail
28template <
typename word_t,
bool is_semi_global,
bool use_max_errors>
29class edit_distance_trace_matrix_full
33 template <std::ranges::viewable_range database_t,
34 std::ranges::viewable_range query_t,
35 typename align_config_t,
37 friend class edit_distance_unbanded;
42 edit_distance_trace_matrix_full() =
default;
43 edit_distance_trace_matrix_full(edit_distance_trace_matrix_full
const &) =
default;
44 edit_distance_trace_matrix_full(edit_distance_trace_matrix_full &&) =
default;
45 edit_distance_trace_matrix_full & operator=(edit_distance_trace_matrix_full
const &) =
default;
46 edit_distance_trace_matrix_full & operator=(edit_distance_trace_matrix_full &&) =
default;
47 ~edit_distance_trace_matrix_full() =
default;
51 template <
typename derived_t,
typename edit_traits>
52 friend class edit_distance_unbanded_trace_matrix_policy;
57 edit_distance_trace_matrix_full(
size_t const rows_size) : rows_size{rows_size}, columns{}
62 struct trace_path_iterator;
66 using word_type = word_t;
69 static constexpr auto word_size = bits_of<word_type>;
72 using value_type = detail::trace_directions;
75 using reference = value_type;
78 using size_type = size_t;
88 void reserve(
size_t const new_capacity)
90 columns.reserve(new_capacity);
95 reference
at(matrix_coordinate
const & coordinate)
const noexcept
97 size_t row = coordinate.row;
98 size_t col = coordinate.col;
100 assert(row < rows());
101 assert(col < cols());
103 column_type
const & column = columns[col];
105 if constexpr (use_max_errors)
106 if (!(row < column.max_rows))
107 return detail::trace_directions::none;
111 if constexpr (is_semi_global)
112 return detail::trace_directions::none;
115 return detail::trace_directions::none;
117 return detail::trace_directions::left;
120 size_t const idx = (row - 1u) / word_size;
121 size_t const offset = (row - 1u) % word_size;
127 auto const dir = (
left ? detail::trace_directions::left : detail::trace_directions::none)
128 | (diagonal ? detail::trace_directions::diagonal : detail::trace_directions::none)
129 | (up ? detail::trace_directions::up : detail::trace_directions::none);
135 size_t rows() const noexcept
141 size_t cols() const noexcept
143 return columns.
size();
152 auto trace_path(matrix_coordinate
const & trace_begin)
const
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>;
158 return path_t{trace_path_iterator{
this, trace_begin}, std::default_sentinel};
163 struct max_errors_state
171 struct trace_matrix_state
182 struct column_type : enable_state_t<true, trace_matrix_state>, enable_state_t<use_max_errors, max_errors_state>
191 requires (!use_max_errors)
193 column_type column{};
194 column.left = std::move(left);
195 column.diagonal = std::move(diagonal);
196 column.up = std::move(up);
198 columns.push_back(std::move(column));
210 size_t const max_rows)
211 requires use_max_errors
213 column_type column{};
214 column.left = std::move(left);
215 column.diagonal = std::move(diagonal);
216 column.up = std::move(up);
217 column.max_rows = max_rows;
219 columns.push_back(std::move(column));
243template <
typename word_t,
bool is_semi_global,
bool use_max_errors>
244struct edit_distance_trace_matrix_full<word_t, is_semi_global, use_max_errors>::trace_path_iterator
252 using value_type = detail::trace_directions;
258 static constexpr value_type D = value_type::diagonal;
260 static constexpr value_type L = value_type::left;
262 static constexpr value_type U = value_type::up;
264 static constexpr value_type N = value_type::none;
270 constexpr value_type operator*()
const
272 value_type dir = parent->at(coordinate());
279 else if ((dir & U) == U)
286 [[nodiscard]]
constexpr matrix_coordinate
const & coordinate()
const
296 constexpr trace_path_iterator & operator++()
298 value_type dir = *(*this);
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);
323 constexpr void operator++(
int)
333 friend bool operator==(trace_path_iterator
const & it, std::default_sentinel_t)
335 return *it == value_type::none;
339 friend bool operator==(std::default_sentinel_t, trace_path_iterator
const & it)
341 return it == std::default_sentinel;
345 friend bool operator!=(trace_path_iterator
const & it, std::default_sentinel_t)
347 return !(it == std::default_sentinel);
351 friend bool operator!=(std::default_sentinel_t, trace_path_iterator
const & it)
353 return it != std::default_sentinel;
358 edit_distance_trace_matrix_full
const * parent{
nullptr};
360 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.
typename decltype(detail::at< idx >(list_t{}))::type at
Return the type at given index from the type list.
Definition type_list/traits.hpp:276
Provides the declaration of seqan3::detail::trace_directions.