SeqAn3 3.2.0
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
24
25namespace seqan3::detail
26{
27// ---------------------------------------------------------------------------------------------------------------------
28// chunk_view class
29// ---------------------------------------------------------------------------------------------------------------------
30
39template <std::ranges::input_range urng_t>
40 requires std::ranges::view<urng_t>
41class chunk_view : public std::ranges::view_interface<chunk_view<urng_t>>
42{
43private:
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
58public:
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
107 requires const_iterable_range<urng_t>
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
137 requires const_iterable_range<urng_t>
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
163template <std::ranges::range rng_t>
164chunk_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
187template <std::ranges::input_range urng_t>
188 requires std::ranges::view<urng_t>
189template <bool const_range>
190class chunk_view<urng_t>::basic_input_iterator :
191 public maybe_iterator_category<maybe_const_iterator_t<const_range, urng_t>>
192{
193private:
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
274public:
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
377private:
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
410template <std::ranges::input_range urng_t>
411 requires std::ranges::view<urng_t>
412template <bool const_range>
413class chunk_view<urng_t>::basic_iterator : public maybe_iterator_category<maybe_const_iterator_t<const_range, urng_t>>
414{
415private:
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
425public:
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;
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
680private:
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
768struct 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
793namespace seqan3::views
794{
835inline 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)
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.