import java.applet.Applet;
import java.awt.*;    
import java.awt.event.*;  
import java.util.Random;

/*Implementacion algoritmo BucketSort*/

public class Bucketsort extends Applet  
{	
	
	static int total;
	static double promedio;
	int minFrec=100;
	int maxFrec=0;
	static int steps;
	static int n=6;
	static double frecuencia[] = new double[100000];
	static int Runs = 1000;
	static Random random = new Random();
	Button ejecutar;
	Label labelN,labelR;
	TextField ene,ere;   
	TextArea textarea=new TextArea();
	Font font1,font2;
	String outputText,outputText1;
	
	static int BucketS(double A[])
	{
		int LongVector=0;
		steps = 0;
		int i=0,j=0,k=0;
		double B[][]= new double[n][n];
		/*insertar en array auxiliar B[][]*/
	   for (k=0; k<n; k++)
		{
			j=0;
			while (B[k][j] != 0 ){
				j++;
				steps++;
				}
			steps++;
			B[(int)Math.floor(n*A[k])][j]=A[k];
		}
	   /*ordena cada fila del array auxiliar B*/
	   j=0;
	   i=0;
	   for (k=0;k<n;k++)
		{
			while (B[k][j]!=0)
			{
				j++;
			}
			LongVector=j;
			steps++;
			//A[i]=B[k][j];
			i++;
			InsertionSort(k,LongVector,B);///O(1)
		}
	
		steps+=3;
		return steps;
	}
	

	

static void InsertionSort( int k, int l,double B[][])
{
	int i;
	int j=0;
	double x;
	
	for  (i=2; i<l; i++) 
	{
  	x = B[k][i];
    j = i-1; 
    while (x<B[k][j] && j>0) 
		{
	    B[k][j+1] = B[k][j];
	    j = j-1;
	    steps=steps+3;
    }
		B[k][j+1] = x;
		steps=steps+5;
		
	}
	steps++;
};

/*Se genera el arreglo inicial A[],invoca a BucketSort*/

  public static void Perm(){
    	      			
				int r,k;
				double v[] = new double[n];
				total = 0;
				for (int j = 0; j < Runs; j++) 
				{ 
				
            	for(k=0; k < n; k++){
            		v[k]= random.nextDouble();
            	   	
            	}
				r = BucketS(v);
				frecuencia[r]++;	
                total += r;
         }     		
				promedio = ((double) total) / Runs;		       
   }
    
    

public void init()
   {
	 setLayout(null);
	 resize(650,450);
	 font1 = new Font ( "Arial",Font.BOLD,14);
	 font2 = new Font ( "TimesRoman",Font.BOLD,12);
	 
	 
	 labelN = new Label( "n:" );			    
     add( labelN );  
     ene = new TextField( 2 );
     ene.setText(Integer.toString(n)); 
	 add(ene);
	
	
     labelR = new Label( "r:" );
     add( labelR ); 
     ere = new TextField( 5 );
     ere.setText(Integer.toString(Runs));
     add( ere );   
     
     ejecutar =new Button("Ejecutar");
     this.add(ejecutar);
     add(textarea);
     

     textarea.reshape(500,30,125,325);
     labelN.reshape(50,10,20,20);
     ene.reshape(75,10,30,20);
     labelR.reshape(150,10,20,20);
     ere.reshape(175,10,60,20);
     ejecutar.reshape(300,10,125,20);

     ejecutar.addActionListener(new java.awt.event.ActionListener() {
         public void actionPerformed(ActionEvent e) {    
         	btnSol_actionPerformed(e);
         	 }

		private void btnSol_actionPerformed(ActionEvent e) {
			n = Integer.parseInt( ene.getText() );
	     	ene.setText(Integer.toString(n));  
				     	repaint(); 
								
	      Runs = Integer.parseInt( ere.getText() );
	     	ere.setText(Integer.toString(Runs));  
				     	repaint();	
		}
     });

   }


	public void paint(Graphics g) {
		
		int k,r;
		total = 0;
		minFrec=50;
		maxFrec=0;	
		double c[] = new double [5];
		
		g.setColor(new Color(224, 224,225));
	    g.fillRoundRect(5,35,480,330,10,20);
	    
		setBackground(Color.white);	
		labelR.setBackground(Color.white);
		
		outputText =  "NÚMERO DE PERMUTACIONES =  "+ Runs;
       
		for(k=0; k<1000; k++) frecuencia[k] = 0;
		
		Perm();
		textarea.setText(" ");		
		for(k = 0; k < 1000; k++){
			frecuencia[k] /= (double)Runs;
			if (( frecuencia[k] > 0.0) && (minFrec > k)){
				minFrec = k;
				c[4] = frecuencia[k];
			}
			if (( frecuencia[k] > 0.0) && (maxFrec < k)) maxFrec = k;
			if (( frecuencia[k] >0.0) && (k<999) && c[4]<frecuencia[k]) c[4] = frecuencia[k];
		}
		int i = 0;
		outputText1= "PROMEDIO=    " + +((double) total)/((double)Runs); 	
		for(i=minFrec; i <= maxFrec; i++) {
			textarea.appendText("P("+i+")="+frecuencia[i]+"\n");		
		}
		

		g.setColor(Color.black);
		g.drawLine(50,50,50,320);
		g.drawLine(50,320,480,320);	
		g.setColor(Color.black);
		
		for (k=0; k<5; k++){
			c[k]=c[4]*0.2*(k+1);
			c[k]=(double)(Math.floor(c[k]*1000))/1000;
			g.drawString(""+(double)c[k], 10, 270-(k*50));
			
		}
		g.drawString("0.0", 10, 320);
		
		
		int yf;
		int shift = (int) (450.0/(double)(maxFrec-minFrec+1));
		int ishift = (int) (100.0/(double)(maxFrec-minFrec+1));
		
		for (i=minFrec; i< (maxFrec+1); i=i+1){
		  yf = (int) (frecuencia[i]*(250.0/c[4])) ;
		  g.setColor(new Color(aleatorio(256),aleatorio(256) ,aleatorio(256)));
		  g.fillRect(50+((i-minFrec)*shift),320-yf, shift, yf);
		  g.setColor(Color.black);
		  g.drawString(""+i,50+ishift+((i-minFrec)*shift) , 330);
			}
		
		g.setFont(font2);
		g.setColor(Color.MAGENTA);
		g.drawString("Prob.",10,50);
		g.drawString("Steps",450,340);
		g.drawString("HISTOGRAMA DEL Nº COMPARACIONES", 150, 50);
		g.setColor(Color.BLUE);
		g.setFont(font1);
		g.drawString(outputText1,50,420);
		g.drawString(outputText,50,400);
	}		
	
	
	public int aleatorio (int rango){ return (( int ) (Math.random()*rango));}
	
}