Horizon
fold_right.hpp
Go to the documentation of this file.
1 // Range v3 library
3 //
4 // Copyright Eric Niebler 2021-present
5 //
6 // Use, modification and distribution is subject to the
7 // Boost Software License, Version 1.0. (See accompanying
8 // file LICENSE_1_0.txt or copy at
9 // http://www.boost.org/LICENSE_1_0.txt)
10 //
11 // Project home: https://github.com/ericniebler/range-v3
12 
13 #ifndef RANGES_V3_ALGORITHM_FOLD_RIGHT_HPP
14 #define RANGES_V3_ALGORITHM_FOLD_RIGHT_HPP
15 
16 #include <meta/meta.hpp>
17 
25 
26 #include <range/v3/detail/prologue.hpp>
27 
28 namespace ranges
29 {
30  namespace detail
31  {
32  template<typename F>
33  struct flipped
34  {
35  F f;
36 
37  template(class T, class U)(requires invocable<F &, U, T>) //
38  invoke_result_t<F &, U, T>
39  operator()(T &&, U &&);
40  };
41  } // namespace detail
42 
43  // clang-format off
46  template<class F, class T, class I>
48  indirectly_binary_left_foldable<detail::flipped<F>, T, I>;
49  // clang-format on
50 
53  RANGES_FUNC_BEGIN(fold_right)
54 
55  template(typename I, typename S, typename T, typename Op)(
56  requires sentinel_for<S, I> AND bidirectional_iterator<I> AND
57  indirectly_binary_right_foldable<Op, T, I>) //
58  constexpr auto
59  RANGES_FUNC(fold_right)(I first, S last, T init, Op op)
60  {
61  using U = std::decay_t<invoke_result_t<Op &, iter_reference_t<I>, T>>;
62 
63  if(first == last)
64  {
65  return U(std::move(init));
66  }
67 
68  I tail = next(first, last);
69  U accum = invoke(op, *--tail, std::move(init));
70  while(first != tail)
71  {
72  accum = invoke(op, *--tail, std::move(accum));
73  }
74  return accum;
75  }
76 
77  template(typename Rng, typename T, typename Op)(
78  requires bidirectional_range<Rng> AND
79  indirectly_binary_right_foldable<Op, T, iterator_t<Rng>>) //
80  constexpr auto
81  RANGES_FUNC(fold_right)(Rng && rng, T init, Op op)
82  {
83  return (*this)(begin(rng), end(rng), std::move(init), std::move(op));
84  }
85 
86  RANGES_FUNC_END(fold_right)
87 
88  RANGES_FUNC_BEGIN(fold_right_last)
89 
90  template(typename I, typename S, typename Op)(
91  requires sentinel_for<S, I> AND bidirectional_iterator<I> AND
92  indirectly_binary_right_foldable<Op, iter_value_t<I>, I>
93  AND constructible_from<iter_value_t<I>, iter_reference_t<I>>) //
94  constexpr auto
95  RANGES_FUNC(fold_right_last)(I first, S last, Op op)
96  {
97  using U = invoke_result_t<fold_right_fn, I, S, iter_value_t<I>, Op>;
98  if(first == last)
99  {
100  return optional<U>();
101  }
102 
103  I tail = prev(next(first, std::move(last)));
104  return optional<U>(
105  in_place,
106  fold_right_fn{}(
107  std::move(first), tail, iter_value_t<I>(*tail), std::move(op)));
108  }
109 
110  template(typename R, typename Op)(
111  requires bidirectional_range<R> AND
112  indirectly_binary_right_foldable<Op, range_value_t<R>, iterator_t<R>>
113  AND constructible_from<range_value_t<R>, range_reference_t<R>>) //
114  constexpr auto
115  RANGES_FUNC(fold_right_last)(R && rng, Op op)
116  {
117  return (*this)(begin(rng), end(rng), std::move(op));
118  }
119 
120  RANGES_FUNC_END(fold_right_last)
122 } // namespace ranges
123 
124 #include <range/v3/detail/epilogue.hpp>
125 
126 #endif
CPP_concept indirectly_binary_right_foldable
\concept indirectly_binary_right_foldable
Definition: fold_right.hpp:47
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
Tiny meta-programming library.
Definition: fold_right.hpp:34