181ad6265SDimitry Andric // -*- C++ -*- 281ad6265SDimitry Andric //===----------------------------------------------------------------------===// 381ad6265SDimitry Andric // 481ad6265SDimitry Andric // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 581ad6265SDimitry Andric // See https://llvm.org/LICENSE.txt for license information. 681ad6265SDimitry Andric // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 781ad6265SDimitry Andric // 881ad6265SDimitry Andric //===----------------------------------------------------------------------===// 9bdd1243dSDimitry Andric 1081ad6265SDimitry Andric #ifndef _LIBCPP___RANGES_FILTER_VIEW_H 1181ad6265SDimitry Andric #define _LIBCPP___RANGES_FILTER_VIEW_H 1281ad6265SDimitry Andric 1381ad6265SDimitry Andric #include <__algorithm/ranges_find_if.h> 1406c3fb27SDimitry Andric #include <__assert> 15bdd1243dSDimitry Andric #include <__concepts/constructible.h> 16bdd1243dSDimitry Andric #include <__concepts/copyable.h> 17bdd1243dSDimitry Andric #include <__concepts/derived_from.h> 18bdd1243dSDimitry Andric #include <__concepts/equality_comparable.h> 1981ad6265SDimitry Andric #include <__config> 2081ad6265SDimitry Andric #include <__functional/bind_back.h> 2181ad6265SDimitry Andric #include <__functional/invoke.h> 2281ad6265SDimitry Andric #include <__functional/reference_wrapper.h> 2381ad6265SDimitry Andric #include <__iterator/concepts.h> 2481ad6265SDimitry Andric #include <__iterator/iter_move.h> 2581ad6265SDimitry Andric #include <__iterator/iter_swap.h> 2681ad6265SDimitry Andric #include <__iterator/iterator_traits.h> 2781ad6265SDimitry Andric #include <__memory/addressof.h> 2881ad6265SDimitry Andric #include <__ranges/access.h> 2981ad6265SDimitry Andric #include <__ranges/all.h> 3081ad6265SDimitry Andric #include <__ranges/concepts.h> 3106c3fb27SDimitry Andric #include <__ranges/movable_box.h> 3281ad6265SDimitry Andric #include <__ranges/non_propagating_cache.h> 3381ad6265SDimitry Andric #include <__ranges/range_adaptor.h> 3481ad6265SDimitry Andric #include <__ranges/view_interface.h> 3506c3fb27SDimitry Andric #include <__type_traits/conditional.h> 3606c3fb27SDimitry Andric #include <__type_traits/decay.h> 3706c3fb27SDimitry Andric #include <__type_traits/is_nothrow_constructible.h> 3806c3fb27SDimitry Andric #include <__type_traits/is_object.h> 3981ad6265SDimitry Andric #include <__utility/forward.h> 4081ad6265SDimitry Andric #include <__utility/in_place.h> 4181ad6265SDimitry Andric #include <__utility/move.h> 4281ad6265SDimitry Andric 4381ad6265SDimitry Andric #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 4481ad6265SDimitry Andric # pragma GCC system_header 4581ad6265SDimitry Andric #endif 4681ad6265SDimitry Andric 47*b3edf446SDimitry Andric _LIBCPP_PUSH_MACROS 48*b3edf446SDimitry Andric #include <__undef_macros> 49*b3edf446SDimitry Andric 5081ad6265SDimitry Andric _LIBCPP_BEGIN_NAMESPACE_STD 5181ad6265SDimitry Andric 5206c3fb27SDimitry Andric #if _LIBCPP_STD_VER >= 20 5381ad6265SDimitry Andric 5481ad6265SDimitry Andric namespace ranges { 5581ad6265SDimitry Andric template <input_range _View, indirect_unary_predicate<iterator_t<_View>> _Pred> 5681ad6265SDimitry Andric requires view<_View> && is_object_v<_Pred> 577a6dacacSDimitry Andric class _LIBCPP_ABI_LLVM18_NO_UNIQUE_ADDRESS filter_view : public view_interface<filter_view<_View, _Pred>> { 5881ad6265SDimitry Andric _LIBCPP_NO_UNIQUE_ADDRESS _View __base_ = _View(); 5906c3fb27SDimitry Andric _LIBCPP_NO_UNIQUE_ADDRESS __movable_box<_Pred> __pred_; 6081ad6265SDimitry Andric 6181ad6265SDimitry Andric // We cache the result of begin() to allow providing an amortized O(1) begin() whenever 6281ad6265SDimitry Andric // the underlying range is at least a forward_range. 6381ad6265SDimitry Andric static constexpr bool _UseCache = forward_range<_View>; 6481ad6265SDimitry Andric using _Cache = _If<_UseCache, __non_propagating_cache<iterator_t<_View>>, __empty_cache>; 6581ad6265SDimitry Andric _LIBCPP_NO_UNIQUE_ADDRESS _Cache __cached_begin_ = _Cache(); 6681ad6265SDimitry Andric 671ac55f4cSDimitry Andric class __iterator; 681ac55f4cSDimitry Andric class __sentinel; 6981ad6265SDimitry Andric 7081ad6265SDimitry Andric public: 71cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI filter_view() 72cb14a3feSDimitry Andric requires default_initializable<_View> && default_initializable<_Pred> 73cb14a3feSDimitry Andric = default; 7481ad6265SDimitry Andric filter_view(_View __base,_Pred __pred)7506c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI constexpr _LIBCPP_EXPLICIT_SINCE_CXX23 filter_view(_View __base, _Pred __pred) 7606c3fb27SDimitry Andric : __base_(std::move(__base)), __pred_(in_place, std::move(__pred)) {} 7781ad6265SDimitry Andric 7881ad6265SDimitry Andric template <class _Vp = _View> base()79cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI constexpr _View base() const& 80cb14a3feSDimitry Andric requires copy_constructible<_Vp> 81cb14a3feSDimitry Andric { 82cb14a3feSDimitry Andric return __base_; 83cb14a3feSDimitry Andric } base()84cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI constexpr _View base() && { return std::move(__base_); } 8581ad6265SDimitry Andric pred()86cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI constexpr _Pred const& pred() const { return *__pred_; } 8781ad6265SDimitry Andric begin()88cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI constexpr __iterator begin() { 891db9f3b2SDimitry Andric // Note: this duplicates a check in `optional` but provides a better error message. 901db9f3b2SDimitry Andric _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS( 91cb14a3feSDimitry Andric __pred_.__has_value(), "Trying to call begin() on a filter_view that does not have a valid predicate."); 9281ad6265SDimitry Andric if constexpr (_UseCache) { 9381ad6265SDimitry Andric if (!__cached_begin_.__has_value()) { 9481ad6265SDimitry Andric __cached_begin_.__emplace(ranges::find_if(__base_, std::ref(*__pred_))); 9581ad6265SDimitry Andric } 9681ad6265SDimitry Andric return {*this, *__cached_begin_}; 9781ad6265SDimitry Andric } else { 9881ad6265SDimitry Andric return {*this, ranges::find_if(__base_, std::ref(*__pred_))}; 9981ad6265SDimitry Andric } 10081ad6265SDimitry Andric } 10181ad6265SDimitry Andric end()102cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI constexpr auto end() { 10381ad6265SDimitry Andric if constexpr (common_range<_View>) 10481ad6265SDimitry Andric return __iterator{*this, ranges::end(__base_)}; 10581ad6265SDimitry Andric else 10681ad6265SDimitry Andric return __sentinel{*this}; 10781ad6265SDimitry Andric } 10881ad6265SDimitry Andric }; 10981ad6265SDimitry Andric 11081ad6265SDimitry Andric template <class _Range, class _Pred> 11181ad6265SDimitry Andric filter_view(_Range&&, _Pred) -> filter_view<views::all_t<_Range>, _Pred>; 11281ad6265SDimitry Andric 11381ad6265SDimitry Andric template <class _View> 11481ad6265SDimitry Andric struct __filter_iterator_category {}; 11581ad6265SDimitry Andric 11681ad6265SDimitry Andric template <forward_range _View> 11781ad6265SDimitry Andric struct __filter_iterator_category<_View> { 11881ad6265SDimitry Andric using _Cat = typename iterator_traits<iterator_t<_View>>::iterator_category; 11981ad6265SDimitry Andric using iterator_category = 120cb14a3feSDimitry Andric _If<derived_from<_Cat, bidirectional_iterator_tag>, 121cb14a3feSDimitry Andric bidirectional_iterator_tag, 122cb14a3feSDimitry Andric _If<derived_from<_Cat, forward_iterator_tag>, 123cb14a3feSDimitry Andric forward_iterator_tag, 124cb14a3feSDimitry Andric /* else */ _Cat >>; 12581ad6265SDimitry Andric }; 12681ad6265SDimitry Andric 12781ad6265SDimitry Andric template <input_range _View, indirect_unary_predicate<iterator_t<_View>> _Pred> 12881ad6265SDimitry Andric requires view<_View> && is_object_v<_Pred> 1291ac55f4cSDimitry Andric class filter_view<_View, _Pred>::__iterator : public __filter_iterator_category<_View> { 13081ad6265SDimitry Andric public: 13181ad6265SDimitry Andric _LIBCPP_NO_UNIQUE_ADDRESS iterator_t<_View> __current_ = iterator_t<_View>(); 1321ac55f4cSDimitry Andric _LIBCPP_NO_UNIQUE_ADDRESS filter_view* __parent_ = nullptr; 13381ad6265SDimitry Andric 13481ad6265SDimitry Andric using iterator_concept = 135cb14a3feSDimitry Andric _If<bidirectional_range<_View>, 136cb14a3feSDimitry Andric bidirectional_iterator_tag, 137cb14a3feSDimitry Andric _If<forward_range<_View>, 138cb14a3feSDimitry Andric forward_iterator_tag, 139cb14a3feSDimitry Andric /* else */ input_iterator_tag >>; 14081ad6265SDimitry Andric // using iterator_category = inherited; 14181ad6265SDimitry Andric using value_type = range_value_t<_View>; 14281ad6265SDimitry Andric using difference_type = range_difference_t<_View>; 14381ad6265SDimitry Andric 144cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI __iterator() 145cb14a3feSDimitry Andric requires default_initializable<iterator_t<_View>> 146cb14a3feSDimitry Andric = default; 14781ad6265SDimitry Andric 148cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI constexpr __iterator(filter_view& __parent, iterator_t<_View> __current) 149cb14a3feSDimitry Andric : __current_(std::move(__current)), __parent_(std::addressof(__parent)) {} 15081ad6265SDimitry Andric 151cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI constexpr iterator_t<_View> const& base() const& noexcept { return __current_; } 152cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI constexpr iterator_t<_View> base() && { return std::move(__current_); } 15381ad6265SDimitry Andric 154cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI constexpr range_reference_t<_View> operator*() const { return *__current_; } 155cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI constexpr iterator_t<_View> operator->() const 15681ad6265SDimitry Andric requires __has_arrow<iterator_t<_View>> && copyable<iterator_t<_View>> 15781ad6265SDimitry Andric { 15881ad6265SDimitry Andric return __current_; 15981ad6265SDimitry Andric } 16081ad6265SDimitry Andric 161cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI constexpr __iterator& operator++() { 162cb14a3feSDimitry Andric __current_ = 163cb14a3feSDimitry Andric ranges::find_if(std::move(++__current_), ranges::end(__parent_->__base_), std::ref(*__parent_->__pred_)); 16481ad6265SDimitry Andric return *this; 16581ad6265SDimitry Andric } 166cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI constexpr void operator++(int) { ++*this; } 167cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI constexpr __iterator operator++(int) 168cb14a3feSDimitry Andric requires forward_range<_View> 169cb14a3feSDimitry Andric { 17081ad6265SDimitry Andric auto __tmp = *this; 17181ad6265SDimitry Andric ++*this; 17281ad6265SDimitry Andric return __tmp; 17381ad6265SDimitry Andric } 17481ad6265SDimitry Andric 175cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI constexpr __iterator& operator--() 176cb14a3feSDimitry Andric requires bidirectional_range<_View> 177cb14a3feSDimitry Andric { 17881ad6265SDimitry Andric do { 17981ad6265SDimitry Andric --__current_; 18081ad6265SDimitry Andric } while (!std::invoke(*__parent_->__pred_, *__current_)); 18181ad6265SDimitry Andric return *this; 18281ad6265SDimitry Andric } 183cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI constexpr __iterator operator--(int) 184cb14a3feSDimitry Andric requires bidirectional_range<_View> 185cb14a3feSDimitry Andric { 18606c3fb27SDimitry Andric auto __tmp = *this; 18781ad6265SDimitry Andric --*this; 18806c3fb27SDimitry Andric return __tmp; 18981ad6265SDimitry Andric } 19081ad6265SDimitry Andric 191cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI friend constexpr bool operator==(__iterator const& __x, __iterator const& __y) 19281ad6265SDimitry Andric requires equality_comparable<iterator_t<_View>> 19381ad6265SDimitry Andric { 19481ad6265SDimitry Andric return __x.__current_ == __y.__current_; 19581ad6265SDimitry Andric } 19681ad6265SDimitry Andric 197cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI friend constexpr range_rvalue_reference_t<_View> 198cb14a3feSDimitry Andric iter_move(__iterator const& __it) noexcept(noexcept(ranges::iter_move(__it.__current_))) { 19981ad6265SDimitry Andric return ranges::iter_move(__it.__current_); 20081ad6265SDimitry Andric } 20181ad6265SDimitry Andric 202cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI friend constexpr void 203cb14a3feSDimitry Andric iter_swap(__iterator const& __x, 204cb14a3feSDimitry Andric __iterator const& __y) noexcept(noexcept(ranges::iter_swap(__x.__current_, __y.__current_))) 20581ad6265SDimitry Andric requires indirectly_swappable<iterator_t<_View>> 20681ad6265SDimitry Andric { 20781ad6265SDimitry Andric return ranges::iter_swap(__x.__current_, __y.__current_); 20881ad6265SDimitry Andric } 20981ad6265SDimitry Andric }; 21081ad6265SDimitry Andric 21181ad6265SDimitry Andric template <input_range _View, indirect_unary_predicate<iterator_t<_View>> _Pred> 21281ad6265SDimitry Andric requires view<_View> && is_object_v<_Pred> 2131ac55f4cSDimitry Andric class filter_view<_View, _Pred>::__sentinel { 21481ad6265SDimitry Andric public: 21581ad6265SDimitry Andric sentinel_t<_View> __end_ = sentinel_t<_View>(); 21681ad6265SDimitry Andric 217cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI __sentinel() = default; 21881ad6265SDimitry Andric 219cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI constexpr explicit __sentinel(filter_view& __parent) : __end_(ranges::end(__parent.__base_)) {} 22081ad6265SDimitry Andric 221cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI constexpr sentinel_t<_View> base() const { return __end_; } 22281ad6265SDimitry Andric 223cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI friend constexpr bool operator==(__iterator const& __x, __sentinel const& __y) { 22481ad6265SDimitry Andric return __x.__current_ == __y.__end_; 22581ad6265SDimitry Andric } 22681ad6265SDimitry Andric }; 22781ad6265SDimitry Andric 22881ad6265SDimitry Andric namespace views { 22981ad6265SDimitry Andric namespace __filter { 23081ad6265SDimitry Andric struct __fn { 23181ad6265SDimitry Andric template <class _Range, class _Pred> 232cb14a3feSDimitry Andric [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr auto operator()(_Range&& __range, _Pred&& __pred) const 23381ad6265SDimitry Andric noexcept(noexcept(filter_view(std::forward<_Range>(__range), std::forward<_Pred>(__pred)))) 234cb14a3feSDimitry Andric -> decltype(filter_view(std::forward<_Range>(__range), std::forward<_Pred>(__pred))) { 235cb14a3feSDimitry Andric return filter_view(std::forward<_Range>(__range), std::forward<_Pred>(__pred)); 236cb14a3feSDimitry Andric } 23781ad6265SDimitry Andric 23881ad6265SDimitry Andric template <class _Pred> 23981ad6265SDimitry Andric requires constructible_from<decay_t<_Pred>, _Pred> 240cb14a3feSDimitry Andric [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr auto operator()(_Pred&& __pred) const 241cb14a3feSDimitry Andric noexcept(is_nothrow_constructible_v<decay_t<_Pred>, _Pred>) { 242cb14a3feSDimitry Andric return __range_adaptor_closure_t(std::__bind_back(*this, std::forward<_Pred>(__pred))); 243cb14a3feSDimitry Andric } 24481ad6265SDimitry Andric }; 24581ad6265SDimitry Andric } // namespace __filter 24681ad6265SDimitry Andric 24781ad6265SDimitry Andric inline namespace __cpo { 24881ad6265SDimitry Andric inline constexpr auto filter = __filter::__fn{}; 24981ad6265SDimitry Andric } // namespace __cpo 25081ad6265SDimitry Andric } // namespace views 25181ad6265SDimitry Andric 25281ad6265SDimitry Andric } // namespace ranges 25381ad6265SDimitry Andric 25406c3fb27SDimitry Andric #endif // _LIBCPP_STD_VER >= 20 25581ad6265SDimitry Andric 25681ad6265SDimitry Andric _LIBCPP_END_NAMESPACE_STD 25781ad6265SDimitry Andric 258*b3edf446SDimitry Andric _LIBCPP_POP_MACROS 259*b3edf446SDimitry Andric 26081ad6265SDimitry Andric #endif // _LIBCPP___RANGES_FILTER_VIEW_H 261