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 explicit 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 explicit 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 explicit minimiser_view(urng1_t urange1, urng2_t urange2,
size_t const window_size) :
132 urange1{
std::move(urange1)},
133 urange2{
std::move(urange2)},
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 explicit 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()
190 return {std::ranges::begin(urange1), std::ranges::end(urange1), std::ranges::begin(urange2), window_size};
194 basic_iterator<true>
begin() const
195 requires const_iterable
197 return {std::ranges::begin(urange1), std::ranges::end(urange1), std::ranges::begin(urange2), window_size};
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 type_pack/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.