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 10 #ifndef _LIBCPP___RANGES_CHUNK_BY_VIEW_H 11 #define _LIBCPP___RANGES_CHUNK_BY_VIEW_H 12 13 #include <__algorithm/ranges_adjacent_find.h> 14 #include <__assert> 15 #include <__concepts/constructible.h> 16 #include <__config> 17 #include <__functional/bind_back.h> 18 #include <__functional/invoke.h> 19 #include <__iterator/concepts.h> 20 #include <__iterator/default_sentinel.h> 21 #include <__iterator/iterator_traits.h> 22 #include <__iterator/next.h> 23 #include <__iterator/prev.h> 24 #include <__memory/addressof.h> 25 #include <__ranges/access.h> 26 #include <__ranges/all.h> 27 #include <__ranges/concepts.h> 28 #include <__ranges/movable_box.h> 29 #include <__ranges/non_propagating_cache.h> 30 #include <__ranges/range_adaptor.h> 31 #include <__ranges/reverse_view.h> 32 #include <__ranges/subrange.h> 33 #include <__ranges/view_interface.h> 34 #include <__type_traits/conditional.h> 35 #include <__type_traits/decay.h> 36 #include <__type_traits/is_nothrow_constructible.h> 37 #include <__type_traits/is_object.h> 38 #include <__utility/forward.h> 39 #include <__utility/in_place.h> 40 #include <__utility/move.h> 41 42 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 43 # pragma GCC system_header 44 #endif 45 46 _LIBCPP_PUSH_MACROS 47 #include <__undef_macros> 48 49 _LIBCPP_BEGIN_NAMESPACE_STD 50 51 #if _LIBCPP_STD_VER >= 23 52 53 namespace ranges { 54 55 template <forward_range _View, indirect_binary_predicate<iterator_t<_View>, iterator_t<_View>> _Pred> 56 requires view<_View> && is_object_v<_Pred> 57 class _LIBCPP_ABI_2023_OVERLAPPING_SUBOBJECT_FIX_TAG chunk_by_view 58 : public view_interface<chunk_by_view<_View, _Pred>> { 59 _LIBCPP_NO_UNIQUE_ADDRESS _View __base_ = _View(); 60 _LIBCPP_NO_UNIQUE_ADDRESS __movable_box<_Pred> __pred_; 61 62 // We cache the result of begin() to allow providing an amortized O(1). 63 using _Cache = __non_propagating_cache<iterator_t<_View>>; 64 _Cache __cached_begin_; 65 66 class __iterator; 67 68 _LIBCPP_HIDE_FROM_ABI constexpr iterator_t<_View> __find_next(iterator_t<_View> __current) { 69 // Note: this duplicates a check in `optional` but provides a better error message. 70 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS( 71 __pred_.__has_value(), "Trying to call __find_next() on a chunk_by_view that does not have a valid predicate."); 72 auto __reversed_pred = [this]<class _Tp, class _Up>(_Tp&& __x, _Up&& __y) -> bool { 73 return !std::invoke(*__pred_, std::forward<_Tp>(__x), std::forward<_Up>(__y)); 74 }; 75 return ranges::next( 76 ranges::adjacent_find(__current, ranges::end(__base_), __reversed_pred), 1, ranges::end(__base_)); 77 } 78 79 _LIBCPP_HIDE_FROM_ABI constexpr iterator_t<_View> __find_prev(iterator_t<_View> __current) 80 requires bidirectional_range<_View> 81 { 82 // Attempting to decrement a begin iterator is a no-op (`__find_prev` would return the same argument given to it). 83 _LIBCPP_ASSERT_PEDANTIC(__current != ranges::begin(__base_), "Trying to call __find_prev() on a begin iterator."); 84 // Note: this duplicates a check in `optional` but provides a better error message. 85 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS( 86 __pred_.__has_value(), "Trying to call __find_prev() on a chunk_by_view that does not have a valid predicate."); 87 88 auto __first = ranges::begin(__base_); 89 reverse_view __reversed{subrange{__first, __current}}; 90 auto __reversed_pred = [this]<class _Tp, class _Up>(_Tp&& __x, _Up&& __y) -> bool { 91 return !std::invoke(*__pred_, std::forward<_Up>(__y), std::forward<_Tp>(__x)); 92 }; 93 return ranges::prev(ranges::adjacent_find(__reversed, __reversed_pred).base(), 1, std::move(__first)); 94 } 95 96 public: 97 _LIBCPP_HIDE_FROM_ABI chunk_by_view() 98 requires default_initializable<_View> && default_initializable<_Pred> 99 = default; 100 101 _LIBCPP_HIDE_FROM_ABI constexpr explicit chunk_by_view(_View __base, _Pred __pred) 102 : __base_(std::move(__base)), __pred_(in_place, std::move(__pred)) {} 103 104 _LIBCPP_HIDE_FROM_ABI constexpr _View base() const& 105 requires copy_constructible<_View> 106 { 107 return __base_; 108 } 109 110 _LIBCPP_HIDE_FROM_ABI constexpr _View base() && { return std::move(__base_); } 111 112 _LIBCPP_HIDE_FROM_ABI constexpr const _Pred& pred() const { return *__pred_; } 113 114 _LIBCPP_HIDE_FROM_ABI constexpr __iterator begin() { 115 // Note: this duplicates a check in `optional` but provides a better error message. 116 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS( 117 __pred_.__has_value(), "Trying to call begin() on a chunk_by_view that does not have a valid predicate."); 118 119 auto __first = ranges::begin(__base_); 120 if (!__cached_begin_.__has_value()) { 121 __cached_begin_.__emplace(__find_next(__first)); 122 } 123 return {*this, std::move(__first), *__cached_begin_}; 124 } 125 126 _LIBCPP_HIDE_FROM_ABI constexpr auto end() { 127 if constexpr (common_range<_View>) { 128 return __iterator{*this, ranges::end(__base_), ranges::end(__base_)}; 129 } else { 130 return default_sentinel; 131 } 132 } 133 }; 134 135 template <class _Range, class _Pred> 136 chunk_by_view(_Range&&, _Pred) -> chunk_by_view<views::all_t<_Range>, _Pred>; 137 138 template <forward_range _View, indirect_binary_predicate<iterator_t<_View>, iterator_t<_View>> _Pred> 139 requires view<_View> && is_object_v<_Pred> 140 class chunk_by_view<_View, _Pred>::__iterator { 141 friend chunk_by_view; 142 143 chunk_by_view* __parent_ = nullptr; 144 _LIBCPP_NO_UNIQUE_ADDRESS iterator_t<_View> __current_ = iterator_t<_View>(); 145 _LIBCPP_NO_UNIQUE_ADDRESS iterator_t<_View> __next_ = iterator_t<_View>(); 146 147 _LIBCPP_HIDE_FROM_ABI constexpr __iterator( 148 chunk_by_view& __parent, iterator_t<_View> __current, iterator_t<_View> __next) 149 : __parent_(std::addressof(__parent)), __current_(__current), __next_(__next) {} 150 151 public: 152 using value_type = subrange<iterator_t<_View>>; 153 using difference_type = range_difference_t<_View>; 154 using iterator_category = input_iterator_tag; 155 using iterator_concept = conditional_t<bidirectional_range<_View>, bidirectional_iterator_tag, forward_iterator_tag>; 156 157 _LIBCPP_HIDE_FROM_ABI __iterator() = default; 158 159 _LIBCPP_HIDE_FROM_ABI constexpr value_type operator*() const { 160 // If the iterator is at end, this would return an empty range which can be checked by the calling code and doesn't 161 // necessarily lead to a bad access. 162 _LIBCPP_ASSERT_PEDANTIC(__current_ != __next_, "Trying to dereference past-the-end chunk_by_view iterator."); 163 return {__current_, __next_}; 164 } 165 166 _LIBCPP_HIDE_FROM_ABI constexpr __iterator& operator++() { 167 // Attempting to increment an end iterator is a no-op (`__find_next` would return the same argument given to it). 168 _LIBCPP_ASSERT_PEDANTIC(__current_ != __next_, "Trying to increment past end chunk_by_view iterator."); 169 __current_ = __next_; 170 __next_ = __parent_->__find_next(__current_); 171 return *this; 172 } 173 174 _LIBCPP_HIDE_FROM_ABI constexpr __iterator operator++(int) { 175 auto __tmp = *this; 176 ++*this; 177 return __tmp; 178 } 179 180 _LIBCPP_HIDE_FROM_ABI constexpr __iterator& operator--() 181 requires bidirectional_range<_View> 182 { 183 __next_ = __current_; 184 __current_ = __parent_->__find_prev(__next_); 185 return *this; 186 } 187 188 _LIBCPP_HIDE_FROM_ABI constexpr __iterator operator--(int) 189 requires bidirectional_range<_View> 190 { 191 auto __tmp = *this; 192 --*this; 193 return __tmp; 194 } 195 196 _LIBCPP_HIDE_FROM_ABI friend constexpr bool operator==(const __iterator& __x, const __iterator& __y) { 197 return __x.__current_ == __y.__current_; 198 } 199 200 _LIBCPP_HIDE_FROM_ABI friend constexpr bool operator==(const __iterator& __x, default_sentinel_t) { 201 return __x.__current_ == __x.__next_; 202 } 203 }; 204 205 namespace views { 206 namespace __chunk_by { 207 struct __fn { 208 template <class _Range, class _Pred> 209 _LIBCPP_NODISCARD_EXT _LIBCPP_HIDE_FROM_ABI constexpr auto operator()(_Range&& __range, _Pred&& __pred) const 210 noexcept(noexcept(/**/ chunk_by_view(std::forward<_Range>(__range), std::forward<_Pred>(__pred)))) 211 -> decltype(/*--*/ chunk_by_view(std::forward<_Range>(__range), std::forward<_Pred>(__pred))) { 212 return /*-------------*/ chunk_by_view(std::forward<_Range>(__range), std::forward<_Pred>(__pred)); 213 } 214 215 template <class _Pred> 216 requires constructible_from<decay_t<_Pred>, _Pred> 217 _LIBCPP_NODISCARD_EXT _LIBCPP_HIDE_FROM_ABI constexpr auto operator()(_Pred&& __pred) const 218 noexcept(is_nothrow_constructible_v<decay_t<_Pred>, _Pred>) { 219 return __range_adaptor_closure_t(std::__bind_back(*this, std::forward<_Pred>(__pred))); 220 } 221 }; 222 } // namespace __chunk_by 223 224 inline namespace __cpo { 225 inline constexpr auto chunk_by = __chunk_by::__fn{}; 226 } // namespace __cpo 227 } // namespace views 228 } // namespace ranges 229 230 #endif // _LIBCPP_STD_VER >= 23 231 232 _LIBCPP_END_NAMESPACE_STD 233 234 _LIBCPP_POP_MACROS 235 236 #endif // _LIBCPP___RANGES_CHUNK_BY_VIEW_H 237