1 files changed, 367 insertions, 0 deletions
diff --git a/3rdParty/Boost/src/boost/random/mersenne_twister.hpp b/3rdParty/Boost/src/boost/random/mersenne_twister.hpp
new file mode 100644
index 0000000..fa80aa6
--- /dev/null
+++ b/3rdParty/Boost/src/boost/random/mersenne_twister.hpp
@@ -0,0 +1,367 @@
+/* boost random/mersenne_twister.hpp header file
+ *
+ * Copyright Jens Maurer 2000-2001
+ * 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)
+ *
+ * See http://www.boost.org for most recent version including documentation.
+ *
+ * $Id: mersenne_twister.hpp 60755 2010-03-22 00:45:06Z steven_watanabe $
+ *
+ * Revision history
+ *  2001-02-18  moved to individual header files
+ */
+
+#ifndef BOOST_RANDOM_MERSENNE_TWISTER_HPP
+#define BOOST_RANDOM_MERSENNE_TWISTER_HPP
+
+#include <iostream>
+#include <algorithm>     // std::copy
+#include <stdexcept>
+#include <boost/config.hpp>
+#include <boost/limits.hpp>
+#include <boost/static_assert.hpp>
+#include <boost/integer_traits.hpp>
+#include <boost/cstdint.hpp>
+#include <boost/random/linear_congruential.hpp>
+#include <boost/detail/workaround.hpp>
+#include <boost/random/detail/config.hpp>
+#include <boost/random/detail/ptr_helper.hpp>
+#include <boost/random/detail/seed.hpp>
+
+namespace boost {
+namespace random {
+
+/**
+ * Instantiations of class template mersenne_twister model a
+ * \pseudo_random_number_generator. It uses the algorithm described in
+ *
+ *  @blockquote
+ *  "Mersenne Twister: A 623-dimensionally equidistributed uniform
+ *  pseudo-random number generator", Makoto Matsumoto and Takuji Nishimura,
+ *  ACM Transactions on Modeling and Computer Simulation: Special Issue on
+ *  Uniform Random Number Generation, Vol. 8, No. 1, January 1998, pp. 3-30. 
+ *  @endblockquote
+ *
+ * @xmlnote
+ * The boost variant has been implemented from scratch and does not
+ * derive from or use mt19937.c provided on the above WWW site. However, it
+ * was verified that both produce identical output.
+ * @endxmlnote
+ *
+ * The seeding from an integer was changed in April 2005 to address a
+ * <a href="http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/MT2002/emt19937ar.html">weakness</a>.
+ * 
+ * The quality of the generator crucially depends on the choice of the
+ * parameters.  User code should employ one of the sensibly parameterized
+ * generators such as \mt19937 instead.
+ *
+ * The generator requires considerable amounts of memory for the storage of
+ * its state array. For example, \mt11213b requires about 1408 bytes and
+ * \mt19937 requires about 2496 bytes.
+ */
+template<class UIntType, int w, int n, int m, int r, UIntType a, int u,
+  int s, UIntType b, int t, UIntType c, int l, UIntType val>
+class mersenne_twister
+{
+public:
+  typedef UIntType result_type;
+  BOOST_STATIC_CONSTANT(int, word_size = w);
+  BOOST_STATIC_CONSTANT(int, state_size = n);
+  BOOST_STATIC_CONSTANT(int, shift_size = m);
+  BOOST_STATIC_CONSTANT(int, mask_bits = r);
+  BOOST_STATIC_CONSTANT(UIntType, parameter_a = a);
+  BOOST_STATIC_CONSTANT(int, output_u = u);
+  BOOST_STATIC_CONSTANT(int, output_s = s);
+  BOOST_STATIC_CONSTANT(UIntType, output_b = b);
+  BOOST_STATIC_CONSTANT(int, output_t = t);
+  BOOST_STATIC_CONSTANT(UIntType, output_c = c);
+  BOOST_STATIC_CONSTANT(int, output_l = l);
+
+  BOOST_STATIC_CONSTANT(bool, has_fixed_range = false);
+  
+  /**
+   * Constructs a @c mersenne_twister and calls @c seed().
+   */
+  mersenne_twister() { seed(); }
+
+  /**
+   * Constructs a @c mersenne_twister and calls @c seed(value).
+   */
+  BOOST_RANDOM_DETAIL_ARITHMETIC_CONSTRUCTOR(mersenne_twister, UIntType, value)
+  { seed(value); }
+  template<class It> mersenne_twister(It& first, It last) { seed(first,last); }
+
+  /**
+   * Constructs a mersenne_twister and calls @c seed(gen).
+   *
+   * @xmlnote
+   * The copy constructor will always be preferred over
+   * the templated constructor.
+   * @endxmlnote
+   */
+  BOOST_RANDOM_DETAIL_GENERATOR_CONSTRUCTOR(mersenne_twister, Generator, gen)
+  { seed(gen); }
+
+  // compiler-generated copy ctor and assignment operator are fine
+
+  /** Calls @c seed(result_type(5489)). */
+  void seed() { seed(UIntType(5489)); }
+
+  /**
+   * Sets the state x(0) to v mod 2w. Then, iteratively,
+   * sets x(i) to (i + 1812433253 * (x(i-1) xor (x(i-1) rshift w-2))) mod 2<sup>w</sup>
+   * for i = 1 .. n-1. x(n) is the first value to be returned by operator().
+   */
+  BOOST_RANDOM_DETAIL_ARITHMETIC_SEED(mersenne_twister, UIntType, value)
+  {
+    // New seeding algorithm from 
+    // http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/MT2002/emt19937ar.html
+    // In the previous versions, MSBs of the seed affected only MSBs of the
+    // state x[].
+    const UIntType mask = ~0u;
+    x[0] = value & mask;
+    for (i = 1; i < n; i++) {
+      // See Knuth "The Art of Computer Programming" Vol. 2, 3rd ed., page 106
+      x[i] = (1812433253UL * (x[i-1] ^ (x[i-1] >> (w-2))) + i) & mask;
+    }
+  }
+
+  /**
+   * Sets the state of this mersenne_twister to the values
+   * returned by n invocations of gen.
+   *
+   * Complexity: Exactly n invocations of gen.
+   */
+  BOOST_RANDOM_DETAIL_GENERATOR_SEED(mersenne_twister, Generator, gen)
+  {
+#ifndef BOOST_NO_LIMITS_COMPILE_TIME_CONSTANTS
+    BOOST_STATIC_ASSERT(!std::numeric_limits<result_type>::is_signed);
+#endif
+    // I could have used std::generate_n, but it takes "gen" by value
+    for(int j = 0; j < n; j++)
+      x[j] = gen();
+    i = n;
+  }
+
+  template<class It>
+  void seed(It& first, It last)
+  {
+    int j;
+    for(j = 0; j < n && first != last; ++j, ++first)
+      x[j] = *first;
+    i = n;
+    if(first == last && j < n)
+      throw std::invalid_argument("mersenne_twister::seed");
+  }
+  
+  result_type min BOOST_PREVENT_MACRO_SUBSTITUTION () const { return 0; }
+  result_type max BOOST_PREVENT_MACRO_SUBSTITUTION () const
+  {
+    // avoid "left shift count >= with of type" warning
+    result_type res = 0;
+    for(int j = 0; j < w; ++j)
+      res |= (1u << j);
+    return res;
+  }
+
+  result_type operator()();
+  static bool validation(result_type v) { return val == v; }
+
+#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 mersenne_twister& mt)
+  {
+    for(int j = 0; j < mt.state_size; ++j)
+      os << mt.compute(j) << " ";
+    return os;
+  }
+
+  template<class CharT, class Traits>
+  friend std::basic_istream<CharT,Traits>&
+  operator>>(std::basic_istream<CharT,Traits>& is, mersenne_twister& mt)
+  {
+    for(int j = 0; j < mt.state_size; ++j)
+      is >> mt.x[j] >> std::ws;
+    // MSVC (up to 7.1) and Borland (up to 5.64) don't handle the template
+    // value parameter "n" available from the class template scope, so use
+    // the static constant with the same value
+    mt.i = mt.state_size;
+    return is;
+  }
+#endif
+
+  friend bool operator==(const mersenne_twister& x, const mersenne_twister& y)
+  {
+    for(int j = 0; j < state_size; ++j)
+      if(x.compute(j) != y.compute(j))
+        return false;
+    return true;
+  }
+
+  friend bool operator!=(const mersenne_twister& x, const mersenne_twister& y)
+  { return !(x == y); }
+#else
+  // Use a member function; Streamable concept not supported.
+  bool operator==(const mersenne_twister& rhs) const
+  {
+    for(int j = 0; j < state_size; ++j)
+      if(compute(j) != rhs.compute(j))
+        return false;
+    return true;
+  }
+
+  bool operator!=(const mersenne_twister& rhs) const
+  { return !(*this == rhs); }
+#endif
+
+private:
+  /// \cond hide_private_members
+  // returns x(i-n+index), where index is in 0..n-1
+  UIntType compute(unsigned int index) const
+  {
+    // equivalent to (i-n+index) % 2n, but doesn't produce negative numbers
+    return x[ (i + n + index) % (2*n) ];
+  }
+  void twist(int block);
+  /// \endcond
+
+  // state representation: next output is o(x(i))
+  //   x[0]  ... x[k] x[k+1] ... x[n-1]     x[n]     ... x[2*n-1]   represents
+  //  x(i-k) ... x(i) x(i+1) ... x(i-k+n-1) x(i-k-n) ... x[i(i-k-1)]
+  // The goal is to always have x(i-n) ... x(i-1) available for
+  // operator== and save/restore.
+
+  UIntType x[2*n]; 
+  int i;
+};
+
+#ifndef BOOST_NO_INCLASS_MEMBER_INITIALIZATION
+//  A definition is required even for integral static constants
+template<class UIntType, int w, int n, int m, int r, UIntType a, int u,
+  int s, UIntType b, int t, UIntType c, int l, UIntType val>
+const bool mersenne_twister<UIntType,w,n,m,r,a,u,s,b,t,c,l,val>::has_fixed_range;
+template<class UIntType, int w, int n, int m, int r, UIntType a, int u,
+  int s, UIntType b, int t, UIntType c, int l, UIntType val>
+const int mersenne_twister<UIntType,w,n,m,r,a,u,s,b,t,c,l,val>::state_size;
+template<class UIntType, int w, int n, int m, int r, UIntType a, int u,
+  int s, UIntType b, int t, UIntType c, int l, UIntType val>
+const int mersenne_twister<UIntType,w,n,m,r,a,u,s,b,t,c,l,val>::shift_size;
+template<class UIntType, int w, int n, int m, int r, UIntType a, int u,
+  int s, UIntType b, int t, UIntType c, int l, UIntType val>
+const int mersenne_twister<UIntType,w,n,m,r,a,u,s,b,t,c,l,val>::mask_bits;
+template<class UIntType, int w, int n, int m, int r, UIntType a, int u,
+  int s, UIntType b, int t, UIntType c, int l, UIntType val>
+const UIntType mersenne_twister<UIntType,w,n,m,r,a,u,s,b,t,c,l,val>::parameter_a;
+template<class UIntType, int w, int n, int m, int r, UIntType a, int u,
+  int s, UIntType b, int t, UIntType c, int l, UIntType val>
+const int mersenne_twister<UIntType,w,n,m,r,a,u,s,b,t,c,l,val>::output_u;
+template<class UIntType, int w, int n, int m, int r, UIntType a, int u,
+  int s, UIntType b, int t, UIntType c, int l, UIntType val>
+const int mersenne_twister<UIntType,w,n,m,r,a,u,s,b,t,c,l,val>::output_s;
+template<class UIntType, int w, int n, int m, int r, UIntType a, int u,
+  int s, UIntType b, int t, UIntType c, int l, UIntType val>
+const UIntType mersenne_twister<UIntType,w,n,m,r,a,u,s,b,t,c,l,val>::output_b;
+template<class UIntType, int w, int n, int m, int r, UIntType a, int u,
+  int s, UIntType b, int t, UIntType c, int l, UIntType val>
+const int mersenne_twister<UIntType,w,n,m,r,a,u,s,b,t,c,l,val>::output_t;
+template<class UIntType, int w, int n, int m, int r, UIntType a, int u,
+  int s, UIntType b, int t, UIntType c, int l, UIntType val>
+const UIntType mersenne_twister<UIntType,w,n,m,r,a,u,s,b,t,c,l,val>::output_c;
+template<class UIntType, int w, int n, int m, int r, UIntType a, int u,
+  int s, UIntType b, int t, UIntType c, int l, UIntType val>
+const int mersenne_twister<UIntType,w,n,m,r,a,u,s,b,t,c,l,val>::output_l;
+#endif
+
+/// \cond hide_private_members
+template<class UIntType, int w, int n, int m, int r, UIntType a, int u,
+  int s, UIntType b, int t, UIntType c, int l, UIntType val>
+void mersenne_twister<UIntType,w,n,m,r,a,u,s,b,t,c,l,val>::twist(int block)
+{
+  const UIntType upper_mask = (~0u) << r;
+  const UIntType lower_mask = ~upper_mask;
+
+  if(block == 0) {
+    for(int j = n; j < 2*n; j++) {
+      UIntType y = (x[j-n] & upper_mask) | (x[j-(n-1)] & lower_mask);
+      x[j] = x[j-(n-m)] ^ (y >> 1) ^ (y&1 ? a : 0);
+    }
+  } else if (block == 1) {
+    // split loop to avoid costly modulo operations
+    {  // extra scope for MSVC brokenness w.r.t. for scope
+      for(int j = 0; j < n-m; j++) {
+        UIntType y = (x[j+n] & upper_mask) | (x[j+n+1] & lower_mask);
+        x[j] = x[j+n+m] ^ (y >> 1) ^ (y&1 ? a : 0);
+      }
+    }
+    
+    for(int j = n-m; j < n-1; j++) {
+      UIntType y = (x[j+n] & upper_mask) | (x[j+n+1] & lower_mask);
+      x[j] = x[j-(n-m)] ^ (y >> 1) ^ (y&1 ? a : 0);
+    }
+    // last iteration
+    UIntType y = (x[2*n-1] & upper_mask) | (x[0] & lower_mask);
+    x[n-1] = x[m-1] ^ (y >> 1) ^ (y&1 ? a : 0);
+    i = 0;
+  }
+}
+/// \endcond
+
+template<class UIntType, int w, int n, int m, int r, UIntType a, int u,
+  int s, UIntType b, int t, UIntType c, int l, UIntType val>
+inline typename mersenne_twister<UIntType,w,n,m,r,a,u,s,b,t,c,l,val>::result_type
+mersenne_twister<UIntType,w,n,m,r,a,u,s,b,t,c,l,val>::operator()()
+{
+  if(i == n)
+    twist(0);
+  else if(i >= 2*n)
+    twist(1);
+  // Step 4
+  UIntType z = x[i];
+  ++i;
+  z ^= (z >> u);
+  z ^= ((z << s) & b);
+  z ^= ((z << t) & c);
+  z ^= (z >> l);
+  return z;
+}
+
+} // namespace random
+
+/**
+ * The specializations \mt11213b and \mt19937 are from
+ *
+ *  @blockquote
+ *  "Mersenne Twister: A 623-dimensionally equidistributed
+ *  uniform pseudo-random number generator", Makoto Matsumoto
+ *  and Takuji Nishimura, ACM Transactions on Modeling and
+ *  Computer Simulation: Special Issue on Uniform Random Number
+ *  Generation, Vol. 8, No. 1, January 1998, pp. 3-30. 
+ *  @endblockquote
+ */
+typedef random::mersenne_twister<uint32_t,32,351,175,19,0xccab8ee7,11,
+  7,0x31b6ab00,15,0xffe50000,17, 0xa37d3c92> mt11213b;
+
+/**
+ * The specializations \mt11213b and \mt19937 are from
+ *
+ *  @blockquote
+ *  "Mersenne Twister: A 623-dimensionally equidistributed
+ *  uniform pseudo-random number generator", Makoto Matsumoto
+ *  and Takuji Nishimura, ACM Transactions on Modeling and
+ *  Computer Simulation: Special Issue on Uniform Random Number
+ *  Generation, Vol. 8, No. 1, January 1998, pp. 3-30. 
+ *  @endblockquote
+ */
+typedef random::mersenne_twister<uint32_t,32,624,397,31,0x9908b0df,11,
+  7,0x9d2c5680,15,0xefc60000,18, 3346425566U> mt19937;
+
+} // namespace boost
+
+BOOST_RANDOM_PTR_HELPER_SPEC(boost::mt19937)
+
+#endif // BOOST_RANDOM_MERSENNE_TWISTER_HPP