RouletteSampler.hh

// Copyright QED Software 2023.
 
#ifndef GRAIL_ROULETTE_SAMPLER_H
#define GRAIL_ROULETTE_SAMPLER_H
 
#include <memory>
#include <numeric>
#include <random>
 
namespace grail
{
namespace evolution
{
    template <class T>
    class RouletteSampler
    {
    public:
        RouletteSampler();
 
        RouletteSampler(const std::vector<std::unique_ptr<T>>& fitnessHavingElements);
 
        void Initialize(const std::vector<std::unique_ptr<T>>& fitnessHavingElements);
 
        T* Sample(std::mt19937_64& randGen);
 
        T* SampleWithReturn(std::mt19937_64& randGen);
        
        std::vector<T*> SampleMany(size_t count, std::mt19937_64& randGen);
 
        std::vector<T*> SampleManyWithReturn(size_t count, std::mt19937_64& randGen);
 
        std::vector<size_t> SampleManyIndices(size_t count, std::mt19937_64& randGen);
 
    private:
        std::size_t SampleIndex(std::mt19937_64& randGen);
        
        std::size_t SampleIndexWithReturn(std::mt19937_64& randGen) const;
 
        std::size_t RemoveIndex(std::size_t index);
 
        std::vector<T*> data{};
        double totalFitness = 0.0;
    };
 
    template <class T>
    inline std::size_t RouletteSampler<T>::RemoveIndex(std::size_t index)
    {
        totalFitness -= data[index]->GetFitness();
        data.erase(data.begin() + index);
        return index;
    }
 
    template <class T>
    inline void RouletteSampler<T>::Initialize(const std::vector<std::unique_ptr<T>>& fitnessHavingElements)
    {
        data.clear();
        totalFitness = 0.0;
        for(auto& individual : fitnessHavingElements)
        {
            totalFitness += individual->GetFitness();
            data.push_back(individual.get());
        }
    }
 
    template <class T>
    inline RouletteSampler<T>::RouletteSampler()
        : totalFitness{0.0}
    {
    }
 
    template <class T>
    inline RouletteSampler<T>::RouletteSampler(const std::vector<std::unique_ptr<T>>& fitnessHavingElements)
    {
        Initialize(fitnessHavingElements);
    }
 
    template <class T>
    inline std::size_t RouletteSampler<T>::SampleIndex(std::mt19937_64& randGen)
    {
        return RemoveIndex(SampleIndexWithReturn(randGen));
    }
 
    template <class T>
    inline std::size_t RouletteSampler<T>::SampleIndexWithReturn(std::mt19937_64& randGen) const
    {
        if(totalFitness <= std::numeric_limits<double>::epsilon())
        {
            return std::uniform_int_distribution<size_t>(0, data.size())(randGen);
        }
 
        double val = std::uniform_real_distribution<double>(0, totalFitness)(randGen);
        for(size_t i = 0; i < data.size(); ++i)
        {
            if(val < data[i]->GetFitness())
            {
                return i;
            }
 
            val -= data[i]->GetFitness();
        }
        return data.size() - 1;
    }
 
    template <class T>
    inline std::vector<size_t> RouletteSampler<T>::SampleManyIndices(size_t count, std::mt19937_64& randGen)
    {
        std::vector<size_t> retData;
        if(count >= data.size())
        {
            retData.resize(data.size());
            std::iota(retData.begin(), retData.end(), 0);
        }
        else
        {
            for(size_t i = 0; i < count; ++i)
            {
                retData.push_back(SampleIndex(randGen));
            }
        }
        return retData;
    }
 
    template <class T>
    inline T* RouletteSampler<T>::Sample(std::mt19937_64& randGen)
    {
        if(data.size() == 0)
        {
            return nullptr;
        }
 
        std::size_t index = SampleIndexWithReturn(randGen);
        T* individual = data[index];
        RemoveIndex(index);
        return individual;
    }
 
    template <class T>
    inline T* RouletteSampler<T>::SampleWithReturn(std::mt19937_64& randGen)
    {
        if (data.size() == 0)
        {
            return nullptr;
        }
 
        return data[SampleIndexWithReturn(randGen)];
    }
 
    template <class T>
    inline std::vector<T*> RouletteSampler<T>::SampleMany(std::size_t count, std::mt19937_64& randGen)
    {
        if(count >= data.size())
        {
            return std::vector<T*>(data);
        }
 
        std::vector<T*> retData;
        for(std::size_t i = 0; i < count; ++i)
        {
            retData.push_back(Sample(randGen));
        }
        return retData;
    }
 
    template <class T>
    inline std::vector<T*> RouletteSampler<T>::SampleManyWithReturn(std::size_t count, std::mt19937_64& randGen)
    {
        if (count >= data.size())
        {
            return std::vector<T*>(data);
        }
 
        std::vector<T*> retData;
        for (std::size_t i = 0; i < count; ++i)
        {
            retData.push_back(SampleWithReturn(randGen));
        }
        return retData;
    }
}
}
 
#endif // GRAIL_ROULETTE_SAMPLER_H