/////////////////////////////////////////////////////
// To  Compile
//
// Linux:
// g++ -lglut rand.cpp
//
// Mac OSX(thanks Aaron):
// g++ rand.c -framework GLUT -framework OpenGL
// and change the next two lines to:
// #include <GLUT/glut.h>
// #include <OpenGL/gl.h>
#include <GL/glut.h>
#include <GL/gl.h>
//
// Windows:
// Download glut from http://www.xmission.com/~nate/glut.html
//
// Go to the properties page and c++->General->Additional Include Directories
// Point that to where you extracted glut too
// Go to the properties page and linker->Additional Dependancies
// Point that too where you extracted glut32.lib to.


////////////////////////////////////////////////////
// To Customize
//
// uncomment one of the define statments bellow to change the random gen method.

//The OS provided random number generation API, unseeded
//#define rand_method os_random

//The c/c++ rand() standard, seeded with time
#define rand_method sys_random

//The fast and simple (seven lines of code) 'shift and xor' PRNG, seeded with time.
//#define rand_method shiftXor

////////////////////////////////////////////////////
//everything beneath this comment is poorly implemented
//
//you have been warned.

#ifdef WIN32
#define _CRT_RAND_S
#endif

#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<time.h>
#include<math.h>
#include <vector>
#include<limits.h>

#ifdef WIN32
class os_random{
public:
	os_random(){
	}
	const static unsigned int MAX = UINT_MAX;
protected:
	unsigned int Next(){
		unsigned int l=0;
		if(rand_s(&l)!=0)
			abort();
		return l;
	}
};

#else
// /dev/random would be better, but it blocks a lot
// so I use /dev/urandom here
class os_random{
public:
	os_random(){
		f=fopen("/dev/urandom","rb");
		if(!f)
			abort();
	}
	const static unsigned int MAX =INT_MAX;
protected:
	unsigned int Next(){
		int out = fread(&rnd, sizeof(rnd),1,f);
		if(out!=1)
			abort();
		return  rnd;
	}
private:
	unsigned int rnd;
	FILE * f;
};
#endif

using namespace std;

class sys_random{
public:
	sys_random(){
		srand(time(0));
	}
	const static unsigned int MAX =RAND_MAX;
protected:
	unsigned int Next(){
		return rand();
	}
};

class shiftXor{
public:
	shiftXor(){
		x=time(0);
		y=time(0);
		z=time(0);
		w=time(0);
		v=time(0);
	}
	const static unsigned int MAX =((unsigned int)-1)/2;
private:
	unsigned int xorshift() {
		int t;
		t=(x^(x>>7));
		x=y;
		y=z;
		z=w;
		w=v;
		v=(v^(v<<6))^(t^(t<<13));
		return (y+y+1)*v;
	}
protected:
	unsigned int x,y,z,w,v;
	unsigned int Next(){
		return xorshift();
	}
};

template<class T>
class _genSeq : public T {
public:
	using T::Next;
	using T::MAX;
	_genSeq(){}
	_genSeq(unsigned int i){
		seq(i);
	}
	unsigned int getX(unsigned int t){
		return seq(t+3)-seq(t+2);
	}
	unsigned int getY(unsigned int t){
		return seq(t+2)-seq(t+1);
	}
	unsigned int getZ(unsigned int t){
		return seq(t+1)-seq(t);
	}
	unsigned int seq(unsigned int i){
		while(i>=seq_list.size()){
			seq_list.push_back(Next());
		}
		return seq_list[i];
	}
private:
	vector<unsigned int> seq_list;
};
_genSeq <rand_method> genSeq;
bool click=false;
float Xrot=0,Yrot=0,Zrot=0;
double zoom=genSeq.MAX*2;
double zoomVal=genSeq.MAX/zoom;
double valx,valy,valz;
bool shiftx=false,shifty=false,shiftz=false;
int oldx=0, oldy=0;
unsigned int bucket=10000;
void display(){
	zoomVal=genSeq.MAX/zoom;
	glClearColor(0,0,0,0);
	glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);

	glMatrixMode(GL_MODELVIEW);
	glPushMatrix();

	glRotatef(Xrot,1,0,0);
	glRotatef(Yrot,0,1,0);
	glRotatef(Zrot,0,0,1);

	glBegin(GL_LINE_STRIP);
		glVertex3d(zoomVal, zoomVal, zoomVal);
		glVertex3d(-zoomVal, zoomVal, zoomVal);
		glVertex3d(-zoomVal, -zoomVal, zoomVal);
		glVertex3d(zoomVal, -zoomVal, zoomVal);
		glVertex3d(zoomVal, zoomVal, zoomVal);
	glEnd();
	glBegin(GL_LINE_STRIP);
		glVertex3d(zoomVal, zoomVal, -zoomVal);
		glVertex3d(-zoomVal, zoomVal, -zoomVal);
		glVertex3d(-zoomVal, -zoomVal, -zoomVal);
		glVertex3d(zoomVal, -zoomVal, -zoomVal);
		glVertex3d(zoomVal, zoomVal, -zoomVal);
	glEnd();
	glBegin(GL_LINES);
		glVertex3d(zoomVal, zoomVal, zoomVal);
		glVertex3d(zoomVal, zoomVal, -zoomVal);
		glVertex3d(-zoomVal, zoomVal, zoomVal);
		glVertex3d(-zoomVal, zoomVal, -zoomVal);
		glVertex3d(zoomVal, -zoomVal, zoomVal);
		glVertex3d(zoomVal, -zoomVal, -zoomVal);
		glVertex3d(-zoomVal, -zoomVal, zoomVal);
		glVertex3d(-zoomVal, -zoomVal, -zoomVal);
	glEnd();
	glTranslatef(-0.5,-0.5,-0.5);
	glBegin(GL_POINTS);
		for(unsigned int i=0;i<bucket;i++){
			valx = (genSeq.getX(i)/zoom);
			valy = (genSeq.getY(i)/zoom);
			valz = (genSeq.getZ(i)/zoom);
			if(shiftx){
				if(valx>0.5){
					valx-=0.5;
				}else{
					valx+=0.5;
				}
			}
			if(shifty){
				if(valy>0.5){
					valy-=0.5;
				}else{
					valy+=0.5;
				}
			}
			if(shiftz){
				if(valz>0.5){
					valz-=0.5;
				}else{
					valz+=0.5;
				}
			}
			glVertex3d(valx, valy,valz);
		}
	glEnd();
	glPopMatrix();
	glutSwapBuffers();
}

