24 namespace seqan3::detail
48 template <std::ranges::view urng1_t,
49 std::ranges::view urng2_t = std::ranges::empty_view<seqan3::detail::empty_type>>
50 class minimiser_view :
public std::ranges::view_interface<minimiser_view<urng1_t, urng2_t>>
53 static_assert(std::ranges::forward_range<urng1_t>,
"The minimiser_view only works on forward_ranges.");
54 static_assert(std::ranges::forward_range<urng2_t>,
"The minimiser_view only works on forward_ranges.");
55 static_assert(std::totally_ordered<std::ranges::range_reference_t<urng1_t>>,
56 "The reference type of the underlying range must model std::totally_ordered.");
59 using default_urng2_t = std::ranges::empty_view<seqan3::detail::empty_type>;
62 static constexpr
bool second_range_is_given = !std::same_as<urng2_t, default_urng2_t>;
64 static_assert(!second_range_is_given || std::totally_ordered_with<std::ranges::range_reference_t<urng1_t>,
65 std::ranges::range_reference_t<urng2_t>>,
66 "The reference types of the underlying ranges must model std::totally_ordered_with.");
80 template <
bool const_range>
84 using sentinel = std::default_sentinel_t;
90 minimiser_view() =
default;
91 minimiser_view(minimiser_view
const & rhs) =
default;
92 minimiser_view(minimiser_view && rhs) =
default;
93 minimiser_view & operator=(minimiser_view
const & rhs) =
default;
94 minimiser_view & operator=(minimiser_view && rhs) =
default;
95 ~minimiser_view() =
default;
102 minimiser_view(urng1_t urange1,
size_t const window_size) :
103 minimiser_view{
std::
move(urange1), default_urng2_t{}, window_size}
113 template <
typename other_urng1_t>
115 requires (std::ranges::viewable_range<other_urng1_t> &&
118 minimiser_view(other_urng1_t && urange1,
size_t const window_size) :
119 urange1{std::views::all(std::forward<other_urng1_t>(urange1))},
120 urange2{default_urng2_t{}},
121 window_size{window_size}
131 minimiser_view(urng1_t urange1, urng2_t urange2,
size_t const window_size) :
134 window_size{window_size}
136 if constexpr (second_range_is_given)
138 if (std::ranges::distance(urange1) != std::ranges::distance(urange2))
154 template <
typename other_urng1_t,
typename other_urng2_t>
156 requires (std::ranges::viewable_range<other_urng1_t> &&
157 std::constructible_from<urng1_t, std::views::all_t<other_urng1_t>> &&
158 std::ranges::viewable_range<other_urng2_t> &&
159 std::constructible_from<urng2_t, std::views::all_t<other_urng2_t>>)
161 minimiser_view(other_urng1_t && urange1, other_urng2_t && urange2,
size_t const window_size) :
162 urange1{std::views::all(std::forward<other_urng1_t>(urange1))},
163 urange2{std::views::all(std::forward<other_urng2_t>(urange2))},
164 window_size{window_size}
166 if constexpr (second_range_is_given)
168 if (std::ranges::distance(urange1) != std::ranges::distance(urange2))
190 basic_iterator<false>
begin()
193 std::ranges::end(urange1),
199 basic_iterator<true>
begin() const
201 requires const_iterable
205 std::ranges::cend(urange1),
233 template <std::ranges::view urng1_t, std::ranges::view urng2_t>
234 template <
bool const_range>
235 class minimiser_view<urng1_t, urng2_t>::basic_iterator
239 using urng1_sentinel_t = maybe_const_sentinel_t<const_range, urng1_t>;
241 using urng1_iterator_t = maybe_const_iterator_t<const_range, urng1_t>;
243 using urng2_iterator_t = maybe_const_iterator_t<const_range, urng2_t>;
246 friend class basic_iterator;
253 using difference_type = std::ranges::range_difference_t<urng1_t>;
255 using value_type = std::ranges::range_value_t<urng1_t>;
257 using pointer = void;
259 using reference = value_type;
263 using iterator_concept = iterator_category;
269 basic_iterator() =
default;
270 basic_iterator(basic_iterator
const &) =
default;
271 basic_iterator(basic_iterator &&) =
default;
272 basic_iterator & operator=(basic_iterator
const &) =
default;
273 basic_iterator & operator=(basic_iterator &&) =
default;
274 ~basic_iterator() =
default;
277 basic_iterator(basic_iterator<!const_range>
const & it)
281 : minimiser_value{
std::move(it.minimiser_value)},
282 urng1_iterator{
std::move(it.urng1_iterator)},
283 urng1_sentinel{
std::move(it.urng1_sentinel)},
284 urng2_iterator{
std::move(it.urng2_iterator)},
285 window_values{
std::move(it.window_values)}
301 basic_iterator(urng1_iterator_t urng1_iterator,
302 urng1_sentinel_t urng1_sentinel,
303 urng2_iterator_t urng2_iterator,
304 size_t window_size) :
305 urng1_iterator{
std::
move(urng1_iterator)},
306 urng1_sentinel{
std::
move(urng1_sentinel)},
307 urng2_iterator{
std::
move(urng2_iterator)}
309 size_t size = std::ranges::distance(urng1_iterator, urng1_sentinel);
310 window_size = std::min<size_t>(window_size,
size);
312 window_first(window_size);
321 friend bool operator==(basic_iterator
const & lhs, basic_iterator
const & rhs)
323 return (lhs.urng1_iterator == rhs.urng1_iterator) &&
324 (rhs.urng2_iterator == rhs.urng2_iterator) &&
325 (lhs.window_values.size() == rhs.window_values.size());
329 friend bool operator!=(basic_iterator
const & lhs, basic_iterator
const & rhs)
331 return !(lhs == rhs);
335 friend bool operator==(basic_iterator
const & lhs, sentinel
const &)
337 return lhs.urng1_iterator == lhs.urng1_sentinel;
341 friend bool operator==(sentinel
const & lhs, basic_iterator
const & rhs)
347 friend bool operator!=(sentinel
const & lhs, basic_iterator
const & rhs)
349 return !(lhs == rhs);
353 friend bool operator!=(basic_iterator
const & lhs, sentinel
const & rhs)
355 return !(lhs == rhs);
360 basic_iterator & operator++() noexcept
362 next_unique_minimiser();
367 basic_iterator operator++(
int) noexcept
369 basic_iterator tmp{*
this};
370 next_unique_minimiser();
375 value_type operator*() const noexcept
377 return minimiser_value;
382 value_type minimiser_value{};
385 size_t minimiser_position_offset{};
388 urng1_iterator_t urng1_iterator{};
390 urng1_sentinel_t urng1_sentinel{};
392 urng2_iterator_t urng2_iterator{};
398 void next_unique_minimiser()
400 while (!next_minimiser()) {}
404 auto window_value()
const
406 if constexpr (!second_range_is_given)
407 return *urng1_iterator;
409 return std::min(*urng1_iterator, *urng2_iterator);
413 void advance_window()
416 if constexpr (second_range_is_given)
421 void window_first(
size_t const window_size)
423 if (window_size == 0u)
426 for (
size_t i = 0u; i < window_size - 1u; ++i)
428 window_values.push_back(window_value());
431 window_values.push_back(window_value());
433 minimiser_value = *minimiser_it ;
443 bool next_minimiser()
446 if (urng1_iterator == urng1_sentinel)
449 value_type
const new_value = window_value();
451 window_values.pop_front();
452 window_values.push_back(new_value);
454 if (minimiser_position_offset == 0)
457 minimiser_value = *minimiser_it ;
462 if (new_value < minimiser_value)
464 minimiser_value = new_value;
465 minimiser_position_offset = window_values.size() - 1;
469 --minimiser_position_offset;
475 template <std::ranges::viewable_range rng1_t>
476 minimiser_view(rng1_t &&,
size_t const window_size) -> minimiser_view<std::views::all_t<rng1_t>>;
479 template <std::ranges::viewable_range rng1_t, std::ranges::viewable_range rng2_t>
480 minimiser_view(rng1_t &&, rng2_t &&,
size_t const window_size) -> minimiser_view<std::views::all_t<rng1_t>,
481 std::views::all_t<rng2_t>>;
492 constexpr
auto operator()(
size_t const window_size)
const
494 return adaptor_from_functor{*
this, window_size};
505 template <std::ranges::range urng1_t>
506 constexpr
auto operator()(urng1_t && urange1,
size_t const window_size)
const
508 static_assert(std::ranges::viewable_range<urng1_t>,
509 "The range parameter to views::minimiser cannot be a temporary of a non-view range.");
510 static_assert(std::ranges::forward_range<urng1_t>,
511 "The range parameter to views::minimiser must model std::ranges::forward_range.");
513 if (window_size == 1)
515 "Please choose a value greater than 1 or use two ranges."};
517 return minimiser_view{urange1, window_size};
589 inline constexpr
auto minimiser = detail::minimiser_fn{};
Provides seqan3::detail::adaptor_from_functor.
Adaptations of algorithms from the Ranges TS.
Provides various transformation traits used by the range module.
Provides seqan3::detail::empty_type.
constexpr size_t size
The size of a type pack.
Definition: traits.hpp:151
constexpr auto minimiser
Computes minimisers for a range of comparable values. A minimiser is the smallest value in a window.
Definition: minimiser.hpp:589
auto const move
A view that turns lvalue-references into rvalue-references.
Definition: move.hpp:74
Specifies requirements of an input range type for which the const version of that type satisfies the ...
Provides lazy template instantiation traits.
The SeqAn namespace for views.
Definition: char_to.hpp:22
SeqAn specific customisations in the standard namespace.
Additional non-standard concepts for ranges.