SeqAn3 3.3.0
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>;
264 using underlying_ref_t = std::iter_reference_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.
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.