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