Horizon
Loading...
Searching...
No Matches
fold_right.hpp
Go to the documentation of this file.
1
2// 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
28namespace 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>
49 // clang-format on
50
53 RANGES_FUNC_BEGIN(fold_right)
54
55 template(typename I, typename S, typename T, typename Op)(
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
The bidirectional_iterator concept.
The indirectly_binary_left_foldable concept.
The indirectly_binary_right_foldable concept.
The invocable concept.
The sentinel_for concept.
front< Pair > first
Retrieve the first element of the pair Pair.
Definition meta.hpp:2251
Tiny meta-programming library.
Definition fold_right.hpp:34