[Boost-commit] svn:boost r63327 - in trunk: boost/random libs/random/doc libs/random/test

Subject: [Boost-commit] svn:boost r63327 - in trunk: boost/random libs/random/doc libs/random/test
From: steven_at_[hidden]
Date: 2010-06-25 17:23:21

Author: steven_watanabe
Date: 2010-06-25 17:23:20 EDT (Fri, 25 Jun 2010)
New Revision: 63327
URL: http://svn.boost.org/trac/boost/changeset/63327

Log:
Sync shuffle_order_engine with C++0x.
Added:
   trunk/boost/random/shuffle_order.hpp
      - copied, changed from r63270, /trunk/boost/random/shuffle_output.hpp
Text files modified: 
   trunk/boost/random/shuffle_order.hpp  |   363 ++++++++++++++++++++++----------------- 
   trunk/boost/random/shuffle_output.hpp |   215 -----------------------                 
   trunk/libs/random/doc/Jamfile.v2      |     3                                         
   trunk/libs/random/doc/generators.qbk  |     1                                         
   trunk/libs/random/doc/random.qbk      |     3                                         
   trunk/libs/random/test/validate.cpp   |     5                                         
   6 files changed, 215 insertions(+), 375 deletions(-)

Copied: trunk/boost/random/shuffle_order.hpp (from r63270, /trunk/boost/random/shuffle_output.hpp)
==============================================================================
--- /trunk/boost/random/shuffle_output.hpp	(original)
+++ trunk/boost/random/shuffle_order.hpp	2010-06-25 17:23:20 EDT (Fri, 25 Jun 2010)
@@ -1,6 +1,7 @@
-/* boost random/shuffle_output.hpp header file
+/* boost random/shuffle_order.hpp header file
  *
  * Copyright Jens Maurer 2000-2001
+ * Copyright Steven Watanabe 2010
  * Distributed under the Boost Software License, Version 1.0. (See
  * accompanying file LICENSE_1_0.txt or copy at
  * http://www.boost.org/LICENSE_1_0.txt)
@@ -9,12 +10,10 @@
  *
  * $Id$
  *
- * Revision history
- *  2001-02-18  moved to individual header files
  */
 
-#ifndef BOOST_RANDOM_SHUFFLE_OUTPUT_HPP
-#define BOOST_RANDOM_SHUFFLE_OUTPUT_HPP
+#ifndef BOOST_RANDOM_SHUFFLE_ORDER_HPP
+#define BOOST_RANDOM_SHUFFLE_ORDER_HPP
 
 #include <iostream>
 #include <algorithm>     // std::copy
@@ -23,13 +22,18 @@
 #include <boost/limits.hpp>
 #include <boost/static_assert.hpp>
 #include <boost/cstdint.hpp>
+#include <boost/random/detail/operators.hpp>
+#include <boost/random/detail/seed.hpp>
+#include <boost/random/detail/signed_unsigned_tools.hpp>
 #include <boost/random/linear_congruential.hpp>
 
