17 #include <range/v3/view/iota.hpp> 18 #include <range/v3/view/zip.hpp> 33 template <
typename derived_t,
typename score_allocator_t,
typename trace_allocator_t>
34 class banded_score_trace_dp_matrix_policy :
35 public banded_score_dp_matrix_policy<banded_score_trace_dp_matrix_policy<derived_t,
43 using base_t = banded_score_dp_matrix_policy<banded_score_trace_dp_matrix_policy<derived_t,
52 using base_t::score_matrix;
53 using base_t::dimension_first_range;
54 using base_t::dimension_second_range;
55 using base_t::current_column_index;
56 using base_t::current_matrix_iter;
57 using base_t::band_column_index;
58 using base_t::band_row_index;
59 using base_t::band_size;
62 using base_t::current_band_size;
63 using base_t::second_range_begin_offset;
64 using base_t::band_touches_last_row;
65 using base_t::trim_sequences;
66 using base_t::map_banded_coordinate_to_range_position;
71 using cell_type =
typename score_allocator_t::value_type;
74 using trace_type =
typename trace_allocator_t::value_type;
84 constexpr banded_score_trace_dp_matrix_policy() =
default;
85 constexpr banded_score_trace_dp_matrix_policy(banded_score_trace_dp_matrix_policy
const &) =
default;
86 constexpr banded_score_trace_dp_matrix_policy(banded_score_trace_dp_matrix_policy &&) =
default;
87 constexpr banded_score_trace_dp_matrix_policy & operator=(banded_score_trace_dp_matrix_policy
const &) =
default;
90 constexpr banded_score_trace_dp_matrix_policy & operator=(banded_score_trace_dp_matrix_policy &&) =
default;
91 ~banded_score_trace_dp_matrix_policy() =
default;
102 template <
typename first_range_t,
typename second_range_t,
typename band_t>
103 constexpr
void allocate_matrix(first_range_t & first_range, second_range_t & second_range, band_t
const & band)
105 base_t::allocate_matrix(first_range, second_range, band);
107 trace_matrix.resize(band_size * dimension_first_range);
112 constexpr
auto current_column() noexcept
114 auto span = base_t::current_band_size();
120 advanceable_alignment_coordinate<advanceable_alignment_coordinate_state::row>
121 col_begin{column_index_type{current_column_index},
123 current_matrix_iter))}};
124 advanceable_alignment_coordinate<advanceable_alignment_coordinate_state::row>
125 col_end{column_index_type{current_column_index}, row_index_type{col_begin.second + span}};
136 constexpr
void go_next_column() noexcept
138 base_t::go_next_column();
140 trace_matrix_iter =
std::ranges::begin(trace_matrix) + band_size * current_column_index;
142 if (current_column_index < band_column_index)
143 trace_matrix_iter += band_column_index - current_column_index;
152 constexpr
auto parse_traceback(alignment_coordinate
const & back_coordinate)
const 161 back_coordinate.second);
164 while (*direction_iter != trace_directions::none)
167 while (static_cast<bool>(*direction_iter & trace_directions::diagonal))
174 if (static_cast<bool>(*direction_iter & trace_directions::up) ||
175 static_cast<bool>(*direction_iter & trace_directions::up_open))
179 gap_segment gap{col_pos, 0u};
182 while (!static_cast<bool>(*direction_iter & trace_directions::up_open))
191 first_segments.push_front(std::move(gap));
195 if (static_cast<bool>(*direction_iter & trace_directions::left) ||
196 static_cast<bool>(*direction_iter & trace_directions::left_open))
200 static_cast<int_fast32_t
>(col_pos - band_column_index);
201 gap_segment gap{pos, 0u};
204 while (!static_cast<bool>(*direction_iter & trace_directions::left_open))
212 second_segments.push_front(std::move(gap));
217 auto c = column_index_type{
220 auto r = row_index_type{
225 auto front_coordinate = map_banded_coordinate_to_range_position(
226 alignment_coordinate{column_index_type{c}, row_index_type{r}});
227 assert(front_coordinate.first >= 0u);
228 assert(front_coordinate.first <= back_coordinate.first);
230 assert(front_coordinate.second >= 0u);
231 assert(front_coordinate.second <= map_banded_coordinate_to_range_position(back_coordinate).second);
233 return std::tuple{front_coordinate, first_segments, second_segments};
237 constexpr
void print_trace_matrix()
const 239 auto printable = [](trace_directions dir)
242 if (dir == trace_directions::none)
244 if ((dir & trace_directions::diagonal) == trace_directions::diagonal)
246 if ((dir & trace_directions::up) == trace_directions::up)
248 if ((dir & trace_directions::up_open) == trace_directions::up_open)
250 if ((dir & trace_directions::left) == trace_directions::left)
252 if ((dir & trace_directions::left_open) == trace_directions::left_open)
258 for (
size_t col = 0; col < band_column_index; ++col)
260 auto it =
std::ranges::begin(trace_matrix) + (band_size * col) + (band_column_index - col);
261 for (
size_t row = 0; row <=
std::min(dimension_second_range - 1, band_row_index + col); ++row, ++it)
269 for (
size_t col = band_column_index; col < dimension_first_range; ++col)
271 for (
size_t padding = 0; padding < col - band_column_index; ++padding)
275 for (
size_t row = 0; row < band_size; ++row, ++it)
278 if (col - band_column_index + row >= dimension_second_range)
287 trace_matrix_type trace_matrix{};
::ranges::distance distance
Alias for ranges::distance. Returns the number of hops from first to last.
Definition: iterator:321
Provides seqan3::detail::unbanded_score_trace_dp_matrix.
constexpr sequenced_policy seq
Global execution policy object for sequenced execution policy.
Definition: execution.hpp:54
constexpr auto zip
A range adaptor that transforms a tuple of range into a range of tuples.
Definition: ranges:948
debug_stream_type debug_stream
A global instance of seqan3::debug_stream_type.
Definition: debug_stream.hpp:249
::ranges::iterator_t iterator_t
Alias for ranges::iterator_t. Obtains the iterator type of a range.
Definition: ranges:204
::ranges::begin begin
Alias for ranges::begin. Returns an iterator to the beginning of a range.
Definition: ranges:174
::ranges::advance advance
Alias for ranges::advance. Advances the iterator by the given distance.
Definition: iterator:316
Provides std::span from the C++20 standard library.
constexpr auto iota
Generates a sequence of elements by repeatedly incrementing an initial value.
Definition: ranges:647
Provides seqan3::detail::banded_score_dp_matrix_policy.
Definition: aligned_sequence_concept.hpp:35
Provides seqan3::detail::alignment_coordinate.