diff --git a/libcxx/include/CMakeLists.txt b/libcxx/include/CMakeLists.txt --- a/libcxx/include/CMakeLists.txt +++ b/libcxx/include/CMakeLists.txt @@ -665,6 +665,7 @@ __ranges/single_view.h __ranges/size.h __ranges/split_view.h + __ranges/stride_view.h __ranges/subrange.h __ranges/take_view.h __ranges/take_while_view.h diff --git a/libcxx/include/__ranges/stride_view.h b/libcxx/include/__ranges/stride_view.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__ranges/stride_view.h @@ -0,0 +1,406 @@ +// -*- C++ -*- +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___RANGES_STRIDE_VIEW_H +#define _LIBCPP___RANGES_STRIDE_VIEW_H + +#include <__compare/three_way_comparable.h> +#include <__concepts/constructible.h> +#include <__concepts/convertible_to.h> +#include <__config> +#include <__functional/bind_back.h> +#include <__iterator/concepts.h> +#include <__iterator/default_sentinel.h> +#include <__iterator/next.h> +#include <__iterator/reverse_iterator.h> +#include <__ranges/access.h> +#include <__ranges/all.h> +#include <__ranges/concepts.h> +#include <__ranges/enable_borrowed_range.h> +#include <__ranges/non_propagating_cache.h> +#include <__ranges/range_adaptor.h> +#include <__ranges/size.h> +#include <__ranges/subrange.h> +#include <__ranges/view_interface.h> +#include <__ranges/views.h> +#include <__type_traits/conditional.h> +#include <__type_traits/maybe_const.h> +#include <__type_traits/remove_cvref.h> +#include <__utility/forward.h> +#include <__utility/move.h> +#include + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +_LIBCPP_BEGIN_NAMESPACE_STD + +#if _LIBCPP_STD_VER >= 20 + +namespace ranges { + +template +_LIBCPP_HIDE_FROM_ABI constexpr static _I div_ceil(_I __left, _I __right) { + _I __r = __left / __right; + if (__left % __right) { + __r++; + } + return __r; +} + +template + requires view<_View> +class stride_view : public view_interface> { + _LIBCPP_NO_UNIQUE_ADDRESS _View __base_ = _View(); + range_difference_t<_View> __stride_ = 0; + + template + class __iterator; + template + class __sentinel; + +public: + _LIBCPP_HIDE_FROM_ABI constexpr explicit stride_view(_View __base, range_difference_t<_View> __stride) + : __base_(std::move(__base)), __stride_(__stride) {} + + _LIBCPP_HIDE_FROM_ABI constexpr _View base() const& + requires copy_constructible<_View> + { + return __base_; + } + + _LIBCPP_HIDE_FROM_ABI constexpr _View base() && { return std::move(__base_); } + + _LIBCPP_HIDE_FROM_ABI constexpr auto stride() { return __stride_; } + + _LIBCPP_HIDE_FROM_ABI constexpr auto begin() + requires(!__simple_view<_View>) + { + return __iterator{*this, ranges::begin(__base_)}; + } + + _LIBCPP_HIDE_FROM_ABI constexpr auto begin() const + requires ranges::range + { + return __iterator{*this, ranges::begin(__base_)}; + } + + _LIBCPP_HIDE_FROM_ABI constexpr auto end() + requires(!__simple_view<_View> && common_range<_View> && sized_range<_View> && forward_range<_View>) + { + auto __missing = (__stride_ - ranges::distance(__base_) % __stride_) % __stride_; + return __iterator{*this, ranges::end(__base_), __missing}; + } + + _LIBCPP_HIDE_FROM_ABI constexpr auto end() + requires(!__simple_view<_View> && common_range<_View> && !bidirectional_range<_View>) + { + return __iterator{*this, ranges::end(__base_)}; + } + + _LIBCPP_HIDE_FROM_ABI constexpr auto end() + requires(!__simple_view<_View>) + { + return std::default_sentinel; + } + + _LIBCPP_HIDE_FROM_ABI constexpr auto end() const + requires(range && common_range && sized_range && forward_range) + { + auto __missing = (__stride_ - ranges::distance(__base_) % __stride_) % __stride_; + return __iterator{*this, ranges::end(__base_), __missing}; + } + _LIBCPP_HIDE_FROM_ABI constexpr auto end() const + requires(range && common_range<_View> && !bidirectional_range<_View>) + { + return __iterator{*this, ranges::end(__base_)}; + } + + _LIBCPP_HIDE_FROM_ABI constexpr auto end() const + requires(range) + { + return std::default_sentinel; + } +}; // class stride_view + +template +struct __stride_iterator_category {}; + +template +struct __stride_iterator_category<_View> { + using _Cat = typename iterator_traits>::iterator_category; + using iterator_category = + _If, + random_access_iterator_tag, + /* else */ _Cat >; +}; + +template + requires view<_View> +template +class stride_view<_View>::__iterator : public __stride_iterator_category<_View> { + using _Parent = __maybe_const<_Const, stride_view<_View>>; + using _Base = __maybe_const<_Const, _View>; + +public: + using difference_type = range_difference_t<_Base>; + using value_type = range_value_t<_Base>; + using iterator_concept = + _If, + random_access_iterator_tag, + _If, + bidirectional_iterator_tag, + _If, + forward_iterator_tag, + /* else */ input_iterator_tag >>>; + + _LIBCPP_NO_UNIQUE_ADDRESS iterator_t<_Base> __current_ = iterator_t<_Base>(); + _LIBCPP_NO_UNIQUE_ADDRESS ranges::sentinel_t<_Base> __end_ = ranges::sentinel_t<_Base>(); + difference_type __stride_ = 0; + difference_type __missing_ = 0; + + // using iterator_category = inherited; + _LIBCPP_HIDE_FROM_ABI __iterator() + requires default_initializable> + = default; + + _LIBCPP_HIDE_FROM_ABI constexpr __iterator(__iterator __i) + requires _Const && std::convertible_to, ranges::iterator_t<_Base>> && + std::convertible_to, ranges::sentinel_t<_Base>> + : __current_(std::move(__i.__current_)), + __end_(std::move(__i.__end_)), + __stride_(__i.__stride_), + __missing_(__i.__missing_) {} + + _LIBCPP_HIDE_FROM_ABI constexpr __iterator( + _Parent& __parent, ranges::iterator_t<_Base> __current, difference_type __missing = 0) + : __current_(std::move(__current)), + __end_(ranges::end(__parent.__base_)), + __stride_(__parent.__stride_), + __missing_(__missing) {} + + _LIBCPP_HIDE_FROM_ABI constexpr iterator_t<_View> const& base() const& noexcept { return __current_; } + _LIBCPP_HIDE_FROM_ABI constexpr iterator_t<_View> base() && { return std::move(__current_); } + + _LIBCPP_HIDE_FROM_ABI constexpr decltype(auto) operator*() const { return *__current_; } + + _LIBCPP_HIDE_FROM_ABI constexpr __iterator& operator++() { + __missing_ = ranges::advance(__current_, __stride_, __end_); + return *this; + } + + _LIBCPP_HIDE_FROM_ABI constexpr void operator++(int) { ++*this; } + _LIBCPP_HIDE_FROM_ABI constexpr __iterator operator++(int) + requires forward_range<_Base> + { + auto __tmp = *this; + ++*this; + return __tmp; + } + + _LIBCPP_HIDE_FROM_ABI constexpr __iterator& operator--() + requires bidirectional_range<_Base> + { + ranges::advance(__current_, __missing_ - __stride_); + __missing_ = 0; + return *this; + } + _LIBCPP_HIDE_FROM_ABI constexpr __iterator operator--(int) + requires bidirectional_range<_Base> + { + auto __tmp = *this; + --*this; + return __tmp; + } + + _LIBCPP_HIDE_FROM_ABI constexpr __iterator& operator+=(difference_type __s) + requires random_access_range<_Base> + { + if (__s > 0) { + ranges::advance(__current_, __stride_ * (__s - 1)); + __missing_ = ranges::advance(__current_, __stride_, __end_); + } else if (__s < 0) { + ranges::advance(__current_, __stride_ * __s + __missing_); + __missing_ = 0; + } + return *this; + } + + _LIBCPP_HIDE_FROM_ABI constexpr __iterator& operator-=(difference_type __s) + requires random_access_range<_Base> + { + return *this += -__s; + } + + _LIBCPP_HIDE_FROM_ABI constexpr __iterator& operator[](difference_type __s) const + requires random_access_range<_Base> + { + return *(*this + __s); + } + + _LIBCPP_HIDE_FROM_ABI friend constexpr bool operator==(__iterator const& __x, default_sentinel_t) { + return __x.__current_ == __x.__end_; + } + + _LIBCPP_HIDE_FROM_ABI friend constexpr bool operator==(__iterator const& __x, __iterator const& __y) + requires equality_comparable> + { + return __x.__current_ == __y.__current_; + } + + _LIBCPP_HIDE_FROM_ABI friend constexpr bool operator<(__iterator const& __x, __iterator const& __y) + requires random_access_range<_Base> + { + return __x.__current_ < __y.__current_; + } + + _LIBCPP_HIDE_FROM_ABI friend constexpr bool operator>(__iterator const& __x, __iterator const& __y) + requires random_access_range<_Base> + { + return __y < __x; + } + + _LIBCPP_HIDE_FROM_ABI friend constexpr bool operator<=(__iterator const& __x, __iterator const& __y) + requires random_access_range<_Base> + { + return !(__y < __x); + } + + _LIBCPP_HIDE_FROM_ABI friend constexpr bool operator>=(__iterator const& __x, __iterator const& __y) + requires random_access_range<_Base> + { + return !(__x < __y); + } + + _LIBCPP_HIDE_FROM_ABI friend constexpr bool operator<=>(__iterator const& __x, __iterator const& __y) + requires random_access_range<_Base> && three_way_comparable> + { + return __x.__current_ <=> __y.__current_; + } + + _LIBCPP_HIDE_FROM_ABI friend constexpr __iterator operator+(__iterator const& __i, difference_type __s) + requires random_access_range<_Base> + { + auto __r = __i; + __r += __s; + return __r; + } + _LIBCPP_HIDE_FROM_ABI friend constexpr __iterator operator+(difference_type __s, __iterator const& __i) + requires random_access_range<_Base> + { + auto __r = __i; + __r += __s; + return __r; + } + + _LIBCPP_HIDE_FROM_ABI friend constexpr __iterator operator-(__iterator const& __i, difference_type __s) + requires random_access_range<_Base> + { + auto __r = __i; + __r -= __s; + return __r; + } + + _LIBCPP_HIDE_FROM_ABI friend constexpr difference_type operator-(__iterator const& __x, __iterator const& __y) + requires sized_sentinel_for, iterator_t<_Base>> && forward_range<_Base> + { + auto __n = __x.__current_ - __y.__current_; + return (__n + __x.__missing_ - __y.__missing_) / __x.__stride_; + } + + _LIBCPP_HIDE_FROM_ABI friend constexpr difference_type operator-(__iterator const& __x, __iterator const& __y) + requires sized_sentinel_for, iterator_t<_Base>> + { + auto __n = __x.__current_ - __y.__current_; + if (__n < 0) { + return -div_ceil(-__n, __x.__stride_); + } + return div_ceil(__n, __x.__stride_); + } + + _LIBCPP_HIDE_FROM_ABI friend constexpr difference_type operator-(default_sentinel_t, __iterator const& __x) + requires sized_sentinel_for, iterator_t<_Base>> + { + return div_ceil(__x.__end_ - __x.__current_, __x.__stride_); + } + _LIBCPP_HIDE_FROM_ABI friend constexpr difference_type operator-(__iterator const& __x, default_sentinel_t __y) + requires sized_sentinel_for, iterator_t<_Base>> + { + return -(__y - __x); + } + + _LIBCPP_HIDE_FROM_ABI friend constexpr range_rvalue_reference_t<_Base> + iter_move(__iterator const& __it) noexcept(noexcept(ranges::iter_move(__it.__current_))) { + return ranges::iter_move(__it.__current_); + } + + _LIBCPP_HIDE_FROM_ABI friend constexpr void + iter_swap(__iterator const& __x, + __iterator const& __y) noexcept(noexcept(ranges::iter_swap(__x.__current_, __y.__current_))) + requires indirectly_swappable> + { + return ranges::iter_swap(__x.__current_, __y.__current_); + } +}; // class stride_view::__iterator + +template + requires view<_View> +template +class stride_view<_View>::__sentinel { +public: + sentinel_t<_View> __end_ = sentinel_t<_View>(); + + _LIBCPP_HIDE_FROM_ABI __sentinel() = default; + + _LIBCPP_HIDE_FROM_ABI constexpr explicit __sentinel(stride_view<_View>& __parent) + : __end_(ranges::end(__parent.__base_)) {} + + _LIBCPP_HIDE_FROM_ABI constexpr sentinel_t<_View> base() const { return __end_; } + + _LIBCPP_HIDE_FROM_ABI friend constexpr bool operator==(__iterator const& __x, __sentinel const& __y) { + return __x.__current_ == __y.__end_; + } +}; // class stride_view::__sentinel + +template +stride_view(_Range&&) -> stride_view>; + +template +inline constexpr bool enable_borrowed_range> = enable_borrowed_range<_Tp>; + +namespace views { +namespace __stride { +// removed this. +struct __fn { + template + [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr auto operator()(_Range&& __range, range_difference_t<_Range> __n) const + noexcept(noexcept(stride_view{std::forward<_Range>(__range)})) + -> decltype(stride_view{std::forward<_Range>(__range), __n}) { + return stride_view{std::forward<_Range>(__range), __n}; + } + + template + [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr auto operator()(_Np&& __n) const { + return __range_adaptor_closure_t(std::__bind_back(*this, std::forward<_Np>(__n))); + } +}; +} // namespace __stride + +inline namespace __cpo { +inline constexpr auto stride = __stride::__fn{}; +} // namespace __cpo +} // namespace views +} // namespace ranges + +#endif // _LIBCPP_STD_VER >= 20 + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP___RANGES_STRIDE_VIEW_H diff --git a/libcxx/include/module.modulemap.in b/libcxx/include/module.modulemap.in --- a/libcxx/include/module.modulemap.in +++ b/libcxx/include/module.modulemap.in @@ -1746,6 +1746,7 @@ export std_private_type_traits_make_unsigned } module std_private_ranges_split_view [system] { header "__ranges/split_view.h" } +module std_private_ranges_stride_view [system] { header "__ranges/stride_view.h" } module std_private_ranges_subrange [system] { header "__ranges/subrange.h" export std_private_ranges_subrange_fwd diff --git a/libcxx/include/ranges b/libcxx/include/ranges --- a/libcxx/include/ranges +++ b/libcxx/include/ranges @@ -398,6 +398,7 @@ #include <__ranges/single_view.h> #include <__ranges/size.h> #include <__ranges/split_view.h> +#include <__ranges/stride_view.h> #include <__ranges/subrange.h> #include <__ranges/take_view.h> #include <__ranges/take_while_view.h> diff --git a/libcxx/modules/std/ranges.cppm b/libcxx/modules/std/ranges.cppm --- a/libcxx/modules/std/ranges.cppm +++ b/libcxx/modules/std/ranges.cppm @@ -270,6 +270,13 @@ using std::ranges::views::zip; } // namespace views + // [range.stride], stride view + using std::ranges::stride_view; + + namespace views { + using std::ranges::views::stride; + } + #if 0 // [range.zip.transform], zip transform view using std::ranges::zip_transform_view; @@ -313,13 +320,6 @@ using std::ranges::views::chunk_by; } - // [range.stride], stride view - using std::ranges::stride_view; - - namespace views { - using std::ranges::views::stride; - } - using std::ranges::cartesian_product_view; namespace views { diff --git a/libcxx/test/std/ranges/range.adaptors/range.stride.view/general.pass.cpp b/libcxx/test/std/ranges/range.adaptors/range.stride.view/general.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/ranges/range.adaptors/range.stride.view/general.pass.cpp @@ -0,0 +1,33 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +// UNSUPPORTED: c++03, c++11, c++14, c++17, c++20 + +// std::views::stride_view + +#include + +#include +#include +#include + +constexpr bool static_smoke_test() { return true; } + +bool smoke_test() { + auto view(std::views::iota(1, 13)); + auto strided = std::views::stride(view, 3); + assert(*strided.begin() == 1); + assert(*(++strided.begin()) == 4); + return true; +} + +int main(int, char**) { + static_assert(static_smoke_test()); + smoke_test(); + return 0; +}