range/algorithm/random_shuffle.hpp

0001 //  Copyright Neil Groves 2009. Use, modification and
0002 //  distribution is subject to the Boost Software License, Version
0003 //  1.0. (See accompanying file LICENSE_1_0.txt or copy at
0004 //  http://www.boost.org/LICENSE_1_0.txt)
0005 //
0006 //
0007 // For more information, see http://www.boost.org/libs/range/
0008 //
0009 #ifndef BOOST_RANGE_ALGORITHM_RANDOM_SHUFFLE_HPP_INCLUDED
0010 #define BOOST_RANGE_ALGORITHM_RANDOM_SHUFFLE_HPP_INCLUDED
0011
0012 #include <boost/concept_check.hpp>
0013 #include <boost/range/begin.hpp>
0014 #include <boost/range/end.hpp>
0015 #include <boost/range/concepts.hpp>
0016 #include <algorithm>
0017 #ifdef BOOST_NO_CXX98_RANDOM_SHUFFLE
0018 #include <cstdlib>
0019 #endif
0020
0021 namespace boost
0022 {
0023     namespace range
0024     {
0025
0026         namespace detail
0027         {
0028 #ifdef BOOST_NO_CXX98_RANDOM_SHUFFLE
0029
0030 // wrap std::rand as UniformRandomBitGenerator
0031 struct wrap_rand
0032 {
0033     typedef unsigned int result_type;
0034
0035     static BOOST_CONSTEXPR result_type (min)()
0036     {
0037         return 0;
0038     }
0039
0040     static BOOST_CONSTEXPR result_type (max)()
0041     {
0042         return RAND_MAX;
0043     }
0044
0045     result_type operator()()
0046     {
0047         return std::rand();
0048     }
0049 };
0050
0051 template< class RandomIt >
0052 inline void random_shuffle(RandomIt first, RandomIt last)
0053 {
0054     std::shuffle(first, last, wrap_rand());
0055 }
0056
0057 // wrap Generator as UniformRandomBitGenerator
0058 template< class Generator >
0059 struct wrap_generator
0060 {
0061     typedef unsigned int result_type;
0062     static const int max_arg = ((0u - 1u) >> 2) + 1;
0063     Generator& g;
0064
0065     wrap_generator(Generator& gen) : g(gen) {}
0066
0067     static BOOST_CONSTEXPR result_type (min)()
0068     {
0069         return 0;
0070     }
0071
0072     static BOOST_CONSTEXPR result_type (max)()
0073     {
0074         return max_arg - 1;
0075     }
0076
0077     result_type operator()()
0078     {
0079         return static_cast<result_type>(g(max_arg));
0080     }
0081 };
0082
0083 template< class RandomIt, class Generator >
0084 inline void random_shuffle(RandomIt first, RandomIt last, Generator& gen)
0085 {
0086     std::shuffle(first, last, wrap_generator< Generator >(gen));
0087 }
0088
0089 #else
0090
0091 using std::random_shuffle;
0092
0093 #endif
0094         } // namespace detail
0095
0096 /// \brief template function random_shuffle
0097 ///
0098 /// range-based version of the random_shuffle std algorithm
0099 ///
0100 /// \pre RandomAccessRange is a model of the RandomAccessRangeConcept
0101 /// \pre Generator is a model of the UnaryFunctionConcept
0102 template<class RandomAccessRange>
0103 inline RandomAccessRange& random_shuffle(RandomAccessRange& rng)
0104 {
0105     BOOST_RANGE_CONCEPT_ASSERT(( RandomAccessRangeConcept<RandomAccessRange> ));
0106     detail::random_shuffle(boost::begin(rng), boost::end(rng));
0107     return rng;
0108 }
0109
0110 /// \overload
0111 template<class RandomAccessRange>
0112 inline const RandomAccessRange& random_shuffle(const RandomAccessRange& rng)
0113 {
0114     BOOST_RANGE_CONCEPT_ASSERT(( RandomAccessRangeConcept<const RandomAccessRange> ));
0115     detail::random_shuffle(boost::begin(rng), boost::end(rng));
0116     return rng;
0117 }
0118
0119 /// \overload
0120 template<class RandomAccessRange, class Generator>
0121 inline RandomAccessRange& random_shuffle(RandomAccessRange& rng, Generator& gen)
0122 {
0123     BOOST_RANGE_CONCEPT_ASSERT(( RandomAccessRangeConcept<RandomAccessRange> ));
0124     detail::random_shuffle(boost::begin(rng), boost::end(rng), gen);
0125     return rng;
0126 }
0127
0128 /// \overload
0129 template<class RandomAccessRange, class Generator>
0130 inline const RandomAccessRange& random_shuffle(const RandomAccessRange& rng, Generator& gen)
0131 {
0132     BOOST_RANGE_CONCEPT_ASSERT(( RandomAccessRangeConcept<const RandomAccessRange> ));
0133     detail::random_shuffle(boost::begin(rng), boost::end(rng), gen);
0134     return rng;
0135 }
0136
0137     } // namespace range
0138     using range::random_shuffle;
0139 } // namespace boost
0140
0141 #endif // include guard