import java.io.*;
import java.math.*;

class map { double[][] cities;
               public double mesafe(double x1,double x2,double y1,double y2)
               { double mesafe;
                 mesafe=Math.pow((Math.pow((x2-x1),2)+Math.pow((y2-y1),2)),0.5);
                 return mesafe;
               }
               public map(readcity x) {
               cities=new double[x.numberofcities][x.numberofcities+3];
               for(int i=0;i<x.numberofcities;i++) {
               cities[i][0]=i; //?ehrin ID si
               cities[i][1]=x.cities[i][0]; //?ehrin x koordinat?
               cities[i][2]=x.cities[i][1]; //?ehrin y koordinat?
               for(int k=3;k<(x.numberofcities+3);k++) 
               {cities[i][k]=mesafe(x.cities[i][0],x.cities[k-3][0],x.cities[i][1],x.cities[k-3][1]);}}
                                          }
             }

class readcity 
{   String dosyaismi=new String(" ");
    double[][] cities;
    int numberofcities;
    public readcity(String x) 
    {   dosyaismi=x;
        cities=Text.readDouble(x);
        numberofcities=cities.length;     
    }
}

public class ant{
	    double mindistance;
	    
        public static void quicksort(double[][] x,int y,int z){
        double[] mid=new double[3];
        double[] temp=new double[3];
        int k,j;
        k=y;
        j=z;
        mid[0]=x[(y+z)/2][0];
        mid[1]=x[(y+z)/2][1];
        mid[2]=x[(y+z)/2][2];
        do {while(x[k][2] < mid[2] & k < z) {k++;}
             while(x[j][2] > mid[2] & j > y) {j--;}
            if(k<=j){
                temp[2]=x[k][2];
                temp[1]=x[k][1];
                temp[0]=x[k][0];
                x[k][2]=x[j][2];
                x[k][1]=x[j][1];
                x[k][0]=x[j][0];
                x[j][2]=temp[2];
                x[j][1]=temp[1];
                x[j][0]=temp[0];
                k++;
                j--;
            }
            
        }while(k<=j);
        if(y<j) {
            quicksort(x,y,j);
        }
        if(k<z) {quicksort(x,k,z);}
        }
                
    public double readDistance()
    {return mindistance;}
        
