v1/__ranges/reverse_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_REVERSE_VIEW_H
0011 #define _LIBCPP___RANGES_REVERSE_VIEW_H
0012
0013 #include <__concepts/constructible.h>
0014 #include <__config>
0015 #include <__iterator/concepts.h>
0016 #include <__iterator/next.h>
0017 #include <__iterator/reverse_iterator.h>
0018 #include <__ranges/access.h>
0019 #include <__ranges/all.h>
0020 #include <__ranges/concepts.h>
0021 #include <__ranges/enable_borrowed_range.h>
0022 #include <__ranges/non_propagating_cache.h>
0023 #include <__ranges/range_adaptor.h>
0024 #include <__ranges/size.h>
0025 #include <__ranges/subrange.h>
0026 #include <__ranges/view_interface.h>
0027 #include <__type_traits/conditional.h>
0028 #include <__type_traits/remove_cvref.h>
0029 #include <__utility/forward.h>
0030 #include <__utility/move.h>
0031
0032 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
0033 #  pragma GCC system_header
0034 #endif
0035
0036 _LIBCPP_PUSH_MACROS
0037 #include <__undef_macros>
0038
0039 _LIBCPP_BEGIN_NAMESPACE_STD
0040
0041 #if _LIBCPP_STD_VER >= 20
0042
0043 namespace ranges {
0044 template <view _View>
0045   requires bidirectional_range<_View>
0046 class reverse_view : public view_interface<reverse_view<_View>> {
0047   // We cache begin() whenever ranges::next is not guaranteed O(1) to provide an
0048   // amortized O(1) begin() method.
0049   static constexpr bool _UseCache = !random_access_range<_View> && !common_range<_View>;
0050   using _Cache _LIBCPP_NODEBUG =
0051       _If<_UseCache, __non_propagating_cache<reverse_iterator<iterator_t<_View>>>, __empty_cache>;
0052   _LIBCPP_NO_UNIQUE_ADDRESS _Cache __cached_begin_ = _Cache();
0053   _LIBCPP_NO_UNIQUE_ADDRESS _View __base_          = _View();
0054
0055 public:
0056   _LIBCPP_HIDE_FROM_ABI reverse_view()
0057     requires default_initializable<_View>
0058   = default;
0059
0060   _LIBCPP_HIDE_FROM_ABI constexpr explicit reverse_view(_View __view) : __base_(std::move(__view)) {}
0061
0062   _LIBCPP_HIDE_FROM_ABI constexpr _View base() const&
0063     requires copy_constructible<_View>
0064   {
0065     return __base_;
0066   }
0067
0068   _LIBCPP_HIDE_FROM_ABI constexpr _View base() && { return std::move(__base_); }
0069
0070   _LIBCPP_HIDE_FROM_ABI constexpr reverse_iterator<iterator_t<_View>> begin() {
0071     if constexpr (_UseCache)
0072       if (__cached_begin_.__has_value())
0073         return *__cached_begin_;
0074
0075     auto __tmp = std::make_reverse_iterator(ranges::next(ranges::begin(__base_), ranges::end(__base_)));
0076     if constexpr (_UseCache)
0077       __cached_begin_.__emplace(__tmp);
0078     return __tmp;
0079   }
0080
0081   _LIBCPP_HIDE_FROM_ABI constexpr reverse_iterator<iterator_t<_View>> begin()
0082     requires common_range<_View>
0083   {
0084     return std::make_reverse_iterator(ranges::end(__base_));
0085   }
0086
0087   _LIBCPP_HIDE_FROM_ABI constexpr auto begin() const
0088     requires common_range<const _View>
0089   {
0090     return std::make_reverse_iterator(ranges::end(__base_));
0091   }
0092
0093   _LIBCPP_HIDE_FROM_ABI constexpr reverse_iterator<iterator_t<_View>> end() {
0094     return std::make_reverse_iterator(ranges::begin(__base_));
0095   }
0096
0097   _LIBCPP_HIDE_FROM_ABI constexpr auto end() const
0098     requires common_range<const _View>
0099   {
0100     return std::make_reverse_iterator(ranges::begin(__base_));
0101   }
0102
0103   _LIBCPP_HIDE_FROM_ABI constexpr auto size()
0104     requires sized_range<_View>
0105   {
0106     return ranges::size(__base_);
0107   }
0108
0109   _LIBCPP_HIDE_FROM_ABI constexpr auto size() const
0110     requires sized_range<const _View>
0111   {
0112     return ranges::size(__base_);
0113   }
0114 };
0115
0116 template <class _Range>
0117 reverse_view(_Range&&) -> reverse_view<views::all_t<_Range>>;
0118
0119 template <class _Tp>
0120 inline constexpr bool enable_borrowed_range<reverse_view<_Tp>> = enable_borrowed_range<_Tp>;
0121
0122 namespace views {
0123 namespace __reverse {
0124 template <class _Tp>
0125 inline constexpr bool __is_reverse_view = false;
0126
0127 template <class _Tp>
0128 inline constexpr bool __is_reverse_view<reverse_view<_Tp>> = true;
0129
0130 template <class _Tp>
0131 inline constexpr bool __is_sized_reverse_subrange = false;
0132
0133 template <class _Iter>
0134 inline constexpr bool
0135     __is_sized_reverse_subrange<subrange<reverse_iterator<_Iter>, reverse_iterator<_Iter>, subrange_kind::sized>> =
0136         true;
0137
0138 template <class _Tp>
0139 inline constexpr bool __is_unsized_reverse_subrange = false;
0140
0141 template <class _Iter, subrange_kind _Kind>
0142 inline constexpr bool __is_unsized_reverse_subrange<subrange<reverse_iterator<_Iter>, reverse_iterator<_Iter>, _Kind>> =
0143     _Kind == subrange_kind::unsized;
0144
0145 template <class _Tp>
0146 struct __unwrapped_reverse_subrange {
0147   using type =
0148       void; // avoid SFINAE-ing out the overload below -- let the concept requirements do it for better diagnostics
0149 };
0150
0151 template <class _Iter, subrange_kind _Kind>
0152 struct __unwrapped_reverse_subrange<subrange<reverse_iterator<_Iter>, reverse_iterator<_Iter>, _Kind>> {
0153   using type = subrange<_Iter, _Iter, _Kind>;
0154 };
0155
0156 struct __fn : __range_adaptor_closure<__fn> {
0157   template <class _Range>
0158     requires __is_reverse_view<remove_cvref_t<_Range>>
0159   [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr auto operator()(_Range&& __range) const
0160       noexcept(noexcept(std::forward<_Range>(__range).base())) -> decltype(std::forward<_Range>(__range).base()) {
0161     return std::forward<_Range>(__range).base();
0162   }
0163
0164   template <class _Range,
0165             class _UnwrappedSubrange = typename __unwrapped_reverse_subrange<remove_cvref_t<_Range>>::type>
0166     requires __is_sized_reverse_subrange<remove_cvref_t<_Range>>
0167   [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr auto operator()(_Range&& __range) const
0168       noexcept(noexcept(_UnwrappedSubrange(__range.end().base(), __range.begin().base(), __range.size())))
0169           -> decltype(_UnwrappedSubrange(__range.end().base(), __range.begin().base(), __range.size())) {
0170     return _UnwrappedSubrange(__range.end().base(), __range.begin().base(), __range.size());
0171   }
0172
0173   template <class _Range,
0174             class _UnwrappedSubrange = typename __unwrapped_reverse_subrange<remove_cvref_t<_Range>>::type>
0175     requires __is_unsized_reverse_subrange<remove_cvref_t<_Range>>
0176   [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr auto operator()(_Range&& __range) const
0177       noexcept(noexcept(_UnwrappedSubrange(__range.end().base(), __range.begin().base())))
0178           -> decltype(_UnwrappedSubrange(__range.end().base(), __range.begin().base())) {
0179     return _UnwrappedSubrange(__range.end().base(), __range.begin().base());
0180   }
0181
0182   template <class _Range>
0183     requires(!__is_reverse_view<remove_cvref_t<_Range>> && !__is_sized_reverse_subrange<remove_cvref_t<_Range>> &&
0184              !__is_unsized_reverse_subrange<remove_cvref_t<_Range>>)
0185   [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr auto operator()(_Range&& __range) const noexcept(noexcept(reverse_view{
0186       std::forward<_Range>(__range)})) -> decltype(reverse_view{std::forward<_Range>(__range)}) {
0187     return reverse_view{std::forward<_Range>(__range)};
0188   }
0189 };
0190 } // namespace __reverse
0191
0192 inline namespace __cpo {
0193 inline constexpr auto reverse = __reverse::__fn{};
0194 } // namespace __cpo
0195 } // namespace views
0196 } // namespace ranges
0197
0198 #endif // _LIBCPP_STD_VER >= 20
0199
0200 _LIBCPP_END_NAMESPACE_STD
0201
0202 _LIBCPP_POP_MACROS
0203
0204 #endif // _LIBCPP___RANGES_REVERSE_VIEW_H