import java.util.*;

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

  public Vertex V[];
  public Vertex midV;
  public int nIter = 0;

  public NelderMeadMinimizer( 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

    // Create and initialize the vertices
    V = new Vertex[dim+1];
    for( i = 0; i <= dim; i++ )
      V[i] = new Vertex( dim );

    midV = new Vertex( dim );
  }

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

  public double eval( Vertex v )
  {
    int i;

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

  public double getLongestEdge()
  {
    int i, j;
    double d, dmax;

    dmax = 0.0;
    for( i = 0; i <= dim; i++ )
      for( j = i + 1; j <= dim; j ++ ) {
        d = V[i].distanceTo( V[j] );
        if( dmax < d )
          dmax = d;
      }

    return dmax;
  }

  public void order()
  {
    int i, j;

    for( i = 0; i <= dim; i++ )
      eval( V[i] );

    // Bubble sort to arrange the vertices in increasing function
    // value order
    for( j = 0; j < dim; j++ ) {
      boolean no_exch = true;
      for( i = dim; i > j; i-- )
        if( V[i].val < V[i-1].val ) {
          Vertex v;
          v = V[i];
          V[i] = V[i-1];
          V[i-1] = v;
          no_exch = false;
        }

      if( no_exch )
        break;
    }
  }

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

    for( i = 0; i < dim; i++ )
      V[dim].coord[i] = v.coord[i];

    for( i = 0; i < dim; i++ ) {
      for( j = 0; j < dim; j++ )
        V[i].coord[j] = v.coord[j];
      V[i].coord[i] = v.coord[i] + h;
    }
    nIter = 0;
  }
  public void start( double h )
  {
    int i;

    for( i = 0; i < dim; i++ )
      V[dim].coord[i] = 0.0;

    for( i = 0; i < dim; i++ )
      V[i].coord[i] = h;
    nIter = 0;
  }

  public String shrink()
  {
    int i;
    for( i = 1; i <= dim; i++ )
      V[i] = V[i].combine( 0.5, V[0] );
    return "SHRINKAGE";
  }

  public String next()
  {
    int i, j;
    Vertex refV;
    order();
    nIter++;
    for( i = 0; i < dim; i++ ) {
      midV.coord[i] = 0.0;
      for( j = 0; j < dim; j++ )
        midV.coord[i] += V[j].coord[i];
      midV.coord[i] /= dim;
    }

    refV = V[dim].combine( -1.0, midV );
    eval( refV );
    if( refV.val < V[0].val ) {
      Vertex expV;
      expV = V[dim].combine( -2.0, midV );
      eval( expV );
      if( expV.val < refV.val ) {
        V[dim] = expV;
        return "EXPANSION";
      }
      V[dim] = refV;
      return "REFLECTION";
    }
    if( refV.val > V[dim].val ) {
      Vertex icV;
      icV = V[dim].combine( 0.5, midV );
      eval( icV );
      if( icV.val < V[dim].val )
        V[dim] = icV;
      else
        return shrink();
      return "INSIDE CONTRACTION";
    }
    if( refV.val > V[dim-1].val ) {
      Vertex ocV;
      ocV = V[dim].combine( -0.5, midV );
      eval( ocV );
      if( ocV.val < refV.val )
        V[dim] = ocV;
      else
        return shrink();
      return "OUTSIDE CONTRACTION";
    }
    V[dim] = refV;
    return "REFLECTION";
  }

  public void debugState()
  {
    order();
    int i;

    for( i = 0; i <= dim; i++ )
      System.out.println( "f" + V[i].toString() + "=" + V[i].val );
    System.out.println( "Longest Simplex Edge=" + getLongestEdge() );
    System.out.println( "" );
  }

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

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

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