[gcc(refs/users/ppalka/heads/libstdcxx-constrained-algos)] Add ranges::rotate
Patrick Palka
ppalka@gcc.gnu.org
Thu Jan 23 16:25:00 GMT 2020
https://gcc.gnu.org/g:3695707dab5c87189dccd4503b7da7c72be49d37
commit 3695707dab5c87189dccd4503b7da7c72be49d37
Author: Patrick Palka <ppalka@redhat.com>
Date: Thu Jan 23 11:19:50 2020 -0500
Add ranges::rotate
Diff:
---
libstdc++-v3/include/bits/ranges_algo.h | 143 +++++++++++++++++++++
.../testsuite/25_algorithms/rotate/constrained.cc | 97 ++++++++++++++
2 files changed, 240 insertions(+)
diff --git a/libstdc++-v3/include/bits/ranges_algo.h b/libstdc++-v3/include/bits/ranges_algo.h
index 5d6eb14..617c173 100644
--- a/libstdc++-v3/include/bits/ranges_algo.h
+++ b/libstdc++-v3/include/bits/ranges_algo.h
@@ -1777,6 +1777,149 @@ namespace ranges
std::move(__result));
}
+ template<permutable _Iter, sentinel_for<_Iter> _Sent>
+ constexpr subrange<_Iter>
+ rotate(_Iter __first, _Iter __middle, _Sent __last)
+ {
+ auto __lasti = ranges::next(__first, __last);
+ if (__first == __middle)
+ return {__lasti, __lasti};
+ if (__last == __middle)
+ return {std::move(__first), std::move(__lasti)};
+
+ if constexpr (random_access_iterator<_Iter>)
+ {
+ auto __n = __lasti - __first;
+ auto __k = __middle - __first;
+
+ if (__k == __n - __k)
+ {
+ ranges::swap_ranges(__first, __middle, __middle, __middle + __k);
+ return {std::move(__middle), std::move(__lasti)};
+ }
+
+ auto __p = __first;
+ auto __ret = __first + (__lasti - __middle);
+
+ for (;;)
+ {
+ if (__k < __n - __k)
+ {
+ // TODO: is_pod is deprecated, but this condition is true to
+ // the STL implementation.
+ if constexpr (__is_pod(iter_value_t<_Iter>))
+ if (__k == 1)
+ {
+ auto __t = std::move(*__p);
+ ranges::move(__p + 1, __p + __n, __p);
+ *(__p + __n - 1) = std::move(__t);
+ return {std::move(__ret), std::move(__lasti)};
+ }
+ auto __q = __p + __k;
+ for (decltype(__n) __i = 0; __i < __n - __k; ++ __i)
+ {
+ ranges::iter_swap(__p, __q);
+ ++__p;
+ ++__q;
+ }
+ __n %= __k;
+ if (__n == 0)
+ return {std::move(__ret), std::move(__lasti)};
+ ranges::swap(__n, __k);
+ __k = __n - __k;
+ }
+ else
+ {
+ __k = __n - __k;
+ // TODO: is_pod is deprecated, but this condition is true to
+ // the STL implementation.
+ if constexpr (__is_pod(iter_value_t<_Iter>))
+ if (__k == 1)
+ {
+ auto __t = std::move(*(__p + __n - 1));
+ ranges::move_backward(__p, __p + __n - 1, __p + __n);
+ *__p = std::move(__t);
+ return {std::move(__ret), std::move(__lasti)};
+ }
+ auto __q = __p + __n;
+ __p = __q - __k;
+ for (decltype(__n) __i = 0; __i < __n - __k; ++ __i)
+ {
+ --__p;
+ --__q;
+ ranges::iter_swap(__p, __q);
+ }
+ __n %= __k;
+ if (__n == 0)
+ return {std::move(__ret), std::move(__lasti)};
+ std::swap(__n, __k);
+ }
+ }
+ }
+ else if constexpr (bidirectional_iterator<_Iter>)
+ {
+ auto __tail = __lasti;
+
+ ranges::reverse(__first, __middle);
+ ranges::reverse(__middle, __tail);
+
+ while (__first != __middle && __middle != __tail)
+ {
+ ranges::iter_swap(__first, --__tail);
+ ++__first;
+ }
+
+ if (__first == __middle)
+ {
+ ranges::reverse(__middle, __tail);
+ return {std::move(__tail), std::move(__lasti)};
+ }
+ else
+ {
+ ranges::reverse(__first, __middle);
+ return {std::move(__first), std::move(__lasti)};
+ }
+ }
+ else
+ {
+ auto __first2 = __middle;
+ do
+ {
+ ranges::iter_swap(__first, __first2);
+ ++__first;
+ ++__first2;
+ if (__first == __middle)
+ __middle = __first2;
+ } while (__first2 != __last);
+
+ auto __ret = __first;
+
+ __first2 = __middle;
+
+ while (__first2 != __last)
+ {
+ ranges::iter_swap(__first, __first2);
+ ++__first;
+ ++__first2;
+ if (__first == __middle)
+ __middle = __first2;
+ else if (__first2 == __last)
+ __first2 = __middle;
+ }
+ return {std::move(__ret), std::move(__lasti)};
+ }
+ }
+
+ template<forward_range R>
+ requires permutable<iterator_t<R>>
+ constexpr safe_subrange_t<R>
+ rotate(R&& __r, iterator_t<R> __middle)
+ {
+ return ranges::rotate(ranges::begin(__r),
+ std::move(__middle),
+ ranges::end(__r));
+ }
+
} // namespace ranges
_GLIBCXX_END_NAMESPACE_VERSION
} // namespace std
diff --git a/libstdc++-v3/testsuite/25_algorithms/rotate/constrained.cc b/libstdc++-v3/testsuite/25_algorithms/rotate/constrained.cc
new file mode 100644
index 0000000..34095e7
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/rotate/constrained.cc
@@ -0,0 +1,97 @@
+// 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::test_range;
+using __gnu_test::forward_iterator_wrapper;
+using __gnu_test::bidirectional_iterator_wrapper;
+using __gnu_test::random_access_iterator_wrapper;
+
+namespace ranges = std::ranges;
+
+struct X
+{
+ int i;
+ X (int a) : i(a) { }
+
+ friend bool
+ operator==(const X& lhs, const X& rhs)
+ {
+ return lhs.i == rhs.i;
+ }
+};
+
+static_assert(!std::is_trivial_v<X>);
+
+template<template<typename, template<typename> typename> typename container,
+ template<typename> typename wrapper,
+ typename T = int>
+void
+test01()
+{
+ for (int a = 0; a <= 7; a++)
+ {
+ T x[] = {1, 2, 3, 4, 5, 6, 7};
+ container<T, wrapper> rx(x);
+ auto i = ranges::begin(rx);
+ std::advance(i, a);
+ auto res = ranges::rotate(rx, i);
+ if (a == 0)
+ VERIFY( ranges::begin(res) == ranges::end(rx) );
+ else
+ VERIFY( ranges::begin(res)
+ == std::next(ranges::begin(rx),
+ ranges::distance(i, ranges::end(rx))) );
+ VERIFY( ranges::end(res) == ranges::end(rx) );
+ for (int k = 0; k < 7; k++)
+ VERIFY( x[k] == (k+a)%7 + 1 );
+ }
+}
+
+constexpr bool
+test02()
+{
+ int x[] = {1, 2, 3, 4};
+ const int y[] = { 2, 3, 1, 4 };
+ ranges::rotate(x, x+1, x+3);
+ return ranges::equal(x, y);
+}
+
+int
+main()
+{
+ test01<test_container, forward_iterator_wrapper>();
+ test01<test_range, forward_iterator_wrapper>();
+
+ test01<test_container, bidirectional_iterator_wrapper>();
+ test01<test_range, bidirectional_iterator_wrapper>();
+
+ test01<test_container, random_access_iterator_wrapper>();
+ test01<test_range, random_access_iterator_wrapper>();
+
+ test01<test_container, random_access_iterator_wrapper, X>();
+ test01<test_range, random_access_iterator_wrapper, X>();
+
+ static_assert(test02());
+}
More information about the Libstdc++-cvs
mailing list