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 =
100 __indirectly_binary_left_foldable_impl<__flipped<_Func>,
101 _Tp,
102 _Iter,
103 invoke_result_t<_Func&, _Tp, iter_reference_t<_Iter>>>;
104
105struct __fold_left_with_iter {
106 template <input_iterator _Ip, sentinel_for<_Ip> _Sp, class _Tp, __indirectly_binary_left_foldable<_Tp, _Ip> _Fp>
107 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI static constexpr auto operator()(_Ip __first, _Sp __last, _Tp __init, _Fp __f) {
108 using _Up = decay_t<invoke_result_t<_Fp&, _Tp, iter_reference_t<_Ip>>>;
109
110 if (__first == __last) {
111 return fold_left_with_iter_result<_Ip, _Up>{std::move(__first), _Up(std::move(__init))};
112 }
113
114 _Up __result = std::invoke(__f, std::move(__init), *__first);
115 ++__first;
116 __identity __proj;
117 auto __end = std::__for_each(
118 std::move(__first),
119 std::move(__last),
120 [&](auto&& __element) {
121 __result = std::invoke(__f, std::move(__result), std::forward<decltype(__element)>(__element));
122 },
123 __proj);
124
125 return fold_left_with_iter_result<_Ip, _Up>{std::move(__end), std::move(__result)};
126 }
127
128 template <input_range _Rp, class _Tp, __indirectly_binary_left_foldable<_Tp, iterator_t<_Rp>> _Fp>
129 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI static constexpr auto operator()(_Rp&& __r, _Tp __init, _Fp __f) {
130 auto __result = operator()(ranges::begin(__r), ranges::end(__r), std::move(__init), std::ref(__f));
131
132 using _Up = decay_t<invoke_result_t<_Fp&, _Tp, range_reference_t<_Rp>>>;
133 return fold_left_with_iter_result<borrowed_iterator_t<_Rp>, _Up>{std::move(__result.in), std::move(__result.value)};
134 }
135};
136
137inline constexpr auto fold_left_with_iter = __fold_left_with_iter();
138
139struct __fold_left {
140 template <input_iterator _Ip, sentinel_for<_Ip> _Sp, class _Tp, __indirectly_binary_left_foldable<_Tp, _Ip> _Fp>
141 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI static constexpr auto operator()(_Ip __first, _Sp __last, _Tp __init, _Fp __f) {
142 return fold_left_with_iter(std::move(__first), std::move(__last), std::move(__init), std::ref(__f)).value;
143 }
144
145 template <input_range _Rp, class _Tp, __indirectly_binary_left_foldable<_Tp, iterator_t<_Rp>> _Fp>
146 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI static constexpr auto operator()(_Rp&& __r, _Tp __init, _Fp __f) {
147 return fold_left_with_iter(ranges::begin(__r), ranges::end(__r), std::move(__init), std::ref(__f)).value;
148 }
149};
150
151inline constexpr auto fold_left = __fold_left();
152
153struct __fold_left_first_with_iter {
154 template <input_iterator _Iter,
155 sentinel_for<_Iter> _Sent,
156 __indirectly_binary_left_foldable<iter_value_t<_Iter>, _Iter> _Func>
157 requires constructible_from<iter_value_t<_Iter>, iter_reference_t<_Iter>>
158 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI static constexpr auto operator()(_Iter __first, _Sent __last, _Func __func) {
159 using _Up = decltype(fold_left(std::move(__first), __last, iter_value_t<_Iter>(*__first), __func));
160
161 if (__first == __last)
162 return fold_left_first_with_iter_result<_Iter, optional<_Up>>{std::move(__first), optional<_Up>()};
163
164 _Up __result(*__first);
165 ++__first;
166 __identity __proj;
167 auto __end = std::__for_each(
168 std::move(__first),
169 std::move(__last),
170 [&](auto&& __element) {
171 __result = std::invoke(__func, std::move(__result), std::forward<decltype(__element)>(__element));
172 },
173 __proj);
174
175 return fold_left_first_with_iter_result<_Iter, optional<_Up>>{std::move(__end), optional<_Up>(std::move(__result))};
176 }
177
178 template <input_range _Range, __indirectly_binary_left_foldable<range_value_t<_Range>, iterator_t<_Range>> _Func>
179 requires constructible_from<range_value_t<_Range>, range_reference_t<_Range>>
180 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI static constexpr auto operator()(_Range&& __range, _Func __func) {
181 auto __result = operator()(ranges::begin(__range), ranges::end(__range), std::ref(__func));
182
183 using _Up = decltype(fold_left(
184 ranges::begin(__range), ranges::end(__range), range_value_t<_Range>(*ranges::begin(__range)), __func));
185 return fold_left_first_with_iter_result<borrowed_iterator_t<_Range>, optional<_Up>>{
186 std::move(__result.in), std::move(__result.value)};
187 }
188};
189
190inline constexpr auto fold_left_first_with_iter = __fold_left_first_with_iter();
191
192struct __fold_left_first {
193 template <input_iterator _Iter,
194 sentinel_for<_Iter> _Sent,
195 __indirectly_binary_left_foldable<iter_value_t<_Iter>, _Iter> _Func>
196 requires constructible_from<iter_value_t<_Iter>, iter_reference_t<_Iter>>
197 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI static constexpr auto operator()(_Iter __first, _Sent __last, _Func __func) {
198 return fold_left_first_with_iter(std::move(__first), std::move(__last), std::ref(__func)).value;
199 }
200
201 template <input_range _Range, __indirectly_binary_left_foldable<range_value_t<_Range>, iterator_t<_Range>> _Func>
202 requires constructible_from<range_value_t<_Range>, range_reference_t<_Range>>
203 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI static constexpr auto operator()(_Range&& __range, _Func __func) {
204 return fold_left_first_with_iter(ranges::begin(__range), ranges::end(__range), std::ref(__func)).value;
205 }
206};
207
208inline constexpr auto fold_left_first = __fold_left_first();
209
210struct __fold_right {
211 template <bidirectional_iterator _Iter,
212 sentinel_for<_Iter> _Sp,
213 class _Tp,
214 __indirectly_binary_right_foldable<_Tp, _Iter> _Func>
215 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI static constexpr auto
216 operator()(_Iter __first, _Sp __last, _Tp __init, _Func __func) {
217 using _Up = decay_t<invoke_result_t<_Func&, iter_reference_t<_Iter>, _Tp>>;
218
219 if (__first == __last)
220 return _Up(std::move(__init));
221
222 _Iter __tail = ranges::next(__first, __last);
223 --__tail;
224 _Up __result = std::invoke(__func, *__tail, std::move(__init));
225 std::for_each(std::make_reverse_iterator(__tail), std::make_reverse_iterator(__first), [&](auto&& __element) {
226 __result = std::invoke(__func, std::forward<decltype(__element)>(__element), std::move(__result));
227 });
228
229 return __result;
230 }
231
232 template <bidirectional_range _Range, class _Tp, __indirectly_binary_right_foldable<_Tp, iterator_t<_Range>> _Func>
233 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI static constexpr auto operator()(_Range&& __range, _Tp __init, _Func __func) {
234 return operator()(ranges::begin(__range), ranges::end(__range), std::move(__init), std::ref(__func));
235 }
236};
237
238inline constexpr auto fold_right = __fold_right();
239
240struct __fold_right_last {
241 template <bidirectional_iterator _Iter,
242 sentinel_for<_Iter> _Sp,
243 __indirectly_binary_right_foldable<iter_value_t<_Iter>, _Iter> _Func>
244 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI static constexpr auto operator()(_Iter __first, _Sp __last, _Func __func) {
245 using _Up = decltype(fold_right(__first, __last, iter_value_t<_Iter>(*__first), __func));
246
247 if (__first == __last)
248 return optional<_Up>();
249
250 _Iter __tail = ranges::prev(ranges::next(__first, __last));
251 return optional<_Up>(
252 in_place, ranges::fold_right(std::move(__first), __tail, iter_value_t<_Iter>(*__tail), std::move(__func)));
253 }
254
255 template <bidirectional_range _Range,
256 __indirectly_binary_right_foldable<range_value_t<_Range>, iterator_t<_Range>> _Func>
257 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI static constexpr auto operator()(_Range&& __range, _Func __func) {
258 return operator()(ranges::begin(__range), ranges::end(__range), std::ref(__func));
259 }
260};
261
262inline constexpr auto fold_right_last = __fold_right_last();
263} // namespace ranges
264
265#endif // _LIBCPP_STD_VER >= 23
266
267_LIBCPP_END_NAMESPACE_STD
268
269_LIBCPP_POP_MACROS
270
271#endif // _LIBCPP___ALGORITHM_RANGES_FOLD_H
272