v3/algorithm/shuffle.hpp

0001 /// \file
0002 // Range v3 library
0003 //
0004 //  Copyright Eric Niebler 2014-present
0005 //
0006 //  Use, modification and distribution is subject to the
0007 //  Boost Software License, Version 1.0. (See accompanying
0008 //  file LICENSE_1_0.txt or copy at
0009 //  http://www.boost.org/LICENSE_1_0.txt)
0010 //
0011 // Project home: https://github.com/ericniebler/range-v3
0012 //
0013 #ifndef RANGES_V3_ALGORITHM_SHUFFLE_HPP
0014 #define RANGES_V3_ALGORITHM_SHUFFLE_HPP
0015
0016 #include <cstdint>
0017 #include <utility>
0018
0019 #include <range/v3/range_fwd.hpp>
0020
0021 #include <range/v3/functional/invoke.hpp>
0022 #include <range/v3/iterator/concepts.hpp>
0023 #include <range/v3/iterator/traits.hpp>
0024 #include <range/v3/range/access.hpp>
0025 #include <range/v3/range/concepts.hpp>
0026 #include <range/v3/range/dangling.hpp>
0027 #include <range/v3/range/traits.hpp>
0028 #include <range/v3/utility/random.hpp>
0029 #include <range/v3/utility/static_const.hpp>
0030 #include <range/v3/utility/swap.hpp>
0031
0032 #include <range/v3/detail/prologue.hpp>
0033
0034 namespace ranges
0035 {
0036     /// \addtogroup group-algorithms
0037     /// @{
0038     RANGES_FUNC_BEGIN(shuffle)
0039
0040         /// \brief function template \c shuffle
0041         template(typename I, typename S, typename Gen = detail::default_random_engine &)(
0042             requires random_access_iterator<I> AND sentinel_for<S, I> AND
0043                 permutable<I> AND
0044                 uniform_random_bit_generator<std::remove_reference_t<Gen>> AND
0045                 convertible_to<invoke_result_t<Gen &>, iter_difference_t<I>>)
0046         I RANGES_FUNC(shuffle)(I const first,
0047                                S const last,
0048                                Gen && gen = detail::get_random_engine()) //
0049         {
0050             auto mid = first;
0051             if(mid == last)
0052                 return mid;
0053             using D1 = iter_difference_t<I>;
0054             using D2 =
0055                 meta::conditional_t<std::is_integral<D1>::value, D1, std::ptrdiff_t>;
0056             std::uniform_int_distribution<D2> uid{};
0057             using param_t = typename decltype(uid)::param_type;
0058             while(++mid != last)
0059             {
0060                 RANGES_ENSURE(mid - first <= PTRDIFF_MAX);
0061                 if(auto const i = uid(gen, param_t{0, D2(mid - first)}))
0062                     ranges::iter_swap(mid - i, mid);
0063             }
0064             return mid;
0065         }
0066
0067         /// \overload
0068         template(typename Rng, typename Gen = detail::default_random_engine &)(
0069             requires random_access_range<Rng> AND permutable<iterator_t<Rng>> AND
0070                 uniform_random_bit_generator<std::remove_reference_t<Gen>> AND
0071                 convertible_to<invoke_result_t<Gen &>,
0072                                iter_difference_t<iterator_t<Rng>>>)
0073         borrowed_iterator_t<Rng> //
0074         RANGES_FUNC(shuffle)(Rng && rng, Gen && rand = detail::get_random_engine()) //
0075         {
0076             return (*this)(begin(rng), end(rng), static_cast<Gen &&>(rand));
0077         }
0078
0079     RANGES_FUNC_END(shuffle)
0080
0081     namespace cpp20
0082     {
0083         using ranges::shuffle;
0084     }
0085     /// @}
0086 } // namespace ranges
0087
0088 #include <range/v3/detail/epilogue.hpp>
0089
0090 #endif