SeqAn3 3.4.0-rc.1
The Modern C++ library for sequence analysis.
Loading...
Searching...
No Matches
minimiser.hpp
Go to the documentation of this file.
1// SPDX-FileCopyrightText: 2006-2024 Knut Reinert & Freie Universität Berlin
2// SPDX-FileCopyrightText: 2016-2024 Knut Reinert & MPI für molekulare Genetik
3// SPDX-License-Identifier: BSD-3-Clause
4
10#pragma once
11
12#include <algorithm>
13#include <deque>
14
20
21namespace seqan3::detail
22{
23// ---------------------------------------------------------------------------------------------------------------------
24// minimiser_view class
25// ---------------------------------------------------------------------------------------------------------------------
26
45template <std::ranges::view urng1_t, std::ranges::view urng2_t = std::ranges::empty_view<seqan3::detail::empty_type>>
46class minimiser_view : public std::ranges::view_interface<minimiser_view<urng1_t, urng2_t>>
47{
48private:
49 static_assert(std::ranges::forward_range<urng1_t>, "The minimiser_view only works on forward_ranges.");
50 static_assert(std::ranges::forward_range<urng2_t>, "The minimiser_view only works on forward_ranges.");
51 static_assert(std::totally_ordered<std::ranges::range_reference_t<urng1_t>>,
52 "The reference type of the underlying range must model std::totally_ordered.");
53
55 using default_urng2_t = std::ranges::empty_view<seqan3::detail::empty_type>;
56
58 static constexpr bool second_range_is_given = !std::same_as<urng2_t, default_urng2_t>;
59
60 static_assert(!second_range_is_given
61 || std::totally_ordered_with<std::ranges::range_reference_t<urng1_t>,
62 std::ranges::range_reference_t<urng2_t>>,
63 "The reference types of the underlying ranges must model std::totally_ordered_with.");
64
66 static constexpr bool const_iterable =
68
70 urng1_t urange1{};
72 urng2_t urange2{};
73
75 size_t window_size{};
76
77 template <bool const_range>
78 class basic_iterator;
79
81 using sentinel = std::default_sentinel_t;
82
83public:
87 minimiser_view()
88 requires std::default_initializable<urng1_t> && std::default_initializable<urng2_t>
89 = 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 explicit 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>
113 requires (std::ranges::viewable_range<other_urng1_t>
114 && std::constructible_from<urng1_t, std::ranges::ref_view<std::remove_reference_t<other_urng1_t>>>)
115 explicit minimiser_view(other_urng1_t && urange1, size_t const window_size) :
116 urange1{std::views::all(std::forward<other_urng1_t>(urange1))},
117 urange2{default_urng2_t{}},
118 window_size{window_size}
119 {}
120
128 explicit minimiser_view(urng1_t urange1, urng2_t urange2, size_t const window_size) :
129 urange1{std::move(urange1)},
130 urange2{std::move(urange2)},
131 window_size{window_size}
132 {
133 if constexpr (second_range_is_given)
134 {
135 if (std::ranges::distance(urange1) != std::ranges::distance(urange2))
136 throw std::invalid_argument{"The two ranges do not have the same size."};
137 }
138 }
139
151 template <typename other_urng1_t, typename other_urng2_t>
152 requires (std::ranges::viewable_range<other_urng1_t>
153 && std::constructible_from<urng1_t, std::views::all_t<other_urng1_t>>
154 && std::ranges::viewable_range<other_urng2_t>
155 && std::constructible_from<urng2_t, std::views::all_t<other_urng2_t>>)
156 explicit minimiser_view(other_urng1_t && urange1, other_urng2_t && urange2, size_t const window_size) :
157 urange1{std::views::all(std::forward<other_urng1_t>(urange1))},
158 urange2{std::views::all(std::forward<other_urng2_t>(urange2))},
159 window_size{window_size}
160 {
161 if constexpr (second_range_is_given)
162 {
163 if (std::ranges::distance(urange1) != std::ranges::distance(urange2))
164 throw std::invalid_argument{"The two ranges do not have the same size."};
165 }
166 }
168
185 basic_iterator<false> begin()
186 {
187 return {std::ranges::begin(urange1), std::ranges::end(urange1), std::ranges::begin(urange2), window_size};
188 }
189
191 basic_iterator<true> begin() const
192 requires const_iterable
193 {
194 return {std::ranges::begin(urange1), std::ranges::end(urange1), std::ranges::begin(urange2), window_size};
195 }
196
212 sentinel end() const
213 {
214 return {};
215 }
217};
218
220template <std::ranges::view urng1_t, std::ranges::view urng2_t>
221template <bool const_range>
222class minimiser_view<urng1_t, urng2_t>::basic_iterator
223{
224private:
226 using urng1_sentinel_t = maybe_const_sentinel_t<const_range, urng1_t>;
228 using urng1_iterator_t = maybe_const_iterator_t<const_range, urng1_t>;
230 using urng2_iterator_t = maybe_const_iterator_t<const_range, urng2_t>;
231
232 template <bool>
233 friend class basic_iterator;
234
235public:
240 using difference_type = std::ranges::range_difference_t<urng1_t>;
242 using value_type = std::ranges::range_value_t<urng1_t>;
244 using pointer = void;
246 using reference = value_type;
248 using iterator_category = std::forward_iterator_tag;
250 using iterator_concept = iterator_category;
252
256 basic_iterator() = default;
257 basic_iterator(basic_iterator const &) = default;
258 basic_iterator(basic_iterator &&) = default;
259 basic_iterator & operator=(basic_iterator const &) = default;
260 basic_iterator & operator=(basic_iterator &&) = default;
261 ~basic_iterator() = default;
262
264 basic_iterator(basic_iterator<!const_range> const & it)
265 requires const_range
266 :
267 minimiser_value{std::move(it.minimiser_value)},
268 urng1_iterator{std::move(it.urng1_iterator)},
269 urng1_sentinel{std::move(it.urng1_sentinel)},
270 urng2_iterator{std::move(it.urng2_iterator)},
271 window_values{std::move(it.window_values)}
272 {}
273
287 basic_iterator(urng1_iterator_t urng1_iterator,
288 urng1_sentinel_t urng1_sentinel,
289 urng2_iterator_t urng2_iterator,
290 size_t window_size) :
291 urng1_iterator{std::move(urng1_iterator)},
292 urng1_sentinel{std::move(urng1_sentinel)},
293 urng2_iterator{std::move(urng2_iterator)}
294 {
295 size_t size = std::ranges::distance(urng1_iterator, urng1_sentinel);
296 window_size = std::min<size_t>(window_size, size);
297
298 window_first(window_size);
299 }
301
305
307 friend bool operator==(basic_iterator const & lhs, basic_iterator const & rhs)
308 {
309 return (lhs.urng1_iterator == rhs.urng1_iterator) && (rhs.urng2_iterator == rhs.urng2_iterator)
310 && (lhs.window_values.size() == rhs.window_values.size());
311 }
312
314 friend bool operator!=(basic_iterator const & lhs, basic_iterator const & rhs)
315 {
316 return !(lhs == rhs);
317 }
318
320 friend bool operator==(basic_iterator const & lhs, sentinel const &)
321 {
322 return lhs.urng1_iterator == lhs.urng1_sentinel;
323 }
324
326 friend bool operator==(sentinel const & lhs, basic_iterator const & rhs)
327 {
328 return rhs == lhs;
329 }
330
332 friend bool operator!=(sentinel const & lhs, basic_iterator const & rhs)
333 {
334 return !(lhs == rhs);
335 }
336
338 friend bool operator!=(basic_iterator const & lhs, sentinel const & rhs)
339 {
340 return !(lhs == rhs);
341 }
343
345 basic_iterator & operator++() noexcept
346 {
347 next_unique_minimiser();
348 return *this;
349 }
350
352 basic_iterator operator++(int) noexcept
353 {
354 basic_iterator tmp{*this};
355 next_unique_minimiser();
356 return tmp;
357 }
358
360 value_type operator*() const noexcept
361 {
362 return minimiser_value;
363 }
364
366 constexpr urng1_iterator_t const & base() const & noexcept
367 {
368 return urng1_iterator;
369 }
370
372 constexpr urng1_iterator_t base() &&
373 {
374 return std::move(urng1_iterator);
375 }
376
377private:
379 value_type minimiser_value{};
380
382 size_t minimiser_position_offset{};
383
385 urng1_iterator_t urng1_iterator{};
387 urng1_sentinel_t urng1_sentinel{};
389 urng2_iterator_t urng2_iterator{};
390
392 std::deque<value_type> window_values{};
393
395 void next_unique_minimiser()
396 {
397 while (!next_minimiser())
398 {}
399 }
400
402 auto window_value() const
403 {
404 if constexpr (!second_range_is_given)
405 return *urng1_iterator;
406 else
407 return std::min(*urng1_iterator, *urng2_iterator);
408 }
409
411 void advance_window()
412 {
413 ++urng1_iterator;
414 if constexpr (second_range_is_given)
415 ++urng2_iterator;
416 }
417
419 void window_first(size_t const window_size)
420 {
421 if (window_size == 0u)
422 return;
423
424 for (size_t i = 0u; i < window_size - 1u; ++i)
425 {
426 window_values.push_back(window_value());
427 advance_window();
428 }
429 window_values.push_back(window_value());
430 auto minimiser_it = std::ranges::min_element(window_values, std::less_equal<value_type>{});
431 minimiser_value = *minimiser_it;
432 minimiser_position_offset = std::distance(std::begin(window_values), minimiser_it);
433 }
434
441 bool next_minimiser()
442 {
443 advance_window();
444 if (urng1_iterator == urng1_sentinel)
445 return true;
446
447 value_type const new_value = window_value();
448
449 window_values.pop_front();
450 window_values.push_back(new_value);
451
452 if (minimiser_position_offset == 0)
453 {
454 auto minimiser_it = std::ranges::min_element(window_values, std::less_equal<value_type>{});
455 minimiser_value = *minimiser_it;
456 minimiser_position_offset = std::distance(std::begin(window_values), minimiser_it);
457 return true;
458 }
459
460 if (new_value < minimiser_value)
461 {
462 minimiser_value = new_value;
463 minimiser_position_offset = window_values.size() - 1;
464 return true;
465 }
466
467 --minimiser_position_offset;
468 return false;
469 }
470};
471
473template <std::ranges::viewable_range rng1_t>
474minimiser_view(rng1_t &&, size_t const window_size) -> minimiser_view<std::views::all_t<rng1_t>>;
475
477template <std::ranges::viewable_range rng1_t, std::ranges::viewable_range rng2_t>
478minimiser_view(rng1_t &&, rng2_t &&, size_t const window_size)
479 -> minimiser_view<std::views::all_t<rng1_t>, std::views::all_t<rng2_t>>;
480
481// ---------------------------------------------------------------------------------------------------------------------
482// minimiser_fn (adaptor definition)
483// ---------------------------------------------------------------------------------------------------------------------
484
488struct minimiser_fn
489{
491 constexpr auto operator()(size_t const window_size) const
492 {
493 return adaptor_from_functor{*this, window_size};
494 }
495
504 template <std::ranges::range urng1_t>
505 constexpr auto operator()(urng1_t && urange1, size_t const window_size) const
506 {
507 static_assert(std::ranges::viewable_range<urng1_t>,
508 "The range parameter to views::minimiser cannot be a temporary of a non-view range.");
509 static_assert(std::ranges::forward_range<urng1_t>,
510 "The range parameter to views::minimiser must model std::ranges::forward_range.");
511
512 if (window_size == 1) // Would just return urange1 without any changes
513 throw std::invalid_argument{"The chosen window_size is not valid. "
514 "Please choose a value greater than 1 or use two ranges."};
515
516 return minimiser_view{urange1, window_size};
517 }
518};
520
521} // namespace seqan3::detail
522
523namespace seqan3::views
524{
583inline constexpr auto minimiser = detail::minimiser_fn{};
584
585} // namespace seqan3::views
Provides seqan3::detail::adaptor_from_functor.
T begin(T... args)
Provides various transformation traits used by the range module.
T distance(T... args)
Provides seqan3::detail::empty_type.
T end(T... args)
constexpr auto minimiser
Computes minimisers for a range of comparable values. A minimiser is the smallest value in a window.
Definition minimiser.hpp:583
constexpr size_t size
The size of a type pack.
Definition type_pack/traits.hpp:143
Specifies requirements of an input range type for which the const version of that type satisfies the ...
Provides lazy template instantiation traits.
T min_element(T... args)
T min(T... args)
T move(T... args)
The SeqAn namespace for views.
Definition char_strictly_to.hpp:19
SeqAn specific customisations in the standard namespace.
T operator!=(T... args)
Additional non-standard concepts for ranges.
Hide me