#ifndef PATTERNSEARCH_H
#define PATTERNSEARCH_H

#include <vec.h>
#include <cirbuffarr.h>
#include <typeop.h>
#include <print.h>

/*!
  \brief Pattern search algorithm by Hooke and Jeeves 1961.

  I modified the algorithm for a variable step length.
  This showed improvement when I used the Fibonacci golden ratio
  as the step length.

  Pattern move : 
  X[n+1] = X[n] + hstep*(X[n]-X[n-1])

*/
template< typename EXP >
class patternsearch
{
public:

  typedef typename typeop<EXP>::Tbare::Ttype T;
  typedef typename typeop<EXP>::Tbare::XItype XI;

  /** The exploratory mover. */
  EXP exp;

  /** Pattern move is X[n+1]=X[n]+hstep*(x[n]-x[n-1]) */
  T hstep;

  /** The pattern move is configured with an exploratory mover and variable step length. */
  patternsearch( EXP exp_, T hstep_=1);

  /** The previous state. */
  cirbuffarr< T > xi0;

  /** The current state as a vec for arithmetic operations. */
  vec< XI, T > xivec;

  /** Reset from the current position and keep the state. */
  void reset();

  /** New position and new state. ie a full reset. */
  void reset( T const * x0 )
    { exp.reset(x0); reset(); }


  /** One exploratory move then pattern moves. */
  void operator ++ ();

  bool const operator ! () const
    { return exp.valid; }
  
};


/*
 *---------------------------------------------------------------
 * Implementation
 */


template< typename EXP >
void patternsearch<EXP>::reset()
{ 
  exp.reset(); 
  xi0.push(exp.xi); 
  exp.move(); 
  xi0.push(exp.xi); 
}

template< typename EXP >
void patternsearch<EXP>::operator ++ ()
{
  for (bool loop=true; loop;)
  {
    xi0.push(exp.xi);
    xivec -= xi0[1];
    xivec *= hstep;
    xivec += xi0[0];
  
    exp.movelocal();

    loop = exp.evaluate();
  }
  xi0.copyto(exp.xi);
}


template< typename EXP >
patternsearch<EXP>::patternsearch( EXP exp_, T hstep_ )
  : exp(exp_), hstep(hstep_), xi0(3,exp.N), xivec(exp.xi,exp.N)
{
}


#endif