Horizon
partial_sum.hpp
Go to the documentation of this file.
1 // Range v3 library
3 //
4 // Copyright Eric Niebler 2013-present
5 // Copyright Gonzalo Brito Gadeschi 2014
6 //
7 // Use, modification and distribution is subject to the
8 // Boost Software License, Version 1.0. (See accompanying
9 // file LICENSE_1_0.txt or copy at
10 // http://www.boost.org/LICENSE_1_0.txt)
11 //
12 // Project home: https://github.com/ericniebler/range-v3
13 //
14 #ifndef RANGES_V3_NUMERIC_PARTIAL_SUM_HPP
15 #define RANGES_V3_NUMERIC_PARTIAL_SUM_HPP
16 
17 #include <meta/meta.hpp>
18 
19 #include <range/v3/algorithm/result_types.hpp>
31 #include <range/v3/utility/static_const.hpp>
32 
33 #include <range/v3/detail/prologue.hpp>
34 
35 namespace ranges
36 {
39 
41  namespace detail
42  {
43  // Only needed for type-checking purposes:
44  struct as_lvalue_fn
45  {
46  template<typename T>
47  constexpr T & operator()(T && t) const noexcept
48  {
49  return t;
50  }
51  };
52  template<typename I>
53  using as_value_type_t = composed<as_lvalue_fn, coerce<iter_value_t<I>>>;
54  } // namespace detail
56 
57  // axiom: BOp is associative over values of I.
58  // clang-format off
61  template(typename I, typename BOp)(
62  concept (indirect_semigroup_)(I, BOp),
63  copyable<iter_value_t<I>> AND
64  indirectly_regular_binary_invocable_<
65  composed<coerce<iter_value_t<I>>, BOp>,
66  iter_value_t<I>*, I>
67  );
70  template<typename I, typename BOp>
71  CPP_concept indirect_semigroup =
72  indirectly_readable<I> &&
73  CPP_concept_ref(ranges::indirect_semigroup_, I, BOp);
74 
77  template(typename I, typename O, typename BOp, typename P)(
78  concept (partial_sum_constraints_)(I, O, BOp, P),
80  projected<projected<I, detail::as_value_type_t<I>>, P>,
81  BOp> AND
83  O,
84  iter_value_t<
85  projected<projected<I, detail::as_value_type_t<I>>, P>> const &>
86  );
89  template<typename I, typename O, typename BOp = plus, typename P = identity>
91  input_iterator<I> &&
92  CPP_concept_ref(ranges::partial_sum_constraints_, I, O, BOp, P);
93  // clang-format on
94 
95  template<typename I, typename O>
96  using partial_sum_result = detail::in_out_result<I, O>;
97 
99  {
100  template(typename I, typename S1, typename O, typename S2, typename BOp = plus,
101  typename P = identity)(
102  requires sentinel_for<S1, I> AND sentinel_for<S2, O> AND
103  partial_sum_constraints<I, O, BOp, P>)
104  partial_sum_result<I, O> operator()(I first,
105  S1 last,
106  O result,
107  S2 end_result,
108  BOp bop = BOp{},
109  P proj = P{}) const
110  {
111  using X = projected<projected<I, detail::as_value_type_t<I>>, P>;
112  coerce<iter_value_t<I>> val_i;
113  coerce<iter_value_t<X>> val_x;
114  if(first != last && result != end_result)
115  {
116  auto && cur1 = val_i(*first);
117  iter_value_t<X> t(invoke(proj, cur1));
118  *result = t;
119  for(++first, ++result; first != last && result != end_result;
120  ++first, ++result)
121  {
122  auto && cur2 = val_i(*first);
123  t = val_x(invoke(bop, t, invoke(proj, cur2)));
124  *result = t;
125  }
126  }
127  return {first, result};
128  }
129 
130  template(typename I, typename S, typename O, typename BOp = plus,
131  typename P = identity)(
132  requires sentinel_for<S, I> AND partial_sum_constraints<I, O, BOp, P>)
133  partial_sum_result<I, O> //
134  operator()(I first, S last, O result, BOp bop = BOp{}, P proj = P{}) const
135  {
136  return (*this)(std::move(first),
137  std::move(last),
138  std::move(result),
139  unreachable,
140  std::move(bop),
141  std::move(proj));
142  }
143 
144  template(typename Rng, typename ORef, typename BOp = plus, typename P = identity,
145  typename I = iterator_t<Rng>, typename O = uncvref_t<ORef>)(
146  requires range<Rng> AND partial_sum_constraints<I, O, BOp, P>)
147  partial_sum_result<borrowed_iterator_t<Rng>, O> //
148  operator()(Rng && rng, ORef && result, BOp bop = BOp{}, P proj = P{}) const
149  {
150  return (*this)(begin(rng),
151  end(rng),
152  static_cast<ORef &&>(result),
153  std::move(bop),
154  std::move(proj));
155  }
156 
157  template(typename Rng, typename ORng, typename BOp = plus, typename P = identity,
158  typename I = iterator_t<Rng>, typename O = iterator_t<ORng>)(
159  requires range<Rng> AND range<ORng> AND partial_sum_constraints<I, O, BOp, P>)
160  partial_sum_result<borrowed_iterator_t<Rng>, borrowed_iterator_t<ORng>> //
161  operator()(Rng && rng, ORng && result, BOp bop = BOp{}, P proj = P{}) const
162  {
163  return (*this)(begin(rng),
164  end(rng),
165  begin(result),
166  end(result),
167  std::move(bop),
168  std::move(proj));
169  }
170  };
171 
174 } // namespace ranges
175 
176 #include <range/v3/detail/epilogue.hpp>
177 
178 #endif
CPP_concept output_iterator
\concept output_iterator
Definition: concepts.hpp:347
CPP_concept partial_sum_constraints
\concept partial_sum_constraints
Definition: partial_sum.hpp:90
CPP_concept indirect_semigroup
\concept indirect_semigroup
Definition: partial_sum.hpp:71
decltype(begin(declval(Rng &))) iterator_t
Definition: access.hpp:698
RANGES_INLINE_VARIABLE(detail::to_container_fn< detail::from_range< std::vector >>, to_vector) template< template< typename... > class ContT > auto to(RANGES_HIDDEN_DETAIL(detail
For initializing a container of the specified type with the elements of an Range.
Definition: conversion.hpp:399
typename Fn::template invoke< Args... > invoke
Evaluate the invocable Fn with the arguments Args.
Definition: meta.hpp:541
front< Pair > first
Retrieve the first element of the pair Pair.
Definition: meta.hpp:2251
std::integral_constant< decltype(T::type::value+U::type::value), T::type::value+U::type::value > plus
An integral constant wrapper around the result of adding the two wrapped integers T::type::value and ...
Definition: meta.hpp:197
Tiny meta-programming library.
Definition: arithmetic.hpp:78
Definition: compose.hpp:33
Definition: identity.hpp:25
Definition: partial_sum.hpp:99