SeqAn3 3.4.0-rc.1
The Modern C++ library for sequence analysis.
Loading...
Searching...
No Matches
pairwise_combine.hpp
Go to the documentation of this file.
1// -----------------------------------------------------------------------------------------------------
2// Copyright (c) 2006-2023, Knut Reinert & Freie Universität Berlin
3// Copyright (c) 2016-2023, 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::begin(u_range), std::ranges::begin(u_range), std::ranges::end(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::begin(u_range), std::ranges::end(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 friend class basic_iterator;
258
260 using underlying_iterator_type = std::ranges::iterator_t<range_type>;
262 using underlying_val_t = std::iter_value_t<underlying_iterator_type>;
265
266public:
272 using difference_type = std::ptrdiff_t;
276 using reference = common_tuple<underlying_ref_t, underlying_ref_t>;
278 using pointer = void;
280 using iterator_concept = detail::iterator_concept_tag_t<underlying_iterator_type>;
282
286 basic_iterator() = default;
287 basic_iterator(basic_iterator const &) = default;
288 basic_iterator(basic_iterator &&) = default;
289 basic_iterator & operator=(basic_iterator const &) = default;
290 basic_iterator & operator=(basic_iterator &&) = default;
291 ~basic_iterator() = default;
292
305 constexpr basic_iterator(underlying_iterator_type iter,
306 underlying_iterator_type begin_it,
307 underlying_iterator_type end_it) noexcept :
308 first_it{iter},
309 second_it{std::ranges::next(iter, 1, end_it)},
310 begin_it{begin_it},
311 end_it{end_it}
312 {}
313
322 template <typename other_range_type>
323 requires std::convertible_to<other_range_type, range_type &>
324 && std::same_as<std::remove_const_t<other_range_type>, std::remove_const_t<range_type>>
325 constexpr basic_iterator(basic_iterator<other_range_type> other) noexcept :
326 basic_iterator{std::move(other.first_it), std::move(other.begin_it), std::move(other.end_it)}
327 {}
329
334 constexpr reference operator*() const noexcept(noexcept(*std::declval<underlying_iterator_type>()))
335 {
336 return reference{*first_it, *second_it};
337 }
338
342 constexpr reference operator[](size_t const index) const
343 noexcept(noexcept(std::declval<basic_iterator &>().from_index(1)))
344 requires std::random_access_iterator<underlying_iterator_type>
345 {
346 return *(*this + index);
347 }
349
354 constexpr basic_iterator &
355 operator++(/*pre-increment*/) noexcept(noexcept(++std::declval<underlying_iterator_type &>()))
356 {
357 if (++second_it == end_it)
358 {
359 ++first_it;
360 second_it = first_it;
361 ++second_it;
362 }
363 return *this;
364 }
365
367 constexpr basic_iterator
368 operator++(int /*post-increment*/) noexcept(noexcept(std::declval<underlying_iterator_type &>()++))
369 {
370 basic_iterator tmp{*this};
371 ++*this;
372 return tmp;
373 }
374
376 constexpr basic_iterator &
377 operator--(/*pre-decrement*/) noexcept(noexcept(--std::declval<underlying_iterator_type &>()))
378 requires std::bidirectional_iterator<underlying_iterator_type>
379 {
380 if (--second_it == first_it)
381 {
382 --first_it;
383 second_it = end_it;
384 --second_it;
385 }
386 return *this;
387 }
388
390 constexpr basic_iterator
391 operator--(int /*post-decrement*/) noexcept(noexcept(std::declval<underlying_iterator_type &>()--))
392 requires std::bidirectional_iterator<underlying_iterator_type>
393 {
394 basic_iterator tmp{*this};
395 --*this;
396 return tmp;
397 }
398
401 constexpr basic_iterator &
402 operator+=(difference_type const offset) noexcept(noexcept(std::declval<basic_iterator &>().from_index(1)))
403 requires std::random_access_iterator<underlying_iterator_type>
404 {
405 from_index(to_index() + offset);
406 return *this;
407 }
408
411 constexpr basic_iterator operator+(difference_type const offset) const
412 noexcept(noexcept(std::declval<basic_iterator &>() += 1))
413 requires std::random_access_iterator<underlying_iterator_type>
414 {
415 basic_iterator tmp{*this};
416 return (tmp += offset);
417 }
418
421 constexpr friend basic_iterator
422 operator+(difference_type const offset,
423 basic_iterator iter) noexcept(noexcept(std::declval<basic_iterator<range_type> &>().from_index(1)))
424 requires std::random_access_iterator<underlying_iterator_type>
425 {
426 iter.from_index(iter.to_index() + offset);
427 return iter;
428 }
429
432 constexpr basic_iterator &
433 operator-=(difference_type const offset) noexcept(noexcept(std::declval<basic_iterator &>().from_index(1)))
434 requires std::random_access_iterator<underlying_iterator_type>
435 {
436 from_index(to_index() - offset);
437 return *this;
438 }
439
442 constexpr basic_iterator operator-(difference_type const offset) const
443 noexcept(noexcept(std::declval<basic_iterator &>() -= 1))
444 requires std::random_access_iterator<underlying_iterator_type>
445 {
446 basic_iterator tmp{*this};
447 return (tmp -= offset);
448 }
449
452 template <typename other_range_type>
453 requires std::random_access_iterator<underlying_iterator_type>
454 && std::same_as<std::remove_const_t<range_type>, std::remove_const_t<other_range_type>>
455 constexpr difference_type operator-(basic_iterator<other_range_type> const & rhs) const
456 noexcept(noexcept(std::declval<basic_iterator &>().to_index()))
457 {
458 return static_cast<difference_type>(to_index() - rhs.to_index());
459 }
461
467 //NOTE: The comparison operators should be implemented as friends, but due to a bug in gcc friend function
468 // cannot yet be constrained. To avoid unexpected errors with the comparison all operators are implemented as
469 // direct members and not as friends.
470
472 template <typename other_range_type>
473 requires std::equality_comparable_with<underlying_iterator_type, std::ranges::iterator_t<other_range_type>>
474 && std::same_as<std::remove_const_t<range_type>, std::remove_const_t<other_range_type>>
475 constexpr bool operator==(basic_iterator<other_range_type> const & rhs) const
476 noexcept(noexcept(std::declval<underlying_iterator_type &>() == std::declval<underlying_iterator_type &>()))
477 {
478 return std::tie(first_it, second_it) == std::tie(rhs.first_it, rhs.second_it);
479 }
480
482 template <typename other_range_type>
483 requires std::equality_comparable_with<underlying_iterator_type, std::ranges::iterator_t<other_range_type>>
484 && std::same_as<std::remove_const_t<range_type>, std::remove_const_t<other_range_type>>
485 constexpr bool operator!=(basic_iterator<other_range_type> const & rhs) const
486 noexcept(noexcept(std::declval<underlying_iterator_type &>() != std::declval<underlying_iterator_type &>()))
487 {
488 return !(*this == rhs);
489 }
490
492 template <typename other_range_type>
493 requires std::totally_ordered_with<underlying_iterator_type, std::ranges::iterator_t<other_range_type>>
494 && std::same_as<std::remove_const_t<range_type>, std::remove_const_t<other_range_type>>
495 constexpr bool operator<(basic_iterator<other_range_type> const & rhs) const
496 noexcept(noexcept(std::declval<underlying_iterator_type &>() < std::declval<underlying_iterator_type &>()))
497 {
498 return std::tie(first_it, second_it) < std::tie(rhs.first_it, rhs.second_it);
499 }
500
502 template <typename other_range_type>
503 requires std::totally_ordered_with<underlying_iterator_type, std::ranges::iterator_t<other_range_type>>
504 && std::same_as<std::remove_const_t<range_type>, std::remove_const_t<other_range_type>>
505 constexpr bool operator>(basic_iterator<other_range_type> const & rhs) const
506 noexcept(noexcept(std::declval<underlying_iterator_type &>() > std::declval<underlying_iterator_type &>()))
507
508 {
509 return std::tie(first_it, second_it) > std::tie(rhs.first_it, rhs.second_it);
510 }
511
513 template <typename other_range_type>
514 requires std::totally_ordered_with<underlying_iterator_type, std::ranges::iterator_t<other_range_type>>
515 && std::same_as<std::remove_const_t<range_type>, std::remove_const_t<other_range_type>>
516 constexpr bool operator<=(basic_iterator<other_range_type> const & rhs) const
517 noexcept(noexcept(std::declval<underlying_iterator_type &>() <= std::declval<underlying_iterator_type &>()))
518 {
519 return std::tie(first_it, second_it) <= std::tie(rhs.first_it, rhs.second_it);
520 }
521
523 template <typename other_range_type>
524 requires std::totally_ordered_with<underlying_iterator_type, std::ranges::iterator_t<other_range_type>>
525 && std::same_as<std::remove_const_t<range_type>, std::remove_const_t<other_range_type>>
526 constexpr bool operator>=(basic_iterator<other_range_type> const & rhs) const
527 noexcept(noexcept(std::declval<underlying_iterator_type &>() >= std::declval<underlying_iterator_type &>()))
528 {
529 return std::tie(first_it, second_it) >= std::tie(rhs.first_it, rhs.second_it);
530 }
532
533private:
546 constexpr size_t to_index() const
547 noexcept(noexcept(std::declval<underlying_iterator_type &>() - std::declval<underlying_iterator_type &>()))
548 requires std::random_access_iterator<underlying_iterator_type>
549 {
550 size_t src_size = end_it - begin_it;
551 size_t index_i = first_it - begin_it;
552 size_t index_j = second_it - begin_it;
553 return (src_size * (src_size - 1) / 2) - (src_size - index_i) * ((src_size - index_i) - 1) / 2 + index_j
554 - index_i - 1;
555 }
556
561 constexpr void from_index(size_t const index) noexcept(noexcept(
562 std::declval<underlying_iterator_type &>()
563 - std::declval<underlying_iterator_type &>()) && noexcept(std::declval<underlying_iterator_type &>() + 1))
564 requires std::random_access_iterator<underlying_iterator_type>
565 {
566 size_t src_size = end_it - begin_it;
567 size_t index_i =
568 src_size - 2 - std::floor(std::sqrt(-8 * index + 4 * src_size * (src_size - 1) - 7) / 2.0 - 0.5);
569 size_t index_j =
570 index + index_i + 1 - src_size * (src_size - 1) / 2 + (src_size - index_i) * ((src_size - index_i) - 1) / 2;
571 first_it = begin_it + index_i;
572 second_it = begin_it + index_j;
573 }
574
576 underlying_iterator_type first_it{};
578 underlying_iterator_type second_it{};
580 underlying_iterator_type begin_it{};
582 underlying_iterator_type end_it{};
583};
584
585} // namespace seqan3::detail
586
587namespace seqan3::views
588{
651inline constexpr auto pairwise_combine = detail::adaptor_for_view_without_args<detail::pairwise_combine_view>{};
652
653} // 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
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.
T move(T... args)
The SeqAn namespace for views.
Definition char_strictly_to.hpp:22
SeqAn specific customisations in the standard namespace.
T operator!=(T... args)
T sqrt(T... args)
T tie(T... args)
Provides seqan3::detail::transformation_trait_or.
Additional non-standard concepts for ranges.