// (c) by Arnoldas Bagdonas RM0/1, 2000
import java.applet.*;
import java.util.*;
import java.awt.*;
import java.awt.event.ActionListener;
import java.awt.event.ActionEvent;
import java.applet.Applet;

public class pirklys extends Applet implements ActionListener 
{
    Button city, random, nearest, bubble; // Programos valdymo klavisai
    TextField max_cities;                 // Tekstiniai laukai skirti koef. ivedimui
    TextField txt_N;
    TextField txt_M;
    TextField txt_T;
    TextField txt_a;
    TextField txt_iter;
    Label label1 = new Label();           // Ivairus uzrasai
    Label label2 = new Label();
    Label label3 = new Label();
    Label label4 = new Label();
    Label best = new Label();
    Label old = new Label();
    Label curent = new Label();
    Label vizual = new Label();
    // Konstantos, kurias gauna klavisai
    static final String CREATE = "create";  // Sukuriamas atsitiktiniu miestu zemelapis
    static final String RAND = "random";    // Atsitiktinis miestu apejimas
    static final String NEAR = "nearest";   // Artimiausio miesto algoritmas
    static final String BUBB = "buble";     // Burbulo algoritmas
    final static Color bg = Color.lightGray; //Spalvos paneles ir juodu liniju 
    final static Color fg = Color.black;
    protected Image image;                   //Zemelapio objektas
    static int LastIndex = 10;               //Kiek miestu reikia sugeneruoti (progrmiskai keiciasi)
    static int MaxIndex = 100;               //Maksimalus miestu skaicius 
    private int miestaix[] = new int[MaxIndex+1]; //Miestu X
    private int miestaiy[] = new int[MaxIndex+1]; //miestu Y koordinates
    private int sarisis[] = new int[MaxIndex+1];  //Miestu apejimo tvarkos masyvai, naudojami skaiciavimuose
    private int senas[] = new int[MaxIndex+1];
    private int kopija[] = new int[MaxIndex+1];
    private int vaizdas[] = new int[MaxIndex+1];
    private int geras[] = new int[MaxIndex+1];

    private int busena = 0;                  // Algoritmo busena, rekalinga norint teisingai nupiesti ekrane matoma vaizdeli
    private boolean sa=false;		     // Jei SA algoritmas vykdomas true, kitaip false
    private int NN=0;                        // Koef. N, T, M, a ir ju kopijos
    private int MM=0;
    private double TT=0;
    private double a=0.99;
    private double min=0;
    private int N=0;
    private int M=0;
    private double T=0;
    private int ii=0;                        //papildomi kintamieji
    private int jj=0;
    private int k=0;
  public void init()
    {
// Inicializuojami visi naudojami objektai
      setBackground(bg);
      setForeground(fg);
      image= this.getImage(this.getDocumentBase(),
                           this.getParameter("map"));

      max_cities = new TextField(4);
      max_cities.setText("10"); 
      add(max_cities);

      txt_N = new TextField(4);
      txt_N.setText("100"); 
      add(txt_N);
      txt_M = new TextField(4);
      txt_M.setText("10"); 
      add(txt_M);
      txt_T = new TextField(4);
      txt_T.setText("50");
      add(txt_T);
      txt_a = new TextField(4);
      txt_a.setText("0.99"); 
      add(txt_a);

      txt_iter = new TextField(4);
      txt_iter.setText("100"); 
      add(txt_iter);

      city = new Button();
      city.setLabel("cities");
      city.setActionCommand(CREATE);

      random = new Button();
      random.setLabel("random");
      random.setEnabled(false);
      random.setActionCommand(RAND);


      nearest = new Button();
      nearest.setLabel("nearest");
      nearest.setEnabled(false);
      nearest.setActionCommand(NEAR);

      bubble = new Button("bubble");
      bubble.setEnabled(false);
      bubble.setActionCommand(BUBB);

      //Listen for actions on buttons 1 and 3.
      city.addActionListener(this);
      random.addActionListener(this);
      nearest.addActionListener(this);
      bubble.addActionListener(this);

      //Add Components to the Applet, using the default FlowLayout. 
      add(city);
      add(random);
      add(nearest);
      add(bubble);
      label1 = new Label();
      label1.setText("N = ");
      label2 = new Label();
      label2.setText("M = ");
      label3 = new Label();
      label3.setText("T = ");
      label4 = new Label();
      label4.setText("a = ");
      vizual.setText("iter");
      add(vizual);

      old = new Label();
      old.setText("Old length = xxxx.xx");

      best = new Label();
      best.setText("The best length = xxxx.xx");

      curent = new Label();
      curent.setText("The curent length = xxxx.xx");

      add(label1);
      add(label2);
      add(label3);
      add(label4);

      add(best);
      add(old);
      add(curent);

   }
   public double atstumas(int i, int j)
   {
     return  Math.sqrt((miestaix[sarisis[i]]-miestaix[sarisis[j]])*(miestaix[sarisis[i]]-miestaix[sarisis[j]]) + (miestaiy[sarisis[i]]-miestaiy[sarisis[j]])*(miestaiy[sarisis[i]]-miestaiy[sarisis[j]]));
   } 
   public double ilgis()
   {
     double s=0;
     for (int i=1; i<=LastIndex+1; i++){ s += atstumas(i-1,i); }
     return  s;
   } 

