v1/__ranges/drop_view.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_DROP_VIEW_H
0011 #define _LIBCPP___RANGES_DROP_VIEW_H
0012
0013 #include <__algorithm/min.h>
0014 #include <__assert>
0015 #include <__concepts/constructible.h>
0016 #include <__concepts/convertible_to.h>
0017 #include <__config>
0018 #include <__cstddef/size_t.h>
0019 #include <__functional/bind_back.h>
0020 #include <__fwd/span.h>
0021 #include <__fwd/string_view.h>
0022 #include <__iterator/concepts.h>
0023 #include <__iterator/distance.h>
0024 #include <__iterator/iterator_traits.h>
0025 #include <__iterator/next.h>
0026 #include <__ranges/access.h>
0027 #include <__ranges/all.h>
0028 #include <__ranges/concepts.h>
0029 #include <__ranges/empty_view.h>
0030 #include <__ranges/enable_borrowed_range.h>
0031 #include <__ranges/iota_view.h>
0032 #include <__ranges/non_propagating_cache.h>
0033 #include <__ranges/range_adaptor.h>
0034 #include <__ranges/repeat_view.h>
0035 #include <__ranges/size.h>
0036 #include <__ranges/subrange.h>
0037 #include <__ranges/view_interface.h>
0038 #include <__type_traits/conditional.h>
0039 #include <__type_traits/decay.h>
0040 #include <__type_traits/is_nothrow_constructible.h>
0041 #include <__type_traits/make_unsigned.h>
0042 #include <__type_traits/remove_cvref.h>
0043 #include <__utility/auto_cast.h>
0044 #include <__utility/forward.h>
0045 #include <__utility/move.h>
0046
0047 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
0048 #  pragma GCC system_header
0049 #endif
0050
0051 _LIBCPP_PUSH_MACROS
0052 #include <__undef_macros>
0053
0054 _LIBCPP_BEGIN_NAMESPACE_STD
0055
0056 #if _LIBCPP_STD_VER >= 20
0057
0058 namespace ranges {
0059 template <view _View>
0060 class drop_view : public view_interface<drop_view<_View>> {
0061   // We cache begin() whenever ranges::next is not guaranteed O(1) to provide an
0062   // amortized O(1) begin() method. If this is an input_range, then we cannot cache
0063   // begin because begin is not equality preserving.
0064   // Note: drop_view<input-range>::begin() is still trivially amortized O(1) because
0065   // one can't call begin() on it more than once.
0066   static constexpr bool _UseCache = forward_range<_View> && !(random_access_range<_View> && sized_range<_View>);
0067   using _Cache _LIBCPP_NODEBUG    = _If<_UseCache, __non_propagating_cache<iterator_t<_View>>, __empty_cache>;
0068   _LIBCPP_NO_UNIQUE_ADDRESS _Cache __cached_begin_ = _Cache();
0069   range_difference_t<_View> __count_               = 0;
0070   _View __base_                                    = _View();
0071
0072 public:
0073   _LIBCPP_HIDE_FROM_ABI drop_view()
0074     requires default_initializable<_View>
0075   = default;
0076
0077   _LIBCPP_HIDE_FROM_ABI constexpr _LIBCPP_EXPLICIT_SINCE_CXX23
0078   drop_view(_View __base, range_difference_t<_View> __count)
0079       : __count_(__count), __base_(std::move(__base)) {
0080     _LIBCPP_ASSERT_UNCATEGORIZED(__count_ >= 0, "count must be greater than or equal to zero.");
0081   }
0082
0083   _LIBCPP_HIDE_FROM_ABI constexpr _View base() const&
0084     requires copy_constructible<_View>
0085   {
0086     return __base_;
0087   }
0088   _LIBCPP_HIDE_FROM_ABI constexpr _View base() && { return std::move(__base_); }
0089
0090   _LIBCPP_HIDE_FROM_ABI constexpr auto begin()
0091     requires(!(__simple_view<_View> && random_access_range<const _View> && sized_range<const _View>))
0092   {
0093     if constexpr (random_access_range<_View> && sized_range<_View>) {
0094       const auto __dist = std::min(ranges::distance(__base_), __count_);
0095       return ranges::begin(__base_) + __dist;
0096     }
0097     if constexpr (_UseCache)
0098       if (__cached_begin_.__has_value())
0099         return *__cached_begin_;
0100
0101     auto __tmp = ranges::next(ranges::begin(__base_), __count_, ranges::end(__base_));
0102     if constexpr (_UseCache)
0103       __cached_begin_.__emplace(__tmp);
0104     return __tmp;
0105   }
0106
0107   _LIBCPP_HIDE_FROM_ABI constexpr auto begin() const
0108     requires random_access_range<const _View> && sized_range<const _View>
0109   {
0110     const auto __dist = std::min(ranges::distance(__base_), __count_);
0111     return ranges::begin(__base_) + __dist;
0112   }
0113
0114   _LIBCPP_HIDE_FROM_ABI constexpr auto end()
0115     requires(!__simple_view<_View>)
0116   {
0117     return ranges::end(__base_);
0118   }
0119
0120   _LIBCPP_HIDE_FROM_ABI constexpr auto end() const
0121     requires range<const _View>
0122   {
0123     return ranges::end(__base_);
0124   }
0125
0126   _LIBCPP_HIDE_FROM_ABI static constexpr auto __size(auto& __self) {
0127     const auto __s = ranges::size(__self.__base_);
0128     const auto __c = static_cast<decltype(__s)>(__self.__count_);
0129     return __s < __c ? 0 : __s - __c;
0130   }
0131
0132   _LIBCPP_HIDE_FROM_ABI constexpr auto size()
0133     requires sized_range<_View>
0134   {
0135     return __size(*this);
0136   }
0137
0138   _LIBCPP_HIDE_FROM_ABI constexpr auto size() const
0139     requires sized_range<const _View>
0140   {
0141     return __size(*this);
0142   }
0143 };
0144
0145 template <class _Range>
0146 drop_view(_Range&&, range_difference_t<_Range>) -> drop_view<views::all_t<_Range>>;
0147
0148 template <class _Tp>
0149 inline constexpr bool enable_borrowed_range<drop_view<_Tp>> = enable_borrowed_range<_Tp>;
0150
0151 namespace views {
0152 namespace __drop {
0153
0154 template <class _Tp>
0155 inline constexpr bool __is_empty_view = false;
0156
0157 template <class _Tp>
0158 inline constexpr bool __is_empty_view<empty_view<_Tp>> = true;
0159
0160 template <class _Tp>
0161 inline constexpr bool __is_passthrough_specialization = false;
0162
0163 template <class _Tp, size_t _Extent>
0164 inline constexpr bool __is_passthrough_specialization<span<_Tp, _Extent>> = true;
0165
0166 template <class _CharT, class _Traits>
0167 inline constexpr bool __is_passthrough_specialization<basic_string_view<_CharT, _Traits>> = true;
0168
0169 template <class _Np, class _Bound>
0170 inline constexpr bool __is_passthrough_specialization<iota_view<_Np, _Bound>> = true;
0171
0172 template <class _Iter, class _Sent, subrange_kind _Kind>
0173 inline constexpr bool __is_passthrough_specialization<subrange<_Iter, _Sent, _Kind>> =
0174     !subrange<_Iter, _Sent, _Kind>::_StoreSize;
0175
0176 template <class _Tp>
0177 inline constexpr bool __is_subrange_specialization_with_store_size = false;
0178
0179 template <class _Iter, class _Sent, subrange_kind _Kind>
0180 inline constexpr bool __is_subrange_specialization_with_store_size<subrange<_Iter, _Sent, _Kind>> =
0181     subrange<_Iter, _Sent, _Kind>::_StoreSize;
0182
0183 template <class _Tp>
0184 struct __passthrough_type;
0185
0186 template <class _Tp, size_t _Extent>
0187 struct __passthrough_type<span<_Tp, _Extent>> {
0188   using type = span<_Tp>;
0189 };
0190
0191 template <class _CharT, class _Traits>
0192 struct __passthrough_type<basic_string_view<_CharT, _Traits>> {
0193   using type = basic_string_view<_CharT, _Traits>;
0194 };
0195
0196 template <class _Np, class _Bound>
0197 struct __passthrough_type<iota_view<_Np, _Bound>> {
0198   using type = iota_view<_Np, _Bound>;
0199 };
0200
0201 template <class _Iter, class _Sent, subrange_kind _Kind>
0202 struct __passthrough_type<subrange<_Iter, _Sent, _Kind>> {
0203   using type = subrange<_Iter, _Sent, _Kind>;
0204 };
0205
0206 template <class _Tp>
0207 using __passthrough_type_t _LIBCPP_NODEBUG = typename __passthrough_type<_Tp>::type;
0208
0209 struct __fn {
0210   // [range.drop.overview]: the `empty_view` case.
0211   template <class _Range, convertible_to<range_difference_t<_Range>> _Np>
0212     requires __is_empty_view<remove_cvref_t<_Range>>
0213   [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr auto operator()(_Range&& __range, _Np&&) const
0214       noexcept(noexcept(_LIBCPP_AUTO_CAST(std::forward<_Range>(__range))))
0215           -> decltype(_LIBCPP_AUTO_CAST(std::forward<_Range>(__range))) {
0216     return _LIBCPP_AUTO_CAST(std::forward<_Range>(__range));
0217   }
0218
0219   // [range.drop.overview]: the `span | basic_string_view | iota_view | subrange (StoreSize == false)` case.
0220   template <class _Range,
0221             convertible_to<range_difference_t<_Range>> _Np,
0222             class _RawRange = remove_cvref_t<_Range>,
0223             class _Dist     = range_difference_t<_Range>>
0224     requires(!__is_empty_view<_RawRange> && random_access_range<_RawRange> && sized_range<_RawRange> &&
0225              __is_passthrough_specialization<_RawRange>)
0226   [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr auto operator()(_Range&& __rng, _Np&& __n) const
0227       noexcept(noexcept(__passthrough_type_t<_RawRange>(
0228           ranges::begin(__rng) + std::min<_Dist>(ranges::distance(__rng), std::forward<_Np>(__n)), ranges::end(__rng))))
0229           -> decltype(__passthrough_type_t<_RawRange>(
0230               // Note: deliberately not forwarding `__rng` to guard against double moves.
0231               ranges::begin(__rng) + std::min<_Dist>(ranges::distance(__rng), std::forward<_Np>(__n)),
0232               ranges::end(__rng))) {
0233     return __passthrough_type_t<_RawRange>(
0234         ranges::begin(__rng) + std::min<_Dist>(ranges::distance(__rng), std::forward<_Np>(__n)), ranges::end(__rng));
0235   }
0236
0237   // [range.drop.overview]: the `subrange (StoreSize == true)` case.
0238   template <class _Range,
0239             convertible_to<range_difference_t<_Range>> _Np,
0240             class _RawRange = remove_cvref_t<_Range>,
0241             class _Dist     = range_difference_t<_Range>>
0242     requires(!__is_empty_view<_RawRange> && random_access_range<_RawRange> && sized_range<_RawRange> &&
0243              __is_subrange_specialization_with_store_size<_RawRange>)
0244   [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr auto operator()(_Range&& __rng, _Np&& __n) const noexcept(noexcept(
0245       _RawRange(ranges::begin(__rng) + std::min<_Dist>(ranges::distance(__rng), std::forward<_Np>(__n)),
0246                 ranges::end(__rng),
0247                 std::__to_unsigned_like(ranges::distance(__rng) -
0248                                         std::min<_Dist>(ranges::distance(__rng), std::forward<_Np>(__n))))))
0249       -> decltype(_RawRange(
0250           // Note: deliberately not forwarding `__rng` to guard against double moves.
0251           ranges::begin(__rng) + std::min<_Dist>(ranges::distance(__rng), std::forward<_Np>(__n)),
0252           ranges::end(__rng),
0253           std::__to_unsigned_like(ranges::distance(__rng) -
0254                                   std::min<_Dist>(ranges::distance(__rng), std::forward<_Np>(__n))))) {
0255     // Introducing local variables avoids calculating `min` and `distance` twice (at the cost of diverging from the
0256     // expression used in the `noexcept` clause and the return statement).
0257     auto __dist    = ranges::distance(__rng);
0258     auto __clamped = std::min<_Dist>(__dist, std::forward<_Np>(__n));
0259     return _RawRange(ranges::begin(__rng) + __clamped, ranges::end(__rng), std::__to_unsigned_like(__dist - __clamped));
0260   }
0261   // clang-format off
0262 #if _LIBCPP_STD_VER >= 23
0263   // [range.drop.overview]: the `repeat_view` "_RawRange models sized_range" case.
0264   template <class _Range,
0265             convertible_to<range_difference_t<_Range>> _Np,
0266             class _RawRange = remove_cvref_t<_Range>,
0267             class _Dist     = range_difference_t<_Range>>
0268     requires (__is_repeat_specialization<_RawRange> && sized_range<_RawRange>)
0269   [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr auto operator()(_Range&& __range, _Np&& __n) const
0270     noexcept(noexcept(views::repeat(*__range.__value_, ranges::distance(__range) - std::min<_Dist>(ranges::distance(__range), std::forward<_Np>(__n)))))
0271     -> decltype(      views::repeat(*__range.__value_, ranges::distance(__range) - std::min<_Dist>(ranges::distance(__range), std::forward<_Np>(__n))))
0272     { return          views::repeat(*__range.__value_, ranges::distance(__range) - std::min<_Dist>(ranges::distance(__range), std::forward<_Np>(__n))); }
0273
0274   // [range.drop.overview]: the `repeat_view` "otherwise" case.
0275   template <class _Range,
0276             convertible_to<range_difference_t<_Range>> _Np,
0277             class _RawRange = remove_cvref_t<_Range>,
0278             class _Dist     = range_difference_t<_Range>>
0279     requires (__is_repeat_specialization<_RawRange> && !sized_range<_RawRange>)
0280   [[nodiscard]] _LIBCPP_HIDE_FROM_ABI
0281   constexpr auto operator()(_Range&& __range, _Np&&) const
0282     noexcept(noexcept(_LIBCPP_AUTO_CAST(std::forward<_Range>(__range))))
0283     -> decltype(      _LIBCPP_AUTO_CAST(std::forward<_Range>(__range)))
0284     { return          _LIBCPP_AUTO_CAST(std::forward<_Range>(__range)); }
0285 #endif
0286   // clang-format on
0287
0288   // [range.drop.overview]: the "otherwise" case.
0289   template <class _Range, convertible_to<range_difference_t<_Range>> _Np, class _RawRange = remove_cvref_t<_Range>>
0290   // Note: without specifically excluding the other cases, GCC sees this overload as ambiguous with the other
0291   // overloads.
0292     requires(!(__is_empty_view<_RawRange> ||
0293 #  if _LIBCPP_STD_VER >= 23
0294                __is_repeat_specialization<_RawRange> ||
0295 #  endif
0296                (__is_subrange_specialization_with_store_size<_RawRange> && sized_range<_RawRange> &&
0297                 random_access_range<_RawRange>) ||
0298                (__is_passthrough_specialization<_RawRange> && sized_range<_RawRange> &&
0299                 random_access_range<_RawRange>)))
0300   [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr auto operator()(_Range&& __range, _Np&& __n) const
0301       noexcept(noexcept(drop_view(std::forward<_Range>(__range), std::forward<_Np>(__n))))
0302           -> decltype(drop_view(std::forward<_Range>(__range), std::forward<_Np>(__n))) {
0303     return drop_view(std::forward<_Range>(__range), std::forward<_Np>(__n));
0304   }
0305
0306   template <class _Np>
0307     requires constructible_from<decay_t<_Np>, _Np>
0308   [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr auto operator()(_Np&& __n) const
0309       noexcept(is_nothrow_constructible_v<decay_t<_Np>, _Np>) {
0310     return __pipeable(std::__bind_back(*this, std::forward<_Np>(__n)));
0311   }
0312 };
0313
0314 } // namespace __drop
0315
0316 inline namespace __cpo {
0317 inline constexpr auto drop = __drop::__fn{};
0318 } // namespace __cpo
0319 } // namespace views
0320
0321 } // namespace ranges
0322
0323 #endif // _LIBCPP_STD_VER >= 20
0324
0325 _LIBCPP_END_NAMESPACE_STD
0326
0327 _LIBCPP_POP_MACROS
0328
0329 #endif // _LIBCPP___RANGES_DROP_VIEW_H