24namespace seqan3::detail
48template <std::ranges::view urng1_t, std::ranges::view urng2_t = std::ranges::empty_view<seqan3::detail::empty_type>>
49class minimiser_view :
public std::ranges::view_interface<minimiser_view<urng1_t, urng2_t>>
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.");
58 using default_urng2_t = std::ranges::empty_view<seqan3::detail::empty_type>;
61 static constexpr bool second_range_is_given = !std::same_as<urng2_t, default_urng2_t>;
63 static_assert(!second_range_is_given
64 || 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.");
69 static constexpr bool const_iterable =
80 template <
bool const_range>
84 using sentinel = std::default_sentinel_t;
91 requires std::default_initializable<urng1_t> &&
std::default_initializable<urng2_t>
93 minimiser_view(minimiser_view const & rhs) = default;
94 minimiser_view(minimiser_view && rhs) = default;
95 minimiser_view & operator=(minimiser_view const & rhs) = default;
96 minimiser_view & operator=(minimiser_view && rhs) = default;
97 ~minimiser_view() = default;
104 minimiser_view(urng1_t urange1,
size_t const window_size) :
105 minimiser_view{std::move(urange1), default_urng2_t{}, window_size}
115 template <
typename other_urng1_t>
116 requires (std::ranges::viewable_range<other_urng1_t>
117 && std::constructible_from<urng1_t, std::ranges::ref_view<std::remove_reference_t<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>
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>>)
159 minimiser_view(other_urng1_t && urange1, other_urng2_t && urange2,
size_t const window_size) :
160 urange1{std::views::all(std::forward<other_urng1_t>(urange1))},
161 urange2{std::views::all(std::forward<other_urng2_t>(urange2))},
162 window_size{window_size}
164 if constexpr (second_range_is_given)
166 if (std::ranges::distance(urange1) != std::ranges::distance(urange2))
188 basic_iterator<false>
begin()
194 basic_iterator<true>
begin() const
195 requires const_iterable
223template <std::ranges::view urng1_t, std::ranges::view urng2_t>
224template <
bool const_range>
225class minimiser_view<urng1_t, urng2_t>::basic_iterator
229 using urng1_sentinel_t = maybe_const_sentinel_t<const_range, urng1_t>;
231 using urng1_iterator_t = maybe_const_iterator_t<const_range, urng1_t>;
233 using urng2_iterator_t = maybe_const_iterator_t<const_range, urng2_t>;
236 friend class basic_iterator;
243 using difference_type = std::ranges::range_difference_t<urng1_t>;
245 using value_type = std::ranges::range_value_t<urng1_t>;
247 using pointer = void;
249 using reference = value_type;
253 using iterator_concept = iterator_category;
259 basic_iterator() =
default;
260 basic_iterator(basic_iterator
const &) =
default;
261 basic_iterator(basic_iterator &&) =
default;
262 basic_iterator & operator=(basic_iterator
const &) =
default;
263 basic_iterator & operator=(basic_iterator &&) =
default;
264 ~basic_iterator() =
default;
267 basic_iterator(basic_iterator<!const_range>
const & it)
270 minimiser_value{std::move(it.minimiser_value)},
271 urng1_iterator{std::move(it.urng1_iterator)},
272 urng1_sentinel{std::move(it.urng1_sentinel)},
273 urng2_iterator{std::move(it.urng2_iterator)},
274 window_values{std::move(it.window_values)}
290 basic_iterator(urng1_iterator_t urng1_iterator,
291 urng1_sentinel_t urng1_sentinel,
292 urng2_iterator_t urng2_iterator,
293 size_t window_size) :
294 urng1_iterator{
std::
move(urng1_iterator)},
295 urng1_sentinel{
std::
move(urng1_sentinel)},
296 urng2_iterator{
std::
move(urng2_iterator)}
298 size_t size = std::ranges::distance(urng1_iterator, urng1_sentinel);
299 window_size = std::min<size_t>(window_size,
size);
301 window_first(window_size);
310 friend bool operator==(basic_iterator
const & lhs, basic_iterator
const & rhs)
312 return (lhs.urng1_iterator == rhs.urng1_iterator) && (rhs.urng2_iterator == rhs.urng2_iterator)
313 && (lhs.window_values.size() == rhs.window_values.size());
317 friend bool operator!=(basic_iterator
const & lhs, basic_iterator
const & rhs)
319 return !(lhs == rhs);
323 friend bool operator==(basic_iterator
const & lhs, sentinel
const &)
325 return lhs.urng1_iterator == lhs.urng1_sentinel;
329 friend bool operator==(sentinel
const & lhs, basic_iterator
const & rhs)
335 friend bool operator!=(sentinel
const & lhs, basic_iterator
const & rhs)
337 return !(lhs == rhs);
341 friend bool operator!=(basic_iterator
const & lhs, sentinel
const & rhs)
343 return !(lhs == rhs);
348 basic_iterator & operator++() noexcept
350 next_unique_minimiser();
355 basic_iterator operator++(
int)
noexcept
357 basic_iterator tmp{*
this};
358 next_unique_minimiser();
363 value_type operator*() const noexcept
365 return minimiser_value;
369 constexpr urng1_iterator_t
const & base() const & noexcept
371 return urng1_iterator;
375 constexpr urng1_iterator_t base() &&
377 return std::move(urng1_iterator);
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())
405 auto window_value()
const
407 if constexpr (!second_range_is_given)
408 return *urng1_iterator;
410 return std::min(*urng1_iterator, *urng2_iterator);
414 void advance_window()
417 if constexpr (second_range_is_given)
422 void window_first(
size_t const window_size)
424 if (window_size == 0u)
427 for (
size_t i = 0u; i < window_size - 1u; ++i)
429 window_values.push_back(window_value());
432 window_values.push_back(window_value());
434 minimiser_value = *minimiser_it;
444 bool next_minimiser()
447 if (urng1_iterator == urng1_sentinel)
450 value_type
const new_value = window_value();
452 window_values.pop_front();
453 window_values.push_back(new_value);
455 if (minimiser_position_offset == 0)
458 minimiser_value = *minimiser_it;
463 if (new_value < minimiser_value)
465 minimiser_value = new_value;
466 minimiser_position_offset = window_values.size() - 1;
470 --minimiser_position_offset;
476template <std::ranges::viewable_range rng1_t>
477minimiser_view(rng1_t &&,
size_t const window_size) -> minimiser_view<std::views::all_t<rng1_t>>;
480template <std::ranges::viewable_range rng1_t, std::ranges::viewable_range rng2_t>
481minimiser_view(rng1_t &&, rng2_t &&,
size_t const window_size)
482 -> minimiser_view<std::views::all_t<rng1_t>, std::views::all_t<rng2_t>>;
494 constexpr auto operator()(
size_t const window_size)
const
496 return adaptor_from_functor{*
this, window_size};
507 template <std::ranges::range urng1_t>
508 constexpr auto operator()(urng1_t && urange1,
size_t const window_size)
const
510 static_assert(std::ranges::viewable_range<urng1_t>,
511 "The range parameter to views::minimiser cannot be a temporary of a non-view range.");
512 static_assert(std::ranges::forward_range<urng1_t>,
513 "The range parameter to views::minimiser must model std::ranges::forward_range.");
515 if (window_size == 1)
517 "Please choose a value greater than 1 or use two ranges."};
519 return minimiser_view{urange1, window_size};
586inline constexpr auto minimiser = detail::minimiser_fn{};
Provides seqan3::detail::adaptor_from_functor.
Provides various transformation traits used by the range module.
Provides seqan3::detail::empty_type.
constexpr auto minimiser
Computes minimisers for a range of comparable values. A minimiser is the smallest value in a window.
Definition: minimiser.hpp:586
constexpr size_t size
The size of a type pack.
Definition: traits.hpp:146
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_strictly_to.hpp:22
SeqAn specific customisations in the standard namespace.
Additional non-standard concepts for ranges.