#include <cassert>
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <deque>
#include <string>
#include <bitset>
#include <limits>

using namespace std;

#include <rpn.h>

#ifndef NDEBUG
// Toggle Debug code.
#define DEBUG_RFC
#endif

// Magic Number
#define PRECISION 30




// Implementation
// ------------------------------------------------------------ 
//

/* g++ wants these. */
rpnbase::~rpnbase() {}
rpnbase* rpnbase::copy() const { return 0; }

ostream& operator << (ostream& os, rpnbase* const p) 
  { return p->print(os); }


rpnreal::rpnreal(deque<rpnbase*>& ds, long double const n)
  : num(n)
{
  eval(ds);
}

/*
This is a MAGIC NUMBER. 

 <TODO> Make configurable for user.

  Why 30?  I do not know, but it is beyond the accuracy
  of my type and hence displaysed the computers approximation.

  eg. On my machine
    73.4 resulted in 
    0: 73.40000000000000568434

  An accuracy of 15 digits. Ofcourse the computer has
   a binary representation/approximation.

  The good thing about displaying the garbage is you
  get to see how inaccurate the computer actually is,
  and its scary.

*/
ostream& rpnreal::print(ostream& os) const
{
  return os << fixed << showpoint 
    << setprecision( PRECISION ) << num;
} 

rpnbase* rpnreal::copy() const
{
  rpnreal* n = new rpnreal();
  n->num = num;
  return n;
}


rpncomplex::rpncomplex
(
  deque<rpnbase*>& ds,
  long double const x, 
  long double const y
)
  : num(x,y)
{
  eval(ds);
}


rpncomplex::rpncomplex
(
  deque<rpnbase*>& ds,
  complex<long double> const & x
)
  : num(x)
{
  eval(ds);
}


ostream& rpncomplex::print(ostream& os) const
{
  return os << fixed << showpoint 
    << setprecision( PRECISION ) << num;
}

rpnbase* rpncomplex::copy() const
{
  rpncomplex* n = new rpncomplex();
  n->num = num;

  return n;
}

 





unsigned int rpninteger::displaybase(10);


rpninteger::rpninteger(deque<rpnbase*>& ds, long int const n)
  : num(n)
{
  eval(ds);
}

ostream& rpninteger::print(ostream& os) const
{

  switch( displaybase )
  {
    case 10: 
      os.unsetf(ios::hex);
      os.unsetf(ios::oct);
      os.setf(ios::dec);
      break;

    case 8:
      os.unsetf(ios::dec);
      os.unsetf(ios::hex);
      os.setf(ios::oct);
      break;

    case 16:
      os.unsetf(ios::dec);
      os.unsetf(ios::oct);
      os.setf(ios::hex);
      break;

    case 2: 

      os << bitset<numeric_limits<long int>::digits>( num );
      return os;
  };

  return os << num;
}

rpnbase* rpninteger::copy() const
{
  rpninteger* n = new rpninteger();
  n->num = num;
  return n;
}


rpnstring::rpnstring(deque<rpnbase*>& ds,string const & s)
  :str(s)
{
  eval(ds);
}

ostream& rpnstring::print(ostream& os) const
{
  if (str=="/")
    return os << "\"/\"";

  if (str.find(' ')!=string::npos)
    return os << '"' << str << '"';

  return os << str;

/*
  if (str != "/")
    return os << str;

  // To distinguish between division and root node. 
  return os << string("\"/");
*/
}

rpnbase* rpnstring::copy() const
{
  rpnstring* s = new rpnstring();
  s->str = str;
  return s;
}

void rpnstring::eval( deque<rpnbase*>& ds )
{
  ds.push_front(this); 
}


void rpnprogram::vinc()
{
  if (!v.empty())
  {
    for (unsigned int i=0, imax=v.size(); i<imax; ++i)
      v[i]->inc();
  }
}

void rpnprogram::inc()
{
  ++ counter;

  vinc();

  if (!variables.empty())
  {
    for (unsigned int i=0, imax=variables.size(); i<imax; ++i)
      variables[i]->inc();
  }
}


