[PATCH] libstdc++: P0769R2 Add shift to <algorithm>

[PATCH] libstdc++: P0769R2 Add shift to <algorithm>

[Patrick Palka]

This patch adds std::shift_left and std::shift_right.  Alhough these are
STL-style algos, they are nonetheless placed 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 and ranges::swap_ranges.

This implementation of std::shift_right for non-bidirectional iterators deviates
from the reference implementation a bit.  The main difference is that this
implementation is significantly simpler, and yet saves around n/2 additional
iterator increments and n/2 iter_moves at the cost of around n/2 additional
iter_swaps (where n is the shift amount).

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.
---
 libstdc++-v3/include/bits/ranges_algo.h       | 48 +++++++++++++
 .../testsuite/25_algorithms/shift_left/1.cc   | 67 +++++++++++++++++++
 .../testsuite/25_algorithms/shift_right/1.cc  | 67 +++++++++++++++++++
 3 files changed, 182 insertions(+)
 create mode 100644 libstdc++-v3/testsuite/25_algorithms/shift_left/1.cc
 create mode 100644 libstdc++-v3/testsuite/25_algorithms/shift_right/1.cc

diff --git a/libstdc++-v3/include/bits/ranges_algo.h b/libstdc++-v3/include/bits/ranges_algo.h
index 7de1072abf0..c36afc6e19b 100644
--- a/libstdc++-v3/include/bits/ranges_algo.h
+++ b/libstdc++-v3/include/bits/ranges_algo.h
@@ -3683,6 +3683,54 @@ 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 = __result;
+	  do
+	    __dest = ranges::swap_ranges(__first, __result,
+					 std::move(__dest), __last).in2;
+	  while (__dest != __last);
+	  return __result;
+	}
+    }
+
 _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 00000000000..9bdb843adbc
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/shift_left/1.cc
@@ -0,0 +1,67 @@
+// 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;
+
+template<int K, template<typename> typename Wrapper>
+void
+test01()
+{
+  static_assert(K == 10 || K == 11);
+  for (int i = 0; i < 15; i++)
+    {
+      int x[K];
+      for (int t = 0; t < K; t++)
+	x[t] = t;
+      test_container<int, Wrapper> cx(x);
+      auto out = std::shift_left(cx.begin(), cx.end(), i);
+      if (i < K)
+	{
+	  VERIFY( out.ptr == x+(K-i) );
+	  for (int j = i; j < K-i; j++)
+	    VERIFY( x[j] == i+j );
+	}
+      else
+	{
+	  VERIFY( out.ptr == x );
+	  for (int j = 0; j < K; j++)
+	    VERIFY( x[j] == j );
+	}
+    }
+}
+
+int
+main()
+{
+  test01<10, forward_iterator_wrapper>();
+  test01<10, bidirectional_iterator_wrapper>();
+  test01<10, random_access_iterator_wrapper>();
+
+  test01<11, forward_iterator_wrapper>();
+  test01<11, bidirectional_iterator_wrapper>();
+  test01<11, 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 00000000000..3ce05ed287b
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/shift_right/1.cc
@@ -0,0 +1,67 @@
+// 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;
+
+template<int K, template<typename> typename Wrapper>
+void
+test01()
+{
+  static_assert(K == 10 || K == 11);
+  for (int i = 0; i < 15; i++)
+    {
+      int x[K];
+      for (int t = 0; t < K; t++)
+	x[t] = t;
+      test_container<int, Wrapper> cx(x);
+      auto out = std::shift_right(cx.begin(), cx.end(), i);
+      if (i < K)
+	{
+	  VERIFY( out.ptr == x+i );
+	  for (int j = i; j < K; j++)
+	    VERIFY( x[j] == j-i );
+	}
+      else
+	{
+	  VERIFY( out.ptr == x+K );
+	  for (int j = 0; j < K; j++)
+	    VERIFY( x[j] == j );
+	}
+    }
+}
+
+int
+main()
+{
+  test01<10, forward_iterator_wrapper>();
+  test01<10, bidirectional_iterator_wrapper>();
+  test01<10, random_access_iterator_wrapper>();
+
+  test01<11, forward_iterator_wrapper>();
+  test01<11, bidirectional_iterator_wrapper>();
+  test01<11, random_access_iterator_wrapper>();
+}
-- 
2.25.1.291.ge68e29171c

Re: [PATCH] libstdc++: P0769R2 Add shift to <algorithm>

[Patrick Palka]

On Fri, 21 Feb 2020, Patrick Palka wrote:

> This patch adds std::shift_left and std::shift_right.  Alhough these are
> STL-style algos, they are nonetheless placed 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 and ranges::swap_ranges.
> 
> This implementation of std::shift_right for non-bidirectional iterators deviates
> from the reference implementation a bit.  The main difference is that this
> implementation is significantly simpler, and yet saves around n/2 additional
> iterator increments and n/2 iter_moves at the cost of around n/2 additional
> iter_swaps (where n is the shift amount).

On second thought, this simplification of shift_right is a not a good
idea because the objects that were shifted and that are no longer a part
of the new range do not end up in a moved-from state at the end of the
algorithm.  Here is a version of the patch that instead adds something
akin to the reference implementation and improves the tests to verify
this moved-from property of both algorithms.

-- >8 --

Subject: [PATCH] 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.
---
 libstdc++-v3/include/bits/ranges_algo.h       |  92 ++++++++++++++++
 .../testsuite/25_algorithms/shift_left/1.cc   | 104 ++++++++++++++++++
 .../testsuite/25_algorithms/shift_right/1.cc  | 103 +++++++++++++++++
 3 files changed, 299 insertions(+)
 create mode 100644 libstdc++-v3/testsuite/25_algorithms/shift_left/1.cc
 create mode 100644 libstdc++-v3/testsuite/25_algorithms/shift_right/1.cc

diff --git a/libstdc++-v3/include/bits/ranges_algo.h b/libstdc++-v3/include/bits/ranges_algo.h
index 7de1072abf0..7d7dbf04103 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 00000000000..f7a716e0563
--- /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 00000000000..cf736ea91b1
--- /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>();
+}
-- 
2.25.1.291.ge68e29171c

