
#include "tools.h"


double Pow(double x,int y){
	double ret = 1;
	for(; y; y>>=1, x = x * x)
		if(y&1) ret = ret * x;
	return ret;
}

//Random
unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
mt19937 rand_num(seed);	
uniform_real_distribution<double> rnd(0, 1);

double randm(){
	return rnd(rand_num);
}

//uniform distribution
  void sampler::init_uniform(const int &n){
	pd.resize(n);
	for(int i = 0; i < pd.size(); i++)
		pd[i] = (i + 1) / (double)n;
}



void sampler::init(const vector<double> &distr){
	pd = distr;
	for(int i = 1; i < pd.size(); i++)
		pd[i] += pd[i-1];
	double sum = *pd.rbegin();
	for(int i = 0; i < pd.size(); i++)
		pd[i] /= sum;
}

int sampler::sample(){
	double val = randm();
	int l = 0, r = pd.size() - 1, mid, ret = pd.size() - 1;
	
	while(l<=r) pd[mid = (l + r) >> 1] > val ? r = (ret = mid) - 1 : l = mid + 1;
	return ret;
}
