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_IOTA_VIEW_H
11#define _LIBCPP___RANGES_IOTA_VIEW_H
12
13#include <__assert>
14#include <__compare/three_way_comparable.h>
15#include <__concepts/arithmetic.h>
16#include <__concepts/constructible.h>
17#include <__concepts/convertible_to.h>
18#include <__concepts/copyable.h>
19#include <__concepts/equality_comparable.h>
20#include <__concepts/invocable.h>
21#include <__concepts/same_as.h>
22#include <__concepts/semiregular.h>
23#include <__concepts/totally_ordered.h>
24#include <__config>
25#include <__iterator/concepts.h>
26#include <__iterator/incrementable_traits.h>
27#include <__iterator/iterator_traits.h>
28#include <__iterator/unreachable_sentinel.h>
29#include <__ranges/enable_borrowed_range.h>
30#include <__ranges/movable_box.h>
31#include <__ranges/view_interface.h>
32#include <__type_traits/conditional.h>
33#include <__type_traits/decay.h>
34#include <__type_traits/is_nothrow_constructible.h>
35#include <__type_traits/make_unsigned.h>
36#include <__type_traits/type_identity.h>
37#include <__utility/forward.h>
38#include <__utility/move.h>
39
40#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
41# pragma GCC system_header
42#endif
43
44_LIBCPP_PUSH_MACROS
45#include <__undef_macros>
46
47_LIBCPP_BEGIN_NAMESPACE_STD
48
49#if _LIBCPP_STD_VER >= 20
50
51namespace ranges {
52template <class _Int>
53struct __get_wider_signed {
54 consteval static auto __call() {
55 if constexpr (sizeof(_Int) < sizeof(short))
56 return type_identity<short>{};
57 else if constexpr (sizeof(_Int) < sizeof(int))
58 return type_identity<int>{};
59 else if constexpr (sizeof(_Int) < sizeof(long))
60 return type_identity<long>{};
61 else if constexpr (sizeof(_Int) < sizeof(long long))
62 return type_identity<long long>{};
63# if _LIBCPP_HAS_INT128
64 else if constexpr (sizeof(_Int) <= sizeof(__int128))
65 return type_identity<__int128>{};
66# else
67 else if constexpr (sizeof(_Int) <= sizeof(long long))
68 return type_identity<long long>{};
69# endif
70 else
71 static_assert(false, "Found integer-like type that is bigger than the largest integer like type.");
72 }
73
74 using type = typename decltype(__call())::type;
75};
76
77template <class _Start>
78using _IotaDiffT _LIBCPP_NODEBUG =
79 typename _If< (!integral<_Start> || sizeof(iter_difference_t<_Start>) > sizeof(_Start)),
80 type_identity<iter_difference_t<_Start>>,
81 __get_wider_signed<_Start> >::type;
82
83template <class _Iter>
84concept __decrementable = incrementable<_Iter> && requires(_Iter __i) {
85 { --__i } -> same_as<_Iter&>;
86 { __i-- } -> same_as<_Iter>;
87};
88
89template <class _Iter>
90concept __advanceable =
91 __decrementable<_Iter> && totally_ordered<_Iter> &&
92 requires(_Iter __i, const _Iter __j, const _IotaDiffT<_Iter> __n) {
93 { __i += __n } -> same_as<_Iter&>;
94 { __i -= __n } -> same_as<_Iter&>;
95 _Iter(__j + __n);
96 _Iter(__n + __j);
97 _Iter(__j - __n);
98 { __j - __j } -> convertible_to<_IotaDiffT<_Iter>>;
99 };
100
101template <class>
102struct __iota_iterator_category {};
103
104template <incrementable _Tp>
105struct __iota_iterator_category<_Tp> {
106 using iterator_category = input_iterator_tag;
107};
108
109template <weakly_incrementable _Start, semiregular _BoundSentinel = unreachable_sentinel_t>
110 requires __weakly_equality_comparable_with<_Start, _BoundSentinel> && copyable<_Start>
111class iota_view : public view_interface<iota_view<_Start, _BoundSentinel>> {
112 struct __iterator : public __iota_iterator_category<_Start> {
113 private:
114 _Start __value_ = _Start();
115
116 _LIBCPP_HIDE_FROM_ABI constexpr explicit __iterator(_Start __value) : __value_(std::move(__value)) {}
117
118 public:
119 friend class iota_view;
120
121 using iterator_concept =
122 _If<__advanceable<_Start>,
123 random_access_iterator_tag,
124 _If<__decrementable<_Start>,
125 bidirectional_iterator_tag,
126 _If<incrementable<_Start>,
127 forward_iterator_tag,
128 /*Else*/ input_iterator_tag>>>;
129
130 using value_type = _Start;
131 using difference_type = _IotaDiffT<_Start>;
132
133 _LIBCPP_HIDE_FROM_ABI __iterator()
134 requires default_initializable<_Start>
135 = default;
136
137 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr _Start operator*() const
138 noexcept(is_nothrow_copy_constructible_v<_Start>) {
139 return __value_;
140 }
141
142 _LIBCPP_HIDE_FROM_ABI constexpr __iterator& operator++() {
143 ++__value_;
144 return *this;
145 }
146
147 _LIBCPP_HIDE_FROM_ABI constexpr void operator++(int) { ++*this; }
148
149 _LIBCPP_HIDE_FROM_ABI constexpr __iterator operator++(int)
150 requires incrementable<_Start>
151 {
152 auto __tmp = *this;
153 ++*this;
154 return __tmp;
155 }
156
157 _LIBCPP_HIDE_FROM_ABI constexpr __iterator& operator--()
158 requires __decrementable<_Start>
159 {
160 --__value_;
161 return *this;
162 }
163
164 _LIBCPP_HIDE_FROM_ABI constexpr __iterator operator--(int)
165 requires __decrementable<_Start>
166 {
167 auto __tmp = *this;
168 --*this;
169 return __tmp;
170 }
171
172 _LIBCPP_HIDE_FROM_ABI constexpr __iterator& operator+=(difference_type __n)
173 requires __advanceable<_Start>
174 {
175 if constexpr (__integer_like<_Start> && !__signed_integer_like<_Start>) {
176 if (__n >= difference_type(0)) {
177 __value_ += static_cast<_Start>(__n);
178 } else {
179 __value_ -= static_cast<_Start>(-__n);
180 }
181 } else {
182 __value_ += __n;
183 }
184 return *this;
185 }
186
187 _LIBCPP_HIDE_FROM_ABI constexpr __iterator& operator-=(difference_type __n)
188 requires __advanceable<_Start>
189 {
190 if constexpr (__integer_like<_Start> && !__signed_integer_like<_Start>) {
191 if (__n >= difference_type(0)) {
192 __value_ -= static_cast<_Start>(__n);
193 } else {
194 __value_ += static_cast<_Start>(-__n);
195 }
196 } else {
197 __value_ -= __n;
198 }
199 return *this;
200 }
201
202 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr _Start operator[](difference_type __n) const
203 requires __advanceable<_Start>
204 {
205 return _Start(__value_ + __n);
206 }
207
208 _LIBCPP_HIDE_FROM_ABI friend constexpr bool operator==(const __iterator& __x, const __iterator& __y)
209 requires equality_comparable<_Start>
210 {
211 return __x.__value_ == __y.__value_;
212 }
213
214 _LIBCPP_HIDE_FROM_ABI friend constexpr bool operator<(const __iterator& __x, const __iterator& __y)
215 requires totally_ordered<_Start>
216 {
217 return __x.__value_ < __y.__value_;
218 }
219
220 _LIBCPP_HIDE_FROM_ABI friend constexpr bool operator>(const __iterator& __x, const __iterator& __y)
221 requires totally_ordered<_Start>
222 {
223 return __y < __x;
224 }
225
226 _LIBCPP_HIDE_FROM_ABI friend constexpr bool operator<=(const __iterator& __x, const __iterator& __y)
227 requires totally_ordered<_Start>
228 {
229 return !(__y < __x);
230 }
231
232 _LIBCPP_HIDE_FROM_ABI friend constexpr bool operator>=(const __iterator& __x, const __iterator& __y)
233 requires totally_ordered<_Start>
234 {
235 return !(__x < __y);
236 }
237
238 _LIBCPP_HIDE_FROM_ABI friend constexpr auto operator<=>(const __iterator& __x, const __iterator& __y)
239 requires totally_ordered<_Start> && three_way_comparable<_Start>
240 {
241 return __x.__value_ <=> __y.__value_;
242 }
243
244 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI friend constexpr __iterator operator+(__iterator __i, difference_type __n)
245 requires __advanceable<_Start>
246 {
247 __i += __n;
248 return __i;
249 }
250
251 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI friend constexpr __iterator operator+(difference_type __n, __iterator __i)
252 requires __advanceable<_Start>
253 {
254 return __i + __n;
255 }
256
257 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI friend constexpr __iterator operator-(__iterator __i, difference_type __n)
258 requires __advanceable<_Start>
259 {
260 __i -= __n;
261 return __i;
262 }
263
264 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI friend constexpr difference_type
265 operator-(const __iterator& __x, const __iterator& __y)
266 requires __advanceable<_Start>
267 {
268 if constexpr (__integer_like<_Start>) {
269 if constexpr (__signed_integer_like<_Start>) {
270 return difference_type(difference_type(__x.__value_) - difference_type(__y.__value_));
271 }
272 if (__y.__value_ > __x.__value_) {
273 return difference_type(-difference_type(__y.__value_ - __x.__value_));
274 }
275 return difference_type(__x.__value_ - __y.__value_);
276 }
277 return __x.__value_ - __y.__value_;
278 }
279 };
280
281 struct __sentinel {
282 friend class iota_view;
283
284 private:
285 _BoundSentinel __bound_sentinel_ = _BoundSentinel();
286
287 _LIBCPP_HIDE_FROM_ABI constexpr explicit __sentinel(_BoundSentinel __bound_sentinel)
288 : __bound_sentinel_(std::move(__bound_sentinel)) {}
289
290 public:
291 _LIBCPP_HIDE_FROM_ABI __sentinel() = default;
292
293 _LIBCPP_HIDE_FROM_ABI friend constexpr bool operator==(const __iterator& __x, const __sentinel& __y) {
294 return __x.__value_ == __y.__bound_sentinel_;
295 }
296
297 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI friend constexpr iter_difference_t<_Start>
298 operator-(const __iterator& __x, const __sentinel& __y)
299 requires sized_sentinel_for<_BoundSentinel, _Start>
300 {
301 return __x.__value_ - __y.__bound_sentinel_;
302 }
303
304 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI friend constexpr iter_difference_t<_Start>
305 operator-(const __sentinel& __x, const __iterator& __y)
306 requires sized_sentinel_for<_BoundSentinel, _Start>
307 {
308 return -(__y - __x);
309 }
310 };
311
312 _Start __value_ = _Start();
313 _BoundSentinel __bound_sentinel_ = _BoundSentinel();
314
315public:
316 _LIBCPP_HIDE_FROM_ABI iota_view()
317 requires default_initializable<_Start>
318 = default;
319
320 _LIBCPP_HIDE_FROM_ABI constexpr explicit iota_view(_Start __value) : __value_(std::move(__value)) {}
321
322 _LIBCPP_HIDE_FROM_ABI constexpr explicit iota_view(type_identity_t<_Start> __value,
323 type_identity_t<_BoundSentinel> __bound_sentinel)
324 : __value_(std::move(__value)), __bound_sentinel_(std::move(__bound_sentinel)) {
325 // Validate the precondition if possible.
326 if constexpr (totally_ordered_with<_Start, _BoundSentinel>) {
327 _LIBCPP_ASSERT_VALID_INPUT_RANGE(
328 bool(__value_ <= __bound_sentinel_), "iota_view: bound must be reachable from value");
329 }
330 }
331
332 _LIBCPP_HIDE_FROM_ABI constexpr explicit iota_view(__iterator __first, __iterator __last)
333 requires same_as<_Start, _BoundSentinel>
334 : iota_view(std::move(__first.__value_), std::move(__last.__value_)) {}
335
336 _LIBCPP_HIDE_FROM_ABI constexpr explicit iota_view(__iterator __first, _BoundSentinel __last)
337 requires same_as<_BoundSentinel, unreachable_sentinel_t>
338 : iota_view(std::move(__first.__value_), std::move(__last)) {}
339
340 _LIBCPP_HIDE_FROM_ABI constexpr explicit iota_view(__iterator __first, __sentinel __last)
341 requires(!same_as<_Start, _BoundSentinel> && !same_as<_BoundSentinel, unreachable_sentinel_t>)
342 : iota_view(std::move(__first.__value_), std::move(__last.__bound_sentinel_)) {}
343
344 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr __iterator begin() const { return __iterator{__value_}; }
345
346 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr auto end() const {
347 if constexpr (same_as<_BoundSentinel, unreachable_sentinel_t>)
348 return unreachable_sentinel;
349 else
350 return __sentinel{__bound_sentinel_};
351 }
352
353 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr __iterator end() const
354 requires same_as<_Start, _BoundSentinel>
355 {
356 return __iterator{__bound_sentinel_};
357 }
358
359 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr bool empty() const { return __value_ == __bound_sentinel_; }
360
361 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr auto size() const
362 requires(same_as<_Start, _BoundSentinel> && __advanceable<_Start>) ||
363 (__integer_like<_Start> && __integer_like<_BoundSentinel>) || sized_sentinel_for<_BoundSentinel, _Start>
364 {
365 if constexpr (__integer_like<_Start> && __integer_like<_BoundSentinel>) {
366 return (__value_ < 0)
367 ? ((__bound_sentinel_ < 0)
368 ? std::__to_unsigned_like(-__value_) - std::__to_unsigned_like(-__bound_sentinel_)
369 : std::__to_unsigned_like(__bound_sentinel_) + std::__to_unsigned_like(-__value_))
370 : std::__to_unsigned_like(__bound_sentinel_) - std::__to_unsigned_like(__value_);
371 } else {
372 return std::__to_unsigned_like(__bound_sentinel_ - __value_);
373 }
374 }
375};
376
377template <class _Start, class _BoundSentinel>
378 requires(!__integer_like<_Start> || !__integer_like<_BoundSentinel> ||
379 (__signed_integer_like<_Start> == __signed_integer_like<_BoundSentinel>))
380iota_view(_Start, _BoundSentinel) -> iota_view<_Start, _BoundSentinel>;
381
382template <class _Start, class _BoundSentinel>
383inline constexpr bool enable_borrowed_range<iota_view<_Start, _BoundSentinel>> = true;
384
385namespace views {
386namespace __iota {
387struct __fn {
388 template <class _Start>
389 requires(requires(_Start __s) { ranges::iota_view<decay_t<_Start>>(std::forward<_Start>(__s)); })
390 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr auto operator()(_Start&& __start) const
391 noexcept(noexcept(ranges::iota_view<decay_t<_Start>>(std::forward<_Start>(__start)))) {
392 return ranges::iota_view<decay_t<_Start>>(std::forward<_Start>(__start));
393 }
394
395 template <class _Start, class _BoundSentinel>
396 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr auto
397 operator()(_Start&& __start, _BoundSentinel&& __bound_sentinel) const noexcept(
398 noexcept(ranges::iota_view(std::forward<_Start>(__start), std::forward<_BoundSentinel>(__bound_sentinel))))
399 -> decltype(ranges::iota_view(std::forward<_Start>(__start), std::forward<_BoundSentinel>(__bound_sentinel))) {
400 return ranges::iota_view(std::forward<_Start>(__start), std::forward<_BoundSentinel>(__bound_sentinel));
401 }
402};
403} // namespace __iota
404
405inline namespace __cpo {
406inline constexpr auto iota = __iota::__fn{};
407} // namespace __cpo
408
409# if _LIBCPP_STD_VER >= 26
410
411inline constexpr auto indices = [] [[nodiscard]] (__integer_like auto __size) static {
412 return ranges::views::iota(decltype(__size){}, __size);
413};
414
415# endif
416
417} // namespace views
418} // namespace ranges
419
420#endif // _LIBCPP_STD_VER >= 20
421
422_LIBCPP_END_NAMESPACE_STD
423
424_LIBCPP_POP_MACROS
425
426#endif // _LIBCPP___RANGES_IOTA_VIEW_H
427