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