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 
24 namespace seqan3::detail
25 {
41 template <std::ranges::view underlying_range_type>
42  requires std::ranges::forward_range<underlying_range_type> && std::ranges::common_range<underlying_range_type>
43 class pairwise_combine_view : public std::ranges::view_interface<pairwise_combine_view<underlying_range_type>>
44 {
45 private:
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 
61 public:
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 
219 private:
221  underlying_range_type u_range{};
223  std::ranges::iterator_t<underlying_range_type> back_iterator{};
224 };
225 
231 template <std::ranges::viewable_range other_range_t>
232 pairwise_combine_view(other_range_t && range) -> pairwise_combine_view<std::views::all_t<other_range_t>>;
234 
248 template <std::ranges::view underlying_range_type>
249  requires std::ranges::forward_range<underlying_range_type> && std::ranges::common_range<underlying_range_type>
250 template <typename range_type>
251 class pairwise_combine_view<underlying_range_type>::basic_iterator :
252  public maybe_iterator_category<std::ranges::iterator_t<range_type>>
253 {
254 private:
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 
267 public:
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 
534 private:
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 
588 namespace seqan3::views
589 {
652 inline 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 declval(T... args)
T end(T... args)
T floor(T... args)
T forward(T... args)
requires requires
The rank_type of the semi-alphabet; defined as the return type of seqan3::to_rank....
Definition: alphabet/concept.hpp:164
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.