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 <__ranges/access.h>
27#include <__ranges/concepts.h>
28#include <__ranges/dangling.h>
29#include <__type_traits/decay.h>
30#include <__type_traits/invoke.h>
31#include <__utility/forward.h>
32#include <__utility/move.h>
33
34#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
35# pragma GCC system_header
36#endif
37
38_LIBCPP_PUSH_MACROS
39#include <__undef_macros>
40
41_LIBCPP_BEGIN_NAMESPACE_STD
42
43#if _LIBCPP_STD_VER >= 23
44
45namespace ranges {
46template <class _Ip, class _Tp>
47struct in_value_result {
48 _LIBCPP_NO_UNIQUE_ADDRESS _Ip in;
49 _LIBCPP_NO_UNIQUE_ADDRESS _Tp value;
50
51 template <class _I2, class _T2>
52 requires convertible_to<const _Ip&, _I2> && convertible_to<const _Tp&, _T2>
53 _LIBCPP_HIDE_FROM_ABI constexpr operator in_value_result<_I2, _T2>() const& {
54 return {in, value};
55 }
56
57 template <class _I2, class _T2>
58 requires convertible_to<_Ip, _I2> && convertible_to<_Tp, _T2>
59 _LIBCPP_HIDE_FROM_ABI constexpr operator in_value_result<_I2, _T2>() && {
60 return {std::move(in), std::move(value)};
61 }
62};
63
64template <class _Ip, class _Tp>
65using fold_left_with_iter_result = in_value_result<_Ip, _Tp>;
66
67template <class _Fp, class _Tp, class _Ip, class _Rp, class _Up = decay_t<_Rp>>
68concept __indirectly_binary_left_foldable_impl =
69 convertible_to<_Rp, _Up> && //
70 movable<_Tp> && //
71 movable<_Up> && //
72 convertible_to<_Tp, _Up> && //
73 invocable<_Fp&, _Up, iter_reference_t<_Ip>> && //
74 assignable_from<_Up&, invoke_result_t<_Fp&, _Up, iter_reference_t<_Ip>>>;
75
76template <class _Fp, class _Tp, class _Ip>
77concept __indirectly_binary_left_foldable =
78 copy_constructible<_Fp> && //
79 invocable<_Fp&, _Tp, iter_reference_t<_Ip>> && //
80 __indirectly_binary_left_foldable_impl<_Fp, _Tp, _Ip, invoke_result_t<_Fp&, _Tp, iter_reference_t<_Ip>>>;
81
82struct __fold_left_with_iter {
83 template <input_iterator _Ip, sentinel_for<_Ip> _Sp, class _Tp, __indirectly_binary_left_foldable<_Tp, _Ip> _Fp>
84 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI static constexpr auto operator()(_Ip __first, _Sp __last, _Tp __init, _Fp __f) {
85 using _Up = decay_t<invoke_result_t<_Fp&, _Tp, iter_reference_t<_Ip>>>;
86
87 if (__first == __last) {
88 return fold_left_with_iter_result<_Ip, _Up>{std::move(__first), _Up(std::move(__init))};
89 }
90
91 _Up __result = std::invoke(__f, std::move(__init), *__first);
92 ++__first;
93 __identity __proj;
94 auto __end = std::__for_each(
95 std::move(__first),
96 std::move(__last),
97 [&](auto&& __element) {
98 __result = std::invoke(__f, std::move(__result), std::forward<decltype(__element)>(__element));
99 },
100 __proj);
101
102 return fold_left_with_iter_result<_Ip, _Up>{std::move(__end), std::move(__result)};
103 }
104
105 template <input_range _Rp, class _Tp, __indirectly_binary_left_foldable<_Tp, iterator_t<_Rp>> _Fp>
106 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI static constexpr auto operator()(_Rp&& __r, _Tp __init, _Fp __f) {
107 auto __result = operator()(ranges::begin(__r), ranges::end(__r), std::move(__init), std::ref(__f));
108
109 using _Up = decay_t<invoke_result_t<_Fp&, _Tp, range_reference_t<_Rp>>>;
110 return fold_left_with_iter_result<borrowed_iterator_t<_Rp>, _Up>{std::move(__result.in), std::move(__result.value)};
111 }
112};
113
114inline constexpr auto fold_left_with_iter = __fold_left_with_iter();
115
116struct __fold_left {
117 template <input_iterator _Ip, sentinel_for<_Ip> _Sp, class _Tp, __indirectly_binary_left_foldable<_Tp, _Ip> _Fp>
118 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI static constexpr auto operator()(_Ip __first, _Sp __last, _Tp __init, _Fp __f) {
119 return fold_left_with_iter(std::move(__first), std::move(__last), std::move(__init), std::ref(__f)).value;
120 }
121
122 template <input_range _Rp, class _Tp, __indirectly_binary_left_foldable<_Tp, iterator_t<_Rp>> _Fp>
123 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI static constexpr auto operator()(_Rp&& __r, _Tp __init, _Fp __f) {
124 return fold_left_with_iter(ranges::begin(__r), ranges::end(__r), std::move(__init), std::ref(__f)).value;
125 }
126};
127
128inline constexpr auto fold_left = __fold_left();
129} // namespace ranges
130
131#endif // _LIBCPP_STD_VER >= 23
132
133_LIBCPP_END_NAMESPACE_STD
134
135_LIBCPP_POP_MACROS
136
137#endif // _LIBCPP___ALGORITHM_RANGES_FOLD_H
138