/*
 Programa para estimar el tiempo
  promedio del InsertionSort para 
 permutaciones con repeticion para n > 10.
 
 CARLOS PIARPUEZAN CODIGO: 256629 */

import java.util.Random;
import java.awt.*; 
import javax.swing.*;
import java.awt.event.*;

public class InSortAverageECR extends JFrame implements ActionListener
{
	public JPanel contentPane;
    public JPanel controlesPanel;
    public JPanel salidaPanel;
	private int [] vecAuxiliar;
	private JLabel MensajeInicio;
	private JTextField longitud;
    private JButton ejecutar;
    private JTextArea output;
    public ScrollPane salida;
    static double probabilidad[] = new double[10000];
	static int casos_posibles [] = new int[10000];
	static long npermut = 0;
	static double promedio = 0;
	static int minimo;
	static int maximo;
		
	private Container crearContentPane() 
	{
		contentPane = new JPanel();
		controlesPanel = new JPanel();
		salidaPanel = new JPanel();
        MensajeInicio = new JLabel();
        longitud = new JTextField();
        ejecutar = new JButton("EJECUTAR");
        ejecutar.addActionListener(this);
        salida = new ScrollPane();
        output = new JTextArea();
        output.setEditable(false);
        output.append("Permutaciones con Repetición \n");
		output.append("Por defecto 10000 iteraciones \n");
        MensajeInicio.setText("DIGITE LA LONGITUD DEL ARREGLO:");

		contentPane.setLayout(new GridLayout(2,1));
		controlesPanel.setLayout(new GridLayout(3,1));
		controlesPanel.add(MensajeInicio);
       
		controlesPanel.add(longitud);
        
		controlesPanel.add(ejecutar);
	
        salidaPanel.setLayout(new GridLayout(1,1)); 
        salida.add(output);
        salidaPanel.add(salida);
        contentPane.setBorder(BorderFactory.createEmptyBorder(20,20,20,20));
        contentPane.add(controlesPanel);
        contentPane.add(salidaPanel);
		return contentPane;
    }
    
    static int insertionSortSteps(int vecAuxiliar[])
 	{
		int steps = 0;
		int i,j,k,x;
		int v[] = new int[vecAuxiliar.length];
		for(i=0;i < v.length; i++) v[i]=vecAuxiliar[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 perm (int v[],int j, int n) 
	{
		if(j < n)
		{
			for(int i = 0; i < n; i++)
			{
				v[j] = i + 1;
				perm(v, j + 1, n);
			}
		}
		else
		{
			npermut++;
			j = insertionSortSteps(v);
			promedio+=j;
			casos_posibles[j]++;
		}
	}
	
	public void actionPerformed(ActionEvent e)
	{
		if (e.getSource() == ejecutar)
        {
        	int n = Integer.parseInt(longitud.getText());
			int k = 0;
	 		int v[] = new int[n];
	 		int[] vecAuxiliar = new int[n];
			promedio = 0;
			npermut = 0;
			minimo=1000;
			maximo=0;
			output.setText("");	
		
			for(k=0; k<1001; k++) 
			{
				probabilidad[k] = 0.0;
				casos_posibles[k] = 0;
			}
		
			for(k=0; k<n; k++)
			{
				v[k]=k+1;
			} 
		
			Random rand = new Random() ;
			for(int times = 0; times < 10000; times++)
			{
			 	for(int i = 0; i < n; i++)
                vecAuxiliar[i] = rand.nextInt(n) + 1;

            	npermut++;
            	k = insertionSortSteps(vecAuxiliar);
            	promedio += k;
            	casos_posibles[k]++;
        	}
		
			for(k=0; k<1001; k++)
			{
				probabilidad[k] = (double) casos_posibles[k] / (double) npermut;
				if (( casos_posibles[k] != 0) && (minimo > k)) minimo = k;
				if (( casos_posibles[k] != 0) && (maximo < k)) maximo = k;
			}
			
			int i = 0;
			for(i=minimo; i <= maximo; i++) 
			{
		  		if (casos_posibles[i] != 0)
		  		{
					output.append(i+" Pasos en. "+casos_posibles[i]+" Casos \n"+"Probabilidad es: "+probabilidad[i]);
					output.append("\n");
				}
			}
			
			if (casos_posibles[minimo] != 0)
				output.append("N_Minimo pasos es:  "+minimo+"\n");
			if (casos_posibles[maximo] != 0)
				output.append("N_Maximo pasos es:  "+maximo+"\n");
			promedio=promedio/npermut;
			output.append("Pasos promedio: "+promedio+"\n");
		}
	}
	
	private static void crear_y_MostrarGUI()
    {
        JFrame.setDefaultLookAndFeelDecorated(true);

        //Crea y configura la ventana
        JFrame frame = new JFrame("PROGRAMA PRINCIPAL: InSortAverage");
        frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        //El tamaño de la ventana no es redefinible
        frame.setResizable(false);

        //Crea y configura el contentenido del panel
        InSortAverageECR demo = new InSortAverageECR();
        frame.setContentPane(demo.crearContentPane());

       // tamaño de la ventana
        frame.setSize(300, 250);
        frame.setVisible(true);
    }
    
    public static void main(String[] args)
    {
      System.out.println("Cargando Componentes Espere...");
      crear_y_MostrarGUI();
    }
}