23 namespace seqan3::detail
47 template <std::ranges::view urng1_t,
48 std::ranges::view urng2_t = std::ranges::empty_view<seqan3::detail::empty_type>>
49 class 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 || std::totally_ordered_with<std::ranges::range_reference_t<urng1_t>,
64 std::ranges::range_reference_t<urng2_t>>,
65 "The reference types of the underlying ranges must model std::totally_ordered_with.");
79 template <
typename rng1_t,
typename rng2_t>
83 using sentinel = std::default_sentinel_t;
89 minimiser_view() =
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;
101 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>
114 requires (std::ranges::viewable_range<other_urng1_t> &&
117 minimiser_view(other_urng1_t && urange1,
size_t const window_size) :
118 urange1{std::views::all(std::forward<other_urng1_t>(urange1))},
119 urange2{default_urng2_t{}},
120 window_size{window_size}
130 minimiser_view(urng1_t urange1, urng2_t urange2,
size_t const window_size) :
133 window_size{window_size}
135 if constexpr (second_range_is_given)
137 if (std::ranges::distance(urange1) != std::ranges::distance(urange2))
153 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>>)
160 minimiser_view(other_urng1_t && urange1, other_urng2_t && urange2,
size_t const window_size) :
161 urange1{std::views::all(std::forward<other_urng1_t>(urange1))},
162 urange2{std::views::all(std::forward<other_urng2_t>(urange2))},
163 window_size{window_size}
165 if constexpr (second_range_is_given)
167 if (std::ranges::distance(urange1) != std::ranges::distance(urange2))
189 basic_iterator<urng1_t, urng2_t>
begin()
192 std::ranges::end(urange1),
198 basic_iterator<urng1_t const, urng2_t const>
begin() const
200 requires const_iterable
204 std::ranges::cend(urange1),
232 template <std::ranges::view urng1_t, std::ranges::view urng2_t>
233 template <
typename rng1_t,
typename rng2_t>
234 class minimiser_view<urng1_t, urng2_t>::basic_iterator
238 using urng1_sentinel_t = std::ranges::sentinel_t<rng1_t>;
240 using urng1_iterator_t = std::ranges::iterator_t<rng1_t>;
242 using urng2_iterator_t = std::ranges::iterator_t<rng2_t>;
244 template <
typename,
typename>
245 friend class basic_iterator;
251 using difference_type = std::ranges::range_difference_t<rng1_t>;
254 using value_type = std::ranges::range_value_t<rng1_t>;
256 using pointer = void;
258 using reference = value_type;
262 using iterator_concept = iterator_category;
268 basic_iterator() =
default;
269 basic_iterator(basic_iterator
const &) =
default;
270 basic_iterator(basic_iterator &&) =
default;
271 basic_iterator & operator=(basic_iterator
const &) =
default;
272 basic_iterator & operator=(basic_iterator &&) =
default;
273 ~basic_iterator() =
default;
276 template <
typename non_const_rng1_t,
typename non_const_rng2_t>
281 basic_iterator(basic_iterator<non_const_rng1_t, non_const_rng2_t> it) :
282 minimiser_value{
std::move(it.minimiser_value)},
283 urng1_iterator{
std::move(it.urng1_iterator)},
284 urng1_sentinel{
std::move(it.urng1_sentinel)},
285 urng2_iterator{
std::move(it.urng2_iterator)},
286 window_values{
std::move(it.window_values)}
302 basic_iterator(urng1_iterator_t urng1_iterator,
303 urng1_sentinel_t urng1_sentinel,
304 urng2_iterator_t urng2_iterator,
305 size_t window_size) :
306 urng1_iterator{
std::move(urng1_iterator)},
307 urng1_sentinel{
std::move(urng1_sentinel)},
308 urng2_iterator{
std::move(urng2_iterator)}
310 size_t size = std::ranges::distance(urng1_iterator, urng1_sentinel);
311 window_size = std::min<size_t>(window_size,
size);
313 window_first(window_size);
322 friend bool operator==(basic_iterator
const & lhs, basic_iterator
const & rhs)
324 return (lhs.urng1_iterator == rhs.urng1_iterator) &&
325 (rhs.urng2_iterator == rhs.urng2_iterator) &&
326 (lhs.window_values.size() == rhs.window_values.size());
330 friend bool operator!=(basic_iterator
const & lhs, basic_iterator
const & rhs)
332 return !(lhs == rhs);
336 friend bool operator==(basic_iterator
const & lhs, sentinel
const &)
338 return lhs.urng1_iterator == lhs.urng1_sentinel;
342 friend bool operator==(sentinel
const & lhs, basic_iterator
const & rhs)
348 friend bool operator!=(sentinel
const & lhs, basic_iterator
const & rhs)
350 return !(lhs == rhs);
354 friend bool operator!=(basic_iterator
const & lhs, sentinel
const & rhs)
356 return !(lhs == rhs);
361 basic_iterator & operator++() noexcept
363 next_unique_minimiser();
368 basic_iterator operator++(
int) noexcept
370 basic_iterator tmp{*
this};
371 next_unique_minimiser();
376 value_type operator*() const noexcept
378 return minimiser_value;
383 value_type minimiser_value{};
386 size_t minimiser_position_offset{};
389 urng1_iterator_t urng1_iterator{};
391 urng1_sentinel_t urng1_sentinel{};
393 urng2_iterator_t urng2_iterator{};
399 void next_unique_minimiser()
401 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;
476 template <std::ranges::viewable_range rng1_t>
477 minimiser_view(rng1_t &&,
size_t const window_size) -> minimiser_view<std::views::all_t<rng1_t>>;
480 template <std::ranges::viewable_range rng1_t, std::ranges::viewable_range rng2_t>
481 minimiser_view(rng1_t &&, rng2_t &&,
size_t const window_size) -> minimiser_view<std::views::all_t<rng1_t>,
482 std::views::all_t<rng2_t>>;
493 constexpr
auto operator()(
size_t const window_size)
const
495 return adaptor_from_functor{*
this, window_size};
506 template <std::ranges::range urng1_t>
507 constexpr
auto operator()(urng1_t && urange1,
size_t const window_size)
const
509 static_assert(std::ranges::viewable_range<urng1_t>,
510 "The range parameter to views::minimiser cannot be a temporary of a non-view range.");
511 static_assert(std::ranges::forward_range<urng1_t>,
512 "The range parameter to views::minimiser must model std::ranges::forward_range.");
514 if (window_size == 1)
516 "Please choose a value greater than 1 or use two ranges."};
518 return minimiser_view{urange1, window_size};
588 inline constexpr
auto minimiser = detail::minimiser_fn{};