williamr@2: /* boost random/uniform_int.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: uniform_int.hpp,v 1.27 2004/07/27 03:43:32 dgregor Exp $
williamr@2:  *
williamr@2:  * Revision history
williamr@2:  *  2001-04-08  added min<max assertion (N. Becker)
williamr@2:  *  2001-02-18  moved to individual header files
williamr@2:  */
williamr@2: 
williamr@2: #ifndef BOOST_RANDOM_UNIFORM_INT_HPP
williamr@2: #define BOOST_RANDOM_UNIFORM_INT_HPP
williamr@2: 
williamr@2: #include <cassert>
williamr@2: #include <iostream>
williamr@2: #include <boost/config.hpp>
williamr@2: #include <boost/limits.hpp>
williamr@2: #include <boost/static_assert.hpp>
williamr@2: #include <boost/detail/workaround.hpp>
williamr@2: #include <boost/random/uniform_smallint.hpp>
williamr@2: #include <boost/random/detail/signed_unsigned_compare.hpp>
williamr@2: #ifdef BOOST_NO_LIMITS_COMPILE_TIME_CONSTANTS
williamr@2: #include <boost/type_traits/is_float.hpp>
williamr@2: #endif
williamr@2: 
williamr@2: namespace boost {
williamr@2: 
williamr@2: // uniform integer distribution on [min, max]
williamr@2: template<class IntType = int>
williamr@2: class uniform_int
williamr@2: {
williamr@2: public:
williamr@2:   typedef IntType input_type;
williamr@2:   typedef IntType result_type;
williamr@2: 
williamr@2:   explicit uniform_int(IntType min = 0, IntType max = 9)
williamr@2:     : _min(min), _max(max)
williamr@2:   {
williamr@2: #ifndef BOOST_NO_LIMITS_COMPILE_TIME_CONSTANTS
williamr@2:     // MSVC fails BOOST_STATIC_ASSERT with std::numeric_limits at class scope
williamr@2:     BOOST_STATIC_ASSERT(std::numeric_limits<IntType>::is_integer);
williamr@2: #endif
williamr@2:     assert(min <= max);
williamr@2:     init();
williamr@2:   }
williamr@2: 
williamr@2:   result_type min BOOST_PREVENT_MACRO_SUBSTITUTION () const { return _min; }
williamr@2:   result_type max BOOST_PREVENT_MACRO_SUBSTITUTION () const { return _max; }
williamr@2:   void reset() { }
williamr@2:   
williamr@2:   // can't have member function templates out-of-line due to MSVC bugs
williamr@2:   template<class Engine>
williamr@2:   result_type operator()(Engine& eng)
williamr@2:   {
williamr@2:     typedef typename Engine::result_type base_result;
williamr@2:     base_result bmin = (eng.min)();
williamr@2:     base_result brange = (eng.max)() - (eng.min)();
williamr@2: 
williamr@2:     if(_range == 0) {
williamr@2:       return _min;    
williamr@2:     } else if(random::equal_signed_unsigned(brange, _range)) {
williamr@2:       // this will probably never happen in real life
williamr@2:       // basically nothing to do; just take care we don't overflow / underflow
williamr@2:       return static_cast<result_type>(eng() - bmin) + _min;
williamr@2:     } else if(random::lessthan_signed_unsigned(brange, _range)) {
williamr@2:       // use rejection method to handle things like 0..3 --> 0..4
williamr@2:       for(;;) {
williamr@2:         // concatenate several invocations of the base RNG
williamr@2:         // take extra care to avoid overflows
williamr@2:         result_type limit;
williamr@2:         if(_range == (std::numeric_limits<result_type>::max)()) {
williamr@2:           limit = _range/(result_type(brange)+1);
williamr@2:           if(_range % result_type(brange)+1 == result_type(brange))
williamr@2:             ++limit;
williamr@2:         } else {
williamr@2:           limit = (_range+1)/(result_type(brange)+1);
williamr@2:         }
williamr@2:         // We consider "result" as expressed to base (brange+1):
williamr@2:         // For every power of (brange+1), we determine a random factor
williamr@2:         result_type result = result_type(0);
williamr@2:         result_type mult = result_type(1);
williamr@2:         while(mult <= limit) {
williamr@2:           result += (eng() - bmin) * mult;
williamr@2:           mult *= result_type(brange)+result_type(1);
williamr@2:         }
williamr@2:         if(mult == limit)
williamr@2:           // _range+1 is an integer power of brange+1: no rejections required
williamr@2:           return result;
williamr@2:         // _range/mult < brange+1  -> no endless loop
williamr@2:         result += uniform_int<result_type>(0, _range/mult)(eng) * mult;
williamr@2:         if(result <= _range)
williamr@2:           return result + _min;
williamr@2:       }
williamr@2:     } else {                   // brange > range
williamr@2:       if(brange / _range > 4 /* quantization_cutoff */ ) {
williamr@2:         // the new range is vastly smaller than the source range,
williamr@2:         // so quantization effects are not relevant
williamr@2:         return boost::uniform_smallint<result_type>(_min, _max)(eng);
williamr@2:       } else {
williamr@2:         // use rejection method to handle cases like 0..5 -> 0..4
williamr@2:         for(;;) {
williamr@2:           base_result result = eng() - bmin;
williamr@2:           // result and range are non-negative, and result is possibly larger
williamr@2:           // than range, so the cast is safe
williamr@2:           if(result <= static_cast<base_result>(_range))
williamr@2:             return result + _min;
williamr@2:         }
williamr@2:       }
williamr@2:     }
williamr@2:   }
williamr@2: 
williamr@2: #if !defined(BOOST_NO_OPERATORS_IN_NAMESPACE) && !defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS)
williamr@2:   template<class CharT, class Traits>
williamr@2:   friend std::basic_ostream<CharT,Traits>&
williamr@2:   operator<<(std::basic_ostream<CharT,Traits>& os, const uniform_int& ud)
williamr@2:   {
williamr@2:     os << ud._min << " " << ud._max;
williamr@2:     return os;
williamr@2:   }
williamr@2: 
williamr@2:   template<class CharT, class Traits>
williamr@2:   friend std::basic_istream<CharT,Traits>&
williamr@2:   operator>>(std::basic_istream<CharT,Traits>& is, uniform_int& ud)
williamr@2:   {
williamr@2: # if BOOST_WORKAROUND(_MSC_FULL_VER, BOOST_TESTED_AT(13102292)) && BOOST_MSVC > 1300
williamr@2:       return detail::extract_uniform_int(is, ud, ud.impl);
williamr@2: # else
williamr@2:    is >> std::ws >> ud._min >> std::ws >> ud._max;
williamr@2:     ud.init();
williamr@2:     return is;
williamr@2: # endif
williamr@2:   }
williamr@2: #endif
williamr@2: 
williamr@2: private:
williamr@2:   void init()
williamr@2:   {
williamr@2:     _range = _max - _min;
williamr@2:   }
williamr@2:     
williamr@2:   result_type _min, _max, _range;
williamr@2: };
williamr@2: 
williamr@2: } // namespace boost
williamr@2: 
williamr@2: #endif // BOOST_RANDOM_UNIFORM_INT_HPP