SeqAn3
The Modern C++ library for sequence analysis.
search_trivial.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 
14 #pragma once
15 
16 #include <type_traits>
17 
18 #include <seqan3/range/concept.hpp>
20 #include <seqan3/std/ranges>
21 
22 namespace seqan3::detail
23 {
24 
49 template <bool abort_on_hit, typename query_t, typename cursor_t, typename delegate_t>
50 inline bool search_trivial(cursor_t cur, query_t & query, typename cursor_t::size_type const query_pos,
51  search_param const error_left, delegate_t && delegate) noexcept(noexcept(delegate))
52 {
53  // Exact case (end of query sequence or no errors left)
54  if (query_pos == std::ranges::size(query) || error_left.total == 0)
55  {
56  // If not at end of query sequence, try searching the remaining suffix without any errors.
57  if (query_pos == std::ranges::size(query) || cur.extend_right(view::drop(query, query_pos)))
58  {
59  delegate(cur);
60  return true;
61  }
62  }
63  // Approximate case
64  else
65  {
66  // Insertion
67  if (error_left.insertion > 0)
68  {
69  search_param error_left2{error_left};
70  error_left2.insertion--;
71  error_left2.total--;
72 
73  // always perform a recursive call. Abort recursion if and only if recursive call found a hit and
74  // abort_on_hit is set to true.
75  if (search_trivial<abort_on_hit>(cur, query, query_pos + 1, error_left2, delegate) && abort_on_hit)
76  return true;
77  }
78 
79  // Do not allow deletions at the beginning of the query sequence
80  if (((query_pos > 0 && error_left.deletion > 0) || error_left.substitution > 0) && cur.extend_right())
81  {
82  do
83  {
84  // Match (when error_left.substitution > 0) and Mismatch
85  if (error_left.substitution > 0)
86  {
87  bool delta = cur.last_rank() != to_rank(query[query_pos]);
88  search_param error_left2{error_left};
89  error_left2.total -= delta;
90  error_left2.substitution -= delta;
91 
92  if (search_trivial<abort_on_hit>(cur, query, query_pos + 1, error_left2, delegate) && abort_on_hit)
93  return true;
94  }
95 
96  // Deletion (Do not allow deletions at the beginning of the query sequence.)
97  if (query_pos > 0)
98  {
99  // Match (when error_left.substitution == 0)
100  if (error_left.substitution == 0 && cur.last_rank() == to_rank(query[query_pos]))
101  {
102  if (search_trivial<abort_on_hit>(cur, query, query_pos + 1, error_left, delegate) &&
103  abort_on_hit)
104  {
105  return true;
106  }
107  }
108 
109  // Deletions at the end of the sequence are not allowed. This cannot happen: when the algorithm
110  // arrives here, it cannot be at the end of the query and since deletions do not touch the query
111  // (i.e. increase query_pos) it won't be at the end of the query after the deletion.
112  if (error_left.deletion > 0)
113  {
114  search_param error_left2{error_left};
115  error_left2.total--;
116  error_left2.deletion--;
117 
118  if (search_trivial<abort_on_hit>(cur, query, query_pos, error_left2, delegate) && abort_on_hit)
119  return true;
120  }
121  }
122  } while (cur.cycle_back());
123  }
124  else
125  {
126  // Match (when error_left.substitution == 0)
127  if (cur.extend_right(query[query_pos]))
128  {
129  if (search_trivial<abort_on_hit>(cur, query, query_pos + 1, error_left, delegate) && abort_on_hit)
130  return true;
131  }
132  }
133  }
134 
135  return false;
136 }
137 
156 template <bool abort_on_hit, typename index_t, typename query_t, typename delegate_t>
157 inline void search_trivial(index_t const & index, query_t & query, search_param const error_left,
158  delegate_t && delegate) noexcept(noexcept(delegate))
159 {
160  search_trivial<abort_on_hit>(index.begin(), query, 0, error_left, delegate);
161 }
162 
164 
165 } // namespace seqan3::detail
constexpr auto to_rank
Return the rank representation of a (semi-)alphabet object.
Definition: concept.hpp:103
constexpr auto drop
A view adaptor that returns all elements after n from the underlying range (or an empty range if the ...
Definition: drop.hpp:171
::ranges::size size
Alias for ranges::size. Obtains the size of a range whose size can be calculated in constant time...
Definition: ranges:189
Additional non-standard concepts for ranges.
Adaptations of concepts from the Ranges TS.
Definition: aligned_sequence_concept.hpp:35
Provides data structures used by different search algorithms.