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