	public  int[] ant_optimization(String dosya,double vaporizarion,double feramoni,int nant )
	{   double tolerans=1.0e-5;
        double dx=0.1;
        //vaporization 0-1
        double buharlasmaorani=vaporizarion; //feramonun buharlasma oranı
        //feramoni=5 (example)
        double feramon=feramoni; //feramon
        double beta=3; //
        double alfa=1; //
        double baslangicferamonu=1; //t=0 anindaki yoldaki feramon miktar?
        //int sakant=10; //iterasyon aras? korunacak maksimum kar?nca say?s?
        //int sakis; //saklanacak karınca işareti
        readcity sehir=new readcity(dosya); //şehirlerin okunması
        map bolge=new map(sehir); //mapnın hazırlanması
        double[][] feramondurumu=new double[sehir.numberofcities][sehir.numberofcities]; //yolların feramon durumunun kaydedileceği 
        double[][] deltaferamon=new double[sehir.numberofcities][sehir.numberofcities];
        //int antsayisi=1000; //koloni büyüklüğü
        int antsayisi=nant; 
        int it=0;
        int maxit=10; //maksimum iterasyon sayisi 
        int ilksehir;
        int numberofroads;
        double toplamprobability=0;
        double[][] probabilities=new double[sehir.numberofcities][sehir.numberofcities];
        double minprobability=0;
        double maxprobability=0;
        double tprobability=0;
        double mesafe;
        mindistance=0;
        double mindistanceeski=0.1;
        dx=Math.abs(mindistance-mindistanceeski);
        int minid=0;
        int[] minguzergah=new int[sehir.numberofcities];
        antorj[] antordusu=new antorj[antsayisi];
        //antorj[] sakkar=new antorj[sakant];
        numberofroads=0;
        //numberofroadsnin hesaplanması
        while (it<maxit  &&  dx>tolerans){
         mindistanceeski=mindistance;
         numberofroads=0;
        for(int i=1;i<sehir.numberofcities-1;i++){
            numberofroads=numberofroads+sehir.numberofcities-i;
        }
        numberofroads=numberofroads+1;
        //System.out.println(numberofroads);
        double[][] probabilitypasta=new double[numberofroads][3];
        
        //t=0 anındaki feramonun yollara konulması
       if(it==0){
        for(int i=0;i<(sehir.numberofcities-1);i++) {
            for(int j=i+1;j<(sehir.numberofcities);j++) {
                if(i==j){
                    feramondurumu[i][j]=0;
                }else{
                    feramondurumu[i][j]=baslangicferamonu;
                }
                          }
        }
       }
        //probability pastasinin hesaplanmasi 
            //toplam olasiligin hesaplanmasi
        for(int i=0;i<sehir.numberofcities-1;i++){
            for(int j=i+1;j<(sehir.numberofcities);j++){
                if(i!=j){
                    toplamprobability=Math.pow((feramondurumu[i][j]),alfa)*Math.pow(bolge.cities[i][j+3],-beta);
                                    }
            }
        }
        //toplamprobability=toplamprobability/2;
            //pastanin hesaplanması
        for(int i=0;i<sehir.numberofcities-1;i++){
            for(int j=i+1;j<(sehir.numberofcities);j++){
                if(i!=j){
                    probabilities[i][j]=(Math.pow((feramondurumu[i][j]),alfa)*Math.pow(bolge.cities[i][j+3],-beta))/toplamprobability;                    
                    if(bolge.cities[i][j+3]==0){
                    }
                    if(i==0 & j==1){
                        maxprobability=probabilities[i][j];
                        minprobability=probabilities[i][j];
                        probabilitypasta[0][2]=minprobability;
                        probabilitypasta[0][0]=i;
                        probabilitypasta[0][1]=j;
                        probabilitypasta[numberofroads-1][2]=maxprobability;
                        probabilitypasta[numberofroads-1][0]=i;
                        probabilitypasta[numberofroads-1][1]=j;
                    } else {
                        if(maxprobability<probabilities[i][j]) {
                            maxprobability=probabilities[i][j];
                            probabilitypasta[numberofroads-1][2]=maxprobability;
                            probabilitypasta[numberofroads-1][0]=i;
                            probabilitypasta[numberofroads-1][1]=j;
                        } else {
                        if(minprobability>probabilities[i][j]){
                            minprobability=probabilities[i][j];
                            probabilitypasta[0][0]=i;
                            probabilitypasta[0][1]=j;
                        } 
                        }
                    }
                                    }
                else {
                    probabilities[i][j]=0;
                }
            }
        }
        for(int i=1;i<numberofroads-1;i++){
            probabilitypasta[i][2]=minprobability;
        }
            //pastanin siralanmasi
        int l=0;
         for(int i=0;i<sehir.numberofcities-1;i++){
            for(int j=i+1;j<(sehir.numberofcities);j++){     
              if(i!=j){
                probabilitypasta[l][2]=probabilities[i][j];
                probabilitypasta[l][0]=i;
                probabilitypasta[l][1]=j;
               l++;
                }               
            }
         }
        //probabilitiesi siralama
        quicksort(probabilitypasta,0,numberofroads-1);
        //t=0 anında ilk antların yerleştirilmesi
        for(int i=0;i<antsayisi;i++){
            double x;
            antordusu[i]=new antorj(i,sehir.numberofcities,feramon);
            x=Math.random()*sehir.numberofcities;
            ilksehir=(int) x;
            antordusu[i].gyol[0]=ilksehir;
        }
        //antların yürümesi 
        for(int i=1;i<sehir.numberofcities;i++){
            for(int j=0;j<antsayisi;j++){
                antordusu[j].yuru(bolge,probabilitypasta,i,numberofroads);
            }
        }
        mindistance=antordusu[0].kmesafe;
        minguzergah=antordusu[0].gyol;
        for(int j=0;j<antsayisi;j++){
            if(antordusu[j].kmesafe<mindistance){
                mindistance=antordusu[j].kmesafe;
                minguzergah=antordusu[j].gyol;
            }
        }
       
        for(int j=0;j<antsayisi;j++){
            antordusu[j].ferguncel(deltaferamon);
        }
         for(int i=0;i<(sehir.numberofcities-1);i++) {
            for(int j=i+1;j<(sehir.numberofcities);j++) {
                if(i==j){
                    feramondurumu[i][j]=0;
                }else{
                    feramondurumu[i][j]=feramondurumu[i][j]*buharlasmaorani+deltaferamon[i][j];
                }
                          }
        }
            it++;  
            dx=Math.abs(mindistance-mindistanceeski);                  
        }
        return minguzergah;		
        }
}