rpnprogram::rpnprogram
(
  deque<rpnbase*>& ds, 
  deque<rpnbase*>& ds2,
  bool const evaluate 
)
  : state(3)
{
  v = ds2;
  reverse(v.begin(),v.end()); /* <TODO> make efficent with reverse copy? */

  if (evaluate)
  {
    eval(ds);
    return;
  }

  ds.push_front(this);
}

rpnprogram::rpnprogram(deque<rpnbase*>& ds)
{
  ds.push_front(this);
}

rpnprogram::rpnprogram()
  : state(3)
{
}

ostream& rpnprogram::print(ostream& os) const
{
  os << "{";
  if( v.empty())
    return os << " }";

  for (unsigned int i=0,imax=v.size(); i<imax; ++i)
  {
    os << " ";
    v[i]->print(os);
  }

  return os << " }";
}

rpnbase* rpnprogram::copy() const
{
  /* A deep copy is required. */

  rpnprogram* p = new rpnprogram();

  if (v.empty())
  {  
    if (variables.empty())
      return p;

    for (unsigned int i=0, imax=variables.size(); i<imax; ++i)
    {
      rpnbase* tmp = variables[i]->copy();
      p->variables.push_back( (rpnvar*)tmp ); 
    }

    return p;
  }

  deque<rpnbase*> &v2 = p->v;

  for (unsigned int i=0, imax=v.size(); i<imax; ++i)
    v2.push_back( v[i]->copy() );

  if (variables.empty())
    return p;

  for (unsigned int i=0, imax=variables.size(); i<imax; ++i)
  {
    rpnbase* tmp = variables[i]->copy();
    p->variables.push_back( (rpnvar*)tmp );
  }

  return p;
};
  
rpnprogram::~rpnprogram()
{
  if (!v.empty())
  {
    for (unsigned int i=0, imax=v.size(); i<imax; ++i)
      v[i]->dec();
    v.clear();
  }

  if (!variables.empty())
  {
    for (unsigned int i=0, imax=variables.size(); i<imax; ++i)
      variables[i]->dec();
    variables.clear();
  }
}

void rpnprogram::eval_01( deque<rpnbase*>& ds )
{
  if(!v.empty())
  {
    for (unsigned int i=0,imax=v.size(); i<imax; ++i )
    {
      v[i]->inc();
      if (v[i]->isprogram())
        ds.push_front(v[i]);
      else
        v[i]->eval(ds);
    }
  }
}

void rpnprogram::eval_00()
{
  if(!v.empty())
  {
    for (unsigned int i=0,imax=v.size(); i<imax; ++i )
    {
      v[i]->inc();
      if (v[i]->isprogram())
        rpnprogramstackstate().ds().push_front(v[i]);
      else
        v[i]->eval(rpnprogramstackstate().ds());
    }
  }
}

void rpnprogram::eval_11( deque<rpnbase*>& ds )
{
  deque<rpnprogram*>& ps(* rpnprogramstackstate().ps);
  ps.push_front(this);

  if(!v.empty())
  {
    for (unsigned int i=0,imax=v.size(); i<imax; ++i )
    {
      v[i]->inc();
      if (v[i]->isprogram())
        ds.push_front(v[i]);
      else
        v[i]->eval(ds);
    }
  }

  // Remove self from program stack.
  if (ps.front()==this)
    rpnprogramstackstate().pop();
  else
  {
    unsigned int const imax=ps.size();
    for (unsigned int i=1; i<imax; ++i)
    {
      if (ps[i]==this)
      {
        ps.erase(ps.begin()+i);
        i=imax;
      }
    }
  }
}

