20 namespace seqan3::detail
31 template <
typename word_t,
typename score_t,
bool is_semi_global,
bool use_max_errors>
32 class edit_distance_score_matrix_full
36 template <std::ranges::viewable_range database_t,
37 std::ranges::viewable_range query_t,
38 typename align_config_t,
40 friend class edit_distance_unbanded;
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;
54 template <
typename derived_t,
typename edit_traits>
55 friend class edit_distance_unbanded_score_matrix_policy;
60 edit_distance_score_matrix_full(
size_t const rows_size)
61 : rows_size{rows_size}, columns{}
67 using word_type = word_t;
70 static constexpr
auto word_size = sizeof_bits<word_type>;
73 using score_type = score_t;
79 using reference = value_type;
82 using size_type = size_t;
95 void reserve(
size_t const new_capacity)
97 columns.reserve(new_capacity);
108 template <
typename score_type>
109 static size_t max_rows(word_type
const score_mask,
unsigned const last_block,
110 score_type
const score, score_type
const max_errors) noexcept
112 size_t const offset = score_mask == 0u ? 0u : most_significant_bit_set(score_mask) + 1u;
113 size_t const active_row = word_size * last_block +
offset;
114 return active_row + (score <= max_errors);
122 static score_type score_delta_of_word(word_type
const & vp, word_type
const & vn) noexcept
131 reference
at(matrix_coordinate
const & coordinate)
const noexcept
133 size_t col = coordinate.col;
134 size_t row = coordinate.row;
136 assert(row < rows());
137 assert(col < cols());
139 column_type
const & column = columns[col];
140 if constexpr(use_max_errors)
141 if (!(row < column.max_rows))
144 score_type score = is_semi_global ? 0u : static_cast<score_type>(col);
146 size_t current_row = 1u;
147 size_t word_idx = 0u;
149 for (; current_row + word_size <= row; ++word_idx, current_row += word_size)
150 score += score_delta_of_word(column.vp[word_idx], column.vn[word_idx]);
152 if (row >= current_row)
154 word_type
const mask = (1u << (row - current_row + 1u)) - 1u;
155 score += score_delta_of_word(column.vp[word_idx] & mask, column.vn[word_idx] & mask);
162 size_t rows() const noexcept
168 size_t cols() const noexcept
170 return columns.size();
175 struct max_errors_state
183 struct score_matrix_state
193 enable_state_t<true, score_matrix_state>,
194 enable_state_t<use_max_errors, max_errors_state>
203 requires !use_max_errors
206 column_type column{};
220 requires use_max_errors
223 column_type column{};
226 column.max_rows = max_rows;