import java.util.*;

public class HookeJeevesMinimizer
{
  public int dim;
  public Vector pfExp;
  public Variable X[];

  public Vertex currV;
  public double[] hStep;
  private double rho = 0.5;
  private int nEvals;
  private int nIter = 0;

  public HookeJeevesMinimizer( int n )
  {
    dim = n;

    // Create and initialize the variables
    X = new Variable[dim];
    int i;
    for( i = 0; i < dim; i++ )
      X[i] = Variable.create( "x" + (i+1), 0.0 );
    // The first variable is called x1

    currV = new Vertex( dim );
    hStep = new double[dim];
  }

  public boolean init( String expr )
  {
    nEvals = 0;
    pfExp = XToken.compileToPostFix( expr );
    if( pfExp != null )
      return true;
    return false;
  }

  public double eval( Vertex v )
  {
    int i;

    nEvals++;
    for( i = 0; i < dim; i++ )
      X[i].setValue( v.coord[i] );
    return v.val = XToken.eval( pfExp );
  }

  public double evalX( Vertex v )
  {
    int i;

    for( i = 0; i < dim; i++ )
      X[i].setValue( v.coord[i] );
    return v.val = XToken.eval( pfExp );
  }

  public void start( Vertex v, double h )
  {
    int i;

    for( i = 0; i < dim; i++ ) {
      currV.coord[i] = v.coord[i];
      hStep[i] = v.coord[i]*h;
      if( hStep[i] == 0 )
        hStep[i] = h;
    }
    eval( currV );
    nIter = 0;
  }
  public void start( double h )
  {
    int i;

    for( i = 0; i < dim; i++ ) {
      currV.coord[i] = 0.0;
      hStep[i] = h;
    }
    eval( currV );
    nIter = 0;
  }

  public double explore( Vertex explV, double min_val )
  {
    int i, j;
    boolean improved = false;

    Vertex saveV = explV.copy();

    /* Exploratory Move */
    for( i = 0; i < dim; i++ ) {
      explV.coord[i] = saveV.coord[i] + hStep[i];
      eval( explV );
      if( explV.val < min_val ) {
        min_val = explV.val;
        improved = true;
        continue;
      }
      explV.coord[i] = saveV.coord[i] - hStep[i];
      eval( explV );
      if( explV.val < min_val ) {
        min_val = explV.val;
        improved = true;
        continue;
      }
      explV.coord[i] = saveV.coord[i];
    }
    if( improved ) {
      explV.val = min_val;
      for( i = 0; i < dim; i++ ) {
        if( explV.coord[i] <= saveV.coord[i] )
          hStep[i] = -Math.abs( hStep[i] );
        else
          hStep[i] = Math.abs( hStep[i] );
      }
    }
    return min_val;
  }

  public void next()
  {
    int i, j;
    boolean improved = false;

    nIter++;
    for( i = 0; i < dim; i++ ) {
      if( hStep[i] == 0 )
        hStep[i] = rho;
    }
    double min_val, new_val;
    Vertex explV = currV.copy();
    min_val = currV.val;
    new_val = explore( explV, min_val );
    while( new_val < min_val ) {
      Vertex disp;
      disp = explV.sub( currV );
      // System.out.println( "Displacement:" + disp.toString() );
      currV = explV;
      min_val = new_val;
      explV = currV.add( disp );
      new_val = explore( explV, min_val );
    }
    for( i = 0; i < dim; i++ ) {
      hStep[i] /= 2;
      if( hStep[i] == 0.0 )
        hStep[i] = rho;
    }
  }

  public void debugState()
  {
    System.out.println( "Iteration:" + nIter );
    System.out.println( "f" + currV.toString() + "=" + currV.val );
    System.out.println( "Number of function evaluations:" + nEvals );
    System.out.println( "" );
  }

  public int countIterations()
  {
    return nIter;
  }

  public int countFnEvals()
  {
    return nEvals;
  }

  public double[] getCurrentX()
  {
    return currV.coord;
  }

  public double getCurrentFnVal()
  {
    return currV.val;
  }

  public static void main( String args[] )
  {
    int n = 25;
    String expr = "100*(x2-x1*x1)^2+(1-x1)^2";

    HookeJeevesMinimizer hjm = new HookeJeevesMinimizer( 2 );
    if( hjm.init( expr ) ) {
      if( args.length > 0 )
        n = Integer.parseInt( args[0] );
      double x[] = { -1.2, 1.0};
      hjm.start( new Vertex( x ), 0.5 );

      hjm.debugState();
      int i;
      for( i = 0; i < n; i++ ) {
        hjm.next();
        hjm.debugState();
      }
    }
  }
}