#include <iostream>
#include <Eigen/Geometry>
#include <bench/BenchTimer.h>
using namespace Eigen;
using namespace std;



template<typename Q>
EIGEN_DONT_INLINE Q nlerp(const Q& a, const Q& b, typename Q::Scalar t)
{
  return Q((a.coeffs() * (1.0-t) + b.coeffs() * t).normalized());
}

template<typename Q>
EIGEN_DONT_INLINE Q slerp_eigen(const Q& a, const Q& b, typename Q::Scalar t)
{
  return a.slerp(t,b);
}

template<typename Q>
EIGEN_DONT_INLINE Q slerp_legacy(const Q& a, const Q& b, typename Q::Scalar t)
{
  typedef typename Q::Scalar Scalar;
  static const Scalar one = Scalar(1) - dummy_precision<Scalar>();
  Scalar d = a.dot(b);
  Scalar absD = internal::abs(d);
  if (absD>=one)
    return a;

  // theta is the angle between the 2 quaternions
  Scalar theta = std::acos(absD);
  Scalar sinTheta = internal::sin(theta);

  Scalar scale0 = internal::sin( ( Scalar(1) - t ) * theta) / sinTheta;
  Scalar scale1 = internal::sin( ( t * theta) ) / sinTheta;
  if (d<0)
    scale1 = -scale1;

  return Q(scale0 * a.coeffs() + scale1 * b.coeffs());
}

template<typename Q>
EIGEN_DONT_INLINE Q slerp_legacy_nlerp(const Q& a, const Q& b, typename Q::Scalar t)
{
  typedef typename Q::Scalar Scalar;
  static const Scalar one = Scalar(1) - epsilon<Scalar>();
  Scalar d = a.dot(b);
  Scalar absD = internal::abs(d);
  
  Scalar scale0;
  Scalar scale1;
  
  if (absD>=one)
  {
    scale0 = Scalar(1) - t;
    scale1 = t;
  }
  else
  {
    // theta is the angle between the 2 quaternions
    Scalar theta = std::acos(absD);
    Scalar sinTheta = internal::sin(theta);

    scale0 = internal::sin( ( Scalar(1) - t ) * theta) / sinTheta;
    scale1 = internal::sin( ( t * theta) ) / sinTheta;
    if (d<0)
      scale1 = -scale1;
  }

  return Q(scale0 * a.coeffs() + scale1 * b.coeffs());
}

template<typename T>
inline T sin_over_x(T x)
{
  if (T(1) + x*x == T(1))
    return T(1);
  else
    return std::sin(x)/x;
}

template<typename Q>
EIGEN_DONT_INLINE Q slerp_rw(const Q& a, const Q& b, typename Q::Scalar t)
{
  typedef typename Q::Scalar Scalar;
  
  Scalar d = a.dot(b);
  Scalar theta;
  if (d<0.0)
    theta = /*M_PI -*/ Scalar(2)*std::asin( (a.coeffs()+b.coeffs()).norm()/2 );
  else
    theta = Scalar(2)*std::asin( (a.coeffs()-b.coeffs()).norm()/2 );
  
  // theta is the angle between the 2 quaternions
//   Scalar theta = std::acos(absD);
  Scalar sinOverTheta = sin_over_x(theta);

  Scalar scale0 = (Scalar(1)-t)*sin_over_x( ( Scalar(1) - t ) * theta) / sinOverTheta;
  Scalar scale1 = t * sin_over_x( ( t * theta) ) / sinOverTheta;
  if (d<0)
    scale1 = -scale1;

  return Quaternion<Scalar>(scale0 * a.coeffs() + scale1 * b.coeffs());
}

