SeqAn3
The Modern C++ library for sequence analysis.
edit_distance_score_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 
19 
20 namespace seqan3::detail
21 {
22 
31 template <typename word_t, typename score_t, bool is_semi_global, bool use_max_errors>
32 class edit_distance_score_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_score_matrix_full() = default;
46  edit_distance_score_matrix_full(edit_distance_score_matrix_full const &) = default;
47  edit_distance_score_matrix_full(edit_distance_score_matrix_full &&) = default;
48  edit_distance_score_matrix_full & operator=(edit_distance_score_matrix_full const &) = default;
49  edit_distance_score_matrix_full & operator=(edit_distance_score_matrix_full &&) = default;
50  ~edit_distance_score_matrix_full() = default;
51 
52 protected:
56  edit_distance_score_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 score_type = score_t;
70 
73 
75  static constexpr std::optional<score_type> inf = std::nullopt;
76 
85  void reserve(size_t const new_capacity)
86  {
87  columns.reserve(new_capacity);
88  }
89 
98  template <typename score_type>
99  static size_t max_rows(word_type const score_mask, unsigned const last_block,
100  score_type const score, score_type const max_errors) noexcept
101  {
102  size_t const offset = score_mask == 0u ? 0u : bit_scan_reverse(score_mask) + 1u;
103  size_t const active_row = word_size * last_block + offset;
104  return active_row + (score <= max_errors);
105  }
106 
112  static score_type score_delta_of_word(word_type const & vp, word_type const & vn) noexcept
113  {
114  score_type const p = std::bitset<word_size>{vp}.count();
115  score_type const n = std::bitset<word_size>{vn}.count();
116  return p - n;
117  }
118 
119 public:
121  entry_type at(size_t const row, size_t const col) const noexcept
122  {
123  assert(row < rows());
124  assert(col < cols());
125 
126  column_type const & column = columns[col];
127  if constexpr(use_max_errors)
128  if (!(row < column.max_rows))
129  return inf;
130 
131  score_type score = is_semi_global ? 0u : static_cast<score_type>(col);
132 
133  size_t current_row = 1u;
134  size_t word_idx = 0u;
135 
136  for (; current_row + word_size <= row; ++word_idx, current_row += word_size)
137  score += score_delta_of_word(column.vp[word_idx], column.vn[word_idx]);
138 
139  if (row >= current_row)
140  {
141  word_type const mask = (1u << (row - current_row + 1u)) - 1u;
142  score += score_delta_of_word(column.vp[word_idx] & mask, column.vn[word_idx] & mask);
143  }
144 
145  return -score;
146  }
147 
149  size_t rows() const noexcept
150  {
151  return rows_size;
152  }
153 
155  size_t cols() const noexcept
156  {
157  return columns.size();
158  }
159 
160 protected:
162  struct max_errors_state
163  {
166  size_t max_rows;
167  };
168 
170  struct score_matrix_state
171  {
176  };
177 
179  struct column_type :
180  enable_state_t<true, score_matrix_state>,
181  enable_state_t<use_max_errors, max_errors_state>
182  {};
183 
188  void add_column(std::vector<word_type> vp, std::vector<word_type> vn)
190  requires !use_max_errors
192  {
193  column_type column{};
194  column.vp = std::move(vp);
195  column.vn = std::move(vn);
196 
197  columns.push_back(std::move(column));
198  }
199 
205  void add_column(std::vector<word_type> vp, std::vector<word_type> vn, size_t const max_rows)
207  requires use_max_errors
209  {
210  column_type column{};
211  column.vp = std::move(vp);
212  column.vn = std::move(vn);
213  column.max_rows = max_rows;
214 
215  columns.push_back(std::move(column));
216  }
217 
218 private:
220  size_t rows_size{};
222  std::vector<column_type> columns{};
223 };
224 
225 } // namespace seqan3::detail
Forwards for seqan3::edit_distance_unbanded related types.
Specifies the requirements of a Range type that is either a std::ranges::View or an lvalue-reference...
T count(T... args)
Definition: aligned_sequence_concept.hpp:35
Provides utility functions for bit twiddling.