void rpnprogram::eval_10()
{
  deque<rpnprogram*>& ps(* rpnprogramstackstate().ps);
  ps.push_front(this);

  if(!v.empty())
  {
    for (unsigned int i=0,imax=v.size(); i<imax; ++i )
    {
      v[i]->inc();
      if (v[i]->isprogram())
        rpnprogramstackstate().ds().push_front(v[i]);
      else
        v[i]->eval(rpnprogramstackstate().ds());
    }
  }

  // Remove self from program stack.
  if (ps.front()==this)
    rpnprogramstackstate().pop();
  else
  {
    unsigned int const imax=ps.size();
    for (unsigned int i=1; i<imax; ++i)
    {
      if (ps[i]==this)
      {
        ps.erase(ps.begin()+i);
        i=imax;
      }
    }
  }
}


void rpnprogram::eval( deque<rpnbase*>& ds )
{
  switch( state )
  {
    case 3: eval_11(ds); break;
    case 1: eval_10();   break;
    case 2: eval_01(ds); break;
    case 0: eval_00();   break;
  }

  dec();

/*
  deque<rpnprogram*>& ps(* rpnprogramstackstate().ps);
  ps.push_front(this);
//  rpnprogramstackstate().push(this);



cout << "rpnprogram::eval( deque<rpnbase*>& ds )" << endl;

  if(!v.empty())
  {
    for (unsigned int i=0,imax=v.size(); i<imax; ++i )
    {
      v[i]->inc();
      if (v[i]->isprogram())
        ds.push_front(v[i]);
      else
        v[i]->eval(ds);
    }
  }

//bool found=false;

  // Remove self from program stack.
  if (ps.front()==this)
  {
//found=true;
    rpnprogramstackstate().pop();
  }
  else
  {
    unsigned int const imax=ps.size();
    for (unsigned int i=1; i<imax; ++i)
    {
      if (ps[i]==this)
      {
//found=true;
        ps.erase(ps.begin()+i);
        i=imax;
      }
    }
  }

//cout << "found=" << found << endl;

//  rpnprogramstackstate().pop();
 
  dec();
*/
}



void rpnvar::inc()
{ 
  ++counter;
  x->inc();
}

rpnvar::~rpnvar()
{
  if (x==0)
    return;

  x->dec();
}

rpnvar::rpnvar(rpnprogram& prog, rpnbase* x_, string const & s)
  : varname(s), x(x_)
{
  prog.variables.push_front(this);
}

rpnvar::rpnvar(rpnbase* x_, string const & s)
  : varname(s), x(x_)
{
}

rpnbase* rpnvar::copy() const
{
  return new rpnvar( x->copy(),varname);
}

ostream& rpnvar::print(ostream& os) const
{
  os << varname << " : ";
  return x->print(os);
}


rpnvector::rpnvector(int index)
{
  reverseindex = indexcomplement(index);
}

rpnbase* rpnvector::copy() const
{
  /* I do not want a default contructor, so put a dummy
     argument in.  The reverseindex should be preserved
     with a copy as they point to the same place.
  */
  rpnvector* p = new rpnvector((int)0);
  p->reverseindex = reverseindex;
  return p;
}

int const rpnvector::indexcomplement(int const n) const
{
  int k = rpnprogramstackstate().ds().size();
  k -= n;
  return k;
}

const int rpnvector::index() const
{
  return indexcomplement(reverseindex);
}


ostream& rpnvector::print(ostream& os) const
{
  return os << " " << index() << " [] ";
  //return os << " " << indexcomplement(reverseindex) << " [] ";
}
  

rpnbase* rpnfunction::copy() const
{
  return 0;
}


deque<rpnbase*> rpnprogramstackstate::ds2;
deque<rpnprogram*>* rpnprogramstackstate::ps =
  new deque<rpnprogram*>();
rpnprogram rpnprogramstackstate::rpnhome;
string rpnprogramstackstate::findprogrampath;

void rpnprogramstackstate::find 
(
  bool & result,
  unsigned int & indexi,
  unsigned int & indexk,
  rpnvar* & x,
  string const & nm
) const
{
  result=false;

  for (unsigned int i=0, imax=ps->size(); i<imax; ++i)
  {
    deque<rpnprogram*>& w = *ps; // <TODO> optimize.
    if ( ! w[i]->variables.empty() )
    {
      deque<rpnvar*>& z = w[i]->variables;
      for (unsigned int k=0, kmax=z.size(); k<kmax; ++k)
      {
        if (z[k]->varname==nm)
        {
          result=true;
          indexi = i;
          indexk = k;
          x = z[k];

          return;
        }
      }
    }
  }
}



