SeqAn3  3.0.2
The Modern C++ library for sequence analysis.
minimiser.hpp
Go to the documentation of this file.
1 // -----------------------------------------------------------------------------------------------------
2 // Copyright (c) 2006-2020, Knut Reinert & Freie Universität Berlin
3 // Copyright (c) 2016-2020, 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 <seqan3/std/algorithm>
16 #include <deque>
17 
20 #include <seqan3/range/concept.hpp>
22 
23 namespace seqan3::detail
24 {
25 // ---------------------------------------------------------------------------------------------------------------------
26 // minimiser_view class
27 // ---------------------------------------------------------------------------------------------------------------------
28 
47 template <std::ranges::view urng1_t,
48  std::ranges::view urng2_t = std::ranges::empty_view<seqan3::detail::empty_type>>
49 class minimiser_view : public std::ranges::view_interface<minimiser_view<urng1_t, urng2_t>>
50 {
51 private:
52  static_assert(std::ranges::forward_range<urng1_t>, "The minimiser_view only works on forward_ranges.");
53  static_assert(std::ranges::forward_range<urng2_t>, "The minimiser_view only works on forward_ranges.");
54  static_assert(std::totally_ordered<std::ranges::range_reference_t<urng1_t>>,
55  "The reference type of the underlying range must model std::totally_ordered.");
56 
58  using default_urng2_t = std::ranges::empty_view<seqan3::detail::empty_type>;
59 
61  static constexpr bool second_range_is_given = !std::same_as<urng2_t, default_urng2_t>;
62 
63  static_assert(!second_range_is_given || std::totally_ordered_with<std::ranges::range_reference_t<urng1_t>,
64  std::ranges::range_reference_t<urng2_t>>,
65  "The reference types of the underlying ranges must model std::totally_ordered_with.");
66 
68  static constexpr bool const_iterable = seqan3::const_iterable_range<urng1_t> &&
70 
72  urng1_t urange1{};
74  urng2_t urange2{};
75 
77  size_t window_size{};
78 
79  template <typename rng1_t, typename rng2_t>
80  class basic_iterator;
81 
83  using sentinel = std::default_sentinel_t;
84 
85 public:
89  minimiser_view() = default;
90  minimiser_view(minimiser_view const & rhs) = default;
91  minimiser_view(minimiser_view && rhs) = default;
92  minimiser_view & operator=(minimiser_view const & rhs) = default;
93  minimiser_view & operator=(minimiser_view && rhs) = default;
94  ~minimiser_view() = default;
95 
101  minimiser_view(urng1_t urange1, size_t const window_size) :
102  minimiser_view{std::move(urange1), default_urng2_t{}, window_size}
103  {}
104 
112  template <typename other_urng1_t>
114  requires (std::ranges::viewable_range<other_urng1_t> &&
115  std::constructible_from<urng1_t, ranges::ref_view<std::remove_reference_t<other_urng1_t>>>)
117  minimiser_view(other_urng1_t && urange1, size_t const window_size) :
118  urange1{std::views::all(std::forward<other_urng1_t>(urange1))},
119  urange2{default_urng2_t{}},
120  window_size{window_size}
121  {}
122 
130  minimiser_view(urng1_t urange1, urng2_t urange2, size_t const window_size) :
131  urange1{std::move(urange1)},
132  urange2{std::move(urange2)},
133  window_size{window_size}
134  {
135  if constexpr (second_range_is_given)
136  {
137  if (std::ranges::distance(urange1) != std::ranges::distance(urange2))
138  throw std::invalid_argument{"The two ranges do not have the same size."};
139  }
140  }
141 
153  template <typename other_urng1_t, typename other_urng2_t>
155  requires (std::ranges::viewable_range<other_urng1_t> &&
156  std::constructible_from<urng1_t, std::views::all_t<other_urng1_t>> &&
157  std::ranges::viewable_range<other_urng2_t> &&
158  std::constructible_from<urng2_t, std::views::all_t<other_urng2_t>>)
160  minimiser_view(other_urng1_t && urange1, other_urng2_t && urange2, size_t const window_size) :
161  urange1{std::views::all(std::forward<other_urng1_t>(urange1))},
162  urange2{std::views::all(std::forward<other_urng2_t>(urange2))},
163  window_size{window_size}
164  {
165  if constexpr (second_range_is_given)
166  {
167  if (std::ranges::distance(urange1) != std::ranges::distance(urange2))
168  throw std::invalid_argument{"The two ranges do not have the same size."};
169  }
170  }
172 
189  basic_iterator<urng1_t, urng2_t> begin()
190  {
191  return {std::ranges::begin(urange1),
192  std::ranges::end(urange1),
193  std::ranges::begin(urange2),
194  window_size};
195  }
196 
198  basic_iterator<urng1_t const, urng2_t const> begin() const
200  requires const_iterable
202  {
203  return {std::ranges::cbegin(urange1),
204  std::ranges::cend(urange1),
205  std::ranges::cbegin(urange2),
206  window_size};
207  }
208 
224  sentinel end() const
225  {
226  return {};
227  }
229 };
230 
232 template <std::ranges::view urng1_t, std::ranges::view urng2_t>
233 template <typename rng1_t, typename rng2_t>
234 class minimiser_view<urng1_t, urng2_t>::basic_iterator
235 {
236 private:
238  using urng1_sentinel_t = std::ranges::sentinel_t<rng1_t>;
240  using urng1_iterator_t = std::ranges::iterator_t<rng1_t>;
242  using urng2_iterator_t = std::ranges::iterator_t<rng2_t>;
243 
244  template <typename, typename>
245  friend class basic_iterator;
246 
247 public:
251  using difference_type = std::ranges::range_difference_t<rng1_t>;
254  using value_type = std::ranges::range_value_t<rng1_t>;
256  using pointer = void;
258  using reference = value_type;
260  using iterator_category = std::forward_iterator_tag;
262  using iterator_concept = iterator_category;
264 
268  basic_iterator() = default;
269  basic_iterator(basic_iterator const &) = default;
270  basic_iterator(basic_iterator &&) = default;
271  basic_iterator & operator=(basic_iterator const &) = default;
272  basic_iterator & operator=(basic_iterator &&) = default;
273  ~basic_iterator() = default;
274 
276  template <typename non_const_rng1_t, typename non_const_rng2_t>
278  requires ((std::is_const_v<rng1_t> && std::same_as<std::remove_const_t<rng1_t>, non_const_rng1_t>) &&
279  (std::is_const_v<rng1_t> && std::same_as<std::remove_const_t<rng2_t>, non_const_rng2_t>))
281  basic_iterator(basic_iterator<non_const_rng1_t, non_const_rng2_t> it) :
282  minimiser_value{std::move(it.minimiser_value)},
283  urng1_iterator{std::move(it.urng1_iterator)},
284  urng1_sentinel{std::move(it.urng1_sentinel)},
285  urng2_iterator{std::move(it.urng2_iterator)},
286  window_values{std::move(it.window_values)}
287  {}
288 
302  basic_iterator(urng1_iterator_t urng1_iterator,
303  urng1_sentinel_t urng1_sentinel,
304  urng2_iterator_t urng2_iterator,
305  size_t window_size) :
306  urng1_iterator{std::move(urng1_iterator)},
307  urng1_sentinel{std::move(urng1_sentinel)},
308  urng2_iterator{std::move(urng2_iterator)}
309  {
310  size_t size = std::ranges::distance(urng1_iterator, urng1_sentinel);
311  window_size = std::min<size_t>(window_size, size);
312 
313  window_first(window_size);
314  }
316 
320 
322  friend bool operator==(basic_iterator const & lhs, basic_iterator const & rhs)
323  {
324  return (lhs.urng1_iterator == rhs.urng1_iterator) &&
325  (rhs.urng2_iterator == rhs.urng2_iterator) &&
326  (lhs.window_values.size() == rhs.window_values.size());
327  }
328 
330  friend bool operator!=(basic_iterator const & lhs, basic_iterator const & rhs)
331  {
332  return !(lhs == rhs);
333  }
334 
336  friend bool operator==(basic_iterator const & lhs, sentinel const &)
337  {
338  return lhs.urng1_iterator == lhs.urng1_sentinel;
339  }
340 
342  friend bool operator==(sentinel const & lhs, basic_iterator const & rhs)
343  {
344  return rhs == lhs;
345  }
346 
348  friend bool operator!=(sentinel const & lhs, basic_iterator const & rhs)
349  {
350  return !(lhs == rhs);
351  }
352 
354  friend bool operator!=(basic_iterator const & lhs, sentinel const & rhs)
355  {
356  return !(lhs == rhs);
357  }
359 
361  basic_iterator & operator++() noexcept
362  {
363  next_unique_minimiser();
364  return *this;
365  }
366 
368  basic_iterator operator++(int) noexcept
369  {
370  basic_iterator tmp{*this};
371  next_unique_minimiser();
372  return tmp;
373  }
374 
376  value_type operator*() const noexcept
377  {
378  return minimiser_value;
379  }
380 
381 private:
383  value_type minimiser_value{};
384 
386  size_t minimiser_position_offset{};
387 
389  urng1_iterator_t urng1_iterator{};
391  urng1_sentinel_t urng1_sentinel{};
393  urng2_iterator_t urng2_iterator{};
394 
396  std::deque<value_type> window_values{};
397 
399  void next_unique_minimiser()
400  {
401  while (!next_minimiser()) {}
402  }
403 
405  auto window_value() const
406  {
407  if constexpr (!second_range_is_given)
408  return *urng1_iterator;
409  else
410  return std::min(*urng1_iterator, *urng2_iterator);
411  }
412 
414  void advance_window()
415  {
416  ++urng1_iterator;
417  if constexpr (second_range_is_given)
418  ++urng2_iterator;
419  }
420 
422  void window_first(size_t const window_size)
423  {
424  if (window_size == 0u)
425  return;
426 
427  for (size_t i = 0u; i < window_size - 1u; ++i)
428  {
429  window_values.push_back(window_value());
430  advance_window();
431  }
432  window_values.push_back(window_value());
433  auto minimiser_it = std::ranges::min_element(window_values, std::less_equal<value_type>{});
434  minimiser_value = *minimiser_it ;
435  minimiser_position_offset = std::distance(std::begin(window_values), minimiser_it);
436  }
437 
444  bool next_minimiser()
445  {
446  advance_window();
447  if (urng1_iterator == urng1_sentinel)
448  return true;
449 
450  value_type const new_value = window_value();
451 
452  window_values.pop_front();
453  window_values.push_back(new_value);
454 
455  if (minimiser_position_offset == 0)
456  {
457  auto minimiser_it = std::ranges::min_element(window_values, std::less_equal<value_type>{});
458  minimiser_value = *minimiser_it ;
459  minimiser_position_offset = std::distance(std::begin(window_values), minimiser_it);
460  return true;
461  }
462 
463  if (new_value < minimiser_value)
464  {
465  minimiser_value = new_value;
466  minimiser_position_offset = window_values.size() - 1;
467  return true;
468  }
469 
470  --minimiser_position_offset;
471  return false;
472  }
473 };
474 
476 template <std::ranges::viewable_range rng1_t>
477 minimiser_view(rng1_t &&, size_t const window_size) -> minimiser_view<std::views::all_t<rng1_t>>;
478 
480 template <std::ranges::viewable_range rng1_t, std::ranges::viewable_range rng2_t>
481 minimiser_view(rng1_t &&, rng2_t &&, size_t const window_size) -> minimiser_view<std::views::all_t<rng1_t>,
482  std::views::all_t<rng2_t>>;
483 
484 // ---------------------------------------------------------------------------------------------------------------------
485 // minimiser_fn (adaptor definition)
486 // ---------------------------------------------------------------------------------------------------------------------
487 
490 struct minimiser_fn
491 {
493  constexpr auto operator()(size_t const window_size) const
494  {
495  return adaptor_from_functor{*this, window_size};
496  }
497 
506  template <std::ranges::range urng1_t>
507  constexpr auto operator()(urng1_t && urange1, size_t const window_size) const
508  {
509  static_assert(std::ranges::viewable_range<urng1_t>,
510  "The range parameter to views::minimiser cannot be a temporary of a non-view range.");
511  static_assert(std::ranges::forward_range<urng1_t>,
512  "The range parameter to views::minimiser must model std::ranges::forward_range.");
513 
514  if (window_size == 1) // Would just return urange1 without any changes
515  throw std::invalid_argument{"The chosen window_size is not valid. "
516  "Please choose a value greater than 1 or use two ranges."};
517 
518  return minimiser_view{urange1, window_size};
519  }
520 };
522 
523 } // namespace seqan3::detail
524 
525 namespace seqan3::views
526 {
527 
588 inline constexpr auto minimiser = detail::minimiser_fn{};
589 
591 
592 } // namespace seqan3::views
seqan3::views
The SeqAn namespace for views.
Definition: view_iota_simd.hpp:218
std::rel_ops::operator!=
T operator!=(T... args)
std::forward_iterator_tag
std::distance
T distance(T... args)
algorithm
Adaptations of algorithms from the Ranges TS.
concept.hpp
Additional non-standard concepts for ranges.
seqan3::views::move
auto const move
A view that turns lvalue-references into rvalue-references.
Definition: move.hpp:68
const_iterable_range
Specifies requirements of an input range type for which the const version of that type satisfies the ...
std::less_equal
deque
std::invalid_argument
seqan3::pack_traits::size
constexpr size_t size
The size of a type pack.
Definition: traits.hpp:116
std::min
T min(T... args)
std::remove_reference_t
empty_type.hpp
Provides seqan3::detail::empty_type.
std::begin
T begin(T... args)
std::remove_const_t
std::end
T end(T... args)
seqan3::views::minimiser
constexpr auto minimiser
Computes minimisers for a range of comparable values. A minimiser is the smallest value in a window.
Definition: minimiser.hpp:588
detail.hpp
Auxiliary header for the views submodule .
lazy.hpp
Provides lazy template instantiation traits.