   public void pakeitimas(int i, int j)
   {
     int k=sarisis[i];
     sarisis[i]=sarisis[j];
     sarisis[j]=k;
   } 

   public double intraukti(int i, int nr, int max)
   {
     int old=sarisis[nr];
     for (int j=max; j>=i; j--){ sarisis[j+1]=sarisis[j]; }
     sarisis[i]=old;
     double s=0;
     for (int j=1; j<=max+2; j++){ s+=atstumas(j-1,j); }
     return s;
   } 
   public void SA(Graphics g)
   {
     NN=Integer.parseInt(txt_N.getText(), 10);
     MM=Integer.parseInt(txt_M.getText(), 10);
     TT=Float.valueOf(txt_T.getText()).floatValue(); 
     a=Float.valueOf(txt_a.getText()).floatValue(); 
     min=ilgis();
     N=0;
     M=0;
     T=TT;
     ii=0;
     jj=0;
     int iterac=Integer.parseInt(txt_iter.getText(), 10);
     double ilg=0;
     double delta=0;
     double min=ilgis();
     double E=0;
     for (k=0; k<=MaxIndex; k++){ geras[k]=sarisis[k]; }
     for (int i=1; i<iterac; i++){
        ii=LastIndex+1;
        jj=LastIndex+1;
        while(ii>LastIndex){ ii=(int)Math.round(1+LastIndex*Math.random());}
        while(jj>LastIndex){ jj=(int)Math.round(1+LastIndex*Math.random());}
        for (k=0; k<=MaxIndex; k++){ sarisis[k]=kopija[k]; }
        E=ilgis();
        pakeitimas(ii, jj);
        ilg=ilgis();
        delta=ilg-E;
        if(delta<0){
          if(min>ilg){min=ilg; for (k=0; k<=MaxIndex; k++){ geras[k]=sarisis[k]; }}
          M++;
          N++;
          for (k=0; k<=MaxIndex; k++){ kopija[k]=sarisis[k]; }
          curent.setText("The curent length = " + ilg);
          best.setText("The best length = " + min);
        }
        if (delta>0){
           if(Math.exp(-(double)delta/T) > Math.random()){
             N++;
             for (k=0; k<=MaxIndex; k++){ kopija[k]=sarisis[k]; }
             curent.setText("The curent length = " + ilg);         
           }
        }
        if((N>=NN)|(M>=MM)){
          N=0;
          M=0;
          T=a*T;
        }
      
     }
     image.flush(); paint(g);
   } 
   public void actionPerformed(ActionEvent e) {
//Cia gaunamas valdymas, kai paspaudziamas koks nors klavisas, koks klavisas nurodo command elute

        Graphics g=getGraphics();
        String command = e.getActionCommand();
        double xx;
        long xi;
        int i;
        int j;
        int nr;
        double min;
        double rez;
        if (command == CREATE) {
        LastIndex=Integer.parseInt(max_cities.getText(), 10);
         for (i=0; i<=LastIndex; i++){
                xx=360*Math.random();
                xi=Math.round(xx);
                miestaix[i]=(int)xi;
                xx=100+260*Math.random();
                xi=Math.round(xx);
                miestaiy[i]=(int)xi;
            }
          random.setEnabled(true);
          nearest.setEnabled(true);
          bubble.setEnabled(true);
          old.setText("Old length = xxxx.xx");
          best.setText("The best length = xxxx.xx");
          curent.setText("The curent length = xxxx.xx");
          busena=1;
          image.flush();
	  paint(g);
        }
        if (command == RAND) { 
          random.setEnabled(false);
          nearest.setEnabled(false);
          bubble.setEnabled(false);
          for (i=0; i<=LastIndex; i++){ sarisis[i]=i; }
          sarisis[LastIndex+1]=0;
          for (k=0; k<=MaxIndex; k++){ senas[k]=sarisis[k]; }
          for (k=0; k<=MaxIndex; k++){ kopija[k]=sarisis[k]; }
          for (k=0; k<=MaxIndex; k++){ vaizdas[k]=sarisis[k]; }
          old.setText("Random length = " + ilgis() );
          SA(g);
          busena=2;
          image.flush();
          paint(g);
          random.setEnabled(true);
          nearest.setEnabled(true);
          bubble.setEnabled(true);
        }

        if (command == NEAR) { 
          random.setEnabled(false);
          nearest.setEnabled(false);
          bubble.setEnabled(false);
          for (i=0; i<=LastIndex; i++){ sarisis[i]=i; }
          sarisis[LastIndex+1]=0;

          for (i=1; i<=LastIndex-1; i++){
             min=atstumas(i-1, i);
             nr=i;
             for (j=i+1; j<=LastIndex; j++){
               if (min>atstumas(i-1, j)){min=atstumas(i-1,j); nr=j;}
             }
             j=sarisis[nr];
             sarisis[nr]=sarisis[i];
             sarisis[i]=j;
          }
          sarisis[LastIndex+1]=0;
          for (k=0; k<=MaxIndex; k++){ senas[k]=sarisis[k]; }
          for (k=0; k<=MaxIndex; k++){ kopija[k]=sarisis[k]; }
          old.setText("Nearest length = " + ilgis() );
          for (k=0; k<=MaxIndex; k++){ vaizdas[k]=sarisis[k]; }
          SA(g);
          busena=3;
          image.flush();
	  paint(g);
          random.setEnabled(true);
          nearest.setEnabled(true);
          bubble.setEnabled(true);
        }

        if (command == BUBB) { 
          random.setEnabled(false);
          nearest.setEnabled(false);
          bubble.setEnabled(false);
          for (i=0; i<=LastIndex; i++){ sarisis[i]=i; }
          sarisis[LastIndex+1]=sarisis[3];
          sarisis[3]=0;
          for (k=0; k<=MaxIndex; k++){ senas[k]=sarisis[k]; }
          for (k=0; k<=MaxIndex; k++){ kopija[k]=sarisis[k]; }
          //Burbulo pletimas
          for (i=3; i<=LastIndex; i++){
              for (k=0; k<=MaxIndex; k++){ sarisis[k]=senas[k]; }
            min=intraukti(1,i+1,i);
            nr=1;
            for (j=1; j<=i; j++){
              for (k=0; k<=MaxIndex; k++){ sarisis[k]=senas[k]; }
              rez=intraukti(j,i+1,i);
              if (min>rez){min=rez; nr=j;}
            }
            for (k=0; k<=MaxIndex; k++){ sarisis[k]=senas[k]; }
            rez=intraukti(nr,i+1,i);
          for (k=0; k<=MaxIndex; k++){ senas[k]=sarisis[k]; }
          }
          for (k=0; k<=MaxIndex; k++){ senas[k]=sarisis[k]; }
          for (k=0; k<=MaxIndex; k++){ kopija[k]=sarisis[k]; }
          old.setText("Bubble length = " + ilgis() );
          for (k=0; k<=MaxIndex; k++){ vaizdas[k]=sarisis[k]; }
          SA(g);
          busena=4;
          image.flush();
	  paint(g);
          random.setEnabled(true);
          nearest.setEnabled(true);
          bubble.setEnabled(true);
        }

    }
  public void destroy()
    {
      image.flush();
    }
  public void update(Graphics g)
    {
      paint(g);
    }
  public void paint(Graphics g)
    {
//Cia vyksta vaizdelio ekrane paisymas
//Sis metodas skvieciamas, kai reikia vaizdeli perpiesti (pslinkus tekstui ekrane ir pan.)
      g.drawImage(image, 0, 0, this);
      g.drawRect(0, 0, 359, 359);
      g.drawRect(0, 0, 359, 100);
      g.setColor(bg);
      g.fillRect(1, 1, 358, 99);
      g.setColor(fg);
      g.drawString("(c) Arnoldas Bagdonas RM0/1 2000", 25, 350);
      city.reshape(5, 5, 40, 23);
      max_cities.reshape(50, 5, 40, 23);
      random.reshape(5, 35, 85, 17);
      nearest.reshape(5, 55, 85, 17);
      bubble.reshape(5, 75, 85, 17);

      label1.reshape(110, 5, 55, 17);
      label2.reshape(110, 27, 55, 17);
      label3.reshape(110, 49, 55, 17);
      label4.reshape(110, 71, 55, 17);

      txt_N.reshape(140, 5,  40, 23);
      txt_M.reshape(140, 27, 40, 23);
      txt_T.reshape(140, 49, 40, 23);
      txt_a.reshape(140, 71, 40, 23);
      vizual.reshape(190, 5, 90, 23);
      txt_iter.reshape(250, 5, 50, 23);

      old.reshape(190, 35, 165, 17);
      best.reshape(190, 55, 165, 17);
      curent.reshape(190, 75, 165, 17);

// Toliau vizualizuojame, jei reikia tai kas yra padaryta
      if (busena > 0){
       g.setColor(Color.blue);
         for (int i=0; i<LastIndex; i++){
           g.fillArc(miestaix[i]-2, miestaiy[i]-2, 5, 5, 0, 360); // x, y, w, h
         if (busena >1){            
            for (i=1; i<=LastIndex+1; i++){
               g.setColor(Color.red);
               g.drawLine(miestaix[geras[i-1]]-2, miestaiy[geras[i-1]]-2,miestaix[geras[i]]-2, miestaiy[geras[i]]-2);
               g.setColor(Color.blue);
               g.drawLine(miestaix[vaizdas[i-1]], miestaiy[vaizdas[i-1]],miestaix[vaizdas[i]], miestaiy[vaizdas[i]]); // x1, y1, x2, y2
               g.fillArc(miestaix[vaizdas[i-1]]-2, miestaiy[vaizdas[i-1]]-2, 5, 5, 0, 360); // x, y, w, h
            }
         }
         }
      }
    }

}