1//===----------------------------------------------------------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8
9// <algorithm>
10
11// UNSUPPORTED: c++03, c++11, c++14, c++17, c++20
12
13// MSVC warning C4244: 'argument': conversion from 'double' to 'const int', possible loss of data
14// ADDITIONAL_COMPILE_FLAGS(cl-style-warnings): /wd4244
15
16// template<input_iterator I, sentinel_for<I> S, class T,
17// indirectly-binary-left-foldable<T, I> F>
18// constexpr see below ranges::fold_left_with_iter(I first, S last, T init, F f);
19//
20// template<input_range R, class T, indirectly-binary-left-foldable<T, iterator_t<R>> F>
21// constexpr see below ranges::fold_left_with_iter(R&& r, T init, F f);
22
23// template<input_iterator I, sentinel_for<I> S, class T,
24// indirectly-binary-left-foldable<T, I> F>
25// constexpr see below ranges::fold_left(I first, S last, T init, F f);
26//
27// template<input_range R, class T, indirectly-binary-left-foldable<T, iterator_t<R>> F>
28// constexpr see below ranges::fold_left(R&& r, T init, F f);
29
30#include <algorithm>
31#include <cassert>
32#include <concepts>
33#include <deque>
34#include <forward_list>
35#include <functional>
36#include <iterator>
37#include <list>
38#include <ranges>
39#include <string_view>
40#include <string>
41#include <vector>
42
43#include "test_macros.h"
44#include "test_range.h"
45#include "invocable_with_telemetry.h"
46#include "maths.h"
47
48#if !defined(TEST_HAS_NO_LOCALIZATION)
49# include <sstream>
50#endif
51
52using std::ranges::fold_left;
53using std::ranges::fold_left_with_iter;
54
55template <class Result, class Range, class T>
56concept is_in_value_result =
57 std::same_as<Result, std::ranges::fold_left_with_iter_result<std::ranges::iterator_t<Range>, T>>;
58
59template <class Result, class T>
60concept is_dangling_with = std::same_as<Result, std::ranges::fold_left_with_iter_result<std::ranges::dangling, T>>;
61
62struct Integer {
63 int value;
64
65 constexpr Integer(int const x) : value(x) {}
66
67 constexpr Integer plus(int const x) const { return Integer{value + x}; }
68
69 friend constexpr bool operator==(Integer const& x, Integer const& y) = default;
70};
71
72template <std::ranges::input_range R, class T, class F, std::equality_comparable Expected>
73 requires std::copyable<R>
74constexpr void check_iterator(R& r, T const& init, F f, Expected const& expected) {
75 {
76 is_in_value_result<R, Expected> decltype(auto) result = fold_left_with_iter(r.begin(), r.end(), init, f);
77 assert(result.in == r.end());
78 assert(result.value == expected);
79 }
80
81 {
82 auto telemetry = invocable_telemetry();
83 auto f2 = invocable_with_telemetry(f, telemetry);
84 is_in_value_result<R, Expected> decltype(auto) result = fold_left_with_iter(r.begin(), r.end(), init, f2);
85 assert(result.in == r.end());
86 assert(result.value == expected);
87 assert(telemetry.invocations == std::ranges::distance(r));
88 assert(telemetry.moves == 0);
89 assert(telemetry.copies == 1);
90 }
91
92 {
93 std::same_as<Expected> decltype(auto) result = fold_left(r.begin(), r.end(), init, f);
94 assert(result == expected);
95 }
96
97 {
98 auto telemetry = invocable_telemetry();
99 auto f2 = invocable_with_telemetry(f, telemetry);
100 std::same_as<Expected> decltype(auto) result = fold_left(r.begin(), r.end(), init, f2);
101 assert(result == expected);
102 assert(telemetry.invocations == std::ranges::distance(r));
103 assert(telemetry.moves == 0);
104 assert(telemetry.copies == 1);
105 }
106}
107
108template <std::ranges::input_range R, class T, class F, std::equality_comparable Expected>
109 requires std::copyable<R>
110constexpr void check_lvalue_range(R& r, T const& init, F f, Expected const& expected) {
111 {
112 is_in_value_result<R, Expected> decltype(auto) result = fold_left_with_iter(r, init, f);
113 assert(result.in == r.end());
114 assert(result.value == expected);
115 }
116
117 {
118 auto telemetry = invocable_telemetry();
119 auto f2 = invocable_with_telemetry(f, telemetry);
120 std::same_as<Expected> decltype(auto) result = fold_left(r, init, f2);
121 assert(result == expected);
122 assert(telemetry.invocations == std::ranges::distance(r));
123 assert(telemetry.moves == 0);
124 assert(telemetry.copies == 1);
125 }
126
127 {
128 std::same_as<Expected> decltype(auto) result = fold_left(r, init, f);
129 assert(result == expected);
130 }
131
132 {
133 auto telemetry = invocable_telemetry();
134 auto f2 = invocable_with_telemetry(f, telemetry);
135 std::same_as<Expected> decltype(auto) result = fold_left(r, init, f2);
136 assert(result == expected);
137 assert(telemetry.invocations == std::ranges::distance(r));
138 assert(telemetry.moves == 0);
139 assert(telemetry.copies == 1);
140 }
141}
142
143template <std::ranges::input_range R, class T, class F, std::equality_comparable Expected>
144 requires std::copyable<R>
145constexpr void check_rvalue_range(R& r, T const& init, F f, Expected const& expected) {
146 {
147 auto r2 = r;
148 is_dangling_with<Expected> decltype(auto) result = fold_left_with_iter(std::move(r2), init, f);
149 assert(result.value == expected);
150 }
151
152 {
153 auto telemetry = invocable_telemetry();
154 auto f2 = invocable_with_telemetry(f, telemetry);
155 auto r2 = r;
156 is_dangling_with<Expected> decltype(auto) result = fold_left_with_iter(std::move(r2), init, f2);
157 assert(result.value == expected);
158 assert(telemetry.invocations == std::ranges::distance(r));
159 assert(telemetry.moves == 0);
160 assert(telemetry.copies == 1);
161 }
162
163 {
164 auto r2 = r;
165 std::same_as<Expected> decltype(auto) result = fold_left(std::move(r2), init, f);
166 assert(result == expected);
167 }
168
169 {
170 auto telemetry = invocable_telemetry();
171 auto f2 = invocable_with_telemetry(f, telemetry);
172 auto r2 = r;
173 std::same_as<Expected> decltype(auto) result = fold_left(std::move(r2), init, f2);
174 assert(result == expected);
175 assert(telemetry.invocations == std::ranges::distance(r));
176 assert(telemetry.moves == 0);
177 assert(telemetry.copies == 1);
178 }
179}
180
181template <std::ranges::input_range R, class T, class F, std::equality_comparable Expected>
182 requires std::copyable<R>
183constexpr void check(R r, T const& init, F f, Expected const& expected) {
184 check_iterator(r, init, f, expected);
185 check_lvalue_range(r, init, f, expected);
186 check_rvalue_range(r, init, f, expected);
187}
188
189constexpr void empty_range_test_case() {
190 auto const data = std::vector<int>{};
191 check(data, 100, std::plus(), 100);
192 check(data, -100, std::multiplies(), -100);
193
194 check(data | std::views::take_while([](auto) { return false; }), 1.23, std::plus(), 1.23);
195 check(data, Integer(52), &Integer::plus, Integer(52));
196}
197
198constexpr void common_range_test_case() {
199 auto const data = std::vector<int>{1, 2, 3, 4};
200 check(data, 0, std::plus(), triangular_sum(data));
201 check(data, 1, std::multiplies(), factorial(data.back()));
202
203 auto multiply_with_prev = [n = 1](auto const x, auto const y) mutable {
204 auto const result = x * y * n;
205 n = y;
206 return static_cast<std::size_t>(result);
207 };
208 check(data, 1, multiply_with_prev, factorial(data.size()) * factorial(data.size() - 1));
209
210 auto fib = [n = 1](auto x, auto) mutable {
211 auto old_x = x;
212 x += n;
213 n = old_x;
214 return x;
215 };
216 check(data, 0, fib, fibonacci(data.back()));
217
218 check(data, Integer(0), &Integer::plus, Integer(triangular_sum(data)));
219}
220
221constexpr void non_common_range_test_case() {
222 auto parse = [](std::string_view const s) {
223 return s == "zero" ? 0.0
224 : s == "one" ? 1.0
225 : s == "two" ? 2.0
226 : s == "three" ? 3.0
227 : s == "four" ? 4.0
228 : s == "five" ? 5.0
229 : s == "six" ? 6.0
230 : s == "seven" ? 7.0
231 : s == "eight" ? 8.0
232 : s == "nine" ? 9.0
233 : (assert(false), 10.0); // the number here is arbitrary
234 };
235
236 {
237 auto data = std::vector<std::string>{"five", "three", "two", "six", "one", "four"};
238 auto range = data | std::views::transform(parse);
239 check(range, 0, std::plus(), triangular_sum(range));
240 }
241
242 {
243 auto data = std::string("five three two six one four");
244 auto to_string_view = [](auto&& r) {
245 auto const n = std::ranges::distance(r);
246 return std::string_view(&*r.begin(), n);
247 };
248 auto range =
249 std::views::lazy_split(data, ' ') | std::views::transform(to_string_view) | std::views::transform(parse);
250 check(range, 0, std::plus(), triangular_sum(range));
251 }
252}
253
254constexpr bool test_case() {
255 empty_range_test_case();
256 common_range_test_case();
257 non_common_range_test_case();
258 return true;
259}
260
261// Most containers aren't constexpr
262void runtime_only_test_case() {
263#if !defined(TEST_HAS_NO_LOCALIZATION)
264 { // istream_view is a genuine input range and needs specific handling.
265 constexpr auto raw_data = "Shells Orange Syrup Baratie Cocoyashi Loguetown";
266 constexpr auto expected = "WindmillShellsOrangeSyrupBaratieCocoyashiLoguetown";
267 auto const init = std::string("Windmill");
268
269 {
270 auto input = std::istringstream(raw_data);
271 auto data = std::views::istream<std::string>(input);
272 is_in_value_result<std::ranges::basic_istream_view<std::string, char>, std::string> decltype(auto) result =
273 fold_left_with_iter(data.begin(), data.end(), init, std::plus());
274
275 assert(result.in == data.end());
276 assert(result.value == expected);
277 }
278
279 {
280 auto input = std::istringstream(raw_data);
281 auto data = std::views::istream<std::string>(input);
282 is_in_value_result<std::ranges::basic_istream_view<std::string, char>, std::string> decltype(auto) result =
283 fold_left_with_iter(data, init, std::plus());
284 assert(result.in == data.end());
285 assert(result.value == expected);
286 }
287
288 {
289 auto input = std::istringstream(raw_data);
290 auto data = std::views::istream<std::string>(input);
291 assert(fold_left(data.begin(), data.end(), init, std::plus()) == expected);
292 }
293
294 {
295 auto input = std::istringstream(raw_data);
296 auto data = std::views::istream<std::string>(input);
297 assert(fold_left(data, init, std::plus()) == expected);
298 }
299 }
300#endif
301 {
302 auto const data = std::forward_list<int>{1, 3, 5, 7, 9};
303 auto const n = std::ranges::distance(data);
304 auto const expected = static_cast<float>(n * n); // sum of n consecutive odd numbers = n^2
305 check(data, 0.0f, std::plus(), expected);
306 }
307
308 {
309 auto const data = std::list<int>{2, 4, 6, 8, 10, 12};
310 auto const expected = triangular_sum(data);
311 check(data, 0, std::plus<long>(), static_cast<long>(expected));
312 }
313
314 {
315 auto const data = std::deque<double>{-1.1, -2.2, -3.3, -4.4, -5.5, -6.6};
316 auto plus = [](int const x, double const y) { return x + y; };
317 auto const expected = -21.6; // int( 0.0) + -1.1 = 0 + -1.1 = -1.1
318 // int(- 1.1) + -2.2 = - 1 + -2.2 = -3.2
319 // int(- 3.2) + -3.3 = - 3 + -3.3 = -6.3
320 // int(- 6.3) + -4.4 = - 6 + -4.4 = -10.4
321 // int(-10.4) + -5.5 = -10 + -5.5 = -15.5
322 // int(-15.5) + -6.6 = -15 + -6.6 = -21.6.
323 check(data, 0.0, plus, expected);
324 }
325}
326
327int main(int, char**) {
328 test_case();
329 static_assert(test_case());
330 runtime_only_test_case();
331 return 0;
332}
333

source code of libcxx/test/std/algorithms/alg.nonmodifying/alg.fold/left_folds.pass.cpp