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