+#include <boost/random/detail/disable_warnings.hpp>
+
 namespace boost {
 namespace random {
 
 /**
- * Instatiations of class template shuffle_output model a
+ * Instatiations of class template @c shuffle_order_engine model a
  * \pseudo_random_number_generator. It mixes the output
  * of some (usually \linear_congruential_engine)
  * \uniform_random_number_generator to get better statistical properties.
@@ -49,171 +53,205 @@
  * 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.
+ * length k, which should be around 100.
  */
-template<class UniformRandomNumberGenerator, int k,
-#ifndef BOOST_NO_DEPENDENT_TYPES_IN_TEMPLATE_VALUE_PARAMETERS
-  typename UniformRandomNumberGenerator::result_type 
-#else
-  uint32_t
-#endif
-  val = 0>
-class shuffle_output
+template<class UniformRandomNumberGenerator, std::size_t k>
+class shuffle_order_engine
 {
 public:
-  typedef UniformRandomNumberGenerator base_type;
-  typedef typename base_type::result_type result_type;
+    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);
+    BOOST_STATIC_CONSTANT(bool, has_fixed_range = false);
+    BOOST_STATIC_CONSTANT(std::size_t, buffer_size = k);
+    BOOST_STATIC_CONSTANT(std::size_t, table_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<class T>
-  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<class It> 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<class T>
-  void seed(T s) { _rng.seed(s); init(); }
-  template<class It> 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<class CharT, class Traits>
-  friend std::basic_ostream<CharT,Traits>&
-  operator<<(std::basic_ostream<CharT,Traits>& 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<class CharT, class Traits>
-  friend std::basic_istream<CharT,Traits>&
-  operator>>(std::basic_istream<CharT,Traits>& 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;
-  }
+    BOOST_STATIC_ASSERT(std::numeric_limits<result_type>::is_integer);
+    BOOST_STATIC_ASSERT(k > 0);
+
+    /**
+     * Constructs a @c shuffle_order_engine by invoking the
+     * default constructor of the base generator.
+     *
+     * Complexity: Exactly k+1 invocations of the base generator.
+     */
+    shuffle_order_engine() : _rng() { init(); }
+    /**
+     * Constructs a @c shuffle_output_engine by invoking the one-argument
+     * constructor of the base generator with the parameter seed.
+     *
+     * Complexity: Exactly k+1 invocations of the base generator.
+     */
+    BOOST_RANDOM_DETAIL_ARITHMETIC_CONSTRUCTOR(shuffle_order_engine,
+                                               result_type, s)
+    { _rng.seed(s); init(); }
+    BOOST_RANDOM_DETAIL_SEED_SEQ_CONSTRUCTOR(shuffle_order_engine, SeedSeq, seq)
+    { _rng.seed(seq); init(); }
+    /**
+     * Constructs a @c shuffle_output_engine 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_order_engine(const base_type & rng) : _rng(rng) { init(); }
+
+#ifndef BOOST_NO_RVALUE_REFERENCES
+    explicit shuffle_order_engine(base_type&& rng) : _rng(rng) { init(); }
 #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); }
+    template<class It> shuffle_order_engine(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<class T>
+    void seed(T s) { _rng.seed(s); init(); }
+    template<class It> 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.
+        typedef typename make_unsigned<result_type>::type base_unsigned;
+        const base_unsigned brange =
+            detail::subtract<result_type>()((max)(), (min)());
+        const base_unsigned off =
+            detail::subtract<result_type>()(y, (min)());
+
+        base_unsigned j;
+        if(k == 1) {
+            j = 0;
+        } else if(brange < (std::numeric_limits<base_unsigned>::max)() / k) {
+            // try to do it in the native type if we know that it won't
+            // overflow
+            j = k * off / (brange + 1);
+        }
+#if !defined(BOOST_NO_INT64_T)
+        else if(brange < (std::numeric_limits<uint64_t>::max)() / k) {
+            // Otherwise try to use uint64_t
+            j = static_cast<base_unsigned>(
+                static_cast<uint64_t>(off) * k /
+                (static_cast<uint64_t>(brange) + 1));
+        }
 #endif
-private:
-  void init()
-  {
-#ifndef BOOST_NO_LIMITS_COMPILE_TIME_CONSTANTS
-    BOOST_STATIC_ASSERT(std::numeric_limits<result_type>::is_integer);
+        else {
+            // If all else fails, fall back to a general algorithm that
+            // never overflows.
+
+            const base_unsigned r_mod_k = ((brange % k) + 1) % k;
+            const base_unsigned bucket_size = (brange - k + 1)/k + 1;
+            // if the candidate from the first round is zero, we're safe.
+            base_unsigned candidate = 0;
+            base_unsigned old_candidate;
+            base_unsigned error = 0;
+            do {
+                old_candidate = candidate;
+                candidate = (off - error) / bucket_size;
+                base_unsigned possible = (off - error + 1) / bucket_size;
+                error = possible - possible * (k - r_mod_k) / k;
+            } while(old_candidate != candidate);
+
+            j = candidate;
+
+            // Would cause overflow
+            // assert(j == uint64_t(off)*k/(uint64_t(brange)+1));
+        }
+        // assert(0 <= j && j < k);
+        y = v[j];
+        v[j] = _rng();
+        return y;
+    }
+
+#ifndef BOOST_NO_LONG_LONG
+    /** Advances the generator by z steps. */
+    void discard(boost::ulong_long_type z)
+    {
+        for(boost::ulong_long_type j = 0; j < z; ++j) {
+            (*this)();
+        }
+    }
 #endif
-    result_type range = (max)()-(min)();
-    assert(range > 0);      // otherwise there would be little choice
-    if(static_cast<unsigned long>(k * range) < 
-       static_cast<unsigned long>(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;
+
+    /** Fills a range with pseudo-random values. */
+    template<class Iter>
+    void generate(Iter first, Iter last)
+    {
+        for(; first != last; ++first) {
+            *first = (*this)();
+        }
+    }
+
+    /** Returns the smallest value that the generator can produce. */
+    static result_type min BOOST_PREVENT_MACRO_SUBSTITUTION ()
+    { return (base_type::min)(); }
+    /** Returns the largest value that the generator can produce. */
+    static result_type max BOOST_PREVENT_MACRO_SUBSTITUTION ()
+    { return (base_type::max)(); }
+
+    /** Writes a @c shuffle_order_engine to a @c std::ostream. */
+    BOOST_RANDOM_DETAIL_OSTREAM_OPERATOR(os, shuffle_order_engine, s)
+    {
+        os << s._rng;
+        for(int i = 0; i < k; ++i)
+            os << ' ' << s.v[i];
+        os << ' ' << s.y;
+        return os;
+    }
+
+    /** Reads a @c shuffle_order_engine from a @c std::istream. */
+    BOOST_RANDOM_DETAIL_ISTREAM_OPERATOR(is, shuffle_order_engine, s)
+    {
+        is >> s._rng;
+        for(int i = 0; i < k; ++i)
+            is >> std::ws >> s.v[i];
+        is >> std::ws >> s.y;
+        return is;
+    }
+
+    /** Returns true if the two generators will produce identical sequences. */
+    BOOST_RANDOM_DETAIL_EQUALITY_OPERATOR(shuffle_order_engine, x, y)
+    { return x._rng == y._rng && x.y == y.y && std::equal(x.v, x.v+k, y.v); }
+    /** Returns true if the two generators will produce different sequences. */
+    BOOST_RANDOM_DETAIL_INEQUALITY_OPERATOR(shuffle_order_engine)
+
+private:
+
+    /// \cond
+
+    void init()
+    {
+        // 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();
+    }
+
+    /// \endcond
+
+    base_type _rng;
+    result_type v[k];
+    result_type y;
 };
 
 #ifndef BOOST_NO_INCLASS_MEMBER_INITIALIZATION
 //  A definition is required even for integral static constants
-template<class UniformRandomNumberGenerator, int k, 
-#ifndef BOOST_NO_DEPENDENT_TYPES_IN_TEMPLATE_VALUE_PARAMETERS
-  typename UniformRandomNumberGenerator::result_type 
-#else
-  uint32_t
-#endif
-  val>
-const bool shuffle_output<UniformRandomNumberGenerator, k, val>::has_fixed_range;
-
-template<class UniformRandomNumberGenerator, int k, 
-#ifndef BOOST_NO_DEPENDENT_TYPES_IN_TEMPLATE_VALUE_PARAMETERS
-  typename UniformRandomNumberGenerator::result_type 
-#else
-  uint32_t
-#endif
-  val>
-const int shuffle_output<UniformRandomNumberGenerator, k, val>::buffer_size;
+template<class URNG, std::size_t k>
+const bool shuffle_order_engine<URNG, k>::has_fixed_range;
+template<class URNG, std::size_t k>
+const std::size_t shuffle_order_engine<URNG, k>::table_size;
+template<class URNG, std::size_t k>
+const std::size_t shuffle_order_engine<URNG, k>::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
@@ -224,11 +262,18 @@
  * Computer Science Series)", Wolfgang Kreutzer, Addison-Wesley, December 1986.
  * @endblockquote
  */
-typedef random::shuffle_output<
-    random::linear_congruential_engine<uint32_t, 1366, 150889, 714025>,
-  97, 139726> kreutzer1986;
+typedef shuffle_order_engine<
+    linear_congruential_engine<uint32_t, 1366, 150889, 714025>,
+    97> kreutzer1986;
+
+typedef shuffle_order_engine<minstd_rand0, 256> knuth_b;
 
+} // namespace random
+
+using random::kreutzer1986;
 
 } // namespace boost
 
+#include <boost/random/detail/enable_warnings.hpp>
+
 #endif // BOOST_RANDOM_SHUFFLE_OUTPUT_HPP

Modified: trunk/boost/random/shuffle_output.hpp
==============================================================================
--- trunk/boost/random/shuffle_output.hpp	(original)
+++ trunk/boost/random/shuffle_output.hpp	2010-06-25 17:23:20 EDT (Fri, 25 Jun 2010)
@@ -16,219 +16,6 @@
 #ifndef BOOST_RANDOM_SHUFFLE_OUTPUT_HPP
 #define BOOST_RANDOM_SHUFFLE_OUTPUT_HPP
 
-#include <iostream>
-#include <algorithm>     // std::copy
-#include <cassert>
-#include <boost/config.hpp>
-#include <boost/limits.hpp>
-#include <boost/static_assert.hpp>
-#include <boost/cstdint.hpp>
-#include <boost/random/linear_congruential.hpp>
-
-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_engine)
- * \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 UniformRandomNumberGenerator, int k,
-#ifndef BOOST_NO_DEPENDENT_TYPES_IN_TEMPLATE_VALUE_PARAMETERS
-  typename UniformRandomNumberGenerator::result_type 
-#else
-  uint32_t
-#endif
-  val = 0>
-class shuffle_output
-{
-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<class T>
-  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<class It> 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<class T>
-  void seed(T s) { _rng.seed(s); init(); }
-  template<class It> 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<class CharT, class Traits>
-  friend std::basic_ostream<CharT,Traits>&
-  operator<<(std::basic_ostream<CharT,Traits>& 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<class CharT, class Traits>
-  friend std::basic_istream<CharT,Traits>&
-  operator>>(std::basic_istream<CharT,Traits>& 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<result_type>::is_integer);
-#endif
-    result_type range = (max)()-(min)();
-    assert(range > 0);      // otherwise there would be little choice
-    if(static_cast<unsigned long>(k * range) < 
-       static_cast<unsigned long>(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;
-};
-
-#ifndef BOOST_NO_INCLASS_MEMBER_INITIALIZATION
-//  A definition is required even for integral static constants
-template<class UniformRandomNumberGenerator, int k, 
-#ifndef BOOST_NO_DEPENDENT_TYPES_IN_TEMPLATE_VALUE_PARAMETERS
-  typename UniformRandomNumberGenerator::result_type 
-#else
-  uint32_t
-#endif
-  val>
-const bool shuffle_output<UniformRandomNumberGenerator, k, val>::has_fixed_range;
-
-template<class UniformRandomNumberGenerator, int k, 
-#ifndef BOOST_NO_DEPENDENT_TYPES_IN_TEMPLATE_VALUE_PARAMETERS
-  typename UniformRandomNumberGenerator::result_type 
-#else
-  uint32_t
-#endif
-  val>
-const int shuffle_output<UniformRandomNumberGenerator, k, val>::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_engine<uint32_t, 1366, 150889, 714025>,
-  97, 139726> kreutzer1986;
-
-
-} // namespace boost
+#include <boost/random/shuffle_order.hpp>
 
 #endif // BOOST_RANDOM_SHUFFLE_OUTPUT_HPP

Modified: trunk/libs/random/doc/Jamfile.v2
==============================================================================
--- trunk/libs/random/doc/Jamfile.v2	(original)
+++ trunk/libs/random/doc/Jamfile.v2	2010-06-25 17:23:20 EDT (Fri, 25 Jun 2010)
@@ -34,7 +34,8 @@
     poisson_distribution
     random_number_generator
     ranlux
-    shuffle_output
+    shuffle_order
+    # shuffle_output
     subtract_with_carry
     triangle_distribution
     uniform_01

Modified: trunk/libs/random/doc/generators.qbk
==============================================================================
--- trunk/libs/random/doc/generators.qbk	(original)
+++ trunk/libs/random/doc/generators.qbk	2010-06-25 17:23:20 EDT (Fri, 25 Jun 2010)
@@ -47,6 +47,7 @@
   [[__minstd_rand] [2[sup 31]-2] [`sizeof(int32_t)`] [[minstd_rand_speed]] [-]]
   [[__rand48][2[sup 48]-1] [`sizeof(uint64_t)`] [[rand48_speed]] [-]]
   [[__ecuyer1988] [approx. 2[sup 61]] [`2*sizeof(int32_t)`] [[ecuyer_combined_speed]] [-]]
+  [[__knuth_b] [?] [`257*sizeof(uint32_t)`] [] [-]]
   [[__kreutzer1986] [?] [`1368*sizeof(uint32_t)`] [[kreutzer1986_speed]] [-]]
   [[__taus88] [~2[sup 88]] [`3*sizeof(uint32_t)`] [[taus88_speed]] [-]]
   [[__hellekalek1995] [2[sup 31]-1] [`sizeof(int32_t)`] [[hellekalek1995__inversive__speed]] [good uniform distribution in several dimensions]]

Modified: trunk/libs/random/doc/random.qbk
==============================================================================
--- trunk/libs/random/doc/random.qbk	(original)
+++ trunk/libs/random/doc/random.qbk	2010-06-25 17:23:20 EDT (Fri, 25 Jun 2010)
@@ -34,7 +34,8 @@
 [def __minstd_rand [classref boost::random::minstd_rand minstd_rand]]
 [def __rand48 [classref boost::random::rand48 rand48]]
 [def __ecuyer1988 [classref boost::ecuyer1988 ecuyer1988]]
-[def __kreutzer1986 [classref boost::kreutzer1986 kreutzer1986]]
+[def __kreutzer1986 [classref boost::random::kreutzer1986 kreutzer1986]]
+[def __knuth_b [classref boost::random::knuth_b knuth_b]]
 [def __taus88 [classref boost::taus88 taus88]]
 [def __hellekalek1995 [classref boost::hellekalek1995 hellekalek1995]]
 [def __mt11213b [classref boost::random::mt11213b mt11213b]]

Modified: trunk/libs/random/test/validate.cpp
==============================================================================
--- trunk/libs/random/test/validate.cpp	(original)
+++ trunk/libs/random/test/validate.cpp	2010-06-25 17:23:20 EDT (Fri, 25 Jun 2010)
@@ -50,6 +50,7 @@
 bool check_(unsigned long x, const boost::mt19937&) { return x == 4123659995U; }
 
 #if !defined(BOOST_NO_INT64_T) && !defined(BOOST_NO_INTEGRAL_INT64_T)
+// validation from the C++0x draft (n3090)
 bool check_(boost::uint64_t x, const boost::mt19937_64&) { return x == UINT64_C(9981545732273789042); }
 #endif
 
@@ -73,6 +74,9 @@
 // validation by experiment from Harry Erwin's generator.h (private e-mail)
 bool check_(unsigned int x, const boost::kreutzer1986&) { return x == 139726; }
 
+// validation from the C++0x draft (n3090)
+bool check_(unsigned int x, const boost::random::knuth_b&) { return x == 1112339016; }
+
 bool check_(double x, const boost::lagged_fibonacci607&) { return std::abs(x-0.401269) < 1e-5; }
 
 // principal operation validated with CLHEP, values by experiment
@@ -126,6 +130,7 @@
   validate("mt19937_64", mt19937_64());
 #endif
   validate("kreutzer1986", kreutzer1986());
+  validate("knuth_b", boost::random::knuth_b());
   validate("ranlux3", ranlux3());
   validate("ranlux4", ranlux4());
   validate("ranlux3_01", ranlux3_01());