/* Simulation of a QTM,  version 1 
________________________________________________________________________
  Christoph D\"urr            ---                            durr@lri.fr
  nov 1994                    ---                http://www.lri.fr/~durr
________________________________________________________________________
 This is classical simulation of a QTM, running with exponential 
   overhead. It's only for pedagogic purposes. The machine has one 
   one-sided infint tape and one read/write-head.

   It's written in C++, and uses the library LEDA. We define the types
   Ampl, Letter, State, Direction, Tape, Config and Superposition.
   LEDA is available by anonymous ftp from 
    ftp.mpi-sb.mpg.de      /pub/LEDA
    ftp.cs.uni-sb.de       /pub/LEDA
    ftp.th-darmstadt.de    /pub/programming/languages/C++/class-libraries/LEDA
   
   Actually it realises the Fourier transformation described in [BV] on
   a parity function described in `oracle'. If you want to change it to
   simulate another machine you may modify:
   (1) LetterStr and StateStr    
           to define you State-set and your alphabet,
   (2) delta(Config,State,Letter,Direction) 
           to call oracles,
   (3) delta(State,Letter,State,Letter,Direction) 
           to describe the finite control
   (4) Config initial; (in main)
           to define the initial configuration.

   Enjoy it, and please send me a mail for suggestions. Thank you.
*/

#include <LEDA/basic.h>
#include <LEDA/d_array.h>
#include <assert.h>
#include <math.h>
#include <string.h>

#define LEDA_COMPARE(type) inline compare(const type &a, const type &b)\
{return a==b?0 : a<=b? -1: 1;}
								    

/*-----------------------
  Complex number class
  `!' gives the conjungate
  length() the magnitude
  <= the lexicographical order
*/
class Complex {
public:
  Complex(double real=0., double imag=0.) :r(real), i(imag) {}
  Complex(const Complex &c) :r(c.r), i(c.i) {}
  Complex operator+(const Complex &c)const 
	{return Complex(r+c.r, i+c.i);}
  Complex operator-(const Complex &c)const 
	{return Complex(r-c.r, i-c.i);}
  Complex operator*(const Complex &c)const 
	{return Complex(r*c.r-i*c.i, i*c.r+r*c.i);}
  Complex &operator+=(const Complex &c) {r+=c.r; i+=c.i; return *this;}
  Complex &operator-=(const Complex &c) {r-=c.r; i-=c.i; return *this;}
  Complex &operator*=(const Complex &c) 
    {return *this = *this * c;}
  Complex operator!()const {return Complex(r,-i);}
  Complex operator=(const Complex &c) {r=c.r; i=c.i; return *this;}
  bool operator==(const Complex &c)const {return r==c.r && i==c.i;}
  bool operator<=(const Complex &c)const 
    {return r<c.r || r==c.r && i<=c.i;}
  bool operator!=(const Complex &c)const {return !((*this)==c);}
  double length()const {return sqrt(r*r+i*i);}
  double r,i;
};

bool isint(double x) {
  double tmp;
  return modf(x,&tmp) < 0.000001;
}

/* Printes in a pretty form a real number */
PrintWell(double x, ostream &out)
{
  if (x<0) {                        /* print `-' for neg. number */
    out << '-';
    x = -x;
  }
  if (x==0)
    out << 0.;
  else    
    if (isint(x))
      out << x;
    else
      if (isint(1/x))
	out << "1/" << 1/x;
      else 
	if (isint(1/(x*x))) 
	  out << "1/sqrt(" << 1/(x*x) << ")";
	else
	  out << x;
}

/* Prints a complex number in a pretty compact form */
void Print(const Complex &c, ostream &out=cout)
{
  if (c==0.)
    out<<0.;
  else {
    if (c.r!=0.)
      PrintWell(c.r,out);
    if (c.i!=0.) {
      if (c.i>0. && c.r!=0.)
	out<<'+';
      PrintWell(c.i,out);
      out<<'i';
    }
  }
}

LEDA_TYPE_PARAMETER(Complex)
LEDA_COMPARE(Complex)
typedef Complex Ampl;


/*-----------------------
  Definition of Letter, state and direction (only two directions)
*/

typedef char    Letter;  
typedef char    State;

#define Left  0
#define Right 1
typedef char Direction;

/* first letter of StateStr  must be initial state
   first letter of LetterStr must be SPACE   
*/
const char LetterStr[] = " 01";
const char StateStr[] =  "qprf";

#define SPACE      LetterStr[0]
#define INIT       StateStr[0]

#define forall_state(q)   for(int iA_##q=0; q=StateStr[iA_##q]; iA_##q++)
#define forall_letter(x)  for(int iB_##x=0; x=LetterStr[iB_##x]; iB_##x++)
#define forall_direction(d) for(Direction d=Left; d<=Right;  d++)

/*-----------------------
   Class Tape, one-sided infinit
   length()  return the limit index behind which all is SPACE
   first letter has index 0
*/
class Tape {
public:
  Tape(const string init="") :s(init) {}
  Tape(const Tape &orig) :s(orig.s) {}
  Letter &operator[](int pos) {if (pos==s.length()) s+=SPACE;
			       return s[pos];}
  Letter operator[](int pos)const {return pos>= s.length()? SPACE: s[pos];}
  bool operator==(const Tape &t)const;
  bool operator<=(const Tape &t)const;
  Tape operator=(const Tape &t) {s=t.s; return *this;}
  int  length() const {return s.length();}
private:
  string s;
};

