[libc++][ranges] Implement `ranges::shuffle`.
Differential Revision: https://reviews.llvm.org/D130321
NOKEYCHECK=True
GitOrigin-RevId: 14cf74d65d9f73e547fd97b00be878ac8e029a7e
diff --git a/include/__algorithm/partial_sort.h b/include/__algorithm/partial_sort.h
index cb6887e..24016e5 100644
--- a/include/__algorithm/partial_sort.h
+++ b/include/__algorithm/partial_sort.h
@@ -54,14 +54,6 @@
return __i;
}
-// TODO(ranges): once `ranges::shuffle` is implemented, remove this helper and make `__debug_randomize_range` support
-// sentinels.
-template <class _AlgPolicy, class _RandomAccessIterator, class _Sentinel>
-_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17
-void __maybe_randomize(_RandomAccessIterator __first, _Sentinel __last) {
- std::__debug_randomize_range<_AlgPolicy>(__first, _IterOps<_AlgPolicy>::next(__first, __last));
-}
-
template <class _AlgPolicy, class _Compare, class _RandomAccessIterator, class _Sentinel>
_LIBCPP_CONSTEXPR_AFTER_CXX17
_RandomAccessIterator __partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _Sentinel __last,
@@ -69,12 +61,12 @@
if (__first == __middle)
return _IterOps<_AlgPolicy>::next(__middle, __last);
- std::__maybe_randomize<_AlgPolicy>(__first, __last);
+ std::__debug_randomize_range<_AlgPolicy>(__first, __last);
using _Comp_ref = typename __comp_ref_type<_Compare>::type;
auto __last_iter = std::__partial_sort_impl<_AlgPolicy, _Comp_ref>(__first, __middle, __last, __comp);
- std::__maybe_randomize<_AlgPolicy>(__middle, __last);
+ std::__debug_randomize_range<_AlgPolicy>(__middle, __last);
return __last_iter;
}
diff --git a/include/__algorithm/ranges_shuffle.h b/include/__algorithm/ranges_shuffle.h
index bf9c28b..b101a85 100644
--- a/include/__algorithm/ranges_shuffle.h
+++ b/include/__algorithm/ranges_shuffle.h
@@ -9,23 +9,22 @@
#ifndef _LIBCPP___ALGORITHM_RANGES_SHUFFLE_H
#define _LIBCPP___ALGORITHM_RANGES_SHUFFLE_H
-#include <__algorithm/make_projected.h>
+#include <__algorithm/iterator_operations.h>
#include <__algorithm/shuffle.h>
#include <__config>
-#include <__functional/identity.h>
#include <__functional/invoke.h>
#include <__functional/ranges_operations.h>
#include <__iterator/concepts.h>
#include <__iterator/iterator_traits.h>
+#include <__iterator/next.h>
#include <__iterator/permutable.h>
-#include <__iterator/projected.h>
#include <__random/uniform_random_bit_generator.h>
#include <__ranges/access.h>
#include <__ranges/concepts.h>
#include <__ranges/dangling.h>
-#include <__type_traits/remove_reference.h>
#include <__utility/forward.h>
#include <__utility/move.h>
+#include <type_traits>
#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
# pragma GCC system_header
@@ -33,29 +32,57 @@
#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
+_LIBCPP_PUSH_MACROS
+#include <__undef_macros>
+
_LIBCPP_BEGIN_NAMESPACE_STD
namespace ranges {
namespace __shuffle {
struct __fn {
+ // `std::shuffle` is more constrained than `std::ranges::shuffle`. `std::ranges::shuffle` only requires the given
+ // generator to satisfy the `std::uniform_random_bit_generator` concept. `std::shuffle` requires the given
+ // generator to meet the uniform random bit generator requirements; these requirements include satisfying
+ // `std::uniform_random_bit_generator` and add a requirement for the generator to provide a nested `result_type`
+ // typedef (see `[rand.req.urng]`).
+ //
+ // To reuse the implementation from `std::shuffle`, make the given generator meet the classic requirements by wrapping
+ // it into an adaptor type that forwards all of its interface and adds the required typedef.
+ template <class _Gen>
+ class _ClassicGenAdaptor {
+ private:
+ // The generator is not required to be copyable or movable, so it has to be stored as a reference.
+ _Gen& __gen;
+
+ public:
+ using result_type = invoke_result_t<_Gen&>;
+
+ _LIBCPP_HIDE_FROM_ABI
+ static constexpr auto min() { return __uncvref_t<_Gen>::min(); }
+ _LIBCPP_HIDE_FROM_ABI
+ static constexpr auto max() { return __uncvref_t<_Gen>::max(); }
+
+ _LIBCPP_HIDE_FROM_ABI
+ constexpr explicit _ClassicGenAdaptor(_Gen& __g) : __gen(__g) {}
+
+ _LIBCPP_HIDE_FROM_ABI
+ constexpr auto operator()() const { return __gen(); }
+ };
template <random_access_iterator _Iter, sentinel_for<_Iter> _Sent, class _Gen>
requires permutable<_Iter> && uniform_random_bit_generator<remove_reference_t<_Gen>>
_LIBCPP_HIDE_FROM_ABI
_Iter operator()(_Iter __first, _Sent __last, _Gen&& __gen) const {
- // TODO: implement
- (void)__first; (void)__last; (void)__gen;
- return {};
+ _ClassicGenAdaptor<_Gen> __adapted_gen(__gen);
+ return std::__shuffle<_RangeAlgPolicy>(std::move(__first), std::move(__last), __adapted_gen);
}
template<random_access_range _Range, class _Gen>
requires permutable<iterator_t<_Range>> && uniform_random_bit_generator<remove_reference_t<_Gen>>
_LIBCPP_HIDE_FROM_ABI
borrowed_iterator_t<_Range> operator()(_Range&& __range, _Gen&& __gen) const {
- // TODO: implement
- (void)__range; (void)__gen;
- return {};
+ return (*this)(ranges::begin(__range), ranges::end(__range), std::forward<_Gen>(__gen));
}
};
@@ -69,6 +96,8 @@
_LIBCPP_END_NAMESPACE_STD
+_LIBCPP_POP_MACROS
+
#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
#endif // _LIBCPP___ALGORITHM_RANGES_SHUFFLE_H
diff --git a/include/__algorithm/shuffle.h b/include/__algorithm/shuffle.h
index 0778815..e32c6a7 100644
--- a/include/__algorithm/shuffle.h
+++ b/include/__algorithm/shuffle.h
@@ -136,11 +136,15 @@
}
#endif
-template <class _AlgPolicy, class _RandomAccessIterator, class _UniformRandomNumberGenerator>
-void __shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last, _UniformRandomNumberGenerator&& __g) {
+template <class _AlgPolicy, class _RandomAccessIterator, class _Sentinel, class _UniformRandomNumberGenerator>
+_RandomAccessIterator __shuffle(
+ _RandomAccessIterator __first, _Sentinel __last_sentinel, _UniformRandomNumberGenerator&& __g) {
typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
typedef uniform_int_distribution<ptrdiff_t> _Dp;
typedef typename _Dp::param_type _Pp;
+
+ auto __original_last = _IterOps<_AlgPolicy>::next(__first, __last_sentinel);
+ auto __last = __original_last;
difference_type __d = __last - __first;
if (__d > 1)
{
@@ -152,12 +156,14 @@
_IterOps<_AlgPolicy>::iter_swap(__first, __first + __i);
}
}
+
+ return __original_last;
}
template <class _RandomAccessIterator, class _UniformRandomNumberGenerator>
void shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
_UniformRandomNumberGenerator&& __g) {
- std::__shuffle<_ClassicAlgPolicy>(
+ (void)std::__shuffle<_ClassicAlgPolicy>(
std::move(__first), std::move(__last), std::forward<_UniformRandomNumberGenerator>(__g));
}
diff --git a/include/__debug_utils/randomize_range.h b/include/__debug_utils/randomize_range.h
index 9ed2255..9843709 100644
--- a/include/__debug_utils/randomize_range.h
+++ b/include/__debug_utils/randomize_range.h
@@ -22,8 +22,9 @@
_LIBCPP_BEGIN_NAMESPACE_STD
-template <class _AlgPolicy, class _Iterator>
-_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 void __debug_randomize_range(_Iterator __first, _Iterator __last) {
+template <class _AlgPolicy, class _Iterator, class _Sentinel>
+_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11
+void __debug_randomize_range(_Iterator __first, _Sentinel __last) {
#ifdef _LIBCPP_DEBUG_RANDOMIZE_UNSPECIFIED_STABILITY
# ifdef _LIBCPP_CXX03_LANG
# error Support for unspecified stability is only for C++11 and higher
diff --git a/include/algorithm b/include/algorithm
index aea6ad8..5958ad1 100644
--- a/include/algorithm
+++ b/include/algorithm
@@ -710,6 +710,16 @@
constexpr ranges::rotate_copy_result<borrowed_iterator_t<R>, O>
ranges::rotate_copy(R&& r, iterator_t<R> middle, O result); // since C++20
+ template<random_access_iterator I, sentinel_for<I> S, class Gen>
+ requires permutable<I> &&
+ uniform_random_bit_generator<remove_reference_t<Gen>>
+ I shuffle(I first, S last, Gen&& g); // Since C++20
+
+ template<random_access_range R, class Gen>
+ requires permutable<iterator_t<R>> &&
+ uniform_random_bit_generator<remove_reference_t<Gen>>
+ borrowed_iterator_t<R> shuffle(R&& r, Gen&& g); // Since C++20
+
template<forward_iterator I1, sentinel_for<I1> S1, forward_iterator I2,
sentinel_for<I2> S2, class Pred = ranges::equal_to,
class Proj1 = identity, class Proj2 = identity>
@@ -1603,6 +1613,7 @@
#include <__algorithm/ranges_set_intersection.h>
#include <__algorithm/ranges_set_symmetric_difference.h>
#include <__algorithm/ranges_set_union.h>
+#include <__algorithm/ranges_shuffle.h>
#include <__algorithm/ranges_sort.h>
#include <__algorithm/ranges_sort_heap.h>
#include <__algorithm/ranges_stable_partition.h>