boost/random/uniform_int.hpp

   1 /* boost random/uniform_int.hpp header file
   2  *
   3  * Copyright Jens Maurer 2000-2001
   4  * Distributed under the Boost Software License, Version 1.0. (See
   5  * accompanying file LICENSE_1_0.txt or copy at
   6  * http://www.boost.org/LICENSE_1_0.txt)
   7  *
   8  * See http://www.boost.org for most recent version including documentation.
   9  *
  10  * $Id$
  11  *
  12  * Revision history
  13  *  2001-04-08  added min<max assertion (N. Becker)
  14  *  2001-02-18  moved to individual header files
  15  */
  16
  17 #ifndef BOOST_RANDOM_UNIFORM_INT_HPP
  18 #define BOOST_RANDOM_UNIFORM_INT_HPP
  19
  20 #include <cassert>
  21 #include <iostream>
  22 #include <boost/config.hpp>
  23 #include <boost/limits.hpp>
  24 #include <boost/static_assert.hpp>
  25 #include <boost/detail/workaround.hpp>
  26 #include <boost/random/uniform_smallint.hpp>
  27 #include <boost/random/detail/config.hpp>
  28 #include <boost/random/detail/signed_unsigned_tools.hpp>
  29 #include <boost/type_traits/make_unsigned.hpp>
  30 #ifdef BOOST_NO_LIMITS_COMPILE_TIME_CONSTANTS
  31 #include <boost/type_traits/is_float.hpp>
  32 #endif
  33
  34 namespace boost {
  35
  36 // uniform integer distribution on [min, max]
  37 template<class IntType = int>
  38 class uniform_int
  39 {
  40 public:
  41   typedef IntType input_type;
  42   typedef IntType result_type;
  43   typedef typename make_unsigned<result_type>::type range_type;
  44
  45   explicit uniform_int(IntType min_arg = 0, IntType max_arg = 9)
  46     : _min(min_arg), _max(max_arg)
  47   {
  48 #ifndef BOOST_NO_LIMITS_COMPILE_TIME_CONSTANTS
  49     // MSVC fails BOOST_STATIC_ASSERT with std::numeric_limits at class scope
  50     BOOST_STATIC_ASSERT(std::numeric_limits<IntType>::is_integer);
  51 #endif
  52     assert(min_arg <= max_arg);
  53     init();
  54   }
  55
  56   result_type min BOOST_PREVENT_MACRO_SUBSTITUTION () const { return _min; }
  57   result_type max BOOST_PREVENT_MACRO_SUBSTITUTION () const { return _max; }
  58   void reset() { }
  59
  60   // can't have member function templates out-of-line due to MSVC bugs
  61   template<class Engine>
  62   result_type operator()(Engine& eng)
  63   {
  64       return generate(eng, _min, _max, _range);
  65   }
  66
  67   template<class Engine>
  68   result_type operator()(Engine& eng, result_type n)
  69   {
  70       assert(n > 0);
  71
  72       if (n == 1)
  73       {
  74         return 0;
  75       }
  76
  77       return generate(eng, 0, n - 1, n - 1);
  78   }
  79
  80 #ifndef BOOST_RANDOM_NO_STREAM_OPERATORS
  81   template<class CharT, class Traits>
  82   friend std::basic_ostream<CharT,Traits>&
  83   operator<<(std::basic_ostream<CharT,Traits>& os, const uniform_int& ud)
  84   {
  85     os << ud._min << " " << ud._max;
  86     return os;
  87   }
  88
  89   template<class CharT, class Traits>
  90   friend std::basic_istream<CharT,Traits>&
  91   operator>>(std::basic_istream<CharT,Traits>& is, uniform_int& ud)
  92   {
  93     is >> std::ws >> ud._min >> std::ws >> ud._max;
  94     ud.init();
  95     return is;
  96   }
  97 #endif
  98
  99 private:
 100   template<class Engine>
 101   static result_type generate(Engine& eng, result_type min_value, result_type max_value, range_type range)
 102   {
 103     typedef typename Engine::result_type base_result;
 104     // ranges are always unsigned
 105     typedef typename make_unsigned<base_result>::type base_unsigned;
 106     const base_result bmin = (eng.min)();
 107     const base_unsigned brange =
 108       random::detail::subtract<base_result>()((eng.max)(), (eng.min)());
 109
 110     if(range == 0) {
 111       return min_value;
 112     } else if(brange == range) {
 113       // this will probably never happen in real life
 114       // basically nothing to do; just take care we don't overflow / underflow
 115       base_unsigned v = random::detail::subtract<base_result>()(eng(), bmin);
 116       return random::detail::add<base_unsigned, result_type>()(v, min_value);
 117     } else if(brange < range) {
 118       // use rejection method to handle things like 0..3 --> 0..4
 119       for(;;) {
 120         // concatenate several invocations of the base RNG
 121         // take extra care to avoid overflows
 122         range_type limit;
 123         if(range == (std::numeric_limits<range_type>::max)()) {
 124           limit = range/(range_type(brange)+1);
 125           if(range % range_type(brange)+1 == range_type(brange))
 126             ++limit;
 127         } else {
 128           limit = (range+1)/(range_type(brange)+1);
 129         }
 130         // We consider "result" as expressed to base (brange+1):
 131         // For every power of (brange+1), we determine a random factor
 132         range_type result = range_type(0);
 133         range_type mult = range_type(1);
 134         while(mult <= limit) {
 135           result += random::detail::subtract<base_result>()(eng(), bmin) * mult;
 136           mult *= range_type(brange)+range_type(1);
 137         }
 138         if(mult == limit)
 139           // range+1 is an integer power of brange+1: no rejections required
 140           return result;
 141         // range/mult < brange+1  -> no endless loop
 142         result += uniform_int<range_type>(0, range/mult)(eng) * mult;
 143         if(result <= range)
 144           return random::detail::add<range_type, result_type>()(result, min_value);
 145       }
 146     } else {                   // brange > range
 147       if(brange / range > 4 /* quantization_cutoff */ ) {
 148         // the new range is vastly smaller than the source range,
 149         // so quantization effects are not relevant
 150         return boost::uniform_smallint<result_type>(min_value, max_value)(eng);
 151       } else {
 152         // use rejection method to handle cases like 0..5 -> 0..4
 153         for(;;) {
 154           base_unsigned result =
 155             random::detail::subtract<base_result>()(eng(), bmin);
 156           // result and range are non-negative, and result is possibly larger
 157           // than range, so the cast is safe
 158           if(result <= static_cast<base_unsigned>(range))
 159             return random::detail::add<base_unsigned, result_type>()(result, min_value);
 160         }
 161       }
 162     }
 163   }
 164
 165   void init()
 166   {
 167     _range = random::detail::subtract<result_type>()(_max, _min);
 168   }
 169
 170   // The result_type may be signed or unsigned, but the _range is always
 171   // unsigned.
 172   result_type _min, _max;
 173   range_type _range;
 174 };
 175
 176 } // namespace boost
 177
 178 #endif // BOOST_RANDOM_UNIFORM_INT_HPP