//==============================  
//  OPTIMISATION
//  One dimensional optimisation
//  brent method with derivative
//==============================  
import java.util.*;
import java.awt.*;
import java.applet.Applet;
import java.awt.event.*;
import javax.swing.*;

//============= Function to be defined ================
class fb extends f_x
{
   public double func (double x)
   { return x*x-2*x;}
}
//===========================================================

public class NA35A
{
	 public static double SIGN(double a,double b) {return (b > 0.0 ? Math.abs(a) : -Math.abs(a));}
     public static double MAX(double a,double b) {return (a > b ? a : b);}

    public static double[] inputdata(String s)
     {
     String s1=JOptionPane.showInputDialog(s);        
     StringTokenizer token=new StringTokenizer(s1);
     int n=token.countTokens()-1;
     int m=n+1;
     double a[]=new double[m];
     int j=0;           
     while(token.hasMoreTokens())
     {
     Double ax=new Double(token.nextToken());
     a[j++]=ax.doubleValue();
     }
     return a; 
     }
     public static double df(f_x f,double x)
     {
// türev alt programı	
// df fonksiyonunun türevini hesaplar
double h0=0.0256;
int i,m;
int n=7;
//turev of a simple function
double T[][];
T=new double[n][n];
double h[];
h=new double[n];
//vector<double> h(n,0);
for(i=0;i<n;i++)
{
  h[i]=0;
  for(int j=0;j<n;j++)
    T[i][j]=0;
}
h[0]=h0;
double r=0.5;
for( i=1;i<n;i++)
{
h[i]=h0*Math.pow(r,i);
}

for(i=0;i<n;i++)
{
T[i][0]=( f.func(x + h[i]) - f.func( x - h[i]))/(2.0*h[i]);
}
for(m=1;m<n;m++)
{
  for(i=0;i<n-m;i++)
  {
  T[i][m]=(h[i]*h[i]*T[i+1][m-1] - h[i+m]*h[i+m]*T[i][m-1])/
          (h[i]*h[i]- h[i+m]*h[i+m]);
  }
}
double xx=T[0][n-1];
return xx;
}

public  static double dbrent(f_x f,double ax,double bx,double cx,double tol)
{
// ax,bx,cx is three initial guesses (bx should be located between ax and cx)
// f : function (defined with f_x abstract class)
// tol tolerance
int ITMAX=100;
double CGOLD=(3.0-Math.sqrt(5))/2.0; //altın oran
double ZEPS=1.0e-10;
	int iter;
	boolean ok1,ok2;
	double a,b,d,d1,d2,du,dv,dw,dx,e=0.0;
	d=0.0;
	double fu,fv,fw,fx,olde,tol1,tol2,u,u1,u2,v,w,x,xm;
	double xmin=bx;
	a=(ax < cx ? ax : cx);
	b=(ax > cx ? ax : cx);
	x=w=v=bx;
	fw=fv=fx=f.func(x);
	dw=dv=dx=df(f,x);
	for (iter=1;iter<=ITMAX;iter++) {
		xm=0.5*(a+b);
		tol1=tol*Math.abs(x)+ZEPS;
		tol2=2.0*tol1;
		if (Math.abs(x-xm) <= (tol2-0.5*(b-a))) {
			xmin=x;
			return xmin;
		}
		if (Math.abs(e) > tol1) {
			d1=2.0*(b-a);
			d2=d1;
			if (dw != dx)  d1=(w-x)*dx/(dx-dw);
			if (dv != dx)  d2=(v-x)*dx/(dx-dv);
			u1=x+d1;
			u2=x+d2;
			ok1 = (a-u1)*(u1-b) > 0.0 && dx*d1 <= 0.0;
			ok2 = (a-u2)*(u2-b) > 0.0 && dx*d2 <= 0.0;
			olde=e;
			e=d;
			if (ok1 || ok2) {
				if (ok1 && ok2)
					d=(Math.abs(d1) < Math.abs(d2) ? d1 : d2);
				else if (ok1)
					d=d1;
				else
					d=d2;
				if (Math.abs(d) <= Math.abs(0.5*olde)) {
					u=x+d;
					if (u-a < tol2 || b-u < tol2)
						d=SIGN(tol1,xm-x);
				} else {
					d=0.5*(e=(dx >= 0.0 ? a-x : b-x));
				}
			} else {
				d=0.5*(e=(dx >= 0.0 ? a-x : b-x));
			}
		} else {
			d=0.5*(e=(dx >= 0.0 ? a-x : b-x));
		}
		if (Math.abs(d) >= tol1) {
			u=x+d;
			fu=f.func(u);
		} else {
			u=x+SIGN(tol1,d);
			fu=f.func(u);
			if (fu > fx) {
				xmin=x;
				return xmin;
			}
		}
		du=df(f,u);
		if (fu <= fx) {
			if (u >= x) a=x; else b=x;
			//MOV3(v,fv,dv, w,fw,dw)
			{v=w;fv=fw;dv=dw;}
			//MOV3(w,fw,dw, x,fx,dx)
			{w=x;fw=fx;dw=dx;}
			//MOV3(x,fx,dx, u,fu,du)
			{x=u;fx=fu;dx=du;}
		} else {
			if (u < x) a=u; else b=u;
			if (fu <= fw || w == x) {
				//MOV3(v,fv,dv, w,fw,dw)
				{v=w;fv=fw;dv=dw;}
				//MOV3(w,fw,dw, u,fu,du)
				{w=u;fw=fu;dw=du;}
			} else if (fu < fv || v == x || v == w) {
				//MOV3(v,fv,dv, u,fu,du)
				{v=u;fv=fu;dv=du;}
			}
		}
	}
	System.out.println("maximum number of iterations are exceeded in DBRENT optimisation");
	return xmin;
}
     public static void main (String args[])  
     {  
	 String s="enter three initial guess values with a space in between xo x1 x2: ";
     double [] x0=inputdata(s);
     fb f=new fb();
     double r1= dbrent(f,x0[0],x0[1],x0[2],1.0e-8);
     s=" optimum value  : "+r1;
     String s2="Optimisation by Brent method with derivatives:";
     JOptionPane.showMessageDialog(null,s,s2,JOptionPane.PLAIN_MESSAGE);
     } 
}
