v3/view/chunk.hpp

0001 /// \file
0002 // Range v3 library
0003 //
0004 //  Copyright Eric Niebler 2013-present
0005 //
0006 //  Use, modification and distribution is subject to the
0007 //  Boost Software License, Version 1.0. (See accompanying
0008 //  file LICENSE_1_0.txt or copy at
0009 //  http://www.boost.org/LICENSE_1_0.txt)
0010 //
0011 // Project home: https://github.com/ericniebler/range-v3
0012 //
0013
0014 #ifndef RANGES_V3_VIEW_CHUNK_HPP
0015 #define RANGES_V3_VIEW_CHUNK_HPP
0016
0017 #include <limits>
0018 #include <utility>
0019
0020 #include <meta/meta.hpp>
0021
0022 #include <range/v3/range_fwd.hpp>
0023
0024 #include <range/v3/functional/bind_back.hpp>
0025 #include <range/v3/iterator/default_sentinel.hpp>
0026 #include <range/v3/iterator/operations.hpp>
0027 #include <range/v3/range/access.hpp>
0028 #include <range/v3/range/concepts.hpp>
0029 #include <range/v3/range/traits.hpp>
0030 #include <range/v3/utility/box.hpp>
0031 #include <range/v3/utility/optional.hpp> // for non_propagating_cache
0032 #include <range/v3/utility/static_const.hpp>
0033 #include <range/v3/view/adaptor.hpp>
0034 #include <range/v3/view/all.hpp>
0035 #include <range/v3/view/facade.hpp>
0036 #include <range/v3/view/take.hpp>
0037 #include <range/v3/view/view.hpp>
0038
0039 #include <range/v3/detail/prologue.hpp>
0040
0041 namespace ranges
0042 {
0043     /// \cond
0044     namespace detail
0045     {
0046         template<typename Rng, bool Const>
0047         constexpr bool can_sized_sentinel_() noexcept
0048         {
0049             using I = iterator_t<meta::const_if_c<Const, Rng>>;
0050             return (bool)sized_sentinel_for<I, I>;
0051         }
0052
0053         template<typename T>
0054         struct zero
0055         {
0056             zero() = default;
0057             constexpr explicit zero(T const &) noexcept
0058             {}
0059             constexpr zero & operator=(T const &) noexcept
0060             {
0061                 return *this;
0062             }
0063             constexpr zero const & operator=(T const &) const noexcept
0064             {
0065                 return *this;
0066             }
0067             constexpr operator T() const
0068             {
0069                 return T(0);
0070             }
0071             constexpr T exchange(T const &) const
0072             {
0073                 return T(0);
0074             }
0075         };
0076     } // namespace detail
0077     /// \endcond
0078
0079     /// \addtogroup group-views
0080     /// @{
0081     template<typename Rng, bool IsForwardRange>
0082     struct chunk_view_
0083       : view_adaptor<chunk_view_<Rng, IsForwardRange>, Rng,
0084                      is_finite<Rng>::value ? finite : range_cardinality<Rng>::value>
0085     {
0086     private:
0087         friend range_access;
0088         CPP_assert(forward_range<Rng>);
0089
0090         template<bool Const>
0091         using offset_t =
0092             meta::if_c<bidirectional_range<meta::const_if_c<Const, Rng>> ||
0093                            detail::can_sized_sentinel_<Rng, Const>(),
0094                        range_difference_t<Rng>, detail::zero<range_difference_t<Rng>>>;
0095
0096         range_difference_t<Rng> n_ = 0;
0097
0098         template<bool Const>
0099         struct RANGES_EMPTY_BASES adaptor
0100           : adaptor_base
0101           , private box<offset_t<Const>>
0102         {
0103         private:
0104             friend adaptor<!Const>;
0105             using CRng = meta::const_if_c<Const, Rng>;
0106
0107             range_difference_t<CRng> n_;
0108             sentinel_t<CRng> end_;
0109
0110             constexpr offset_t<Const> const & offset() const
0111             {
0112                 offset_t<Const> const & result = this->box<offset_t<Const>>::get();
0113                 RANGES_EXPECT(0 <= result && result < n_);
0114                 return result;
0115             }
0116             constexpr offset_t<Const> & offset()
0117             {
0118                 return const_cast<offset_t<Const> &>(
0119                     const_cast<adaptor const &>(*this).offset());
0120             }
0121
0122         public:
0123             adaptor() = default;
0124             constexpr adaptor(meta::const_if_c<Const, chunk_view_> * cv)
0125               : box<offset_t<Const>>{0}
0126               , n_((RANGES_EXPECT(0 < cv->n_), cv->n_))
0127               , end_(ranges::end(cv->base()))
0128             {}
0129             template(bool Other)(
0130                 requires Const AND CPP_NOT(Other)) //
0131             constexpr adaptor(adaptor<Other> that)
0132               : box<offset_t<Const>>(that.offset())
0133               , n_(that.n_)
0134               , end_(that.end_)
0135             {}
0136             constexpr auto read(iterator_t<CRng> const & it) const
0137                 -> decltype(views::take(make_subrange(it, end_), n_))
0138             {
0139                 RANGES_EXPECT(it != end_);
0140                 RANGES_EXPECT(0 == offset());
0141                 return views::take(make_subrange(it, end_), n_);
0142             }
0143             constexpr void next(iterator_t<CRng> & it)
0144             {
0145                 RANGES_EXPECT(it != end_);
0146                 RANGES_EXPECT(0 == offset());
0147                 offset() = ranges::advance(it, n_, end_);
0148             }
0149             CPP_member
0150             constexpr auto prev(iterator_t<CRng> & it) //
0151                 -> CPP_ret(void)(
0152                     requires bidirectional_range<CRng>)
0153             {
0154                 ranges::advance(it, -n_ + offset());
0155                 offset() = 0;
0156             }
0157             CPP_member
0158             constexpr auto distance_to(iterator_t<CRng> const & here,
0159                                        iterator_t<CRng> const & there,
0160                                        adaptor const & that) const
0161                 -> CPP_ret(range_difference_t<Rng>)(
0162                     requires (detail::can_sized_sentinel_<Rng, Const>()))
0163             {
0164                 auto const delta = (there - here) + (that.offset() - offset());
0165                 // This can fail for cyclic base ranges when the chunk size does not
0166                 // divide the cycle length. Such iterator pairs are NOT in the domain of
0167                 // -.
0168                 RANGES_ENSURE(0 == delta % n_);
0169                 return delta / n_;
0170             }
0171             CPP_member
0172             constexpr auto advance(iterator_t<CRng> & it, range_difference_t<Rng> n) //
0173                 -> CPP_ret(void)(
0174                     requires random_access_range<CRng>)
0175             {
0176                 using Limits = std::numeric_limits<range_difference_t<CRng>>;
0177                 if(0 < n)
0178                 {
0179                     RANGES_EXPECT(0 == offset());
0180                     RANGES_EXPECT(n <= Limits::max() / n_);
0181                     auto const remainder = ranges::advance(it, n * n_, end_) % n_;
0182                     RANGES_EXPECT(0 <= remainder && remainder < n_);
0183                     offset() = remainder;
0184                 }
0185                 else if(0 > n)
0186                 {
0187                     RANGES_EXPECT(n >= Limits::min() / n_);
0188                     ranges::advance(it, n * n_ + offset());
0189                     offset() = 0;
0190                 }
0191             }
0192         };
0193
0194         constexpr adaptor<simple_view<Rng>()> begin_adaptor()
0195         {
0196             return adaptor<simple_view<Rng>()>{this};
0197         }
0198         CPP_member
0199         constexpr auto begin_adaptor() const //
0200             -> CPP_ret(adaptor<true>)(
0201                 requires forward_range<Rng const>)
0202         {
0203             return adaptor<true>{this};
0204         }
0205         template<typename Size>
0206         constexpr Size size_(Size base_size) const
0207         {
0208             auto const n = static_cast<Size>(n_);
0209             return base_size / n + (0 != (base_size % n));
0210         }
0211
0212     public:
0213         chunk_view_() = default;
0214         constexpr chunk_view_(Rng rng, range_difference_t<Rng> n)
0215           : chunk_view_::view_adaptor(detail::move(rng))
0216           , n_((RANGES_EXPECT(0 < n), n))
0217         {}
0218         CPP_auto_member
0219         constexpr auto CPP_fun(size)()(const
0220             requires sized_range<Rng const>)
0221         {
0222             return size_(ranges::size(this->base()));
0223         }
0224         CPP_auto_member
0225         constexpr auto CPP_fun(size)()(
0226             requires sized_range<Rng>)
0227         {
0228             return size_(ranges::size(this->base()));
0229         }
0230     };
0231
0232     template<typename Rng>
0233     struct chunk_view_<Rng, false>
0234       : view_facade<chunk_view_<Rng, false>,
0235                     is_finite<Rng>::value ? finite : range_cardinality<Rng>::value>
0236     {
0237     private:
0238         friend range_access;
0239         CPP_assert(input_range<Rng> && !forward_range<Rng>);
0240
0241         using iter_cache_t = detail::non_propagating_cache<iterator_t<Rng>>;
0242
0243         Rng base_;
0244         range_difference_t<Rng> n_;
0245         range_difference_t<Rng> remainder_;
0246         mutable iter_cache_t it_cache_;
0247
0248         constexpr iterator_t<Rng> & it() noexcept
0249         {
0250             return *it_cache_;
0251         }
0252         constexpr iterator_t<Rng> const & it() const noexcept
0253         {
0254             return *it_cache_;
0255         }
0256
0257         struct outer_cursor
0258         {
0259         private:
0260             struct inner_view : view_facade<inner_view, finite>
0261             {
0262             private:
0263                 friend range_access;
0264
0265                 using value_type = range_value_t<Rng>;
0266
0267                 chunk_view_ * rng_ = nullptr;
0268
0269                 constexpr bool done() const noexcept
0270                 {
0271                     RANGES_EXPECT(rng_);
0272                     return rng_->remainder_ == 0;
0273                 }
0274                 constexpr bool equal(default_sentinel_t) const noexcept
0275                 {
0276                     return done();
0277                 }
0278                 constexpr iter_reference_t<iterator_t<Rng>> read() const
0279                 {
0280                     RANGES_EXPECT(!done());
0281                     return *rng_->it();
0282                 }
0283                 constexpr iter_rvalue_reference_t<iterator_t<Rng>> move() const
0284                 {
0285                     RANGES_EXPECT(!done());
0286                     return ranges::iter_move(rng_->it());
0287                 }
0288                 constexpr void next()
0289                 {
0290                     RANGES_EXPECT(!done());
0291                     ++rng_->it();
0292                     --rng_->remainder_;
0293                     if(rng_->remainder_ != 0 && rng_->it() == ranges::end(rng_->base_))
0294                         rng_->remainder_ = 0;
0295                 }
0296                 CPP_member
0297                 constexpr auto distance_to(default_sentinel_t) const
0298                     -> CPP_ret(range_difference_t<Rng>)(
0299                         requires sized_sentinel_for<sentinel_t<Rng>, iterator_t<Rng>>)
0300                 {
0301                     RANGES_EXPECT(rng_);
0302                     auto const d = ranges::end(rng_->base_) - rng_->it();
0303                     return ranges::min(d, rng_->remainder_);
0304                 }
0305
0306             public:
0307                 inner_view() = default;
0308                 constexpr explicit inner_view(chunk_view_ * view) noexcept
0309                   : rng_{view}
0310                 {}
0311                 CPP_auto_member
0312                 constexpr auto CPP_fun(size)()(
0313                     requires sized_sentinel_for<sentinel_t<Rng>, iterator_t<Rng>>)
0314                 {
0315                     using size_type = detail::iter_size_t<iterator_t<Rng>>;
0316                     return static_cast<size_type>(distance_to(default_sentinel_t{}));
0317                 }
0318             };
0319
0320             chunk_view_ * rng_ = nullptr;
0321
0322         public:
0323             using value_type = inner_view;
0324
0325             outer_cursor() = default;
0326             constexpr explicit outer_cursor(chunk_view_ * view) noexcept
0327               : rng_{view}
0328             {}
0329             constexpr inner_view read() const
0330             {
0331                 RANGES_EXPECT(!done());
0332                 return inner_view{rng_};
0333             }
0334             constexpr bool done() const
0335             {
0336                 RANGES_EXPECT(rng_);
0337                 return rng_->it() == ranges::end(rng_->base_) && rng_->remainder_ != 0;
0338             }
0339             constexpr bool equal(default_sentinel_t) const
0340             {
0341                 return done();
0342             }
0343             constexpr void next()
0344             {
0345                 RANGES_EXPECT(!done());
0346                 ranges::advance(rng_->it(), rng_->remainder_, ranges::end(rng_->base_));
0347                 rng_->remainder_ = rng_->n_;
0348             }
0349             CPP_member
0350             constexpr auto distance_to(default_sentinel_t) const
0351                 -> CPP_ret(range_difference_t<Rng>)(
0352                     requires sized_sentinel_for<sentinel_t<Rng>, iterator_t<Rng>>)
0353             {
0354                 RANGES_EXPECT(rng_);
0355                 auto d = ranges::end(rng_->base_) - rng_->it();
0356                 if(d < rng_->remainder_)
0357                     return 1;
0358
0359                 d -= rng_->remainder_;
0360                 d = (d + rng_->n_ - 1) / rng_->n_;
0361                 d += (rng_->remainder_ != 0);
0362                 return d;
0363             }
0364         };
0365
0366         constexpr outer_cursor begin_cursor() noexcept
0367         {
0368             it_cache_ = ranges::begin(base_);
0369             return outer_cursor{this};
0370         }
0371         template<typename Size>
0372         constexpr Size size_(Size base_size) const
0373         {
0374             auto const n = static_cast<Size>(this->n_);
0375             return base_size / n + (0 != base_size % n);
0376         }
0377
0378     public:
0379         chunk_view_() = default;
0380         constexpr chunk_view_(Rng rng, range_difference_t<Rng> n)
0381           : base_(detail::move(rng))
0382           , n_((RANGES_EXPECT(0 < n), n))
0383           , remainder_(n)
0384           , it_cache_{nullopt}
0385         {}
0386         CPP_auto_member
0387         constexpr auto CPP_fun(size)()(const
0388             requires sized_range<Rng const>)
0389         {
0390             return size_(ranges::size(base_));
0391         }
0392         CPP_auto_member
0393         constexpr auto CPP_fun(size)()(
0394             requires sized_range<Rng>)
0395         {
0396             return size_(ranges::size(base_));
0397         }
0398         Rng base() const
0399         {
0400             return base_;
0401         }
0402     };
0403
0404     template<typename Rng>
0405     struct chunk_view : chunk_view_<Rng, (bool)forward_range<Rng>>
0406     {
0407         chunk_view() = default;
0408         constexpr chunk_view(Rng rng, range_difference_t<Rng> n)
0409           : chunk_view_<Rng, (bool)forward_range<Rng>>(static_cast<Rng &&>(rng), n)
0410         {}
0411     };
0412
0413     // Need to keep extra state for input_range, but forward_range is transparent
0414     template<typename Rng>
0415     RANGES_INLINE_VAR constexpr bool enable_borrowed_range<chunk_view<Rng>> =
0416         enable_borrowed_range<Rng> && forward_range<Rng>;
0417
0418 #if RANGES_CXX_DEDUCTION_GUIDES >= RANGES_CXX_DEDUCTION_GUIDES_17
0419     template<typename Rng>
0420     chunk_view(Rng &&, range_difference_t<Rng>)
0421         -> chunk_view<views::all_t<Rng>>;
0422 #endif
0423
0424     namespace views
0425     {
0426         // In:  range<T>
0427         // Out: range<range<T>>, where each inner range has $n$ elements.
0428         //                       The last range may have fewer.
0429         struct chunk_base_fn
0430         {
0431             template(typename Rng)(
0432                 requires viewable_range<Rng> AND input_range<Rng>)
0433             constexpr chunk_view<all_t<Rng>> //
0434             operator()(Rng && rng, range_difference_t<Rng> n) const
0435             {
0436                 return {all(static_cast<Rng &&>(rng)), n};
0437             }
0438         };
0439
0440         struct chunk_fn : chunk_base_fn
0441         {
0442             using chunk_base_fn::operator();
0443
0444             template(typename Int)(
0445                 requires detail::integer_like_<Int>)
0446             constexpr auto operator()(Int n) const
0447             {
0448                 return make_view_closure(bind_back(chunk_base_fn{}, n));
0449             }
0450         };
0451
0452         /// \relates chunk_fn
0453         /// \ingroup group-views
0454         RANGES_INLINE_VARIABLE(chunk_fn, chunk)
0455     } // namespace views
0456     /// @}
0457 } // namespace ranges
0458
0459 #include <range/v3/detail/epilogue.hpp>
0460 #include <range/v3/detail/satisfy_boost_range.hpp>
0461 RANGES_SATISFY_BOOST_RANGE(::ranges::chunk_view)
0462
0463 #endif