SeqAn3  3.2.0-rc.1
The Modern C++ library for sequence analysis.
join_with.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 <ranges>
16 #include <variant>
17 
22 
24 // Contains helpers for seqan3::views::join_with.
25 // See https://eel.is/c++draft/range.join.with
27 {
28 
29 template <class R, class P>
30 concept compatible_joinable_ranges =
31  std::common_with<std::ranges::range_value_t<R>, std::ranges::range_value_t<P>>
32  && std::common_reference_with<std::ranges::range_reference_t<R>, std::ranges::range_reference_t<P>>
33  && std::common_reference_with<std::ranges::range_rvalue_reference_t<R>, std::ranges::range_rvalue_reference_t<P>>;
34 
35 template <class R>
36 concept bidirectional_common = std::ranges::bidirectional_range<R> && std::ranges::common_range<R>;
37 
38 // A helper to decide whether the join_with view should have a non_propagating_cache member.
39 template <typename InnerRng>
40 struct cache_helper
41 {};
42 
43 // If the inner range is a reference, we do not need a cache.
44 template <typename InnerRng>
45  requires std::is_reference_v<InnerRng>
46 struct cache_helper<InnerRng>
47 {};
48 
49 // If the inner range is not a reference, we need a cache.
50 template <typename InnerRng>
51  requires (!std::is_reference_v<InnerRng>)
52 struct cache_helper<InnerRng>
53 {
54  non_propagating_cache<std::remove_cv_t<InnerRng>> inner_;
55 };
56 
57 } // namespace seqan3::detail::join_with
58 
59 namespace seqan3::detail
60 {
61 
62 template <std::ranges::input_range V, std::ranges::forward_range Pattern>
63  requires std::ranges::view<V> && std::ranges::input_range<std::ranges::range_reference_t<V>>
64  && std::ranges::view<Pattern>
65  && join_with::compatible_joinable_ranges<std::ranges::range_reference_t<V>, Pattern>
66 class join_with_view :
67  public std::ranges::view_interface<join_with_view<V, Pattern>>,
68  private join_with::cache_helper<std::ranges::range_reference_t<V>>
69 {
70  using InnerRng = std::ranges::range_reference_t<V>;
71 
72  V base_{};
73 
74  Pattern pattern_{};
75 
76  template <bool Const>
77  struct iterator;
78 
79  template <bool Const>
80  struct sentinel;
81 
82 public:
83  join_with_view()
84  requires std::default_initializable<V> && std::default_initializable<Pattern>
85  = default;
86 
87  constexpr join_with_view(V base, Pattern pattern) : base_(std::move(base)), pattern_(std::move(pattern))
88  {}
89 
90  template <std::ranges::input_range R>
91  requires std::constructible_from<V, std::ranges::views::all_t<R>>
92  && std::constructible_from<Pattern, std::ranges::single_view<std::ranges::range_value_t<InnerRng>>>
93  constexpr join_with_view(R && r, std::ranges::range_value_t<InnerRng> e) :
94  base_(std::ranges::views::all(std::forward<R>(r))),
95  pattern_(std::ranges::views::single(std::move(e)))
96  {}
97 
98  constexpr V base() const &
99  requires std::copy_constructible<V>
100  {
101  return base_;
102  }
103 
104  constexpr V base() &&
105  {
106  return std::move(base_);
107  }
108 
109  constexpr auto begin()
110  {
111  // In essence, simple_view means that the iterators of the non-const view and const range are the same and
112  // the sentinels of the non-const view and const range are the same.
113  // If std::is_reference_v<InnerRng>, we do not have a cache to store the value. Hence, we do not change
114  // any members and can use the const iterator.
115  constexpr bool use_const =
116  view_helper::simple_view<V> && std::is_reference_v<InnerRng> && view_helper::simple_view<Pattern>;
117  return iterator<use_const>{*this, std::ranges::begin(base_)};
118  }
119 
120  constexpr auto begin() const
121  requires std::ranges::input_range<V const> && std::ranges::forward_range<Pattern const>
122  && std::is_reference_v<std::ranges::range_reference_t<V const>>
123  {
124  return iterator<true>{*this, std::ranges::begin(base_)};
125  }
126 
127  constexpr auto end()
128 #if defined(__GNUC__) && (__GNUC__ == 10) // GCC10 needs a little help with the return type
129  -> std::conditional_t<std::ranges::forward_range<V> && std::is_reference_v<InnerRng>
130  && std::ranges::forward_range<InnerRng> && std::ranges::common_range<V>
131  && std::ranges::common_range<InnerRng>,
132  iterator<view_helper::simple_view<V> && view_helper::simple_view<Pattern>>,
133  sentinel<view_helper::simple_view<V> && view_helper::simple_view<Pattern>>>
134 #endif
135  {
136  constexpr bool is_simple = view_helper::simple_view<V> && view_helper::simple_view<Pattern>;
137  if constexpr (std::ranges::forward_range<V> && std::is_reference_v<InnerRng>
138  && std::ranges::forward_range<InnerRng> && std::ranges::common_range<V>
139  && std::ranges::common_range<InnerRng>)
140  return iterator<is_simple>{*this, std::ranges::end(base_)};
141  else
142  return sentinel<is_simple>{*this};
143  }
144 
145  constexpr auto end() const
146  requires std::ranges::input_range<V const> && std::ranges::forward_range<Pattern const>
147  && std::is_reference_v<std::ranges::range_reference_t<V const>>
148  {
149  using InnerConstRng = std::ranges::range_reference_t<V const>;
150  if constexpr (std::ranges::forward_range<V const> && std::ranges::forward_range<InnerConstRng>
151  && std::ranges::common_range<V const> && std::ranges::common_range<InnerConstRng>)
152  return iterator<true>{*this, std::ranges::end(base_)};
153  else
154  return sentinel<true>{*this};
155  }
156 };
157 
158 template <class R, class P>
159 join_with_view(R &&, P &&) -> join_with_view<seqan3::detail::all_t<R>, seqan3::detail::all_t<P>>;
160 
161 template <std::ranges::input_range R>
162 join_with_view(R &&, std::ranges::range_value_t<std::ranges::range_reference_t<R>>)
163  -> join_with_view<seqan3::detail::all_t<R>,
164  std::ranges::single_view<std::ranges::range_value_t<std::ranges::range_reference_t<R>>>>;
165 
166 } // namespace seqan3::detail
167 
169 {
170 
171 // These definitions are needed in multiple places. This helper struct avoids the need to define them separately
172 // at each location.
173 template <bool Const, typename V, typename Pattern>
174 struct helper
175 {
176  using Parent = view_helper::maybe_const<Const, join_with_view<V, Pattern>>;
177  using Base = view_helper::maybe_const<Const, V>;
178  using InnerBase = std::ranges::range_reference_t<Base>;
179  using PatternBase = view_helper::maybe_const<Const, Pattern>;
180 
181  using OuterIter = std::ranges::iterator_t<Base>;
182  using InnerIter = std::ranges::iterator_t<InnerBase>;
183  using PatternIter = std::ranges::iterator_t<PatternBase>;
184 
185  static constexpr bool ref_is_glvalue = std::is_reference_v<InnerBase>;
186 };
187 
188 template <bool Const, typename V, typename Pattern, bool ref_is_glvalue>
189 struct iterator_category_t;
190 
191 // If std::is_reference_v<InnerBase> is true, define iterator_category.
192 template <bool Const, typename V, typename Pattern>
193 struct iterator_category_t<Const, V, Pattern, true>
194 {
195  using Parent = helper<Const, V, Pattern>::Parent;
196  using Base = helper<Const, V, Pattern>::Base;
197  using InnerBase = helper<Const, V, Pattern>::InnerBase;
198  using PatternBase = helper<Const, V, Pattern>::PatternBase;
199 
200  using OuterIter = helper<Const, V, Pattern>::OuterIter;
201  using InnerIter = helper<Const, V, Pattern>::InnerIter;
202  using PatternIter = helper<Const, V, Pattern>::PatternIter;
203 
204  using iterator_category = std::conditional_t<
206  std::common_reference_t<std::iter_reference_t<InnerIter>, std::iter_reference_t<PatternIter>>>,
209  std::derived_from<std::bidirectional_iterator_tag,
211  && std::derived_from<std::bidirectional_iterator_tag,
213  && std::derived_from<std::bidirectional_iterator_tag,
215  && std::ranges::common_range<InnerBase> && std::ranges::common_range<PatternBase>,
219  && std::derived_from<std::forward_iterator_tag,
221  && std::derived_from<std::forward_iterator_tag,
225 };
226 
227 // If std::is_reference_v<InnerBase> is false, there is no iterator_category.
228 template <bool Const, typename V, typename Pattern>
229 struct iterator_category_t<Const, V, Pattern, false>
230 {};
231 
232 } // namespace seqan3::detail::join_with
233 
234 namespace seqan3::detail
235 {
236 
237 template <std::ranges::input_range V, std::ranges::forward_range Pattern>
238  requires std::ranges::view<V> && std::ranges::input_range<std::ranges::range_reference_t<V>>
239  && std::ranges::view<Pattern>
240  && join_with::compatible_joinable_ranges<std::ranges::range_reference_t<V>, Pattern>
241 template <bool Const>
242 class join_with_view<V, Pattern>::iterator :
243  public join_with::iterator_category_t<Const, V, Pattern, join_with::helper<Const, V, Pattern>::ref_is_glvalue>
244 {
245  using helper_t = join_with::helper<Const, V, Pattern>;
246  using Parent = helper_t::Parent;
247  using Base = helper_t::Base;
248  using InnerBase = helper_t::InnerBase;
249  using PatternBase = helper_t::PatternBase;
250 
251  using OuterIter = helper_t::OuterIter;
252  using InnerIter = helper_t::InnerIter;
253  using PatternIter = helper_t::PatternIter;
254 
255  static constexpr bool ref_is_glvalue = helper_t::ref_is_glvalue;
256 
257  friend class join_with_view<V, Pattern>;
258 
259  Parent * parent_{nullptr};
260 
261 public:
262  OuterIter outer_it_{};
263 
264 private:
266 
267  constexpr iterator(Parent & parent, std::ranges::iterator_t<Base> outer) :
268  parent_(std::addressof(parent)),
269  outer_it_(std::move(outer))
270  {
271  if (outer_it_ != std::ranges::end(parent_->base_))
272  {
273  auto && inner = update_inner(outer_it_);
274  inner_it_.template emplace<1>(std::ranges::begin(inner));
275  satisfy();
276  }
277  }
278 
279  constexpr auto && update_inner(OuterIter const & x)
280  {
281  if constexpr (ref_is_glvalue)
282  return *x;
283  else
284  return parent_->inner_.emplace_deref(x);
285  }
286 
287  constexpr auto && get_inner(OuterIter const & x)
288  {
289  if constexpr (ref_is_glvalue)
290  return *x;
291  else
292  return *parent_->inner_;
293  }
294 
295  // Skips over empty inner ranges.
296  // https://eel.is/c++draft/range.join.with#iterator-7
297  constexpr void satisfy()
298  {
299  while (true)
300  {
301  if (inner_it_.index() == 0)
302  {
303  if (std::get<0>(inner_it_) != std::ranges::end(parent_->pattern_))
304  break;
305  auto && inner = update_inner(outer_it_);
306  inner_it_.template emplace<1>(std::ranges::begin(inner));
307  }
308  else
309  {
310  auto && inner = get_inner(outer_it_);
311  if (std::get<1>(inner_it_) != std::ranges::end(inner))
312  break;
313  if (++outer_it_ == std::ranges::end(parent_->base_))
314  {
315  if constexpr (ref_is_glvalue)
316  inner_it_.template emplace<0>();
317  break;
318  }
319  inner_it_.template emplace<0>(std::ranges::begin(parent_->pattern_));
320  }
321  }
322  }
323 
324 public:
325  using iterator_concept = std::conditional_t<
326  !ref_is_glvalue,
328  std::conditional_t<std::ranges::bidirectional_range<Base> && join_with::bidirectional_common<InnerBase>
329  && join_with::bidirectional_common<PatternBase>,
331  std::conditional_t<std::ranges::forward_range<Base> && std::ranges::forward_range<InnerBase>,
334 
335  using value_type = std::common_type_t<std::iter_value_t<InnerIter>, std::iter_value_t<PatternIter>>;
337  std::iter_difference_t<InnerIter>,
338  std::iter_difference_t<PatternIter>>;
339 
340  iterator()
341  requires std::default_initializable<OuterIter>
342  = default;
343 
344  constexpr iterator(iterator<!Const> i)
345  requires Const && std::convertible_to<std::ranges::iterator_t<V>, OuterIter>
346  && std::convertible_to<std::ranges::iterator_t<InnerRng>, InnerIter>
347  && std::convertible_to<std::ranges::iterator_t<Pattern>, PatternIter>
348  : outer_it_(std::move(i.outer_it_)), parent_(i.parent_)
349  {
350  if (i.inner_it_.index() == 0)
351  inner_it_.template emplace<0>(std::get<0>(std::move(i.inner_it_)));
352  else
353  inner_it_.template emplace<1>(std::get<1>(std::move(i.inner_it_)));
354  }
355 
356  constexpr decltype(auto) operator*() const
357  {
358  using reference = std::common_reference_t<std::iter_reference_t<InnerIter>, std::iter_reference_t<PatternIter>>;
359  return std::visit(
360  [](auto & it) -> reference
361  {
362  return *it;
363  },
364  inner_it_);
365  }
366 
367  constexpr iterator & operator++()
368  {
369  std::visit(
370  [](auto & it)
371  {
372  ++it;
373  },
374  inner_it_);
375  satisfy();
376  return *this;
377  }
378 
379  constexpr void operator++(int)
380  {
381  ++*this;
382  }
383 
384  constexpr iterator operator++(int)
385  requires ref_is_glvalue && std::forward_iterator<OuterIter> && std::forward_iterator<InnerIter>
386  {
387  iterator tmp = *this;
388  ++*this;
389  return tmp;
390  }
391 
392  constexpr iterator & operator--()
393  requires ref_is_glvalue && std::ranges::bidirectional_range<Base> && join_with::bidirectional_common<InnerBase>
394  && join_with::bidirectional_common<PatternBase>
395  {
396  if (outer_it_ == std::ranges::end(parent_->base_))
397  {
398  auto && inner = *--outer_it_;
399  inner_it_.template emplace<1>(std::ranges::end(inner));
400  }
401 
402  // Similar to satifsy(). Skips over empty inner ranges when going backwards.
403  while (true)
404  {
405  if (inner_it_.index() == 0)
406  {
407  auto & it = std::get<0>(inner_it_);
408  if (it == std::ranges::begin(parent_->pattern_))
409  {
410  auto && inner = *--outer_it_;
411  inner_it_.template emplace<1>(std::ranges::end(inner));
412  }
413  else
414  {
415  break;
416  }
417  }
418  else
419  {
420  auto & it = std::get<1>(inner_it_);
421  auto && inner = *outer_it_;
422  if (it == std::ranges::begin(inner))
423  {
424  inner_it_.template emplace<0>(std::ranges::end(parent_->pattern_));
425  }
426  else
427  {
428  break;
429  }
430  }
431  }
432 
433  std::visit(
434  [](auto & it)
435  {
436  --it;
437  },
438  inner_it_);
439  return *this;
440  }
441 
442  constexpr iterator operator--(int)
443  requires ref_is_glvalue && std::ranges::bidirectional_range<Base> && join_with::bidirectional_common<InnerBase>
444  && join_with::bidirectional_common<PatternBase>
445  {
446  iterator tmp = *this;
447  --*this;
448  return tmp;
449  }
450 
451  friend constexpr bool operator==(iterator const & x, iterator const & y)
452  requires ref_is_glvalue && std::equality_comparable<OuterIter> && std::equality_comparable<InnerIter>
453  {
454  return x.outer_it_ == y.outer_it_ && x.inner_it_ == y.inner_it_;
455  }
456 
457  friend constexpr decltype(auto) iter_move(iterator const & x)
458  {
459  using rvalue_reference =
460  std::common_reference_t<std::iter_rvalue_reference_t<InnerIter>, std::iter_rvalue_reference_t<PatternIter>>;
461  return std::visit<rvalue_reference>(std::ranges::iter_move, x.inner_it_);
462  }
463 
464  friend constexpr void iter_swap(iterator const & x, iterator const & y)
465  requires std::indirectly_swappable<InnerIter, PatternIter>
466  {
467  std::visit(std::ranges::iter_swap, x.inner_it_, y.inner_it_);
468  }
469 };
470 
471 template <std::ranges::input_range V, std::ranges::forward_range Pattern>
472  requires std::ranges::view<V> && std::ranges::input_range<std::ranges::range_reference_t<V>>
473  && std::ranges::view<Pattern>
474  && join_with::compatible_joinable_ranges<std::ranges::range_reference_t<V>, Pattern>
475 template <bool Const>
476 class join_with_view<V, Pattern>::sentinel
477 {
478  using Parent = view_helper::maybe_const<Const, join_with_view>;
479  using Base = view_helper::maybe_const<Const, V>;
480  std::ranges::sentinel_t<Base> end_ = std::ranges::sentinel_t<Base>();
481 
482  friend class join_with_view<V, Pattern>;
483 
484  constexpr explicit sentinel(Parent & parent) : end_(std::ranges::end(parent.base_))
485  {}
486 
487 public:
488  sentinel() = default;
489  constexpr sentinel(sentinel<!Const> s)
490  requires Const && std::convertible_to<std::ranges::sentinel_t<V>, std::ranges::sentinel_t<Base>>
491  : end_(std::move(s.end_))
492  {}
493 
494  template <bool OtherConst>
495  requires std::sentinel_for<std::ranges::sentinel_t<Base>,
496  std::ranges::iterator_t<view_helper::maybe_const<OtherConst, V>>>
497  friend constexpr bool operator==(iterator<OtherConst> const & x, sentinel const & y)
498  {
499  return x.outer_it_ == y.end_;
500  }
501 };
502 
503 struct join_with_fn
504 {
505  template <typename Pattern>
506  constexpr auto operator()(Pattern && pattern) const
507  {
508  return seqan3::detail::adaptor_from_functor{*this, std::forward<Pattern>(pattern)};
509  }
510 
511  template <std::ranges::range urng_t, typename Pattern>
512  constexpr auto operator()(urng_t && urange, Pattern && pattern) const
513  {
514  return join_with_view{std::forward<urng_t>(urange), std::forward<Pattern>(pattern)};
515  }
516 };
517 
518 } // namespace seqan3::detail
520 
521 namespace seqan3::views
522 {
523 
531 inline constexpr auto join_with = seqan3::detail::join_with_fn{};
532 
533 } // namespace seqan3::views
Provides seqan3::detail::adaptor_from_functor.
T addressof(T... args)
Provides seqan3::detail::all.
T begin(T... args)
T end(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
@ single
The text is a single range.
Definition: search/fm_index/concept.hpp:93
constexpr auto join_with
A view adaptor that represents view consisting of the sequence obtained from flattening a view of ran...
Definition: join_with.hpp:531
Provides implementation helper for seqan3::views::zip and seqan3::views::join_with.
T is_lvalue_reference_v
T iter_swap(T... args)
The SeqAn namespace for views.
Definition: char_strictly_to.hpp:22
SeqAn specific customisations in the standard namespace.
Provides seqan3::detail::views::non_propagating_cache.
The <ranges> header from C++20's standard library.
T visit(T... args)