v3/view/partial_sum.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_PARTIAL_SUM_HPP
0015 #define RANGES_V3_VIEW_PARTIAL_SUM_HPP
0016
0017 #include <iterator>
0018 #include <type_traits>
0019 #include <utility>
0020
0021 #include <meta/meta.hpp>
0022
0023 #include <range/v3/range_fwd.hpp>
0024
0025 #include <range/v3/functional/arithmetic.hpp>
0026 #include <range/v3/functional/bind_back.hpp>
0027 #include <range/v3/functional/invoke.hpp>
0028 #include <range/v3/range/access.hpp>
0029 #include <range/v3/range/primitives.hpp>
0030 #include <range/v3/range/traits.hpp>
0031 #include <range/v3/utility/addressof.hpp>
0032 #include <range/v3/utility/semiregular_box.hpp>
0033 #include <range/v3/utility/static_const.hpp>
0034 #include <range/v3/view/all.hpp>
0035 #include <range/v3/view/facade.hpp>
0036 #include <range/v3/view/view.hpp>
0037
0038 #include <range/v3/detail/prologue.hpp>
0039
0040 namespace ranges
0041 {
0042     /// \cond
0043     namespace detail
0044     {
0045         // clang-format off
0046         /// \concept partial_sum_view_constraints_
0047         /// \brief The \c partial_sum_view_constraints_ concept
0048         template(typename Rng, typename Fun)(
0049         concept (partial_sum_view_constraints_)(Rng, Fun),
0050             copy_constructible<range_value_t<Rng>> AND
0051             constructible_from<range_value_t<Rng>, range_reference_t<Rng>> AND
0052             assignable_from<range_value_t<Rng> &, range_reference_t<Rng>> AND
0053             indirectly_binary_invocable_<Fun &, iterator_t<Rng>, iterator_t<Rng>> AND
0054             assignable_from<
0055                 range_value_t<Rng> &,
0056                 indirect_result_t<Fun &, iterator_t<Rng>, iterator_t<Rng>>>
0057         );
0058         /// \concept partial_sum_view_constraints
0059         /// \brief The \c partial_sum_view_constraints concept
0060         template<typename Rng, typename Fun>
0061         CPP_concept partial_sum_view_constraints =
0062             input_range<Rng> &&
0063             copy_constructible<Fun> &&
0064             CPP_concept_ref(detail::partial_sum_view_constraints_, Rng, Fun);
0065         // clang-format on
0066     } // namespace detail
0067     /// \endcond
0068
0069     /// \addtogroup group-views
0070     /// @{
0071     template<typename Rng, typename Fun>
0072     struct partial_sum_view
0073       : view_facade<partial_sum_view<Rng, Fun>, range_cardinality<Rng>::value>
0074     {
0075     private:
0076         friend range_access;
0077         CPP_assert(view_<Rng>);
0078         CPP_assert(detail::partial_sum_view_constraints<Rng, Fun>);
0079
0080         RANGES_NO_UNIQUE_ADDRESS Rng base_{};
0081         RANGES_NO_UNIQUE_ADDRESS semiregular_box_t<Fun> fun_;
0082
0083         template<bool IsConst>
0084         struct cursor
0085         {
0086         private:
0087             friend cursor<true>;
0088
0089             using Parent = meta::const_if_c<IsConst, partial_sum_view>;
0090             using Base = meta::const_if_c<IsConst, Rng>;
0091
0092             Parent * parent_ = nullptr;
0093             RANGES_NO_UNIQUE_ADDRESS iterator_t<Base> current_{};
0094             RANGES_NO_UNIQUE_ADDRESS semiregular_box_t<range_value_t<Rng>> sum_;
0095
0096         public:
0097             using single_pass = meta::bool_<single_pass_iterator_<iterator_t<Base>>>;
0098
0099             cursor() = default;
0100             constexpr explicit cursor(Parent * rng)
0101               : parent_{rng}
0102               , current_(ranges::begin(rng->base_))
0103             {
0104                 if(current_ != ranges::end(rng->base_))
0105                     sum_ = *current_;
0106             }
0107             template(bool Other)(
0108                 requires IsConst AND CPP_NOT(Other) AND
0109                 convertible_to<iterator_t<Rng> const &,
0110                                iterator_t<Base>>)
0111             constexpr cursor(cursor<Other> const & that)
0112               : parent_{that.parent_}
0113               , current_(that.current_)
0114               , sum_(that.sum_)
0115             {}
0116             constexpr range_value_t<Rng> read() const
0117             {
0118                 RANGES_EXPECT(current_ != ranges::end(parent_->base_));
0119                 return sum_;
0120             }
0121             constexpr void next()
0122             {
0123                 auto last = ranges::end(parent_->base_);
0124                 RANGES_EXPECT(current_ != last);
0125                 if(++current_ != last)
0126                 {
0127                     auto & sum = static_cast<range_value_t<Rng> &>(sum_);
0128                     using F = meta::const_if_c<IsConst, Fun>;
0129                     auto & f = static_cast<F &>(parent_->fun_);
0130                     sum = invoke(f, sum, *current_);
0131                 }
0132             }
0133             constexpr bool equal(default_sentinel_t) const
0134             {
0135                 return current_ == ranges::end(parent_->base_);
0136             }
0137             CPP_auto_member
0138             constexpr bool CPP_fun(equal)(cursor const & that)(const //
0139                 requires equality_comparable<iterator_t<Base>>)
0140             {
0141                 RANGES_EXPECT(parent_ == that.parent_);
0142                 return current_ == that.current_;
0143             }
0144         };
0145
0146         constexpr cursor<false> begin_cursor()
0147         {
0148             return cursor<false>{this};
0149         }
0150         template(typename CRng = Rng const)(
0151             requires detail::partial_sum_view_constraints<CRng, Fun const>)
0152         constexpr cursor<true> begin_cursor() const
0153         {
0154             return cursor<true>{this};
0155         }
0156
0157     public:
0158         partial_sum_view() = default;
0159         constexpr partial_sum_view(Rng rng, Fun fun) noexcept(
0160             std::is_nothrow_move_constructible<Rng>::value &&
0161                 std::is_nothrow_move_constructible<Fun>::value)
0162           : base_(std::move(rng))
0163           , fun_(std::move(fun))
0164         {}
0165         CPP_auto_member
0166         constexpr auto CPP_fun(size)()(
0167             requires sized_range<Rng>)
0168         {
0169             return ranges::size(base_);
0170         }
0171         CPP_auto_member
0172         constexpr auto CPP_fun(size)()(const //
0173             requires sized_range<Rng const>)
0174         {
0175             return ranges::size(base_);
0176         }
0177     };
0178
0179 #if RANGES_CXX_DEDUCTION_GUIDES >= RANGES_CXX_DEDUCTION_GUIDES_17
0180     template(typename Rng, typename Fun)(
0181         requires copy_constructible<Fun>)
0182     partial_sum_view(Rng &&, Fun)
0183         -> partial_sum_view<views::all_t<Rng>, Fun>;
0184 #endif
0185
0186     namespace views
0187     {
0188         struct partial_sum_base_fn
0189         {
0190             template(typename Rng, typename Fun = plus)(
0191                 requires detail::partial_sum_view_constraints<all_t<Rng>, Fun>)
0192             constexpr partial_sum_view<all_t<Rng>, Fun> //
0193             operator()(Rng && rng, Fun fun = {}) const
0194             {
0195                 return {all(static_cast<Rng &&>(rng)), std::move(fun)};
0196             }
0197         };
0198
0199         struct partial_sum_fn : partial_sum_base_fn
0200         {
0201             using partial_sum_base_fn::operator();
0202
0203             template(typename Fun)(
0204                 requires (!range<Fun>))
0205             constexpr auto operator()(Fun && fun) const
0206             {
0207                 return make_view_closure(
0208                     bind_back(partial_sum_base_fn{}, static_cast<Fun &&>(fun)));
0209             }
0210             template<typename Fun = plus>
0211             RANGES_DEPRECATED(
0212                 "Use \"ranges::views::partial_sum\" instead of "
0213                 "\"ranges::views::partial_sum()\".")
0214             constexpr auto
0215             operator()() const
0216             {
0217                 return make_view_closure(bind_back(partial_sum_base_fn{}, Fun{}));
0218             }
0219         };
0220
0221         /// \relates partial_sum_fn
0222         /// \ingroup group-views
0223         RANGES_INLINE_VARIABLE(view_closure<partial_sum_fn>, partial_sum)
0224     } // namespace views
0225     /// @}
0226 } // namespace ranges
0227
0228 #include <range/v3/detail/epilogue.hpp>
0229
0230 #include <range/v3/detail/satisfy_boost_range.hpp>
0231 RANGES_SATISFY_BOOST_RANGE(::ranges::partial_sum_view)
0232
0233 #endif