SeqAn3 3.2.0
The Modern C++ library for sequence analysis.
pairwise_combine.hpp
Go to the documentation of this file.
1// -----------------------------------------------------------------------------------------------------
2// Copyright (c) 2006-2022, Knut Reinert & Freie Universität Berlin
3// Copyright (c) 2016-2022, Knut Reinert & MPI für molekulare Genetik
4// This file may be used, modified and/or redistributed under the terms of the 3-clause BSD-License
5// shipped with this file and also available at: https://github.com/seqan/seqan3/blob/master/LICENSE.md
6// -----------------------------------------------------------------------------------------------------
7
13#pragma once
14
15#include <cmath>
16#include <ranges>
17
23
24namespace seqan3::detail
25{
41template <std::ranges::view underlying_range_type>
42 requires std::ranges::forward_range<underlying_range_type> && std::ranges::common_range<underlying_range_type>
43class pairwise_combine_view : public std::ranges::view_interface<pairwise_combine_view<underlying_range_type>>
44{
45private:
47 template <typename range_type>
48 class basic_iterator;
49
55 using iterator = basic_iterator<underlying_range_type>;
57 using const_iterator =
58 transformation_trait_or_t<std::type_identity<basic_iterator<underlying_range_type const>>, void>;
60
61public:
65 pairwise_combine_view() = default;
66 pairwise_combine_view(pairwise_combine_view const &) = default;
67 pairwise_combine_view(pairwise_combine_view &&) = default;
68 pairwise_combine_view & operator=(pairwise_combine_view const &) = default;
69 pairwise_combine_view & operator=(pairwise_combine_view &&) = default;
70 ~pairwise_combine_view() = default;
71
88 explicit constexpr pairwise_combine_view(underlying_range_type range) : u_range{std::move(range)}
89 {
90 // Check if range is empty.
91 if (std::ranges::empty(u_range))
92 {
93 back_iterator = std::ranges::end(u_range);
94 }
95 else
96 {
97 if constexpr (std::ranges::bidirectional_range<underlying_range_type>)
98 { // Simply take one before the end. We can do this as we require underlying_range_type to be a common range.
99 back_iterator = std::ranges::prev(std::ranges::end(u_range));
100 }
101 else
102 { // For all other cases we need to set the back_iterator in linear time to the correct position.
103 back_iterator = std::ranges::begin(u_range);
104 if constexpr (std::ranges::sized_range<underlying_range_type>)
105 {
106 std::ranges::advance(back_iterator, std::ranges::size(u_range) - 1);
107 }
108 else // We don't have the size, so we need to increment until one before the end in a linear pass.
109 {
110 auto tmp_it = back_iterator;
111 do
112 {
113 back_iterator = tmp_it;
114 }
115 while (++tmp_it != std::ranges::end(u_range));
116 }
117 }
118 }
119 }
120
140 template <typename other_range_t>
141 requires (!std::same_as<std::remove_cvref_t<other_range_t>, pairwise_combine_view>)
142 && std::ranges::viewable_range<other_range_t>
143 && // Must come after self type check to avoid conflicts with the move constructor.
144 std::constructible_from<underlying_range_type,
145 std::ranges::ref_view<std::remove_reference_t<other_range_t>>>
146 //TODO: Investigate: the following expression is equivalent to the one above but raises a weird assertion in
147 // the ranges adaptor suggesting that the pairwise_combine_view is not a viewable_range.
148 // std::constructible_from<underlying_range_type, decltype(std::views::all(std::declval<other_range_t &&>()))>
149 explicit constexpr pairwise_combine_view(other_range_t && range) :
150 pairwise_combine_view{std::views::all(std::forward<other_range_t>(range))}
151 {}
152
169 constexpr iterator begin() noexcept
170 {
171 return {std::ranges::begin(u_range), std::ranges::begin(u_range), std::ranges::end(u_range)};
172 }
173
175 constexpr const_iterator begin() const noexcept
176 requires const_iterable_range<underlying_range_type>
177 {
178 return {std::ranges::cbegin(u_range), std::ranges::cbegin(u_range), std::ranges::cend(u_range)};
179 }
180
194 constexpr iterator end() noexcept
195 {
196 return {back_iterator, std::ranges::begin(u_range), std::ranges::end(u_range)};
197 }
198
200 constexpr const_iterator end() const noexcept
201 requires const_iterable_range<underlying_range_type>
202 {
203 return {back_iterator, std::ranges::cbegin(u_range), std::ranges::cend(u_range)};
204 }
206
211 constexpr auto size() const noexcept
212 requires std::ranges::sized_range<underlying_range_type>
213 {
214 auto const size = std::ranges::size(u_range);
215 return (size * (size - 1)) / 2;
216 }
218
219private:
221 underlying_range_type u_range{};
223 std::ranges::iterator_t<underlying_range_type> back_iterator{};
224};
225
231template <std::ranges::viewable_range other_range_t>
232pairwise_combine_view(other_range_t && range) -> pairwise_combine_view<std::views::all_t<other_range_t>>;
234
248template <std::ranges::view underlying_range_type>
249 requires std::ranges::forward_range<underlying_range_type> && std::ranges::common_range<underlying_range_type>
250template <typename range_type>
251class pairwise_combine_view<underlying_range_type>::basic_iterator :
252 public maybe_iterator_category<std::ranges::iterator_t<range_type>>
253{
254private:
256 template <typename other_range_type>
257 requires std::same_as<std::remove_const_t<range_type>, std::remove_const_t<other_range_type>>
258 friend class basic_iterator;
259
261 using underlying_iterator_type = std::ranges::iterator_t<range_type>;
263 using underlying_val_t = std::iter_value_t<underlying_iterator_type>;
265 using underlying_ref_t = std::iter_reference_t<underlying_iterator_type>;
266
267public:
273 using difference_type = std::ptrdiff_t;
277 using reference = common_tuple<underlying_ref_t, underlying_ref_t>;
279 using pointer = void;
281 using iterator_concept = detail::iterator_concept_tag_t<underlying_iterator_type>;
283
287 basic_iterator() = default;
288 basic_iterator(basic_iterator const &) = default;
289 basic_iterator(basic_iterator &&) = default;
290 basic_iterator & operator=(basic_iterator const &) = default;
291 basic_iterator & operator=(basic_iterator &&) = default;
292 ~basic_iterator() = default;
293
306 constexpr basic_iterator(underlying_iterator_type iter,
307 underlying_iterator_type begin_it,
308 underlying_iterator_type end_it) noexcept :
309 first_it{iter},
310 second_it{std::ranges::next(iter, 1, end_it)},
311 begin_it{begin_it},
312 end_it{end_it}
313 {}
314
323 template <typename other_range_type>
324 requires std::convertible_to<other_range_type, range_type &>
325 && std::same_as<std::remove_const_t<other_range_type>, std::remove_const_t<range_type>>
326 constexpr basic_iterator(basic_iterator<other_range_type> other) noexcept :
327 basic_iterator{std::move(other.first_it), std::move(other.begin_it), std::move(other.end_it)}
328 {}
330
335 constexpr reference operator*() const noexcept(noexcept(*std::declval<underlying_iterator_type>()))
336 {
337 return reference{*first_it, *second_it};
338 }
339
343 constexpr reference operator[](size_t const index) const
344 noexcept(noexcept(std::declval<basic_iterator &>().from_index(1)))
345 requires std::random_access_iterator<underlying_iterator_type>
346 {
347 return *(*this + index);
348 }
350
355 constexpr basic_iterator &
356 operator++(/*pre-increment*/) noexcept(noexcept(++std::declval<underlying_iterator_type &>()))
357 {
358 if (++second_it == end_it)
359 {
360 ++first_it;
361 second_it = first_it;
362 ++second_it;
363 }
364 return *this;
365 }
366
368 constexpr basic_iterator
369 operator++(int /*post-increment*/) noexcept(noexcept(std::declval<underlying_iterator_type &>()++))
370 {
371 basic_iterator tmp{*this};
372 ++*this;
373 return tmp;
374 }
375
377 constexpr basic_iterator &
378 operator--(/*pre-decrement*/) noexcept(noexcept(--std::declval<underlying_iterator_type &>()))
379 requires std::bidirectional_iterator<underlying_iterator_type>
380 {
381 if (--second_it == first_it)
382 {
383 --first_it;
384 second_it = end_it;
385 --second_it;
386 }
387 return *this;
388 }
389
391 constexpr basic_iterator
392 operator--(int /*post-decrement*/) noexcept(noexcept(std::declval<underlying_iterator_type &>()--))
393 requires std::bidirectional_iterator<underlying_iterator_type>
394 {
395 basic_iterator tmp{*this};
396 --*this;
397 return tmp;
398 }
399
402 constexpr basic_iterator &
403 operator+=(difference_type const offset) noexcept(noexcept(std::declval<basic_iterator &>().from_index(1)))
404 requires std::random_access_iterator<underlying_iterator_type>
405 {
406 from_index(to_index() + offset);
407 return *this;
408 }
409
412 constexpr basic_iterator operator+(difference_type const offset) const
413 noexcept(noexcept(std::declval<basic_iterator &>() += 1))
414 requires std::random_access_iterator<underlying_iterator_type>
415 {
416 basic_iterator tmp{*this};
417 return (tmp += offset);
418 }
419
422 constexpr friend basic_iterator
423 operator+(difference_type const offset,
424 basic_iterator iter) noexcept(noexcept(std::declval<basic_iterator<range_type> &>().from_index(1)))
425 requires std::random_access_iterator<underlying_iterator_type>
426 {
427 iter.from_index(iter.to_index() + offset);
428 return iter;
429 }
430
433 constexpr basic_iterator &
434 operator-=(difference_type const offset) noexcept(noexcept(std::declval<basic_iterator &>().from_index(1)))
435 requires std::random_access_iterator<underlying_iterator_type>
436 {
437 from_index(to_index() - offset);
438 return *this;
439 }
440
443 constexpr basic_iterator operator-(difference_type const offset) const
444 noexcept(noexcept(std::declval<basic_iterator &>() -= 1))
445 requires std::random_access_iterator<underlying_iterator_type>
446 {
447 basic_iterator tmp{*this};
448 return (tmp -= offset);
449 }
450
453 template <typename other_range_type>
454 requires std::random_access_iterator<underlying_iterator_type>
455 && std::same_as<std::remove_const_t<range_type>, std::remove_const_t<other_range_type>>
456 constexpr difference_type operator-(basic_iterator<other_range_type> const & rhs) const
457 noexcept(noexcept(std::declval<basic_iterator &>().to_index()))
458 {
459 return static_cast<difference_type>(to_index() - rhs.to_index());
460 }
462
468 //NOTE: The comparison operators should be implemented as friends, but due to a bug in gcc friend function
469 // cannot yet be constrained. To avoid unexpected errors with the comparison all operators are implemented as
470 // direct members and not as friends.
471
473 template <typename other_range_type>
474 requires std::equality_comparable_with<underlying_iterator_type, std::ranges::iterator_t<other_range_type>>
475 && std::same_as<std::remove_const_t<range_type>, std::remove_const_t<other_range_type>>
476 constexpr bool operator==(basic_iterator<other_range_type> const & rhs) const
477 noexcept(noexcept(std::declval<underlying_iterator_type &>() == std::declval<underlying_iterator_type &>()))
478 {
479 return std::tie(first_it, second_it) == std::tie(rhs.first_it, rhs.second_it);
480 }
481
483 template <typename other_range_type>
484 requires std::equality_comparable_with<underlying_iterator_type, std::ranges::iterator_t<other_range_type>>
485 && std::same_as<std::remove_const_t<range_type>, std::remove_const_t<other_range_type>>
486 constexpr bool operator!=(basic_iterator<other_range_type> const & rhs) const
487 noexcept(noexcept(std::declval<underlying_iterator_type &>() != std::declval<underlying_iterator_type &>()))
488 {
489 return !(*this == rhs);
490 }
491
493 template <typename other_range_type>
494 requires std::totally_ordered_with<underlying_iterator_type, std::ranges::iterator_t<other_range_type>>
495 && std::same_as<std::remove_const_t<range_type>, std::remove_const_t<other_range_type>>
496 constexpr bool operator<(basic_iterator<other_range_type> const & rhs) const
497 noexcept(noexcept(std::declval<underlying_iterator_type &>() < std::declval<underlying_iterator_type &>()))
498 {
499 return std::tie(first_it, second_it) < std::tie(rhs.first_it, rhs.second_it);
500 }
501
503 template <typename other_range_type>
504 requires std::totally_ordered_with<underlying_iterator_type, std::ranges::iterator_t<other_range_type>>
505 && std::same_as<std::remove_const_t<range_type>, std::remove_const_t<other_range_type>>
506 constexpr bool operator>(basic_iterator<other_range_type> const & rhs) const
507 noexcept(noexcept(std::declval<underlying_iterator_type &>() > std::declval<underlying_iterator_type &>()))
508
509 {
510 return std::tie(first_it, second_it) > std::tie(rhs.first_it, rhs.second_it);
511 }
512
514 template <typename other_range_type>
515 requires std::totally_ordered_with<underlying_iterator_type, std::ranges::iterator_t<other_range_type>>
516 && std::same_as<std::remove_const_t<range_type>, std::remove_const_t<other_range_type>>
517 constexpr bool operator<=(basic_iterator<other_range_type> const & rhs) const
518 noexcept(noexcept(std::declval<underlying_iterator_type &>() <= std::declval<underlying_iterator_type &>()))
519 {
520 return std::tie(first_it, second_it) <= std::tie(rhs.first_it, rhs.second_it);
521 }
522
524 template <typename other_range_type>
525 requires std::totally_ordered_with<underlying_iterator_type, std::ranges::iterator_t<other_range_type>>
526 && std::same_as<std::remove_const_t<range_type>, std::remove_const_t<other_range_type>>
527 constexpr bool operator>=(basic_iterator<other_range_type> const & rhs) const
528 noexcept(noexcept(std::declval<underlying_iterator_type &>() >= std::declval<underlying_iterator_type &>()))
529 {
530 return std::tie(first_it, second_it) >= std::tie(rhs.first_it, rhs.second_it);
531 }
533
534private:
547 constexpr size_t to_index() const
548 noexcept(noexcept(std::declval<underlying_iterator_type &>() - std::declval<underlying_iterator_type &>()))
549 requires std::random_access_iterator<underlying_iterator_type>
550 {
551 size_t src_size = end_it - begin_it;
552 size_t index_i = first_it - begin_it;
553 size_t index_j = second_it - begin_it;
554 return (src_size * (src_size - 1) / 2) - (src_size - index_i) * ((src_size - index_i) - 1) / 2 + index_j
555 - index_i - 1;
556 }
557
562 constexpr void from_index(size_t const index) noexcept(noexcept(
563 std::declval<underlying_iterator_type &>()
564 - std::declval<underlying_iterator_type &>()) && noexcept(std::declval<underlying_iterator_type &>() + 1))
565 requires std::random_access_iterator<underlying_iterator_type>
566 {
567 size_t src_size = end_it - begin_it;
568 size_t index_i =
569 src_size - 2 - std::floor(std::sqrt(-8 * index + 4 * src_size * (src_size - 1) - 7) / 2.0 - 0.5);
570 size_t index_j =
571 index + index_i + 1 - src_size * (src_size - 1) / 2 + (src_size - index_i) * ((src_size - index_i) - 1) / 2;
572 first_it = begin_it + index_i;
573 second_it = begin_it + index_j;
574 }
575
577 underlying_iterator_type first_it{};
579 underlying_iterator_type second_it{};
581 underlying_iterator_type begin_it{};
583 underlying_iterator_type end_it{};
584};
585
586} // namespace seqan3::detail
587
588namespace seqan3::views
589{
652inline constexpr auto pairwise_combine = detail::adaptor_for_view_without_args<detail::pairwise_combine_view>{};
653
654} // namespace seqan3::views
Provides seqan3::detail::adaptor_for_view_without_args.
T begin(T... args)
Provides seqan3::common_tuple.
T end(T... args)
T floor(T... args)
@ offset
Sequence (seqan3::field::seq) relative start position (0-based), unsigned value.
constexpr size_t size
The size of a type pack.
Definition: type_pack/traits.hpp:146
constexpr auto pairwise_combine
A view adaptor that generates all pairwise combinations of the elements of the underlying range.
Definition: pairwise_combine.hpp:652
Specifies requirements of an input range type for which the const version of that type satisfies the ...
Provides various transformation traits for use on iterators.
The SeqAn namespace for views.
Definition: char_strictly_to.hpp:22
SeqAn specific customisations in the standard namespace.
T operator!=(T... args)
The <ranges> header from C++20's standard library.
T sqrt(T... args)
T tie(T... args)
Provides seqan3::detail::transformation_trait_or.
Additional non-standard concepts for ranges.