SeqAn3
The Modern C++ library for sequence analysis.
edit_distance_trace_matrix_full.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 <bitset>
16 
20 
21 namespace seqan3::detail
22 {
23 
31 template <typename word_t, bool is_semi_global, bool use_max_errors>
32 class edit_distance_trace_matrix_full
33 {
34 public:
36  template <std::ranges::ViewableRange database_t,
38  typename align_config_t,
39  typename edit_traits>
40  friend class edit_distance_unbanded;
41 
45  edit_distance_trace_matrix_full() = default;
46  edit_distance_trace_matrix_full(edit_distance_trace_matrix_full const &) = default;
47  edit_distance_trace_matrix_full(edit_distance_trace_matrix_full &&) = default;
48  edit_distance_trace_matrix_full & operator=(edit_distance_trace_matrix_full const &) = default;
49  edit_distance_trace_matrix_full & operator=(edit_distance_trace_matrix_full &&) = default;
50  ~edit_distance_trace_matrix_full() = default;
51 
52  protected:
56  edit_distance_trace_matrix_full(size_t const rows_size)
57  : rows_size{rows_size}, columns{}
58  {}
60 
61 public:
63  using word_type = word_t;
64 
66  static constexpr auto word_size = sizeof_bits<word_type>;
67 
69  using entry_type = detail::trace_directions;
70 
79  void reserve(size_t const new_capacity)
80  {
81  columns.reserve(new_capacity);
82  }
83 
84 public:
86  entry_type at(size_t const row, size_t const col) const noexcept
87  {
88  assert(row < rows());
89  assert(col < cols());
90 
91  column_type const & column = columns[col];
92 
93  if constexpr(use_max_errors)
94  if (!(row < column.max_rows))
96 
97  if (row == 0u)
98  {
99  if constexpr(is_semi_global)
101 
102  if (col == 0u)
104 
105  return detail::trace_directions::left;
106  }
107 
108  size_t const idx = (row - 1u) / word_size;
109  size_t const offset = (row - 1u) % word_size;
110 
111  bool const left = std::bitset<word_size>(column.left[idx])[offset];
112  bool const diagonal = std::bitset<word_size>(column.diagonal[idx])[offset];
113  bool const up = std::bitset<word_size>(column.up[idx])[offset];
114 
115  auto const dir = (left ? detail::trace_directions::left : detail::trace_directions::none) |
116  (diagonal ? detail::trace_directions::diagonal : detail::trace_directions::none) |
117  (up ? detail::trace_directions::up : detail::trace_directions::none);
118 
119  return dir;
120  }
121 
123  size_t rows() const noexcept
124  {
125  return rows_size;
126  }
127 
129  size_t cols() const noexcept
130  {
131  return columns.size();
132  }
133 
134 protected:
136  struct max_errors_state
137  {
140  size_t max_rows{};
141  };
142 
144  struct trace_matrix_state
145  {
147  std::vector<word_type> left{};
149  std::vector<word_type> diagonal{};
152  };
153 
155  struct column_type :
156  enable_state_t<true, trace_matrix_state>,
157  enable_state_t<use_max_errors, max_errors_state>
158  {};
159 
165  void add_column(std::vector<word_type> left, std::vector<word_type> diagonal, std::vector<word_type> up)
167  requires !use_max_errors
169  {
170  column_type column{};
171  column.left = std::move(left);
172  column.diagonal = std::move(diagonal);
173  column.up = std::move(up);
174 
175  columns.push_back(std::move(column));
176  }
177 
184  void add_column(std::vector<word_type> left, std::vector<word_type> diagonal, std::vector<word_type> up,
185  size_t const max_rows)
187  requires use_max_errors
189  {
190  column_type column{};
191  column.left = std::move(left);
192  column.diagonal = std::move(diagonal);
193  column.up = std::move(up);
194  column.max_rows = max_rows;
195 
196  columns.push_back(std::move(column));
197  }
198 
199 private:
201  size_t rows_size{};
203  std::vector<column_type> columns{};
204 };
205 
206 } // namespace seqan3::detail
T left(T... args)
Forwards for seqan3::edit_distance_unbanded related types.
No flag is set.
Definition: debug_stream.hpp:39
Provides the declaration of seqan3::detail::trace_directions.
Specifies the requirements of a Range type that is either a std::ranges::View or an lvalue-reference...
Definition: aligned_sequence_concept.hpp:35
T size(T... args)
Provides utility functions for bit twiddling.