1 // Copyright Neil Groves 2009. Use, modification and
2 // distribution is subject to the Boost Software License, Version
3 // 1.0. (See accompanying file LICENSE_1_0.txt or copy at
4 // http://www.boost.org/LICENSE_1_0.txt)
5 //
6 //
7 // For more information, see http://www.boost.org/libs/range/
8 //
9 #ifndef BOOST_RANGE_ALGORITHM_RANDOM_SHUFFLE_HPP_INCLUDED
10 #define BOOST_RANGE_ALGORITHM_RANDOM_SHUFFLE_HPP_INCLUDED
11
12 #include <boost/concept_check.hpp>
13 #include <boost/range/begin.hpp>
14 #include <boost/range/end.hpp>
15 #include <boost/range/concepts.hpp>
16 #include <algorithm>
17 #ifdef BOOST_NO_CXX98_RANDOM_SHUFFLE
18 #include <cstdlib>
19 #endif
20
21 namespace boost
22 {
23 namespace range
24 {
25
26 namespace detail
27 {
28 #ifdef BOOST_NO_CXX98_RANDOM_SHUFFLE
29
30 // wrap std::rand as UniformRandomBitGenerator
31 struct wrap_rand
32 {
33 typedef unsigned int result_type;
34
result_typeboost::range::detail::wrap_rand35 static BOOST_CONSTEXPR result_type (min)()
36 {
37 return 0;
38 }
39
result_typeboost::range::detail::wrap_rand40 static BOOST_CONSTEXPR result_type (max)()
41 {
42 return RAND_MAX;
43 }
44
operator ()boost::range::detail::wrap_rand45 result_type operator()()
46 {
47 return std::rand();
48 }
49 };
50
51 template< class RandomIt >
random_shuffle(RandomIt first,RandomIt last)52 inline void random_shuffle(RandomIt first, RandomIt last)
53 {
54 std::shuffle(first, last, wrap_rand());
55 }
56
57 // wrap Generator as UniformRandomBitGenerator
58 template< class Generator >
59 struct wrap_generator
60 {
61 typedef unsigned int result_type;
62 static const int max_arg = ((0u - 1u) >> 2) + 1;
63 Generator& g;
64
wrap_generatorboost::range::detail::wrap_generator65 wrap_generator(Generator& gen) : g(gen) {}
66
result_typeboost::range::detail::wrap_generator67 static BOOST_CONSTEXPR result_type (min)()
68 {
69 return 0;
70 }
71
result_typeboost::range::detail::wrap_generator72 static BOOST_CONSTEXPR result_type (max)()
73 {
74 return max_arg - 1;
75 }
76
operator ()boost::range::detail::wrap_generator77 result_type operator()()
78 {
79 return static_cast<result_type>(g(max_arg));
80 }
81 };
82
83 template< class RandomIt, class Generator >
random_shuffle(RandomIt first,RandomIt last,Generator & gen)84 inline void random_shuffle(RandomIt first, RandomIt last, Generator& gen)
85 {
86 std::shuffle(first, last, wrap_generator< Generator >(gen));
87 }
88
89 #else
90
91 using std::random_shuffle;
92
93 #endif
94 } // namespace detail
95
96 /// \brief template function random_shuffle
97 ///
98 /// range-based version of the random_shuffle std algorithm
99 ///
100 /// \pre RandomAccessRange is a model of the RandomAccessRangeConcept
101 /// \pre Generator is a model of the UnaryFunctionConcept
102 template<class RandomAccessRange>
random_shuffle(RandomAccessRange & rng)103 inline RandomAccessRange& random_shuffle(RandomAccessRange& rng)
104 {
105 BOOST_RANGE_CONCEPT_ASSERT(( RandomAccessRangeConcept<RandomAccessRange> ));
106 detail::random_shuffle(boost::begin(rng), boost::end(rng));
107 return rng;
108 }
109
110 /// \overload
111 template<class RandomAccessRange>
random_shuffle(const RandomAccessRange & rng)112 inline const RandomAccessRange& random_shuffle(const RandomAccessRange& rng)
113 {
114 BOOST_RANGE_CONCEPT_ASSERT(( RandomAccessRangeConcept<const RandomAccessRange> ));
115 detail::random_shuffle(boost::begin(rng), boost::end(rng));
116 return rng;
117 }
118
119 /// \overload
120 template<class RandomAccessRange, class Generator>
random_shuffle(RandomAccessRange & rng,Generator & gen)121 inline RandomAccessRange& random_shuffle(RandomAccessRange& rng, Generator& gen)
122 {
123 BOOST_RANGE_CONCEPT_ASSERT(( RandomAccessRangeConcept<RandomAccessRange> ));
124 detail::random_shuffle(boost::begin(rng), boost::end(rng), gen);
125 return rng;
126 }
127
128 /// \overload
129 template<class RandomAccessRange, class Generator>
random_shuffle(const RandomAccessRange & rng,Generator & gen)130 inline const RandomAccessRange& random_shuffle(const RandomAccessRange& rng, Generator& gen)
131 {
132 BOOST_RANGE_CONCEPT_ASSERT(( RandomAccessRangeConcept<const RandomAccessRange> ));
133 detail::random_shuffle(boost::begin(rng), boost::end(rng), gen);
134 return rng;
135 }
136
137 } // namespace range
138 using range::random_shuffle;
139 } // namespace boost
140
141 #endif // include guard
142