Subject: [Boost-commit] svn:boost r50601 - in branches/release: . boost/random libs/random
From: marshall_at_[hidden]
Date: 2009-01-14 22:43:37
Author: marshall
Date: 2009-01-14 22:43:36 EST (Wed, 14 Jan 2009)
New Revision: 50601
URL: http://svn.boost.org/trac/boost/changeset/50601
Log:
Merged revisions 50312 via svnmerge from
https://svn.boost.org/svn/boost/trunk
........
r50312 | marshall | 2008-12-17 18:37:07 -0800 (Wed, 17 Dec 2008) | 1 line
Applied patch from bug #1546
........
Properties modified:
branches/release/ (props changed)
Text files modified:
branches/release/boost/random/uniform_int.hpp | 103 +++++++++++++++++++++++----------------
branches/release/libs/random/random_test.cpp | 67 ++++++++++++++++++++++++++
2 files changed, 128 insertions(+), 42 deletions(-)
Modified: branches/release/boost/random/uniform_int.hpp
==============================================================================
--- branches/release/boost/random/uniform_int.hpp (original)
+++ branches/release/boost/random/uniform_int.hpp 2009-01-14 22:43:36 EST (Wed, 14 Jan 2009)
@@ -60,6 +60,49 @@
template<class Engine>
result_type operator()(Engine& eng)
{
+ return generate(eng, _min, _max, _range);
+ }
+
+ template<class Engine>
+ result_type operator()(Engine& eng, result_type n)
+ {
+ assert(n > 0);
+
+ if (n == 1)
+ {
+ return 0;
+ }
+
+ return generate(eng, 0, n - 1, n - 1);
+ }
+
+#if !defined(BOOST_NO_OPERATORS_IN_NAMESPACE) && !defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS)
+ template<class CharT, class Traits>
+ friend std::basic_ostream<CharT,Traits>&
+ operator<<(std::basic_ostream<CharT,Traits>& os, const uniform_int& ud)
+ {
+ os << ud._min << " " << ud._max;
+ return os;
+ }
+
+ template<class CharT, class Traits>
+ friend std::basic_istream<CharT,Traits>&
+ operator>>(std::basic_istream<CharT,Traits>& is, uniform_int& ud)
+ {
+# if BOOST_WORKAROUND(_MSC_FULL_VER, BOOST_TESTED_AT(13102292)) && BOOST_MSVC == 1400
+ return detail::extract_uniform_int(is, ud, ud.impl);
+# else
+ is >> std::ws >> ud._min >> std::ws >> ud._max;
+ ud.init();
+ return is;
+# endif
+ }
+#endif
+
+private:
+ template<class Engine>
+ static result_type generate(Engine& eng, result_type min_value, result_type max_value, range_type range)
+ {
typedef typename Engine::result_type base_result;
// ranges are always unsigned
typedef typename make_unsigned<base_result>::type base_unsigned;
@@ -67,25 +110,25 @@
const base_unsigned brange =
random::detail::subtract<base_result>()((eng.max)(), (eng.min)());
- if(_range == 0) {
- return _min;
- } else if(brange == _range) {
+ if(range == 0) {
+ return min_value;
+ } else if(brange == range) {
// this will probably never happen in real life
// basically nothing to do; just take care we don't overflow / underflow
base_unsigned v = random::detail::subtract<base_result>()(eng(), bmin);
- return random::detail::add<base_unsigned, result_type>()(v, _min);
- } else if(brange < _range) {
+ return random::detail::add<base_unsigned, result_type>()(v, min_value);
+ } else if(brange < range) {
// use rejection method to handle things like 0..3 --> 0..4
for(;;) {
// concatenate several invocations of the base RNG
// take extra care to avoid overflows
range_type limit;
- if(_range == (std::numeric_limits<range_type>::max)()) {
- limit = _range/(range_type(brange)+1);
- if(_range % range_type(brange)+1 == range_type(brange))
+ if(range == (std::numeric_limits<range_type>::max)()) {
+ limit = range/(range_type(brange)+1);
+ if(range % range_type(brange)+1 == range_type(brange))
++limit;
} else {
- limit = (_range+1)/(range_type(brange)+1);
+ limit = (range+1)/(range_type(brange)+1);
}
// We consider "result" as expressed to base (brange+1):
// For every power of (brange+1), we determine a random factor
@@ -96,18 +139,18 @@
mult *= range_type(brange)+range_type(1);
}
if(mult == limit)
- // _range+1 is an integer power of brange+1: no rejections required
+ // range+1 is an integer power of brange+1: no rejections required
return result;
- // _range/mult < brange+1 -> no endless loop
- result += uniform_int<range_type>(0, _range/mult)(eng) * mult;
- if(result <= _range)
- return random::detail::add<range_type, result_type>()(result, _min);
+ // range/mult < brange+1 -> no endless loop
+ result += uniform_int<range_type>(0, range/mult)(eng) * mult;
+ if(result <= range)
+ return random::detail::add<range_type, result_type>()(result, min_value);
}
} else { // brange > range
- if(brange / _range > 4 /* quantization_cutoff */ ) {
+ if(brange / range > 4 /* quantization_cutoff */ ) {
// the new range is vastly smaller than the source range,
// so quantization effects are not relevant
- return boost::uniform_smallint<result_type>(_min, _max)(eng);
+ return boost::uniform_smallint<result_type>(min_value, max_value)(eng);
} else {
// use rejection method to handle cases like 0..5 -> 0..4
for(;;) {
@@ -115,37 +158,13 @@
random::detail::subtract<base_result>()(eng(), bmin);
// result and range are non-negative, and result is possibly larger
// than range, so the cast is safe
- if(result <= static_cast<base_unsigned>(_range))
- return random::detail::add<base_unsigned, result_type>()(result, _min);
+ if(result <= static_cast<base_unsigned>(range))
+ return random::detail::add<base_unsigned, result_type>()(result, min_value);
}
}
}
}
-#if !defined(BOOST_NO_OPERATORS_IN_NAMESPACE) && !defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS)
- template<class CharT, class Traits>
- friend std::basic_ostream<CharT,Traits>&
- operator<<(std::basic_ostream<CharT,Traits>& os, const uniform_int& ud)
- {
- os << ud._min << " " << ud._max;
- return os;
- }
-
- template<class CharT, class Traits>
- friend std::basic_istream<CharT,Traits>&
- operator>>(std::basic_istream<CharT,Traits>& is, uniform_int& ud)
- {
-# if BOOST_WORKAROUND(_MSC_FULL_VER, BOOST_TESTED_AT(13102292)) && BOOST_MSVC == 1400
- return detail::extract_uniform_int(is, ud, ud.impl);
-# else
- is >> std::ws >> ud._min >> std::ws >> ud._max;
- ud.init();
- return is;
-# endif
- }
-#endif
-
-private:
void init()
{
_range = random::detail::subtract<result_type>()(_max, _min);
Modified: branches/release/libs/random/random_test.cpp
==============================================================================
--- branches/release/libs/random/random_test.cpp (original)
+++ branches/release/libs/random/random_test.cpp 2009-01-14 22:43:36 EST (Wed, 14 Jan 2009)
@@ -500,6 +500,72 @@
{ }
#endif
+template <typename EngineT>
+struct rand_for_random_shuffle
+{
+ explicit rand_for_random_shuffle(EngineT &engine)
+ : m_engine(engine)
+ { }
+
+ template <typename IntT>
+ IntT operator()(IntT upperBound)
+ {
+ assert(upperBound > 0);
+
+ if (upperBound == 1)
+ {
+ return 0;
+ }
+
+ typedef boost::uniform_int<IntT> distribution_type;
+ typedef boost::variate_generator<EngineT &, distribution_type> generator_type;
+
+ return generator_type(m_engine, distribution_type(0, upperBound - 1))();
+ }
+
+ EngineT &m_engine;
+
+};
+
+// Test that uniform_int<> can be used with std::random_shuffle
+// Author: Jos Hickson
+void test_random_shuffle()
+{
+ typedef boost::uniform_int<> distribution_type;
+ typedef boost::variate_generator<boost::mt19937 &, distribution_type> generator_type;
+
+ boost::mt19937 engine1(1234);
+ boost::mt19937 engine2(1234);
+
+ rand_for_random_shuffle<boost::mt19937> referenceRand(engine1);
+
+ distribution_type dist(0,10);
+ generator_type testRand(engine2, dist);
+
+ std::vector<int> referenceVec;
+
+ for (int i = 0; i < 200; ++i)
+ {
+ referenceVec.push_back(i);
+ }
+
+ std::vector<int> testVec(referenceVec);
+
+ std::random_shuffle(referenceVec.begin(), referenceVec.end(), referenceRand);
+ std::random_shuffle(testVec.begin(), testVec.end(), testRand);
+
+ typedef std::vector<int>::iterator iter_type;
+ iter_type theEnd(referenceVec.end());
+
+ for (iter_type referenceIter(referenceVec.begin()), testIter(testVec.begin());
+ referenceIter != theEnd;
+ ++referenceIter, ++testIter)
+ {
+ BOOST_CHECK_EQUAL(*referenceIter, *testIter);
+ }
+}
+
+
int test_main(int, char*[])
{
@@ -528,6 +594,7 @@
<< std::endl;
test_overflow_range();
+ test_random_shuffle();
return 0;
#else