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_SUBRANGE_H 10 #define _LIBCPP___RANGES_SUBRANGE_H 11 12 #include <__config> 13 #include <__iterator/concepts.h> 14 #include <__iterator/incrementable_traits.h> 15 #include <__iterator/iterator_traits.h> 16 #include <__iterator/advance.h> 17 #include <__ranges/access.h> 18 #include <__ranges/concepts.h> 19 #include <__ranges/dangling.h> 20 #include <__ranges/enable_borrowed_range.h> 21 #include <__ranges/size.h> 22 #include <__ranges/view_interface.h> 23 #include <concepts> 24 #include <type_traits> 25 26 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 27 #pragma GCC system_header 28 #endif 29 30 _LIBCPP_PUSH_MACROS 31 #include <__undef_macros> 32 33 _LIBCPP_BEGIN_NAMESPACE_STD 34 35 #if !defined(_LIBCPP_HAS_NO_RANGES) 36 37 // clang-format off 38 namespace ranges { 39 template<class _From, class _To> 40 concept __convertible_to_non_slicing = 41 convertible_to<_From, _To> && 42 // If they're both pointers, they must have the same element type. 43 !(is_pointer_v<decay_t<_From>> && 44 is_pointer_v<decay_t<_To>> && 45 __different_from<remove_pointer_t<decay_t<_From>>, remove_pointer_t<decay_t<_To>>>); 46 47 template<class _Tp> 48 concept __pair_like = 49 !is_reference_v<_Tp> && requires(_Tp __t) { 50 typename tuple_size<_Tp>::type; // Ensures `tuple_size<T>` is complete. 51 requires derived_from<tuple_size<_Tp>, integral_constant<size_t, 2>>; 52 typename tuple_element_t<0, remove_const_t<_Tp>>; 53 typename tuple_element_t<1, remove_const_t<_Tp>>; 54 { _VSTD::get<0>(__t) } -> convertible_to<const tuple_element_t<0, _Tp>&>; 55 { _VSTD::get<1>(__t) } -> convertible_to<const tuple_element_t<1, _Tp>&>; 56 }; 57 58 template<class _Pair, class _Iter, class _Sent> 59 concept __pair_like_convertible_from = 60 !range<_Pair> && __pair_like<_Pair> && 61 constructible_from<_Pair, _Iter, _Sent> && 62 __convertible_to_non_slicing<_Iter, tuple_element_t<0, _Pair>> && 63 convertible_to<_Sent, tuple_element_t<1, _Pair>>; 64 65 enum class _LIBCPP_ENUM_VIS subrange_kind : bool { unsized, sized }; 66 67 template<class _Iter, class _Sent, bool> 68 struct __subrange_base { 69 static constexpr bool __store_size = false; 70 _Iter __begin_ = _Iter(); 71 _Sent __end_ = _Sent(); 72 73 _LIBCPP_HIDE_FROM_ABI 74 constexpr __subrange_base() = default; 75 76 _LIBCPP_HIDE_FROM_ABI 77 constexpr __subrange_base(_Iter __iter, _Sent __sent, make_unsigned_t<iter_difference_t<_Iter>> = 0) 78 : __begin_(_VSTD::move(__iter)), __end_(__sent) { } 79 }; 80 81 template<class _Iter, class _Sent> 82 struct __subrange_base<_Iter, _Sent, true> { 83 static constexpr bool __store_size = true; 84 _Iter __begin_ = _Iter(); 85 _Sent __end_ = _Sent(); 86 make_unsigned_t<iter_difference_t<_Iter>> __size_ = 0; 87 88 _LIBCPP_HIDE_FROM_ABI 89 constexpr __subrange_base() = default; 90 91 _LIBCPP_HIDE_FROM_ABI 92 constexpr __subrange_base(_Iter __iter, _Sent __sent, decltype(__size_) __size) 93 : __begin_(_VSTD::move(__iter)), __end_(__sent), __size_(__size) { } 94 }; 95 96 template<input_or_output_iterator _Iter, sentinel_for<_Iter> _Sent = _Iter, 97 subrange_kind _Kind = sized_sentinel_for<_Sent, _Iter> 98 ? subrange_kind::sized 99 : subrange_kind::unsized> 100 requires (_Kind == subrange_kind::sized || !sized_sentinel_for<_Sent, _Iter>) 101 struct _LIBCPP_TEMPLATE_VIS subrange 102 : public view_interface<subrange<_Iter, _Sent, _Kind>>, 103 private __subrange_base<_Iter, _Sent, _Kind == subrange_kind::sized && !sized_sentinel_for<_Sent, _Iter>> { 104 105 using _Base = __subrange_base<_Iter, _Sent, _Kind == subrange_kind::sized && !sized_sentinel_for<_Sent, _Iter>>; 106 107 _LIBCPP_HIDE_FROM_ABI 108 subrange() requires default_initializable<_Iter> = default; 109 110 _LIBCPP_HIDE_FROM_ABI 111 constexpr subrange(__convertible_to_non_slicing<_Iter> auto __iter, _Sent __sent) 112 requires (!_Base::__store_size) 113 : _Base(_VSTD::move(__iter), __sent) {} 114 115 _LIBCPP_HIDE_FROM_ABI 116 constexpr subrange(__convertible_to_non_slicing<_Iter> auto __iter, _Sent __sent, 117 make_unsigned_t<iter_difference_t<_Iter>> __n) 118 requires (_Kind == subrange_kind::sized) 119 : _Base(_VSTD::move(__iter), __sent, __n) { } 120 121 template<__different_from<subrange> _Range> 122 requires borrowed_range<_Range> && 123 __convertible_to_non_slicing<iterator_t<_Range>, _Iter> && 124 convertible_to<sentinel_t<_Range>, _Sent> 125 _LIBCPP_HIDE_FROM_ABI 126 constexpr subrange(_Range&& __range) 127 requires (!_Base::__store_size) 128 : subrange(ranges::begin(__range), ranges::end(__range)) { } 129 130 template<__different_from<subrange> _Range> 131 requires borrowed_range<_Range> && 132 __convertible_to_non_slicing<iterator_t<_Range>, _Iter> && 133 convertible_to<sentinel_t<_Range>, _Sent> 134 _LIBCPP_HIDE_FROM_ABI 135 constexpr subrange(_Range&& __range) 136 requires _Base::__store_size && sized_range<_Range> 137 : subrange(__range, ranges::size(__range)) { } 138 139 140 template<borrowed_range _Range> 141 requires __convertible_to_non_slicing<iterator_t<_Range>, _Iter> && 142 convertible_to<sentinel_t<_Range>, _Sent> 143 _LIBCPP_HIDE_FROM_ABI 144 constexpr subrange(_Range&& __range, make_unsigned_t<iter_difference_t<_Iter>> __n) 145 requires (_Kind == subrange_kind::sized) 146 : subrange(ranges::begin(__range), ranges::end(__range), __n) { } 147 148 template<__different_from<subrange> _Pair> 149 requires __pair_like_convertible_from<_Pair, const _Iter&, const _Sent&> 150 _LIBCPP_HIDE_FROM_ABI 151 constexpr operator _Pair() const { return _Pair(this->__begin_, this->__end_); } 152 153 _LIBCPP_HIDE_FROM_ABI 154 constexpr _Iter begin() const requires copyable<_Iter> { 155 return this->__begin_; 156 } 157 158 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr _Iter begin() requires (!copyable<_Iter>) { 159 return _VSTD::move(this->__begin_); 160 } 161 162 _LIBCPP_HIDE_FROM_ABI 163 constexpr _Sent end() const { return this->__end_; } 164 165 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr bool empty() const { return this->__begin_ == this->__end_; } 166 167 _LIBCPP_HIDE_FROM_ABI 168 constexpr make_unsigned_t<iter_difference_t<_Iter>> size() const 169 requires (_Kind == subrange_kind::sized) 170 { 171 if constexpr (_Base::__store_size) 172 return this->__size_; 173 else 174 return __to_unsigned_like(this->__end_ - this->__begin_); 175 } 176 177 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr subrange next(iter_difference_t<_Iter> __n = 1) const& 178 requires forward_iterator<_Iter> { 179 auto __tmp = *this; 180 __tmp.advance(__n); 181 return __tmp; 182 } 183 184 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr subrange next(iter_difference_t<_Iter> __n = 1) && { 185 advance(__n); 186 return _VSTD::move(*this); 187 } 188 189 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr subrange prev(iter_difference_t<_Iter> __n = 1) const 190 requires bidirectional_iterator<_Iter> { 191 auto __tmp = *this; 192 __tmp.advance(-__n); 193 return __tmp; 194 } 195 196 _LIBCPP_HIDE_FROM_ABI 197 constexpr subrange& advance(iter_difference_t<_Iter> __n) { 198 if constexpr (bidirectional_iterator<_Iter>) { 199 if (__n < 0) { 200 ranges::advance(this->__begin_, __n); 201 if constexpr (_Base::__store_size) 202 this->__size_ += _VSTD::__to_unsigned_like(-__n); 203 return *this; 204 } 205 } 206 207 auto __d = __n - ranges::advance(this->__begin_, __n, this->__end_); 208 if constexpr (_Base::__store_size) 209 this->__size_ -= _VSTD::__to_unsigned_like(__d); 210 return *this; 211 } 212 }; 213 214 template<input_or_output_iterator _Iter, sentinel_for<_Iter> _Sent> 215 subrange(_Iter, _Sent) -> subrange<_Iter, _Sent>; 216 217 template<input_or_output_iterator _Iter, sentinel_for<_Iter> _Sent> 218 subrange(_Iter, _Sent, make_unsigned_t<iter_difference_t<_Iter>>) 219 -> subrange<_Iter, _Sent, subrange_kind::sized>; 220 221 template<borrowed_range _Range> 222 subrange(_Range&&) -> subrange<iterator_t<_Range>, sentinel_t<_Range>, 223 (sized_range<_Range> || sized_sentinel_for<sentinel_t<_Range>, iterator_t<_Range>>) 224 ? subrange_kind::sized : subrange_kind::unsized>; 225 226 template<borrowed_range _Range> 227 subrange(_Range&&, make_unsigned_t<range_difference_t<_Range>>) 228 -> subrange<iterator_t<_Range>, sentinel_t<_Range>, subrange_kind::sized>; 229 230 template<size_t _Index, class _Iter, class _Sent, subrange_kind _Kind> 231 requires (_Index < 2) 232 _LIBCPP_HIDE_FROM_ABI 233 constexpr auto get(const subrange<_Iter, _Sent, _Kind>& __subrange) { 234 if constexpr (_Index == 0) 235 return __subrange.begin(); 236 else 237 return __subrange.end(); 238 } 239 240 template<size_t _Index, class _Iter, class _Sent, subrange_kind _Kind> 241 requires (_Index < 2) 242 _LIBCPP_HIDE_FROM_ABI 243 constexpr auto get(subrange<_Iter, _Sent, _Kind>&& __subrange) { 244 if constexpr (_Index == 0) 245 return __subrange.begin(); 246 else 247 return __subrange.end(); 248 } 249 250 template<class _Ip, class _Sp, subrange_kind _Kp> 251 inline constexpr bool enable_borrowed_range<subrange<_Ip, _Sp, _Kp>> = true; 252 253 template<range _Rp> 254 using borrowed_subrange_t = _If<borrowed_range<_Rp>, subrange<iterator_t<_Rp> >, dangling>; 255 } // namespace ranges 256 257 using ranges::get; 258 259 // clang-format off 260 261 #endif // !defined(_LIBCPP_HAS_NO_RANGES) 262 263 _LIBCPP_END_NAMESPACE_STD 264 265 _LIBCPP_POP_MACROS 266 267 #endif // _LIBCPP___RANGES_SUBRANGE_H 268