libstdc++: Implement ranges::chunk_by_view from P2443R1

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.

4 files changed, 290 insertions, 37 deletions

diff --git a/libstdc++-v3/include/bits/ranges_algo.h b/libstdc++-v3/include/bits/ranges_algo.h
index 2a11636..228e10b 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 bb56dee..85ddea6 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 44a4df8..53093a3 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 0000000..d57b127
--- /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();
+}