v1/__ranges/subrange.h

0001 // -*- C++ -*-
0002 //===----------------------------------------------------------------------===//
0003 //
0004 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0005 // See https://llvm.org/LICENSE.txt for license information.
0006 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0007 //
0008 //===----------------------------------------------------------------------===//
0009
0010 #ifndef _LIBCPP___RANGES_SUBRANGE_H
0011 #define _LIBCPP___RANGES_SUBRANGE_H
0012
0013 #include <__assert>
0014 #include <__concepts/constructible.h>
0015 #include <__concepts/convertible_to.h>
0016 #include <__concepts/copyable.h>
0017 #include <__concepts/derived_from.h>
0018 #include <__concepts/different_from.h>
0019 #include <__config>
0020 #include <__cstddef/size_t.h>
0021 #include <__fwd/subrange.h>
0022 #include <__iterator/advance.h>
0023 #include <__iterator/concepts.h>
0024 #include <__iterator/incrementable_traits.h>
0025 #include <__iterator/iterator_traits.h>
0026 #include <__ranges/access.h>
0027 #include <__ranges/concepts.h>
0028 #include <__ranges/dangling.h>
0029 #include <__ranges/enable_borrowed_range.h>
0030 #include <__ranges/size.h>
0031 #include <__ranges/view_interface.h>
0032 #include <__tuple/tuple_element.h>
0033 #include <__tuple/tuple_like_no_subrange.h>
0034 #include <__tuple/tuple_size.h>
0035 #include <__type_traits/conditional.h>
0036 #include <__type_traits/decay.h>
0037 #include <__type_traits/integral_constant.h>
0038 #include <__type_traits/is_pointer.h>
0039 #include <__type_traits/is_reference.h>
0040 #include <__type_traits/make_unsigned.h>
0041 #include <__type_traits/remove_const.h>
0042 #include <__type_traits/remove_pointer.h>
0043 #include <__utility/move.h>
0044
0045 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
0046 #  pragma GCC system_header
0047 #endif
0048
0049 _LIBCPP_PUSH_MACROS
0050 #include <__undef_macros>
0051
0052 _LIBCPP_BEGIN_NAMESPACE_STD
0053
0054 #if _LIBCPP_STD_VER >= 20
0055
0056 namespace ranges {
0057 template <class _From, class _To>
0058 concept __uses_nonqualification_pointer_conversion =
0059     is_pointer_v<_From> && is_pointer_v<_To> &&
0060     !convertible_to<remove_pointer_t<_From> (*)[], remove_pointer_t<_To> (*)[]>;
0061
0062 template <class _From, class _To>
0063 concept __convertible_to_non_slicing =
0064     convertible_to<_From, _To> && !__uses_nonqualification_pointer_conversion<decay_t<_From>, decay_t<_To>>;
0065
0066 template <class _Pair, class _Iter, class _Sent>
0067 concept __pair_like_convertible_from =
0068     !range<_Pair> && __pair_like_no_subrange<_Pair> && constructible_from<_Pair, _Iter, _Sent> &&
0069     __convertible_to_non_slicing<_Iter, tuple_element_t<0, _Pair>> && convertible_to<_Sent, tuple_element_t<1, _Pair>>;
0070
0071 template <input_or_output_iterator _Iter,
0072           sentinel_for<_Iter> _Sent = _Iter,
0073           subrange_kind _Kind       = sized_sentinel_for<_Sent, _Iter> ? subrange_kind::sized : subrange_kind::unsized>
0074   requires(_Kind == subrange_kind::sized || !sized_sentinel_for<_Sent, _Iter>)
0075 class _LIBCPP_TEMPLATE_VIS subrange : public view_interface<subrange<_Iter, _Sent, _Kind>> {
0076 public:
0077   // Note: this is an internal implementation detail that is public only for internal usage.
0078   static constexpr bool _StoreSize = (_Kind == subrange_kind::sized && !sized_sentinel_for<_Sent, _Iter>);
0079
0080 private:
0081   static constexpr bool _MustProvideSizeAtConstruction = !_StoreSize; // just to improve compiler diagnostics
0082   struct _Empty {
0083     _LIBCPP_HIDE_FROM_ABI constexpr _Empty(auto) noexcept {}
0084   };
0085   using _Size _LIBCPP_NODEBUG = conditional_t<_StoreSize, make_unsigned_t<iter_difference_t<_Iter>>, _Empty>;
0086   _LIBCPP_NO_UNIQUE_ADDRESS _Iter __begin_ = _Iter();
0087   _LIBCPP_NO_UNIQUE_ADDRESS _Sent __end_   = _Sent();
0088   _LIBCPP_NO_UNIQUE_ADDRESS _Size __size_  = 0;
0089
0090 public:
0091   _LIBCPP_HIDE_FROM_ABI subrange()
0092     requires default_initializable<_Iter>
0093   = default;
0094
0095   _LIBCPP_HIDE_FROM_ABI constexpr subrange(__convertible_to_non_slicing<_Iter> auto __iter, _Sent __sent)
0096     requires _MustProvideSizeAtConstruction
0097       : __begin_(std::move(__iter)), __end_(std::move(__sent)) {}
0098
0099   _LIBCPP_HIDE_FROM_ABI constexpr subrange(
0100       __convertible_to_non_slicing<_Iter> auto __iter, _Sent __sent, make_unsigned_t<iter_difference_t<_Iter>> __n)
0101     requires(_Kind == subrange_kind::sized)
0102       : __begin_(std::move(__iter)), __end_(std::move(__sent)), __size_(__n) {
0103     if constexpr (sized_sentinel_for<_Sent, _Iter>)
0104       _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS((__end_ - __begin_) == static_cast<iter_difference_t<_Iter>>(__n),
0105                                           "std::ranges::subrange was passed an invalid size hint");
0106   }
0107
0108   template <__different_from<subrange> _Range>
0109     requires borrowed_range<_Range> && __convertible_to_non_slicing<iterator_t<_Range>, _Iter> &&
0110              convertible_to<sentinel_t<_Range>, _Sent>
0111              _LIBCPP_HIDE_FROM_ABI constexpr subrange(_Range&& __range)
0112                requires(!_StoreSize)
0113       : subrange(ranges::begin(__range), ranges::end(__range)) {}
0114
0115   template <__different_from<subrange> _Range>
0116     requires borrowed_range<_Range> && __convertible_to_non_slicing<iterator_t<_Range>, _Iter> &&
0117              convertible_to<sentinel_t<_Range>, _Sent>
0118              _LIBCPP_HIDE_FROM_ABI constexpr subrange(_Range&& __range)
0119                requires _StoreSize && sized_range<_Range>
0120       : subrange(__range, ranges::size(__range)) {}
0121
0122   template <borrowed_range _Range>
0123     requires __convertible_to_non_slicing<iterator_t<_Range>, _Iter> &&
0124              convertible_to<sentinel_t<_Range>, _Sent>
0125              _LIBCPP_HIDE_FROM_ABI constexpr subrange(_Range&& __range, make_unsigned_t<iter_difference_t<_Iter>> __n)
0126                requires(_Kind == subrange_kind::sized)
0127       : subrange(ranges::begin(__range), ranges::end(__range), __n) {}
0128
0129   template <__pair_like_convertible_from<const _Iter&, const _Sent&> _Pair>
0130   _LIBCPP_HIDE_FROM_ABI constexpr operator _Pair() const {
0131     return _Pair(__begin_, __end_);
0132   }
0133
0134   _LIBCPP_HIDE_FROM_ABI constexpr _Iter begin() const
0135     requires copyable<_Iter>
0136   {
0137     return __begin_;
0138   }
0139
0140   [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr _Iter begin()
0141     requires(!copyable<_Iter>)
0142   {
0143     return std::move(__begin_);
0144   }
0145
0146   _LIBCPP_HIDE_FROM_ABI constexpr _Sent end() const { return __end_; }
0147
0148   [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr bool empty() const { return __begin_ == __end_; }
0149
0150   _LIBCPP_HIDE_FROM_ABI constexpr make_unsigned_t<iter_difference_t<_Iter>> size() const
0151     requires(_Kind == subrange_kind::sized)
0152   {
0153     if constexpr (_StoreSize)
0154       return __size_;
0155     else
0156       return std::__to_unsigned_like(__end_ - __begin_);
0157   }
0158
0159   [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr subrange next(iter_difference_t<_Iter> __n = 1) const&
0160     requires forward_iterator<_Iter>
0161   {
0162     auto __tmp = *this;
0163     __tmp.advance(__n);
0164     return __tmp;
0165   }
0166
0167   [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr subrange next(iter_difference_t<_Iter> __n = 1) && {
0168     advance(__n);
0169     return std::move(*this);
0170   }
0171
0172   [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr subrange prev(iter_difference_t<_Iter> __n = 1) const
0173     requires bidirectional_iterator<_Iter>
0174   {
0175     auto __tmp = *this;
0176     __tmp.advance(-__n);
0177     return __tmp;
0178   }
0179
0180   _LIBCPP_HIDE_FROM_ABI constexpr subrange& advance(iter_difference_t<_Iter> __n) {
0181     if constexpr (bidirectional_iterator<_Iter>) {
0182       if (__n < 0) {
0183         ranges::advance(__begin_, __n);
0184         if constexpr (_StoreSize)
0185           __size_ += std::__to_unsigned_like(-__n);
0186         return *this;
0187       }
0188     }
0189
0190     auto __d = __n - ranges::advance(__begin_, __n, __end_);
0191     if constexpr (_StoreSize)
0192       __size_ -= std::__to_unsigned_like(__d);
0193     return *this;
0194   }
0195 };
0196
0197 template <input_or_output_iterator _Iter, sentinel_for<_Iter> _Sent>
0198 subrange(_Iter, _Sent) -> subrange<_Iter, _Sent>;
0199
0200 template <input_or_output_iterator _Iter, sentinel_for<_Iter> _Sent>
0201 subrange(_Iter, _Sent, make_unsigned_t<iter_difference_t<_Iter>>) -> subrange<_Iter, _Sent, subrange_kind::sized>;
0202
0203 template <borrowed_range _Range>
0204 subrange(_Range&&) -> subrange<iterator_t<_Range>,
0205                                sentinel_t<_Range>,
0206                                (sized_range<_Range> || sized_sentinel_for<sentinel_t<_Range>, iterator_t<_Range>>)
0207                                    ? subrange_kind::sized
0208                                    : subrange_kind::unsized>;
0209
0210 template <borrowed_range _Range>
0211 subrange(_Range&&, make_unsigned_t<range_difference_t<_Range>>)
0212     -> subrange<iterator_t<_Range>, sentinel_t<_Range>, subrange_kind::sized>;
0213
0214 template <size_t _Index, class _Iter, class _Sent, subrange_kind _Kind>
0215   requires((_Index == 0 && copyable<_Iter>) || _Index == 1)
0216 _LIBCPP_HIDE_FROM_ABI constexpr auto get(const subrange<_Iter, _Sent, _Kind>& __subrange) {
0217   if constexpr (_Index == 0)
0218     return __subrange.begin();
0219   else
0220     return __subrange.end();
0221 }
0222
0223 template <size_t _Index, class _Iter, class _Sent, subrange_kind _Kind>
0224   requires(_Index < 2)
0225 _LIBCPP_HIDE_FROM_ABI constexpr auto get(subrange<_Iter, _Sent, _Kind>&& __subrange) {
0226   if constexpr (_Index == 0)
0227     return __subrange.begin();
0228   else
0229     return __subrange.end();
0230 }
0231
0232 template <class _Ip, class _Sp, subrange_kind _Kp>
0233 inline constexpr bool enable_borrowed_range<subrange<_Ip, _Sp, _Kp>> = true;
0234
0235 template <range _Rp>
0236 using borrowed_subrange_t = _If<borrowed_range<_Rp>, subrange<iterator_t<_Rp>>, dangling>;
0237 } // namespace ranges
0238
0239 // [range.subrange.general]
0240
0241 using ranges::get;
0242
0243 // [ranges.syn]
0244
0245 template <class _Ip, class _Sp, ranges::subrange_kind _Kp>
0246 struct tuple_size<ranges::subrange<_Ip, _Sp, _Kp>> : integral_constant<size_t, 2> {};
0247
0248 template <class _Ip, class _Sp, ranges::subrange_kind _Kp>
0249 struct tuple_element<0, ranges::subrange<_Ip, _Sp, _Kp>> {
0250   using type = _Ip;
0251 };
0252
0253 template <class _Ip, class _Sp, ranges::subrange_kind _Kp>
0254 struct tuple_element<1, ranges::subrange<_Ip, _Sp, _Kp>> {
0255   using type = _Sp;
0256 };
0257
0258 template <class _Ip, class _Sp, ranges::subrange_kind _Kp>
0259 struct tuple_element<0, const ranges::subrange<_Ip, _Sp, _Kp>> {
0260   using type = _Ip;
0261 };
0262
0263 template <class _Ip, class _Sp, ranges::subrange_kind _Kp>
0264 struct tuple_element<1, const ranges::subrange<_Ip, _Sp, _Kp>> {
0265   using type = _Sp;
0266 };
0267
0268 #endif // _LIBCPP_STD_VER >= 20
0269
0270 _LIBCPP_END_NAMESPACE_STD
0271
0272 _LIBCPP_POP_MACROS
0273
0274 #endif // _LIBCPP___RANGES_SUBRANGE_H