18 #include <range/v3/view/repeat_n.hpp> 36 template <
typename derived_t,
typename allocator_type>
37 class banded_score_dp_matrix_policy :
38 public unbanded_score_dp_matrix_policy<banded_score_dp_matrix_policy<derived_t, allocator_type>, allocator_type>
43 using base_t = unbanded_score_dp_matrix_policy<banded_score_dp_matrix_policy<derived_t, allocator_type>, allocator_type>;
51 using cell_type =
typename base_t::cell_type;
54 using score_matrix_type =
typename base_t::score_matrix_type;
58 static constexpr std::tuple_element_t<0, cell_type> INF =
64 constexpr banded_score_dp_matrix_policy() =
default;
65 constexpr banded_score_dp_matrix_policy(banded_score_dp_matrix_policy
const &) =
default;
66 constexpr banded_score_dp_matrix_policy(banded_score_dp_matrix_policy &&) =
default;
67 constexpr banded_score_dp_matrix_policy & operator=(banded_score_dp_matrix_policy
const &) =
default;
68 constexpr banded_score_dp_matrix_policy & operator=(banded_score_dp_matrix_policy &&) =
default;
69 ~banded_score_dp_matrix_policy() =
default;
82 template <
typename first_range_t,
typename second_range_t,
typename band_t>
83 constexpr
void allocate_matrix(first_range_t & first_range, second_range_t & second_range, band_t
const & band)
89 band_column_index =
std::max(static_cast<uint_fast32_t>(band.upper_bound), static_cast<uint_fast32_t>(0));
91 band_row_index = std::abs(
std::min(static_cast<int_fast32_t>(band.lower_bound),
92 static_cast<int_fast32_t>(0)));
95 band_column_index =
std::min(band_column_index, static_cast<uint_fast32_t>(dimension_second_range - 1));
96 band_row_index =
std::min(band_row_index, static_cast<uint_fast32_t>(dimension_first_range - 1));
98 band_size = band_column_index + band_row_index + 1;
102 score_matrix.resize(band_size + 1);
105 get<0>(score_matrix.back()) = INF;
106 get<1>(score_matrix.back()) = INF;
107 get<2>(score_matrix.back()) = trace_directions::none;
108 current_column_index = 0;
114 constexpr
auto current_column() noexcept
116 auto span = 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
139 base_t::go_next_column();
142 --current_matrix_iter;
146 constexpr uint_fast32_t current_band_size() const noexcept
149 int_fast32_t remaining_column_size =
150 static_cast<int_fast32_t
>(dimension_second_range) -
151 std::max(static_cast<int_fast32_t>(0),
static_cast<int_fast32_t
>(current_column_index - band_column_index));
155 assert(remaining_column_size > 0);
159 return std::min(static_cast<uint_fast32_t>(remaining_column_size),
160 static_cast<uint_fast32_t>(
172 constexpr uint_fast32_t second_range_begin_offset() const noexcept
174 assert(current_column_index > band_column_index);
176 return current_column_index - band_column_index - 1;
180 constexpr
bool band_touches_last_row() const noexcept
182 if (current_column_index > band_column_index)
183 return (second_range_begin_offset() + current_band_size() + 1) == dimension_second_range;
185 return current_band_size() >= dimension_second_range;
201 template <
typename first_range_t,
typename second_range_t,
typename band_t>
202 constexpr
auto trim_sequences(first_range_t & first_range,
203 second_range_t & second_range,
204 band_t
const & band)
const noexcept
206 using band_type = decltype(band.lower_bound);
211 auto trim_first_range = [&]() constexpr
213 size_t begin_pos =
std::max(band.lower_bound - 1, static_cast<band_type>(0));
214 size_t end_pos =
std::min(band.upper_bound + dimension_second, dimension_first);
215 return first_range |
view::slice(begin_pos, end_pos);
218 auto trim_second_range = [&]() constexpr
220 size_t begin_pos = std::abs(
std::min(band.upper_bound + 1, static_cast<band_type>(0)));
221 size_t end_pos =
std::min(dimension_first - band.lower_bound, dimension_second);
222 return second_range |
view::slice(begin_pos, end_pos);
225 return std::tuple{trim_first_range(), trim_second_range()};
231 constexpr
auto map_banded_coordinate_to_range_position(alignment_coordinate coordinate)
const noexcept
239 coordinate.second +=
static_cast<as_int_t
>(coordinate.first - band_column_index);
245 using base_t::score_matrix;
246 using base_t::dimension_first_range;
247 using base_t::dimension_second_range;
248 using base_t::current_column_index;
251 typename score_matrix_type::iterator current_matrix_iter;
253 uint_fast32_t band_column_index{};
255 uint_fast32_t band_row_index{};
257 uint_fast32_t band_size{};
::ranges::distance distance
Alias for ranges::distance. Returns the number of hops from first to last.
Definition: iterator:321
constexpr auto zip
A range adaptor that transforms a tuple of range into a range of tuples.
Definition: ranges:948
Provides various shortcuts for common std::ranges functions.
constexpr auto slice
A view adaptor that returns a half-open interval on the underlying range.
Definition: slice.hpp:144
constexpr auto common
A range adaptor that makes any range model std::ranges::CommonRange (at the expense of some performan...
Definition: ranges:447
Provides seqan3::detail::unbanded_score_dp_matrix_policy.
Adaptations of concepts from the Ranges TS.
::ranges::begin begin
Alias for ranges::begin. Returns an iterator to the beginning of a range.
Definition: ranges:174
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 the declaration of seqan3::detail::trace_directions.
Definition: aligned_sequence_concept.hpp:35
auto const get
A view calling std::get on each element in a range.
Definition: get.hpp:66
Provides seqan3::view::slice.
Provides seqan3::detail::alignment_coordinate.
constexpr auto repeat_n
A view factory that repeats a given value n times.
Definition: repeat_n.hpp:97
::ranges::end end
Alias for ranges::end. Returns an iterator to the end of a range.
Definition: ranges:179