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 43namespace ranges { 44 45template <forward_range _View, forward_range _Pattern> 46 requires view<_View> && view<_Pattern> && 47 indirectly_comparable<iterator_t<_View>, iterator_t<_Pattern>, ranges::equal_to> 48class split_view : public view_interface<split_view<_View, _Pattern>> { 49private: 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 73public: 74 _LIBCPP_HIDE_FROM_ABI split_view() 75 requires default_initializable<_View> && default_initializable<_Pattern> 76 = default; 77 78 _LIBCPP_HIDE_FROM_ABI constexpr 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 split_view(_Range&& __range, range_value_t<_Range> __elem) 85 : __base_(views::all(std::forward<_Range>(__range))), __pattern_(views::single(std::move(__elem))) {} 86 87 _LIBCPP_HIDE_FROM_ABI constexpr _View base() const& 88 requires copy_constructible<_View> 89 { 90 return __base_; 91 } 92 93 _LIBCPP_HIDE_FROM_ABI constexpr _View base() && { return std::move(__base_); } 94 95 _LIBCPP_HIDE_FROM_ABI constexpr __iterator begin() { 96 if (!__cached_begin_.__has_value()) { 97 __cached_begin_.__emplace(__find_next(ranges::begin(__base_))); 98 } 99 return {*this, ranges::begin(__base_), *__cached_begin_}; 100 } 101 102 _LIBCPP_HIDE_FROM_ABI constexpr auto end() { 103 if constexpr (common_range<_View>) { 104 return __iterator{*this, ranges::end(__base_), {}}; 105 } else { 106 return __sentinel{*this}; 107 } 108 } 109}; 110 111template <class _Range, class _Pattern> 112split_view(_Range&&, _Pattern&&) -> split_view<views::all_t<_Range>, views::all_t<_Pattern>>; 113 114template <forward_range _Range> 115split_view(_Range&&, range_value_t<_Range>) -> split_view<views::all_t<_Range>, single_view<range_value_t<_Range>>>; 116 117template <forward_range _View, forward_range _Pattern> 118 requires view<_View> && view<_Pattern> && 119 indirectly_comparable<iterator_t<_View>, iterator_t<_Pattern>, ranges::equal_to> 120struct split_view<_View, _Pattern>::__iterator { 121private: 122 split_view* __parent_ = nullptr; 123 _LIBCPP_NO_UNIQUE_ADDRESS iterator_t<_View> __cur_ = iterator_t<_View>(); 124 _LIBCPP_NO_UNIQUE_ADDRESS subrange<iterator_t<_View>> __next_ = subrange<iterator_t<_View>>(); 125 bool __trailing_empty_ = false; 126 127 friend struct __sentinel; 128 129public: 130 using iterator_concept = forward_iterator_tag; 131 using iterator_category = input_iterator_tag; 132 using value_type = subrange<iterator_t<_View>>; 133 using difference_type = range_difference_t<_View>; 134 135 _LIBCPP_HIDE_FROM_ABI __iterator() = default; 136 137 _LIBCPP_HIDE_FROM_ABI constexpr __iterator( 138 split_view<_View, _Pattern>& __parent, iterator_t<_View> __current, subrange<iterator_t<_View>> __next) 139 : __parent_(std::addressof(__parent)), __cur_(std::move(__current)), __next_(std::move(__next)) {} 140 141 _LIBCPP_HIDE_FROM_ABI constexpr iterator_t<_View> base() const { return __cur_; } 142 143 _LIBCPP_HIDE_FROM_ABI constexpr value_type operator*() const { return {__cur_, __next_.begin()}; } 144 145 _LIBCPP_HIDE_FROM_ABI constexpr __iterator& operator++() { 146 __cur_ = __next_.begin(); 147 if (__cur_ != ranges::end(__parent_->__base_)) { 148 __cur_ = __next_.end(); 149 if (__cur_ == ranges::end(__parent_->__base_)) { 150 __trailing_empty_ = true; 151 __next_ = {__cur_, __cur_}; 152 } else { 153 __next_ = __parent_->__find_next(__cur_); 154 } 155 } else { 156 __trailing_empty_ = false; 157 } 158 return *this; 159 } 160 161 _LIBCPP_HIDE_FROM_ABI constexpr __iterator operator++(int) { 162 auto __tmp = *this; 163 ++*this; 164 return __tmp; 165 } 166 167 _LIBCPP_HIDE_FROM_ABI friend constexpr bool operator==(const __iterator& __x, const __iterator& __y) { 168 return __x.__cur_ == __y.__cur_ && __x.__trailing_empty_ == __y.__trailing_empty_; 169 } 170}; 171 172template <forward_range _View, forward_range _Pattern> 173 requires view<_View> && view<_Pattern> && 174 indirectly_comparable<iterator_t<_View>, iterator_t<_Pattern>, ranges::equal_to> 175struct split_view<_View, _Pattern>::__sentinel { 176private: 177 _LIBCPP_NO_UNIQUE_ADDRESS sentinel_t<_View> __end_ = sentinel_t<_View>(); 178 179 _LIBCPP_HIDE_FROM_ABI static constexpr bool __equals(const __iterator& __x, const __sentinel& __y) { 180 return __x.__cur_ == __y.__end_ && !__x.__trailing_empty_; 181 } 182 183public: 184 _LIBCPP_HIDE_FROM_ABI __sentinel() = default; 185 186 _LIBCPP_HIDE_FROM_ABI constexpr explicit __sentinel(split_view<_View, _Pattern>& __parent) 187 : __end_(ranges::end(__parent.__base_)) {} 188 189 _LIBCPP_HIDE_FROM_ABI friend constexpr bool operator==(const __iterator& __x, const __sentinel& __y) { 190 return __equals(__x, __y); 191 } 192}; 193 194namespace views { 195namespace __split_view { 196struct __fn : __range_adaptor_closure<__fn> { 197 // clang-format off 198 template <class _Range, class _Pattern> 199 _LIBCPP_NODISCARD_EXT _LIBCPP_HIDE_FROM_ABI 200 constexpr auto operator()(_Range&& __range, _Pattern&& __pattern) const 201 noexcept(noexcept(split_view(std::forward<_Range>(__range), std::forward<_Pattern>(__pattern)))) 202 -> decltype( split_view(std::forward<_Range>(__range), std::forward<_Pattern>(__pattern))) 203 { return split_view(std::forward<_Range>(__range), std::forward<_Pattern>(__pattern)); } 204 // clang-format on 205 206 template <class _Pattern> 207 requires constructible_from<decay_t<_Pattern>, _Pattern> 208 _LIBCPP_NODISCARD_EXT _LIBCPP_HIDE_FROM_ABI constexpr auto operator()(_Pattern&& __pattern) const 209 noexcept(is_nothrow_constructible_v<decay_t<_Pattern>, _Pattern>) { 210 return __range_adaptor_closure_t(std::__bind_back(*this, std::forward<_Pattern>(__pattern))); 211 } 212}; 213} // namespace __split_view 214 215inline namespace __cpo { 216inline constexpr auto split = __split_view::__fn{}; 217} // namespace __cpo 218} // namespace views 219 220} // namespace ranges 221 222#endif // _LIBCPP_STD_VER >= 20 223 224_LIBCPP_END_NAMESPACE_STD 225 226#endif // _LIBCPP___RANGES_SPLIT_VIEW_H 227