SeqAn3
The Modern C++ library for sequence analysis.
search_scheme_precomputed.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 namespace seqan3::detail
16 {
17 
22 template <uint8_t nbr_blocks>
25 struct search
26 {
28  typedef std::array<size_t, nbr_blocks> blocks_length_type;
29 
36 
38  constexpr uint8_t blocks() const noexcept
39  {
40  return nbr_blocks;
41  }
42 };
43 
46 struct search_dyn
47 {
49  typedef std::vector<size_t> blocks_length_type;
50 
57 
59  uint8_t blocks() const noexcept
60  {
61  return pi.size();
62  }
63 };
64 
66 template <uint8_t nbr_searches, uint8_t nbr_blocks>
67 using search_scheme_type = std::array<search<nbr_blocks>, nbr_searches>;
68 
70 using search_scheme_dyn_type = std::vector<search_dyn>;
71 
80 template <uint8_t min_error, uint8_t max_error>
81 inline int constexpr optimum_search_scheme;
82 
84 
85 template <>
86 inline search_scheme_type<1, 1> constexpr optimum_search_scheme<0, 0>
87 {{
88  {{1}, {0}, {0}}
89 }};
90 
91 template <>
92 inline search_scheme_type<2, 2> constexpr optimum_search_scheme<0, 1>
93 {{
94  {{1, 2}, {0, 0}, {0, 1}},
95  {{2, 1}, {0, 1}, {0, 1}}
96 }};
97 
98 template <>
99 inline search_scheme_type<2, 2> constexpr optimum_search_scheme<1, 1>
100 {{
101  {{1, 2}, {0, 1}, {0, 1}},
102  {{2, 1}, {0, 1}, {0, 1}}
103 }};
104 
105 template <>
106 inline search_scheme_type<3, 4> constexpr optimum_search_scheme<0, 2>
107 {{
108  {{1, 2, 3, 4}, {0, 0, 1, 1}, {0, 0, 2, 2}},
109  {{3, 2, 1, 4}, {0, 0, 0, 0}, {0, 1, 1, 2}},
110  {{4, 3, 2, 1}, {0, 0, 0, 2}, {0, 1, 2, 2}}
111 }};
112 
113 template <>
114 inline search_scheme_type<3, 4> constexpr optimum_search_scheme<1, 2>
115 {{
116  {{1, 2, 3, 4}, {0, 0, 0, 1}, {0, 0, 2, 2}},
117  {{3, 2, 1, 4}, {0, 0, 1, 1}, {0, 1, 1, 2}},
118  {{4, 3, 2, 1}, {0, 0, 0, 2}, {0, 1, 2, 2}}
119 }};
120 
121 template <>
122 inline search_scheme_type<3, 4> constexpr optimum_search_scheme<2, 2>
123 {{
124  {{4, 3, 2, 1}, {0, 0, 1, 2}, {0, 0, 2, 2}},
125  {{2, 3, 4, 1}, {0, 0, 0, 2}, {0, 1, 1, 2}},
126  {{1, 2, 3, 4}, {0, 0, 0, 2}, {0, 1, 2, 2}}
127 }};
128 
129 template <>
130 inline search_scheme_type<4, 5> constexpr optimum_search_scheme<0, 3>
131 {{
132  // TODO: benchmark whether the first search is really the fastest one (see \details of optimum_search_scheme)
133  {{5, 4, 3, 2, 1}, {0, 0, 0, 0, 0}, {0, 0, 3, 3, 3}},
134  {{3, 4, 5, 2, 1}, {0, 0, 1, 1, 1}, {0, 1, 1, 2, 3}},
135  {{2, 3, 4, 5, 1}, {0, 0, 0, 2, 2}, {0, 1, 2, 2, 3}},
136  {{1, 2, 3, 4, 5}, {0, 0, 0, 0, 3}, {0, 2, 2, 3, 3}}
137 }};
138 
139 template <>
140 inline search_scheme_type<4, 5> constexpr optimum_search_scheme<1, 3>
141 {{
142  {{5, 4, 3, 2, 1}, {0, 0, 0, 0, 1}, {0, 0, 3, 3, 3}},
143  {{3, 4, 5, 2, 1}, {0, 0, 1, 1, 1}, {0, 1, 1, 2, 3}},
144  {{2, 3, 4, 5, 1}, {0, 0, 0, 2, 2}, {0, 1, 2, 2, 3}},
145  {{1, 2, 3, 4, 5}, {0, 0, 0, 0, 3}, {0, 2, 2, 3, 3}}
146 }};
147 
148 template <>
149 inline search_scheme_type<4, 5> constexpr optimum_search_scheme<2, 3>
150 {{
151  {{5, 4, 3, 2, 1}, {0, 0, 0, 0, 2}, {0, 0, 3, 3, 3}},
152  {{3, 4, 5, 2, 1}, {0, 0, 1, 1, 2}, {0, 1, 1, 2, 3}},
153  {{2, 3, 4, 5, 1}, {0, 0, 0, 2, 2}, {0, 1, 2, 2, 3}},
154  {{1, 2, 3, 4, 5}, {0, 0, 0, 0, 3}, {0, 2, 2, 3, 3}}
155 }};
156 
157 template <>
158 inline search_scheme_type<4, 5> constexpr optimum_search_scheme<3, 3>
159 {{
160  {{5, 4, 3, 2, 1}, {0, 0, 0, 0, 3}, {0, 0, 3, 3, 3}},
161  {{3, 4, 5, 2, 1}, {0, 0, 1, 1, 3}, {0, 1, 1, 2, 3}},
162  {{2, 3, 4, 5, 1}, {0, 0, 0, 2, 3}, {0, 1, 2, 2, 3}},
163  {{1, 2, 3, 4, 5}, {0, 0, 0, 0, 3}, {0, 2, 2, 3, 3}}
164 }};
165 
166 // TODO: add the following missing optimum search schemes (computation has not finished yet)
167 // optimum_search_scheme<i, 4>, 0 < i <= 4
168 
170 
172 
173 } // namespace seqan3::detail
auto search(queries_t &&queries, index_t const &index, configuration_t const &cfg)
Search a query or a range of queries in an index.
Definition: search.hpp:56
Definition: aligned_sequence_concept.hpp:35
T size(T... args)