Re: [PATCH] libstdc++: P0769R2 Add shift to <algorithm>

[Jonathan Wakely]

On 21/02/20 16:12 -0500, Patrick Palka wrote:
>On Fri, 21 Feb 2020, Patrick Palka wrote:
>
>> This patch adds std::shift_left and std::shift_right.  Alhough these are
>> STL-style algos, they are nonetheless placed 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 and ranges::swap_ranges.
>>
>> This implementation of std::shift_right for non-bidirectional iterators deviates
>> from the reference implementation a bit.  The main difference is that this
>> implementation is significantly simpler, and yet saves around n/2 additional
>> iterator increments and n/2 iter_moves at the cost of around n/2 additional
>> iter_swaps (where n is the shift amount).
>
>On second thought, this simplification of shift_right is a not a good
>idea because the objects that were shifted and that are no longer a part
>of the new range do not end up in a moved-from state at the end of the
>algorithm.  Here is a version of the patch that instead adds something
>akin to the reference implementation and improves the tests to verify
>this moved-from property of both algorithms.
>
>-- >8 --
>
>Subject: [PATCH] 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.
>---
> libstdc++-v3/include/bits/ranges_algo.h       |  92 ++++++++++++++++
> .../testsuite/25_algorithms/shift_left/1.cc   | 104 ++++++++++++++++++
> .../testsuite/25_algorithms/shift_right/1.cc  | 103 +++++++++++++++++
> 3 files changed, 299 insertions(+)
> create mode 100644 libstdc++-v3/testsuite/25_algorithms/shift_left/1.cc
> create mode 100644 libstdc++-v3/testsuite/25_algorithms/shift_right/1.cc
>
>diff --git a/libstdc++-v3/include/bits/ranges_algo.h b/libstdc++-v3/include/bits/ranges_algo.h
>index 7de1072abf0..7d7dbf04103 100644
>--- a/libstdc++-v3/include/bits/ranges_algo.h
>+++ b/libstdc++-v3/include/bits/ranges_algo.h

These new algos should go in <bits/stl_algo.h> because they're not in
namespace ranges.

>@@ -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 I'm reading the current draft correctly, n < 0 is allowed (and does
nothing) so we shouldn't assert here.


>+      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);

Same here.

Re: [PATCH] libstdc++: P0769R2 Add shift to <algorithm>

[Patrick Palka]

On Mon, 24 Feb 2020, Jonathan Wakely wrote:

