SeqAn3 3.4.0-rc.3
The Modern C++ library for sequence analysis.
Loading...
Searching...
No Matches
pairwise_combine.hpp
Go to the documentation of this file.
1// SPDX-FileCopyrightText: 2006-2024 Knut Reinert & Freie Universität Berlin
2// SPDX-FileCopyrightText: 2016-2024 Knut Reinert & MPI für molekulare Genetik
3// SPDX-License-Identifier: BSD-3-Clause
4
10#pragma once
11
12#include <cmath>
13#include <ranges>
14
20
21namespace seqan3::detail
22{
38template <std::ranges::view underlying_range_type>
39 requires std::ranges::forward_range<underlying_range_type> && std::ranges::common_range<underlying_range_type>
40class pairwise_combine_view : public std::ranges::view_interface<pairwise_combine_view<underlying_range_type>>
41{
42private:
44 template <typename range_type>
45 class basic_iterator;
46
52 using iterator = basic_iterator<underlying_range_type>;
54 using const_iterator =
55 transformation_trait_or_t<std::type_identity<basic_iterator<underlying_range_type const>>, void>;
57
58public:
62 pairwise_combine_view() = default;
63 pairwise_combine_view(pairwise_combine_view const &) = default;
64 pairwise_combine_view(pairwise_combine_view &&) = default;
65 pairwise_combine_view & operator=(pairwise_combine_view const &) = default;
66 pairwise_combine_view & operator=(pairwise_combine_view &&) = default;
67 ~pairwise_combine_view() = default;
68
85 explicit constexpr pairwise_combine_view(underlying_range_type range) : u_range{std::move(range)}
86 {
87 // Check if range is empty.
88 if (std::ranges::empty(u_range))
89 {
90 back_iterator = std::ranges::end(u_range);
91 }
92 else
93 {
94 if constexpr (std::ranges::bidirectional_range<underlying_range_type>)
95 { // Simply take one before the end. We can do this as we require underlying_range_type to be a common range.
96 back_iterator = std::ranges::prev(std::ranges::end(u_range));
97 }
98 else
99 { // For all other cases we need to set the back_iterator in linear time to the correct position.
100 back_iterator = std::ranges::begin(u_range);
101 if constexpr (std::ranges::sized_range<underlying_range_type>)
102 {
103 std::ranges::advance(back_iterator, std::ranges::size(u_range) - 1);
104 }
105 else // We don't have the size, so we need to increment until one before the end in a linear pass.
106 {
107 auto tmp_it = back_iterator;
108 do
109 {
110 back_iterator = tmp_it;
111 }
112 while (++tmp_it != std::ranges::end(u_range));
113 }
114 }
115 }
116 }
117
137 template <typename other_range_t>
138 requires (!std::same_as<std::remove_cvref_t<other_range_t>, pairwise_combine_view>)
139 && std::ranges::viewable_range<other_range_t>
140 && // Must come after self type check to avoid conflicts with the move constructor.
141 std::constructible_from<underlying_range_type,
142 std::ranges::ref_view<std::remove_reference_t<other_range_t>>>
143 //TODO: Investigate: the following expression is equivalent to the one above but raises a weird assertion in
144 // the ranges adaptor suggesting that the pairwise_combine_view is not a viewable_range.
145 // std::constructible_from<underlying_range_type, decltype(std::views::all(std::declval<other_range_t &&>()))>
146 explicit constexpr pairwise_combine_view(other_range_t && range) :
147 pairwise_combine_view{std::views::all(std::forward<other_range_t>(range))}
148 {}
149
166 constexpr iterator begin() noexcept
167 {
168 return {std::ranges::begin(u_range), std::ranges::begin(u_range), std::ranges::end(u_range)};
169 }
170
172 constexpr const_iterator begin() const noexcept
173 requires const_iterable_range<underlying_range_type>
174 {
175 return {std::ranges::begin(u_range), std::ranges::begin(u_range), std::ranges::end(u_range)};
176 }
177
191 constexpr iterator end() noexcept
192 {
193 return {back_iterator, std::ranges::begin(u_range), std::ranges::end(u_range)};
194 }
195
197 constexpr const_iterator end() const noexcept
198 requires const_iterable_range<underlying_range_type>
199 {
200 return {back_iterator, std::ranges::begin(u_range), std::ranges::end(u_range)};
201 }
203
208 constexpr auto size() const noexcept
209 requires std::ranges::sized_range<underlying_range_type>
210 {
211 auto const size = std::ranges::size(u_range);
212 return (size * (size - 1)) / 2;
213 }
215
216private:
218 underlying_range_type u_range;
220 std::ranges::iterator_t<underlying_range_type> back_iterator{};
221};
222
228template <std::ranges::viewable_range other_range_t>
229pairwise_combine_view(other_range_t && range) -> pairwise_combine_view<std::views::all_t<other_range_t>>;
231
245template <std::ranges::view underlying_range_type>
246 requires std::ranges::forward_range<underlying_range_type> && std::ranges::common_range<underlying_range_type>
247template <typename range_type>
248class pairwise_combine_view<underlying_range_type>::basic_iterator :
249 public maybe_iterator_category<std::ranges::iterator_t<range_type>>
250{
251private:
253 template <typename other_range_type>
254 friend class basic_iterator;
255
257 using underlying_iterator_type = std::ranges::iterator_t<range_type>;
259 using underlying_val_t = std::iter_value_t<underlying_iterator_type>;
261 using underlying_ref_t = std::iter_reference_t<underlying_iterator_type>;
262
263public:
269 using difference_type = std::ptrdiff_t;
273 using reference = common_tuple<underlying_ref_t, underlying_ref_t>;
275 using pointer = void;
277 using iterator_concept = detail::iterator_concept_tag_t<underlying_iterator_type>;
279
283 basic_iterator() = default;
284 basic_iterator(basic_iterator const &) = default;
285 basic_iterator(basic_iterator &&) = default;
286 basic_iterator & operator=(basic_iterator const &) = default;
287 basic_iterator & operator=(basic_iterator &&) = default;
288 ~basic_iterator() = default;
289
302 constexpr basic_iterator(underlying_iterator_type iter,
303 underlying_iterator_type begin_it,
304 underlying_iterator_type end_it) noexcept :
305 first_it{iter},
306 second_it{std::ranges::next(iter, 1, end_it)},
307 begin_it{begin_it},
308 end_it{end_it}
309 {}
310
319 template <typename other_range_type>
320 requires std::convertible_to<other_range_type, range_type &>
321 && std::same_as<std::remove_const_t<other_range_type>, std::remove_const_t<range_type>>
322 constexpr basic_iterator(basic_iterator<other_range_type> other) noexcept :
323 basic_iterator{std::move(other.first_it), std::move(other.begin_it), std::move(other.end_it)}
324 {}
326
331 constexpr reference operator*() const noexcept(noexcept(*std::declval<underlying_iterator_type>()))
332 {
333 return reference{*first_it, *second_it};
334 }
335
339 constexpr reference operator[](size_t const index) const
340 noexcept(noexcept(std::declval<basic_iterator &>().from_index(1)))
341 requires std::random_access_iterator<underlying_iterator_type>
342 {
343 return *(*this + index);
344 }
346
351 constexpr basic_iterator & operator++(/*pre-increment*/)
352 noexcept(noexcept(++std::declval<underlying_iterator_type &>()))
353 {
354 if (++second_it == end_it)
355 {
356 ++first_it;
357 second_it = first_it;
358 ++second_it;
359 }
360 return *this;
361 }
362
364 constexpr basic_iterator operator++(int /*post-increment*/)
365 noexcept(noexcept(std::declval<underlying_iterator_type &>()++))
366 {
367 basic_iterator tmp{*this};
368 ++*this;
369 return tmp;
370 }
371
373 constexpr basic_iterator & operator--(/*pre-decrement*/)
374 noexcept(noexcept(--std::declval<underlying_iterator_type &>()))
375 requires std::bidirectional_iterator<underlying_iterator_type>
376 {
377 if (--second_it == first_it)
378 {
379 --first_it;
380 second_it = end_it;
381 --second_it;
382 }
383 return *this;
384 }
385
387 constexpr basic_iterator operator--(int /*post-decrement*/)
388 noexcept(noexcept(std::declval<underlying_iterator_type &>()--))
389 requires std::bidirectional_iterator<underlying_iterator_type>
390 {
391 basic_iterator tmp{*this};
392 --*this;
393 return tmp;
394 }
395
398 constexpr basic_iterator & operator+=(difference_type const offset)
399 noexcept(noexcept(std::declval<basic_iterator &>().from_index(1)))
400 requires std::random_access_iterator<underlying_iterator_type>
401 {
402 from_index(to_index() + offset);
403 return *this;
404 }
405
408 constexpr basic_iterator operator+(difference_type const offset) const
409 noexcept(noexcept(std::declval<basic_iterator &>() += 1))
410 requires std::random_access_iterator<underlying_iterator_type>
411 {
412 basic_iterator tmp{*this};
413 return (tmp += offset);
414 }
415
418 constexpr friend basic_iterator operator+(difference_type const offset, basic_iterator iter)
419 noexcept(noexcept(std::declval<basic_iterator<range_type> &>().from_index(1)))
420 requires std::random_access_iterator<underlying_iterator_type>
421 {
422 iter.from_index(iter.to_index() + offset);
423 return iter;
424 }
425
428 constexpr basic_iterator & operator-=(difference_type const offset)
429 noexcept(noexcept(std::declval<basic_iterator &>().from_index(1)))
430 requires std::random_access_iterator<underlying_iterator_type>
431 {
432 from_index(to_index() - offset);
433 return *this;
434 }
435
438 constexpr basic_iterator operator-(difference_type const offset) const
439 noexcept(noexcept(std::declval<basic_iterator &>() -= 1))
440 requires std::random_access_iterator<underlying_iterator_type>
441 {
442 basic_iterator tmp{*this};
443 return (tmp -= offset);
444 }
445
448 template <typename other_range_type>
449 requires std::random_access_iterator<underlying_iterator_type>
450 && std::same_as<std::remove_const_t<range_type>, std::remove_const_t<other_range_type>>
451 constexpr difference_type operator-(basic_iterator<other_range_type> const & rhs) const
452 noexcept(noexcept(std::declval<basic_iterator &>().to_index()))
453 {
454 return static_cast<difference_type>(to_index() - rhs.to_index());
455 }
457
463 //NOTE: The comparison operators should be implemented as friends, but due to a bug in gcc friend function
464 // cannot yet be constrained. To avoid unexpected errors with the comparison all operators are implemented as
465 // direct members and not as friends.
466
468 template <typename other_range_type>
469 requires std::equality_comparable_with<underlying_iterator_type, std::ranges::iterator_t<other_range_type>>
470 && std::same_as<std::remove_const_t<range_type>, std::remove_const_t<other_range_type>>
471 constexpr bool operator==(basic_iterator<other_range_type> const & rhs) const
472 noexcept(noexcept(std::declval<underlying_iterator_type &>() == std::declval<underlying_iterator_type &>()))
473 {
474 return std::tie(first_it, second_it) == std::tie(rhs.first_it, rhs.second_it);
475 }
476
478 template <typename other_range_type>
479 requires std::equality_comparable_with<underlying_iterator_type, std::ranges::iterator_t<other_range_type>>
480 && std::same_as<std::remove_const_t<range_type>, std::remove_const_t<other_range_type>>
481 constexpr bool operator!=(basic_iterator<other_range_type> const & rhs) const
482 noexcept(noexcept(std::declval<underlying_iterator_type &>() != std::declval<underlying_iterator_type &>()))
483 {
484 return !(*this == rhs);
485 }
486
488 template <typename other_range_type>
489 requires std::totally_ordered_with<underlying_iterator_type, std::ranges::iterator_t<other_range_type>>
490 && std::same_as<std::remove_const_t<range_type>, std::remove_const_t<other_range_type>>
491 constexpr bool operator<(basic_iterator<other_range_type> const & rhs) const
492 noexcept(noexcept(std::declval<underlying_iterator_type &>() < std::declval<underlying_iterator_type &>()))
493 {
494 return std::tie(first_it, second_it) < std::tie(rhs.first_it, rhs.second_it);
495 }
496
498 template <typename other_range_type>
499 requires std::totally_ordered_with<underlying_iterator_type, std::ranges::iterator_t<other_range_type>>
500 && std::same_as<std::remove_const_t<range_type>, std::remove_const_t<other_range_type>>
501 constexpr bool operator>(basic_iterator<other_range_type> const & rhs) const
502 noexcept(noexcept(std::declval<underlying_iterator_type &>() > std::declval<underlying_iterator_type &>()))
503
504 {
505 return std::tie(first_it, second_it) > std::tie(rhs.first_it, rhs.second_it);
506 }
507
509 template <typename other_range_type>
510 requires std::totally_ordered_with<underlying_iterator_type, std::ranges::iterator_t<other_range_type>>
511 && std::same_as<std::remove_const_t<range_type>, std::remove_const_t<other_range_type>>
512 constexpr bool operator<=(basic_iterator<other_range_type> const & rhs) const
513 noexcept(noexcept(std::declval<underlying_iterator_type &>() <= std::declval<underlying_iterator_type &>()))
514 {
515 return std::tie(first_it, second_it) <= std::tie(rhs.first_it, rhs.second_it);
516 }
517
519 template <typename other_range_type>
520 requires std::totally_ordered_with<underlying_iterator_type, std::ranges::iterator_t<other_range_type>>
521 && std::same_as<std::remove_const_t<range_type>, std::remove_const_t<other_range_type>>
522 constexpr bool operator>=(basic_iterator<other_range_type> const & rhs) const
523 noexcept(noexcept(std::declval<underlying_iterator_type &>() >= std::declval<underlying_iterator_type &>()))
524 {
525 return std::tie(first_it, second_it) >= std::tie(rhs.first_it, rhs.second_it);
526 }
528
529private:
542 constexpr size_t to_index() const
543 noexcept(noexcept(std::declval<underlying_iterator_type &>() - std::declval<underlying_iterator_type &>()))
544 requires std::random_access_iterator<underlying_iterator_type>
545 {
546 size_t src_size = end_it - begin_it;
547 size_t index_i = first_it - begin_it;
548 size_t index_j = second_it - begin_it;
549 return (src_size * (src_size - 1) / 2) - (src_size - index_i) * ((src_size - index_i) - 1) / 2 + index_j
550 - index_i - 1;
551 }
552
557 constexpr void from_index(size_t const index)
558 noexcept(noexcept(std::declval<underlying_iterator_type &>() - std::declval<underlying_iterator_type &>())
559 && noexcept(std::declval<underlying_iterator_type &>() + 1))
560 requires std::random_access_iterator<underlying_iterator_type>
561 {
562 size_t src_size = end_it - begin_it;
563 size_t index_i =
564 src_size - 2 - std::floor(std::sqrt(-8 * index + 4 * src_size * (src_size - 1) - 7) / 2.0 - 0.5);
565 size_t index_j =
566 index + index_i + 1 - src_size * (src_size - 1) / 2 + (src_size - index_i) * ((src_size - index_i) - 1) / 2;
567 first_it = begin_it + index_i;
568 second_it = begin_it + index_j;
569 }
570
572 underlying_iterator_type first_it{};
574 underlying_iterator_type second_it{};
576 underlying_iterator_type begin_it{};
578 underlying_iterator_type end_it{};
579};
580
581} // namespace seqan3::detail
582
583namespace seqan3::views
584{
647inline constexpr auto pairwise_combine = detail::adaptor_for_view_without_args<detail::pairwise_combine_view>{};
648
649} // 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:143
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:19
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.
Hide me