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 <__compare/three_way_comparable.h> 13 #include <__concepts/arithmetic.h> 14 #include <__concepts/constructible.h> 15 #include <__concepts/convertible_to.h> 16 #include <__concepts/copyable.h> 17 #include <__concepts/equality_comparable.h> 18 #include <__concepts/invocable.h> 19 #include <__concepts/same_as.h> 20 #include <__concepts/semiregular.h> 21 #include <__concepts/totally_ordered.h> 22 #include <__config> 23 #include <__debug> 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 !defined(_LIBCPP_HAS_NO_CONCEPTS) && !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 _Bound = unreachable_sentinel_t> 94 requires __weakly_equality_comparable_with<_Start, _Bound> && copyable<_Start> 95 class iota_view : public view_interface<iota_view<_Start, _Bound>> { 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_(_VSTD::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 _Bound __bound_ = _Bound(); 275 276 public: 277 _LIBCPP_HIDE_FROM_ABI 278 __sentinel() = default; 279 constexpr explicit __sentinel(_Bound __bound) : __bound_(_VSTD::move(__bound)) {} 280 281 _LIBCPP_HIDE_FROM_ABI 282 friend constexpr bool operator==(const __iterator& __x, const __sentinel& __y) { 283 return __x.__value_ == __y.__bound_; 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<_Bound, _Start> 289 { 290 return __x.__value_ - __y.__bound_; 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<_Bound, _Start> 296 { 297 return -(__y - __x); 298 } 299 }; 300 301 _Start __value_ = _Start(); 302 _Bound __bound_ = _Bound(); 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_(_VSTD::move(__value)) { } 310 311 _LIBCPP_HIDE_FROM_ABI 312 constexpr iota_view(type_identity_t<_Start> __value, type_identity_t<_Bound> __bound) 313 : __value_(_VSTD::move(__value)), __bound_(_VSTD::move(__bound)) { 314 // Validate the precondition if possible. 315 if constexpr (totally_ordered_with<_Start, _Bound>) { 316 _LIBCPP_ASSERT(ranges::less_equal()(__value_, __bound_), 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, _Bound> 324 : iota_view(_VSTD::move(__first.__value_), _VSTD::move(__last.__value_)) {} 325 326 _LIBCPP_HIDE_FROM_ABI 327 constexpr iota_view(__iterator __first, _Bound __last) 328 requires same_as<_Bound, unreachable_sentinel_t> 329 : iota_view(_VSTD::move(__first.__value_), _VSTD::move(__last)) {} 330 331 _LIBCPP_HIDE_FROM_ABI 332 constexpr iota_view(__iterator __first, __sentinel __last) 333 requires (!same_as<_Start, _Bound> && !same_as<_Start, unreachable_sentinel_t>) 334 : iota_view(_VSTD::move(__first.__value_), _VSTD::move(__last.__bound_)) {} 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<_Bound, unreachable_sentinel_t>) 342 return unreachable_sentinel; 343 else 344 return __sentinel{__bound_}; 345 } 346 347 _LIBCPP_HIDE_FROM_ABI 348 constexpr __iterator end() const requires same_as<_Start, _Bound> { 349 return __iterator{__bound_}; 350 } 351 352 _LIBCPP_HIDE_FROM_ABI 353 constexpr auto size() const 354 requires (same_as<_Start, _Bound> && __advanceable<_Start>) || 355 (integral<_Start> && integral<_Bound>) || 356 sized_sentinel_for<_Bound, _Start> 357 { 358 if constexpr (__integer_like<_Start> && __integer_like<_Bound>) { 359 if (__value_ < 0) { 360 if (__bound_ < 0) { 361 return _VSTD::__to_unsigned_like(-__value_) - _VSTD::__to_unsigned_like(-__bound_); 362 } 363 return _VSTD::__to_unsigned_like(__bound_) + _VSTD::__to_unsigned_like(-__value_); 364 } 365 return _VSTD::__to_unsigned_like(__bound_) - _VSTD::__to_unsigned_like(__value_); 366 } 367 return _VSTD::__to_unsigned_like(__bound_ - __value_); 368 } 369 }; 370 371 template<class _Start, class _Bound> 372 requires (!__integer_like<_Start> || !__integer_like<_Bound> || 373 (__signed_integer_like<_Start> == __signed_integer_like<_Bound>)) 374 iota_view(_Start, _Bound) -> iota_view<_Start, _Bound>; 375 376 template<class _Start, class _Bound> 377 inline constexpr bool enable_borrowed_range<iota_view<_Start, _Bound>> = true; 378 379 namespace views { 380 namespace __iota { 381 struct __fn { 382 template<class _Start> 383 _LIBCPP_HIDE_FROM_ABI 384 constexpr auto operator()(_Start&& __start) const 385 noexcept(noexcept(ranges::iota_view(_VSTD::forward<_Start>(__start)))) 386 -> decltype( ranges::iota_view(_VSTD::forward<_Start>(__start))) 387 { return ranges::iota_view(_VSTD::forward<_Start>(__start)); } 388 389 template<class _Start, class _Bound> 390 _LIBCPP_HIDE_FROM_ABI 391 constexpr auto operator()(_Start&& __start, _Bound&& __bound) const 392 noexcept(noexcept(ranges::iota_view(_VSTD::forward<_Start>(__start), _VSTD::forward<_Bound>(__bound)))) 393 -> decltype( ranges::iota_view(_VSTD::forward<_Start>(__start), _VSTD::forward<_Bound>(__bound))) 394 { return ranges::iota_view(_VSTD::forward<_Start>(__start), _VSTD::forward<_Bound>(__bound)); } 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 // !defined(_LIBCPP_HAS_NO_CONCEPTS) && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) 405 406 _LIBCPP_END_NAMESPACE_STD 407 408 #endif // _LIBCPP___RANGES_IOTA_VIEW_H 409