bool Tape::operator==(const Tape &t)const
{
  int max( Max(s.length(), t.s.length()));
  for (int i=0; i<max; i++)
    if (!((*this)[i]==t[i])) return false;
  return true;
}

bool Tape::operator<=(const Tape &t)const
{
  int max( Max(s.length(), t.s.length()));
  for (int i=0; i<max; i++)
    if ((*this)[i]<t[i])
      return true;
    else 
      if ((*this)[i]>t[i])
	return false;
  return true;
}

/*-----------------------
   Class configuration
   read() return the letter under the read/write head
   Config(c,p,tau,d) creates the configuration c where the transition
                     defined by (p,tau,d) is applied
*/
class Config  {
public:
  Config(const string s="") :state(INIT), head(0), tape(s) {}
  Config(const Config &c) :state(c.state), head(c.head), tape(c.tape) {}
  Config(const Config &orig, State p, Letter tau, Direction d);
  bool operator==(const Config &c)const;
  bool operator<=(const Config &c)const;
  Config &operator=(const Config&c) {state=c.state; head=c.head; tape=c.tape; 
				     return *this;}
  Letter read()const {return tape[head];}
  State state;
  int   head;
  Tape  tape;
};

LEDA_TYPE_PARAMETER(Config)
LEDA_COMPARE(Config)

Config::Config(const Config &orig, State p, Letter tau, Direction d)
:state(p), head(orig.head), tape(orig.tape) {
  tape[head] = tau;
  switch (d) {
  case Left:
    head--; assert(head>=0); break;
  case Right:
    head++; break;
  default:
    assert("Direction"=="bad");
  }
}

inline
bool Config::operator==(const Config &c)const
{
  return state==c.state && head==c.head && tape==c.tape;
}

bool Config::operator<=(const Config &c)const
{
  return (state< c.state ||
	  state==c.state && head< c.head ||
	  state==c.state && head==c.head &&  tape<=c.tape);
}


void Print(const Config &c, ostream &out=cout)
{
  int max = Max(c.tape.length(),c.head);
  Print('|', out);
  for(int i=0; i<=max; i++) {
    if (i==c.head) 
      Print(c.state, out);
    Print(c.tape[i], out);
  }
  out<<"..>";
} 

/*-----------------------
  The definition of the simulated machine
*/

/* This oracle is like in [BV]
   returns the parity of the tape bits selected by toFind.
*/
oracle(const Config &conf) 
{
  static const char *toFind = " 01101";
  int nb = 0;
  for (int i=0; toFind[i]; i++)
    if (toFind[i]=='1' && conf.tape[i]=='1')
      nb++;
  return nb&1;
}

Complex delta(State q, Letter sigma, State p, Letter tau, Direction d);

inline
Complex delta(const Config &conf, State state, Letter tau, Direction d)
{
  if (conf.state =='p' &&         /* Calls the oracle */
      state      =='r' &&
      conf.read()==SPACE && 
      SPACE      ==tau && 
      d          ==Left)
    return oracle(conf)? -1: 1;
  else
    return delta(conf.state, conf.read(), state, tau, d);
}

/* Describes the finite state control
   (It's not very readable, I've no idea how to improve this)
*/
Complex delta(State q, Letter sigma, State p, Letter tau, Direction d)
{
  switch (q) {
  case 'q':
    return (p=='p' && d==Right && sigma==tau)?1:0;
  case 'p':
    if (p=='p' && d==Right && tau!=SPACE && sigma!=SPACE)       
      if (sigma=='1' && tau=='1')
	return -1/sqrt(2);
      else 
	return  1/sqrt(2);
    else
      return 0;
  case 'r':
    if (tau==SPACE && sigma==SPACE)
      return (d==Right && p=='f')?1:0;
    else 
      if (p=='r' && d==Left && tau!=SPACE && sigma!=SPACE)       
	if (sigma=='1' && tau=='1')
	  return -1/sqrt(2);
	else 
	  return  1/sqrt(2);
      else
	return 0;
  case 'f':
    return (p=='f' && sigma==tau && d==Right)?1:0;
  default:
    assert("State"=="Bad");
  }
}

/*-----------------------
   Class Superposition
   associates to a configuration an amplitude
   (is a vector with complex elements and index are configurations)
*/
typedef d_array<Config,Ampl> Superpos;

void Print(const Superpos &sup, ostream &out=cout)
{
  Config conf;
  forall_defined(conf, (Superpos &)sup) 
    if (((Superpos &)sup)[conf] != 0.) {
      Print(((Superpos &)sup)[conf], out);
      Print('\t', out);
      Print(conf, out);
      newline;
    }
}

/* returns the new superposition after one transition 
*/
Superpos delta( Superpos &past)
{
  Superpos future(0.);
  Config   conf;
  State    p;
  Letter   tau;
  forall_defined(conf, past) {
   Complex beta( past[conf]);
    if (beta!=0.)
      forall_state(p)
	forall_letter(tau)
	  forall_direction(d) {
	    Complex alpha( delta(conf, p, tau, d));
	    if (alpha!=0.)
	      future[Config(conf, p, tau, d)] += alpha*beta;
	  }
  }
  return future;
}

/*-----------------------
   the executable can be called with a command-line parameter:
     an initial configuration
*/
main(int argc, char *argv[])
{
  Config initial(argc==2? argv[1]: " 0000");
  Superpos v(0.);
  v[initial] = 1.;
  for (int n=0; n<10; n++) {
    cout << "-----------" << n;
    newline;
    Print(v);
    v = delta(v);
  }
  cout << "-----------" << n;
  newline;
  Print(v);
}
