SeqAn3  3.2.0-rc.1
The Modern C++ library for sequence analysis.
zip.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 <algorithm>
16 #include <functional>
17 #include <ranges>
18 
23 
25 // Contains helpers for seqan3::views::zip.
26 namespace seqan3::detail::zip
27 {
28 
29 // https://eel.is/c++draft/range.zip#concept:zip-is-common
30 template <typename... range_ts>
31 concept zip_is_common = (sizeof...(range_ts) == 1 && (std::ranges::common_range<range_ts> && ...))
32  || (!(std::ranges::bidirectional_range<range_ts> && ...)
33  && (std::ranges::common_range<range_ts> && ...))
34  || ((std::ranges::random_access_range<range_ts> && ...)
35  && (std::ranges::sized_range<range_ts> && ...));
36 
37 // Helper for tuple_or_pair
38 template <typename... ts>
39 struct tuple_or_pair_impl;
40 
41 // Helper for tuple_or_pair
42 template <typename... ts>
43  requires (sizeof...(ts) != 2)
44 struct tuple_or_pair_impl<ts...>
45 {
46  using type = seqan3::common_tuple<ts...>;
47 };
48 
49 // Helper for tuple_or_pair
50 template <typename... ts>
51  requires (sizeof...(ts) == 2)
52 struct tuple_or_pair_impl<ts...>
53 {
54  using type = seqan3::common_pair<ts...>;
55 };
56 
57 // https://eel.is/c++draft/range.zip#view-1
58 template <typename... ts>
59 using tuple_or_pair = tuple_or_pair_impl<ts...>::type;
60 
61 // std::abs has problems with ambiguous overloads
62 template <typename t>
63 constexpr t abs(t && v) noexcept
64 {
65  if constexpr (std::is_signed_v<t>)
66  return v < 0 ? -v : v;
67  else
68  return v;
69 }
70 
71 // Returns a new tuple containing the result of applying a function to each tuple element.
72 // https://eel.is/c++draft/range.zip.view
73 template <typename fun_t, typename tuple_t>
74 constexpr auto tuple_transform(fun_t && f, tuple_t && tuple)
75 {
76  return std::apply(
77  [&]<typename... ts>(ts &&... elements)
78  {
79  return tuple_or_pair<std::invoke_result_t<fun_t &, ts>...>{std::invoke(f, std::forward<ts>(elements))...};
80  },
81  std::forward<tuple_t>(tuple));
82 }
83 
84 // Applies a function to each tuple element.
85 // https://eel.is/c++draft/range.zip.view
86 template <typename fun_t, typename tuple_t>
87 constexpr void tuple_for_each(fun_t && f, tuple_t && tuple)
88 {
89  std::apply(
90  [&]<typename... ts>(ts &&... elements)
91  {
92  (std::invoke(f, std::forward<ts>(elements)), ...);
93  },
94  std::forward<tuple_t>(tuple));
95 }
96 
97 template <bool is_const, typename... range_ts>
98 concept all_random_access = (std::ranges::random_access_range<view_helper::maybe_const<is_const, range_ts>> && ...);
99 
100 template <bool is_const, typename... range_ts>
101 concept all_bidirectional = (std::ranges::bidirectional_range<view_helper::maybe_const<is_const, range_ts>> && ...);
102 
103 template <bool is_const, typename... range_ts>
104 concept all_forward = (std::ranges::forward_range<view_helper::maybe_const<is_const, range_ts>> && ...);
105 
106 // Pre cpp20-iterators: Infer iterator_category from modelled concepts.
107 #if defined(__GNUC__) && (__GNUC__ == 10)
108 template <bool is_const, typename... range_ts>
109 concept all_contiguous = (std::ranges::contiguous_range<view_helper::maybe_const<is_const, range_ts>> && ...);
110 
111 template <bool Const, typename... Views>
112 struct iterator_category_t
113 {
114  using iterator_category = std::conditional_t<
115  all_contiguous<Const, Views...>,
116  std::contiguous_iterator_tag,
118  all_random_access<Const, Views...>,
121  all_bidirectional<Const, Views...>,
123  std::conditional_t<all_forward<Const, Views...>, std::forward_iterator_tag, std::input_iterator_tag>>>>;
124 };
125 #else // cpp20 iterators
126 template <bool>
127 struct iterator_category_t;
128 template <>
129 struct iterator_category_t<true>
130 {
131  using iterator_category = std::input_iterator_tag;
132 };
133 template <>
134 struct iterator_category_t<false>
135 {};
136 #endif
137 
138 } // namespace seqan3::detail::zip
139 
140 namespace seqan3::detail
141 {
142 
143 template <std::ranges::input_range... Views>
144  requires (std::ranges::view<Views> && ...) && (sizeof...(Views) > 0)
145 class zip_view : public std::ranges::view_interface<zip_view<Views...>>
146 {
147  seqan3::common_tuple<Views...> views_;
148 
149  template <bool>
150  class iterator;
151 
152  template <bool>
153  class sentinel;
154 
155 public:
156  zip_view()
157  requires (std::is_default_constructible_v<Views> && ...)
158  = default;
159  constexpr explicit zip_view(Views... views) : views_(std::move(views)...)
160  {}
161 
162  constexpr auto begin()
163  requires (!(view_helper::simple_view<Views> && ...))
164  {
165  return iterator<false>(zip::tuple_transform(std::ranges::begin, views_));
166  }
167 
168  constexpr auto begin() const
169  requires (std::ranges::range<Views const> && ...)
170  {
171  return iterator<true>(zip::tuple_transform(std::ranges::begin, views_));
172  }
173 
174  constexpr auto end()
175  requires (!(view_helper::simple_view<Views> && ...))
176  {
177  if constexpr (!zip::zip_is_common<Views...>)
178  return sentinel<false>(zip::tuple_transform(std::ranges::end, views_));
179  else if constexpr ((std::ranges::random_access_range<Views> && ...))
180  return begin() + std::iter_difference_t<iterator<false>>(size());
181  else
182  return iterator<false>(zip::tuple_transform(std::ranges::end, views_));
183  }
184 
185  constexpr auto end() const
186  requires (std::ranges::range<Views const> && ...)
187  {
188  if constexpr (!zip::zip_is_common<Views const...>)
189  return sentinel<true>(zip::tuple_transform(std::ranges::end, views_));
190  else if constexpr ((std::ranges::random_access_range<Views const> && ...))
191  return begin() + std::iter_difference_t<iterator<true>>(size());
192  else
193  return iterator<true>(zip::tuple_transform(std::ranges::end, views_));
194  }
195 
196  constexpr auto size()
197  requires (std::ranges::sized_range<Views> && ...)
198  {
199  return std::apply(
200  [](auto... sizes)
201  {
202  using common_size_t = std::make_unsigned_t<std::common_type_t<decltype(sizes)...>>;
203  return std::ranges::min({static_cast<common_size_t>(sizes)...});
204  },
205  zip::tuple_transform(std::ranges::size, views_));
206  }
207 
208  constexpr auto size() const
209  requires (std::ranges::sized_range<Views const> && ...)
210  {
211  return std::apply(
212  [](auto... sizes)
213  {
214  using common_size_t = std::make_unsigned_t<std::common_type_t<decltype(sizes)...>>;
215  return std::ranges::min({static_cast<common_size_t>(sizes)...});
216  },
217  zip::tuple_transform(std::ranges::size, views_));
218  }
219 };
220 
221 template <typename... range_ts>
222 zip_view(range_ts &&...) -> zip_view<seqan3::detail::all_t<range_ts>...>;
223 
224 template <std::ranges::input_range... Views>
225  requires (std::ranges::view<Views> && ...) && (sizeof...(Views) > 0)
226 template <bool Const>
227 #if defined(__GNUC__) && (__GNUC__ == 10) // cpp17 iterators
228 class zip_view<Views...>::iterator : public zip::iterator_category_t<Const, Views...>
229 #else // cpp20 iterators
230 class zip_view<Views...>::iterator : public zip::iterator_category_t<zip::all_forward<Const, Views...>>
231 #endif
232 {
233 private:
234  constexpr explicit iterator(
235  zip::tuple_or_pair<std::ranges::iterator_t<view_helper::maybe_const<Const, Views>>...> current) :
236  current_(std::move(current))
237  {}
238 
239  friend class zip_view<Views...>;
240 
241 public:
242  // Exposition-only. Is public for access via friend operator== of the sentinel.
243  zip::tuple_or_pair<std::ranges::iterator_t<view_helper::maybe_const<Const, Views>>...> current_;
244 
245  using iterator_concept = std::conditional_t<
246  zip::all_random_access<Const, Views...>,
249  zip::all_bidirectional<Const, Views...>,
251  std::conditional_t<zip::all_forward<Const, Views...>, std::forward_iterator_tag, std::input_iterator_tag>>>;
252  using value_type = zip::tuple_or_pair<std::ranges::range_value_t<view_helper::maybe_const<Const, Views>>...>;
253  using difference_type =
255 
256  iterator() = default;
257  constexpr iterator(iterator<!Const> i)
258  requires Const
259  && (std::convertible_to<std::ranges::iterator_t<Views>,
260  std::ranges::iterator_t<view_helper::maybe_const<Const, Views>>>
261  && ...)
262  : current_(std::move(i.current))
263  {}
264 
265  constexpr auto operator*() const
266  {
267  return zip::tuple_transform(
268  [](auto & i) -> decltype(auto)
269  {
270  return *i;
271  },
272  current_);
273  }
274 
275  constexpr iterator & operator++()
276  {
277  zip::tuple_for_each(
278  [](auto & i)
279  {
280  ++i;
281  },
282  current_);
283  return *this;
284  }
285 
286  constexpr void operator++(int)
287  {
288  ++*this;
289  }
290 
291  constexpr iterator operator++(int)
292  requires zip::all_forward<Const, Views...>
293  {
294  auto tmp = *this;
295  ++*this;
296  return tmp;
297  }
298 
299  constexpr iterator & operator--()
300  requires zip::all_bidirectional<Const, Views...>
301  {
302  zip::tuple_for_each(
303  [](auto & i)
304  {
305  --i;
306  },
307  current_);
308  return *this;
309  }
310 
311  constexpr iterator operator--(int)
312  requires zip::all_bidirectional<Const, Views...>
313  {
314  auto tmp = *this;
315  --*this;
316  return tmp;
317  }
318 
319  constexpr iterator & operator+=(difference_type x)
320  requires zip::all_random_access<Const, Views...>
321  {
322  zip::tuple_for_each(
323  [&]<typename I>(I & i)
324  {
325  i += std::iter_difference_t<I>(x);
326  },
327  current_);
328  return *this;
329  }
330 
331  constexpr iterator & operator-=(difference_type x)
332  requires zip::all_random_access<Const, Views...>
333  {
334  zip::tuple_for_each(
335  [&]<typename I>(I & i)
336  {
337  i -= std::iter_difference_t<I>(x);
338  },
339  current_);
340  return *this;
341  }
342 
343  constexpr auto operator[](difference_type n) const
344  requires zip::all_random_access<Const, Views...>
345  {
346  return zip::tuple_transform(
347  [&]<typename I>(I & i) -> decltype(auto)
348  {
349  return i[std::iter_difference_t<I>(n)];
350  },
351  current_);
352  }
353 
354  friend constexpr bool operator==(iterator const & x, iterator const & y)
355  requires (std::equality_comparable<std::ranges::iterator_t<view_helper::maybe_const<Const, Views>>> && ...)
356  {
357  if constexpr (zip::all_bidirectional<Const, Views...>)
358  {
359  return x.current_ == y.current_;
360  }
361  else
362  {
363  return [&]<size_t... N>(std::integer_sequence<size_t, N...>)
364  {
365  return ((std::get<N>(x.current_) == std::get<N>(y.current_)) || ...);
366  }
367  (std::index_sequence_for<Views...>{});
368  }
369  }
370 
371  friend constexpr bool operator<(iterator const & x, iterator const & y)
372  requires zip::all_random_access<Const, Views...>
373  {
374  return x.current_ < y.current_;
375  }
376 
377  friend constexpr bool operator>(iterator const & x, iterator const & y)
378  requires zip::all_random_access<Const, Views...>
379  {
380  return y < x;
381  }
382 
383  friend constexpr bool operator<=(iterator const & x, iterator const & y)
384  requires zip::all_random_access<Const, Views...>
385  {
386  return !(y < x);
387  }
388 
389  friend constexpr bool operator>=(iterator const & x, iterator const & y)
390  requires zip::all_random_access<Const, Views...>
391  {
392  return !(x < y);
393  }
394 
395 #ifdef __cpp_lib_three_way_comparison
396  friend constexpr auto operator<=>(iterator const & x, iterator const & y)
397  requires zip::all_random_access<Const, Views...>
398  && (std::three_way_comparable<std::ranges::iterator_t<view_helper::maybe_const<Const, Views>>> && ...)
399  {
400  return x.current_ <=> y.current_;
401  }
402 #endif
403 
404  friend constexpr iterator operator+(iterator const & i, difference_type n)
405  requires zip::all_random_access<Const, Views...>
406  {
407  auto r = i;
408  r += n;
409  return r;
410  }
411 
412  friend constexpr iterator operator+(difference_type n, iterator const & i)
413  requires zip::all_random_access<Const, Views...>
414  {
415  return i + n;
416  }
417 
418  friend constexpr iterator operator-(iterator const & i, difference_type n)
419  requires zip::all_random_access<Const, Views...>
420  {
421  auto r = i;
422  r -= n;
423  return r;
424  }
425 
426  friend constexpr difference_type operator-(iterator const & x, iterator const & y)
427  requires (std::sized_sentinel_for<std::ranges::iterator_t<view_helper::maybe_const<Const, Views>>,
428  std::ranges::iterator_t<view_helper::maybe_const<Const, Views>>>
429  && ...)
430  {
431  return [&]<size_t... N>(std::integer_sequence<size_t, N...>)
432  {
433  return std::ranges::min(
434  {static_cast<difference_type>(std::get<N>(x.current_) - std::get<N>(y.current_))...},
435  [](difference_type a, difference_type b)
436  {
437  return zip::abs(b) < zip::abs(a);
438  });
439  }
440  (std::index_sequence_for<Views...>{});
441  }
442 
443  friend constexpr auto iter_move(iterator const & i) noexcept(
444  (noexcept(std::ranges::iter_move(
445  std::declval<std::ranges::iterator_t<view_helper::maybe_const<Const, Views>> const &>()))
446  && ...)
448  std::ranges::range_rvalue_reference_t<view_helper::maybe_const<Const, Views>>>
449  && ...))
450  {
451  return zip::tuple_transform(std::ranges::iter_move, i.current_);
452  }
453 
454  friend constexpr void iter_swap(iterator const & l, iterator const & r) noexcept(
455  (noexcept(std::ranges::iter_swap(
456  std::declval<std::ranges::iterator_t<view_helper::maybe_const<Const, Views>> const &>(),
457  std::declval<std::ranges::iterator_t<view_helper::maybe_const<Const, Views>> const &>()))
458  && ...))
459  requires (std::indirectly_swappable<std::ranges::iterator_t<view_helper::maybe_const<Const, Views>>> && ...)
460  {
461  [&]<size_t... N>(std::integer_sequence<size_t, N...>)
462  {
463  (std::ranges::iter_swap(std::get<N>(l.current_), std::get<N>(r.current)), ...);
464  }
465  (std::index_sequence_for<Views...>{});
466  }
467 };
468 
469 template <std::ranges::input_range... Views>
470  requires (std::ranges::view<Views> && ...) && (sizeof...(Views) > 0)
471 template <bool Const>
472 class zip_view<Views...>::sentinel
473 {
474 private:
475  constexpr explicit sentinel(
476  zip::tuple_or_pair<std::ranges::sentinel_t<view_helper::maybe_const<Const, Views>>...> end) :
477  end_(std::move(end))
478  {}
479 
480  friend class zip_view<Views...>;
481 
482 public:
483  // Exposition-only. Is public such that it can be accessed by friends.
484  zip::tuple_or_pair<std::ranges::sentinel_t<view_helper::maybe_const<Const, Views>>...> end_;
485 
486  sentinel() = default;
487  constexpr sentinel(sentinel<!Const> i)
488  requires Const
489  && (std::convertible_to<std::ranges::sentinel_t<Views>,
490  std::ranges::sentinel_t<view_helper::maybe_const<Const, Views>>>
491  && ...)
492  : end_(std::move(i.end_))
493  {}
494 
495  template <bool OtherConst>
496  requires (std::sentinel_for<std::ranges::sentinel_t<view_helper::maybe_const<Const, Views>>,
497  std::ranges::iterator_t<view_helper::maybe_const<OtherConst, Views>>>
498  && ...)
499  friend constexpr bool operator==(iterator<OtherConst> const & x, sentinel const & y)
500  {
501  return [&]<size_t... N>(std::integer_sequence<size_t, N...>)
502  {
503  return ((std::get<N>(x.current_) == std::get<N>(y.end_)) || ...);
504  }
505  (std::index_sequence_for<Views...>{});
506  }
507 
508  template <bool OtherConst>
509  requires (std::sized_sentinel_for<std::ranges::sentinel_t<view_helper::maybe_const<Const, Views>>,
510  std::ranges::iterator_t<view_helper::maybe_const<OtherConst, Views>>>
511  && ...)
512  friend constexpr std::common_type_t<std::ranges::range_difference_t<view_helper::maybe_const<OtherConst, Views>>...>
513  operator-(iterator<OtherConst> const & x, sentinel const & y)
514  {
515  using return_t =
517  return [&]<size_t... N>(std::integer_sequence<size_t, N...>)
518  {
519  return std::ranges::min({static_cast<return_t>(std::get<N>(x.current_) - std::get<N>(y.end_))...},
520  [](return_t a, return_t b)
521  {
522  return zip::abs(b) < zip::abs(a);
523  });
524  }
525  (std::index_sequence_for<Views...>{});
526  }
527 
528  template <bool OtherConst>
529  requires (std::sized_sentinel_for<std::ranges::sentinel_t<view_helper::maybe_const<Const, Views>>,
530  std::ranges::iterator_t<view_helper::maybe_const<OtherConst, Views>>>
531  && ...)
532  friend constexpr std::common_type_t<std::ranges::range_difference_t<view_helper::maybe_const<OtherConst, Views>>...>
533  operator-(sentinel const & y, iterator<OtherConst> const & x)
534  {
535  return -(x - y);
536  }
537 };
538 
539 struct zip_fn
540 {
541  template <typename urng_t>
542  constexpr auto operator()(urng_t && rng) const
543  {
544  return adaptor_from_functor{*this, std::forward<urng_t>(rng)};
545  }
546 
547  template <typename... urng_ts>
548  requires (sizeof...(urng_ts) == 0)
549  constexpr auto operator()(urng_ts &&... ranges) const
550  {
551  return std::views::empty<seqan3::common_tuple<>>;
552  }
553 
554  template <typename... urng_ts>
555  requires (sizeof...(urng_ts) > 1)
556  constexpr auto operator()(urng_ts &&... ranges) const
557  {
558  return zip_view{std::forward<urng_ts>(ranges)...};
559  }
560 };
561 
562 } // namespace seqan3::detail
564 
565 namespace seqan3::views
566 {
567 
573 inline constexpr auto zip = seqan3::detail::zip_fn{};
574 
575 } // namespace seqan3::views
Provides seqan3::detail::adaptor_from_functor.
Provides seqan3::detail::all.
T apply(T... args)
T begin(T... args)
A std::tuple implementation that incorporates most changes from C++23's standard library.
Definition: common_tuple.hpp:29
Provides seqan3::common_tuple.
T declval(T... args)
T end(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 zip
A view adaptor that takes several views and returns tuple-like values from every i-th element of each...
Definition: zip.hpp:573
constexpr auto elements
A view calling get on each element in a range.
Definition: elements.hpp:80
Provides implementation helper for seqan3::views::zip and seqan3::views::join_with.
T invoke(T... args)
T is_nothrow_move_constructible_v
T iter_swap(T... args)
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.
A std::pair implementation that incorporates most changes from C++23's standard library.
Definition: common_pair.hpp:28