import java.util.Vector;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;

abstract class f_xj
{
abstract double func(double x[]);
}


public class gravitional_search_algorithm
{
int D;//Number of dimension(Agent's dimension)
int N;//Number of Agents
int maxiter;//iteration number
double fmin;//minimum value of a function(so far)
double fsol[]; //minimum value of an agent(mass)
double Masses[];
double Lowerbound[];
double Upperbound[];
double Lbvec[];
double Ubvec[];
double X[][];
double V[][];
double A[][];
double fitness[];
double Lb;
double Ub;
int index;
double min;
double[] dep;
double G;
f_xj ff;

     public gravitional_search_algorithm(f_xj iff,int iN,int imaxiter,double[] iLowerbound,double[] iUpperbound)
     {
	 ff=iff;    
	 Lowerbound=iLowerbound;
	 Upperbound=iUpperbound;
	 D=Upperbound.length;    
	 N=iN;
	 maxiter=imaxiter;
	 Lbvec=new double[D];    
	 Ubvec=new double[D];    
	 X=new double[N][D];
	 V=new double[N][D];
	 fitness=new double[N];
	 fsol=new double[D];
	 Masses=new double[N];
	 A=new double[N][D];
	 }

	 void initialize()
	 {
	 for(int i=0;i<N;i++)
	 {for(int j=0;j<D;j++)
	  {X[i][j]=Lowerbound[j]+((Upperbound[j]-Lowerbound[j])*Math.random());}}	 
	 }

	 // if out of bounds,shift into boundary
         double[][] simplebounds(double s[][])
	 {
	   for(int i=0;i<N;i++)
	   {for(int j=0;j<D;j++)
	   {if(s[i][j]<Lowerbound[j]){s[i][j]=Lowerbound[j];}
	    if(s[i][j]>Upperbound[j]){s[i][j]=Upperbound[j];}}}
	   return s;	 
	 }
	 
	 //if out of bounds create a random number between Lb and Ub
	 double[][] randomsimplebounds(double s[][])
	 {
	   for(int i=0;i<N;i++)
	   {for(int j=0;j<D;j++)
		{if((s[i][j]<Lowerbound[j])||(s[i][j]>Upperbound[j]))
		 {s[i][j]=Lowerbound[j]+(Upperbound[j]-Lowerbound[j])*Math.random();}}}	 
	    return s;	 
	 }
	 // Fitness Calculation
	 double[] Fitcalc(double a[][])
	 {
	 	 for(int i=0;i<N;i++)
	 	 {fitness[i]=ff.func(a[i]);}
	 	 return fitness;
	 }
	 
	 
	 // get minimum value and index from array
	 double[] getminval_index(double[] a)
	 {
	 double m=0.0;	 
	 double b[]=new double[a.length];
	 for(int i=0;i<a.length;i++)
	 {b[i]=a[i];}  
	 double minval=a[0];
	 for(int i=0;i<a.length;i++)
	 {if(a[i]<minval){minval=a[i];}}
	 for(int i=0;i<a.length;i++)
	 {if(b[i]==minval){m=i;break;}};
	 double[] dep=new double[2];
	 dep[0]=minval;
	 dep[1]=m;
	 return dep;	 
	 } 
	 
	 // get maximum value and index from array
	 double[] getmaxval_index(double a[])
	 {
	 double m=0.0;
	 double b[]=new double[a.length];
	 for(int i=0;i<a.length;i++)
	 {b[i]=a[i];}
	 double maxval=a[0];
	 for(int j=0;j<a.length;j++)
	 {if(a[j]>maxval){maxval=a[j];}}
	 for(int i=0;i<b.length;i++)
	 {if(b[i]==maxval){m=i;break;}}
	 double dep2[]=new double[2];
	 dep2[0]=maxval;
	 dep2[1]=m;
	 return dep2;	 
	 }
	 
	 // Calculation of masses for mininum solution // equation 14-18
	 double[] Calcmass(double fit[])
	 {
	 double[] dpmin=new double[2];	 
	 double[] dpmax=new double[2];		 
	 double FFmin=0.0;double FFmax=0.0;
	 double best=0.0;double worst=0.0;
	 double[] Masss =new double[fit.length];
	 double[] Massss =new double[fit.length];
	 dpmin=getminval_index(fit);
	 FFmin=dpmin[0];
	 dpmax=getmaxval_index(fit);
	 FFmax=dpmax[0];
	 best=FFmin;
	 worst=FFmax;
	 for(int i=0;i<fit.length;i++)
	 {Masss[i]=(fit[i]-worst)/(best-worst);}
	 double t=0.0;
	 for(int i=0;i<fit.length;i++)
	 {t+=Masss[i];}
	 for(int i=0;i<fit.length;i++)
	 {Massss[i]=Masss[i]/t;}
	 
	 return Massss;
	 }
	 
