import java.applet.Applet;
import java.awt.*;    // import the java.awt package
import java.awt.event.*;  // import the java.awt.event package
import java.util.*;
import javax.swing.JCheckBox;



public class InsertionSort extends Applet implements ActionListener {

	/**
	 * 
	 */
	private static final long serialVersionUID = 1L;
	static int max = 10000;
	static long total = 0;
	static long npermut = 0;
	static double prob[] = new double[max+1];
	static int cases [] = new int[max+1];
	static int minCase= max;
	static int maxCase=0;
	static int n=4;
	static int m =100;
	JCheckBox muestreo;
	Label prompt;      // message that prompts user to input
	TextField input;   // input values are entered here
	Label prompt2;
	TextField input2;



static int inversions(int v[] )
{
int cont = 0;
	for(int i =0; i<v.length -1 ; i++ )
	{
		for(int j = i+1 ; j<v.length ; j++)
		{
		if(v[i] < v[j]) cont ++;
		}
}
return cont;
}

static int isortSteps(int aux[])
{
	
		int steps = 0;
		int i,j,k,x;
		
		int v[] = new int[aux.length];
		for(i=0;i < v.length; i++) v[i]=aux[i];
		

		for(i=1;i < v.length; i++)
		{
		  x = v[i];
			j = i-1;
			
			
		  while( (j > -1)&& (v[j] > x)  ){
					v[j+1] = v[j];
					j--;	
					steps+=3;
					
			}
			steps++;
			
			v[j+1] = x;
			
			
		}
		steps += (4*v.length)-3;
		
		return steps;
		
	}



	
static void swap (int v[], int i, int j) {
	int	t;
	t = v[i];
	v[i] = v[j];
	v[j] = t;
}


	
static void permASR (int v[], int n , int m)
{
	Random gen = new Random();
	int k = 0;
	int pos;
	for(int j=0; j<m;j++)
	{
		for(int z=0; z<n;z++)v[z] = z+1;	
		for(int i = 0; i<n-1;i++)
		{		
			pos = gen.nextInt(n-i) + i;
			swap(v,i,pos);
		}
		
		npermut++;
		k = isortSteps(v);
		total+=k;

		cases[k]++;
	}
}
	

static void perm (int v[],int i, int n) {

	/* this function generates the permutations of the array
	 * from element i to element n-1
	 */
	int j = 0;	
	int k = 0;
	
	if (i == n) {
				
			npermut++;
		
	  		k = isortSteps(v);
			total+=k;
			cases[k]++;
			
    	
	} else

		for (j=i; j<n; j++) {


			swap (v, i, j);
			perm (v, i+1, n);
			swap (v, i, j);
		}
}
	


public void init()
   {
      prompt = new Label( "Enter n:" );
      add( prompt );  // put prompt on applet 

      input = new TextField( 2 );
      input.setText(Integer.toString(n));
		add( input );   // put input TextField on applet
		
		muestreo = new JCheckBox("con muestreo");
		add(muestreo);
	  
	prompt2 = new Label( "Tamaņo de la muestra:" );
	  add( prompt2 );
	  input2 = new TextField( 3 );
      input2.setText(Integer.toString(m));
		add( input2 );  
      // "this" applet handles action events for TextField input
	  	
	  input2.addActionListener( this );
	  muestreo.addActionListener(this);
      input.addActionListener( this );
   }
   

   // process user's action in TextField input 
   public void actionPerformed( ActionEvent e )
   {
      // get the number and convert it to an integer
	   
	  m = Integer.parseInt(input2.getText() );
      n = Integer.parseInt(input.getText() );
     	input.setText(Integer.toString(n));  
     	input2.setText(Integer.toString(m));  
     	repaint(); 
     	if(muestreo.isSelected())
     		{
     		input2.setVisible(true);
     		prompt2.setVisible(true);
     		}
     	else {input2.setVisible(false);
     	prompt2.setVisible(false);
     	}
   }	
	
	public void paint(Graphics g) {
		
		double desviacion = 0;
		double promedio = 0;
				
		int k = 0;
	 	int v[] = new int[n];
		total = 0;
		npermut = 0;
		minCase=max;
		maxCase=0;	
		
		for(k=0; k<max+1; k++) {
			cases[k] = 0;
		}
		if(muestreo.isSelected())
     	{	
     		permASR(v,n,m);
     	}else
     	{
     		for(int z=1;z<=v.length ;z++) v[z-1] = z;	
			perm(v,0,n);
     	}
		
		
		
		
		for(k=0; k<max+1; k++){
					prob[k] = (double)cases[k]/  (double)npermut;
					if (( cases[k] != 0) && (minCase > k)) minCase = k;
					if (( cases[k] != 0) && (maxCase < k)) maxCase = k;			
		}
	
		
		int i = 0;
		g.setColor(Color.black);
		g.drawString("Probability",10,50);
		g.drawString("Steps",350,340);
		g.drawString("n = "+n,155,50);
		g.drawString("Number of permutations = "+ npermut,155,65);
		g.drawString("Average number of steps =  " + +((double) total)/((double)npermut) ,50,380);
		int y = 80;
		promedio =  ((double) total)/((double)npermut);
		for(i=minCase; i <= maxCase; i++) {
			if ( cases[i] != 0){
				y += 15;
				g.drawString("P("+i+")="+prob[i]+" ["+cases[i]+"]",300,y);
				desviacion = desviacion + (cases[i] - promedio)*(cases[i] - promedio);
			}
		}
		desviacion = desviacion/(double)total;
		y += 50;
		g.drawString("DESVIACION"+desviacion,300,y);

		g.setColor(Color.red);
		g.drawLine(50,50,50,320);
		g.drawLine(50,320,350,320);	
		
		g.setColor(Color.black);
		
		g.drawString("1.0", 10, 70);
		g.drawString("0.8", 10, 120);
		g.drawString("0.6", 10, 170);
		g.drawString("0.4", 10, 220);
		g.drawString("0.2", 10, 270);
		g.drawString("0.0", 10, 320);
		
		int yf;
		int shift = (int) (200.0/(double)(maxCase-minCase+1));
		int ishift = (int) (100.0/(double)(maxCase-minCase+1));
		g.setColor(Color.blue);
		for (i=minCase; i< (maxCase+1); i=i+1){
		  yf = (int) (prob[i] *250.0) ;
			g.fillRect(50+((i-minCase)*shift),320-yf, shift, yf);
			g.drawString(""+i,50+ishift+((i-minCase)*shift) , 330);
		
		}
		
		
	}	
	

	
}