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_STRIDE_VIEW_H
11#define _LIBCPP___RANGES_STRIDE_VIEW_H
12
13#include <__assert>
14#include <__compare/three_way_comparable.h>
15#include <__concepts/constructible.h>
16#include <__concepts/convertible_to.h>
17#include <__concepts/derived_from.h>
18#include <__concepts/equality_comparable.h>
19#include <__config>
20#include <__functional/bind_back.h>
21#include <__iterator/advance.h>
22#include <__iterator/concepts.h>
23#include <__iterator/default_sentinel.h>
24#include <__iterator/distance.h>
25#include <__iterator/iter_move.h>
26#include <__iterator/iter_swap.h>
27#include <__iterator/iterator_traits.h>
28#include <__ranges/access.h>
29#include <__ranges/all.h>
30#include <__ranges/concepts.h>
31#include <__ranges/enable_borrowed_range.h>
32#include <__ranges/range_adaptor.h>
33#include <__ranges/view_interface.h>
34#include <__type_traits/make_unsigned.h>
35
36#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
37# pragma GCC system_header
38#endif
39
40_LIBCPP_PUSH_MACROS
41#include <__undef_macros>
42
43_LIBCPP_BEGIN_NAMESPACE_STD
44
45#if _LIBCPP_STD_VER >= 23
46
47namespace ranges {
48
49template <class _Value>
50_LIBCPP_HIDE_FROM_ABI constexpr _Value __div_ceil(_Value __left, _Value __right) {
51 _Value __r = __left / __right;
52 if (__left % __right) {
53 ++__r;
54 }
55 return __r;
56}
57
58template <input_range _View>
59 requires view<_View>
60class stride_view : public view_interface<stride_view<_View>> {
61 _LIBCPP_NO_UNIQUE_ADDRESS _View __base_ = _View();
62 range_difference_t<_View> __stride_ = 0;
63
64 template <bool _Const>
65 class __iterator;
66
67public:
68 _LIBCPP_HIDE_FROM_ABI constexpr explicit stride_view(_View __base, range_difference_t<_View> __stride)
69 : __base_(std::move(__base)), __stride_(__stride) {
70 _LIBCPP_ASSERT_ARGUMENT_WITHIN_DOMAIN(__stride > 0, "The value of stride must be greater than 0");
71 }
72
73 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr _View base() const&
74 requires copy_constructible<_View>
75 {
76 return __base_;
77 }
78
79 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr _View base() && { return std::move(__base_); }
80
81 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr range_difference_t<_View> stride() const noexcept { return __stride_; }
82
83 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr auto begin()
84 requires(!__simple_view<_View>)
85 {
86 return __iterator</*_Const=*/false>(this, ranges::begin(__base_), 0);
87 }
88
89 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr auto begin() const
90 requires range<const _View>
91 {
92 return __iterator</*_Const=*/true>(this, ranges::begin(__base_), 0);
93 }
94
95 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr auto end()
96 requires(!__simple_view<_View>)
97 {
98 if constexpr (common_range<_View> && sized_range<_View> && forward_range<_View>) {
99 auto __missing = (__stride_ - ranges::distance(__base_) % __stride_) % __stride_;
100 return __iterator</*_Const=*/false>(this, ranges::end(__base_), __missing);
101 } else if constexpr (common_range<_View> && !bidirectional_range<_View>) {
102 return __iterator</*_Const=*/false>(this, ranges::end(__base_), 0);
103 } else {
104 return default_sentinel;
105 }
106 }
107
108 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr auto end() const
109 requires(range<const _View>)
110 {
111 if constexpr (common_range<const _View> && sized_range<const _View> && forward_range<const _View>) {
112 auto __missing = (__stride_ - ranges::distance(__base_) % __stride_) % __stride_;
113 return __iterator</*_Const=*/true>(this, ranges::end(__base_), __missing);
114 } else if constexpr (common_range<const _View> && !bidirectional_range<const _View>) {
115 return __iterator</*_Const=*/true>(this, ranges::end(__base_), 0);
116 } else {
117 return default_sentinel;
118 }
119 }
120
121 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr auto size()
122 requires sized_range<_View>
123 {
124 return std::__to_unsigned_like(ranges::__div_ceil(ranges::distance(__base_), __stride_));
125 }
126
127 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr auto size() const
128 requires sized_range<const _View>
129 {
130 return std::__to_unsigned_like(ranges::__div_ceil(ranges::distance(__base_), __stride_));
131 }
132}; // class stride_view
133
134template <class _Range>
135stride_view(_Range&&, range_difference_t<_Range>) -> stride_view<views::all_t<_Range>>;
136
137template <class _View>
138struct __stride_iterator_category {};
139
140template <forward_range _View>
141struct __stride_iterator_category<_View> {
142 using _Cat _LIBCPP_NODEBUG = typename iterator_traits<iterator_t<_View>>::iterator_category;
143 using iterator_category =
144 _If<derived_from<_Cat, random_access_iterator_tag>,
145 /* then */ random_access_iterator_tag,
146 /* else */ _Cat >;
147};
148
149template <input_range _View>
150 requires view<_View>
151template <bool _Const>
152class stride_view<_View>::__iterator : public __stride_iterator_category<__maybe_const<_Const, _View>> {
153 using _Parent _LIBCPP_NODEBUG = __maybe_const<_Const, stride_view<_View>>;
154 using _Base _LIBCPP_NODEBUG = __maybe_const<_Const, _View>;
155
156 _LIBCPP_NO_UNIQUE_ADDRESS iterator_t<_Base> __current_ = iterator_t<_Base>();
157 _LIBCPP_NO_UNIQUE_ADDRESS ranges::sentinel_t<_Base> __end_ = ranges::sentinel_t<_Base>();
158 range_difference_t<_Base> __stride_ = 0;
159 range_difference_t<_Base> __missing_ = 0;
160
161 friend stride_view;
162
163 _LIBCPP_HIDE_FROM_ABI constexpr __iterator(
164 _Parent* __parent, ranges::iterator_t<_Base> __current, range_difference_t<_Base> __missing)
165 : __current_(std::move(__current)),
166 __end_(ranges::end(__parent->__base_)),
167 __stride_(__parent->__stride_),
168 __missing_(__missing) {}
169
170 static consteval auto __get_stride_view_iterator_concept() {
171 if constexpr (random_access_range<_Base>) {
172 return random_access_iterator_tag{};
173 } else if constexpr (bidirectional_range<_Base>) {
174 return bidirectional_iterator_tag{};
175 } else if constexpr (forward_range<_Base>) {
176 return forward_iterator_tag{};
177 } else {
178 return input_iterator_tag{};
179 }
180 }
181
182public:
183 using difference_type = range_difference_t<_Base>;
184 using value_type = range_value_t<_Base>;
185 using iterator_concept = decltype(__get_stride_view_iterator_concept());
186 // using iterator_category = inherited;
187
188 _LIBCPP_HIDE_FROM_ABI __iterator()
189 requires default_initializable<iterator_t<_Base>>
190 = default;
191
192 _LIBCPP_HIDE_FROM_ABI constexpr __iterator(__iterator<!_Const> __i)
193 requires _Const && convertible_to<ranges::iterator_t<_View>, iterator_t<_Base>> &&
194 convertible_to<sentinel_t<_View>, sentinel_t<_Base>>
195 : __current_(std::move(__i.__current_)),
196 __end_(std::move(__i.__end_)),
197 __stride_(__i.__stride_),
198 __missing_(__i.__missing_) {}
199
200 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr iterator_t<_Base> const& base() const& noexcept { return __current_; }
201 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr iterator_t<_Base> base() && { return std::move(__current_); }
202
203 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr decltype(auto) operator*() const {
204 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(__current_ != __end_, "Cannot dereference an iterator at the end.");
205 return *__current_;
206 }
207
208 _LIBCPP_HIDE_FROM_ABI constexpr __iterator& operator++() {
209 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(__current_ != __end_, "Cannot increment an iterator already at the end.");
210 __missing_ = ranges::advance(__current_, __stride_, __end_);
211 return *this;
212 }
213
214 _LIBCPP_HIDE_FROM_ABI constexpr void operator++(int) {
215 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(__current_ != __end_, "Cannot increment an iterator already at the end.");
216 ++*this;
217 }
218 _LIBCPP_HIDE_FROM_ABI constexpr __iterator operator++(int)
219 requires forward_range<_Base>
220 {
221 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(__current_ != __end_, "Cannot increment an iterator already at the end.");
222 auto __tmp = *this;
223 ++*this;
224 return __tmp;
225 }
226
227 _LIBCPP_HIDE_FROM_ABI constexpr __iterator& operator--()
228 requires bidirectional_range<_Base>
229 {
230 ranges::advance(__current_, __missing_ - __stride_);
231 __missing_ = 0;
232 return *this;
233 }
234 _LIBCPP_HIDE_FROM_ABI constexpr __iterator operator--(int)
235 requires bidirectional_range<_Base>
236 {
237 auto __tmp = *this;
238 --*this;
239 return __tmp;
240 }
241
242 _LIBCPP_HIDE_FROM_ABI constexpr __iterator& operator+=(difference_type __n)
243 requires random_access_range<_Base>
244 {
245 if (__n > 0) {
246 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(ranges::distance(__current_, __end_) > __stride_ * (__n - 1),
247 "Advancing the iterator beyond the end is not allowed.");
248 ranges::advance(__current_, __stride_ * (__n - 1));
249 __missing_ = ranges::advance(__current_, __stride_, __end_);
250
251 } else if (__n < 0) {
252 ranges::advance(__current_, __stride_ * __n + __missing_);
253 __missing_ = 0;
254 }
255 return *this;
256 }
257
258 _LIBCPP_HIDE_FROM_ABI constexpr __iterator& operator-=(difference_type __n)
259 requires random_access_range<_Base>
260 {
261 return *this += -__n;
262 }
263
264 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr decltype(auto) operator[](difference_type __n) const
265 requires random_access_range<_Base>
266 {
267 return *(*this + __n);
268 }
269
270 _LIBCPP_HIDE_FROM_ABI friend constexpr bool operator==(__iterator const& __x, default_sentinel_t) {
271 return __x.__current_ == __x.__end_;
272 }
273
274 _LIBCPP_HIDE_FROM_ABI friend constexpr bool operator==(__iterator const& __x, __iterator const& __y)
275 requires equality_comparable<iterator_t<_Base>>
276 {
277 return __x.__current_ == __y.__current_;
278 }
279
280 _LIBCPP_HIDE_FROM_ABI friend constexpr bool operator<(__iterator const& __x, __iterator const& __y)
281 requires random_access_range<_Base>
282 {
283 return __x.__current_ < __y.__current_;
284 }
285
286 _LIBCPP_HIDE_FROM_ABI friend constexpr bool operator>(__iterator const& __x, __iterator const& __y)
287 requires random_access_range<_Base>
288 {
289 return __y < __x;
290 }
291
292 _LIBCPP_HIDE_FROM_ABI friend constexpr bool operator<=(__iterator const& __x, __iterator const& __y)
293 requires random_access_range<_Base>
294 {
295 return !(__y < __x);
296 }
297
298 _LIBCPP_HIDE_FROM_ABI friend constexpr bool operator>=(__iterator const& __x, __iterator const& __y)
299 requires random_access_range<_Base>
300 {
301 return !(__x < __y);
302 }
303
304 _LIBCPP_HIDE_FROM_ABI friend constexpr auto operator<=>(__iterator const& __x, __iterator const& __y)
305 requires random_access_range<_Base> && three_way_comparable<iterator_t<_Base>>
306 {
307 return __x.__current_ <=> __y.__current_;
308 }
309
310 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI friend constexpr __iterator operator+(__iterator const& __i, difference_type __s)
311 requires random_access_range<_Base>
312 {
313 auto __r = __i;
314 __r += __s;
315 return __r;
316 }
317 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI friend constexpr __iterator operator+(difference_type __s, __iterator const& __i)
318 requires random_access_range<_Base>
319 {
320 auto __r = __i;
321 __r += __s;
322 return __r;
323 }
324
325 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI friend constexpr __iterator operator-(__iterator const& __i, difference_type __s)
326 requires random_access_range<_Base>
327 {
328 auto __r = __i;
329 __r -= __s;
330 return __r;
331 }
332
333 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI friend constexpr difference_type
334 operator-(__iterator const& __x, __iterator const& __y)
335 requires sized_sentinel_for<iterator_t<_Base>, iterator_t<_Base>>
336 {
337 if constexpr (forward_range<_Base>) {
338 auto __n = __x.__current_ - __y.__current_;
339 return (__n + __x.__missing_ - __y.__missing_) / __x.__stride_;
340 }
341 auto __n = __x.__current_ - __y.__current_;
342 if (__n < 0) {
343 return -ranges::__div_ceil(-__n, __x.__stride_);
344 }
345 return ranges::__div_ceil(__n, __x.__stride_);
346 }
347
348 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI friend constexpr difference_type
349 operator-(default_sentinel_t, __iterator const& __x)
350 requires sized_sentinel_for<sentinel_t<_Base>, iterator_t<_Base>>
351 {
352 return ranges::__div_ceil(__x.__end_ - __x.__current_, __x.__stride_);
353 }
354 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI friend constexpr difference_type
355 operator-(__iterator const& __x, default_sentinel_t __y)
356 requires sized_sentinel_for<sentinel_t<_Base>, iterator_t<_Base>>
357 {
358 return -(__y - __x);
359 }
360
361 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI friend constexpr range_rvalue_reference_t<_Base>
362 iter_move(__iterator const& __it) noexcept(noexcept(ranges::iter_move(__it.__current_))) {
363 return ranges::iter_move(__it.__current_);
364 }
365
366 _LIBCPP_HIDE_FROM_ABI friend constexpr void
367 iter_swap(__iterator const& __x,
368 __iterator const& __y) noexcept(noexcept(ranges::iter_swap(__x.__current_, __y.__current_)))
369 requires indirectly_swappable<iterator_t<_Base>>
370 {
371 return ranges::iter_swap(__x.__current_, __y.__current_);
372 }
373}; // class stride_view::__iterator
374
375template <class _Tp>
376inline constexpr bool enable_borrowed_range<stride_view<_Tp>> = enable_borrowed_range<_Tp>;
377
378namespace views {
379namespace __stride_view {
380struct __fn {
381 // clang-format off
382 template <viewable_range _Range>
383 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI
384 constexpr auto operator()(_Range&& __range, range_difference_t<_Range> __n) const
385 noexcept(noexcept(stride_view{std::forward<_Range>(__range), __n}))
386 -> decltype( stride_view{std::forward<_Range>(__range), __n})
387 { return stride_view(std::forward<_Range>(__range), __n); }
388 // clang-format on
389
390 template <class _Np>
391 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr auto operator()(_Np&& __n) const {
392 return __pipeable(std::__bind_back(*this, std::forward<_Np>(__n)));
393 }
394};
395} // namespace __stride_view
396
397inline namespace __cpo {
398inline constexpr auto stride = __stride_view::__fn{};
399} // namespace __cpo
400} // namespace views
401
402} // namespace ranges
403
404#endif // _LIBCPP_STD_VER >= 23
405
406_LIBCPP_END_NAMESPACE_STD
407
408_LIBCPP_POP_MACROS
409
410#endif // _LIBCPP___RANGES_STRIDE_VIEW_H
411