SeqAn3  3.2.0-rc.1
The Modern C++ library for sequence analysis.
policy_optimum_tracker_simd.hpp
Go to the documentation of this file.
1 // -----------------------------------------------------------------------------------------------------
2 // Copyright (c) 2006-2022, Knut Reinert & Freie Universität Berlin
3 // Copyright (c) 2016-2022, Knut Reinert & MPI für molekulare Genetik
4 // This file may be used, modified and/or redistributed under the terms of the 3-clause BSD-License
5 // shipped with this file and also available at: https://github.com/seqan/seqan3/blob/master/LICENSE.md
6 // -----------------------------------------------------------------------------------------------------
7 
13 #pragma once
14 
15 #include <limits>
16 #include <ranges>
17 
24 
25 namespace seqan3::detail
26 {
27 
44 struct max_score_updater_simd_global
45 {
46 
63  template <typename score_t, typename coordinate_t>
64  requires (std::assignable_from<score_t &, score_t const &> &&
65  requires (coordinate_t coordinate)
66  {
67  requires simd_concept<decltype(coordinate.col)>;
68  requires simd_concept<decltype(coordinate.row)>;
69  })
70  void operator()(score_t & optimal_score,
71  coordinate_t const & optimal_coordinate,
72  score_t current_score,
73  coordinate_t const & current_coordinate) const noexcept
74  {
75  auto mask =
76  (optimal_coordinate.col == current_coordinate.col) && (optimal_coordinate.row == current_coordinate.row);
77  optimal_score = (mask) ? std::move(current_score) : optimal_score;
78  }
79 };
80 
85 template <typename alignment_configuration_t, std::semiregular optimum_updater_t>
86  requires is_type_specialisation_of_v<alignment_configuration_t, configuration>
87  && std::invocable<
88  optimum_updater_t,
89  typename alignment_configuration_traits<alignment_configuration_t>::score_type &,
90  typename alignment_configuration_traits<alignment_configuration_t>::matrix_coordinate_type &,
91  typename alignment_configuration_traits<alignment_configuration_t>::score_type,
92  typename alignment_configuration_traits<alignment_configuration_t>::matrix_coordinate_type>
93 class policy_optimum_tracker_simd : protected policy_optimum_tracker<alignment_configuration_t, optimum_updater_t>
94 {
95 protected:
97  using base_policy_t = policy_optimum_tracker<alignment_configuration_t, optimum_updater_t>;
98 
99  // Import the configured score type.
100  using typename base_policy_t::score_type;
101  using typename base_policy_t::traits_type;
102 
104  using scalar_type = typename simd::simd_traits<score_type>::scalar_type;
106  using original_score_type = typename traits_type::original_score_type;
107 
108  static_assert(simd_concept<score_type>, "Must be a simd type!");
109 
110  // Import base variables into class scope.
111  using base_policy_t::compare_and_set_optimum;
112  using base_policy_t::optimal_coordinate;
113  using base_policy_t::optimal_score;
116 
120  policy_optimum_tracker_simd() = default;
121  policy_optimum_tracker_simd(policy_optimum_tracker_simd const &) = default;
122  policy_optimum_tracker_simd(policy_optimum_tracker_simd &&) = default;
123  policy_optimum_tracker_simd & operator=(policy_optimum_tracker_simd const &) = default;
124  policy_optimum_tracker_simd & operator=(policy_optimum_tracker_simd &&) = default;
125  ~policy_optimum_tracker_simd() = default;
126 
135  policy_optimum_tracker_simd(alignment_configuration_t const & config) : base_policy_t{config}
136  {
137  base_policy_t::test_last_row_cell = true;
138  base_policy_t::test_last_column_cell = true;
139  }
141 
143  void reset_optimum()
144  {
145  optimal_score = simd::fill<score_type>(std::numeric_limits<scalar_type>::lowest());
146  }
147 
194  template <std::ranges::input_range sequence1_collection_t, std::ranges::input_range sequence2_collection_t>
195  void initialise_tracker(sequence1_collection_t & sequence1_collection,
196  sequence2_collection_t & sequence2_collection)
197  {
198  using index_t = typename traits_type::matrix_index_type;
199  using scalar_index_t = typename simd_traits<index_t>::scalar_type;
200 
201  scalar_index_t largest_sequence1_size{};
202  scalar_index_t largest_sequence2_size{};
203  alignas(alignof(index_t)) std::array<scalar_index_t, traits_type::alignments_per_vector> sequence1_sizes{};
204  alignas(alignof(index_t)) std::array<scalar_index_t, traits_type::alignments_per_vector> sequence2_sizes{};
205 
206  // First, get all dimensions from the sequences and keep track of the maximal size in either dimension.
207  size_t sequence_count{};
208  for (auto && [sequence1, sequence2] : views::zip(sequence1_collection, sequence2_collection))
209  {
210  sequence1_sizes[sequence_count] = std::ranges::distance(sequence1);
211  sequence2_sizes[sequence_count] = std::ranges::distance(sequence2);
212  largest_sequence1_size = std::max(largest_sequence1_size, sequence1_sizes[sequence_count]);
213  largest_sequence2_size = std::max(largest_sequence2_size, sequence2_sizes[sequence_count]);
214  ++sequence_count;
215  }
216 
217  // Second, determine the offset for each individual end-coordinate which is used to project the cell to the
218  // last row or column of the global alignment matrix. Choose the smallest distance as the correct offset
219  // to the projected cell.
220  for (size_t index = 0; index != sequence_count; ++index)
221  {
222  assert(sequence1_sizes[index] <= largest_sequence1_size);
223  assert(sequence2_sizes[index] <= largest_sequence2_size);
224 
225  padding_offsets[index] = std::min(largest_sequence1_size - sequence1_sizes[index],
226  largest_sequence2_size - sequence2_sizes[index]);
227  sequence1_sizes[index] += padding_offsets[index];
228  sequence2_sizes[index] += padding_offsets[index];
229  }
230 
231  // Load the target coordinate indices from the respective arrays.
232  optimal_coordinate.col = simd::load<index_t>(sequence1_sizes.data());
233  optimal_coordinate.row = simd::load<index_t>(sequence2_sizes.data());
234  }
235 };
236 } // namespace seqan3::detail
Provides algorithms to modify seqan3::simd::simd_type.
requires requires
The rank_type of the semi-alphabet; defined as the return type of seqan3::to_rank....
Definition: alphabet/concept.hpp:164
constexpr auto zip
A view adaptor that takes several views and returns tuple-like values from every i-th element of each...
Definition: zip.hpp:573
Provides lazy template instantiation traits.
T max(T... args)
T min(T... args)
Provides seqan3::detail::policy_optimum_tracker.
The <ranges> header from C++20's standard library.
Provides seqan3::simd::simd_type.
Provides seqan3::simd::simd_traits.
Provides seqan3::views::zip.