SeqAn3  3.0.2
The Modern C++ library for sequence analysis.
pairwise_combine.hpp
Go to the documentation of this file.
1 // -----------------------------------------------------------------------------------------------------
2 // Copyright (c) 2006-2020, Knut Reinert & Freie Universität Berlin
3 // Copyright (c) 2016-2020, 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 
19 #include <seqan3/range/concept.hpp>
21 #include <seqan3/std/ranges>
22 
23 namespace seqan3::detail
24 {
40 template <std::ranges::view underlying_range_type>
42  requires std::ranges::forward_range<underlying_range_type> && std::ranges::common_range<underlying_range_type>
44 class pairwise_combine_view : public std::ranges::view_interface<pairwise_combine_view<underlying_range_type>>
45 {
46 private:
47 
49  template <typename range_type>
50  class basic_iterator;
51 
56  using iterator = basic_iterator<underlying_range_type>;
59  using const_iterator = transformation_trait_or_t<std::type_identity<basic_iterator<underlying_range_type const>>,
60  void>;
62 
63 public:
67  pairwise_combine_view() = default;
68  pairwise_combine_view(pairwise_combine_view const &) = default;
69  pairwise_combine_view(pairwise_combine_view &&) = default;
70  pairwise_combine_view & operator=(pairwise_combine_view const &) = default;
71  pairwise_combine_view & operator=(pairwise_combine_view &&) = default;
72  ~pairwise_combine_view() = default;
73 
90  explicit constexpr pairwise_combine_view(underlying_range_type range) : u_range{std::move(range)}
91  {
92  // Check if range is empty.
93  if (std::ranges::empty(u_range))
94  {
95  back_iterator = std::ranges::end(u_range);
96  }
97  else
98  {
99  if constexpr (std::ranges::bidirectional_range<underlying_range_type>)
100  { // Simply take one before the end. We can do this as we require underlying_range_type to be a common range.
101  back_iterator = std::ranges::prev(std::ranges::end(u_range));
102  }
103  else
104  { // For all other cases we need to set the back_iterator in linear time to the correct position.
105  back_iterator = std::ranges::begin(u_range);
106  if constexpr (std::ranges::sized_range<underlying_range_type>)
107  {
108  std::ranges::advance(back_iterator, std::ranges::size(u_range) - 1);
109  }
110  else // We don't have the size, so we need to increment until one before the end in a linear pass.
111  {
112  auto tmp_it = back_iterator;
113  do
114  {
115  back_iterator = tmp_it;
116  } while (++tmp_it != std::ranges::end(u_range));
117  }
118  }
119  }
120  }
121 
141  template <typename other_range_t>
143  requires (!std::same_as<std::remove_cvref_t<other_range_t>, pairwise_combine_view>) &&
144  std::ranges::viewable_range<other_range_t> && // Must come after self type check to avoid conflicts with the move constructor.
145  std::constructible_from<underlying_range_type,
146  std::ranges::ref_view<std::remove_reference_t<other_range_t>>>
147  //TODO: Investigate: the following expression is equivalent to the one above but raises a weird assertion in
148  // the ranges adaptor suggesting that the pairwise_combine_view is not a viewable_range.
149  // std::constructible_from<underlying_range_type, decltype(std::views::all(std::declval<other_range_t &&>()))>
151  explicit constexpr pairwise_combine_view(other_range_t && range) :
152  pairwise_combine_view{std::views::all(std::forward<other_range_t>(range))}
153  {}
154 
171  constexpr iterator begin() noexcept
172  {
173  return {std::ranges::begin(u_range), std::ranges::begin(u_range), std::ranges::end(u_range)};
174  }
175 
177  constexpr const_iterator begin() const noexcept
179  requires const_iterable_range<underlying_range_type>
181  {
182  return {std::ranges::cbegin(u_range), std::ranges::cbegin(u_range), std::ranges::cend(u_range)};
183  }
184 
198  constexpr iterator end() noexcept
199  {
200  return {back_iterator, std::ranges::begin(u_range), std::ranges::end(u_range)};
201  }
202 
204  constexpr const_iterator end() const noexcept
206  requires const_iterable_range<underlying_range_type>
208  {
209  return {back_iterator, std::ranges::cbegin(u_range), std::ranges::cend(u_range)};
210  }
212 
216  constexpr auto size() const noexcept
219  requires std::ranges::sized_range<underlying_range_type>
221  {
222  return (std::ranges::size(u_range) * (std::ranges::size(u_range) - 1) / 2);
223  }
225 
226 private:
227 
229  underlying_range_type u_range{};
231  std::ranges::iterator_t<underlying_range_type> back_iterator{};
232 };
233 
238 template <std::ranges::viewable_range other_range_t>
240 pairwise_combine_view(other_range_t && range) ->
241  pairwise_combine_view<std::views::all_t<other_range_t>>;
243 
257 template <std::ranges::view underlying_range_type>
259  requires std::ranges::forward_range<underlying_range_type> && std::ranges::common_range<underlying_range_type>
261 template <typename range_type>
262 class pairwise_combine_view<underlying_range_type>::basic_iterator
263 {
264 private:
265 
267  template <typename other_range_type>
268  requires std::same_as<std::remove_const_t<range_type>, std::remove_const_t<other_range_type>>
269  friend class basic_iterator;
270 
272  using underlying_iterator_type = std::ranges::iterator_t<range_type>;
274  using underlying_val_t = std::iter_value_t<underlying_iterator_type>;
276  using underlying_ref_t = std::iter_reference_t<underlying_iterator_type>;
277 
278 public:
283  using difference_type = std::ptrdiff_t;
288  using reference = common_tuple<underlying_ref_t, underlying_ref_t>;
290  using pointer = void;
292  using iterator_category = detail::iterator_category_tag_t<underlying_iterator_type>;
294  using iterator_concept = detail::iterator_concept_tag_t<underlying_iterator_type>;
296 
300  basic_iterator() = default;
301  basic_iterator(basic_iterator const &) = default;
302  basic_iterator(basic_iterator &&) = default;
303  basic_iterator & operator=(basic_iterator const &) = default;
304  basic_iterator & operator=(basic_iterator &&) = default;
305  ~basic_iterator() = default;
306 
319  constexpr basic_iterator(underlying_iterator_type iter,
320  underlying_iterator_type begin_it,
321  underlying_iterator_type end_it) noexcept :
322  first_it{iter},
323  second_it{std::ranges::next(iter, 1, end_it)},
324  begin_it{begin_it},
325  end_it{end_it}
326  {}
327 
336  template <typename other_range_type>
338  requires std::convertible_to<other_range_type, range_type &> &&
339  std::same_as<std::remove_const_t<other_range_type>, std::remove_const_t<range_type>>
341  constexpr basic_iterator(basic_iterator<other_range_type> other) noexcept :
342  basic_iterator{std::move(other.first_it), std::move(other.begin_it), std::move(other.end_it)}
343  {}
345 
349  constexpr reference operator*() const
351  noexcept(noexcept(*std::declval<underlying_iterator_type>()))
352  {
353  return reference{*first_it, *second_it};
354  }
355 
359  constexpr reference operator[](size_t const index) const
360  noexcept(noexcept(std::declval<basic_iterator &>().from_index(1)))
362  requires std::random_access_iterator<underlying_iterator_type>
364  {
365  return *(*this + index);
366  }
368 
372  constexpr basic_iterator & operator++(/*pre-increment*/)
374  noexcept(noexcept(++std::declval<underlying_iterator_type &>()))
375  {
376  if (++second_it == end_it)
377  {
378  ++first_it;
379  second_it = first_it;
380  ++second_it;
381  }
382  return *this;
383  }
384 
386  constexpr basic_iterator operator++(int /*post-increment*/)
387  noexcept(noexcept(std::declval<underlying_iterator_type &>()++))
388  {
389  basic_iterator tmp{*this};
390  ++*this;
391  return tmp;
392  }
393 
395  constexpr basic_iterator & operator--(/*pre-decrement*/)
396  noexcept(noexcept(--std::declval<underlying_iterator_type &>()))
398  requires std::bidirectional_iterator<underlying_iterator_type>
400  {
401  if (--second_it == first_it)
402  {
403  --first_it;
404  second_it = end_it;
405  --second_it;
406  }
407  return *this;
408  }
409 
411  constexpr basic_iterator operator--(int /*post-decrement*/)
412  noexcept(noexcept(std::declval<underlying_iterator_type &>()--))
414  requires std::bidirectional_iterator<underlying_iterator_type>
416  {
417  basic_iterator tmp{*this};
418  --*this;
419  return tmp;
420  }
421 
424  constexpr basic_iterator & operator+=(difference_type const offset)
425  noexcept(noexcept(std::declval<basic_iterator &>().from_index(1)))
427  requires std::random_access_iterator<underlying_iterator_type>
429  {
430  from_index(to_index() + offset);
431  return *this;
432  }
433 
436  constexpr basic_iterator operator+(difference_type const offset) const
437  noexcept(noexcept(std::declval<basic_iterator &>() += 1))
439  requires std::random_access_iterator<underlying_iterator_type>
441  {
442  basic_iterator tmp{*this};
443  return (tmp += offset);
444  }
445 
448  constexpr friend basic_iterator operator+(difference_type const offset, basic_iterator iter)
449  noexcept(noexcept(std::declval<basic_iterator<range_type> &>().from_index(1)))
451  requires std::random_access_iterator<underlying_iterator_type>
453  {
454  iter.from_index(iter.to_index() + offset);
455  return iter;
456  }
457 
460  constexpr basic_iterator & operator-=(difference_type const offset)
461  noexcept(noexcept(std::declval<basic_iterator &>().from_index(1)))
463  requires std::random_access_iterator<underlying_iterator_type>
465  {
466  from_index(to_index() - offset);
467  return *this;
468  }
469 
472  constexpr basic_iterator operator-(difference_type const offset) const
473  noexcept(noexcept(std::declval<basic_iterator &>() -= 1))
475  requires std::random_access_iterator<underlying_iterator_type>
477  {
478  basic_iterator tmp{*this};
479  return (tmp -= offset);
480  }
481 
484  template <typename other_range_type>
486  requires std::random_access_iterator<underlying_iterator_type> &&
487  std::same_as<std::remove_const_t<range_type>, std::remove_const_t<other_range_type>>
489  constexpr difference_type operator-(basic_iterator<other_range_type> const & rhs) const
490  noexcept(noexcept(std::declval<basic_iterator &>().to_index()))
491  {
492  return static_cast<difference_type>(to_index() - rhs.to_index());
493  }
495 
501  //NOTE: The comparison operators should be implemented as friends, but due to a bug in gcc friend function
502  // cannot yet be constrained. To avoid unexpected errors with the comparison all operators are implemented as
503  // direct members and not as friends.
504 
506  template <typename other_range_type>
508  requires std::equality_comparable_with<underlying_iterator_type, std::ranges::iterator_t<other_range_type>> &&
509  std::same_as<std::remove_const_t<range_type>, std::remove_const_t<other_range_type>>
511  constexpr bool operator==(basic_iterator<other_range_type> const & rhs) const
512  noexcept(noexcept(std::declval<underlying_iterator_type &>() == std::declval<underlying_iterator_type &>()))
513  {
514  return std::tie(first_it, second_it) == std::tie(rhs.first_it, rhs.second_it);
515  }
516 
518  template <typename other_range_type>
520  requires std::equality_comparable_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>>
523  constexpr bool operator!=(basic_iterator<other_range_type> const & rhs) const
524  noexcept(noexcept(std::declval<underlying_iterator_type &>() != std::declval<underlying_iterator_type &>()))
525  {
526  return !(*this == rhs);
527  }
528 
530  template <typename other_range_type>
532  requires std::totally_ordered_with<underlying_iterator_type,
533  std::ranges::iterator_t<other_range_type>> &&
534  std::same_as<std::remove_const_t<range_type>, std::remove_const_t<other_range_type>>
536  constexpr bool operator<(basic_iterator<other_range_type> const & rhs) const
537  noexcept(noexcept(std::declval<underlying_iterator_type &>() < std::declval<underlying_iterator_type &>()))
538  {
539  return std::tie(first_it, second_it) < std::tie(rhs.first_it, rhs.second_it);
540  }
541 
543  template <typename other_range_type>
545  requires std::totally_ordered_with<underlying_iterator_type,
546  std::ranges::iterator_t<other_range_type>> &&
547  std::same_as<std::remove_const_t<range_type>, std::remove_const_t<other_range_type>>
549  constexpr bool operator>(basic_iterator<other_range_type> const & rhs) const
550  noexcept(noexcept(std::declval<underlying_iterator_type &>() > std::declval<underlying_iterator_type &>()))
551 
552  {
553  return std::tie(first_it, second_it) > std::tie(rhs.first_it, rhs.second_it);
554  }
555 
557  template <typename other_range_type>
559  requires std::totally_ordered_with<underlying_iterator_type,
560  std::ranges::iterator_t<other_range_type>> &&
561  std::same_as<std::remove_const_t<range_type>, std::remove_const_t<other_range_type>>
563  constexpr bool operator<=(basic_iterator<other_range_type> const & rhs) const
564  noexcept(noexcept(std::declval<underlying_iterator_type &>() <= std::declval<underlying_iterator_type &>()))
565  {
566  return std::tie(first_it, second_it) <= std::tie(rhs.first_it, rhs.second_it);
567  }
568 
570  template <typename other_range_type>
572  requires std::totally_ordered_with<underlying_iterator_type,
573  std::ranges::iterator_t<other_range_type>> &&
574  std::same_as<std::remove_const_t<range_type>, std::remove_const_t<other_range_type>>
576  constexpr bool operator>=(basic_iterator<other_range_type> const & rhs) const
577  noexcept(noexcept(std::declval<underlying_iterator_type &>() >= std::declval<underlying_iterator_type &>()))
578  {
579  return std::tie(first_it, second_it) >= std::tie(rhs.first_it, rhs.second_it);
580  }
582 
583 private:
584 
597  constexpr size_t to_index() const
598  noexcept(noexcept(std::declval<underlying_iterator_type &>() - std::declval<underlying_iterator_type &>()))
600  requires std::random_access_iterator<underlying_iterator_type>
602  {
603  size_t src_size = end_it - begin_it;
604  size_t index_i = first_it - begin_it;
605  size_t index_j = second_it - begin_it;
606  return (src_size * (src_size - 1)/2) - (src_size - index_i) * ((src_size - index_i) - 1)/2 +
607  index_j - index_i - 1;
608  }
609 
614  constexpr void from_index(size_t const index)
615  noexcept(noexcept(std::declval<underlying_iterator_type &>() - std::declval<underlying_iterator_type &>()) &&
616  noexcept(std::declval<underlying_iterator_type &>() + 1))
618  requires std::random_access_iterator<underlying_iterator_type>
620  {
621  size_t src_size = end_it - begin_it;
622  size_t index_i = src_size - 2 -
623  std::floor(std::sqrt(-8 * index + 4 * src_size * (src_size - 1) - 7)/2.0 - 0.5);
624  size_t index_j = index + index_i + 1 - src_size * (src_size - 1)/2 + (src_size - index_i) *
625  ((src_size - index_i) - 1)/2;
626  first_it = begin_it + index_i;
627  second_it = begin_it + index_j;
628  }
629 
631  underlying_iterator_type first_it{};
633  underlying_iterator_type second_it{};
635  underlying_iterator_type begin_it{};
637  underlying_iterator_type end_it{};
638 };
639 
640 } // namespace seqan3::detail
641 
642 namespace seqan3::views
643 {
708 inline constexpr auto pairwise_combine = detail::adaptor_for_view_without_args<detail::pairwise_combine_view>{};
709 
711 } // namespace seqan3::views
std::floor
T floor(T... args)
seqan3::views
The SeqAn namespace for views.
Definition: view_iota_simd.hpp:218
std::rel_ops::operator!=
T operator!=(T... args)
std::tuple
cmath
std::sqrt
T sqrt(T... args)
concept.hpp
Additional non-standard concepts for ranges.
std::tie
T tie(T... args)
seqan3::views::pairwise_combine
constexpr auto pairwise_combine
A view adaptor that generates all pairwise combinations of the elements of the underlying range.
Definition: pairwise_combine.hpp:708
seqan3::views::move
auto const move
A view that turns lvalue-references into rvalue-references.
Definition: move.hpp:68
const_iterable_range
Specifies requirements of an input range type for which the const version of that type satisfies the ...
transformation_trait_or.hpp
Provides seqan3::detail::transformation_trait_or.
std::iter_value_t
seqan3::pack_traits::size
constexpr size_t size
The size of a type pack.
Definition: traits.hpp:116
ranges
Adaptations of concepts from the Ranges TS.
std::ranges::begin
T begin(T... args)
std
SeqAn specific customisations in the standard namespace.
std::ptrdiff_t
std::remove_cvref_t
std::remove_const_t
common_tuple.hpp
Provides seqan3::common_tuple and seqan3::common_pair.
std::end
T end(T... args)
detail.hpp
Auxiliary header for the views submodule .
std::declval
T declval(T... args)