diff --git a/libcxx/docs/Status/RangesAlgorithms.csv b/libcxx/docs/Status/RangesAlgorithms.csv
--- a/libcxx/docs/Status/RangesAlgorithms.csv
+++ b/libcxx/docs/Status/RangesAlgorithms.csv
@@ -82,8 +82,8 @@
Permutation,push_heap,Konstantin Varlamov,`D128115 <https://llvm.org/D128115>`_,✅
Permutation,pop_heap,Konstantin Varlamov,`D128115 <https://llvm.org/D128115>`_,✅
Permutation,sort_heap,Konstantin Varlamov,`D128115 <https://llvm.org/D128115>`_,✅
-Permutation,prev_permutation,Not assigned,n/a,Not started
-Permutation,next_permutation,Not assigned,n/a,Not started
+Permutation,Nikolas Klauser,`D129859 <https://llvm.org/D129859>`_,✅
+Permutation,Nikolas Klauser,`D129859 <https://llvm.org/D129859>`_,✅
Uninitialised memory,uninitialized_copy,Konstantin Varlamov,`D116023 <https://llvm.org/D116023>`_,✅
Uninitialised memory,uninitialized_copy_n,Konstantin Varlamov,`D116023 <https://llvm.org/D116023>`_,✅
Uninitialised memory,uninitialized_fill,Konstantin Varlamov,`D115626 <https://llvm.org/D115626>`_,✅
diff --git a/libcxx/include/CMakeLists.txt b/libcxx/include/CMakeLists.txt
--- a/libcxx/include/CMakeLists.txt
+++ b/libcxx/include/CMakeLists.txt
@@ -111,6 +111,7 @@
__algorithm/ranges_mismatch.h
__algorithm/ranges_move.h
__algorithm/ranges_move_backward.h
+ __algorithm/ranges_next_permutation.h
__algorithm/ranges_none_of.h
__algorithm/ranges_nth_element.h
__algorithm/ranges_partial_sort_copy.h
@@ -118,6 +119,7 @@
__algorithm/ranges_partition_copy.h
__algorithm/ranges_partition_point.h
__algorithm/ranges_pop_heap.h
+ __algorithm/ranges_prev_permutation.h
__algorithm/ranges_push_heap.h
__algorithm/ranges_remove.h
__algorithm/ranges_remove_copy.h
diff --git a/libcxx/include/__algorithm/ranges_next_permutation.h b/libcxx/include/__algorithm/ranges_next_permutation.h
new file mode 100644
--- /dev/null
+++ b/libcxx/include/__algorithm/ranges_next_permutation.h
@@ -0,0 +1,60 @@
+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef _LIBCPP___ALGORITHM_RANGES_NEXT_PERMUTATION_H
+#define _LIBCPP___ALGORITHM_RANGES_NEXT_PERMUTATION_H
+
+#include <__algorithm/in_found_result.h>
+#include <__algorithm/ranges_prev_permutation.h>
+#include <__config>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+# pragma GCC system_header
+#endif
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
+
+namespace ranges {
+
+template <class _InIter>
+using next_permutation_result = in_found_result<_InIter>;
+
+namespace __next_permutation {
+
+struct __fn {
+ template <bidirectional_iterator _Iter, sentinel_for<_Iter> _Sent, class _Comp = ranges::less, class _Proj = identity>
+ requires sortable<_Iter, _Comp, _Proj>
+ _LIBCPP_HIDE_FROM_ABI constexpr next_permutation_result<_Iter>
+ operator()(_Iter __first, _Sent __last, _Comp __comp = {}, _Proj __proj = {}) const {
+ auto __comp_reverse_args = [&](auto&& __lhs, auto&& __rhs) { return std::invoke(__comp, __rhs, __lhs); };
+ return ranges::__prev_permutation_impl(__first, __last, __comp_reverse_args, __proj);
+ }
+
+ template <bidirectional_range _Range, class _Comp = ranges::less, class _Proj = identity>
+ requires sortable<iterator_t<_Range>, _Comp, _Proj>
+ _LIBCPP_HIDE_FROM_ABI constexpr next_permutation_result<borrowed_iterator_t<_Range>>
+ operator()(_Range&& __range, _Comp __comp = {}, _Proj __proj = {}) const {
+ auto __comp_reverse_args = [&](auto&& __lhs, auto&& __rhs) { return std::invoke(__comp, __rhs, __lhs); };
+ return ranges::__prev_permutation_impl(ranges::begin(__range), ranges::end(__range), __comp_reverse_args, __proj);
+ }
+};
+
+} // namespace __next_permutation
+
+inline namespace __cpo {
+constexpr inline auto next_permutation = __next_permutation::__fn{};
+} // namespace __cpo
+} // namespace ranges
+
+#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif // _LIBCPP___ALGORITHM_RANGES_NEXT_PERMUTATION_H
diff --git a/libcxx/include/__algorithm/ranges_prev_permutation.h b/libcxx/include/__algorithm/ranges_prev_permutation.h
new file mode 100644
--- /dev/null
+++ b/libcxx/include/__algorithm/ranges_prev_permutation.h
@@ -0,0 +1,96 @@
+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef _LIBCPP___ALGORITHM_RANGES_PREV_PERMUTATION_H
+#define _LIBCPP___ALGORITHM_RANGES_PREV_PERMUTATION_H
+
+#include <__algorithm/in_found_result.h>
+#include <__algorithm/ranges_reverse.h>
+#include <__config>
+#include <__functional/identity.h>
+#include <__functional/ranges_operations.h>
+#include <__iterator/concepts.h>
+#include <__iterator/iter_swap.h>
+#include <__iterator/next.h>
+#include <__iterator/sortable.h>
+#include <__ranges/access.h>
+#include <__ranges/concepts.h>
+#include <__ranges/dangling.h>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+# pragma GCC system_header
+#endif
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
+
+namespace ranges {
+
+template <class _InIter>
+using prev_permutation_result = in_found_result<_InIter>;
+
+template <class _Iter, class _Sent, class _Comp, class _Proj>
+_LIBCPP_HIDE_FROM_ABI constexpr prev_permutation_result<_Iter>
+__prev_permutation_impl(_Iter __first, _Sent __sent, _Comp& __comp, _Proj& __proj) {
+ auto __last = ranges::next(__first, __sent);
+ auto __i = __last;
+ if (__first == __last || __first == --__i)
+ return {std::move(__last), false};
+
+ while (true) {
+ auto __ip1 = __i;
+ --__i;
+
+ if (std::invoke(__comp, std::invoke(__proj, *__ip1), std::invoke(__proj, *__i))) {
+ auto __j = __last;
+ do {
+ --__j;
+ } while (!std::invoke(__comp, std::invoke(__proj, *__j), std::invoke(__proj, *__i)));
+
+ ranges::iter_swap(__i, __j);
+ ranges::reverse(__ip1, __last);
+ return {std::move(__last), true};
+ }
+
+ if (__i == __first) {
+ ranges::reverse(__first, __last);
+ return {std::move(__last), false};
+ }
+ }
+}
+
+namespace __prev_permutation {
+
+struct __fn {
+ template <bidirectional_iterator _Iter, sentinel_for<_Iter> _Sent, class _Comp = ranges::less, class _Proj = identity>
+ requires sortable<_Iter, _Comp, _Proj>
+ _LIBCPP_HIDE_FROM_ABI constexpr prev_permutation_result<_Iter>
+ operator()(_Iter __first, _Sent __last, _Comp __comp = {}, _Proj __proj = {}) const {
+ return ranges::__prev_permutation_impl(std::move(__first), std::move(__last), __comp, __proj);
+ }
+
+ template <bidirectional_range _Range, class _Comp = ranges::less, class _Proj = identity>
+ requires sortable<iterator_t<_Range>, _Comp, _Proj>
+ _LIBCPP_HIDE_FROM_ABI constexpr prev_permutation_result<borrowed_iterator_t<_Range>>
+ operator()(_Range&& __range, _Comp __comp = {}, _Proj __proj = {}) const {
+ return ranges::__prev_permutation_impl(ranges::begin(__range), ranges::end(__range), __comp, __proj);
+ }
+};
+} // namespace __prev_permutation
+
+inline namespace __cpo {
+constexpr inline auto prev_permutation = __prev_permutation::__fn{};
+} // namespace __cpo
+} // namespace ranges
+
+#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif // _LIBCPP___ALGORITHM_RANGES_PREV_PERMUTATION_H
diff --git a/libcxx/include/algorithm b/libcxx/include/algorithm
--- a/libcxx/include/algorithm
+++ b/libcxx/include/algorithm
@@ -703,7 +703,7 @@
set_symmetric_difference(I1 first1, S1 last1, I2 first2, S2 last2, O result,
Comp comp = {}, Proj1 proj1 = {},
Proj2 proj2 = {}); // since C++20
-
+
template<input_range R1, input_range R2, weakly_incrementable O,
class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity>
requires mergeable<iterator_t<R1>, iterator_t<R2>, O, Comp, Proj1, Proj2>
@@ -711,7 +711,7 @@
borrowed_iterator_t<R2>, O>
set_symmetric_difference(R1&& r1, R2&& r2, O result, Comp comp = {},
Proj1 proj1 = {}, Proj2 proj2 = {}); // since C++20
-
+
template<class I1, class I2, class O>
using set_union_result = in_in_out_result<I1, I2, O>; // since C++20
@@ -729,6 +729,34 @@
constexpr set_union_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>, O>
set_union(R1&& r1, R2&& r2, O result, Comp comp = {},
Proj1 proj1 = {}, Proj2 proj2 = {}); // since C++20
+
+ template<class I>
+ using prev_permutation_result = in_found_result<I>; // since C++20
+
+ template<bidirectional_iterator I, sentinel_for<I> S, class Comp = ranges::less,
+ class Proj = identity>
+ requires sortable<I, Comp, Proj>
+ constexpr ranges::prev_permutation_result<I>
+ ranges::prev_permutation(I first, S last, Comp comp = {}, Proj proj = {}); // since C++20
+
+ template<bidirectional_range R, class Comp = ranges::less,
+ class Proj = identity>
+ requires sortable<iterator_t<R>, Comp, Proj>
+ constexpr ranges::prev_permutation_result<borrowed_iterator_t<R>>
+ ranges::prev_permutation(R&& r, Comp comp = {}, Proj proj = {}); // since C++20
+
+ template<bidirectional_iterator I, sentinel_for<I> S, class Comp = ranges::less,
+ class Proj = identity>
+ requires sortable<I, Comp, Proj>
+ constexpr ranges::next_permutation_result<I>
+ ranges::next_permutation(I first, S last, Comp comp = {}, Proj proj = {}); // since C++20
+
+ template<bidirectional_range R, class Comp = ranges::less,
+ class Proj = identity>
+ requires sortable<iterator_t<R>, Comp, Proj>
+ constexpr ranges::next_permutation_result<borrowed_iterator_t<R>>
+ ranges::next_permutation(R&& r, Comp comp = {}, Proj proj = {}); // since C++20
+
}
constexpr bool // constexpr in C++20
@@ -1494,9 +1522,11 @@
#include <__algorithm/ranges_mismatch.h>
#include <__algorithm/ranges_move.h>
#include <__algorithm/ranges_move_backward.h>
+#include <__algorithm/ranges_next_permutation.h>
#include <__algorithm/ranges_none_of.h>
#include <__algorithm/ranges_nth_element.h>
#include <__algorithm/ranges_pop_heap.h>
+#include <__algorithm/ranges_prev_permutation.h>
#include <__algorithm/ranges_push_heap.h>
#include <__algorithm/ranges_remove.h>
#include <__algorithm/ranges_remove_if.h>
diff --git a/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_comparators.pass.cpp b/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_comparators.pass.cpp
--- a/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_comparators.pass.cpp
+++ b/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_comparators.pass.cpp
@@ -165,8 +165,8 @@
(void)std::ranges::minmax_element(a, Less(&copies)); assert(copies == 0);
(void)std::ranges::mismatch(first, last, first2, last2, Equal(&copies)); assert(copies == 0);
(void)std::ranges::mismatch(a, b, Equal(&copies)); assert(copies == 0);
- //(void)std::ranges::next_permutation(first, last, Less(&copies)); assert(copies == 0);
- //(void)std::ranges::next_permutation(a, Less(&copies)); assert(copies == 0);
+ (void)std::ranges::next_permutation(first, last, Less(&copies)); assert(copies == 0);
+ (void)std::ranges::next_permutation(a, Less(&copies)); assert(copies == 0);
(void)std::ranges::none_of(first, last, UnaryTrue(&copies)); assert(copies == 0);
(void)std::ranges::none_of(a, UnaryTrue(&copies)); assert(copies == 0);
(void)std::ranges::nth_element(first, mid, last, Less(&copies)); assert(copies == 0);
@@ -183,8 +183,8 @@
//(void)std::ranges::partition_point(a, UnaryTrue(&copies)); assert(copies == 0);
(void)std::ranges::pop_heap(first, last, Less(&copies)); assert(copies == 0);
(void)std::ranges::pop_heap(a, Less(&copies)); assert(copies == 0);
- //(void)std::ranges::prev_permutation(first, last, Less(&copies)); assert(copies == 0);
- //(void)std::ranges::prev_permutation(a, Less(&copies)); assert(copies == 0);
+ (void)std::ranges::prev_permutation(first, last, Less(&copies)); assert(copies == 0);
+ (void)std::ranges::prev_permutation(a, Less(&copies)); assert(copies == 0);
(void)std::ranges::push_heap(first, last, Less(&copies)); assert(copies == 0);
(void)std::ranges::push_heap(a, Less(&copies)); assert(copies == 0);
//(void)std::ranges::remove_copy_if(first, last, first2, UnaryTrue(&copies)); assert(copies == 0);
diff --git a/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_projections.pass.cpp b/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_projections.pass.cpp
--- a/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_projections.pass.cpp
+++ b/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_projections.pass.cpp
@@ -148,8 +148,8 @@
(void)std::ranges::minmax_element(a, Less(), Proj(&copies)); assert(copies == 0);
(void)std::ranges::mismatch(first, last, first2, last2, Equal(), Proj(&copies), Proj(&copies)); assert(copies == 0);
(void)std::ranges::mismatch(a, b, Equal(), Proj(&copies), Proj(&copies)); assert(copies == 0);
- //(void)std::ranges::next_permutation(first, last, Less(), Proj(&copies)); assert(copies == 0);
- //(void)std::ranges::next_permutation(a, Less(), Proj(&copies)); assert(copies == 0);
+ (void)std::ranges::next_permutation(first, last, Less(), Proj(&copies)); assert(copies == 0);
+ (void)std::ranges::next_permutation(a, Less(), Proj(&copies)); assert(copies == 0);
(void)std::ranges::none_of(first, last, UnaryTrue(), Proj(&copies)); assert(copies == 0);
(void)std::ranges::none_of(a, UnaryTrue(), Proj(&copies)); assert(copies == 0);
(void)std::ranges::nth_element(first, mid, last, Less(), Proj(&copies)); assert(copies == 0);
@@ -166,8 +166,8 @@
//(void)std::ranges::partition_point(a, UnaryTrue(), Proj(&copies)); assert(copies == 0);
(void)std::ranges::pop_heap(first, last, Less(), Proj(&copies)); assert(copies == 0);
(void)std::ranges::pop_heap(a, Less(), Proj(&copies)); assert(copies == 0);
- //(void)std::ranges::prev_permutation(first, last, Less(), Proj(&copies)); assert(copies == 0);
- //(void)std::ranges::prev_permutation(a, Less(), Proj(&copies)); assert(copies == 0);
+ (void)std::ranges::prev_permutation(first, last, Less(), Proj(&copies)); assert(copies == 0);
+ (void)std::ranges::prev_permutation(a, Less(), Proj(&copies)); assert(copies == 0);
(void)std::ranges::push_heap(first, last, Less(), Proj(&copies)); assert(copies == 0);
(void)std::ranges::push_heap(a, Less(), Proj(&copies)); assert(copies == 0);
//(void)std::ranges::remove_copy(first, last, first2, value, Proj(&copies)); assert(copies == 0);
diff --git a/libcxx/test/libcxx/private_headers.verify.cpp b/libcxx/test/libcxx/private_headers.verify.cpp
--- a/libcxx/test/libcxx/private_headers.verify.cpp
+++ b/libcxx/test/libcxx/private_headers.verify.cpp
@@ -148,6 +148,7 @@
#include <__algorithm/ranges_mismatch.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_mismatch.h'}}
#include <__algorithm/ranges_move.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_move.h'}}
#include <__algorithm/ranges_move_backward.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_move_backward.h'}}
+#include <__algorithm/ranges_next_permutation.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_next_permutation.h'}}
#include <__algorithm/ranges_none_of.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_none_of.h'}}
#include <__algorithm/ranges_nth_element.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_nth_element.h'}}
#include <__algorithm/ranges_partial_sort_copy.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_partial_sort_copy.h'}}
@@ -155,6 +156,7 @@
#include <__algorithm/ranges_partition_copy.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_partition_copy.h'}}
#include <__algorithm/ranges_partition_point.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_partition_point.h'}}
#include <__algorithm/ranges_pop_heap.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_pop_heap.h'}}
+#include <__algorithm/ranges_prev_permutation.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_prev_permutation.h'}}
#include <__algorithm/ranges_push_heap.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_push_heap.h'}}
#include <__algorithm/ranges_remove.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_remove.h'}}
#include <__algorithm/ranges_remove_copy.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_remove_copy.h'}}
diff --git a/libcxx/test/std/algorithms/alg.sorting/alg.permutation.generators/ranges.next_permutation.pass.cpp b/libcxx/test/std/algorithms/alg.sorting/alg.permutation.generators/ranges.next_permutation.pass.cpp
new file mode 100644
--- /dev/null
+++ b/libcxx/test/std/algorithms/alg.sorting/alg.permutation.generators/ranges.next_permutation.pass.cpp
@@ -0,0 +1,144 @@
+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+// <algorithm>
+
+// UNSUPPORTED: c++03, c++11, c++14, c++17
+// UNSUPPORTED: libcpp-has-no-incomplete-ranges
+
+// template<bidirectional_iterator I, sentinel_for<I> S, class Comp = ranges::less,
+// class Proj = identity>
+// requires sortable<I, Comp, Proj>
+// constexpr ranges::next_permutation_result<I>
+// ranges::next_permutation(I first, S last, Comp comp = {}, Proj proj = {});
+// template<bidirectional_range R, class Comp = ranges::less,
+// class Proj = identity>
+// requires sortable<iterator_t<R>, Comp, Proj>
+// constexpr ranges::next_permutation_result<borrowed_iterator_t<R>>
+// ranges::next_permutation(R&& r, Comp comp = {}, Proj proj = {});
+
+#include <algorithm>
+#include <array>
+#include <cassert>
+#include <cstddef>
+#include <ranges>
+
+#include "almost_satisfies_types.h"
+#include "test_iterators.h"
+
+template <class Iter, class Sent = sentinel_wrapper<Iter>>
+concept HasNextPermutationIt = requires(Iter first, Sent last) { std::ranges::next_permutation(first, last); };
+
+static_assert(HasNextPermutationIt<int*>);
+static_assert(!HasNextPermutationIt<BidirectionalIteratorNotDerivedFrom>);
+static_assert(!HasNextPermutationIt<BidirectionalIteratorNotDecrementable>);
+static_assert(!HasNextPermutationIt<int*, SentinelForNotSemiregular>);
+static_assert(!HasNextPermutationIt<int*, SentinelForNotWeaklyEqualityComparableWith>);
+static_assert(!HasNextPermutationIt<const int*>); // not sortable
+
+template <class Range>
+concept HasNextPermutationR = requires(Range range) { std::ranges::next_permutation(range); };
+
+static_assert(HasNextPermutationR<UncheckedRange<int*>>);
+static_assert(!HasNextPermutationR<BidirectionalRangeNotDerivedFrom>);
+static_assert(!HasNextPermutationR<BidirectionalRangeNotDecrementable>);
+static_assert(!HasNextPermutationR<BidirectionalRangeNotSentinelSemiregular>);
+static_assert(!HasNextPermutationR<BidirectionalRangeNotSentinelWeaklyEqualityComparableWith>);
+static_assert(!HasNextPermutationR<UncheckedRange<const int*>>); // not sortable
+
+constexpr size_t factorial(size_t i) {
+ size_t result = 1;
+ for (; i != 0; --i)
+ result *= i;
+ return result;
+}
+
+template <class Iter, class Sent>
+void test_permutations() {
+ auto test_next_permutations = [](auto call_next_permutation) {
+ auto input = std::array{1, 2, 3, 4, 5, 6};
+ std::array<int, input.size()> last_permutation;
+ for (size_t i = 0; i <= input.size(); ++i) {
+ size_t count = 0;
+
+ bool found_permutation = true;
+ while (found_permutation) {
+ last_permutation = input;
+ std::same_as<std::ranges::next_permutation_result<Iter>> decltype(auto) ret =
+ call_next_permutation(Iter(input.data()), Sent(Iter(input.data() + i)));
+ found_permutation = ret.found;
+ assert(base(ret.in) == input.data() + i);
+ if (i > 1) {
+ auto input_subrange = input | std::views::take(i);
+ auto last_permutation_subrange = last_permutation | std::views::take(i);
+ if (found_permutation)
+ assert(std::ranges::lexicographical_compare(last_permutation_subrange, input_subrange));
+ else
+ assert(std::ranges::lexicographical_compare(input_subrange, last_permutation_subrange));
+ }
+ ++count;
+ }
+ assert(count == factorial(i));
+ }
+ return true;
+ };
+
+ auto iterator_overload = [](auto&& first, auto&& last) { return std::ranges::next_permutation(first, last); };
+ auto range_overload = [](auto&& first, auto&& last) {
+ auto range = std::ranges::subrange(first, last);
+ return std::ranges::next_permutation(range);
+ };
+
+ if constexpr (std::is_same_v<Iter, Sent>) {
+ auto iterator_overload_counted =
+ [](auto first, auto last) -> std::ranges::next_permutation_result<decltype(first)> {
+ int count = 0;
+ auto ret = std::ranges::next_permutation(SwapCountingIterator(first, &count), SwapCountingIterator(last, &count));
+ assert(count <= (base(last) - base(first) + 1) / 2);
+ return ret;
+ };
+
+ auto range_overload_counted = [](auto first, auto last) -> std::ranges::next_permutation_result<decltype(first)> {
+ int count = 0;
+ auto range = std::ranges::subrange(SwapCountingIterator(first, &count), SwapCountingIterator(last, &count));
+ auto ret = std::ranges::next_permutation(range);
+ assert(count <= (base(last) - base(first) + 1) / 2);
+ return ret;
+ };
+
+ test_next_permutations(iterator_overload_counted);
+ static_assert(test_next_permutations(iterator_overload_counted));
+ test_next_permutations(range_overload_counted);
+ static_assert(test_next_permutations(range_overload_counted));
+ }
+
+ test_next_permutations(iterator_overload);
+ static_assert(test_next_permutations(iterator_overload));
+ test_next_permutations(range_overload);
+ static_assert(test_next_permutations(range_overload));
+}
+
+template <class Iter>
+void test_sentinels() {
+ test_permutations<Iter, Iter>();
+ test_permutations<Iter, sentinel_wrapper<Iter>>();
+ test_permutations<Iter, sized_sentinel<Iter>>();
+}
+
+void test() {
+ test_sentinels<bidirectional_iterator<int*>>();
+ test_sentinels<random_access_iterator<int*>>();
+ test_sentinels<contiguous_iterator<int*>>();
+ test_sentinels<int*>();
+}
+
+int main(int, char**) {
+ test();
+
+ return 0;
+}
diff --git a/libcxx/test/std/algorithms/alg.sorting/alg.permutation.generators/ranges.prev_permutation.pass.cpp b/libcxx/test/std/algorithms/alg.sorting/alg.permutation.generators/ranges.prev_permutation.pass.cpp
new file mode 100644
--- /dev/null
+++ b/libcxx/test/std/algorithms/alg.sorting/alg.permutation.generators/ranges.prev_permutation.pass.cpp
@@ -0,0 +1,140 @@
+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+// <algorithm>
+
+// UNSUPPORTED: c++03, c++11, c++14, c++17
+// UNSUPPORTED: libcpp-has-no-incomplete-ranges
+
+// template<bidirectional_iterator I, sentinel_for<I> S, class Comp = ranges::less,
+// class Proj = identity>
+// requires sortable<I, Comp, Proj>
+// constexpr ranges::prev_permutation_result<I>
+// ranges::prev_permutation(I first, S last, Comp comp = {}, Proj proj = {});
+// template<bidirectional_range R, class Comp = ranges::less,
+// class Proj = identity>
+// requires sortable<iterator_t<R>, Comp, Proj>
+// constexpr ranges::prev_permutation_result<borrowed_iterator_t<R>>
+// ranges::prev_permutation(R&& r, Comp comp = {}, Proj proj = {});
+
+#include <algorithm>
+#include <array>
+#include <cassert>
+#include <cstddef>
+#include <ranges>
+
+#include "almost_satisfies_types.h"
+#include "test_iterators.h"
+
+template <class Iter, class Sent = sentinel_wrapper<Iter>>
+concept HasPrevPermutationIt = requires(Iter first, Sent last) { std::ranges::prev_permutation(first, last); };
+
+static_assert(HasPrevPermutationIt<int*>);
+static_assert(!HasPrevPermutationIt<BidirectionalIteratorNotDerivedFrom>);
+static_assert(!HasPrevPermutationIt<BidirectionalIteratorNotDecrementable>);
+static_assert(!HasPrevPermutationIt<int*, SentinelForNotSemiregular>);
+static_assert(!HasPrevPermutationIt<int*, SentinelForNotWeaklyEqualityComparableWith>);
+static_assert(!HasPrevPermutationIt<const int*>); // not sortable
+
+template <class Range>
+concept HasPrevPermutationR = requires(Range range) { std::ranges::prev_permutation(range); };
+
+static_assert(HasPrevPermutationR<UncheckedRange<int*>>);
+static_assert(!HasPrevPermutationR<BidirectionalRangeNotDerivedFrom>);
+static_assert(!HasPrevPermutationR<BidirectionalRangeNotDecrementable>);
+static_assert(!HasPrevPermutationR<BidirectionalRangeNotSentinelSemiregular>);
+static_assert(!HasPrevPermutationR<BidirectionalRangeNotSentinelWeaklyEqualityComparableWith>);
+static_assert(!HasPrevPermutationR<UncheckedRange<const int*>>); // not sortable
+
+constexpr size_t factorial(size_t i) {
+ size_t result = 1;
+ for (; i != 0; --i)
+ result *= i;
+ return result;
+}
+
+template <class Iter, class Sent>
+void test_permutations() {
+ auto test_prev_permutations = [](auto call_prev_permutation) {
+ auto input = std::array{6, 5, 4, 3, 2, 1};
+ std::array<int, input.size()> last_permutation;
+ for (size_t i = 0; i <= input.size(); ++i) {
+ size_t count = 0;
+
+ bool found_permutation = true;
+ while (found_permutation) {
+ last_permutation = input;
+ std::same_as<std::ranges::prev_permutation_result<Iter>> decltype(auto) ret =
+ call_prev_permutation(Iter(input.data()), Sent(Iter(input.data() + i)));
+ found_permutation = ret.found;
+ assert(base(ret.in) == input.data() + i);
+ if (i > 1) {
+ auto input_subrange = input | std::views::take(i);
+ auto last_permutation_subrange = last_permutation | std::views::take(i);
+ if (found_permutation)
+ assert(std::ranges::lexicographical_compare(input_subrange, last_permutation_subrange));
+ else
+ assert(std::ranges::lexicographical_compare(last_permutation_subrange, input_subrange));
+ }
+ ++count;
+ }
+ assert(count == factorial(i));
+ }
+ return true;
+ };
+
+ auto iterator_overload = [](auto&& first, auto&& last) { return std::ranges::prev_permutation(first, last); };
+ auto range_overload = [](auto&& first, auto&& last) {
+ auto range = std::ranges::subrange(first, last);
+ return std::ranges::prev_permutation(range);
+ };
+
+ if constexpr (std::is_same_v<Iter, Sent>) {
+ auto iterator_overload_counted =
+ [](auto first, auto last) -> std::ranges::prev_permutation_result<decltype(first)> {
+ int count = 0;
+ auto ret = std::ranges::prev_permutation(SwapCountingIterator(first, &count), SwapCountingIterator(last, &count));
+ assert(count <= (base(last) - base(first) + 1) / 2);
+ return ret;
+ };
+
+ auto range_overload_counted = [](auto first, auto last) -> std::ranges::prev_permutation_result<decltype(first)> {
+ int count = 0;
+ auto range = std::ranges::subrange(SwapCountingIterator(first, &count), SwapCountingIterator(last, &count));
+ auto ret = std::ranges::prev_permutation(range);
+ assert(count <= (base(last) - base(first) + 1) / 2);
+ return ret;
+ };
+
+ test_prev_permutations(iterator_overload_counted);
+ static_assert(test_prev_permutations(iterator_overload_counted));
+ test_prev_permutations(range_overload_counted);
+ static_assert(test_prev_permutations(range_overload_counted));
+ }
+
+ test_prev_permutations(iterator_overload);
+ static_assert(test_prev_permutations(iterator_overload));
+ test_prev_permutations(range_overload);
+ static_assert(test_prev_permutations(range_overload));
+}
+
+template <class Iter>
+void test_sentinels() {
+ test_permutations<Iter, Iter>();
+ test_permutations<Iter, sentinel_wrapper<Iter>>();
+ test_permutations<Iter, sized_sentinel<Iter>>();
+}
+
+void test() {
+ test_sentinels<bidirectional_iterator<int*>>();
+ test_sentinels<random_access_iterator<int*>>();
+ test_sentinels<contiguous_iterator<int*>>();
+ test_sentinels<int*>();
+}
+
+int main(int, char**) { test(); }
diff --git a/libcxx/test/std/algorithms/ranges_result_alias_declarations.compile.pass.cpp b/libcxx/test/std/algorithms/ranges_result_alias_declarations.compile.pass.cpp
--- a/libcxx/test/std/algorithms/ranges_result_alias_declarations.compile.pass.cpp
+++ b/libcxx/test/std/algorithms/ranges_result_alias_declarations.compile.pass.cpp
@@ -56,7 +56,7 @@
static_assert(std::is_same_v<min_max_result<int>, minmax_result<int>>);
static_assert(std::is_same_v<min_max_result<int>, minmax_element_result<int>>);
-// static_assert(std::is_same_v<in_found_result<int>, next_permutation_result<int>>);
-// static_assert(std::is_same_v<in_found_result<int>, prev_permutation_result<int>>);
+static_assert(std::is_same_v<in_found_result<int>, next_permutation_result<int>>);
+static_assert(std::is_same_v<in_found_result<int>, prev_permutation_result<int>>);
// static_assert(std::is_same_v<out_value_result<int>, iota_result<int>>);
diff --git a/libcxx/test/std/algorithms/ranges_robust_against_nonbool_predicates.compile.pass.cpp b/libcxx/test/std/algorithms/ranges_robust_against_nonbool_predicates.compile.pass.cpp
--- a/libcxx/test/std/algorithms/ranges_robust_against_nonbool_predicates.compile.pass.cpp
+++ b/libcxx/test/std/algorithms/ranges_robust_against_nonbool_predicates.compile.pass.cpp
@@ -167,6 +167,6 @@
in_pred(std::ranges::push_heap, in, binary_pred);
in_pred(std::ranges::pop_heap, in, binary_pred);
in_pred(std::ranges::sort_heap, in, binary_pred);
- //in_pred(std::ranges::prev_permutation, in, binary_pred);
- //in_pred(std::ranges::next_permutation, in, binary_pred);
+ in_pred(std::ranges::prev_permutation, in, binary_pred);
+ in_pred(std::ranges::next_permutation, in, binary_pred);
}
diff --git a/libcxx/test/std/algorithms/ranges_robust_against_omitting_invoke.compile.pass.cpp b/libcxx/test/std/algorithms/ranges_robust_against_omitting_invoke.compile.pass.cpp
--- a/libcxx/test/std/algorithms/ranges_robust_against_omitting_invoke.compile.pass.cpp
+++ b/libcxx/test/std/algorithms/ranges_robust_against_omitting_invoke.compile.pass.cpp
@@ -212,6 +212,6 @@
in_pred(std::ranges::push_heap, in, &Foo::binary_pred, &Bar::val);
in_pred(std::ranges::pop_heap, in, &Foo::binary_pred, &Bar::val);
in_pred(std::ranges::sort_heap, in, &Foo::binary_pred, &Bar::val);
- //in_pred(std::ranges::prev_permutation, in, &Foo::binary_pred, &Bar::val);
- //in_pred(std::ranges::next_permutation, in, &Foo::binary_pred, &Bar::val);
+ in_pred(std::ranges::prev_permutation, in, &Foo::binary_pred, &Bar::val);
+ in_pred(std::ranges::next_permutation, in, &Foo::binary_pred, &Bar::val);
}
diff --git a/libcxx/test/support/almost_satisfies_types.h b/libcxx/test/support/almost_satisfies_types.h
--- a/libcxx/test/support/almost_satisfies_types.h
+++ b/libcxx/test/support/almost_satisfies_types.h
@@ -202,6 +202,10 @@
};
using BidirectionalRangeNotDerivedFrom = UncheckedRange<BidirectionalIteratorNotDerivedFrom>;
+using BidirectionalRangeNotSentinelSemiregular =
+ UncheckedRange<bidirectional_iterator<int*>, SentinelForNotSemiregular>;
+using BidirectionalRangeNotSentinelWeaklyEqualityComparableWith =
+ UncheckedRange<bidirectional_iterator<int*>, SentinelForNotWeaklyEqualityComparableWith>;
static_assert(std::forward_iterator<BidirectionalIteratorNotDerivedFrom>);
static_assert(!std::bidirectional_iterator<BidirectionalIteratorNotDerivedFrom>);
diff --git a/libcxx/test/support/test_iterators.h b/libcxx/test/support/test_iterators.h
--- a/libcxx/test/support/test_iterators.h
+++ b/libcxx/test/support/test_iterators.h
@@ -726,6 +726,140 @@
difference_type stride_displacement_ = 0;
};
+template <std::input_iterator Base>
+consteval auto get_iterator_concept() {
+ if constexpr (std::contiguous_iterator<Base>) {
+ return std::contiguous_iterator_tag();
+ } else if constexpr (std::random_access_iterator<Base>) {
+ return std::random_access_iterator_tag{};
+ } else if constexpr (std::bidirectional_iterator<Base>) {
+ return std::bidirectional_iterator_tag{};
+ } else if constexpr (std::forward_iterator<Base>) {
+ return std::forward_iterator_tag{};
+ } else {
+ return std::input_iterator_tag{};
+ }
+}
+
+template <std::input_iterator Iter>
+using iter_concept_t = decltype(get_iterator_concept<Iter>());
+
+template <class Iter>
+struct SwapCountingIterator {
+ using difference_type = std::iter_difference_t<Iter>;
+ using value_type = std::iter_value_t<Iter>;
+ using iterator_concept = iter_concept_t<Iter>;
+
+ Iter iter_;
+ int* counter_;
+ SwapCountingIterator() = default;
+ constexpr SwapCountingIterator(const Iter& iter, int* counter) : iter_(iter), counter_(counter) {}
+
+ constexpr friend void iter_swap(const SwapCountingIterator& lhs, const SwapCountingIterator& rhs) {
+ std::ranges::iter_swap(lhs.iter_, rhs.iter_);
+ ++*lhs.counter_;
+ }
+
+ constexpr SwapCountingIterator& operator++() {
+ ++iter_;
+ return *this;
+ }
+
+ constexpr SwapCountingIterator operator++(int) {
+ auto tmp = *this;
+ ++*this;
+ return tmp;
+ }
+
+ constexpr SwapCountingIterator& operator--() {
+ --iter_;
+ return *this;
+ }
+
+ constexpr SwapCountingIterator operator--(int) {
+ auto tmp = *this;
+ ++*this;
+ return tmp;
+ }
+
+ constexpr auto base() { return base(iter_); }
+
+ constexpr decltype(auto) operator*() const { return *iter_; }
+
+ friend bool operator==(const SwapCountingIterator& lhs, const SwapCountingIterator& rhs) = default;
+
+ constexpr operator Iter() {
+ return iter_;
+ }
+
+ // to satisfy random_access_iterator
+ constexpr SwapCountingIterator& operator+=(difference_type n)
+ requires std::random_access_iterator<Iter> {
+ iter_ += n;
+ return *this;
+ }
+
+ constexpr SwapCountingIterator& operator-=(difference_type n)
+ requires std::random_access_iterator<Iter> {
+ iter_ -= n;
+ return *this;
+ }
+
+ constexpr decltype(auto) operator[](difference_type n) const
+ requires std::random_access_iterator<Iter> {
+ return iter_[n];
+ }
+
+ friend constexpr bool operator<(const SwapCountingIterator& x, const SwapCountingIterator& y)
+ requires std::random_access_iterator<Iter> {
+ return x.iter_ < y.iter_;
+ }
+
+ friend constexpr bool operator>(const SwapCountingIterator& x, const SwapCountingIterator& y)
+ requires std::random_access_iterator<Iter> {
+ return x.iter_ > y.iter_;
+ }
+
+ friend constexpr bool operator<=(const SwapCountingIterator& x, const SwapCountingIterator& y)
+ requires std::random_access_iterator<Iter> {
+ return x.iter_ <= y.iter_;
+ }
+
+ friend constexpr bool operator>=(const SwapCountingIterator& x, const SwapCountingIterator& y)
+ requires std::random_access_iterator<Iter> {
+ return x.iter_ >= y.iter_;
+ }
+
+ friend constexpr auto operator<=>(const SwapCountingIterator& x, const SwapCountingIterator& y)
+ requires(std::random_access_iterator<Iter> && std::three_way_comparable<Iter>) {
+ return x.iter_ <=> y.iter_;
+ }
+
+ friend constexpr SwapCountingIterator operator+(const SwapCountingIterator& x, difference_type n)
+ requires std::random_access_iterator<Iter> {
+ return SwapCountingIterator{x.iter_ + n};
+ }
+
+ friend constexpr SwapCountingIterator operator+(difference_type n, const SwapCountingIterator& x)
+ requires std::random_access_iterator<Iter> {
+ return SwapCountingIterator{n + x.iter_};
+ }
+
+ friend constexpr SwapCountingIterator operator-(const SwapCountingIterator& x, difference_type n)
+ requires std::random_access_iterator<Iter> {
+ return SwapCountingIterator{x.iter_ - n};
+ }
+
+ friend constexpr difference_type operator-(const SwapCountingIterator& x, const SwapCountingIterator& y)
+ requires std::random_access_iterator<Iter> {
+ return x.iter_ - y.iter_;
+ }
+
+};
+
+static_assert(std::bidirectional_iterator<SwapCountingIterator<bidirectional_iterator<int*>>>);
+static_assert(std::random_access_iterator<SwapCountingIterator<random_access_iterator<int*>>>);
+
#endif // TEST_STD_VER > 17
#if TEST_STD_VER > 17
@@ -827,12 +961,12 @@
// ======================================================================
// Proxy that can wrap a value or a reference. It simulates C++23's tuple
// but simplified to just hold one argument.
-// Note that unlike tuple, this class deliberately doesn't have special handling
-// of swap to cause a compilation error if it's used in an algorithm that relies
+// Note that unlike tuple, this class deliberately doesn't have special handling
+// of swap to cause a compilation error if it's used in an algorithm that relies
// on plain swap instead of ranges::iter_swap.
// This class is useful for testing that if algorithms support proxy iterator
// properly, i.e. calling ranges::iter_swap and ranges::iter_move instead of
-// plain swap and std::move
+// plain swap and std::move
template <class T>
struct Proxy;
@@ -920,29 +1054,16 @@
template <class Base>
requires std::derived_from<
typename std::iterator_traits<Base>::iterator_category,
- std::input_iterator_tag>
+ std::input_iterator_tag>
struct ProxyIteratorBase<Base> {
using iterator_category = std::input_iterator_tag;
};
-template <std::input_iterator Base>
-consteval auto get_iterator_concept() {
- if constexpr (std::random_access_iterator<Base>) {
- return std::random_access_iterator_tag{};
- } else if constexpr (std::bidirectional_iterator<Base>) {
- return std::bidirectional_iterator_tag{};
- } else if constexpr (std::forward_iterator<Base>) {
- return std::forward_iterator_tag{};
- } else {
- return std::input_iterator_tag{};
- }
-}
-
template <std::input_iterator Base>
struct ProxyIterator : ProxyIteratorBase<Base> {
Base base_;
- using iterator_concept = decltype(get_iterator_concept<Base>());
+ using iterator_concept = iter_concept_t<Base>;
using value_type = Proxy<std::iter_value_t<Base>>;
using difference_type = std::iter_difference_t<Base>;
@@ -951,8 +1072,8 @@
= default;
constexpr ProxyIterator(Base base) : base_{std::move(base)} {}
-
- template <class T>
+
+ template <class T>
requires std::constructible_from<Base, T&&>
constexpr ProxyIterator(T&& t) : base_{std::forward<T>(t)} {}