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.

4 files changed, 306 insertions, 0 deletions

diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog
index eefb2a5..9996c19 100644
--- a/libstdc++-v3/ChangeLog
+++ b/libstdc++-v3/ChangeLog
@@ -1,3 +1,10 @@
+2020-02-24  Patrick Palka  <ppalka@redhat.com>
+
+	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.
+
 2020-02-24  Jonathan Wakely  <jwakely@redhat.com>
 
 	* include/bits/stream_iterator.h (istream_iterator(default_sentinel_t)):
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
diff --git a/libstdc++-v3/testsuite/25_algorithms/shift_left/1.cc b/libstdc++-v3/testsuite/25_algorithms/shift_left/1.cc
new file mode 100644
index 0000000..f7a716e
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/shift_left/1.cc
@@ -0,0 +1,104 @@
+// Copyright (C) 2020 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-options "-std=gnu++2a" }
+// { dg-do run { target c++2a } }
+
+#include <algorithm>
+#include <testsuite_hooks.h>
+#include <testsuite_iterators.h>
+
+using __gnu_test::test_container;
+using __gnu_test::forward_iterator_wrapper;
+using __gnu_test::bidirectional_iterator_wrapper;
+using __gnu_test::random_access_iterator_wrapper;
+
+struct X
+{
+  int a = -1;
+  bool moved_from = false;
+
+  X() = default;
+
+  X(int a)
+    : a(a)
+  { }
+
+  X(const X&) = delete;
+  X& operator=(const X&) = delete;
+
+  X(X&& other)
+  {
+    if (this != &other)
+    *this = std::move(other);
+  }
+
+  X&
+  operator=(X&& other)
+  {
+    a = other.a;
+    other.moved_from = true;
+    moved_from = false;
+    return *this;
+  }
+};
+
+template<int N, template<typename> typename Wrapper>
+void
+test01()
+{
+  for (int n = 0; n < N+5; n++)
+    {
+      X x[N];
+      for (int i = 0; i < N; i++)
+	x[i] = X{i};
+      test_container<X, Wrapper> cx(x);
+      auto out = std::shift_left(cx.begin(), cx.end(), n);
+      if (n < N)
+	{
+	  VERIFY( out.ptr == x+(N-n) );
+	  for (int i = 0; i < N-n; i++)
+	    {
+	      VERIFY( x[i].a == n+i );
+	      VERIFY( !x[i].moved_from );
+	    }
+	  for (int i = std::max(n, N-n); i < N; i++)
+	    VERIFY( x[i].moved_from );
+	}
+      else
+	{
+	  VERIFY( out.ptr == x );
+	  for (int i = 0; i < N; i++)
+	    {
+	      VERIFY( x[i].a == i );
+	      VERIFY( !x[i].moved_from );
+	    }
+	}
+    }
+}
+
+int
+main()
+{
+  test01<23, forward_iterator_wrapper>();
+  test01<23, bidirectional_iterator_wrapper>();
+  test01<23, random_access_iterator_wrapper>();
+
+  test01<24, forward_iterator_wrapper>();
+  test01<24, bidirectional_iterator_wrapper>();
+  test01<24, random_access_iterator_wrapper>();
+}
diff --git a/libstdc++-v3/testsuite/25_algorithms/shift_right/1.cc b/libstdc++-v3/testsuite/25_algorithms/shift_right/1.cc
new file mode 100644
index 0000000..cf736ea
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/shift_right/1.cc
@@ -0,0 +1,103 @@
+// Copyright (C) 2020 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-options "-std=gnu++2a" }
+// { dg-do run { target c++2a } }
+
+#include <algorithm>
+#include <testsuite_hooks.h>
+#include <testsuite_iterators.h>
+
+using __gnu_test::test_container;
+using __gnu_test::forward_iterator_wrapper;
+using __gnu_test::bidirectional_iterator_wrapper;
+using __gnu_test::random_access_iterator_wrapper;
+
+struct X
+{
+  int a = -1;
+  bool moved_from = false;
+
+  X() = default;
+
+  X(int a)
+    : a(a)
+  { }
+
+  X(const X&) = delete;
+  X& operator=(const X&) = delete;
+
+  X(X&& other)
+  {
+    if (this != &other)
+    *this = std::move(other);
+  }
+
+  X&
+  operator=(X&& other)
+  {
+    a = other.a;
+    other.moved_from = true;
+    moved_from = false;
+    return *this;
+  }
+};
+
+template<int N, template<typename> typename Wrapper>
+void
+test01()
+{
+  for (int n = 0; n < N+5; n++)
+    {
+      X x[N];
+      for (int i = 0; i < N; i++)
+	x[i] = X(i);
+      test_container<X, Wrapper> cx(x);
+      auto out = std::shift_right(cx.begin(), cx.end(), n);
+      if (n < N)
+	{
+	  VERIFY( out.ptr == x+n );
+	  for (int i = n; i < N; i++)
+	    VERIFY( x[i].a == i-n );
+	  for (int i = 0; i < std::min(n, N-n); i++)
+	    VERIFY( x[i].moved_from );
+	  for (int i = std::min(n, N-n); i < std::max(n, N-n); i++)
+	    VERIFY( !x[i].moved_from );
+	}
+      else
+	{
+	  VERIFY( out.ptr == x+N );
+	  for (int i = 0; i < N; i++)
+	    {
+	      VERIFY( x[i].a == i );
+	      VERIFY( !x[i].moved_from );
+	    }
+	}
+    }
+}
+
+int
+main()
+{
+  test01<23, forward_iterator_wrapper>();
+  test01<23, bidirectional_iterator_wrapper>();
+  test01<23, random_access_iterator_wrapper>();
+
+  test01<24, forward_iterator_wrapper>();
+  test01<24, bidirectional_iterator_wrapper>();
+  test01<24, random_access_iterator_wrapper>();
+}