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