* [PATCH] libstdc++: Implement ranges::chunk_by_view from P2443R1
@ 2022-09-14 14:19 Patrick Palka
2022-09-15 15:32 ` Jonathan Wakely
0 siblings, 1 reply; 2+ messages in thread
From: Patrick Palka @ 2022-09-14 14:19 UTC (permalink / raw)
To: gcc-patches; +Cc: libstdc++, Patrick Palka
Tested on x86_64-pc-linux-gnu, does this look OK for trunk?
libstdc++-v3/ChangeLog:
* include/bits/ranges_algo.h (__adjacent_find_fn, adjacent_find):
Move to ...
* include/bits/ranges_util.h: ... here.
* include/std/ranges (chunk_by_view): Define.
(chunk_by_view::_Iterator): Define.
(__detail::__can_chunk_by_view): Define.
(_ChunkBy, chunk_by): Define.
* testsuite/std/ranges/adaptors/chunk_by/1.cc: New test.
---
libstdc++-v3/include/bits/ranges_algo.h | 38 +---
libstdc++-v3/include/bits/ranges_util.h | 38 ++++
libstdc++-v3/include/std/ranges | 193 ++++++++++++++++++
.../std/ranges/adaptors/chunk_by/1.cc | 58 ++++++
4 files changed, 290 insertions(+), 37 deletions(-)
create mode 100644 libstdc++-v3/testsuite/std/ranges/adaptors/chunk_by/1.cc
diff --git a/libstdc++-v3/include/bits/ranges_algo.h b/libstdc++-v3/include/bits/ranges_algo.h
index 2a116361a67..228e10b62bf 100644
--- a/libstdc++-v3/include/bits/ranges_algo.h
+++ b/libstdc++-v3/include/bits/ranges_algo.h
@@ -506,43 +506,7 @@ namespace ranges
inline constexpr __find_end_fn find_end{};
- struct __adjacent_find_fn
- {
- template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
- typename _Proj = identity,
- indirect_binary_predicate<projected<_Iter, _Proj>,
- projected<_Iter, _Proj>> _Pred
- = ranges::equal_to>
- constexpr _Iter
- operator()(_Iter __first, _Sent __last,
- _Pred __pred = {}, _Proj __proj = {}) const
- {
- if (__first == __last)
- return __first;
- auto __next = __first;
- for (; ++__next != __last; __first = __next)
- {
- if (std::__invoke(__pred,
- std::__invoke(__proj, *__first),
- std::__invoke(__proj, *__next)))
- return __first;
- }
- return __next;
- }
-
- template<forward_range _Range, typename _Proj = identity,
- indirect_binary_predicate<
- projected<iterator_t<_Range>, _Proj>,
- projected<iterator_t<_Range>, _Proj>> _Pred = ranges::equal_to>
- constexpr borrowed_iterator_t<_Range>
- operator()(_Range&& __r, _Pred __pred = {}, _Proj __proj = {}) const
- {
- return (*this)(ranges::begin(__r), ranges::end(__r),
- std::move(__pred), std::move(__proj));
- }
- };
-
- inline constexpr __adjacent_find_fn adjacent_find{};
+ // adjacent_find is defined in <bits/ranges_util.h>.
struct __is_permutation_fn
{
diff --git a/libstdc++-v3/include/bits/ranges_util.h b/libstdc++-v3/include/bits/ranges_util.h
index bb56deee01b..85ddea68407 100644
--- a/libstdc++-v3/include/bits/ranges_util.h
+++ b/libstdc++-v3/include/bits/ranges_util.h
@@ -704,6 +704,44 @@ namespace ranges
inline constexpr __min_fn min{};
+ struct __adjacent_find_fn
+ {
+ template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
+ typename _Proj = identity,
+ indirect_binary_predicate<projected<_Iter, _Proj>,
+ projected<_Iter, _Proj>> _Pred
+ = ranges::equal_to>
+ constexpr _Iter
+ operator()(_Iter __first, _Sent __last,
+ _Pred __pred = {}, _Proj __proj = {}) const
+ {
+ if (__first == __last)
+ return __first;
+ auto __next = __first;
+ for (; ++__next != __last; __first = __next)
+ {
+ if (std::__invoke(__pred,
+ std::__invoke(__proj, *__first),
+ std::__invoke(__proj, *__next)))
+ return __first;
+ }
+ return __next;
+ }
+
+ template<forward_range _Range, typename _Proj = identity,
+ indirect_binary_predicate<
+ projected<iterator_t<_Range>, _Proj>,
+ projected<iterator_t<_Range>, _Proj>> _Pred = ranges::equal_to>
+ constexpr borrowed_iterator_t<_Range>
+ operator()(_Range&& __r, _Pred __pred = {}, _Proj __proj = {}) const
+ {
+ return (*this)(ranges::begin(__r), ranges::end(__r),
+ std::move(__pred), std::move(__proj));
+ }
+ };
+
+ inline constexpr __adjacent_find_fn adjacent_find{};
+
} // namespace ranges
using ranges::get;
diff --git a/libstdc++-v3/include/std/ranges b/libstdc++-v3/include/std/ranges
index 44a4df8b5d5..53093a3762f 100644
--- a/libstdc++-v3/include/std/ranges
+++ b/libstdc++-v3/include/std/ranges
@@ -6676,6 +6676,199 @@ namespace views::__adaptor
inline constexpr _Slide slide;
}
+
+ template<forward_range _Vp,
+ indirect_binary_predicate<iterator_t<_Vp>, iterator_t<_Vp>> _Pred>
+ requires view<_Vp> && is_object_v<_Pred>
+ class chunk_by_view : public view_interface<chunk_by_view<_Vp, _Pred>>
+ {
+ _Vp _M_base = _Vp();
+ __detail::__box<_Pred> _M_pred = _Pred();
+ __detail::_CachedPosition<_Vp> _M_cached_begin;
+
+ constexpr iterator_t<_Vp>
+ _M_find_next(iterator_t<_Vp> __current)
+ {
+ __glibcxx_assert(_M_pred.has_value());
+ auto __pred = [this]<typename _Tp>(_Tp&& __x, _Tp&& __y) {
+ return !bool((*_M_pred)(std::forward<_Tp>(__x), std::forward<_Tp>(__y)));
+ };
+ auto __it = ranges::adjacent_find(__current, ranges::end(_M_base), __pred);
+ return ranges::next(__it, 1, ranges::end(_M_base));
+ }
+
+ constexpr iterator_t<_Vp>
+ _M_find_prev(iterator_t<_Vp> __current) requires bidirectional_range<_Vp>
+ {
+ __glibcxx_assert(_M_pred.has_value());
+ auto __pred = [this]<typename _Tp>(_Tp&& __x, _Tp&& __y) {
+ return !bool((*_M_pred)(std::forward<_Tp>(__y), std::forward<_Tp>(__x)));
+ };
+ auto __rbegin = std::make_reverse_iterator(__current);
+ auto __rend = std::make_reverse_iterator(ranges::begin(_M_base));
+ __glibcxx_assert(__rbegin != __rend);
+ auto __it = ranges::adjacent_find(__rbegin, __rend, __pred).base();
+ return ranges::prev(__it, 1, ranges::begin(_M_base));
+ }
+
+ class _Iterator;
+
+ public:
+ chunk_by_view() requires (default_initializable<_Vp>
+ && default_initializable<_Pred>)
+ = default;
+
+ constexpr explicit
+ chunk_by_view(_Vp __base, _Pred __pred)
+ : _M_base(std::move(__base)), _M_pred(std::move(__pred))
+ { }
+
+ constexpr _Vp
+ base() const & requires copy_constructible<_Vp>
+ { return _M_base; }
+
+ constexpr _Vp
+ base() &&
+ { return std::move(_M_base); }
+
+ constexpr const _Pred&
+ pred() const
+ { return *_M_pred; }
+
+ constexpr _Iterator
+ begin()
+ {
+ __glibcxx_assert(_M_pred.has_value());
+ iterator_t<_Vp> __it;
+ if (_M_cached_begin._M_has_value())
+ __it = _M_cached_begin._M_get(_M_base);
+ else
+ {
+ __it = _M_find_next(ranges::begin(_M_base));
+ _M_cached_begin._M_set(_M_base, __it);
+ }
+ return _Iterator(*this, ranges::begin(_M_base), __it);
+ }
+
+ constexpr auto
+ end()
+ {
+ if constexpr (common_range<_Vp>)
+ return _Iterator(*this, ranges::end(_M_base), ranges::end(_M_base));
+ else
+ return default_sentinel;
+ }
+ };
+
+ template<typename _Range, typename _Pred>
+ chunk_by_view(_Range&&, _Pred) -> chunk_by_view<views::all_t<_Range>, _Pred>;
+
+ template<forward_range _Vp,
+ indirect_binary_predicate<iterator_t<_Vp>, iterator_t<_Vp>> _Pred>
+ requires view<_Vp> && is_object_v<_Pred>
+ class chunk_by_view<_Vp, _Pred>::_Iterator
+ {
+ chunk_by_view* _M_parent = nullptr;
+ iterator_t<_Vp> _M_current = iterator_t<_Vp>();
+ iterator_t<_Vp> _M_next = iterator_t<_Vp>();
+
+ constexpr
+ _Iterator(chunk_by_view& __parent, iterator_t<_Vp> __current, iterator_t<_Vp> __next)
+ : _M_parent(std::__addressof(__parent)), _M_current(__current), _M_next(__next)
+ { }
+
+ static auto
+ _S_iter_concept()
+ {
+ if constexpr (bidirectional_range<_Vp>)
+ return bidirectional_iterator_tag{};
+ else
+ return forward_iterator_tag{};
+ }
+
+ friend chunk_by_view;
+
+ public:
+ using value_type = subrange<iterator_t<_Vp>>;
+ using difference_type = range_difference_t<_Vp>;
+ using iterator_category = input_iterator_tag;
+ using iterator_concept = decltype(_S_iter_concept());
+
+ _Iterator() = default;
+
+ constexpr value_type
+ operator*() const
+ {
+ __glibcxx_assert(_M_current != _M_next);
+ return ranges::subrange(_M_current, _M_next);
+ }
+
+ constexpr _Iterator&
+ operator++()
+ {
+ __glibcxx_assert(_M_current != _M_next);
+ _M_current = _M_next;
+ _M_next = _M_parent->_M_find_next(_M_current);
+ return *this;
+ }
+
+ constexpr _Iterator
+ operator++(int)
+ {
+ auto __tmp = *this;
+ ++*this;
+ return __tmp;
+ }
+
+ constexpr _Iterator&
+ operator--() requires bidirectional_range<_Vp>
+ {
+ _M_next = _M_current;
+ _M_current = _M_parent->_M_find_prev(_M_next);
+ return *this;
+ }
+
+ constexpr _Iterator
+ operator--(int) requires bidirectional_range<_Vp>
+ {
+ auto __tmp = *this;
+ --*this;
+ return __tmp;
+ }
+
+ friend constexpr bool
+ operator==(const _Iterator& __x, const _Iterator& __y)
+ { return __x._M_current == __y._M_current; }
+
+ friend constexpr bool
+ operator==(const _Iterator& __x, default_sentinel_t)
+ { return __x._M_current == __x._M_next; }
+ };
+
+ namespace views
+ {
+ namespace __detail
+ {
+ template<typename _Range, typename _Pred>
+ concept __can_chunk_by_view
+ = requires { chunk_by_view(std::declval<_Range>(), std::declval<_Pred>()); };
+ }
+
+ struct _ChunkBy : __adaptor::_RangeAdaptor<_ChunkBy>
+ {
+ template<viewable_range _Range, typename _Pred>
+ requires __detail::__can_chunk_by_view<_Range, _Pred>
+ constexpr auto
+ operator() [[nodiscard]] (_Range&& __r, _Pred&& __pred) const
+ { return chunk_by_view(std::forward<_Range>(__r), std::forward<_Pred>(__pred)); }
+
+ using __adaptor::_RangeAdaptor<_ChunkBy>::operator();
+ static constexpr int _S_arity = 2;
+ static constexpr bool _S_has_simple_extra_args = true;
+ };
+
+ inline constexpr _ChunkBy chunk_by;
+ }
#endif // C++23
} // namespace ranges
diff --git a/libstdc++-v3/testsuite/std/ranges/adaptors/chunk_by/1.cc b/libstdc++-v3/testsuite/std/ranges/adaptors/chunk_by/1.cc
new file mode 100644
index 00000000000..d57b127fbc8
--- /dev/null
+++ b/libstdc++-v3/testsuite/std/ranges/adaptors/chunk_by/1.cc
@@ -0,0 +1,58 @@
+// { dg-options "-std=gnu++23" }
+// { dg-do run { target c++23 } }
+
+#include <ranges>
+#include <algorithm>
+#include <vector>
+#include <testsuite_hooks.h>
+#include <testsuite_iterators.h>
+
+namespace ranges = std::ranges;
+namespace views = std::views;
+
+constexpr bool
+test01()
+{
+ int x[] = {1, 2, 2, 3, 0, 4, 5, 2};
+ auto v = x | views::chunk_by(ranges::less_equal{});
+ static_assert(ranges::bidirectional_range<decltype(v)>
+ && ranges::common_range<decltype(v)>);
+ VERIFY( ranges::equal(v, (std::initializer_list<int>[]){{1, 2, 2, 3}, {0, 4, 5}, {2}},
+ ranges::equal) );
+ VERIFY( ranges::equal(v | views::reverse,
+ (std::initializer_list<int>[]){{2}, {0, 4, 5}, {1, 2, 2, 3}},
+ ranges::equal) );
+ VERIFY( ranges::equal(v | views::join, x) );
+ auto i = v.begin();
+ auto j = i;
+ j++;
+ VERIFY( i == i && i != v.end() );
+ VERIFY( j == j && j != v.end() );
+ VERIFY( j != i );
+ j--;
+ VERIFY( j == i );
+
+ return true;
+}
+
+void
+test02()
+{
+ int x[] = {1, 2, 3};
+ __gnu_test::test_forward_range<int> rx(x);
+ auto v = rx | views::chunk_by(ranges::equal_to{});
+ static_assert(!ranges::bidirectional_range<decltype(v)>
+ && !ranges::common_range<decltype(v)>);
+ VERIFY( ranges::equal(v, x | views::transform(views::single), ranges::equal) );
+ auto i = v.begin();
+ VERIFY( i != v.end() );
+ ranges::advance(i, 3);
+ VERIFY( i == v.end() );
+}
+
+int
+main()
+{
+ static_assert(test01());
+ test02();
+}
--
2.37.3.611.ge188ec3a73
^ permalink raw reply [flat|nested] 2+ messages in thread
end of thread, other threads:[~2022-09-15 15:32 UTC | newest]
Thread overview: 2+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2022-09-14 14:19 [PATCH] libstdc++: Implement ranges::chunk_by_view from P2443R1 Patrick Palka
2022-09-15 15:32 ` Jonathan Wakely
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).