> On 21/02/20 16:12 -0500, Patrick Palka wrote:
> > On Fri, 21 Feb 2020, Patrick Palka wrote:
> > 
> > > This patch adds std::shift_left and std::shift_right.  Alhough these are
> > > STL-style algos, they are nonetheless placed 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 and ranges::swap_ranges.
> > > 
> > > This implementation of std::shift_right for non-bidirectional iterators
> > > deviates
> > > from the reference implementation a bit.  The main difference is that this
> > > implementation is significantly simpler, and yet saves around n/2
> > > additional
> > > iterator increments and n/2 iter_moves at the cost of around n/2
> > > additional
> > > iter_swaps (where n is the shift amount).
> > 
> > On second thought, this simplification of shift_right is a not a good
> > idea because the objects that were shifted and that are no longer a part
> > of the new range do not end up in a moved-from state at the end of the
> > algorithm.  Here is a version of the patch that instead adds something
> > akin to the reference implementation and improves the tests to verify
> > this moved-from property of both algorithms.
> > 
> > -- >8 --
> > 
> > Subject: [PATCH] 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.
> > ---
> > libstdc++-v3/include/bits/ranges_algo.h       |  92 ++++++++++++++++
> > .../testsuite/25_algorithms/shift_left/1.cc   | 104 ++++++++++++++++++
> > .../testsuite/25_algorithms/shift_right/1.cc  | 103 +++++++++++++++++
> > 3 files changed, 299 insertions(+)
> > create mode 100644 libstdc++-v3/testsuite/25_algorithms/shift_left/1.cc
> > create mode 100644 libstdc++-v3/testsuite/25_algorithms/shift_right/1.cc
> > 
> > diff --git a/libstdc++-v3/include/bits/ranges_algo.h
> > b/libstdc++-v3/include/bits/ranges_algo.h
> > index 7de1072abf0..7d7dbf04103 100644
> > --- a/libstdc++-v3/include/bits/ranges_algo.h
> > +++ b/libstdc++-v3/include/bits/ranges_algo.h
> 
> These new algos should go in <bits/stl_algo.h> because they're not in
> namespace ranges.

Since their implementation uses ranges::next(__it, __n, __last), putting
them in <bits/stl_algo.h> means we would need to include
<bits/range_access.h> from <bits/stl_algo.h>, or reimplement the
ranges::next() routine in <bits/stl_algo.h> (and its random access
iterator optimization) it seems.

> 
> > @@ -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 I'm reading the current draft correctly, n < 0 is allowed (and does
> nothing) so we shouldn't assert here.

From what I can tell, this is changed by P1243R4 (Rangify new
algorithms) which adds the precondition n >= 0 to these routines.

> 
> 
> > +      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);
> 
> Same here.

Re: [PATCH] libstdc++: P0769R2 Add shift to <algorithm>

[Daniel Krügler]

Am Mo., 24. Feb. 2020 um 15:12 Uhr schrieb Patrick Palka <ppalka@redhat.com>:
>
> On Mon, 24 Feb 2020, Jonathan Wakely wrote:
>
[...]
> > > @@ -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 I'm reading the current draft correctly, n < 0 is allowed (and does
> > nothing) so we shouldn't assert here.
>
> From what I can tell, this is changed by P1243R4 (Rangify new
> algorithms) which adds the precondition n >= 0 to these routines.

Yes, that's correct. This part of the wording applied the accepted
changes of p1233r1.

- Daniel

Re: [PATCH] libstdc++: P0769R2 Add shift to <algorithm>

[Jonathan Wakely]

On 24/02/20 09:12 -0500, Patrick Palka wrote:
>On Mon, 24 Feb 2020, Jonathan Wakely wrote:
>
>> On 21/02/20 16:12 -0500, Patrick Palka wrote:
>> > On Fri, 21 Feb 2020, Patrick Palka wrote:
>> >
>> > > This patch adds std::shift_left and std::shift_right.  Alhough these are
>> > > STL-style algos, they are nonetheless placed 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 and ranges::swap_ranges.
>> > >
>> > > This implementation of std::shift_right for non-bidirectional iterators
>> > > deviates
>> > > from the reference implementation a bit.  The main difference is that this
>> > > implementation is significantly simpler, and yet saves around n/2
>> > > additional
>> > > iterator increments and n/2 iter_moves at the cost of around n/2
>> > > additional
>> > > iter_swaps (where n is the shift amount).
>> >
>> > On second thought, this simplification of shift_right is a not a good
>> > idea because the objects that were shifted and that are no longer a part
>> > of the new range do not end up in a moved-from state at the end of the
>> > algorithm.  Here is a version of the patch that instead adds something
>> > akin to the reference implementation and improves the tests to verify
>> > this moved-from property of both algorithms.
>> >
>> > -- >8 --
>> >
>> > Subject: [PATCH] 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.
>> > ---
>> > libstdc++-v3/include/bits/ranges_algo.h       |  92 ++++++++++++++++
>> > .../testsuite/25_algorithms/shift_left/1.cc   | 104 ++++++++++++++++++
>> > .../testsuite/25_algorithms/shift_right/1.cc  | 103 +++++++++++++++++
>> > 3 files changed, 299 insertions(+)
>> > create mode 100644 libstdc++-v3/testsuite/25_algorithms/shift_left/1.cc
>> > create mode 100644 libstdc++-v3/testsuite/25_algorithms/shift_right/1.cc
>> >
>> > diff --git a/libstdc++-v3/include/bits/ranges_algo.h
>> > b/libstdc++-v3/include/bits/ranges_algo.h
>> > index 7de1072abf0..7d7dbf04103 100644
>> > --- a/libstdc++-v3/include/bits/ranges_algo.h
>> > +++ b/libstdc++-v3/include/bits/ranges_algo.h
>>
>> These new algos should go in <bits/stl_algo.h> because they're not in
>> namespace ranges.
>
>Since their implementation uses ranges::next(__it, __n, __last), putting
>them in <bits/stl_algo.h> means we would need to include
><bits/range_access.h> from <bits/stl_algo.h>, or reimplement the
>ranges::next() routine in <bits/stl_algo.h> (and its random access
>iterator optimization) it seems.