/* While developing rely on general find, optimize at a later date. */



void rpnprogramstackstate::exists
(
  bool & res,
  string const & nm
) const
{
  unsigned int i,k;
  rpnvar* x;

  find(res,i,k,x,nm);
}


void rpnprogramstackstate::evaluate
(
  deque<rpnbase*>& ds,
  string const & nm
) const
{
  bool res;
  unsigned int i,k;
  rpnvar* x;

  find(res,i,k,x,nm);
  if (res)
    x->x->copy()->eval(ds);
}

void rpnprogramstackstate::recall
(
  deque<rpnbase*>& ds,
  string const & nm
) const
{
  bool res;
  unsigned int i,k;
  rpnvar* x;

  find(res,i,k,x,nm);
  if (res)
    ds.push_front(x->x->copy());
}

void rpnprogramstackstate::recallpointer
(
  deque<rpnbase*>& ds,
  string const & nm
) const
{
  bool res;
  unsigned int i,k;
  rpnvar* x;

  find(res,i,k,x,nm);
  if (res)
  {
    x->x->inc();
    ds.push_front(x->x);
  }
}


void rpnprogramstackstate::replace(rpnbase* x, string const & nm)
{
  bool res;
  unsigned int i,k;
  rpnvar* x2;

  find(res,i,k,x2,nm);
  if (res)
  {
    x2->x->dec();
    x2->x = x; 
  }
  else
    x->dec();  /* harsh */
}

void rpnprogramstackstate::erase(string const & nm)
{
  bool res;
  unsigned int i,k;
  rpnvar* x2;

  find(res,i,k,x2,nm);
  if (res)
  {
    deque<rpnprogram*>& w = *ps;
    w[i]->variables.erase( w[i]->variables.begin()+k );
  }
}

void rpnprogramstackstate::init()
{
  ps->push_front( &rpnhome );
}

ostream& rpnprogramstackstate::print(ostream& os) const
{
  for (unsigned int i=0, imax=ps->size(); i<imax; ++i)
  {
    os << "{ ";
    deque<rpnprogram*>& w = *ps;
    if ( ! w[i]->variables.empty() )
    {
      deque<rpnvar*>& z = w[i]->variables;
      for (unsigned int k=0, kmax=z.size(); k<kmax; ++k)
      {
        os << "(" << z[k]->varname << ",";
        z[k]->x->print(os);
        os << ") ";
      }
    }
    os << "}" << endl;
  }
  return os;
}

void rpnprogramstackstate::add(rpnbase* x, string const & s)
{
  ps->front()->variables.push_front( new rpnvar(x,s) );
}


void rpnprogramstackstate::findprogram
(
  bool& found, 
  string& path, 
  rpnprogram* targ
)
{
  found = false;


  if (targ==&rpnhome)
  {
    findprogrampath = path = "/";
    found = true;
    return;
  }

  findprogram(found,&rpnhome,"",targ);

  if (found)
    path = findprogrampath;
}

void rpnprogramstackstate::findprogram
(
  bool& found, 
  rpnprogram* p, 
  string const path, 
  rpnprogram* targ
)
{
  /* Depth first search. */
  /* Assume non-cyclic data structure. */

  if (!p->variables.empty())
  {
    for (unsigned int i=0, imax=p->variables.size(); i<imax; ++i)
    {
      if (found)
        return;

      if (p->variables[i]->x->isprogram())
      {
        rpnprogram* pr = (rpnprogram*)(p->variables[i]->x);

        string pathnew( path + string("/") + p->variables[i]->varname );

        if (pr == targ)
        {
          found = true;
          findprogrampath = pathnew;
          return;
        }
        else
          findprogram(found,pr,pathnew,targ);

      }
    }
  }
}


ostream& operator << (ostream& os, rpnprogramstackstate const & ps)
  { return ps.print(os); }