21namespace seqan3::detail
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>>
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.");
55 using default_urng2_t = std::ranges::empty_view<seqan3::detail::empty_type>;
58 static constexpr bool second_range_is_given = !std::same_as<urng2_t, default_urng2_t>;
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.");
66 static constexpr bool const_iterable =
77 template <
bool const_range>
81 using sentinel = std::default_sentinel_t;
88 requires std::default_initializable<urng1_t> &&
std::default_initializable<urng2_t>
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;
101 explicit minimiser_view(urng1_t urange1,
size_t const window_size) :
102 minimiser_view{std::move(urange1), default_urng2_t{}, window_size}
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}
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}
133 if constexpr (second_range_is_given)
135 if (std::ranges::distance(urange1) != std::ranges::distance(urange2))
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}
161 if constexpr (second_range_is_given)
163 if (std::ranges::distance(urange1) != std::ranges::distance(urange2))
185 basic_iterator<false>
begin()
187 return {std::ranges::begin(urange1), std::ranges::end(urange1), std::ranges::begin(urange2), window_size};
191 basic_iterator<true>
begin() const
192 requires const_iterable
194 return {std::ranges::begin(urange1), std::ranges::end(urange1), std::ranges::begin(urange2), window_size};
220template <std::ranges::view urng1_t, std::ranges::view urng2_t>
221template <
bool const_range>
222class minimiser_view<urng1_t, urng2_t>::basic_iterator
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>;
233 friend class basic_iterator;
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;
250 using iterator_concept = iterator_category;
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;
264 basic_iterator(basic_iterator<!const_range>
const & it)
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)}
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)}
295 size_t size = std::ranges::distance(urng1_iterator, urng1_sentinel);
296 window_size = std::min<size_t>(window_size, size);
298 window_first(window_size);
307 friend bool operator==(basic_iterator
const & lhs, basic_iterator
const & rhs)
309 return (lhs.urng1_iterator == rhs.urng1_iterator) && (rhs.urng2_iterator == rhs.urng2_iterator)
310 && (lhs.window_values.size() == rhs.window_values.size());
314 friend bool operator!=(basic_iterator
const & lhs, basic_iterator
const & rhs)
316 return !(lhs == rhs);
320 friend bool operator==(basic_iterator
const & lhs, sentinel
const &)
322 return lhs.urng1_iterator == lhs.urng1_sentinel;
326 friend bool operator==(sentinel
const & lhs, basic_iterator
const & rhs)
332 friend bool operator!=(sentinel
const & lhs, basic_iterator
const & rhs)
334 return !(lhs == rhs);
338 friend bool operator!=(basic_iterator
const & lhs, sentinel
const & rhs)
340 return !(lhs == rhs);
345 basic_iterator & operator++() noexcept
347 next_unique_minimiser();
352 basic_iterator operator++(
int)
noexcept
354 basic_iterator tmp{*
this};
355 next_unique_minimiser();
360 value_type operator*() const noexcept
362 return minimiser_value;
366 constexpr urng1_iterator_t
const & base() const & noexcept
368 return urng1_iterator;
372 constexpr urng1_iterator_t base() &&
374 return std::move(urng1_iterator);
379 value_type minimiser_value{};
382 size_t minimiser_position_offset{};
385 urng1_iterator_t urng1_iterator{};
387 urng1_sentinel_t urng1_sentinel{};
389 urng2_iterator_t urng2_iterator{};
395 void next_unique_minimiser()
397 while (!next_minimiser())
402 auto window_value()
const
404 if constexpr (!second_range_is_given)
405 return *urng1_iterator;
407 return std::min(*urng1_iterator, *urng2_iterator);
411 void advance_window()
414 if constexpr (second_range_is_given)
419 void window_first(
size_t const window_size)
421 if (window_size == 0u)
424 for (
size_t i = 0u; i < window_size - 1u; ++i)
426 window_values.push_back(window_value());
429 window_values.push_back(window_value());
431 minimiser_value = *minimiser_it;
441 bool next_minimiser()
444 if (urng1_iterator == urng1_sentinel)
447 value_type
const new_value = window_value();
449 window_values.pop_front();
450 window_values.push_back(new_value);
452 if (minimiser_position_offset == 0)
455 minimiser_value = *minimiser_it;
460 if (new_value < minimiser_value)
462 minimiser_value = new_value;
463 minimiser_position_offset = window_values.size() - 1;
467 --minimiser_position_offset;
473template <std::ranges::viewable_range rng1_t>
474minimiser_view(rng1_t &&,
size_t const window_size) -> minimiser_view<std::views::all_t<rng1_t>>;
477template <std::ranges::viewable_range rng1_t, std::ranges::viewable_range rng2_t>
478minimiser_view(rng1_t &&,
480 size_t const window_size) -> minimiser_view<std::views::all_t<rng1_t>, 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};
584inline constexpr auto minimiser = detail::minimiser_fn{};
Provides seqan3::detail::adaptor_from_functor.
A "pretty printer" for most SeqAn data structures and related types.
Definition debug_stream_type.hpp:79
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:584
constexpr size_t size
The size of a type pack.
Definition type_pack/traits.hpp:143
Provides lazy template instantiation traits.
The SeqAn namespace for views.
Definition char_strictly_to.hpp:19
SeqAn specific customisations in the standard namespace.
Additional non-standard concepts for ranges.