Ah right.

>> > @@ -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 I'm reading the current draft correctly, n < 0 is allowed (and does
>> nothing) so we shouldn't assert here.
>
From what I can tell, this is changed by P1243R4 (Rangify new
>algorithms) which adds the precondition n >= 0 to these routines.

Thanks, I forgot that paper still changed shuft_left and shift_right
even thogh it didn't add ranges::shift_left and ranges::shift_right.

OK for master then, thanks.

Re: [PATCH] libstdc++: P0769R2 Add shift to <algorithm>

[Stephan Bergmann]

On 21/02/2020 20:29, Patrick Palka wrote:
> diff --git a/libstdc++-v3/include/bits/ranges_algo.h b/libstdc++-v3/include/bits/ranges_algo.h
> index 7de1072abf0..c36afc6e19b 100644
> --- a/libstdc++-v3/include/bits/ranges_algo.h
> +++ b/libstdc++-v3/include/bits/ranges_algo.h
> @@ -3683,6 +3683,54 @@ 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;

^ FYI, the above line causes recent Clang 10 trunk with -std=c++20 to 
fail due to a "missing" typedef

> +      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 = __result;
> +	  do
> +	    __dest = ranges::swap_ranges(__first, __result,
> +					 std::move(__dest), __last).in2;
> +	  while (__dest != __last);
> +	  return __result;
> +	}
> +    }
> +
>   _GLIBCXX_END_NAMESPACE_VERSION
>   } // namespace std
>   #endif // concepts

Re: [PATCH] libstdc++: P0769R2 Add shift to <algorithm>

[Jonathan Wakely]

[-- Attachment #1: Type: text/plain, Size: 1548 bytes --]

On 02/03/20 10:03 +0100, Stephan Bergmann wrote:
>On 21/02/2020 20:29, Patrick Palka wrote:
>>diff --git a/libstdc++-v3/include/bits/ranges_algo.h b/libstdc++-v3/include/bits/ranges_algo.h
>>index 7de1072abf0..c36afc6e19b 100644
>>--- a/libstdc++-v3/include/bits/ranges_algo.h
>>+++ b/libstdc++-v3/include/bits/ranges_algo.h
>>@@ -3683,6 +3683,54 @@ 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;
>
>^ FYI, the above line causes recent Clang 10 trunk with -std=c++20 to 
>fail due to a "missing" typedef

Thanks, fixed by this patch, committed to master now.

[-- Attachment #2: patch.txt --]
[-- Type: text/x-patch, Size: 909 bytes --]

commit 5fad000324d0bcc87283dc339423bfad6fa42c74
Author: Jonathan Wakely <jwakely@redhat.com>
Date:   Mon Mar 2 12:18:45 2020 +0000

    libstdc++: Add 'typename' to fix compilation with Clang
    
            * include/bits/ranges_algo.h (shift_right): Add 'typename' to
            dependent type.

diff --git a/libstdc++-v3/include/bits/ranges_algo.h b/libstdc++-v3/include/bits/ranges_algo.h
index 8fa4a8a9161..a34f75f53d8 100644
--- a/libstdc++-v3/include/bits/ranges_algo.h
+++ b/libstdc++-v3/include/bits/ranges_algo.h
@@ -3710,7 +3710,7 @@ namespace ranges
       if (__n == 0)
 	return __first;
 
-      using _Cat = iterator_traits<ForwardIterator>::iterator_category;
+      using _Cat = typename iterator_traits<ForwardIterator>::iterator_category;
       if constexpr (derived_from<_Cat, bidirectional_iterator_tag>)
 	{
 	  auto __mid = ranges::next(__last, -__n, __first);