1// -*- C++ -*-
2//===----------------------------------------------------------------------===//
3//
4// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
5// See https://llvm.org/LICENSE.txt for license information.
6// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7//
8//===----------------------------------------------------------------------===//
9
10#ifndef _LIBCPP___ALGORITHM_RANGES_FOLD_H
11#define _LIBCPP___ALGORITHM_RANGES_FOLD_H
12
13#include <__algorithm/for_each.h>
14#include <__concepts/assignable.h>
15#include <__concepts/constructible.h>
16#include <__concepts/convertible_to.h>
17#include <__concepts/invocable.h>
18#include <__concepts/movable.h>
19#include <__config>
20#include <__functional/identity.h>
21#include <__functional/invoke.h>
22#include <__functional/reference_wrapper.h>
23#include <__iterator/concepts.h>
24#include <__iterator/iterator_traits.h>
25#include <__iterator/next.h>
26#include <__iterator/prev.h>
27#include <__iterator/reverse_iterator.h>
28#include <__optional/optional.h>
29#include <__ranges/access.h>
30#include <__ranges/concepts.h>
31#include <__ranges/dangling.h>
32#include <__type_traits/decay.h>
33#include <__type_traits/invoke.h>
34#include <__utility/forward.h>
35#include <__utility/in_place.h>
36#include <__utility/move.h>
37
38#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
39# pragma GCC system_header
40#endif
41
42_LIBCPP_PUSH_MACROS
43#include <__undef_macros>
44
45_LIBCPP_BEGIN_NAMESPACE_STD
46
47#if _LIBCPP_STD_VER >= 23
48
49namespace ranges {
50template <class _Ip, class _Tp>
51struct in_value_result {
52 _LIBCPP_NO_UNIQUE_ADDRESS _Ip in;
53 _LIBCPP_NO_UNIQUE_ADDRESS _Tp value;
54
55 template <class _I2, class _T2>
56 requires convertible_to<const _Ip&, _I2> && convertible_to<const _Tp&, _T2>
57 _LIBCPP_HIDE_FROM_ABI constexpr operator in_value_result<_I2, _T2>() const& {
58 return {in, value};
59 }
60
61 template <class _I2, class _T2>
62 requires convertible_to<_Ip, _I2> && convertible_to<_Tp, _T2>
63 _LIBCPP_HIDE_FROM_ABI constexpr operator in_value_result<_I2, _T2>() && {
64 return {std::move(in), std::move(value)};
65 }
66};
67
68template <class _Ip, class _Tp>
69using fold_left_with_iter_result = in_value_result<_Ip, _Tp>;
70
71template <class _Ip, class _Tp>
72using fold_left_first_with_iter_result = in_value_result<_Ip, _Tp>;
73
74template <class _Fp, class _Tp, class _Ip, class _Rp, class _Up = decay_t<_Rp>>
75concept __indirectly_binary_left_foldable_impl =
76 convertible_to<_Rp, _Up> && //
77 movable<_Tp> && //
78 movable<_Up> && //
79 convertible_to<_Tp, _Up> && //
80 invocable<_Fp&, _Up, iter_reference_t<_Ip>> && //
81 assignable_from<_Up&, invoke_result_t<_Fp&, _Up, iter_reference_t<_Ip>>>;
82
83template <class _Fp, class _Tp, class _Ip>
84concept __indirectly_binary_left_foldable =
85 copy_constructible<_Fp> && //
86 invocable<_Fp&, _Tp, iter_reference_t<_Ip>> && //
87 __indirectly_binary_left_foldable_impl<_Fp, _Tp, _Ip, invoke_result_t<_Fp&, _Tp, iter_reference_t<_Ip>>>;
88
89template <class _Func>
90struct __flipped {
91 _Func __func;
92
93 template <class _Tp, class _Up>
94 requires invocable<_Func&, _Up, _Tp>
95 invoke_result_t<_Func&, _Up, _Tp> operator()(_Tp&&, _Up&&);
96};
97
98template <class _Func, class _Tp, class _Iter>
99concept __indirectly_binary_right_foldable = __indirectly_binary_left_foldable<__flipped<_Func>, _Tp, _Iter>;
100
101struct __fold_left_with_iter {
102 template <input_iterator _Ip, sentinel_for<_Ip> _Sp, class _Tp, __indirectly_binary_left_foldable<_Tp, _Ip> _Fp>
103 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI static constexpr auto operator()(_Ip __first, _Sp __last, _Tp __init, _Fp __f) {
104 using _Up = decay_t<invoke_result_t<_Fp&, _Tp, iter_reference_t<_Ip>>>;
105
106 if (__first == __last) {
107 return fold_left_with_iter_result<_Ip, _Up>{std::move(__first), _Up(std::move(__init))};
108 }
109
110 _Up __result = std::invoke(__f, std::move(__init), *__first);
111 ++__first;
112 __identity __proj;
113 auto __end = std::__for_each(
114 std::move(__first),
115 std::move(__last),
116 [&](auto&& __element) {
117 __result = std::invoke(__f, std::move(__result), std::forward<decltype(__element)>(__element));
118 },
119 __proj);
120
121 return fold_left_with_iter_result<_Ip, _Up>{std::move(__end), std::move(__result)};
122 }
123
124 template <input_range _Rp, class _Tp, __indirectly_binary_left_foldable<_Tp, iterator_t<_Rp>> _Fp>
125 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI static constexpr auto operator()(_Rp&& __r, _Tp __init, _Fp __f) {
126 auto __result = operator()(ranges::begin(__r), ranges::end(__r), std::move(__init), std::ref(__f));
127
128 using _Up = decay_t<invoke_result_t<_Fp&, _Tp, range_reference_t<_Rp>>>;
129 return fold_left_with_iter_result<borrowed_iterator_t<_Rp>, _Up>{std::move(__result.in), std::move(__result.value)};
130 }
131};
132
133inline constexpr auto fold_left_with_iter = __fold_left_with_iter();
134
135struct __fold_left {
136 template <input_iterator _Ip, sentinel_for<_Ip> _Sp, class _Tp, __indirectly_binary_left_foldable<_Tp, _Ip> _Fp>
137 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI static constexpr auto operator()(_Ip __first, _Sp __last, _Tp __init, _Fp __f) {
138 return fold_left_with_iter(std::move(__first), std::move(__last), std::move(__init), std::ref(__f)).value;
139 }
140
141 template <input_range _Rp, class _Tp, __indirectly_binary_left_foldable<_Tp, iterator_t<_Rp>> _Fp>
142 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI static constexpr auto operator()(_Rp&& __r, _Tp __init, _Fp __f) {
143 return fold_left_with_iter(ranges::begin(__r), ranges::end(__r), std::move(__init), std::ref(__f)).value;
144 }
145};
146
147inline constexpr auto fold_left = __fold_left();
148
149struct __fold_left_first_with_iter {
150 template <input_iterator _Iter,
151 sentinel_for<_Iter> _Sent,
152 __indirectly_binary_left_foldable<iter_value_t<_Iter>, _Iter> _Func>
153 requires constructible_from<iter_value_t<_Iter>, iter_reference_t<_Iter>>
154 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI static constexpr auto operator()(_Iter __first, _Sent __last, _Func __func) {
155 using _Up = decltype(fold_left(std::move(__first), __last, iter_value_t<_Iter>(*__first), __func));
156
157 if (__first == __last)
158 return fold_left_first_with_iter_result<_Iter, optional<_Up>>{std::move(__first), optional<_Up>()};
159
160 _Up __result(*__first);
161 ++__first;
162 __identity __proj;
163 auto __end = std::__for_each(
164 std::move(__first),
165 std::move(__last),
166 [&](auto&& __element) {
167 __result = std::invoke(__func, std::move(__result), std::forward<decltype(__element)>(__element));
168 },
169 __proj);
170
171 return fold_left_first_with_iter_result<_Iter, optional<_Up>>{std::move(__end), optional<_Up>(std::move(__result))};
172 }
173
174 template <input_range _Range, __indirectly_binary_left_foldable<range_value_t<_Range>, iterator_t<_Range>> _Func>
175 requires constructible_from<range_value_t<_Range>, range_reference_t<_Range>>
176 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI static constexpr auto operator()(_Range&& __range, _Func __func) {
177 auto __result = operator()(ranges::begin(__range), ranges::end(__range), std::ref(__func));
178
179 using _Up = decltype(fold_left(
180 ranges::begin(__range), ranges::end(__range), range_value_t<_Range>(*ranges::begin(__range)), __func));
181 return fold_left_first_with_iter_result<borrowed_iterator_t<_Range>, optional<_Up>>{
182 std::move(__result.in), std::move(__result.value)};
183 }
184};
185
186inline constexpr auto fold_left_first_with_iter = __fold_left_first_with_iter();
187
188struct __fold_left_first {
189 template <input_iterator _Iter,
190 sentinel_for<_Iter> _Sent,
191 __indirectly_binary_left_foldable<iter_value_t<_Iter>, _Iter> _Func>
192 requires constructible_from<iter_value_t<_Iter>, iter_reference_t<_Iter>>
193 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI static constexpr auto operator()(_Iter __first, _Sent __last, _Func __func) {
194 return fold_left_first_with_iter(std::move(__first), std::move(__last), std::ref(__func)).value;
195 }
196
197 template <input_range _Range, __indirectly_binary_left_foldable<range_value_t<_Range>, iterator_t<_Range>> _Func>
198 requires constructible_from<range_value_t<_Range>, range_reference_t<_Range>>
199 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI static constexpr auto operator()(_Range&& __range, _Func __func) {
200 return fold_left_first_with_iter(ranges::begin(__range), ranges::end(__range), std::ref(__func)).value;
201 }
202};
203
204inline constexpr auto fold_left_first = __fold_left_first();
205
206struct __fold_right {
207 template <bidirectional_iterator _Iter,
208 sentinel_for<_Iter> _Sp,
209 class _Tp,
210 __indirectly_binary_right_foldable<_Tp, _Iter> _Func>
211 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI static constexpr auto
212 operator()(_Iter __first, _Sp __last, _Tp __init, _Func __func) {
213 using _Up = decay_t<invoke_result_t<_Func&, iter_reference_t<_Iter>, _Tp>>;
214
215 if (__first == __last)
216 return _Up(std::move(__init));
217
218 _Iter __tail = ranges::next(__first, __last);
219 --__tail;
220 _Up __result = std::invoke(__func, *__tail, std::move(__init));
221 std::for_each(std::make_reverse_iterator(__tail), std::make_reverse_iterator(__first), [&](auto&& __element) {
222 __result = std::invoke(__func, std::forward<decltype(__element)>(__element), std::move(__result));
223 });
224
225 return __result;
226 }
227
228 template <bidirectional_range _Range, class _Tp, __indirectly_binary_right_foldable<_Tp, iterator_t<_Range>> _Func>
229 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI static constexpr auto operator()(_Range&& __range, _Tp __init, _Func __func) {
230 return operator()(ranges::begin(__range), ranges::end(__range), std::move(__init), std::ref(__func));
231 }
232};
233
234inline constexpr auto fold_right = __fold_right();
235
236struct __fold_right_last {
237 template <bidirectional_iterator _Iter,
238 sentinel_for<_Iter> _Sp,
239 __indirectly_binary_right_foldable<iter_value_t<_Iter>, _Iter> _Func>
240 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI static constexpr auto operator()(_Iter __first, _Sp __last, _Func __func) {
241 using _Up = decltype(fold_right(__first, __last, iter_value_t<_Iter>(*__first), __func));
242
243 if (__first == __last)
244 return optional<_Up>();
245
246 _Iter __tail = ranges::prev(ranges::next(__first, __last));
247 return optional<_Up>(
248 in_place, ranges::fold_right(std::move(__first), __tail, iter_value_t<_Iter>(*__tail), std::move(__func)));
249 }
250
251 template <bidirectional_range _Range,
252 __indirectly_binary_right_foldable<range_value_t<_Range>, iterator_t<_Range>> _Func>
253 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI static constexpr auto operator()(_Range&& __range, _Func __func) {
254 return operator()(ranges::begin(__range), ranges::end(__range), std::ref(__func));
255 }
256};
257
258inline constexpr auto fold_right_last = __fold_right_last();
259} // namespace ranges
260
261#endif // _LIBCPP_STD_VER >= 23
262
263_LIBCPP_END_NAMESPACE_STD
264
265_LIBCPP_POP_MACROS
266
267#endif // _LIBCPP___ALGORITHM_RANGES_FOLD_H
268