SeqAn3  3.2.0-rc.1
The Modern C++ library for sequence analysis.
chunk.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 
20 #include <seqan3/core/platform.hpp>
24 
25 namespace seqan3::detail
26 {
27 // ---------------------------------------------------------------------------------------------------------------------
28 // chunk_view class
29 // ---------------------------------------------------------------------------------------------------------------------
30 
39 template <std::ranges::input_range urng_t>
40  requires std::ranges::view<urng_t>
41 class chunk_view : public std::ranges::view_interface<chunk_view<urng_t>>
42 {
43 private:
45  urng_t urange;
46 
48  std::ranges::range_difference_t<urng_t> chunk_size;
49 
50  // The iterator type if `urng_t` is a pure input range. See class definition for details.
51  template <bool const_range>
52  class basic_input_iterator;
53 
54  // The iterator type if `urng_t` is at least a forward range. See class definition for details.
55  template <bool const_range>
56  class basic_iterator;
57 
58 public:
62  chunk_view()
63  requires std::default_initializable<urng_t>
64  = default;
65  chunk_view(chunk_view const & rhs) = default;
66  chunk_view(chunk_view && rhs) = default;
67  chunk_view & operator=(chunk_view const & rhs) = default;
68  chunk_view & operator=(chunk_view && rhs) = default;
69  ~chunk_view() = default;
70 
75  constexpr explicit chunk_view(urng_t urng, std::ranges::range_difference_t<urng_t> const size_of_chunk) :
76  urange{std::move(urng)},
77  chunk_size{size_of_chunk}
78  {}
80 
97  auto begin() noexcept
98  {
99  if constexpr (std::ranges::forward_range<urng_t>)
100  return basic_iterator<false>{std::ranges::begin(urange), std::ranges::end(urange), chunk_size};
101  else
102  return basic_input_iterator<false>{std::ranges::begin(urange), std::ranges::end(urange), chunk_size};
103  }
104 
106  auto begin() const noexcept
108  {
109  if constexpr (std::ranges::forward_range<urng_t>)
110  return basic_iterator<true>{std::ranges::cbegin(urange), std::ranges::cend(urange), chunk_size};
111  else
112  return basic_input_iterator<true>{std::ranges::cbegin(urange), std::ranges::cend(urange), chunk_size};
113  }
114 
130  auto end() noexcept
131  {
132  return std::ranges::end(urange);
133  }
134 
136  auto end() const noexcept
138  {
139  return std::ranges::cend(urange);
140  }
142 
146  auto size()
147  requires std::ranges::sized_range<urng_t>
148  {
149  using size_type = std::ranges::range_size_t<urng_t>;
150  return static_cast<size_type>((std::ranges::size(urange) + chunk_size - 1) / chunk_size); // round up
151  }
152 
154  auto size() const
155  requires std::ranges::sized_range<urng_t const>
156  {
157  using size_type = std::ranges::range_size_t<urng_t const>;
158  return static_cast<size_type>((std::ranges::size(urange) + chunk_size - 1) / chunk_size); // round up
159  }
160 };
161 
163 template <std::ranges::range rng_t>
164 chunk_view(rng_t &&, std::ranges::range_difference_t<rng_t> const &) -> chunk_view<seqan3::detail::all_t<rng_t>>;
165 
166 // ---------------------------------------------------------------------------------------------------------------------
167 // chunk_view iterators (basic_input_iterator and basic_iterator)
168 // ---------------------------------------------------------------------------------------------------------------------
169 
187 template <std::ranges::input_range urng_t>
188  requires std::ranges::view<urng_t>
189 template <bool const_range>
190 class chunk_view<urng_t>::basic_input_iterator :
191  public maybe_iterator_category<maybe_const_iterator_t<const_range, urng_t>>
192 {
193 private:
195  using urng_it_t = maybe_const_iterator_t<const_range, urng_t>;
196 
198  using sentinel_t = maybe_const_sentinel_t<const_range, urng_t>;
199 
212  template <typename outer_it_type>
213  class input_helper_iterator : public urng_it_t
214  {
215  public:
219  constexpr input_helper_iterator() = default;
220  constexpr input_helper_iterator(input_helper_iterator const &) = default;
221  constexpr input_helper_iterator(input_helper_iterator &&) = default;
222  constexpr input_helper_iterator & operator=(input_helper_iterator const &) = default;
223  constexpr input_helper_iterator & operator=(input_helper_iterator &&) = default;
224  ~input_helper_iterator() = default;
225 
227  constexpr explicit input_helper_iterator(outer_it_type & outer_iterator, urng_it_t urng_it) :
228  urng_it_t(std::move(urng_it)),
229  outer_it(std::addressof(outer_iterator))
230  {}
231 
233  constexpr explicit input_helper_iterator(urng_it_t urng_it) : urng_it_t(std::move(urng_it))
234  {}
236 
238  input_helper_iterator & operator++() noexcept
239  {
240  --(outer_it->remaining);
241  urng_it_t::operator++();
242  return *this;
243  }
244 
246  input_helper_iterator operator++(int) noexcept
247  {
248  input_helper_iterator tmp{*this};
249  ++(*this);
250  return tmp;
251  }
252 
254  bool operator==(sentinel_t const & /* rhs */) noexcept
255  {
256  return this->outer_it->remaining == 0u || this->outer_it->urng_begin == this->outer_it->urng_end;
257  }
258 
260  outer_it_type * outer_it{nullptr};
261  };
262 
264  using helper_it_t = input_helper_iterator<basic_input_iterator>;
265 
266  // befriend the iterator on a const range
267  template <bool other_const_range>
268  friend class basic_input_iterator;
269 
270  // befriend the inner iterator type
271  template <typename outer_it_type>
272  friend class input_helper_iterator;
273 
274 public:
279  using difference_type = typename std::iter_difference_t<urng_it_t>;
281  using value_type = std::ranges::subrange<helper_it_t, sentinel_t>;
283  using pointer = void;
285  using reference = value_type;
287  using iterator_concept = std::input_iterator_tag;
289 
293  constexpr basic_input_iterator() = default;
294  constexpr basic_input_iterator(basic_input_iterator const &) = default;
295  constexpr basic_input_iterator(basic_input_iterator &&) = default;
296  constexpr basic_input_iterator & operator=(basic_input_iterator const &) = default;
297  constexpr basic_input_iterator & operator=(basic_input_iterator &&) = default;
298  ~basic_input_iterator() = default;
299 
301  constexpr explicit basic_input_iterator(basic_input_iterator<!const_range> it) noexcept
302  requires const_range
303  :
304  chunk_size{std::move(it.chunk_size)},
305  remaining{std::move(it.remaining)},
306  urng_begin{std::move(it.urng_begin)},
307  urng_end{std::move(it.urng_end)},
308  current_chunk{std::move(it.current_chunk)}
309  {}
310 
322  constexpr explicit basic_input_iterator(urng_it_t it_begin,
323  sentinel_t it_end,
324  std::ranges::range_difference_t<urng_t> const size_of_chunk) :
325  chunk_size{size_of_chunk},
326  remaining{size_of_chunk},
327  urng_begin{std::move(it_begin)},
328  urng_end{std::move(it_end)}
329  {
330  current_chunk = std::ranges::subrange<helper_it_t, sentinel_t>{helper_it_t{*this, it_begin}, it_end};
331  }
333 
337 
339  friend constexpr bool operator==(basic_input_iterator const & lhs, sentinel_t const & rhs) noexcept
340  {
341  return lhs.urng_begin == rhs;
342  }
343 
345  friend constexpr bool operator==(basic_input_iterator const & lhs, basic_input_iterator const & rhs) noexcept
346  {
347  return (lhs.urng_begin == rhs.urng_begin) && (lhs.remaining == rhs.remaining);
348  }
349 
351  constexpr basic_input_iterator & operator++() noexcept
352  {
353  while (remaining > 0u && urng_begin != urng_end) // if chunk was not fully consumed and range is not at end
354  {
355  ++urng_begin;
356  --remaining;
357  }
358  current_chunk = std::ranges::subrange<helper_it_t, sentinel_t>{helper_it_t{*this, urng_begin}, urng_end};
359  remaining = chunk_size;
360  return *this;
361  }
362 
364  constexpr basic_input_iterator operator++(int) noexcept
365  {
366  basic_input_iterator tmp{*this};
367  ++(*this);
368  return tmp;
369  }
370 
372  constexpr value_type operator*() const noexcept
373  {
374  return current_chunk;
375  }
376 
377 private:
379  std::ranges::range_difference_t<urng_t> chunk_size;
380 
382  std::ranges::range_difference_t<urng_t> remaining;
383 
385  urng_it_t urng_begin;
386 
388  sentinel_t urng_end;
389 
391  value_type current_chunk;
392 };
393 
410 template <std::ranges::input_range urng_t>
411  requires std::ranges::view<urng_t>
412 template <bool const_range>
413 class chunk_view<urng_t>::basic_iterator : public maybe_iterator_category<maybe_const_iterator_t<const_range, urng_t>>
414 {
415 private:
417  using it_t = maybe_const_iterator_t<const_range, urng_t>;
419  using sentinel_t = maybe_const_sentinel_t<const_range, urng_t>;
420 
421  // befriend the iterator on a const range
422  template <bool other_const_range>
423  friend class basic_iterator;
424 
425 public:
430  using difference_type = typename std::iter_difference_t<it_t>;
432  using value_type = std::ranges::subrange<it_t, it_t>;
434  using pointer = void;
436  using reference = value_type;
438  using iterator_concept = std::conditional_t<std::contiguous_iterator<it_t>,
440  detail::iterator_concept_tag_t<it_t>>;
442 
446  constexpr basic_iterator() = default;
447  constexpr basic_iterator(basic_iterator const &) = default;
448  constexpr basic_iterator(basic_iterator &&) = default;
449  constexpr basic_iterator & operator=(basic_iterator const &) = default;
450  constexpr basic_iterator & operator=(basic_iterator &&) = default;
451  ~basic_iterator() = default;
452 
454  constexpr basic_iterator(basic_iterator<!const_range> const & it) noexcept
455  requires const_range
456  :
457  chunk_size{std::move(it.chunk_size)},
458  urng_begin{std::move(it.urng_begin)},
459  urng_end{std::move(it.urng_end)},
460  current_chunk{std::move(it.current_chunk)}
461  {}
462 
474  constexpr explicit basic_iterator(it_t it_start,
475  sentinel_t it_end,
476  std::ranges::range_difference_t<urng_t> const size_of_chunk) :
477  chunk_size{size_of_chunk},
478  urng_begin{std::move(it_start)},
479  urng_end{std::move(it_end)}
480  {
481  current_chunk = value_type{it_start, get_next_end_of_chunk(it_start)};
482  }
484 
488 
490  friend constexpr bool operator==(basic_iterator const & lhs, sentinel_t const & rhs) noexcept
491  {
492  return lhs.current_chunk.begin() == rhs;
493  }
494 
496  friend constexpr bool operator==(basic_iterator const & lhs, basic_iterator const & rhs) noexcept
497  {
498  return (lhs.current_chunk.begin() == rhs.current_chunk.begin()) && (lhs.chunk_size == rhs.chunk_size);
499  }
500 
502  friend constexpr bool operator!=(basic_iterator const & lhs, sentinel_t const & rhs) noexcept
503  {
504  return !(lhs == rhs);
505  }
506 
508  friend constexpr bool operator!=(basic_iterator const & lhs, basic_iterator const & rhs) noexcept
509  {
510  return !(lhs == rhs);
511  }
512 
514  friend constexpr bool operator<(basic_iterator const & lhs, basic_iterator const & rhs) noexcept
515  {
516  return lhs.current_chunk.begin() < rhs.current_chunk.begin();
517  }
518 
520  friend constexpr bool operator>(basic_iterator const & lhs, basic_iterator const & rhs) noexcept
521  {
522  return lhs.current_chunk.begin() > rhs.current_chunk.begin();
523  }
524 
526  friend constexpr bool operator<=(basic_iterator const & lhs, basic_iterator const & rhs) noexcept
527  {
528  return lhs.current_chunk.begin() <= rhs.current_chunk.begin();
529  }
530 
532  friend constexpr bool operator>=(basic_iterator const & lhs, basic_iterator const & rhs) noexcept
533  {
534  return lhs.current_chunk.begin() >= rhs.current_chunk.begin();
535  }
536 
538 
540  constexpr basic_iterator & operator++() noexcept
541  {
542  current_chunk = value_type{current_chunk.end(), get_next_end_of_chunk(current_chunk.end())};
543  return *this;
544  }
545 
547  basic_iterator operator++(int) noexcept
548  {
549  basic_iterator tmp{*this};
550  ++(*this);
551  return tmp;
552  }
553 
557  constexpr basic_iterator & operator--() noexcept
558  requires std::bidirectional_iterator<it_t>
559  {
560  current_chunk = value_type{get_former_start_of_chunk(current_chunk.begin()), current_chunk.begin()};
561  return *this;
562  }
563 
567  constexpr basic_iterator operator--(int) noexcept
568  requires std::bidirectional_iterator<it_t>
569  {
570  basic_iterator tmp{*this};
571  --(*this);
572  return tmp;
573  }
574 
578  constexpr basic_iterator & operator+=(difference_type const skip) noexcept
579  requires std::random_access_iterator<it_t>
580  {
581  auto new_start_it = current_chunk.begin() + (chunk_size * skip);
582  current_chunk = value_type{new_start_it, get_next_end_of_chunk(new_start_it)};
583  return *this;
584  }
585 
589  constexpr basic_iterator operator+(difference_type const skip) const noexcept
590  requires std::random_access_iterator<it_t>
591  {
592  basic_iterator tmp{*this};
593  return tmp += skip;
594  }
595 
599  friend constexpr basic_iterator operator+(difference_type const skip, basic_iterator const & it) noexcept
600  requires std::random_access_iterator<it_t>
601  {
602  return it + skip;
603  }
604 
608  constexpr basic_iterator & operator-=(difference_type const skip) noexcept
609  requires std::random_access_iterator<it_t>
610  {
611  auto new_start_it = current_chunk.begin() - (chunk_size * skip);
612  current_chunk = value_type{new_start_it, get_next_end_of_chunk(new_start_it)};
613  return *this;
614  }
615 
620  constexpr basic_iterator operator-(difference_type const skip) const noexcept
621  requires std::random_access_iterator<it_t>
622  {
623  basic_iterator tmp{*this};
624  return tmp -= skip;
625  }
626 
630  friend constexpr basic_iterator operator-(difference_type const skip, basic_iterator const & it) noexcept
631  requires std::random_access_iterator<it_t>
632  {
633  return it - skip;
634  }
635 
640  friend constexpr difference_type operator-(basic_iterator const & lhs, basic_iterator const & rhs) noexcept
641  requires std::sized_sentinel_for<it_t, it_t>
642  {
643  return static_cast<difference_type>((lhs.current_chunk.begin() - rhs.current_chunk.begin()) / lhs.chunk_size);
644  }
645 
649  friend constexpr difference_type operator-(sentinel_t const & /* lhs */, basic_iterator const & rhs) noexcept
650  requires std::sized_sentinel_for<sentinel_t, it_t>
651  {
652  return static_cast<difference_type>((rhs.urng_end - rhs.current_chunk.begin() + rhs.chunk_size - 1)
653  / rhs.chunk_size);
654  }
655 
659  friend constexpr difference_type operator-(basic_iterator const & lhs, sentinel_t const & rhs) noexcept
660  requires std::sized_sentinel_for<sentinel_t, it_t>
661  {
662  return -(rhs - lhs);
663  }
664 
668  constexpr reference operator[](difference_type const n) const
669  requires std::random_access_iterator<it_t>
670  {
671  return *(*this + n);
672  }
673 
675  constexpr value_type operator*() const noexcept
676  {
677  return current_chunk;
678  }
679 
680 private:
682  std::ranges::range_difference_t<urng_t> chunk_size;
683 
685  it_t urng_begin;
686 
688  sentinel_t urng_end;
689 
691  value_type current_chunk;
692 
694  constexpr it_t get_next_end_of_chunk(it_t start_of_chunk) const
695  {
696  // Very similar to `return std::ranges::next(start_of_chunk, chunk_size, urng_end);`.
697  // However, the STL checks that the direction of chunk_size and urng_end are the same for sized_sentinels when
698  // -D_GLIBCXX_ASSERTIONS is enabled.
699  // If start_of_chunk was moved past urng_end, we should constrain it.
700  // =========X===========Y============
701  // ^ ^
702  // urng_end new_start_it
703  // <----------- // direction from iterator to bound
704  // ---------> // direction from chunk_size
705  // See https://eel.is/c++draft/range.iter.op.advance (next just takes and returns a copy of the iterator)
706  // Note: n is chunk_size and always positive.
707  if constexpr (std::sized_sentinel_for<sentinel_t, it_t>) // We can check whether we can jump.
708  {
709  if (chunk_size >= std::abs(urng_end - start_of_chunk)) // Remaining range smaller than chunk_size
710  return std::ranges::next(start_of_chunk, urng_end); // Returns it_t which is equal to urng_end
711  else // We can jump chunk_size many times
712  return std::ranges::next(start_of_chunk, chunk_size);
713  }
714  else // We need to increment one by one to not cross urng_end.
715  {
716  for (std::ranges::range_difference_t<urng_t> increments{};
717  increments != chunk_size && start_of_chunk != urng_end;
718  ++increments)
719  {
720  ++start_of_chunk;
721  }
722 
723  return start_of_chunk;
724  }
725  }
726 
728  constexpr it_t get_former_start_of_chunk(it_t end_of_chunk) const
729  {
730  // Very similar to `return std::ranges::prev(end_of_chunk, chunk_size, urng_begin);`.
731  // However, the STL checks that the direction of chunk_size and urng_end are the same for sized_sentinels when
732  // -D_GLIBCXX_ASSERTIONS is enabled.
733  // If end_of_chunk was moved before urng_begin, we should constrain it.
734  // =========X===========Y============
735  // ^ ^
736  // end_of_chunk urng_begin
737  // <--------- // direction from chunk_size
738  // ---------> // direction from iterator to bound
739  // See https://eel.is/c++draft/range.iter.op.advance (prev(i, n, bound) is equal to advance(i, -n, bound))
740  // Note: n is chunk_size and always positive.
741  if constexpr (std::sized_sentinel_for<sentinel_t, it_t>) // We can check whether we can jump.
742  {
743  if (chunk_size >= std::abs(urng_begin - end_of_chunk)) // Remaining range smaller than chunk_size
744  return urng_begin;
745  else // We can jump chunk_size many times
746  return std::ranges::prev(end_of_chunk, chunk_size);
747  }
748  else // We need to decrement one by one to not cross urng_begin.
749  {
750  for (std::ranges::range_difference_t<urng_t> decrements{};
751  decrements != chunk_size && end_of_chunk != urng_begin;
752  ++decrements)
753  {
754  --end_of_chunk;
755  }
756 
757  return end_of_chunk;
758  }
759  }
760 };
761 
762 // ---------------------------------------------------------------------------------------------------------------------
763 // chunk_fn (adaptor definition)
764 // ---------------------------------------------------------------------------------------------------------------------
765 
768 struct chunk_fn
769 {
771  constexpr auto operator()(std::ptrdiff_t const chunk_size) const
772  {
773  return adaptor_from_functor{*this, chunk_size};
774  }
775 
781  template <std::ranges::range urng_t>
782  constexpr auto operator()(urng_t && urange, std::ranges::range_difference_t<urng_t> const chunk_size) const
783  {
784  static_assert(std::ranges::input_range<urng_t>,
785  "The range parameter to views::chunk must model std::ranges::input_range.");
786 
787  return chunk_view{std::forward<urng_t>(urange), chunk_size};
788  }
789 };
790 
791 } // namespace seqan3::detail
792 
793 namespace seqan3::views
794 {
835 inline constexpr auto chunk = detail::chunk_fn{};
836 
837 } // namespace seqan3::views
Provides seqan3::detail::adaptor_from_functor.
T addressof(T... args)
Provides seqan3::detail::all.
Core alphabet concept and free function/type trait wrappers.
T begin(T... args)
Provides various transformation traits used by the range module.
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 chunk
Divide a range in chunks.
Definition: chunk.hpp:835
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)
Provides platform and dependency checks.
The <ranges> header from C++20's standard library.
Additional non-standard concepts for ranges.