	int[] descendingsort_index(double[] Mass) 
	 {
		Vector<Double> vv=new Vector<Double>();
		for(int i=0;i<Mass.length;i++)
		{vv.add(Mass[i]);}
		Object[] vold=vv.toArray();
		String str="";
		double[] voldarray1=new double[Mass.length];
		for(int i=0;i<Mass.length;i++)
		{voldarray1[i]=Double.parseDouble(vold[i].toString());}
		// voldarray1 holds unsorted values
		
		Collections.sort(vv,Collections.reverseOrder());//sorts in descending order
		Object[] vsort=vv.toArray();
		String strsorted="";
		double[] vsorted=new double[Mass.length];
		for(int i=0;i<Mass.length;i++)
		{vsorted[i]=Double.parseDouble(vsort[i].toString());}
		int[] indexed=new int[Mass.length];
	    for(int i=0;i<Mass.length;i++)
		{for(int j=0;j<Mass.length;j++)
		{if(voldarray1[i]==vsorted[j])
		  {indexed[j]=i;}}}
		
		return indexed;
		 
	 }
	 // Calculation of Gravitational constant //Equation 28
	 double Gconst(int iterr)
	 {return 100.0*Math.exp(-20.0*(double)iterr/(double)maxiter);}
	 
	 public double[][] Gravfield(double[] Mass,double[][] XX,double GG)
	 {
	 double epsilon=0.001;	 
	 double[][] dummy=new double[N][D];	 
	 int[] xx=new int[N];
	 double R=0.0;
	 int[] indexed=descendingsort_index(Mass);
	 int j=0;	 
	 
	 for(int i=0;i<N;i++)
	 {for(int tt=0;tt<N;tt++)
	   {j=indexed[tt];	   
		  if(j!=i)
		  {R=Matrix.norm(Matrix.substract(X[i],X[j]));//Equation 8
		  for(int k=0;k<D;k++)
		  {dummy[i][k]+=Math.random()*Mass[j]*((X[j][k]-X[i][k])/(R*R+epsilon));} //Equation 7
		  }
	   }	 
	 }	 
	 return  Matrix.multiply(GG,dummy);	 
	 }
	 
	 double[][][] movements(double x[][],double a[][],double[][] v)
	 {
	 double[][] dummy=new double[N][D]; 	 
	 for(int i=0;i<N;i++)
	 {for(int j=0;j<D;j++)
	  {dummy[i][j]=Math.random();}};
	  v=Matrix.add(Matrix.dotproduct(dummy,v),a);//Equation (11)
	  x=Matrix.add(x,v);//Equation (12) 	 
	  for(int i=0;i<N;i++)
	  {for(int j=0;j<D;j++)
	   {X[i][j]=x[i][j];V[i][j]=v[i][j];}
	  }
	  double d3[][][]=new double[2][N][D];
	  for(int i=0;i<N;i++)
	  {for(int j=0;j<D;j++)
	     {d3[0][i][j]=X[i][j];d3[1][i][j]=V[i][j];}}
	  return d3;
	  }
	 
	 
	 
     double[][] solution()
     {
	 initialize();
	 //System.out.println(Matrix.toString(X));
	 double[][][] d4=new double[2][N][D];
	 int iter=1;    
	     while(iter<maxiter)
	     {
		 X=randomsimplebounds(X);   
		 fitness=Fitcalc(X);
	         dep=getminval_index(fitness);	     
		 min=dep[0]; 
		 index=(int)dep[1];    
		 if(iter==1)
		 {fmin=min;
		 for(int i=0;i<D;i++)
		 {fsol[i]=X[index][i];}
		 }
		 if(min<fmin)
		 {fmin=min;
		 for(int i=0;i<D;i++)
		 {fsol[i]=X[index][i];}
		 }
		     
		 Masses=Calcmass(fitness);
		 G=Gconst(iter);    
		 A=Gravfield(Masses,X,G);  
		 d4=movements(X,A,V);
		 for(int i=0;i<N;i++)
		 {for(int j=0;j<D;j++)
		  {X[i][j]=d4[0][i][j];V[i][j]=d4[1][i][j];}}
		 iter++;
		 }
	     double[][] d5=new double[2][D];
	     d5[0][0]=fmin;
	     for(int i=0;i<D;i++)
	     {d5[1][i]=fsol[i];}
	     return d5;
	    }
	    
	    
	    void toStringnew()
	    {
		double[][] dd=solution();    
		System.out.println("Optimized value = "+dd[0][0]);
		for(int i=0;i<D;i++)
		{System.out.println("x["+i+"] ="+dd[1][i]);}    
	    }


}