libstdc++: P0769R2 Add shift to <algorithm>

This patch adds std::shift_left and std::shift_right as per P0769R2.  Alhough
these are STL-style algos, this patch places them in <bits/ranges_algo.h>
because they make use of some functions in the ranges namespace that are more
easily reachable from <bits/ranges_algo.h> than from <bits/stl_algo.h>, namely
ranges::next.  In order to place these algos in <bits/stl_algo.h>, we would need
to include <bits/range_access.h> from <bits/stl_algo.h> which would undesirably
increase the size of <bits/stl_algo.h>.

libstdc++-v3/ChangeLog:

	P0769R2 Add shift to <algorithm>
	* include/bits/ranges_algo.h (shift_left, shift_right): New.
	* testsuite/25_algorithms/shift_left/1.cc: New test.
	* testsuite/25_algorithms/shift_right/1.cc: New test.

1 files changed, 92 insertions, 0 deletions

diff --git a/libstdc++-v3/include/bits/ranges_algo.h b/libstdc++-v3/include/bits/ranges_algo.h
index 7de1072..7d7dbf0 100644
--- a/libstdc++-v3/include/bits/ranges_algo.h
+++ b/libstdc++-v3/include/bits/ranges_algo.h
@@ -3683,6 +3683,98 @@ namespace ranges
   inline constexpr __prev_permutation_fn prev_permutation{};
 
 } // namespace ranges
+
+  template<class ForwardIterator>
+    constexpr ForwardIterator
+    shift_left(ForwardIterator __first, ForwardIterator __last,
+	       typename iterator_traits<ForwardIterator>::difference_type __n)
+    {
+      __glibcxx_assert(__n >= 0);
+      if (__n == 0)
+	return __last;
+
+      auto __mid = ranges::next(__first, __n, __last);
+      if (__mid == __last)
+	return __first;
+      return std::move(std::move(__mid), std::move(__last), std::move(__first));
+    }
+
+  template<class ForwardIterator>
+    constexpr ForwardIterator
+    shift_right(ForwardIterator __first, ForwardIterator __last,
+		typename iterator_traits<ForwardIterator>::difference_type __n)
+    {
+      __glibcxx_assert(__n >= 0);
+      if (__n == 0)
+	return __first;
+
+      using _Cat = iterator_traits<ForwardIterator>::iterator_category;
+      if constexpr (derived_from<_Cat, bidirectional_iterator_tag>)
+	{
+	  auto __mid = ranges::next(__last, -__n, __first);
+	  if (__mid == __first)
+	    return __last;
+
+	  return std::move_backward(std::move(__first), std::move(__mid),
+				    std::move(__last));
+	}
+      else
+	{
+	  auto __result = ranges::next(__first, __n, __last);
+	  if (__result == __last)
+	    return __last;
+
+	  auto __dest_head = __first, __dest_tail = __result;
+	  while (__dest_head != __result)
+	    {
+	      if (__dest_tail == __last)
+		{
+		  // If we get here, then we must have
+		  //     2*n >= distance(__first, __last)
+		  // i.e. we are shifting out at least half of the range.  In
+		  // this case we can safely perform the shift with a single
+		  // move.
+		  std::move(std::move(__first), std::move(__dest_head),
+			    std::move(__result));
+		  return __result;
+		}
+	      ++__dest_head;
+	      ++__dest_tail;
+	    }
+
+	  for (;;)
+	    {
+	      // At the start of each iteration of this outer loop, the range
+	      // [__first, __result) contains those elements that after shifting
+	      // the whole range right by __n, should end up in
+	      // [__dest_head, __dest_tail) in order.
+
+	      // The below inner loop swaps the elements of [__first, __result)
+	      // and [__dest_head, __dest_tail), while simultaneously shifting
+	      // the latter range by __n.
+	      auto __cursor = __first;
+	      while (__cursor != __result)
+		{
+		  if (__dest_tail == __last)
+		    {
+		      // At this point the ranges [__first, result) and
+		      // [__dest_head, dest_tail) are disjoint, so we can safely
+		      // move the remaining elements.
+		      __dest_head = std::move(__cursor, __result,
+					      std::move(__dest_head));
+		      std::move(std::move(__first), std::move(__cursor),
+				std::move(__dest_head));
+		      return __result;
+		    }
+		  std::iter_swap(__cursor, __dest_head);
+		  ++__dest_head;
+		  ++__dest_tail;
+		  ++__cursor;
+		}
+	    }
+	}
+    }
+
 _GLIBCXX_END_NAMESPACE_VERSION
 } // namespace std
 #endif // concepts