random_number_generator.h

Go to the documentation of this file.

// Copyright (C) 2010-2020 Internet Systems Consortium, Inc. ("ISC")
//
// This Source Code Form is subject to the terms of the Mozilla Public
// License, v. 2.0. If a copy of the MPL was not distributed with this
// file, You can obtain one at http://mozilla.org/MPL/2.0/.

#ifndef NSAS_RANDOM_NUMBER_GENERATOR_H
#define NSAS_RANDOM_NUMBER_GENERATOR_H

#include <algorithm>
#include <cmath>
#include <iterator>
#include <numeric>
#include <vector>

#include <exceptions/exceptions.h>

#include <boost/random/mersenne_twister.hpp>
#include <boost/random/uniform_int.hpp>
#include <boost/random/uniform_real.hpp>
#include <boost/random/variate_generator.hpp>


namespace isc {
namespace util {
namespace random {

class InvalidLimits : public isc::BadValue {
public:
    InvalidLimits(const char* file, size_t line, const char* what) :
        isc::BadValue(file, line, what) {}
};

class SumNotOne : public isc::BadValue {
public:
    SumNotOne(const char* file, size_t line, const char* what) :
        isc::BadValue(file, line, what) {}
};

class InvalidProbValue : public isc::BadValue {
public:
    InvalidProbValue(const char* file, size_t line, const char* what) :
        isc::BadValue(file, line, what) {}
};



class UniformRandomIntegerGenerator{
public:
    UniformRandomIntegerGenerator(int min, int max):
        min_(std::min(min, max)), max_(std::max(min, max)),
        dist_(min_, max_), generator_(rng_, dist_)
    {
        // To preserve the restriction of the underlying uniform_int class (and
        // to retain compatibility with earlier versions of the class), we will
        // abort if the minimum and maximum given are the wrong way round.
        if (min > max) {
            isc_throw(InvalidLimits, "minimum limit is greater than maximum "
                      "when initializing UniformRandomIntegerGenerator");
        }

        // Init with the current time
        rng_.seed(time(NULL));
    }

    int operator()() { return generator_(); }
private:
    UniformRandomIntegerGenerator();
    UniformRandomIntegerGenerator(const UniformRandomIntegerGenerator&); 

    int min_;                       
    int max_;                       
    boost::uniform_int<> dist_;     
    boost::mt19937 rng_;            
    boost::variate_generator<boost::mt19937&, boost::uniform_int<> > generator_; 
};

class WeightedRandomIntegerGenerator {
public:
    WeightedRandomIntegerGenerator(const std::vector<double>& probabilities,
        size_t min = 0):
        dist_(0, 1.0), uniform_real_gen_(rng_, dist_), min_(min)
    {
        // The probabilities must be valid.  Checking is quite an expensive
        // operation, so is only done in a debug build.
        areProbabilitiesValid(probabilities);

        // Calculate the partial sum of probabilities
        std::partial_sum(probabilities.begin(), probabilities.end(),
                                     std::back_inserter(cumulative_));
        // Init with the current time
        rng_.seed(time(NULL));
    }

    WeightedRandomIntegerGenerator():
        dist_(0, 1.0), uniform_real_gen_(rng_, dist_), min_(0)
    {
    }

    void reset(const std::vector<double>& probabilities, size_t min = 0)
    {
        // The probabilities must be valid.
        areProbabilitiesValid(probabilities);

        // Reset the cumulative sum
        cumulative_.clear();

        // Calculate the partial sum of probabilities
        std::partial_sum(probabilities.begin(), probabilities.end(),
                                     std::back_inserter(cumulative_));

        // Reset the minimum integer
        min_ = min;
    }

    size_t operator()()
    {
        return std::lower_bound(cumulative_.begin(), cumulative_.end(), uniform_real_gen_())
            - cumulative_.begin() + min_;
    }

private:
    void areProbabilitiesValid(const std::vector<double>& probabilities) const
    {
        double sum = probabilities.empty() ? 1.0 : 0.0;
        for (const double it : probabilities) {
            //The probability must be in [0, 1.0]
            if (it < 0.0 || it > 1.0) {
                isc_throw(InvalidProbValue,
                          "probability must be in the range 0..1");
            }

            sum += it;
        }

        double epsilon = 0.0001;
        // The sum must be equal to 1
        if (std::fabs(sum - 1.0) >= epsilon) {
            isc_throw(SumNotOne, "Sum of probabilities is not equal to 1");
        }

        return;
    }

    std::vector<double> cumulative_;    
    boost::mt19937 rng_;                
    boost::uniform_real<> dist_;        

    // Shortcut typedef
    // This typedef is placed directly before its use, as the sunstudio
    // compiler could not handle it being anywhere else (don't know why)
    typedef boost::variate_generator<boost::mt19937&, boost::uniform_real<> > UniformRealGenerator;
    UniformRealGenerator uniform_real_gen_;     

    size_t min_;                                
};

}   // namespace random
}   // namespace util
}   // namespace isc

#endif//NSAS_RANDOM_NUMBER_GENERATOR_H