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