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 #ifndef _LIBCPP___RANGES_IOTA_VIEW_H 10 #define _LIBCPP___RANGES_IOTA_VIEW_H 11 12 #include <__assert> 13 #include <__compare/three_way_comparable.h> 14 #include <__concepts/arithmetic.h> 15 #include <__concepts/constructible.h> 16 #include <__concepts/convertible_to.h> 17 #include <__concepts/copyable.h> 18 #include <__concepts/equality_comparable.h> 19 #include <__concepts/invocable.h> 20 #include <__concepts/same_as.h> 21 #include <__concepts/semiregular.h> 22 #include <__concepts/totally_ordered.h> 23 #include <__config> 24 #include <__functional/ranges_operations.h> 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/copyable_box.h> 30 #include <__ranges/enable_borrowed_range.h> 31 #include <__ranges/view_interface.h> 32 #include <__utility/forward.h> 33 #include <__utility/move.h> 34 #include <type_traits> 35 36 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 37 # pragma GCC system_header 38 #endif 39 40 _LIBCPP_BEGIN_NAMESPACE_STD 41 42 #if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) 43 44 namespace ranges { 45 template<class _Int> 46 struct __get_wider_signed { 47 static auto __call() { 48 if constexpr (sizeof(_Int) < sizeof(short)) return type_identity<short>{}; 49 else if constexpr (sizeof(_Int) < sizeof(int)) return type_identity<int>{}; 50 else if constexpr (sizeof(_Int) < sizeof(long)) return type_identity<long>{}; 51 else return type_identity<long long>{}; 52 53 static_assert(sizeof(_Int) <= sizeof(long long), 54 "Found integer-like type that is bigger than largest integer like type."); 55 } 56 57 using type = typename decltype(__call())::type; 58 }; 59 60 template<class _Start> 61 using _IotaDiffT = typename _If< 62 (!integral<_Start> || sizeof(iter_difference_t<_Start>) > sizeof(_Start)), 63 type_identity<iter_difference_t<_Start>>, 64 __get_wider_signed<_Start> 65 >::type; 66 67 template<class _Iter> 68 concept __decrementable = incrementable<_Iter> && requires(_Iter __i) { 69 { --__i } -> same_as<_Iter&>; 70 { __i-- } -> same_as<_Iter>; 71 }; 72 73 template<class _Iter> 74 concept __advanceable = 75 __decrementable<_Iter> && totally_ordered<_Iter> && 76 requires(_Iter __i, const _Iter __j, const _IotaDiffT<_Iter> __n) { 77 { __i += __n } -> same_as<_Iter&>; 78 { __i -= __n } -> same_as<_Iter&>; 79 _Iter(__j + __n); 80 _Iter(__n + __j); 81 _Iter(__j - __n); 82 { __j - __j } -> convertible_to<_IotaDiffT<_Iter>>; 83 }; 84 85 template<class> 86 struct __iota_iterator_category {}; 87 88 template<incrementable _Tp> 89 struct __iota_iterator_category<_Tp> { 90 using iterator_category = input_iterator_tag; 91 }; 92 93 template <weakly_incrementable _Start, semiregular _BoundSentinel = unreachable_sentinel_t> 94 requires __weakly_equality_comparable_with<_Start, _BoundSentinel> && copyable<_Start> 95 class iota_view : public view_interface<iota_view<_Start, _BoundSentinel>> { 96 struct __iterator : public __iota_iterator_category<_Start> { 97 friend class iota_view; 98 99 using iterator_concept = 100 _If<__advanceable<_Start>, random_access_iterator_tag, 101 _If<__decrementable<_Start>, bidirectional_iterator_tag, 102 _If<incrementable<_Start>, forward_iterator_tag, 103 /*Else*/ input_iterator_tag>>>; 104 105 using value_type = _Start; 106 using difference_type = _IotaDiffT<_Start>; 107 108 _Start __value_ = _Start(); 109 110 _LIBCPP_HIDE_FROM_ABI 111 __iterator() requires default_initializable<_Start> = default; 112 113 _LIBCPP_HIDE_FROM_ABI 114 constexpr explicit __iterator(_Start __value) : __value_(std::move(__value)) {} 115 116 _LIBCPP_HIDE_FROM_ABI 117 constexpr _Start operator*() const noexcept(is_nothrow_copy_constructible_v<_Start>) { 118 return __value_; 119 } 120 121 _LIBCPP_HIDE_FROM_ABI 122 constexpr __iterator& operator++() { 123 ++__value_; 124 return *this; 125 } 126 127 _LIBCPP_HIDE_FROM_ABI 128 constexpr void operator++(int) { ++*this; } 129 130 _LIBCPP_HIDE_FROM_ABI 131 constexpr __iterator operator++(int) requires incrementable<_Start> { 132 auto __tmp = *this; 133 ++*this; 134 return __tmp; 135 } 136 137 _LIBCPP_HIDE_FROM_ABI 138 constexpr __iterator& operator--() requires __decrementable<_Start> { 139 --__value_; 140 return *this; 141 } 142 143 _LIBCPP_HIDE_FROM_ABI 144 constexpr __iterator operator--(int) requires __decrementable<_Start> { 145 auto __tmp = *this; 146 --*this; 147 return __tmp; 148 } 149 150 _LIBCPP_HIDE_FROM_ABI 151 constexpr __iterator& operator+=(difference_type __n) 152 requires __advanceable<_Start> 153 { 154 if constexpr (__integer_like<_Start> && !__signed_integer_like<_Start>) { 155 if (__n >= difference_type(0)) { 156 __value_ += static_cast<_Start>(__n); 157 } else { 158 __value_ -= static_cast<_Start>(-__n); 159 } 160 } else { 161 __value_ += __n; 162 } 163 return *this; 164 } 165 166 _LIBCPP_HIDE_FROM_ABI 167 constexpr __iterator& operator-=(difference_type __n) 168 requires __advanceable<_Start> 169 { 170 if constexpr (__integer_like<_Start> && !__signed_integer_like<_Start>) { 171 if (__n >= difference_type(0)) { 172 __value_ -= static_cast<_Start>(__n); 173 } else { 174 __value_ += static_cast<_Start>(-__n); 175 } 176 } else { 177 __value_ -= __n; 178 } 179 return *this; 180 } 181 182 _LIBCPP_HIDE_FROM_ABI 183 constexpr _Start operator[](difference_type __n) const 184 requires __advanceable<_Start> 185 { 186 return _Start(__value_ + __n); 187 } 188 189 _LIBCPP_HIDE_FROM_ABI 190 friend constexpr bool operator==(const __iterator& __x, const __iterator& __y) 191 requires equality_comparable<_Start> 192 { 193 return __x.__value_ == __y.__value_; 194 } 195 196 _LIBCPP_HIDE_FROM_ABI 197 friend constexpr bool operator<(const __iterator& __x, const __iterator& __y) 198 requires totally_ordered<_Start> 199 { 200 return __x.__value_ < __y.__value_; 201 } 202 203 _LIBCPP_HIDE_FROM_ABI 204 friend constexpr bool operator>(const __iterator& __x, const __iterator& __y) 205 requires totally_ordered<_Start> 206 { 207 return __y < __x; 208 } 209 210 _LIBCPP_HIDE_FROM_ABI 211 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 218 friend constexpr bool operator>=(const __iterator& __x, const __iterator& __y) 219 requires totally_ordered<_Start> 220 { 221 return !(__x < __y); 222 } 223 224 friend constexpr auto operator<=>(const __iterator& __x, const __iterator& __y) 225 requires totally_ordered<_Start> && three_way_comparable<_Start> 226 { 227 return __x.__value_ <=> __y.__value_; 228 } 229 230 _LIBCPP_HIDE_FROM_ABI 231 friend constexpr __iterator operator+(__iterator __i, difference_type __n) 232 requires __advanceable<_Start> 233 { 234 __i += __n; 235 return __i; 236 } 237 238 _LIBCPP_HIDE_FROM_ABI 239 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 246 friend constexpr __iterator operator-(__iterator __i, difference_type __n) 247 requires __advanceable<_Start> 248 { 249 __i -= __n; 250 return __i; 251 } 252 253 _LIBCPP_HIDE_FROM_ABI 254 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 278 __sentinel() = default; 279 constexpr explicit __sentinel(_BoundSentinel __bound_sentinel) : __bound_sentinel_(std::move(__bound_sentinel)) {} 280 281 _LIBCPP_HIDE_FROM_ABI 282 friend constexpr bool operator==(const __iterator& __x, const __sentinel& __y) { 283 return __x.__value_ == __y.__bound_sentinel_; 284 } 285 286 _LIBCPP_HIDE_FROM_ABI 287 friend constexpr iter_difference_t<_Start> 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 294 friend constexpr iter_difference_t<_Start> 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 306 iota_view() requires default_initializable<_Start> = default; 307 308 _LIBCPP_HIDE_FROM_ABI 309 constexpr explicit iota_view(_Start __value) : __value_(std::move(__value)) { } 310 311 _LIBCPP_HIDE_FROM_ABI 312 constexpr 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(ranges::less_equal()(__value_, __bound_sentinel_), 317 "Precondition violated: value is greater than bound."); 318 } 319 } 320 321 _LIBCPP_HIDE_FROM_ABI 322 constexpr iota_view(__iterator __first, __iterator __last) 323 requires same_as<_Start, _BoundSentinel> 324 : iota_view(std::move(__first.__value_), std::move(__last.__value_)) {} 325 326 _LIBCPP_HIDE_FROM_ABI 327 constexpr iota_view(__iterator __first, _BoundSentinel __last) 328 requires same_as<_BoundSentinel, unreachable_sentinel_t> 329 : iota_view(std::move(__first.__value_), std::move(__last)) {} 330 331 _LIBCPP_HIDE_FROM_ABI 332 constexpr iota_view(__iterator __first, __sentinel __last) 333 requires(!same_as<_Start, _BoundSentinel> && !same_as<_Start, unreachable_sentinel_t>) 334 : iota_view(std::move(__first.__value_), std::move(__last.__bound_sentinel_)) {} 335 336 _LIBCPP_HIDE_FROM_ABI 337 constexpr __iterator begin() const { return __iterator{__value_}; } 338 339 _LIBCPP_HIDE_FROM_ABI 340 constexpr auto end() const { 341 if constexpr (same_as<_BoundSentinel, unreachable_sentinel_t>) 342 return unreachable_sentinel; 343 else 344 return __sentinel{__bound_sentinel_}; 345 } 346 347 _LIBCPP_HIDE_FROM_ABI 348 constexpr __iterator end() const 349 requires same_as<_Start, _BoundSentinel> 350 { 351 return __iterator{__bound_sentinel_}; 352 } 353 354 _LIBCPP_HIDE_FROM_ABI 355 constexpr auto size() const 356 requires(same_as<_Start, _BoundSentinel> && __advanceable<_Start>) || 357 (integral<_Start> && integral<_BoundSentinel>) || sized_sentinel_for<_BoundSentinel, _Start> 358 { 359 if constexpr (__integer_like<_Start> && __integer_like<_BoundSentinel>) { 360 if (__value_ < 0) { 361 if (__bound_sentinel_ < 0) { 362 return std::__to_unsigned_like(-__value_) - std::__to_unsigned_like(-__bound_sentinel_); 363 } 364 return std::__to_unsigned_like(__bound_sentinel_) + std::__to_unsigned_like(-__value_); 365 } 366 return std::__to_unsigned_like(__bound_sentinel_) - std::__to_unsigned_like(__value_); 367 } 368 return std::__to_unsigned_like(__bound_sentinel_ - __value_); 369 } 370 }; 371 372 template <class _Start, class _BoundSentinel> 373 requires(!__integer_like<_Start> || !__integer_like<_BoundSentinel> || 374 (__signed_integer_like<_Start> == __signed_integer_like<_BoundSentinel>)) 375 iota_view(_Start, _BoundSentinel) -> iota_view<_Start, _BoundSentinel>; 376 377 template <class _Start, class _BoundSentinel> 378 inline constexpr bool enable_borrowed_range<iota_view<_Start, _BoundSentinel>> = true; 379 380 namespace views { 381 namespace __iota { 382 struct __fn { 383 template<class _Start> 384 _LIBCPP_HIDE_FROM_ABI 385 constexpr auto operator()(_Start&& __start) const 386 noexcept(noexcept(ranges::iota_view(std::forward<_Start>(__start)))) 387 -> decltype( ranges::iota_view(std::forward<_Start>(__start))) 388 { return ranges::iota_view(std::forward<_Start>(__start)); } 389 390 template <class _Start, class _BoundSentinel> 391 _LIBCPP_HIDE_FROM_ABI constexpr auto operator()(_Start&& __start, _BoundSentinel&& __bound_sentinel) const 392 noexcept(noexcept(ranges::iota_view(std::forward<_Start>(__start), std::forward<_BoundSentinel>(__bound_sentinel)))) 393 -> decltype( ranges::iota_view(std::forward<_Start>(__start), std::forward<_BoundSentinel>(__bound_sentinel))) 394 { return ranges::iota_view(std::forward<_Start>(__start), std::forward<_BoundSentinel>(__bound_sentinel)); } 395 }; 396 } // namespace __iota 397 398 inline namespace __cpo { 399 inline constexpr auto iota = __iota::__fn{}; 400 } // namespace __cpo 401 } // namespace views 402 } // namespace ranges 403 404 #endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) 405 406 _LIBCPP_END_NAMESPACE_STD 407 408 #endif // _LIBCPP___RANGES_IOTA_VIEW_H 409