//package MCMC;

import java.util.Vector;

public class LCG {

	public double[] random_numbers; //contains "U[0,1]"-pseudo-random numbers
	public int[] int_random_numbers; //contains the sequence of integer random numbers
	
	
	public LCG(int z0, int a,int c,int m, int how_many ){
	this.generate(z0,a,c,m,how_many);
	}
	
	/*
	 * generates a sequence of pseudo-random numbers using the linear congruential method
	 * 
	 */
	public void generate(int z0, int a,int c,int m, int how_many ){
		this.random_numbers=new double[how_many];
		this.int_random_numbers= new int[how_many];
		int z=z0;
		/*
		 * generate pseudo-random  numbers in {0,...,m-1}
		 */
		for(int i=0; i<int_random_numbers.length; i++){
			z=(a*z+c)%m;
			int_random_numbers[i]=z;
		}
		
		/*
		 * scale the pseudo-random  numbers to the interval [0,1)
		 */
		for(int i=0; i<random_numbers.length; i++){
			random_numbers[i]=((double)int_random_numbers[i])/((double)m);
		}
	}
	
	//method to print the [0,1] pseudo-random numbers to Stdout
	public void print_random_numbers(){
		
		for(int i=0; i<random_numbers.length; i++){
			System.out.println(random_numbers[i]);
		}
	}
       //	method to print the {0,...,m-1} pseudo-random numbers to Stdout
       public void print_int_random_numbers(){
		
		for(int i=0; i<int_random_numbers.length; i++){
			System.out.println(int_random_numbers[i]);
		}
	}
	
/*
 * prints all pairs of consecutive [0,1] pseudo-random numbers in the sequence
 * into a usual coordinate system
 */
	public void print_point_pattern(){
		
		//set up the graphics for the coordinate system
		ClassCanvas c = new ClassCanvas(510,510);
		c.setSize(510,510);
		javax.swing.JFrame j = new javax.swing.JFrame();	
		c.drawLine(10,0,10,500);
		c.drawLine(10,500,500,500);
		c.setColor(java.awt.Color.red);
		
		//print the points into the coordinate system
		for(int i=0; i<random_numbers.length-1; i++){
			
			// we need a little transformation from points to image coordinates
			int x=(int) Math.round(500.0*random_numbers[i]);
			int y=(int) Math.round(500.0*random_numbers[i+1]);
			
			x=x+10;
			y=(-1)*(y-500);
			
			c.drawRectFilled(x,y,5,5);
			
		}	
		//some more stuff for plotting 
		c.repaint();		
		j.getContentPane().add(c);
		j.pack();
		j.show();
		
	}
	
	//prints a quantile-quantile plot of the pseudo-random numbers 
	// y-axis: empirical quantiles,  x-axis: U[0,1] quantiles
	public void QQ_plot(){
		
		/*
		 * get the empirical quantiles
		 */
			Vector QQ= new Vector(); // here we will store the points to plot
		
		//number of different quantiles considered is the lenght of the random number vector
		// Now we compute the empirical quantiles for every single alpha.
		for(int k=1; k<random_numbers.length; k++){
			
			double alpha=k*1.0/(double)random_numbers.length;
			
			//get the smallest pseudo-random number
			double x=next_bigger_rnd_number(0);
			double n=(double) random_numbers.length;
			
			//This while loop will be left if x=min{x : (relative frequency of x_i<=x)>=alpha } 
			while(((double)no_of_prns_leq_than(x))/n <alpha){
				x=next_bigger_rnd_number(x);
			}
			
			//add the just found alpha-quantile to QQ
			//note: the theoretical alpha quantile  is just alpha itself (due to uniform distribution)
			double[] newQQ= new double[]{alpha, x};
			QQ.add(newQQ);
			}
		
		/*
		 * now we plot the points
		 */
		ClassCanvas c = new ClassCanvas(510,510);
		c.setSize(510,510);
		javax.swing.JFrame j = new javax.swing.JFrame();	
		c.drawLine(10,0,10,500);
		c.drawLine(10,500,500,500);
		c.setColor(java.awt.Color.red);
		
		for(int i=0; i<QQ.size(); i++){
			
			int x=(int) Math.round(500.0*( (double[]) QQ.get(i))[0]);
			int y=(int) Math.round(500.0*( (double[]) QQ.get(i))[1]);
			
			x=x+10;
			y=(-1)*(y-500);
			
			c.drawRectFilled(x,y,5,5);
			
		}	
		c.repaint();		
		j.getContentPane().add(c);
		j.pack();
		j.show();
		
	}
	
	public double[] sort_rnd_numbers(){
		double[] sorted= new double[this.random_numbers.length];
		double x=next_bigger_rnd_number(0);
		sorted[0]=x;
		for(int i=1; i<this.random_numbers.length; i++){
			x=next_bigger_rnd_number(x);
			sorted[i]=x;
		}
		return sorted;
		
	}
	
	/*
	 * returns the next bigger pseudo-random number in the sequence
	 */
	public double next_bigger_rnd_number(double x){
		double current=2.0;
		for(int i=0; i<this.random_numbers.length; i++){
			if(this.random_numbers[i]>x && this.random_numbers[i]<current){
				current=this.random_numbers[i];
			}
		}
		if(current==2.0){
			return x;
		}
		else{
			return current;
		}
	}
	


	/*
	 * returns the number of pseudo-random numbers less or equal to x
	 */
	public int no_of_prns_leq_than(double x){
		int count=0;
		for(int i=0; i<random_numbers.length; i++){
			if(random_numbers[i]<=x){
				count++;
				}
		}
		
		return count;
	}
	
	
	/*
	 * Implements the chi square goodness of fit test for uniform distribution
	 * see e.g. Statistik II chapter 5.
	 * r: number of classes
	 * The test statistic is compared to "quantile".
	 * The user needs to enter the 1-gamma quantile of the chi-squared distribution
	 * with r-1 degrees of freedom in order to obtain the test level gamma.
	 */
	public void chi_square_test(double r, double quantile){
		double T=0;
		double n=(double) this.random_numbers.length;
		
		for(int j=1; j<=r; j++ ){
			T=T+Math.pow(count_rnds_in_interval(((double)(j-1))/r,((double)j)/r)-n/r,2)/(n/r);
		}
		System.out.println("T="+T);
		if(T>quantile){
			System.out.println("reject H0: equal class probabilities");
		}
		else{
			System.out.println("do not reject H0: equal class probabilities");
		}
	}
	//returns the number of pseudo-random numbers in  the interval (lower_bound,upper_bound]
	public int count_rnds_in_interval(double lower_bound, double upper_bound){
		int count=0;
		for(int i=0; i<random_numbers.length;i++){
			if(lower_bound<this.random_numbers[i] && this.random_numbers[i]<=upper_bound){
				count++;
			}	
		}
		return count;	
	}
	
/*
 * Here we finally have our main program
 */
	public static void main(String[] args) {
		//parameters for the LCG
		int z0=5;
		int a=137; 
		int c=1;
		int m=256;
		int how_many=256;
		
		//generate an object of the class LCD
		LCG generator=new LCG(z0,a,c,m,how_many);
		
		generator.print_int_random_numbers();
		generator.print_random_numbers();
		generator.print_point_pattern();
		generator.chi_square_test(11,18.31);
		
		//Note: the empirical quantiles are not computed efficiently by the method above
		//=>if there are too many random numbers the program might not terminate within 
		//reasonable time.
		
		generator.QQ_plot();
		
	}

}