rpn2.h

Go to the documentation of this file.

#ifndef RPN_H
#define RPN_H

#include <iostream>
#include <iomanip>
#include <deque>
#include <string>

// Toggle ALL debug code. 
//#define NDEBUG
#include <cassert>

using namespace std;

#include <html.h>

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


class rpnfunction;

class rpnbase 
{
public:

  /* Reference counting for memory management. */
  unsigned int counter;
  virtual void inc() 
    { ++counter; }
  void dec() 
    { --counter; if (counter==0) delete this; }

  /* Constructors, destructors and deep copy. */
  rpnbase() : counter(1) {}
  virtual ~rpnbase()=0;
  virtual rpnbase* copy() const=0;

  virtual ostream& print(ostream& os) const 
    { return os << this->name(); }
  /* Associated symbol with the class. */
  virtual string const name() const 
    { return string("undefined"); }

  /* Evaluation on the stack. */
  virtual void eval( deque<rpnbase*>& ds )
    { ds.push_front(this); }
  
  /* Visitor patterns accept function forwards data type. */
  virtual void accept(deque<rpnbase*>& ds,rpnfunction& f) {}

  /* Real time type information. */
  virtual bool const isinteger() const  { return false; } 
  virtual bool const isreal() const     { return false; }
  virtual bool const isstring() const   { return false; }
  virtual bool const isprogram() const  { return false; } 
  virtual bool const isvariable() const { return false; }
  virtual bool const isvector() const   { return false; }
  bool const isnumber() const 
    { return this->isreal() || this->isinteger(); }

};

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

class rpnprogram;
class rpnstring;
class rpnreal;
class rpninteger;
class rpnvar;
class rpnvector;


/* Derive functions */
class rpnfunction : public rpnbase
{
public:

  rpnfunction() {}
  ~rpnfunction() {}
  rpnbase* copy() const;

  virtual void visit(deque<rpnbase*>& ds,rpnprogram& p) {}
  virtual void visit(deque<rpnbase*>& ds,rpnstring& s) {}
  virtual void visit(deque<rpnbase*>& ds,rpnreal& n) {}
  virtual void visit(deque<rpnbase*>& ds,rpninteger& n) {}
  virtual void visit(deque<rpnbase*>& ds,rpnvar& n) {}
  virtual void visit(deque<rpnbase*>& ds,rpnvector& v) {}

  string const name() const 
    { return string("rpnfunction"); }
};


class rpnreal : public rpnbase
{
public:

  long double num;
  typedef long double type;

  rpnreal() {}
  rpnreal(double const n) : num(n) {} /* <TODO> Is this necessary? */
  rpnreal(deque<rpnbase*>& ds,double const n); 
  ~rpnreal() {}
  rpnbase* copy() const;

  void accept(deque<rpnbase*>& ds,rpnfunction& f) 
    { f.visit(ds,*this); }

  ostream& print(ostream& os) const;
  string const name() const 
    { return string("rpnreal"); }

  bool const isreal() const 
    { return true; }
};


class rpninteger: public rpnbase
{
public:
/* <TODO>  - template the integer so much better integer arithmetic
 * can be used. 
 */
  long int num;
  typedef long int type;

  rpninteger() {}
  rpninteger(deque<rpnbase*>& ds,long int const n);
  ~rpninteger() {}
  rpnbase* copy() const;

  void accept(deque<rpnbase*>& ds,rpnfunction& f) 
    { f.visit(ds,*this); }

  ostream& print(ostream& os) const;
  string const name() const 
    { return string("rpninteger"); }

  bool const isinteger() const 
    { return true; }
};


class rpnstring : public rpnbase
{
public:

  string str;

  rpnstring() {}
  rpnstring(deque<rpnbase*>& ds,string const & s);
  ~rpnstring() {}
  rpnbase* copy() const;

  void accept(deque<rpnbase*>& ds,rpnfunction& f) 
    { f.visit(ds,*this); }

  ostream& print(ostream& os) const;

  void eval( deque<rpnbase*>& ds );

  bool const isstring() const 
    { return true; }
};


/* <TODO> Restrict to access by rpnprogram, don't create on the stack. */

/* Rpn Variable class. - Used by rpnprogram. 
 */
class rpnvar : public rpnbase
{
public:

  string varname;
  rpnbase* x;  

  void inc();

  rpnvar(rpnbase* x_, string const & s);
  rpnvar(rpnprogram& prog, rpnbase* x_, string const & s);
  ~rpnvar();

