SeqAn3  3.2.0-rc.1
The Modern C++ library for sequence analysis.
aligned_sequence_builder.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 <concepts>
16 #include <ranges>
17 #include <type_traits>
18 #include <vector>
19 
31 
32 namespace seqan3::detail
33 {
34 
52 template <std::ranges::viewable_range range_t>
53 struct make_aligned_sequence_type
54 {
55 private:
56  // The following expressions are used to check if the sequence types can be used as template arguments for the
57  // seqan3::gap_decorator. Ranges that do not model std::random_access_range for instance cannot be augmented with
58  // the gap_decorator and need to be copied instead.
59 
61  using unaligned_sequence_type = decltype(std::declval<range_t>() | views::type_reduce | views::slice(0, 1));
62 
63 public:
65  using type = lazy_conditional_t<is_class_template_declarable_with_v<gap_decorator, unaligned_sequence_type>,
66  lazy<gap_decorator, unaligned_sequence_type>,
67  lazy<std::vector, gapped<std::ranges::range_value_t<unaligned_sequence_type>>>>;
68 };
69 
77 template <std::ranges::viewable_range first_sequence_t, std::ranges::viewable_range second_sequence_t>
78 struct make_pairwise_alignment_type
79 {
81  using first_aligned_t = typename make_aligned_sequence_type<first_sequence_t>::type;
83  using second_aligned_t = typename make_aligned_sequence_type<second_sequence_t>::type;
84 
86  "first_aligned_t is required to model seqan3::writable_aligned_sequence!");
88  "second_aligned_t is required to model seqan3::writable_aligned_sequence!");
89 
92 };
93 
115 template <std::ranges::viewable_range fst_sequence_t, std::ranges::viewable_range sec_sequence_t>
116 class aligned_sequence_builder
117 {
118 public:
120  using alignment_type = typename make_pairwise_alignment_type<fst_sequence_t, sec_sequence_t>::type;
121 
123  struct [[nodiscard]] result_type
124  {
126  std::pair<size_t, size_t> first_sequence_slice_positions{};
128  std::pair<size_t, size_t> second_sequence_slice_positions{};
131  alignment_type alignment{};
132  };
133 
137  constexpr aligned_sequence_builder()
138  requires std::default_initializable<type_reduce_t<fst_sequence_t>>
139  && std::default_initializable<type_reduce_t<sec_sequence_t>>
140  = default;
141  constexpr aligned_sequence_builder(aligned_sequence_builder const &) = default;
142  constexpr aligned_sequence_builder(aligned_sequence_builder &&) = default;
143  constexpr aligned_sequence_builder & operator=(aligned_sequence_builder const &) = default;
144  constexpr aligned_sequence_builder & operator=(aligned_sequence_builder &&) = default;
145  ~aligned_sequence_builder() = default;
146 
151  constexpr aligned_sequence_builder(fst_sequence_t fst_rng, sec_sequence_t sec_rng) :
152  fst_rng{views::type_reduce(std::forward<fst_sequence_t>(fst_rng))},
153  sec_rng{views::type_reduce(std::forward<sec_sequence_t>(sec_rng))}
154  {}
156 
171  template <std::ranges::input_range trace_path_t>
172  result_type operator()(trace_path_t && trace_path)
173  {
174  static_assert(std::same_as<std::ranges::range_value_t<trace_path_t>, trace_directions>,
175  "The value type of the trace path must be seqan3::detail::trace_directions");
176 
177  result_type res{};
178  auto trace_it = std::ranges::begin(trace_path);
179  std::tie(res.first_sequence_slice_positions.second, res.second_sequence_slice_positions.second) =
180  std::pair<size_t, size_t>{trace_it.coordinate()};
181 
183 
184  while (trace_it != std::ranges::end(trace_path))
185  {
186  trace_directions last_dir = *trace_it;
187  size_t span = 0;
188  for (; trace_it != std::ranges::end(trace_path) && *trace_it == last_dir; ++trace_it, ++span)
189  {}
190 
191  trace_segments.emplace_back(last_dir, span);
192  }
193 
194  std::tie(res.first_sequence_slice_positions.first, res.second_sequence_slice_positions.first) =
195  std::pair<size_t, size_t>{trace_it.coordinate()};
196 
197  assign_unaligned(
198  std::get<0>(res.alignment),
199  std::views::all(fst_rng)
200  | views::slice(res.first_sequence_slice_positions.first, res.first_sequence_slice_positions.second));
201  assign_unaligned(
202  std::get<1>(res.alignment),
203  std::views::all(sec_rng)
204  | views::slice(res.second_sequence_slice_positions.first, res.second_sequence_slice_positions.second));
205 
206  // Now we need to insert the values.
207  fill_aligned_sequence(trace_segments | std::views::reverse,
208  std::get<0>(res.alignment),
209  std::get<1>(res.alignment));
210 
211  return res;
212  }
213 
214 private:
221  template <typename reverse_traces_t, typename fst_aligned_t, typename sec_aligned_t>
222  void fill_aligned_sequence(reverse_traces_t && rev_traces,
223  fst_aligned_t & fst_aligned,
224  sec_aligned_t & sec_aligned) const
225  {
226  if (std::ranges::empty(rev_traces))
227  return;
228 
229  auto fst_it = std::ranges::begin(fst_aligned);
230  auto sec_it = std::ranges::begin(sec_aligned);
231 
232  for (auto const & [dir, span] : rev_traces)
233  {
234  assert(dir == trace_directions::up || dir == trace_directions::left || dir == trace_directions::diagonal);
235 
236  if (dir == trace_directions::up)
237  fst_it = insert_gap(fst_aligned, fst_it, span);
238 
239  if (dir == trace_directions::left)
240  sec_it = insert_gap(sec_aligned, sec_it, span);
241 
242  fst_it += span;
243  sec_it += span;
244  }
245  }
246 
247  type_reduce_t<fst_sequence_t> fst_rng;
248  type_reduce_t<sec_sequence_t> sec_rng;
249 };
250 
256 template <std::ranges::viewable_range fst_sequence_t, std::ranges::viewable_range sec_sequence_t>
257 aligned_sequence_builder(fst_sequence_t &&, sec_sequence_t &&)
258  -> aligned_sequence_builder<fst_sequence_t, sec_sequence_t>;
260 } // namespace seqan3::detail
Includes the aligned_sequence and the related insert_gap and erase_gap functions to enable stl contai...
The <concepts> header from C++20's standard library.
T emplace_back(T... args)
Provides seqan3::gap_decorator.
Provides seqan3::gapped.
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 slice
A view adaptor that returns a half-open interval on the underlying range.
Definition: slice.hpp:178
constexpr auto type_reduce
A view adaptor that behaves like std::views::all, but type erases certain ranges.
Definition: type_reduce.hpp:150
The generic concept for an aligned sequence that is writable.
Provides a type trait for verifying valid template declarations.
Provides lazy template instantiation traits.
Provides seqan3::detail::matrix_index, seqan3::detail::matrix_coordinate and associated strong types.
decltype(views::type_reduce(std::declval< t >())) type_reduce_t
Deduces the return value of seqan3::views::type_reduce.
Definition: type_reduce.hpp:162
SeqAn specific customisations in the standard namespace.
The <ranges> header from C++20's standard library.
Provides seqan3::views::slice.
T tie(T... args)
Provides the declaration of seqan3::detail::trace_directions.
Provides seqan3::views::type_reduce.
Provides the concepts seqan3::transformation_trait and seqan3::unary_type_trait.
Provides seqan3::views::convert.