SeqAn3  3.2.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-2022, Knut Reinert & Freie Universität Berlin
3 // Copyright (c) 2016-2022, 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 
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 
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 constexpr int optimum_search_scheme{0};
88 
90 
91 template <>
92 inline constexpr search_scheme_type<1, 1> optimum_search_scheme<0, 0>{{{{1}, {0}, {0}}}};
93 
94 template <>
95 inline constexpr search_scheme_type<2, 2> optimum_search_scheme<0, 1>{
96  {{{1, 2}, {0, 0}, {0, 1}}, {{2, 1}, {0, 1}, {0, 1}}}};
97 
98 template <>
99 inline constexpr search_scheme_type<2, 2> optimum_search_scheme<1, 1>{
100  {{{1, 2}, {0, 1}, {0, 1}}, {{2, 1}, {0, 1}, {0, 1}}}};
101 
102 template <>
103 inline constexpr search_scheme_type<3, 4> optimum_search_scheme<0, 2>{{{{1, 2, 3, 4}, {0, 0, 1, 1}, {0, 0, 2, 2}},
104  {{3, 2, 1, 4}, {0, 0, 0, 0}, {0, 1, 1, 2}},
105  {{4, 3, 2, 1}, {0, 0, 0, 2}, {0, 1, 2, 2}}}};
106 
107 template <>
108 inline constexpr search_scheme_type<3, 4> optimum_search_scheme<1, 2>{{{{1, 2, 3, 4}, {0, 0, 0, 1}, {0, 0, 2, 2}},
109  {{3, 2, 1, 4}, {0, 0, 1, 1}, {0, 1, 1, 2}},
110  {{4, 3, 2, 1}, {0, 0, 0, 2}, {0, 1, 2, 2}}}};
111 
112 template <>
113 inline constexpr search_scheme_type<3, 4> optimum_search_scheme<2, 2>{{{{4, 3, 2, 1}, {0, 0, 1, 2}, {0, 0, 2, 2}},
114  {{2, 3, 4, 1}, {0, 0, 0, 2}, {0, 1, 1, 2}},
115  {{1, 2, 3, 4}, {0, 0, 0, 2}, {0, 1, 2, 2}}}};
116 
117 template <>
118 inline constexpr search_scheme_type<4, 5> optimum_search_scheme<0, 3>{
119  {// TODO: benchmark whether the first search is really the fastest one (see \details of optimum_search_scheme)
120  {{5, 4, 3, 2, 1}, {0, 0, 0, 0, 0}, {0, 0, 3, 3, 3}},
121  {{3, 4, 5, 2, 1}, {0, 0, 1, 1, 1}, {0, 1, 1, 2, 3}},
122  {{2, 3, 4, 5, 1}, {0, 0, 0, 2, 2}, {0, 1, 2, 2, 3}},
123  {{1, 2, 3, 4, 5}, {0, 0, 0, 0, 3}, {0, 2, 2, 3, 3}}}};
124 
125 template <>
126 inline constexpr search_scheme_type<4, 5> optimum_search_scheme<1, 3>{
127  {{{5, 4, 3, 2, 1}, {0, 0, 0, 0, 1}, {0, 0, 3, 3, 3}},
128  {{3, 4, 5, 2, 1}, {0, 0, 1, 1, 1}, {0, 1, 1, 2, 3}},
129  {{2, 3, 4, 5, 1}, {0, 0, 0, 2, 2}, {0, 1, 2, 2, 3}},
130  {{1, 2, 3, 4, 5}, {0, 0, 0, 0, 3}, {0, 2, 2, 3, 3}}}};
131 
132 template <>
133 inline constexpr search_scheme_type<4, 5> optimum_search_scheme<2, 3>{
134  {{{5, 4, 3, 2, 1}, {0, 0, 0, 0, 2}, {0, 0, 3, 3, 3}},
135  {{3, 4, 5, 2, 1}, {0, 0, 1, 1, 2}, {0, 1, 1, 2, 3}},
136  {{2, 3, 4, 5, 1}, {0, 0, 0, 2, 2}, {0, 1, 2, 2, 3}},
137  {{1, 2, 3, 4, 5}, {0, 0, 0, 0, 3}, {0, 2, 2, 3, 3}}}};
138 
139 template <>
140 inline constexpr search_scheme_type<4, 5> optimum_search_scheme<3, 3>{
141  {{{5, 4, 3, 2, 1}, {0, 0, 0, 0, 3}, {0, 0, 3, 3, 3}},
142  {{3, 4, 5, 2, 1}, {0, 0, 1, 1, 3}, {0, 1, 1, 2, 3}},
143  {{2, 3, 4, 5, 1}, {0, 0, 0, 2, 3}, {0, 1, 2, 2, 3}},
144  {{1, 2, 3, 4, 5}, {0, 0, 0, 0, 3}, {0, 2, 2, 3, 3}}}};
145 
146 // TODO: add the following missing optimum search schemes (computation has not finished yet)
147 // optimum_search_scheme<i, 4>, 0 < i <= 4
148 
150 
151 } // namespace seqan3::detail
requires std::ranges::forward_range< std::ranges::range_reference_t< queries_t > > &&std::same_as< range_innermost_value_t< queries_t >, typename index_t::alphabet_type > 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:103
Provides platform and dependency checks.
T size(T... args)