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_RANGES
11#define _LIBCPP_RANGES
12
13/*
14
15#include <compare> // see [compare.syn]
16#include <initializer_list> // see [initializer.list.syn]
17#include <iterator> // see [iterator.synopsis]
18
19namespace std::ranges {
20 inline namespace unspecified {
21 // [range.access], range access
22 inline constexpr unspecified begin = unspecified;
23 inline constexpr unspecified end = unspecified;
24 inline constexpr unspecified cbegin = unspecified;
25 inline constexpr unspecified cend = unspecified;
26
27 inline constexpr unspecified size = unspecified;
28 inline constexpr unspecified ssize = unspecified;
29 }
30
31 // [range.range], ranges
32 template<class T>
33 concept range = see below;
34
35 template<class T>
36 inline constexpr bool enable_borrowed_range = false;
37
38 template<class T>
39 using iterator_t = decltype(ranges::begin(declval<T&>()));
40 template<range R>
41 using sentinel_t = decltype(ranges::end(declval<R&>()));
42 template<range R>
43 using range_difference_t = iter_difference_t<iterator_t<R>>;
44 template<sized_range R>
45 using range_size_t = decltype(ranges::size(declval<R&>()));
46 template<range R>
47 using range_value_t = iter_value_t<iterator_t<R>>;
48 template<range R>
49 using range_reference_t = iter_reference_t<iterator_t<R>>;
50 template<range R>
51 using range_rvalue_reference_t = iter_rvalue_reference_t<iterator_t<R>>;
52 template <range R>
53 using range_common_reference_t = iter_common_reference_t<iterator_t<R>>;
54
55 // [range.sized], sized ranges
56 template<class>
57 inline constexpr bool disable_sized_range = false;
58
59 template<class T>
60 concept sized_range = ...;
61
62 // [range.view], views
63 template<class T>
64 inline constexpr bool enable_view = ...;
65
66 struct view_base { };
67
68 template<class T>
69 concept view = ...;
70
71 // [range.refinements], other range refinements
72 template<class R, class T>
73 concept output_range = see below;
74
75 template<class T>
76 concept input_range = see below;
77
78 template<class T>
79 concept forward_range = see below;
80
81 template<class T>
82 concept bidirectional_range = see below;
83
84 template<class T>
85 concept random_access_range = see below;
86
87 template<class T>
88 concept contiguous_range = see below;
89
90 template <class _Tp>
91 concept common_range = see below;
92
93 template<class T>
94 concept viewable_range = see below;
95
96 // [range.adaptor.object], range adaptor objects
97 template<class D>
98 requires is_class_v<D> && same_as<D, remove_cv_t<D>>
99 class range_adaptor_closure { }; // Since c++23
100
101 // [view.interface], class template view_interface
102 template<class D>
103 requires is_class_v<D> && same_as<D, remove_cv_t<D>>
104 class view_interface;
105
106 // [range.subrange], sub-ranges
107 enum class subrange_kind : bool { unsized, sized };
108
109 template<input_or_output_iterator I, sentinel_for<I> S = I, subrange_kind K = see below>
110 requires (K == subrange_kind::sized || !sized_sentinel_for<S, I>)
111 class subrange;
112
113 template<class I, class S, subrange_kind K>
114 inline constexpr bool enable_borrowed_range<subrange<I, S, K>> = true;
115
116 // [range.dangling], dangling iterator handling
117 struct dangling;
118
119 // [range.elementsof], class template elements_of
120 template<range R, class Allocator = allocator<byte>>
121 struct elements_of;
122
123 template<range R>
124 using borrowed_iterator_t = see below;
125
126 template<range R>
127 using borrowed_subrange_t = see below;
128
129 // [range.elements], elements view
130 template<input_range V, size_t N>
131 requires see below
132 class elements_view;
133
134 template<class T, size_t N>
135 inline constexpr bool enable_borrowed_range<elements_view<T, N>> =
136 enable_borrowed_range<T>;
137
138 template<class R>
139 using keys_view = elements_view<R, 0>;
140 template<class R>
141 using values_view = elements_view<R, 1>;
142
143 namespace views {
144 template<size_t N>
145 inline constexpr unspecified elements = unspecified;
146 inline constexpr auto keys = elements<0>;
147 inline constexpr auto values = elements<1>;
148 }
149
150 // [range.utility.conv], range conversions
151 template<class C, input_range R, class... Args> requires (!view<C>)
152 constexpr C to(R&& r, Args&&... args); // Since C++23
153 template<template<class...> class C, input_range R, class... Args>
154 constexpr auto to(R&& r, Args&&... args); // Since C++23
155 template<class C, class... Args> requires (!view<C>)
156 constexpr auto to(Args&&... args); // Since C++23
157 template<template<class...> class C, class... Args>
158 constexpr auto to(Args&&... args); // Since C++23
159
160 // [range.empty], empty view
161 template<class T>
162 requires is_object_v<T>
163 class empty_view;
164
165 template<class T>
166 inline constexpr bool enable_borrowed_range<empty_view<T>> = true;
167
168 namespace views {
169 template<class T>
170 inline constexpr empty_view<T> empty{};
171 }
172
173 // [range.all], all view
174 namespace views {
175 inline constexpr unspecified all = unspecified;
176
177 template<viewable_range R>
178 using all_t = decltype(all(declval<R>()));
179 }
180
181 template<range R>
182 requires is_object_v<R>
183 class ref_view;
184
185 template<class T>
186 inline constexpr bool enable_borrowed_range<ref_view<T>> = true;
187
188 template<range R>
189 requires see below
190 class owning_view;
191
192 template<class T>
193 inline constexpr bool enable_borrowed_range<owning_view<T>> = enable_borrowed_range<T>;
194
195 // [range.filter], filter view
196 template<input_range V, indirect_unary_predicate<iterator_t<V>> Pred>
197 requires view<V> && is_object_v<Pred>
198 class filter_view;
199
200 namespace views {
201 inline constexpr unspecified filter = unspecified;
202 }
203
204 // [range.concat], concat view
205 template <input_range... Views>
206 requires (view<Views> && ...) && (sizeof...(Views) > 0) &&
207 concatable<Views...>
208 class concat_view;
209
210 namespace views {
211 inline constexpr unspecified concat = unspecified;
212 }
213
214 // [range.drop], drop view
215 template<view V>
216 class drop_view;
217
218 template<class T>
219 inline constexpr bool enable_borrowed_range<drop_view<T>> = enable_borrowed_range<T>;
220
221 // [range.drop.while], drop while view
222 template<view V, class Pred>
223 requires input_range<V> && is_object_v<Pred> &&
224 indirect_unary_predicate<const Pred, iterator_t<V>>
225 class drop_while_view;
226
227 template<class T, class Pred>
228 inline constexpr bool enable_borrowed_range<drop_while_view<T, Pred>> =
229 enable_borrowed_range<T>;
230
231 namespace views { inline constexpr unspecified drop_while = unspecified; }
232
233 // [range.transform], transform view
234 template<input_range V, copy_constructible F>
235 requires view<V> && is_object_v<F> &&
236 regular_invocable<F&, range_reference_t<V>> &&
237 can-reference<invoke_result_t<F&, range_reference_t<V>>>
238 class transform_view;
239
240 // [range.counted], counted view
241 namespace views { inline constexpr unspecified counted = unspecified; }
242
243 // [range.common], common view
244 template<view V>
245 requires (!common_range<V> && copyable<iterator_t<V>>)
246 class common_view;
247
248 // [range.reverse], reverse view
249 template<view V>
250 requires bidirectional_range<V>
251 class reverse_view;
252
253 template<class T>
254 inline constexpr bool enable_borrowed_range<reverse_view<T>> = enable_borrowed_range<T>;
255
256 template<class T>
257 inline constexpr bool enable_borrowed_range<common_view<T>> = enable_borrowed_range<T>;
258
259 // [range.take], take view
260 template<view> class take_view;
261
262 template<class T>
263 inline constexpr bool enable_borrowed_range<take_view<T>> = enable_borrowed_range<T>;
264
265 // [range.take.while], take while view
266 template<view V, class Pred>
267 requires input_range<V> && is_object_v<Pred> &&
268 indirect_unary_predicate<const Pred, iterator_t<V>>
269 class take_while_view;
270
271 namespace views { inline constexpr unspecified take_while = unspecified; }
272
273 template<copy_constructible T>
274 requires is_object_v<T>
275 class single_view;
276
277 template<weakly_incrementable W, semiregular Bound = unreachable_sentinel_t>
278 requires weakly-equality-comparable-with<W, Bound> && copyable<W>
279 class iota_view;
280
281 template<class W, class Bound>
282 inline constexpr bool enable_borrowed_range<iota_view<W, Bound>> = true;
283
284 namespace views {
285 inline constexpr unspecified iota = unspecified;
286 inline constexpr unspecified indices = unspecified; // Since C++26
287 }
288
289 // [range.repeat], repeat view
290 template<class T>
291 concept integer-like-with-usable-difference-type = // exposition only
292 is-signed-integer-like<T> || (is-integer-like<T> && weakly_incrementable<T>);
293
294 template<move_constructible T, semiregular Bound = unreachable_sentinel_t>
295 requires (is_object_v<T> && same_as<T, remove_cv_t<T>> &&
296 (integer-like-with-usable-difference-type<Bound> ||
297 same_as<Bound, unreachable_sentinel_t>))
298 class repeat_view;
299
300 namespace views { inline constexpr unspecified repeat = unspecified; }
301
302 // [range.join], join view
303 template<input_range V>
304 requires view<V> && input_range<range_reference_t<V>>
305 class join_view;
306
307 // [range.join.with], join with view
308 template<input_range V, forward_range Pattern>
309 requires view<V> && input_range<range_reference_t<V>>
310 && view<Pattern>
311 && concatable<range_reference_t<V>, Pattern>
312 class join_with_view; // since C++23
313
314 namespace views { inline constexpr unspecified join_with = unspecified; } // since C++23
315
316 // [range.lazy.split], lazy split view
317 template<class R>
318 concept tiny-range = see below; // exposition only
319
320 template<input_range V, forward_range Pattern>
321 requires view<V> && view<Pattern> &&
322 indirectly_comparable<iterator_t<V>, iterator_t<Pattern>, ranges::equal_to> &&
323 (forward_range<V> || tiny-range<Pattern>)
324 class lazy_split_view;
325
326 // [range.split], split view
327 template<forward_range V, forward_range Pattern>
328 requires view<V> && view<Pattern> &&
329 indirectly_comparable<iterator_t<V>, iterator_t<Pattern>, ranges::equal_to>
330 class split_view;
331
332 namespace views {
333 inline constexpr unspecified lazy_split = unspecified;
334 inline constexpr unspecified split = unspecified;
335 }
336
337 // [range.istream], istream view
338 template<movable Val, class CharT, class Traits = char_traits<CharT>>
339 requires see below
340 class basic_istream_view;
341
342 template<class Val>
343 using istream_view = basic_istream_view<Val, char>;
344
345 template<class Val>
346 using wistream_view = basic_istream_view<Val, wchar_t>;
347
348 namespace views { template<class T> inline constexpr unspecified istream = unspecified; }
349
350 // [range.enumerate], enumerate view
351 template<view View>
352 requires see below
353 class enumerate_view; // since C++23
354
355 template<class View>
356 constexpr bool enable_borrowed_range<enumerate_view<View>> = // since C++23
357 enable_borrowed_range<View>;
358
359 namespace views { inline constexpr unspecified enumerate = unspecified; } // since C++23
360
361 // [range.zip], zip view
362 template<input_range... Views>
363 requires (view<Views> && ...) && (sizeof...(Views) > 0)
364 class zip_view; // C++23
365
366 template<class... Views>
367 inline constexpr bool enable_borrowed_range<zip_view<Views...>> = // C++23
368 (enable_borrowed_range<Views> && ...);
369
370 namespace views { inline constexpr unspecified zip = unspecified; } // C++23
371
372 // [range.zip.transform], zip transform view
373 template<move_constructible F, input_range... Views>
374 requires (view<Views> && ...) && (sizeof...(Views) > 0) && is_object_v<F> &&
375 regular_invocable<F&, range_reference_t<Views>...> &&
376 can-reference<invoke_result_t<F&, range_reference_t<Views>...>>
377 class zip_transform_view; // C++23
378
379 namespace views { inline constexpr unspecified zip_transform = unspecified; } // C++23
380
381 // [range.adjacent], adjacent view
382 template<forward_range V, size_t N>
383 requires view<V> && (N > 0)
384 class adjacent_view;
385
386 template<class V, size_t N>
387 constexpr bool enable_borrowed_range<adjacent_view<V, N>> =
388 enable_borrowed_range<V>;
389
390 namespace views {
391 template<size_t N>
392 constexpr unspecified adjacent = unspecified;
393 inline constexpr auto pairwise = adjacent<2>;
394 }
395
396 // [range.adjacent.transform], adjacent transform view
397 template<forward_range V, move_constructible F, size_t N>
398 requires see below
399 class adjacent_transform_view;
400
401 namespace views {
402 template<size_t N>
403 constexpr unspecified adjacent_transform = unspecified;
404 inline constexpr auto pairwise_transform = adjacent_transform<2>;
405 }
406
407 // [range.as.rvalue]
408 template <view V>
409 requires input_range<V>
410 class as_rvalue_view; // C++23
411
412 namespace views { inline constexpr unspecified as_rvalue ) unspecified; } // C++23
413
414 [range.chunk.by]
415 template<forward_range V, indirect_binary_predicate<iterator_t<V>, iterator_t<V>> Pred>
416 requires view<V> && is_object_v<Pred>
417 class chunk_by_view; // C++23
418
419 namespace views { inline constexpr unspecified chunk_by = unspecified; } // C++23
420
421 // [range.stride.view], stride view
422 template<input_range V>
423 requires view<V>
424 class stride_view; // C++23
425
426 template<class V>
427 constexpr bool enable_borrowed_range<stride_view<V>> =
428 enable_borrowed_range<V>; // C++23
429
430 namespace views { inline constexpr unspecified stride = unspecified; } // C++23
431}
432
433namespace std {
434 namespace views = ranges::views;
435
436 template<class T> struct tuple_size;
437 template<size_t I, class T> struct tuple_element;
438
439 template<class I, class S, ranges::subrange_kind K>
440 struct tuple_size<ranges::subrange<I, S, K>>
441 : integral_constant<size_t, 2> {};
442
443 template<class I, class S, ranges::subrange_kind K>
444 struct tuple_element<0, ranges::subrange<I, S, K>> {
445 using type = I;
446 };
447
448 template<class I, class S, ranges::subrange_kind K>
449 struct tuple_element<1, ranges::subrange<I, S, K>> {
450 using type = S;
451 };
452
453 template<class I, class S, ranges::subrange_kind K>
454 struct tuple_element<0, const ranges::subrange<I, S, K>> {
455 using type = I;
456 };
457
458 template<class I, class S, ranges::subrange_kind K>
459 struct tuple_element<1, const ranges::subrange<I, S, K>> {
460 using type = S;
461 };
462
463 struct from_range_t { explicit from_range_t() = default; }; // Since C++23
464 inline constexpr from_range_t from_range{}; // Since C++23
465}
466*/
467
468#if __cplusplus < 201103L && defined(_LIBCPP_USE_FROZEN_CXX03_HEADERS)
469# include <__cxx03/__config>
470#else
471# include <__config>
472
473# if _LIBCPP_STD_VER >= 20
474# include <__ranges/access.h>
475# include <__ranges/all.h>
476# include <__ranges/common_view.h>
477# include <__ranges/concepts.h>
478# include <__ranges/counted.h>
479# include <__ranges/dangling.h>
480# include <__ranges/data.h>
481# include <__ranges/drop_view.h>
482# include <__ranges/drop_while_view.h>
483# include <__ranges/elements_of.h>
484# include <__ranges/elements_view.h>
485# include <__ranges/empty.h>
486# include <__ranges/empty_view.h>
487# include <__ranges/enable_borrowed_range.h>
488# include <__ranges/enable_view.h>
489# include <__ranges/filter_view.h>
490# include <__ranges/iota_view.h>
491# include <__ranges/join_view.h>
492# include <__ranges/lazy_split_view.h>
493# include <__ranges/rbegin.h>
494# include <__ranges/ref_view.h>
495# include <__ranges/rend.h>
496# include <__ranges/reverse_view.h>
497# include <__ranges/single_view.h>
498# include <__ranges/size.h>
499# include <__ranges/split_view.h>
500# include <__ranges/subrange.h>
501# include <__ranges/take_view.h>
502# include <__ranges/take_while_view.h>
503# include <__ranges/transform_view.h>
504# include <__ranges/view_interface.h>
505# include <__ranges/views.h>
506
507# if _LIBCPP_HAS_LOCALIZATION
508# include <__ranges/istream_view.h>
509# endif
510# endif
511
512# if _LIBCPP_STD_VER >= 23
513# include <__ranges/adjacent_transform_view.h>
514# include <__ranges/adjacent_view.h>
515# include <__ranges/as_rvalue_view.h>
516# include <__ranges/chunk_by_view.h>
517# include <__ranges/enumerate_view.h>
518# include <__ranges/from_range.h>
519# include <__ranges/join_with_view.h>
520# include <__ranges/repeat_view.h>
521# include <__ranges/stride_view.h>
522# include <__ranges/to.h>
523# include <__ranges/zip_transform_view.h>
524# include <__ranges/zip_view.h>
525# endif
526
527# if _LIBCPP_STD_VER >= 26
528# include <__ranges/concat_view.h>
529# endif
530
531# include <version>
532
533// standard-mandated includes
534
535// [ranges.syn]
536# include <compare>
537# include <initializer_list>
538# include <iterator>
539
540// [tuple.helper]
541# include <__tuple/tuple_element.h>
542# include <__tuple/tuple_size.h>
543
544# if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
545# pragma GCC system_header
546# endif
547
548# if defined(_LIBCPP_KEEP_TRANSITIVE_INCLUDES_LLVM23) && _LIBCPP_STD_VER <= 20
549# include <cstdlib>
550# include <iosfwd>
551# include <type_traits>
552# endif
553#endif // __cplusplus < 201103L && defined(_LIBCPP_USE_FROZEN_CXX03_HEADERS)
554
555#endif // _LIBCPP_RANGES
556