williamr@2: /* boost random/shuffle_output.hpp header file williamr@2: * williamr@2: * Copyright Jens Maurer 2000-2001 williamr@2: * Distributed under the Boost Software License, Version 1.0. (See williamr@2: * accompanying file LICENSE_1_0.txt or copy at williamr@2: * http://www.boost.org/LICENSE_1_0.txt) williamr@2: * williamr@2: * See http://www.boost.org for most recent version including documentation. williamr@2: * williamr@2: * $Id: shuffle_output.hpp,v 1.10 2005/08/25 16:27:22 johnmaddock Exp $ williamr@2: * williamr@2: * Revision history williamr@2: * 2001-02-18 moved to individual header files williamr@2: */ williamr@2: williamr@2: #ifndef BOOST_RANDOM_SHUFFLE_OUTPUT_HPP williamr@2: #define BOOST_RANDOM_SHUFFLE_OUTPUT_HPP williamr@2: williamr@2: #include williamr@2: #include // std::copy williamr@2: #include williamr@2: #include williamr@2: #include williamr@2: #include williamr@2: #include williamr@2: #include williamr@2: williamr@2: namespace boost { williamr@2: namespace random { williamr@2: williamr@2: // Carter Bays and S.D. Durham 1979 williamr@2: template williamr@2: class shuffle_output williamr@2: { williamr@2: public: williamr@2: typedef UniformRandomNumberGenerator base_type; williamr@2: typedef typename base_type::result_type result_type; williamr@2: williamr@2: BOOST_STATIC_CONSTANT(bool, has_fixed_range = false); williamr@2: BOOST_STATIC_CONSTANT(int, buffer_size = k); williamr@2: williamr@2: shuffle_output() : _rng() { init(); } williamr@2: #if defined(BOOST_MSVC) && _MSC_VER < 1300 williamr@2: // MSVC does not implicitly generate the copy constructor here williamr@2: shuffle_output(const shuffle_output & x) williamr@2: : _rng(x._rng), y(x.y) { std::copy(x.v, x.v+k, v); } williamr@2: #endif williamr@2: template williamr@2: explicit shuffle_output(T seed) : _rng(seed) { init(); } williamr@2: explicit shuffle_output(const base_type & rng) : _rng(rng) { init(); } williamr@2: template shuffle_output(It& first, It last) williamr@2: : _rng(first, last) { init(); } williamr@2: void seed() { _rng.seed(); init(); } williamr@2: template williamr@2: void seed(T s) { _rng.seed(s); init(); } williamr@2: template void seed(It& first, It last) williamr@2: { williamr@2: _rng.seed(first, last); williamr@2: init(); williamr@2: } williamr@2: williamr@2: const base_type& base() const { return _rng; } williamr@2: williamr@2: result_type operator()() { williamr@2: // calculating the range every time may seem wasteful. However, this williamr@2: // makes the information locally available for the optimizer. williamr@2: result_type range = (max)()-(min)()+1; williamr@2: int j = k*(y-(min)())/range; williamr@2: // assert(0 <= j && j < k); williamr@2: y = v[j]; williamr@2: v[j] = _rng(); williamr@2: return y; williamr@2: } williamr@2: williamr@2: result_type min BOOST_PREVENT_MACRO_SUBSTITUTION () const { return (_rng.min)(); } williamr@2: result_type max BOOST_PREVENT_MACRO_SUBSTITUTION () const { return (_rng.max)(); } williamr@2: static bool validation(result_type x) { return val == x; } williamr@2: williamr@2: #ifndef BOOST_NO_OPERATORS_IN_NAMESPACE williamr@2: williamr@2: #ifndef BOOST_NO_MEMBER_TEMPLATE_FRIENDS williamr@2: template williamr@2: friend std::basic_ostream& williamr@2: operator<<(std::basic_ostream& os, const shuffle_output& s) williamr@2: { williamr@2: os << s._rng << " " << s.y << " "; williamr@2: for(int i = 0; i < s.buffer_size; ++i) williamr@2: os << s.v[i] << " "; williamr@2: return os; williamr@2: } williamr@2: williamr@2: template williamr@2: friend std::basic_istream& williamr@2: operator>>(std::basic_istream& is, shuffle_output& s) williamr@2: { williamr@2: is >> s._rng >> std::ws >> s.y >> std::ws; williamr@2: for(int i = 0; i < s.buffer_size; ++i) williamr@2: is >> s.v[i] >> std::ws; williamr@2: return is; williamr@2: } williamr@2: #endif williamr@2: williamr@2: friend bool operator==(const shuffle_output& x, const shuffle_output& y) williamr@2: { return x._rng == y._rng && x.y == y.y && std::equal(x.v, x.v+k, y.v); } williamr@2: friend bool operator!=(const shuffle_output& x, const shuffle_output& y) williamr@2: { return !(x == y); } williamr@2: #else williamr@2: // Use a member function; Streamable concept not supported. williamr@2: bool operator==(const shuffle_output& rhs) const williamr@2: { return _rng == rhs._rng && y == rhs.y && std::equal(v, v+k, rhs.v); } williamr@2: bool operator!=(const shuffle_output& rhs) const williamr@2: { return !(*this == rhs); } williamr@2: #endif williamr@2: private: williamr@2: void init() williamr@2: { williamr@2: #ifndef BOOST_NO_LIMITS_COMPILE_TIME_CONSTANTS williamr@2: BOOST_STATIC_ASSERT(std::numeric_limits::is_integer); williamr@2: #endif williamr@2: result_type range = (max)()-(min)(); williamr@2: assert(range > 0); // otherwise there would be little choice williamr@2: if(static_cast(k * range) < williamr@2: static_cast(range)) // not a sufficient condition williamr@2: // likely overflow with bucket number computation williamr@2: assert(!"overflow will occur"); williamr@2: williamr@2: // we cannot use std::generate, because it uses pass-by-value for _rng williamr@2: for(result_type * p = v; p != v+k; ++p) williamr@2: *p = _rng(); williamr@2: y = _rng(); williamr@2: } williamr@2: williamr@2: base_type _rng; williamr@2: result_type v[k]; williamr@2: result_type y; williamr@2: }; williamr@2: williamr@2: #ifndef BOOST_NO_INCLASS_MEMBER_INITIALIZATION williamr@2: // A definition is required even for integral static constants williamr@2: template williamr@2: const bool shuffle_output::has_fixed_range; williamr@2: williamr@2: template williamr@2: const int shuffle_output::buffer_size; williamr@2: #endif williamr@2: williamr@2: } // namespace random williamr@2: williamr@2: // validation by experiment from Harry Erwin's generator.h (private e-mail) williamr@2: typedef random::shuffle_output< williamr@2: random::linear_congruential, williamr@2: 97, 139726> kreutzer1986; williamr@2: williamr@2: williamr@2: } // namespace boost williamr@2: williamr@2: #endif // BOOST_RANDOM_SHUFFLE_OUTPUT_HPP