#include <stream.h>
#include <string.h>
#include "external.h"
#include "basic.h"


string operator+( const string& a, const string& b ) {
  string r;
  r.sp = new (GC) char[strlen(a.sp)+strlen(b.sp)+1];
  strcpy(r.sp,a.sp);
  strcat(r.sp,b.sp);
  return r;
};


unsigned long string::hash () {
  if (hash_value>0)
     return hash_value;
  else { unsigned long res = 0;
	 for(int i = strlen(sp)-1; i>=0; i--)
	    res = (res<<3) | (sp[i]);
	 hash_value = res;
	 return res;
  };
};


String reads ( ifstream& from ) {
  int len;
  from >> len;
  char c;
  from.get(c);
  char buf[len+1];
  for(int i = 0; i<len; i++)
     from.get(buf[i]);
  buf[len] = '\0';
  return new string(buf);
};


string::write ( ofstream& to ) {
  to << ' ' << strlen(sp) << ' ' << sp;
};


/*--------------------------------------------------------------------------------*/


Expr variable (String s) {
  expr *e = new expr;
  e->tag = VAR;
  e->info.Variable = new string(*s);
  return e;
};


Expr integer (int n) {
  expr *e = new expr;
  e->tag = INT;
  e->info.Integer = n;
  return e;
};


Expr estring (String s) {
  expr *e = new expr;
  e->tag = STRING;
  e->info.Estring = new string(*s);
  return e;
};


Expr function (Expr s, list<Expr> *r) {
   expr *e = new expr;
   e->tag = FNC;
   e->info.Function.Name = s;
   e->info.Function.Parameters = r;
   return e;
};


bool member (Expr e, list<Expr> *r) {
   bool found = false;
   for(list<Expr>* s = r; !found && s->consp(); s=s->tl)
      found = found || (s->hd->eq(e));
   return found;
};


bool member (Expr e, list<String> *r) {
   bool found = false;
   for(list<String>* s = r; !found && s->consp(); s=s->tl)
      found = found || (s->hd->eq(e->info.Variable));
   return found;
};


ostream& operator<<( ostream& s, expr *e ) {
  if (e->variablep()) s << e->info.Variable;
  else if (e->integerp()) s << e->info.Integer;
  else if (e->stringp()) s << '\"' << e->info.Estring << '\"';
  else if (e->functionp())
       s << e->info.Function.Name << e->info.Function.Parameters;
};


int expr::size () {
  if (variablep()) return strlen(info.Variable->value());
  else if (integerp()) return strlen(form("%i",info.Integer));
  else if (stringp()) return strlen(info.Estring->value())+2;
  else if (functionp())
       { int n = info.Function.Name->size()+1;
	 for(list<Expr>* r = info.Function.Parameters; r->consp(); r=r->tl)
	    n += r->hd->size()+1;
	 return n;
	};
  return 0;
};


expr::pretty_print (int pos) {
  if (variablep()) cout << info.Variable;
  else if (integerp()) cout << info.Integer;
  else if (stringp()) cout << '\"' << info.Estring << '\"';
  else if (functionp())
	  if (info.Function.Parameters->consp() && pos+size()>screen_size)
	  { cout << info.Function.Name << '(';
	    int new_pos = pos+info.Function.Name->size()+1;
	    info.Function.Parameters->hd->pretty_print(new_pos);
	    for(list<Expr>* r=info.Function.Parameters->tl; r->consp(); r=r->tl)
	    { cout << ",\n";
	      for(int i=0; i<new_pos; i++) cout << ' ';
	      r->hd->pretty_print(new_pos);
	    };
	    cout << ")";
	  }
	  else cout << info.Function.Name << info.Function.Parameters;
};


bool expr::eq ( Expr x ) {
  if (&(*this)==&(*x)) return true;
  else if (variablep() && info.Variable->eq("_")) return true;
  else if (x->variablep() && x->info.Variable->eq("_")) return true;
  else if (variablep() && x->variablep())
       return info.Variable->eq(x->info.Variable);
  else if (integerp() && x->integerp())
       return (info.Integer==x->info.Integer);
  else if (stringp() && x->stringp())
       return info.Estring->eq(x->info.Estring);
  else if (functionp() && x->functionp())
          if (info.Function.Name->eq(x->info.Function.Name))
	     { bool b = true;
	       list<Expr>* s = x->info.Function.Parameters;
	       list<Expr>* r = info.Function.Parameters;
	       for(;b && r->consp() && s->consp(); r=r->tl, s=s->tl)
		  b = b && r->hd->eq(s->hd);
	       return (b && r->nullp() && s->nullp());
             }
          else return false;
  else return false;
};


unsigned long expr::hash() {
  unsigned long res = 0;
  if (hash_value>0) res = hash_value;
  else if (variablep()) res = info.Variable->hash();
  else if (integerp()) res = info.Integer;
  else if (stringp()) res = info.Estring->hash();
  else if (functionp())
       { res = info.Function.Name->hash();
         for(list<Expr>* r = info.Function.Parameters; r->consp(); r = r->tl)
            res = res ^ (r->hd->hash());
       };
  hash_value = res;
  return res;
};


Expr subst_expr ( Expr variable, Expr value, Expr term ) {
  if (term->eq(variable))
     return value;
  else if (term->functionp())
       return function(subst_expr(variable,value,term->info.Function.Name),
		       subst_list(variable,value,term->info.Function.Parameters));
  else return term;
};


list<Expr>* subst_list ( Expr variable, Expr value, list<Expr>* terms ) {
  list<Expr>* res = Nil;
  for(list<Expr>* r = terms; r->consp(); r=r->tl)
     res = Cons(subst_expr(variable,value,r->hd),res);
  return res->reverse();
};


Expr read ( ifstream& from ) {
  Expr res = new expr;
  short tag;
  char c;
  from >> tag;
  from.get(c);
  /*   (int) res->tag = tag; */
  res->tag = (tagtype) tag;
  if (res->variablep()) res->info.Variable = reads(from);
  else if (res->integerp()) from >> res->info.Integer;
  else if (res->stringp()) res->info.Estring = reads(from);
  else if (res->functionp())
       { int len;
	 res->info.Function.Name = read(from);
	 from >> len;
	 res->info.Function.Parameters = Nil;
	 for(int i=0; i<len; i++)
	    res->info.Function.Parameters = res->info.Function.Parameters->cons(read(from));
	 res->info.Function.Parameters = res->info.Function.Parameters->reverse();
       };
  return res;
};


expr::write ( ofstream& to ) {
  to << ' ' << tag;
  if (variablep()) info.Variable->write(to);
  else if (integerp()) to << ' ' << info.Integer;
  else if (stringp()) info.Estring->write(to);
  else if (functionp())
       { info.Function.Name->write(to);
	 to << ' ' << info.Function.Parameters->length();
         for(list<Expr>* r = info.Function.Parameters; r->consp(); r = r->tl)
	     r->hd->write(to);
       };
};