template<typename Q>
EIGEN_DONT_INLINE Q slerp_gael(const Q& a, const Q& b, typename Q::Scalar t)
{
  typedef typename Q::Scalar Scalar;
  
  Scalar d = a.dot(b);
  Scalar theta;
//   theta = Scalar(2) * atan2((a.coeffs()-b.coeffs()).norm(),(a.coeffs()+b.coeffs()).norm());
//   if (d<0.0)
//     theta = M_PI-theta;
  
  if (d<0.0)
    theta = /*M_PI -*/ Scalar(2)*std::asin( (-a.coeffs()-b.coeffs()).norm()/2 );
  else
    theta = Scalar(2)*std::asin( (a.coeffs()-b.coeffs()).norm()/2 );
  
  
  Scalar scale0;
  Scalar scale1;
  if(theta*theta-Scalar(6)==-Scalar(6))
  {
    scale0 = Scalar(1) - t;
    scale1 = t;
  }
  else
  {
    Scalar sinTheta = std::sin(theta);
    scale0 = internal::sin( ( Scalar(1) - t ) * theta) / sinTheta;
    scale1 = internal::sin( ( t * theta) ) / sinTheta;
    if (d<0)
      scale1 = -scale1;
  }

  return Quaternion<Scalar>(scale0 * a.coeffs() + scale1 * b.coeffs());
}

int main()
{
  typedef double RefScalar;
  typedef float TestScalar;
  
  typedef Quaternion<RefScalar>  Qd;
  typedef Quaternion<TestScalar> Qf;
  
  unsigned int g_seed = (unsigned int) time(NULL);
  std::cout << g_seed << "\n";
//   g_seed = 1259932496;
  srand(g_seed);
  
  Matrix<RefScalar,Dynamic,1> maxerr(7);
  maxerr.setZero();
  
  Matrix<RefScalar,Dynamic,1> avgerr(7);
  avgerr.setZero();
  
  cout << "double=>float=>double       nlerp        eigen        legacy(snap)         legacy(nlerp)        rightway         gael's criteria\n";
  
  int rep = 100;
  int iters = 40;
  for (int w=0; w<rep; ++w)
  {
    Qf a, b;
    a.coeffs().setRandom();
    a.normalize();
    b.coeffs().setRandom();
    b.normalize();
    
    Qf c[6];
    
    Qd ar(a.cast<RefScalar>());
    Qd br(b.cast<RefScalar>());
    Qd cr;
    
    
    
    cout.precision(8);
    cout << std::scientific;
    for (int i=0; i<iters; ++i)
    {
      RefScalar t = 0.65;
      cr = slerp_rw(ar,br,t);
      
      Qf refc = cr.cast<TestScalar>();
      c[0] = nlerp(a,b,t);
      c[1] = slerp_eigen(a,b,t);
      c[2] = slerp_legacy(a,b,t);
      c[3] = slerp_legacy_nlerp(a,b,t);
      c[4] = slerp_rw(a,b,t);
      c[5] = slerp_gael(a,b,t);
      
      VectorXd err(7);
      err[0] = (cr.coeffs()-refc.cast<RefScalar>().coeffs()).norm();
//       std::cout << err[0] << "    ";
      for (int k=0; k<6; ++k)
      {
        err[k+1] = (c[k].coeffs()-refc.coeffs()).norm();
//         std::cout << err[k+1] << "    ";
      }
      maxerr = maxerr.cwise().max(err);
      avgerr += err;
//       std::cout << "\n";
      b = cr.cast<TestScalar>();
      br = cr;
    }
//     std::cout << "\n";
  }
  avgerr /= RefScalar(rep*iters);
  cout << "\n\nAccuracy:\n"
       << "  max: " << maxerr.transpose() << "\n";
  cout << "  avg: " << avgerr.transpose() << "\n";
  
  // perf bench
  Quaternionf a,b;
  a.coeffs().setRandom();
  a.normalize();
  b.coeffs().setRandom();
  b.normalize();
  //b = a;
  float s = 0.65;
    
  #define BENCH(FUNC) {\
    BenchTimer t; \
    for(int k=0; k<2; ++k) {\
      t.start(); \
      for(int i=0; i<1000000; ++i) \
        FUNC(a,b,s); \
      t.stop(); \
    } \
    cout << "  " << #FUNC << " => \t " << t.value() << "s\n"; \
  }
  
  cout << "\nSpeed:\n" << std::fixed;
  BENCH(nlerp);
  BENCH(slerp_eigen);
  BENCH(slerp_legacy);
  BENCH(slerp_legacy_nlerp);
  BENCH(slerp_rw);
  BENCH(slerp_gael);
}