/* boost random/uniform_int.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: uniform_int.hpp,v 1.27 2004/07/27 03:43:32 dgregor Exp $

 *

 * Revision history

 *  2001-04-08  added min<max assertion (N. Becker)

 *  2001-02-18  moved to individual header files

 */

#ifndef BOOST_RANDOM_UNIFORM_INT_HPP

#define BOOST_RANDOM_UNIFORM_INT_HPP

#include <cassert>

#include <iostream>

#include <boost/config.hpp>

#include <boost/limits.hpp>

#include <boost/static_assert.hpp>

#include <boost/detail/workaround.hpp>

#include <boost/random/uniform_smallint.hpp>

#include <boost/random/detail/signed_unsigned_compare.hpp>

#ifdef BOOST_NO_LIMITS_COMPILE_TIME_CONSTANTS

#include <boost/type_traits/is_float.hpp>

#endif

namespace boost {

// uniform integer distribution on [min, max]

template<class IntType = int>

class uniform_int

{

public:

  typedef IntType input_type;

  typedef IntType result_type;

  explicit uniform_int(IntType min = 0, IntType max = 9)

    : _min(min), _max(max)

  {

#ifndef BOOST_NO_LIMITS_COMPILE_TIME_CONSTANTS

    // MSVC fails BOOST_STATIC_ASSERT with std::numeric_limits at class scope

    BOOST_STATIC_ASSERT(std::numeric_limits<IntType>::is_integer);

#endif

    assert(min <= max);

    init();

  }

  result_type min BOOST_PREVENT_MACRO_SUBSTITUTION () const { return _min; }

  result_type max BOOST_PREVENT_MACRO_SUBSTITUTION () const { return _max; }

  void reset() { }

  // can't have member function templates out-of-line due to MSVC bugs

  template<class Engine>

  result_type operator()(Engine& eng)

  {

    typedef typename Engine::result_type base_result;

    base_result bmin = (eng.min)();

    base_result brange = (eng.max)() - (eng.min)();

    if(_range == 0) {

      return _min;    

    } else if(random::equal_signed_unsigned(brange, _range)) {

      // this will probably never happen in real life

      // basically nothing to do; just take care we don't overflow / underflow

      return static_cast<result_type>(eng() - bmin) + _min;

    } else if(random::lessthan_signed_unsigned(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

        result_type limit;

        if(_range == (std::numeric_limits<result_type>::max)()) {

          limit = _range/(result_type(brange)+1);

          if(_range % result_type(brange)+1 == result_type(brange))

            ++limit;

        } else {

          limit = (_range+1)/(result_type(brange)+1);

        }

        // We consider "result" as expressed to base (brange+1):

        // For every power of (brange+1), we determine a random factor

        result_type result = result_type(0);

        result_type mult = result_type(1);

        while(mult <= limit) {

          result += (eng() - bmin) * mult;

          mult *= result_type(brange)+result_type(1);

        }

        if(mult == limit)

          // _range+1 is an integer power of brange+1: no rejections required

          return result;

        // _range/mult < brange+1  -> no endless loop

        result += uniform_int<result_type>(0, _range/mult)(eng) * mult;

        if(result <= _range)

          return result + _min;

      }

    } else {                   // brange > range

      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);

      } else {

        // use rejection method to handle cases like 0..5 -> 0..4

        for(;;) {

          base_result 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_result>(_range))

            return result + _min;

        }

      }

    }

  }

#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 > 1300

      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 = _max - _min;

  }

  result_type _min, _max, _range;

};

} // namespace boost

#endif // BOOST_RANDOM_UNIFORM_INT_HPP