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