  rpnbase* copy() const;
  void accept(deque<rpnbase*>& ds,rpnfunction& f) 
    { f.visit(ds,*this); }

  void eval( deque<rpnbase*>& ds )
    { rpnbase* w = x->copy(); w->eval(ds); }

  ostream& print(ostream& os) const;
  string const name() const 
    { return varname; }

  bool const isvariable() const 
    { return true; }
};




class rpnvector : public rpnbase
{
/* Counting from the stack bottom is 0 as the first element.
   Counting from the stack end is 1 as the first element.
   Then can convert between the two with the same formula:
     f(k) = n-k  eg n=6, k=1 then f(1)=5 which is 1: ,f( f(1) ) = 1.
*/
public:

  /* Counting from  the end of the stack. */
  int reverseindex;
  
  rpnvector(int index);

  rpnbase* copy() const;
  void accept(deque<rpnbase*>& ds,rpnfunction& f) 
    { f.visit(ds,*this); }

  ostream& print(ostream& os) const;
  string const name() const 
    { return "rpnvector"; }

  /* Convert between counting from the start of the stack 
     and the end of the stack. */
  int const indexcomplement(int const n) const;
  /* Return the index relative to the current stack. */
  const int rpnvector::index() const;

  bool const isvector() const 
    { return true; }
};



class rpnprogram : public rpnbase 
{
public:

  deque<rpnbase*> v;
  deque<rpnvar*> variables;

  void inc();

  bool const valid() const;

  rpnprogram();
  rpnprogram(deque<rpnbase*>& ds);
  rpnprogram
  (
    deque<rpnbase*>& ds,
    deque<rpnbase*>& ds2,
    bool const evaluate=true
  );
  ~rpnprogram();
  rpnbase* copy() const;

  void accept(deque<rpnbase*>& ds,rpnfunction& f) 
    { f.visit(ds,*this); }

  ostream& print(ostream& os) const;

  void eval( deque<rpnbase*>& ds ); 

  bool const isprogram() const 
    { return true; }
};


/* Access the programs state. Its a singleton class
 * which holds pointers to the systems state.
 * Also supports variable operations for var suggesting
 * that this class should be made into two classes. */ 

class rpnprogramstackstate
{
  static string findprogrampath;
  void findprogram
  (
    bool& found, 
    rpnprogram* p, 
    string const path, 
    rpnprogram* targ
  );
public:

  static rpnprogram rpnhome;

  /* The primary program pointer, is never empty. */
  static deque<rpnprogram*>* ps;

  /* Minor stack. */
  static deque<rpnbase*> ds2;

  rpnprogramstackstate() {}

  /* Client must call before and after use. */
  void init();

  /* Access the most recent program's stack. */
  deque<rpnbase*>& ds() 
    { return ps->front()->v; }
  /* Access the most recent programs's variables. */
  deque<rpnvar*>& vs() 
    { return ps->front()->variables; }

  ostream& print(ostream& os) const;

  /* Control scoping/visability of programs and consequently variables. */
  void push(rpnprogram* p)
    { ps->push_front(p); }
  void pop()
    { if(ps->size()>1) ps->pop_front(); }

  /* Add a variable to the most rescent stack program. */
  void add(rpnbase* x, string const & s);

  /* Find the program in the rpnhome tree. */
  void findprogram(bool& found, string& path, rpnprogram* targ);

  /* Searches for a named variable, in the stack order. */
  void find
  (
    bool & result,
    unsigned int & indexi,
    unsigned int & indexk,
    rpnvar* & x,
    string const & nm
  ) const;

  /* Support operations on variables. */
  void erase(string const &nm);
  void replace(rpnbase* x, string const & nm);
  void exists(bool& res, string const & nm) const;
  void evaluate(deque<rpnbase*>& ds, string const & nm) const;
  void recall(deque<rpnbase*>& ds, string const & nm) const; 
  void recallpointer(deque<rpnbase*>& ds, string const & nm) const;

};

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


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

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


rpnreal::rpnreal(deque<rpnbase*>& ds, 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( 30 ) << num;
} 

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


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

ostream& rpninteger::print(ostream& os) const
{
  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 << str;

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

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

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


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

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

  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 
)
{
  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()
{
}

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( deque<rpnbase*>& ds )
{
  rpnprogramstackstate().push(this);

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

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

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

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

  x->dec();
}

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

inline 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);

      }
    }
  }
}





#endif