15 #include <type_traits>
24 namespace seqan3::detail
38 template <simd::simd_concept simd_t>
39 struct simd_global_alignment_state
42 simd_t score_offset{};
44 simd_t coordinate_offset{};
46 simd_t last_column_mask{};
48 simd_t last_row_mask{};
80 template <
typename alignment_algorithm_t,
81 simd::simd_concept simd_t,
82 typename is_global_alignment_t,
83 typename traits_type = default_find_optimum_trait>
84 class simd_find_optimum_policy :
public std::conditional_t<is_global_alignment_t::value,
85 simd_global_alignment_state<simd_t>,
90 friend alignment_algorithm_t;
93 static constexpr
bool is_global_alignment = is_global_alignment_t::value;
95 static constexpr
bool search_in_every_cell = traits_type::find_in_every_cell_type::value;
97 static constexpr
bool search_in_last_row = traits_type::find_in_last_row_type::value || is_global_alignment;
99 static constexpr
bool search_in_last_column = traits_type::find_in_last_column_type::value || is_global_alignment;
104 constexpr simd_find_optimum_policy() =
default;
105 constexpr simd_find_optimum_policy(simd_find_optimum_policy
const &) =
default;
106 constexpr simd_find_optimum_policy(simd_find_optimum_policy &&) =
default;
107 constexpr simd_find_optimum_policy & operator=(simd_find_optimum_policy
const &) =
default;
108 constexpr simd_find_optimum_policy & operator=(simd_find_optimum_policy &&) =
default;
109 ~simd_find_optimum_policy() =
default;
114 template <
typename cell_t,
typename score_t>
115 constexpr
void check_score_of_cell([[maybe_unused]] cell_t
const & current_cell,
116 [[maybe_unused]] alignment_algorithm_state<score_t> & state)
const noexcept
118 if constexpr (search_in_every_cell)
119 check_and_update(current_cell, state);
123 template <
typename other_alignment_algorithm_t,
typename score_t,
typename is_local_t>
124 friend class simd_affine_gap_policy;
127 template <
typename other_alignment_algorithm_t,
typename other_traits_type>
128 friend class affine_gap_init_policy;
131 template <
typename cell_t,
typename score_t>
132 constexpr
void check_score_of_last_row_cell([[maybe_unused]] cell_t
const & last_row_cell,
133 [[maybe_unused]] alignment_algorithm_state<score_t> & state)
const
137 if constexpr (!search_in_every_cell && search_in_last_row)
139 if constexpr (is_global_alignment)
140 check_and_update<true>(last_row_cell, state);
142 check_and_update(last_row_cell, state);
147 template <
typename alignment_column_t,
typename score_t>
148 constexpr
void check_score_of_cells_in_last_column([[maybe_unused]] alignment_column_t && last_column,
149 [[maybe_unused]] alignment_algorithm_state<score_t> & state)
153 if constexpr (!search_in_every_cell && search_in_last_column)
155 for (
auto && cell : last_column)
157 if constexpr (is_global_alignment)
158 check_and_update<false>(cell, state);
160 check_and_update(cell, state);
166 template <
typename cell_t,
typename score_t>
167 constexpr
void check_score_of_last_cell([[maybe_unused]] cell_t
const & last_cell,
168 [[maybe_unused]] alignment_algorithm_state<score_t> & state)
const noexcept
171 if constexpr (!search_in_every_cell && !search_in_last_row && !search_in_last_column)
172 check_and_update(last_cell, state);
187 template <std::ranges::forward_range sequence1_collection_t,
188 std::ranges::forward_range sequence2_collection_t,
190 void initialise_find_optimum_policy([[maybe_unused]] sequence1_collection_t && sequence1_collection,
191 [[maybe_unused]] sequence2_collection_t && sequence2_collection,
192 [[maybe_unused]] score_t
const padding_score)
194 if constexpr (is_global_alignment)
196 assert(std::ranges::distance(sequence1_collection) == std::ranges::distance(sequence2_collection));
198 constexpr
size_t simd_size = simd_traits<simd_t>::length;
206 size_t array_index{};
207 for (
auto && [sequence1, sequence2] : views::zip(sequence1_collection, sequence2_collection))
209 sequence1_sizes[array_index] = std::ranges::distance(sequence1);
210 sequence2_sizes[array_index] = std::ranges::distance(sequence2);
211 max_sequence1_size = std::max<std::ptrdiff_t>(sequence1_sizes[array_index], max_sequence1_size);
212 max_sequence2_size = std::max<std::ptrdiff_t>(sequence2_sizes[array_index], max_sequence2_size);
217 std::ptrdiff_t global_diagonal = max_sequence1_size - max_sequence2_size;
219 for (
size_t simd_index = 0; simd_index < simd_size; ++simd_index)
221 if (
std::ptrdiff_t local_diagonal = sequence1_sizes[simd_index] - sequence2_sizes[simd_index];
222 local_diagonal < global_diagonal)
224 this->last_row_mask[simd_index] = max_sequence1_size - (global_diagonal - local_diagonal);
225 this->last_column_mask[simd_index] = max_sequence2_size + 1;
226 this->coordinate_offset[simd_index] = max_sequence2_size - sequence2_sizes[simd_index];
227 this->score_offset[simd_index] = padding_score * this->coordinate_offset[simd_index];
231 this->last_column_mask[simd_index] = max_sequence2_size - (local_diagonal - global_diagonal);
232 this->last_row_mask[simd_index] = max_sequence1_size + 1;
233 this->coordinate_offset[simd_index] = max_sequence1_size - sequence1_sizes[simd_index];
234 this->score_offset[simd_index] = padding_score * this->coordinate_offset[simd_index];
250 template <
typename cell_t,
typename score_t>
251 constexpr
void check_and_update(cell_t
const & cell, alignment_algorithm_state<score_t> & state)
const noexcept
253 static_assert(!is_global_alignment,
"This function should not be called for the global alignment. "
254 "Use the other check_and_update function instead.");
255 auto const & [score_cell, trace_cell] = cell;
256 state.optimum.update_if_new_optimal_score(score_cell.current,
257 column_index_type{trace_cell.coordinate.first},
258 row_index_type{trace_cell.coordinate.second});
277 template <
bool in_last_row,
typename cell_t,
typename score_t>
278 constexpr
void check_and_update(cell_t
const & cell, alignment_algorithm_state<score_t> & state)
const noexcept
280 static_assert(is_global_alignment,
"This function should only be called for the global alignment. "
281 "Use the other check_and_update function instead.");
283 using simd_mask_t =
typename simd_traits<simd_t>::mask_type;
284 auto const & [score_cell, trace_cell] = cell;
285 simd_t column_positions = simd::fill<simd_t>(trace_cell.coordinate.first);
286 simd_t row_positions = simd::fill<simd_t>(trace_cell.coordinate.second);
290 if constexpr (in_last_row)
291 mask = (column_positions == this->last_row_mask);
293 mask = (row_positions == this->last_column_mask);
297 state.optimum.score = mask ? score_cell.current - this->score_offset : state.optimum.score;
298 state.optimum.column_index = mask ? column_positions - this->coordinate_offset
299 : state.optimum.column_index;
300 state.optimum.row_index = mask ? row_positions - this->coordinate_offset
301 : state.optimum.row_index;