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_REVERSE_VIEW_H 10 #define _LIBCPP___RANGES_REVERSE_VIEW_H 11 12 #include <__concepts/constructible.h> 13 #include <__config> 14 #include <__iterator/concepts.h> 15 #include <__iterator/next.h> 16 #include <__iterator/reverse_iterator.h> 17 #include <__ranges/access.h> 18 #include <__ranges/all.h> 19 #include <__ranges/concepts.h> 20 #include <__ranges/enable_borrowed_range.h> 21 #include <__ranges/non_propagating_cache.h> 22 #include <__ranges/range_adaptor.h> 23 #include <__ranges/size.h> 24 #include <__ranges/subrange.h> 25 #include <__ranges/view_interface.h> 26 #include <__utility/forward.h> 27 #include <__utility/move.h> 28 #include <type_traits> 29 30 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 31 #pragma GCC system_header 32 #endif 33 34 _LIBCPP_BEGIN_NAMESPACE_STD 35 36 #if !defined(_LIBCPP_HAS_NO_CONCEPTS) && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) 37 38 namespace ranges { 39 template<view _View> 40 requires bidirectional_range<_View> 41 class reverse_view : public view_interface<reverse_view<_View>> { 42 // We cache begin() whenever ranges::next is not guaranteed O(1) to provide an 43 // amortized O(1) begin() method. 44 static constexpr bool _UseCache = !random_access_range<_View> && !common_range<_View>; 45 using _Cache = _If<_UseCache, __non_propagating_cache<reverse_iterator<iterator_t<_View>>>, __empty_cache>; 46 [[no_unique_address]] _Cache __cached_begin_ = _Cache(); 47 [[no_unique_address]] _View __base_ = _View(); 48 49 public: 50 _LIBCPP_HIDE_FROM_ABI 51 reverse_view() requires default_initializable<_View> = default; 52 53 _LIBCPP_HIDE_FROM_ABI 54 constexpr explicit reverse_view(_View __view) : __base_(_VSTD::move(__view)) {} 55 56 _LIBCPP_HIDE_FROM_ABI 57 constexpr _View base() const& requires copy_constructible<_View> { return __base_; } 58 59 _LIBCPP_HIDE_FROM_ABI 60 constexpr _View base() && { return _VSTD::move(__base_); } 61 62 _LIBCPP_HIDE_FROM_ABI 63 constexpr reverse_iterator<iterator_t<_View>> begin() { 64 if constexpr (_UseCache) 65 if (__cached_begin_.__has_value()) 66 return *__cached_begin_; 67 68 auto __tmp = _VSTD::make_reverse_iterator(ranges::next(ranges::begin(__base_), ranges::end(__base_))); 69 if constexpr (_UseCache) 70 __cached_begin_.__emplace(__tmp); 71 return __tmp; 72 } 73 74 _LIBCPP_HIDE_FROM_ABI 75 constexpr reverse_iterator<iterator_t<_View>> begin() requires common_range<_View> { 76 return _VSTD::make_reverse_iterator(ranges::end(__base_)); 77 } 78 79 _LIBCPP_HIDE_FROM_ABI 80 constexpr auto begin() const requires common_range<const _View> { 81 return _VSTD::make_reverse_iterator(ranges::end(__base_)); 82 } 83 84 _LIBCPP_HIDE_FROM_ABI 85 constexpr reverse_iterator<iterator_t<_View>> end() { 86 return _VSTD::make_reverse_iterator(ranges::begin(__base_)); 87 } 88 89 _LIBCPP_HIDE_FROM_ABI 90 constexpr auto end() const requires common_range<const _View> { 91 return _VSTD::make_reverse_iterator(ranges::begin(__base_)); 92 } 93 94 _LIBCPP_HIDE_FROM_ABI 95 constexpr auto size() requires sized_range<_View> { 96 return ranges::size(__base_); 97 } 98 99 _LIBCPP_HIDE_FROM_ABI 100 constexpr auto size() const requires sized_range<const _View> { 101 return ranges::size(__base_); 102 } 103 }; 104 105 template<class _Range> 106 reverse_view(_Range&&) -> reverse_view<views::all_t<_Range>>; 107 108 template<class _Tp> 109 inline constexpr bool enable_borrowed_range<reverse_view<_Tp>> = enable_borrowed_range<_Tp>; 110 111 namespace views { 112 namespace __reverse { 113 template<class _Tp> 114 constexpr bool __is_reverse_view = false; 115 116 template<class _Tp> 117 constexpr bool __is_reverse_view<reverse_view<_Tp>> = true; 118 119 template<class _Tp> 120 constexpr bool __is_sized_reverse_subrange = false; 121 122 template<class _Iter> 123 constexpr bool __is_sized_reverse_subrange<subrange<reverse_iterator<_Iter>, reverse_iterator<_Iter>, subrange_kind::sized>> = true; 124 125 template<class _Tp> 126 constexpr bool __is_unsized_reverse_subrange = false; 127 128 template<class _Iter, subrange_kind _Kind> 129 constexpr bool __is_unsized_reverse_subrange<subrange<reverse_iterator<_Iter>, reverse_iterator<_Iter>, _Kind>> = _Kind == subrange_kind::unsized; 130 131 template<class _Tp> 132 struct __unwrapped_reverse_subrange { 133 using type = void; // avoid SFINAE-ing out the overload below -- let the concept requirements do it for better diagnostics 134 }; 135 136 template<class _Iter, subrange_kind _Kind> 137 struct __unwrapped_reverse_subrange<subrange<reverse_iterator<_Iter>, reverse_iterator<_Iter>, _Kind>> { 138 using type = subrange<_Iter, _Iter, _Kind>; 139 }; 140 141 struct __fn : __range_adaptor_closure<__fn> { 142 template<class _Range> 143 requires __is_reverse_view<remove_cvref_t<_Range>> 144 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI 145 constexpr auto operator()(_Range&& __range) const 146 noexcept(noexcept(_VSTD::forward<_Range>(__range).base())) 147 -> decltype( _VSTD::forward<_Range>(__range).base()) 148 { return _VSTD::forward<_Range>(__range).base(); } 149 150 template<class _Range, 151 class _UnwrappedSubrange = typename __unwrapped_reverse_subrange<remove_cvref_t<_Range>>::type> 152 requires __is_sized_reverse_subrange<remove_cvref_t<_Range>> 153 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI 154 constexpr auto operator()(_Range&& __range) const 155 noexcept(noexcept(_UnwrappedSubrange(__range.end().base(), __range.begin().base(), __range.size()))) 156 -> decltype( _UnwrappedSubrange(__range.end().base(), __range.begin().base(), __range.size())) 157 { return _UnwrappedSubrange(__range.end().base(), __range.begin().base(), __range.size()); } 158 159 template<class _Range, 160 class _UnwrappedSubrange = typename __unwrapped_reverse_subrange<remove_cvref_t<_Range>>::type> 161 requires __is_unsized_reverse_subrange<remove_cvref_t<_Range>> 162 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI 163 constexpr auto operator()(_Range&& __range) const 164 noexcept(noexcept(_UnwrappedSubrange(__range.end().base(), __range.begin().base()))) 165 -> decltype( _UnwrappedSubrange(__range.end().base(), __range.begin().base())) 166 { return _UnwrappedSubrange(__range.end().base(), __range.begin().base()); } 167 168 template<class _Range> 169 requires (!__is_reverse_view<remove_cvref_t<_Range>> && 170 !__is_sized_reverse_subrange<remove_cvref_t<_Range>> && 171 !__is_unsized_reverse_subrange<remove_cvref_t<_Range>>) 172 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI 173 constexpr auto operator()(_Range&& __range) const 174 noexcept(noexcept(reverse_view{_VSTD::forward<_Range>(__range)})) 175 -> decltype( reverse_view{_VSTD::forward<_Range>(__range)}) 176 { return reverse_view{_VSTD::forward<_Range>(__range)}; } 177 }; 178 } // namespace __reverse 179 180 inline namespace __cpo { 181 inline constexpr auto reverse = __reverse::__fn{}; 182 } // namespace __cpo 183 } // namespace views 184 } // namespace ranges 185 186 #endif // !defined(_LIBCPP_HAS_NO_CONCEPTS) && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) 187 188 _LIBCPP_END_NAMESPACE_STD 189 190 #endif // _LIBCPP___RANGES_REVERSE_VIEW_H 191