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_SPLIT_VIEW_H 11 #define _LIBCPP___RANGES_SPLIT_VIEW_H 12 13 #include <__algorithm/ranges_search.h> 14 #include <__concepts/constructible.h> 15 #include <__config> 16 #include <__functional/bind_back.h> 17 #include <__functional/ranges_operations.h> 18 #include <__iterator/indirectly_comparable.h> 19 #include <__iterator/iterator_traits.h> 20 #include <__memory/addressof.h> 21 #include <__ranges/access.h> 22 #include <__ranges/all.h> 23 #include <__ranges/concepts.h> 24 #include <__ranges/empty.h> 25 #include <__ranges/non_propagating_cache.h> 26 #include <__ranges/range_adaptor.h> 27 #include <__ranges/single_view.h> 28 #include <__ranges/subrange.h> 29 #include <__ranges/view_interface.h> 30 #include <__type_traits/decay.h> 31 #include <__type_traits/is_nothrow_constructible.h> 32 #include <__utility/forward.h> 33 #include <__utility/move.h> 34 35 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 36 # pragma GCC system_header 37 #endif 38 39 _LIBCPP_BEGIN_NAMESPACE_STD 40 41 #if _LIBCPP_STD_VER >= 20 42 43 namespace ranges { 44 45 template <forward_range _View, forward_range _Pattern> 46 requires view<_View> && view<_Pattern> && 47 indirectly_comparable<iterator_t<_View>, iterator_t<_Pattern>, ranges::equal_to> 48 class split_view : public view_interface<split_view<_View, _Pattern>> { 49 private: 50 _LIBCPP_NO_UNIQUE_ADDRESS _View __base_ = _View(); 51 _LIBCPP_NO_UNIQUE_ADDRESS _Pattern __pattern_ = _Pattern(); 52 using _Cache = __non_propagating_cache<subrange<iterator_t<_View>>>; 53 _Cache __cached_begin_ = _Cache(); 54 55 template <class, class> 56 friend struct __iterator; 57 58 template <class, class> 59 friend struct __sentinel; 60 61 struct __iterator; 62 struct __sentinel; 63 64 _LIBCPP_HIDE_FROM_ABI constexpr subrange<iterator_t<_View>> __find_next(iterator_t<_View> __it) { 65 auto [__begin, __end] = ranges::search(subrange(__it, ranges::end(__base_)), __pattern_); 66 if (__begin != ranges::end(__base_) && ranges::empty(__pattern_)) { 67 ++__begin; 68 ++__end; 69 } 70 return {__begin, __end}; 71 } 72 73 public: 74 _LIBCPP_HIDE_FROM_ABI split_view() 75 requires default_initializable<_View> && default_initializable<_Pattern> 76 = default; 77 78 _LIBCPP_HIDE_FROM_ABI constexpr _LIBCPP_EXPLICIT_SINCE_CXX23 split_view(_View __base, _Pattern __pattern) 79 : __base_(std::move(__base)), __pattern_(std::move((__pattern))) {} 80 81 template <forward_range _Range> 82 requires constructible_from<_View, views::all_t<_Range>> && 83 constructible_from<_Pattern, single_view<range_value_t<_Range>>> 84 _LIBCPP_HIDE_FROM_ABI constexpr _LIBCPP_EXPLICIT_SINCE_CXX23 85 split_view(_Range&& __range, range_value_t<_Range> __elem) 86 : __base_(views::all(std::forward<_Range>(__range))), __pattern_(views::single(std::move(__elem))) {} 87 88 _LIBCPP_HIDE_FROM_ABI constexpr _View base() const& 89 requires copy_constructible<_View> 90 { 91 return __base_; 92 } 93 94 _LIBCPP_HIDE_FROM_ABI constexpr _View base() && { return std::move(__base_); } 95 96 _LIBCPP_HIDE_FROM_ABI constexpr __iterator begin() { 97 if (!__cached_begin_.__has_value()) { 98 __cached_begin_.__emplace(__find_next(ranges::begin(__base_))); 99 } 100 return {*this, ranges::begin(__base_), *__cached_begin_}; 101 } 102 103 _LIBCPP_HIDE_FROM_ABI constexpr auto end() { 104 if constexpr (common_range<_View>) { 105 return __iterator{*this, ranges::end(__base_), {}}; 106 } else { 107 return __sentinel{*this}; 108 } 109 } 110 }; 111 112 template <class _Range, class _Pattern> 113 split_view(_Range&&, _Pattern&&) -> split_view<views::all_t<_Range>, views::all_t<_Pattern>>; 114 115 template <forward_range _Range> 116 split_view(_Range&&, range_value_t<_Range>) -> split_view<views::all_t<_Range>, single_view<range_value_t<_Range>>>; 117 118 template <forward_range _View, forward_range _Pattern> 119 requires view<_View> && view<_Pattern> && 120 indirectly_comparable<iterator_t<_View>, iterator_t<_Pattern>, ranges::equal_to> 121 struct split_view<_View, _Pattern>::__iterator { 122 private: 123 split_view* __parent_ = nullptr; 124 _LIBCPP_NO_UNIQUE_ADDRESS iterator_t<_View> __cur_ = iterator_t<_View>(); 125 _LIBCPP_NO_UNIQUE_ADDRESS subrange<iterator_t<_View>> __next_ = subrange<iterator_t<_View>>(); 126 bool __trailing_empty_ = false; 127 128 friend struct __sentinel; 129 130 public: 131 using iterator_concept = forward_iterator_tag; 132 using iterator_category = input_iterator_tag; 133 using value_type = subrange<iterator_t<_View>>; 134 using difference_type = range_difference_t<_View>; 135 136 _LIBCPP_HIDE_FROM_ABI __iterator() = default; 137 138 _LIBCPP_HIDE_FROM_ABI constexpr __iterator( 139 split_view<_View, _Pattern>& __parent, iterator_t<_View> __current, subrange<iterator_t<_View>> __next) 140 : __parent_(std::addressof(__parent)), __cur_(std::move(__current)), __next_(std::move(__next)) {} 141 142 _LIBCPP_HIDE_FROM_ABI constexpr iterator_t<_View> base() const { return __cur_; } 143 144 _LIBCPP_HIDE_FROM_ABI constexpr value_type operator*() const { return {__cur_, __next_.begin()}; } 145 146 _LIBCPP_HIDE_FROM_ABI constexpr __iterator& operator++() { 147 __cur_ = __next_.begin(); 148 if (__cur_ != ranges::end(__parent_->__base_)) { 149 __cur_ = __next_.end(); 150 if (__cur_ == ranges::end(__parent_->__base_)) { 151 __trailing_empty_ = true; 152 __next_ = {__cur_, __cur_}; 153 } else { 154 __next_ = __parent_->__find_next(__cur_); 155 } 156 } else { 157 __trailing_empty_ = false; 158 } 159 return *this; 160 } 161 162 _LIBCPP_HIDE_FROM_ABI constexpr __iterator operator++(int) { 163 auto __tmp = *this; 164 ++*this; 165 return __tmp; 166 } 167 168 _LIBCPP_HIDE_FROM_ABI friend constexpr bool operator==(const __iterator& __x, const __iterator& __y) { 169 return __x.__cur_ == __y.__cur_ && __x.__trailing_empty_ == __y.__trailing_empty_; 170 } 171 }; 172 173 template <forward_range _View, forward_range _Pattern> 174 requires view<_View> && view<_Pattern> && 175 indirectly_comparable<iterator_t<_View>, iterator_t<_Pattern>, ranges::equal_to> 176 struct split_view<_View, _Pattern>::__sentinel { 177 private: 178 _LIBCPP_NO_UNIQUE_ADDRESS sentinel_t<_View> __end_ = sentinel_t<_View>(); 179 180 _LIBCPP_HIDE_FROM_ABI static constexpr bool __equals(const __iterator& __x, const __sentinel& __y) { 181 return __x.__cur_ == __y.__end_ && !__x.__trailing_empty_; 182 } 183 184 public: 185 _LIBCPP_HIDE_FROM_ABI __sentinel() = default; 186 187 _LIBCPP_HIDE_FROM_ABI constexpr explicit __sentinel(split_view<_View, _Pattern>& __parent) 188 : __end_(ranges::end(__parent.__base_)) {} 189 190 _LIBCPP_HIDE_FROM_ABI friend constexpr bool operator==(const __iterator& __x, const __sentinel& __y) { 191 return __equals(__x, __y); 192 } 193 }; 194 195 namespace views { 196 namespace __split_view { 197 struct __fn : __range_adaptor_closure<__fn> { 198 // clang-format off 199 template <class _Range, class _Pattern> 200 _LIBCPP_NODISCARD_EXT _LIBCPP_HIDE_FROM_ABI 201 constexpr auto operator()(_Range&& __range, _Pattern&& __pattern) const 202 noexcept(noexcept(split_view(std::forward<_Range>(__range), std::forward<_Pattern>(__pattern)))) 203 -> decltype( split_view(std::forward<_Range>(__range), std::forward<_Pattern>(__pattern))) 204 { return split_view(std::forward<_Range>(__range), std::forward<_Pattern>(__pattern)); } 205 // clang-format on 206 207 template <class _Pattern> 208 requires constructible_from<decay_t<_Pattern>, _Pattern> 209 _LIBCPP_NODISCARD_EXT _LIBCPP_HIDE_FROM_ABI constexpr auto operator()(_Pattern&& __pattern) const 210 noexcept(is_nothrow_constructible_v<decay_t<_Pattern>, _Pattern>) { 211 return __range_adaptor_closure_t(std::__bind_back(*this, std::forward<_Pattern>(__pattern))); 212 } 213 }; 214 } // namespace __split_view 215 216 inline namespace __cpo { 217 inline constexpr auto split = __split_view::__fn{}; 218 } // namespace __cpo 219 } // namespace views 220 221 } // namespace ranges 222 223 #endif // _LIBCPP_STD_VER >= 20 224 225 _LIBCPP_END_NAMESPACE_STD 226 227 #endif // _LIBCPP___RANGES_SPLIT_VIEW_H 228