[gcc(refs/users/ppalka/heads/libstdcxx-constrained-algos)] Add ranges::{next_permutation, prev_permutation}
Patrick Palka
ppalka@gcc.gnu.org
Sat Jan 25 22:56:00 GMT 2020
https://gcc.gnu.org/g:25766afb0f7ab3256d04a572051e8f42102549f8
commit 25766afb0f7ab3256d04a572051e8f42102549f8
Author: Patrick Palka <ppalka@redhat.com>
Date: Sat Jan 25 13:59:20 2020 -0500
Add ranges::{next_permutation,prev_permutation}
Diff:
---
libstdc++-v3/include/bits/ranges_algo.h | 117 +++++++++++++++++++++
.../25_algorithms/next_permutation/constrained.cc | 83 +++++++++++++++
.../25_algorithms/prev_permutation/constrained.cc | 84 +++++++++++++++
3 files changed, 284 insertions(+)
diff --git a/libstdc++-v3/include/bits/ranges_algo.h b/libstdc++-v3/include/bits/ranges_algo.h
index 1746484..d0d941c 100644
--- a/libstdc++-v3/include/bits/ranges_algo.h
+++ b/libstdc++-v3/include/bits/ranges_algo.h
@@ -2596,6 +2596,123 @@ namespace ranges
std::move(__comp), std::move(__proj));
}
+ template<typename _Iter>
+ struct next_permutation_result {
+ bool found;
+ _Iter in;
+ };
+
+ template<bidirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
+ typename _Comp = ranges::less, typename _Proj = identity>
+ requires sortable<_Iter, _Comp, _Proj>
+ constexpr next_permutation_result<_Iter>
+ next_permutation(_Iter __first, _Sent __last,
+ _Comp __comp = {}, _Proj __proj = {})
+ {
+ if (__first == __last)
+ return {false, std::move(__first)};
+
+ auto __i = __first;
+ ++__i;
+ if (__i == __last)
+ return {false, std::move(__i)};
+
+ auto __lasti = ranges::next(__first, __last);
+ __i = __lasti;
+ --__i;
+
+ for (;;)
+ {
+ auto __ii = __i;
+ --__i;
+ if (std::__invoke(__comp,
+ std::__invoke(__proj, *__i),
+ std::__invoke(__proj, *__ii)))
+ {
+ auto __j = __lasti;
+ while (!std::__invoke(__comp,
+ std::__invoke(__proj, *__i),
+ std::__invoke(__proj, *--__j)))
+ ;
+ ranges::iter_swap(__i, __j);
+ ranges::reverse(__ii, __last);
+ return {true, std::move(__lasti)};
+ }
+ if (__i == __first)
+ {
+ ranges::reverse(__first, __last);
+ return {false, std::move(__lasti)};
+ }
+ }
+ }
+
+ template<bidirectional_range _Range, typename _Comp = ranges::less,
+ typename _Proj = identity>
+ requires sortable<iterator_t<_Range>, _Comp, _Proj>
+ constexpr next_permutation_result<safe_iterator_t<_Range>>
+ next_permutation(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
+ {
+ return ranges::next_permutation(ranges::begin(__r), ranges::end(__r),
+ std::move(__comp), std::move(__proj));
+ }
+
+ template<typename _Iter>
+ using prev_permutation_result = next_permutation_result<_Iter>;
+
+ template<bidirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
+ typename _Comp = ranges::less, typename _Proj = identity>
+ requires sortable<_Iter, _Comp, _Proj>
+ constexpr prev_permutation_result<_Iter>
+ prev_permutation(_Iter __first, _Sent __last,
+ _Comp __comp = {}, _Proj __proj = {})
+ {
+ if (__first == __last)
+ return {false, std::move(__first)};
+
+ auto __i = __first;
+ ++__i;
+ if (__i == __last)
+ return {false, std::move(__i)};
+
+ auto __lasti = ranges::next(__first, __last);
+ __i = __lasti;
+ --__i;
+
+ for (;;)
+ {
+ auto __ii = __i;
+ --__i;
+ if (std::__invoke(__comp,
+ std::__invoke(__proj, *__ii),
+ std::__invoke(__proj, *__i)))
+ {
+ auto __j = __lasti;
+ while (!std::__invoke(__comp,
+ std::__invoke(__proj, *--__j),
+ std::__invoke(__proj, *__i)))
+ ;
+ ranges::iter_swap(__i, __j);
+ ranges::reverse(__ii, __last);
+ return {true, std::move(__lasti)};
+ }
+ if (__i == __first)
+ {
+ ranges::reverse(__first, __last);
+ return {false, std::move(__lasti)};
+ }
+ }
+ }
+
+ template<bidirectional_range _Range, typename _Comp = ranges::less,
+ typename _Proj = identity>
+ requires sortable<iterator_t<_Range>, _Comp, _Proj>
+ constexpr prev_permutation_result<safe_iterator_t<_Range>>
+ prev_permutation(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
+ {
+ return ranges::prev_permutation(ranges::begin(__r), ranges::end(__r),
+ std::move(__comp), std::move(__proj));
+ }
+
} // namespace ranges
_GLIBCXX_END_NAMESPACE_VERSION
} // namespace std
diff --git a/libstdc++-v3/testsuite/25_algorithms/next_permutation/constrained.cc b/libstdc++-v3/testsuite/25_algorithms/next_permutation/constrained.cc
new file mode 100644
index 0000000..e69b551
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/next_permutation/constrained.cc
@@ -0,0 +1,83 @@
+// 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::bidirectional_iterator_wrapper;
+
+namespace ranges = std::ranges;
+
+void
+test01()
+{
+ int x[] = {1, 2, 3, 4, 5};
+ int y[] = {1, 2, 3, 4, 5};
+
+ for (int i = 0; i <= 5; i++)
+ {
+ test_container<int, bidirectional_iterator_wrapper> cx(x, x+i);
+ test_container<int, bidirectional_iterator_wrapper> cy(y, y+i);
+ for (int j = 0; ; j++)
+ {
+ auto found1 = std::next_permutation(cx.begin(), cx.end());
+ auto [found2,last] = ranges::next_permutation(cy.begin(), cy.end());
+ VERIFY( found1 == found2 );
+ VERIFY( ranges::equal(cx, cy) );
+ if (!found2)
+ break;
+ }
+ }
+}
+
+void
+test02()
+{
+ int x[] = {5, 4, 3, 2, 1};
+ test_range<int, bidirectional_iterator_wrapper> rx(x);
+ auto [found,last] = ranges::next_permutation(rx, ranges::greater{});
+ VERIFY( found && last == rx.end() );
+ VERIFY( last == rx.end() );
+ VERIFY( ranges::equal(rx, (int[]){5,4,3,1,2}) );
+ ranges::next_permutation(rx, {}, [] (int a) { return -a; });
+ VERIFY( ranges::equal(rx, (int[]){5,4,2,3,1}) );
+
+ VERIFY( !ranges::next_permutation(x, x).found );
+ VERIFY( !ranges::next_permutation(x, x+1).found );
+}
+
+constexpr bool
+test03()
+{
+ int x[] = {1,2,3};
+ ranges::next_permutation(x);
+ return ranges::equal(x, (int[]){1,3,2});
+}
+
+int
+main()
+{
+ test01();
+ test02();
+ static_assert(test03());
+}
diff --git a/libstdc++-v3/testsuite/25_algorithms/prev_permutation/constrained.cc b/libstdc++-v3/testsuite/25_algorithms/prev_permutation/constrained.cc
new file mode 100644
index 0000000..25bbad9
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/prev_permutation/constrained.cc
@@ -0,0 +1,84 @@
+// 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::bidirectional_iterator_wrapper;
+
+namespace ranges = std::ranges;
+
+void
+test01()
+{
+ int x[] = {5, 4, 3, 2, 1};
+ int y[] = {5, 4, 3, 2, 1};
+
+ for (int i = 0; i <= 5; i++)
+ {
+ test_container<int, bidirectional_iterator_wrapper> cx(x, x+i);
+ test_container<int, bidirectional_iterator_wrapper> cy(y, y+i);
+ for (int j = 0; ; j++)
+ {
+ auto found1 = std::prev_permutation(cx.begin(), cx.end());
+ auto [found2,last] = ranges::prev_permutation(cy.begin(), cy.end());
+ VERIFY( found1 == found2 );
+ VERIFY( ranges::equal(cx, cy) );
+ if (!found2)
+ break;
+ }
+ }
+}
+
+void
+test02()
+{
+ int x[] = {1, 2, 3, 4, 5};
+ test_range<int, bidirectional_iterator_wrapper> rx(x);
+ auto [found,last] = ranges::prev_permutation(rx, ranges::greater{});
+ VERIFY( found && last == rx.end() );
+ VERIFY( last == rx.end() );
+ VERIFY( ranges::equal(rx, (int[]){1,2,3,5,4}) );
+ ranges::prev_permutation(rx, {}, [] (int a) { return -a; });
+ VERIFY( ranges::equal(rx, (int[]){1,2,4,3,5}) );
+
+ VERIFY( !ranges::prev_permutation(x, x).found );
+ VERIFY( !ranges::prev_permutation(x, x+1).found );
+}
+
+constexpr bool
+test03()
+{
+ int x[] = {3,2,1};
+ ranges::prev_permutation(x);
+ return ranges::equal(x, (int[]){3,1,2});
+}
+
+int
+main()
+{
+ test01();
+ test02();
+ static_assert(test03());
+}
+
More information about the Libstdc++-cvs
mailing list