SeqAn3 3.4.0-rc.1
The Modern C++ library for sequence analysis.
Loading...
Searching...
No Matches
search_scheme_precomputed.hpp
Go to the documentation of this file.
1// SPDX-FileCopyrightText: 2006-2024 Knut Reinert & Freie Universität Berlin
2// SPDX-FileCopyrightText: 2016-2024 Knut Reinert & MPI für molekulare Genetik
3// SPDX-License-Identifier: BSD-3-Clause
4
10#pragma once
11
12#include <array>
13#include <vector>
14
16
17namespace seqan3::detail
18{
19
23template <uint8_t nbr_blocks>
24struct search
25{
27 using blocks_length_type = std::array<size_t, nbr_blocks>;
28
35
37 constexpr uint8_t blocks() const noexcept
38 {
39 return nbr_blocks;
40 }
41};
42
46struct search_dyn
47{
49 using blocks_length_type = std::vector<size_t>;
50
57
59 uint8_t blocks() const noexcept
60 {
61 return pi.size();
62 }
63};
64
67template <uint8_t nbr_searches, uint8_t nbr_blocks>
68using search_scheme_type = std::array<search<nbr_blocks>, nbr_searches>;
69
72using search_scheme_dyn_type = std::vector<search_dyn>;
73
83template <uint8_t min_error, uint8_t max_error>
84inline constexpr int optimum_search_scheme{0};
85
87
88template <>
89inline constexpr search_scheme_type<1, 1> optimum_search_scheme<0, 0>{{{{1}, {0}, {0}}}};
90
91template <>
92inline constexpr search_scheme_type<2, 2> optimum_search_scheme<0, 1>{
93 {{{1, 2}, {0, 0}, {0, 1}}, {{2, 1}, {0, 1}, {0, 1}}}};
94
95template <>
96inline constexpr search_scheme_type<2, 2> optimum_search_scheme<1, 1>{
97 {{{1, 2}, {0, 1}, {0, 1}}, {{2, 1}, {0, 1}, {0, 1}}}};
98
99template <>
100inline constexpr search_scheme_type<3, 4> optimum_search_scheme<0, 2>{{{{1, 2, 3, 4}, {0, 0, 1, 1}, {0, 0, 2, 2}},
101 {{3, 2, 1, 4}, {0, 0, 0, 0}, {0, 1, 1, 2}},
102 {{4, 3, 2, 1}, {0, 0, 0, 2}, {0, 1, 2, 2}}}};
103
104template <>
105inline constexpr search_scheme_type<3, 4> optimum_search_scheme<1, 2>{{{{1, 2, 3, 4}, {0, 0, 0, 1}, {0, 0, 2, 2}},
106 {{3, 2, 1, 4}, {0, 0, 1, 1}, {0, 1, 1, 2}},
107 {{4, 3, 2, 1}, {0, 0, 0, 2}, {0, 1, 2, 2}}}};
108
109template <>
110inline constexpr search_scheme_type<3, 4> optimum_search_scheme<2, 2>{{{{4, 3, 2, 1}, {0, 0, 1, 2}, {0, 0, 2, 2}},
111 {{2, 3, 4, 1}, {0, 0, 0, 2}, {0, 1, 1, 2}},
112 {{1, 2, 3, 4}, {0, 0, 0, 2}, {0, 1, 2, 2}}}};
113
114// TODO: benchmark whether the first search is really the fastest one (see \details of optimum_search_scheme)
115template <>
116inline constexpr search_scheme_type<4, 5> optimum_search_scheme<0, 3>{
117 {{{5, 4, 3, 2, 1}, {0, 0, 0, 0, 0}, {0, 0, 3, 3, 3}},
118 {{3, 4, 5, 2, 1}, {0, 0, 1, 1, 1}, {0, 1, 1, 2, 3}},
119 {{2, 3, 4, 5, 1}, {0, 0, 0, 2, 2}, {0, 1, 2, 2, 3}},
120 {{1, 2, 3, 4, 5}, {0, 0, 0, 0, 3}, {0, 2, 2, 3, 3}}}};
121
122template <>
123inline constexpr search_scheme_type<4, 5> optimum_search_scheme<1, 3>{
124 {{{5, 4, 3, 2, 1}, {0, 0, 0, 0, 1}, {0, 0, 3, 3, 3}},
125 {{3, 4, 5, 2, 1}, {0, 0, 1, 1, 1}, {0, 1, 1, 2, 3}},
126 {{2, 3, 4, 5, 1}, {0, 0, 0, 2, 2}, {0, 1, 2, 2, 3}},
127 {{1, 2, 3, 4, 5}, {0, 0, 0, 0, 3}, {0, 2, 2, 3, 3}}}};
128
129template <>
130inline constexpr search_scheme_type<4, 5> optimum_search_scheme<2, 3>{
131 {{{5, 4, 3, 2, 1}, {0, 0, 0, 0, 2}, {0, 0, 3, 3, 3}},
132 {{3, 4, 5, 2, 1}, {0, 0, 1, 1, 2}, {0, 1, 1, 2, 3}},
133 {{2, 3, 4, 5, 1}, {0, 0, 0, 2, 2}, {0, 1, 2, 2, 3}},
134 {{1, 2, 3, 4, 5}, {0, 0, 0, 0, 3}, {0, 2, 2, 3, 3}}}};
135
136template <>
137inline constexpr search_scheme_type<4, 5> optimum_search_scheme<3, 3>{
138 {{{5, 4, 3, 2, 1}, {0, 0, 0, 0, 3}, {0, 0, 3, 3, 3}},
139 {{3, 4, 5, 2, 1}, {0, 0, 1, 1, 3}, {0, 1, 1, 2, 3}},
140 {{2, 3, 4, 5, 1}, {0, 0, 0, 2, 3}, {0, 1, 2, 2, 3}},
141 {{1, 2, 3, 4, 5}, {0, 0, 0, 0, 3}, {0, 2, 2, 3, 3}}}};
142
143// TODO: add the following missing optimum search schemes (computation has not finished yet)
144// optimum_search_scheme<i, 4>, 0 < i <= 4
145
147
148} // namespace seqan3::detail
Provides platform and dependency checks.
T search(T... args)
T size(T... args)
Hide me