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