SeqAn3  3.1.0-rc.1
The Modern C++ library for sequence analysis.
search_scheme_precomputed.hpp
Go to the documentation of this file.
1 // -----------------------------------------------------------------------------------------------------
2 // Copyright (c) 2006-2021, Knut Reinert & Freie Universität Berlin
3 // Copyright (c) 2016-2021, 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 <array>
16 #include <vector>
17 
18 #include <seqan3/core/platform.hpp>
19 
20 namespace seqan3::detail
21 {
22 
26 template <uint8_t nbr_blocks>
27 struct search
28 {
30  typedef std::array<size_t, nbr_blocks> blocks_length_type;
31 
33  std::array<uint8_t, nbr_blocks> pi;
35  std::array<uint8_t, nbr_blocks> l;
37  std::array<uint8_t, nbr_blocks> u;
38 
40  constexpr uint8_t blocks() const noexcept
41  {
42  return nbr_blocks;
43  }
44 };
45 
49 struct search_dyn
50 {
52  typedef std::vector<size_t> blocks_length_type;
53 
55  std::vector<uint8_t> pi;
57  std::vector<uint8_t> l;
59  std::vector<uint8_t> u;
60 
62  uint8_t blocks() const noexcept
63  {
64  return pi.size();
65  }
66 };
67 
70 template <uint8_t nbr_searches, uint8_t nbr_blocks>
71 using search_scheme_type = std::array<search<nbr_blocks>, nbr_searches>;
72 
75 using search_scheme_dyn_type = std::vector<search_dyn>;
76 
86 template <uint8_t min_error, uint8_t max_error>
87 inline int constexpr optimum_search_scheme;
88 
90 
91 template <>
92 inline search_scheme_type<1, 1> constexpr optimum_search_scheme<0, 0>
93 {{
94  {{1}, {0}, {0}}
95 }};
96 
97 template <>
98 inline search_scheme_type<2, 2> constexpr optimum_search_scheme<0, 1>
99 {{
100  {{1, 2}, {0, 0}, {0, 1}},
101  {{2, 1}, {0, 1}, {0, 1}}
102 }};
103 
104 template <>
105 inline search_scheme_type<2, 2> constexpr optimum_search_scheme<1, 1>
106 {{
107  {{1, 2}, {0, 1}, {0, 1}},
108  {{2, 1}, {0, 1}, {0, 1}}
109 }};
110 
111 template <>
112 inline search_scheme_type<3, 4> constexpr optimum_search_scheme<0, 2>
113 {{
114  {{1, 2, 3, 4}, {0, 0, 1, 1}, {0, 0, 2, 2}},
115  {{3, 2, 1, 4}, {0, 0, 0, 0}, {0, 1, 1, 2}},
116  {{4, 3, 2, 1}, {0, 0, 0, 2}, {0, 1, 2, 2}}
117 }};
118 
119 template <>
120 inline search_scheme_type<3, 4> constexpr optimum_search_scheme<1, 2>
121 {{
122  {{1, 2, 3, 4}, {0, 0, 0, 1}, {0, 0, 2, 2}},
123  {{3, 2, 1, 4}, {0, 0, 1, 1}, {0, 1, 1, 2}},
124  {{4, 3, 2, 1}, {0, 0, 0, 2}, {0, 1, 2, 2}}
125 }};
126 
127 template <>
128 inline search_scheme_type<3, 4> constexpr optimum_search_scheme<2, 2>
129 {{
130  {{4, 3, 2, 1}, {0, 0, 1, 2}, {0, 0, 2, 2}},
131  {{2, 3, 4, 1}, {0, 0, 0, 2}, {0, 1, 1, 2}},
132  {{1, 2, 3, 4}, {0, 0, 0, 2}, {0, 1, 2, 2}}
133 }};
134 
135 template <>
136 inline search_scheme_type<4, 5> constexpr optimum_search_scheme<0, 3>
137 {{
138  // TODO: benchmark whether the first search is really the fastest one (see \details of optimum_search_scheme)
139  {{5, 4, 3, 2, 1}, {0, 0, 0, 0, 0}, {0, 0, 3, 3, 3}},
140  {{3, 4, 5, 2, 1}, {0, 0, 1, 1, 1}, {0, 1, 1, 2, 3}},
141  {{2, 3, 4, 5, 1}, {0, 0, 0, 2, 2}, {0, 1, 2, 2, 3}},
142  {{1, 2, 3, 4, 5}, {0, 0, 0, 0, 3}, {0, 2, 2, 3, 3}}
143 }};
144 
145 template <>
146 inline search_scheme_type<4, 5> constexpr optimum_search_scheme<1, 3>
147 {{
148  {{5, 4, 3, 2, 1}, {0, 0, 0, 0, 1}, {0, 0, 3, 3, 3}},
149  {{3, 4, 5, 2, 1}, {0, 0, 1, 1, 1}, {0, 1, 1, 2, 3}},
150  {{2, 3, 4, 5, 1}, {0, 0, 0, 2, 2}, {0, 1, 2, 2, 3}},
151  {{1, 2, 3, 4, 5}, {0, 0, 0, 0, 3}, {0, 2, 2, 3, 3}}
152 }};
153 
154 template <>
155 inline search_scheme_type<4, 5> constexpr optimum_search_scheme<2, 3>
156 {{
157  {{5, 4, 3, 2, 1}, {0, 0, 0, 0, 2}, {0, 0, 3, 3, 3}},
158  {{3, 4, 5, 2, 1}, {0, 0, 1, 1, 2}, {0, 1, 1, 2, 3}},
159  {{2, 3, 4, 5, 1}, {0, 0, 0, 2, 2}, {0, 1, 2, 2, 3}},
160  {{1, 2, 3, 4, 5}, {0, 0, 0, 0, 3}, {0, 2, 2, 3, 3}}
161 }};
162 
163 template <>
164 inline search_scheme_type<4, 5> constexpr optimum_search_scheme<3, 3>
165 {{
166  {{5, 4, 3, 2, 1}, {0, 0, 0, 0, 3}, {0, 0, 3, 3, 3}},
167  {{3, 4, 5, 2, 1}, {0, 0, 1, 1, 3}, {0, 1, 1, 2, 3}},
168  {{2, 3, 4, 5, 1}, {0, 0, 0, 2, 3}, {0, 1, 2, 2, 3}},
169  {{1, 2, 3, 4, 5}, {0, 0, 0, 0, 3}, {0, 2, 2, 3, 3}}
170 }};
171 
172 // TODO: add the following missing optimum search schemes (computation has not finished yet)
173 // optimum_search_scheme<i, 4>, 0 < i <= 4
174 
176 
177 } // namespace seqan3::detail
auto search(queries_t &&queries, index_t const &index, configuration_t const &cfg=search_cfg::default_configuration)
Search a query or a range of queries in an index.
Definition: search.hpp:104
Provides platform and dependency checks.