X-Git-Url: https://git.donarmstrong.com/?p=rsem.git;a=blobdiff_plain;f=boost%2Frandom%2Fshuffle_output.hpp;fp=boost%2Frandom%2Fshuffle_output.hpp;h=44b823f5733bf72abfc5232249ea4cab47bdd587;hp=f06f462104012a00f6a6dbac5e5441c48bfb65f7;hb=2d71eb92104693ca9baa5a2e1c23eeca776d8fd3;hpb=da57529b92adbb7ae74a89861cb39fb35ac7c62d diff --git a/boost/random/shuffle_output.hpp b/boost/random/shuffle_output.hpp index f06f462..44b823f 100644 --- a/boost/random/shuffle_output.hpp +++ b/boost/random/shuffle_output.hpp @@ -7,7 +7,7 @@ * * See http://www.boost.org for most recent version including documentation. * - * $Id: shuffle_output.hpp 60755 2010-03-22 00:45:06Z steven_watanabe $ + * $Id: shuffle_output.hpp 71018 2011-04-05 21:27:52Z steven_watanabe $ * * Revision history * 2001-02-18 moved to individual header files @@ -16,219 +16,36 @@ #ifndef BOOST_RANDOM_SHUFFLE_OUTPUT_HPP #define BOOST_RANDOM_SHUFFLE_OUTPUT_HPP -#include -#include // std::copy -#include -#include -#include -#include -#include -#include +#include namespace boost { namespace random { -/** - * Instatiations of class template shuffle_output model a - * \pseudo_random_number_generator. It mixes the output - * of some (usually \linear_congruential) \uniform_random_number_generator - * to get better statistical properties. - * The algorithm is described in - * - * @blockquote - * "Improving a poor random number generator", Carter Bays - * and S.D. Durham, ACM Transactions on Mathematical Software, - * Vol 2, No. 1, March 1976, pp. 59-64. - * http://doi.acm.org/10.1145/355666.355670 - * @endblockquote - * - * The output of the base generator is buffered in an array of - * length k. Every output X(n) has a second role: It gives an - * index into the array where X(n+1) will be retrieved. Used - * array elements are replaced with fresh output from the base - * generator. - * - * Template parameters are the base generator and the array - * length k, which should be around 100. The template parameter - * val is the validation value checked by validation. - */ -template -class shuffle_output +/// \cond + +template +class shuffle_output : public shuffle_order_engine { + typedef shuffle_order_engine base_t; + typedef typename base_t::result_type result_type; public: - typedef UniformRandomNumberGenerator base_type; - typedef typename base_type::result_type result_type; - - BOOST_STATIC_CONSTANT(bool, has_fixed_range = false); - BOOST_STATIC_CONSTANT(int, buffer_size = k); - - /** - * Constructs a @c shuffle_output generator by invoking the - * default constructor of the base generator. - * - * Complexity: Exactly k+1 invocations of the base generator. - */ - shuffle_output() : _rng() { init(); } -#if defined(BOOST_MSVC) && _MSC_VER < 1300 - // MSVC does not implicitly generate the copy constructor here - shuffle_output(const shuffle_output & x) - : _rng(x._rng), y(x.y) { std::copy(x.v, x.v+k, v); } -#endif - /** - * Constructs a shuffle_output generator by invoking the one-argument - * constructor of the base generator with the parameter seed. - * - * Complexity: Exactly k+1 invocations of the base generator. - */ - template - explicit shuffle_output(T s) : _rng(s) { init(); } - /** - * Constructs a shuffle_output generator by using a copy - * of the provided generator. - * - * Precondition: The template argument UniformRandomNumberGenerator - * shall denote a CopyConstructible type. - * - * Complexity: Exactly k+1 invocations of the base generator. - */ - explicit shuffle_output(const base_type & rng) : _rng(rng) { init(); } - template shuffle_output(It& first, It last) - : _rng(first, last) { init(); } - void seed() { _rng.seed(); init(); } - /** - * Invokes the one-argument seed method of the base generator - * with the parameter seed and re-initializes the internal buffer array. - * - * Complexity: Exactly k+1 invocations of the base generator. - */ - template - void seed(T s) { _rng.seed(s); init(); } - template void seed(It& first, It last) - { - _rng.seed(first, last); - init(); - } - - const base_type& base() const { return _rng; } - - result_type operator()() { - // calculating the range every time may seem wasteful. However, this - // makes the information locally available for the optimizer. - result_type range = (max)()-(min)()+1; - int j = k*(y-(min)())/range; - // assert(0 <= j && j < k); - y = v[j]; - v[j] = _rng(); - return y; - } - - result_type min BOOST_PREVENT_MACRO_SUBSTITUTION () const { return (_rng.min)(); } - result_type max BOOST_PREVENT_MACRO_SUBSTITUTION () const { return (_rng.max)(); } - static bool validation(result_type x) { return val == x; } - -#ifndef BOOST_NO_OPERATORS_IN_NAMESPACE - -#ifndef BOOST_RANDOM_NO_STREAM_OPERATORS - template - friend std::basic_ostream& - operator<<(std::basic_ostream& os, const shuffle_output& s) - { - os << s._rng << " " << s.y << " "; - for(int i = 0; i < s.buffer_size; ++i) - os << s.v[i] << " "; - return os; - } - - template - friend std::basic_istream& - operator>>(std::basic_istream& is, shuffle_output& s) - { - is >> s._rng >> std::ws >> s.y >> std::ws; - for(int i = 0; i < s.buffer_size; ++i) - is >> s.v[i] >> std::ws; - return is; - } -#endif - - friend bool operator==(const shuffle_output& x, const shuffle_output& y) - { return x._rng == y._rng && x.y == y.y && std::equal(x.v, x.v+k, y.v); } - friend bool operator!=(const shuffle_output& x, const shuffle_output& y) - { return !(x == y); } -#else - // Use a member function; Streamable concept not supported. - bool operator==(const shuffle_output& rhs) const - { return _rng == rhs._rng && y == rhs.y && std::equal(v, v+k, rhs.v); } - bool operator!=(const shuffle_output& rhs) const - { return !(*this == rhs); } -#endif -private: - void init() - { -#ifndef BOOST_NO_LIMITS_COMPILE_TIME_CONSTANTS - BOOST_STATIC_ASSERT(std::numeric_limits::is_integer); -#endif - result_type range = (max)()-(min)(); - assert(range > 0); // otherwise there would be little choice - if(static_cast(k * range) < - static_cast(range)) // not a sufficient condition - // likely overflow with bucket number computation - assert(!"overflow will occur"); - - // we cannot use std::generate, because it uses pass-by-value for _rng - for(result_type * p = v; p != v+k; ++p) - *p = _rng(); - y = _rng(); - } - - base_type _rng; - result_type v[k]; - result_type y; + shuffle_output() {} + template + shuffle_output(T& arg) : base_t(arg) {} + template + shuffle_output(const T& arg) : base_t(arg) {} + template + shuffle_output(It& first, It last) : base_t(first, last) {} + result_type min BOOST_PREVENT_MACRO_SUBSTITUTION () + { return (this->base().min)(); } + result_type max BOOST_PREVENT_MACRO_SUBSTITUTION () + { return (this->base().max)(); } }; -#ifndef BOOST_NO_INCLASS_MEMBER_INITIALIZATION -// A definition is required even for integral static constants -template -const bool shuffle_output::has_fixed_range; - -template -const int shuffle_output::buffer_size; -#endif - -} // namespace random - -// validation by experiment from Harry Erwin's generator.h (private e-mail) -/** - * According to Harry Erwin (private e-mail), the specialization - * @c kreutzer1986 was suggested in: - * - * @blockquote - * "System Simulation: Programming Styles and Languages (International - * Computer Science Series)", Wolfgang Kreutzer, Addison-Wesley, December 1986. - * @endblockquote - */ -typedef random::shuffle_output< - random::linear_congruential, - 97, 139726> kreutzer1986; - +/// \endcond -} // namespace boost +} +} #endif // BOOST_RANDOM_SHUFFLE_OUTPUT_HPP