v3/numeric/partial_sum.hpp

0001 /// \file
0002 // Range v3 library
0003 //
0004 //  Copyright Eric Niebler 2013-present
0005 //  Copyright Gonzalo Brito Gadeschi 2014
0006 //
0007 //  Use, modification and distribution is subject to the
0008 //  Boost Software License, Version 1.0. (See accompanying
0009 //  file LICENSE_1_0.txt or copy at
0010 //  http://www.boost.org/LICENSE_1_0.txt)
0011 //
0012 // Project home: https://github.com/ericniebler/range-v3
0013 //
0014 #ifndef RANGES_V3_NUMERIC_PARTIAL_SUM_HPP
0015 #define RANGES_V3_NUMERIC_PARTIAL_SUM_HPP
0016
0017 #include <meta/meta.hpp>
0018
0019 #include <range/v3/algorithm/result_types.hpp>
0020 #include <range/v3/functional/arithmetic.hpp>
0021 #include <range/v3/functional/compose.hpp>
0022 #include <range/v3/functional/identity.hpp>
0023 #include <range/v3/functional/invoke.hpp>
0024 #include <range/v3/iterator/concepts.hpp>
0025 #include <range/v3/iterator/traits.hpp>
0026 #include <range/v3/iterator/unreachable_sentinel.hpp>
0027 #include <range/v3/range/access.hpp>
0028 #include <range/v3/range/concepts.hpp>
0029 #include <range/v3/range/dangling.hpp>
0030 #include <range/v3/range/traits.hpp>
0031 #include <range/v3/utility/static_const.hpp>
0032
0033 #include <range/v3/detail/prologue.hpp>
0034
0035 namespace ranges
0036 {
0037     /// \addtogroup group-numerics
0038     /// @{
0039
0040     /// \cond
0041     namespace detail
0042     {
0043         // Only needed for type-checking purposes:
0044         struct as_lvalue_fn
0045         {
0046             template<typename T>
0047             constexpr T & operator()(T && t) const noexcept
0048             {
0049                 return t;
0050             }
0051         };
0052         template<typename I>
0053         using as_value_type_t = composed<as_lvalue_fn, coerce<iter_value_t<I>>>;
0054     } // namespace detail
0055       /// \endcond
0056
0057     // axiom: BOp is associative over values of I.
0058     // clang-format off
0059     /// \concept indirect_semigroup_
0060     /// \brief The \c indirect_semigroup_ concept
0061     template(typename I, typename BOp)(
0062     concept (indirect_semigroup_)(I, BOp),
0063         copyable<iter_value_t<I>> AND
0064         indirectly_regular_binary_invocable_<
0065             composed<coerce<iter_value_t<I>>, BOp>,
0066             iter_value_t<I>*, I>
0067     );
0068     /// \concept indirect_semigroup
0069     /// \brief The \c indirect_semigroup concept
0070     template<typename I, typename BOp>
0071     CPP_concept indirect_semigroup =
0072         indirectly_readable<I> &&
0073         CPP_concept_ref(ranges::indirect_semigroup_, I, BOp);
0074
0075     /// \concept partial_sum_constraints_
0076     /// \brief The \c partial_sum_constraints_ concept
0077     template(typename I, typename O, typename BOp, typename P)(
0078     concept (partial_sum_constraints_)(I, O, BOp, P),
0079         indirect_semigroup<
0080             projected<projected<I, detail::as_value_type_t<I>>, P>,
0081             BOp> AND
0082         output_iterator<
0083             O,
0084             iter_value_t<
0085                 projected<projected<I, detail::as_value_type_t<I>>, P>> const &>
0086     );
0087     /// \concept partial_sum_constraints
0088     /// \brief The \c partial_sum_constraints concept
0089     template<typename I, typename O, typename BOp = plus, typename P = identity>
0090     CPP_concept partial_sum_constraints =
0091         input_iterator<I> &&
0092         CPP_concept_ref(ranges::partial_sum_constraints_, I, O, BOp, P);
0093     // clang-format on
0094
0095     template<typename I, typename O>
0096     using partial_sum_result = detail::in_out_result<I, O>;
0097
0098     struct partial_sum_fn
0099     {
0100         template(typename I, typename S1, typename O, typename S2, typename BOp = plus,
0101                  typename P = identity)(
0102             requires sentinel_for<S1, I> AND sentinel_for<S2, O> AND
0103                 partial_sum_constraints<I, O, BOp, P>)
0104         partial_sum_result<I, O> operator()(I first,
0105                                             S1 last,
0106                                             O result,
0107                                             S2 end_result,
0108                                             BOp bop = BOp{},
0109                                             P proj = P{}) const
0110         {
0111             using X = projected<projected<I, detail::as_value_type_t<I>>, P>;
0112             coerce<iter_value_t<I>> val_i;
0113             coerce<iter_value_t<X>> val_x;
0114             if(first != last && result != end_result)
0115             {
0116                 auto && cur1 = val_i(*first);
0117                 iter_value_t<X> t(invoke(proj, cur1));
0118                 *result = t;
0119                 for(++first, ++result; first != last && result != end_result;
0120                     ++first, ++result)
0121                 {
0122                     auto && cur2 = val_i(*first);
0123                     t = val_x(invoke(bop, t, invoke(proj, cur2)));
0124                     *result = t;
0125                 }
0126             }
0127             return {first, result};
0128         }
0129
0130         template(typename I, typename S, typename O, typename BOp = plus,
0131                  typename P = identity)(
0132             requires sentinel_for<S, I> AND partial_sum_constraints<I, O, BOp, P>)
0133         partial_sum_result<I, O> //
0134         operator()(I first, S last, O result, BOp bop = BOp{}, P proj = P{}) const
0135         {
0136             return (*this)(std::move(first),
0137                            std::move(last),
0138                            std::move(result),
0139                            unreachable,
0140                            std::move(bop),
0141                            std::move(proj));
0142         }
0143
0144         template(typename Rng, typename ORef, typename BOp = plus, typename P = identity,
0145                  typename I = iterator_t<Rng>, typename O = uncvref_t<ORef>)(
0146             requires range<Rng> AND partial_sum_constraints<I, O, BOp, P>)
0147         partial_sum_result<borrowed_iterator_t<Rng>, O> //
0148         operator()(Rng && rng, ORef && result, BOp bop = BOp{}, P proj = P{}) const
0149         {
0150             return (*this)(begin(rng),
0151                            end(rng),
0152                            static_cast<ORef &&>(result),
0153                            std::move(bop),
0154                            std::move(proj));
0155         }
0156
0157         template(typename Rng, typename ORng, typename BOp = plus, typename P = identity,
0158                  typename I = iterator_t<Rng>, typename O = iterator_t<ORng>)(
0159             requires range<Rng> AND range<ORng> AND partial_sum_constraints<I, O, BOp, P>)
0160         partial_sum_result<borrowed_iterator_t<Rng>, borrowed_iterator_t<ORng>> //
0161         operator()(Rng && rng, ORng && result, BOp bop = BOp{}, P proj = P{}) const
0162         {
0163             return (*this)(begin(rng),
0164                            end(rng),
0165                            begin(result),
0166                            end(result),
0167                            std::move(bop),
0168                            std::move(proj));
0169         }
0170     };
0171
0172     RANGES_INLINE_VARIABLE(partial_sum_fn, partial_sum)
0173     /// @}
0174 } // namespace ranges
0175
0176 #include <range/v3/detail/epilogue.hpp>
0177
0178 #endif