SeqAn3
The Modern C++ library for sequence analysis.
find_optimum_policy.hpp
Go to the documentation of this file.
1 // -----------------------------------------------------------------------------------------------------
2 // Copyright (c) 2006-2019, Knut Reinert & Freie Universität Berlin
3 // Copyright (c) 2016-2019, 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 <type_traits>
16 
17 #include <range/v3/algorithm/for_each.hpp>
18 
22 #include <seqan3/std/concepts>
23 #include <seqan3/std/iterator>
24 #include <seqan3/std/ranges>
25 
26 namespace seqan3::detail
27 {
28 
37 struct default_find_optimum_trait
38 {
40  using find_in_every_cell_type = std::false_type;
42  using find_in_last_row_type = std::false_type;
44  using find_in_last_column_type = std::false_type;
45 };
46 
58 template <typename derived_t, typename traits_type = default_find_optimum_trait>
59 class find_optimum_policy
60 {
61 
62 private:
63 
65  friend derived_t;
66 
70  constexpr find_optimum_policy() = default;
71  constexpr find_optimum_policy(find_optimum_policy const &) = default;
72  constexpr find_optimum_policy(find_optimum_policy &&) = default;
73  constexpr find_optimum_policy & operator=(find_optimum_policy const &) = default;
74  constexpr find_optimum_policy & operator=(find_optimum_policy &&) = default;
75  ~find_optimum_policy() = default;
76 
78 protected:
79 
89  template <typename score_t>
90  constexpr void check_score([[maybe_unused]] alignment_optimum<score_t> const & current,
91  [[maybe_unused]] alignment_optimum<score_t> & optimum) const noexcept
92  {
93  if constexpr (traits_type::find_in_every_cell_type::value)
94  {
95  optimum = std::max(optimum, current, alignment_optimum_compare_less{}); // if equal => optimum
96  }
97 
98  }
99 
111  template <typename score_t>
112  constexpr void check_score_last_row([[maybe_unused]] alignment_optimum<score_t> const & current,
113  [[maybe_unused]] alignment_optimum<score_t> & optimum) const noexcept
114  {
115  if constexpr (traits_type::find_in_last_row_type::value)
116  optimum = std::max(optimum, current, alignment_optimum_compare_less{}); // if equal => optimum
117  }
118 
131  template <std::ranges::BidirectionalRange rng_t, typename score_t>
132  constexpr void check_score_last_column(rng_t const & rng,
133  alignment_optimum<score_t> & optimum) const noexcept
134  {
135  using std::get;
136  // Only check the entire column if it was configured to search here.
137  if constexpr (traits_type::find_in_last_column_type::value)
138  {
139  ranges::for_each(rng, [&](auto && entry)
140  {
141  optimum = std::max(optimum,
142  alignment_optimum<score_t>{get<0>(get<0>(entry)),
143  static_cast<alignment_coordinate>(get<1>(entry))},
144  alignment_optimum_compare_less{}); // if equal => optimum
145  });
146  }
147  else // Only check the last cell for the global alignment.
148  {
149  auto && last = *std::ranges::prev(std::ranges::end(rng));
150  optimum = std::max(optimum,
151  alignment_optimum<score_t>{get<0>(get<0>(last)),
152  static_cast<alignment_coordinate>(get<1>(last))},
153  alignment_optimum_compare_less{}); // if equal => optimum
154  }
155  }
156 
168  template <typename optimum_type,
169  typename dimension_type,
170  typename band_type,
171  typename gap_scheme_type>
172  constexpr void balance_trailing_gaps([[maybe_unused]] optimum_type & total,
173  [[maybe_unused]] dimension_type const dimension_first,
174  [[maybe_unused]] dimension_type const dimension_second,
175  [[maybe_unused]] band_type const & band,
176  [[maybe_unused]] gap_scheme_type const & scheme)
177  {
178  using cmp_int_type = std::make_signed_t<dimension_type>;
179 
180  // Only balance score if max is not searched in entire last row.
181  if constexpr (!traits_type::find_in_last_row_type::value && !traits_type::find_in_every_cell_type::value)
182  { // The band ends before crossing the last column.
183  cmp_int_type gap_size = dimension_first -
184  std::min(static_cast<cmp_int_type>(band.upper_bound + dimension_second),
185  static_cast<cmp_int_type>(dimension_first));
186 
187  assert(gap_size >= 0);
188  total.score += scheme.score(gap_size);
189  }
190 
191  // Only balance score if max is not searched in entire last column.
192  if constexpr (!traits_type::find_in_last_column_type::value && !traits_type::find_in_every_cell_type::value)
193  {
194  // The band ends before crossing the last row.
195  cmp_int_type gap_size = dimension_second -
196  std::min(static_cast<cmp_int_type>(dimension_first - band.lower_bound),
197  static_cast<cmp_int_type>(dimension_second));
198 
199  assert(gap_size >= 0);
200  total.score += scheme.score(gap_size);
201  }
202  }
203 };
204 
205 } // namespace seqan3::detail
::ranges::prev prev
Alias for ranges::prev. Returns the nth predecessor of the given iterator.
Definition: iterator:326
Provides C++20 additions to the <iterator> header.
Provides various shortcuts for common std::ranges functions.
Provides seqan3::detail::deferred_crtp_base.
T min(T... args)
The Concepts library.
Adaptations of concepts from the Ranges TS.
T max(T... args)
Definition: aligned_sequence_concept.hpp:35
auto const get
A view calling std::get on each element in a range.
Definition: get.hpp:66
::ranges::end end
Alias for ranges::end. Returns an iterator to the end of a range.
Definition: ranges:179
Provides seqan3::detail::alignment_optimum.