void time(int var){
	display();
	glutTimerFunc(5,time,5);
}

void motion(int x, int y){
	if(click){
		Xrot=(oldy-y)+Xrot;
		Yrot=(oldx-x)+Yrot;
		oldy=y;
		oldx=x;
	}
}

void reshape(int w, int h){
	float aspect=(float)h/w;
	float fPos[4] = {0.0f, 0.0f, 0.0f, 0.0f};
	float white[4] = {1.0f, 1.0f, 1.0f, 1.0f};
	float fCol[4] = {1.0f, 1.0f, 1.0f, 1.0f};
	glViewport(0,0,w,h);
	glMatrixMode(GL_PROJECTION);
	glLoadIdentity();
	glFrustum(-1,1,-aspect,aspect,0,(unsigned int)-1);
	glMatrixMode(GL_MODELVIEW);
	glLoadIdentity();
	glEnable(GL_CULL_FACE);
	glEnable(GL_DEPTH_TEST);
	glEnable(GL_NORMALIZE);
	
	glLightfv(GL_LIGHT0, GL_POSITION, fPos);
	glEnable(GL_LIGHT0);
	glMaterialfv(GL_FRONT, GL_AMBIENT_AND_DIFFUSE, fCol);
}

void keyboard(unsigned char byte, int X, int Y){
	if(byte=='+'){
		zoom*=1.5;
	}else if(byte=='-'){
		zoom/=1.5;
	}else if(byte=='1'){
		shiftx=!shiftx;
	}else if(byte=='2'){
		shifty=!shifty;
	}else if(byte=='3'){
		shiftz=!shiftz;
	}else if(byte=='[' && bucket<100000){
		bucket*=2;
	}else if(byte==']'  && bucket>1000){
		bucket/=2;
	}
}

void mouse(int but, int state, int x, int y){
	oldy=y;
	oldx=x;
	if(state==GLUT_UP){
		click=false;
	}else{
		click=true;
	}
}
void glutsim(int argc, char ** argv){
	glutInitDisplayMode(GLUT_RGB|GLUT_DOUBLE|GLUT_DEPTH);
	glutInitWindowSize(500, 500);
	glutInit(&argc, argv);
	glutCreateWindow("Metric!");
	glutDisplayFunc(display);
	glutReshapeFunc(reshape);
	glutKeyboardFunc(keyboard);
	glutMouseFunc(mouse);
	glutMotionFunc(motion);
	glutTimerFunc(20,time,5);
	glutMainLoop();
}

void countone(){
	unsigned int score[16]={0};
	for(int i=0;i<200000;i++){
		int a=genSeq.seq(i);
		char b=0;
		for(int j=1;j<=15;j++){
			if(a<<j <0)
				b++;
		}
		score[b]++;
	}
	for(int i=0;i<16;i++)
		cout << "Bucket " << i << "\tscore: " << score[i] << endl;
}

void squeeze(){
	unsigned int score[2550]={0};
	for(int i=0; i<100000;i++){
		double a=1000;
		unsigned int count=0;
		do{
			a-=(double)((genSeq.Next()%254)+1)/(double)255;
			count++;
		}while(a>1);
		score[count-100]++;
	}
	for(int i=0;i<2550;i++){
		if(score[i]!=0)
			cout << "Bucket " << i << "\tscore: " << score[i] << endl;
	}
}

void bday(){
	vector<unsigned int> bucket;
	vector<unsigned int> score;
	unsigned int max=5000;
	int tries=5;
	double expected = 2.5*sqrt((float)max);

	for(int k=0; k<tries;k++){
		vector<unsigned int> tmp;
		unsigned int j;
		for(unsigned int i=0; i<max;i++){
			bool hit=false;
			unsigned int rnd=genSeq.Next()%max;
			for(j=0; j<tmp.size(); j++){
				if(tmp[j]==rnd){
					hit=true;
					break;
				}
			}
			if(!hit)
				tmp.push_back(rnd);
		}
		score.push_back(j);
	}
	double av=0;
	for(int i=0;i<tries;i++){
		av+=score[i];
	}
	av/=(tries*10);
	cout << "score: " << av << "." << endl;
	cout << "sould be greater then: " << expected << endl;
}
int main(int argc, char ** argv){
	int bla=0;
	do{
		cout << " Choose a method of analysis:" << endl;
		cout << " 1. 3D GL graph" << endl;
		cout << " 2. squeeze to 1000 (bucket scores should bell curve)" << endl;
		cout << " 3. count the 1s  (bucket scores should bell curve)(slow)" << endl;
		cout << " 4. birthday attack(slow)" << endl;
		cin >> bla;
	}while(bla<1 || bla>5);
	switch(bla){
		case 1:
			glutsim(argc, argv);
		break;
		case 2:
			squeeze();
		break;
		case 3:
			countone();
		break;
		case 4:
			bday();
		break;
	}
}