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