/********************************************************************************
*
* File: basic.h
* The interface of the classes used in OPTGEN and the query optimizers
* Programmer: Leonidas Fegaras, UTA
* Date: 4/12/97
*
********************************************************************************/

#include <string.h>
#include <stream.h>
#include <fstream.h>

static int name_counter = 0;


/*--------------------------------------------------------------------------------
-  Strings
---------------------------------------------------------------------------------*/


class string: public gc {

  char* sp;		      /* the string content */
  unsigned long hash_value;   /* the hash key of the string */

public:

  /* string constructors */
  string() { sp = 0; hash_value = 0; }
  string( string& b ) { sp = b.sp; hash_value = 0; };
  string( const char* s ) { sp = new (GC) char[strlen(s)+1]; strcpy(sp,s); hash_value = 0; };

  /* access the string content */
  inline char* value() { return sp; }

  /* various string equalities */
  inline bool eq( string* a ) { return strcmp(sp,a->sp)==0; };
  inline bool eq( string a ) { return strcmp(sp,a.sp)==0; };
  inline bool eq( const char* a ) { return strcmp(sp,a)==0; };

  /* string concatenation */
  friend string operator+( const string&, const string& );

  /* map a string into an integer; it is used in hashing */
  unsigned long hash ();

  /* new_name() returns a name that hasn't been used before */
  friend inline string* new_name () { return new string(form("X_%i",name_counter++)); }

  /* I/O functions */
  write ( ofstream& to );
  friend string* reads ( ifstream& from );
  friend ostream& operator<<( ostream& s, const string& a ) { return s << a.sp; };
  friend ostream& operator<<( ostream& s, const string* a ) { return s << a->sp; };

};


typedef string* String;


/*--------------------------------------------------------------------------------
-  pair<T,S> is a pair with two elements: one of type T and one of type S
----------------------------------------------------------------------------------*/

template<class T,class S>
class pair: public gc {
public:
  T first;
  S second;
  pair ( T x, S y ) { first = x; second = y; };
  inline friend pair* Pair ( T x, S y ) { return new pair(x,y); };
  friend ostream& operator<< ( ostream& s, pair* p )
         { return s << p->first << ": " << p->second; };
};


/*--------------------------------------------------------------------------------
-  list<T> is a list of elements of type T
----------------------------------------------------------------------------------*/


template<class T>
class list: public gc {
public:

  enum { Nil, Cons } tag;
  T hd;        /* list head */
  list *tl;    /* list tail */

  /* list constructor */
  list () { tag = Nil; };

  /* construct a list from a vector of values */
  list ( const T[] );

  /* test whether the list is null or not */
  inline nullp () { return (tag==Nil); };
  inline consp () { return (tag==Cons); };

  /* construct a new list cell */
  list* cons ( T );
  friend inline list* Cons ( T x, list* r ) { return r->cons(x); };

  /* list size */
  int length();

  /* append the argument to the end of the list forming a new list */
  list* append ( list* );
  friend inline list* Append ( list* x, list* y ) { return x->append(y); };

  /* list reverse */
  list* reverse ();

  /* sort the list using bubble sort */
  list* sort ( bool (less_than)(T,T) );

  /* display a list */
  friend ostream& operator<< ( ostream&, list* );

};


typedef list<String>* Names;


/*--------------------------------------------------------------------------------
-  binding lists associate names with values of type T
--------------------------------------------------------------------------------*/


template<class T>
class binding: public gc {
public:

  list<pair<String,T>*>* env;

  /* binding constructors */
  binding () { env = new list<pair<String,T>*>; };
  binding ( binding* e ) { env = e->env; };
  binding ( list<pair<String,T>*>* e ) { env = e; };
  binding ( pair<String,T>* x );
  binding ( String, T );

  /* extend the binding list with a new binding */
  binding* extend ( pair<String,T>* x );
  inline binding* extend ( String s, T c ) { return extend(new pair<String,T>(s,c)); };

  /* append two binding lists */
  binding* extend ( binding* r );

  /* get the current element of the binding list */
  inline pair<String,T>* current () { return env->hd; };

  /* get the next element of the binding list */
  inline binding* next () { return new binding(env->tl); };

  /* are there more elements in the binding list? */
  inline bool more () { return env->consp(); }

  /* find a value T given its name */
  T find ( String );

  /* find a value T given its name; if you don't find return a default value */
  T find ( String, T );

  /* is name bound in the binding list? */
  bool in ( String );

  /* return the list of all the names bound in the binding list */
  Names names ();

  inline int length () { return env->length(); };

  /* display a binding list */
  friend ostream& operator<< ( ostream&, binding* );

};



/*--------------------------------------------------------------------------------
-  This is the data structure for graphs
--------------------------------------------------------------------------------*/


template<class T,class S> class graph;


template<class T,class S>
class node: public gc {

  typedef pair<node*,S>* edge;

public:

  T info;			/* the content of a node */
  list<edge>* edges;		/* the edges attached to a node */

  /* constructor */
  node( T v ) { info = v; edges = new list<edge>; };

  /* attach a new directed edge (from this to x) to the node */
  inline node* new_edge ( node* x, S v ) { edges = edges->cons(new pair<node*,S>(x,v)); };

  inline bool eq ( node* x ) { return this == x; };

  bool member ( list<node*>* n );
  inline bool member ( graph<T,S>* n ) { return member(n->nodes); };

  /* display a node */
  friend ostream& operator<< ( ostream& s, node* n ) { s << n->info; return s; };

};


template<class T,class S>
class graph: public gc {

public:

  list<node<T,S>*>* nodes;

  /* constructor */
  graph () { nodes = new list<node<T,S>*>; };

  /* insert a new node in the graph */
  inline node<T,S>* new_node ( T v ) { node<T,S>* n = new node<T,S>(v); nodes = nodes->cons(n); return n; };

  /* attach a new directed edge x->y with label v to the graph */
  inline new_edge ( node<T,S>* x, node<T,S>* y, S v ) { x->new_edge(y,v); };

  inline new_bedge ( node<T,S>* x, node<T,S>* y, S v ) { x->new_edge(y,v); y->new_edge(x,v); };

  /* number of nodes in a graph */
  inline int size () { return nodes->length(); };

  /* display a graph */
  friend ostream& operator<< ( ostream&, graph* );

};


/*--------------------------------------------------------------------------------
-  This is the data structure to represent algebraic forms, plans, etc
--------------------------------------------------------------------------------*/


class expr;

typedef expr* Expr;

typedef list<Expr>* Params;


class expr: public gc {
  enum { ERROR, VAR, INT, STRING, FNC } tag;	/* the type of expression */
  unsigned long hash_value;			/* the hash key of the Expr */
  const screen_size = 100;			/* used in pretty printing */
  int size ();

public:
  union { String		Variable;
          int			Integer;
          String		Estring;
          struct { Expr		Name;
	           Params	Parameters;
	         }		Function;
        } info;

  /* expr constructors */
  expr () { hash_value = 0; tag = ERROR; };
  friend Expr variable (String);
  friend inline Expr variable (string s) { return variable(&s); };
  friend Expr integer (const int);
  friend Expr estring (String);
  friend inline Expr estring (string s) { return estring(&s); };
  friend Expr function (Expr,list<Expr>*);

  /* accessors */
  inline String name () { return info.Variable; };
  inline list<Expr>* arguments () { return info.Function.Parameters; };

  /* testing the type of expr */
  inline variablep () { return (tag==VAR); };
  inline integerp () { return (tag==INT); };
  inline stringp () { return (tag==STRING); };
  inline functionp () { return (tag==FNC); };

  /* expr deep equality */
  bool eq ( Expr );

  /* check if an expr is a member of a list of exprs or a list of strings */
  friend bool member (Expr,list<Expr>*);
  friend bool member (Expr,list<String>*);

  /* substitute value for variable terms(s) */
  friend Expr subst_expr ( Expr variable, Expr value, Expr term );
  friend list<Expr>* subst_list ( Expr variable, Expr value, list<Expr>* terms );
  friend inline Expr substitute ( Expr e, Expr term )
         { return subst_expr(e->arguments()->hd,term,e->arguments()->tl->hd); }

  /* new_variable() returns a variable name that hasn't been used before */
  friend inline Expr new_variable () { return variable(new_name()); }

  /* map an expr to integer; use for hashing in memoization */
  unsigned long hash ();

  /* print with indentations to look nice */
  pretty_print ( int );

  /* I/O functions */
  friend ostream& operator<< ( ostream&, Expr );
  friend Expr read ( ifstream& );
  write ( ofstream& );

};


#define Nil (new list<Expr>)


/*--------------------------------------------------------------------------------
-  The template method's code.
-  Must be included here, since templates are macros
--------------------------------------------------------------------------------*/


template<class T>
list<T>::list ( const T x[] ) {
  list<T>* n = new list<T>;
  for(short i=sizeof(x)-1; i>=0; i--)
     n = n->cons(x[i]);
  if ( n->nullp() ) tag = Nil;
  else { tag = Cons;
         hd = n->hd;
	 tl = n->tl;
  };
};

template<class T>
list<T>* list<T>::cons ( T a ) {
  list<T> *n = new list<T>;
  n->tag = Cons;
  n->hd = a;
  n->tl = this;
  return n;
};

template<class T>
int list<T>::length () {
  int n = 0;
  for(list* r = this; r->consp(); r=r->tl) n++;
  return n;
};

template<class T>
list<T>* list<T>::append ( list<T>* x ) {
  if ( nullp() ) return x;
  else return tl->append(x)->cons(hd);
};

template<class T>
list<T>* rev ( list<T>* x, list<T>* y ) {
  if ( x->nullp() ) return y;
  else return rev(x->tl,y->cons(x->hd));
};

template<class T>
list<T>* list<T>::reverse () {
  return rev(this,new list<T>);
};

template<class T>
list<T>* list<T>::sort ( bool (less_than) (T,T) ) {
  int len = length();
  T A[len];
  int k = 0;
  for(list<T>* r = this; r->consp(); r=r->tl)
     A[k++] = r->hd;
  for(int j = len-1; j>=1; j--)
     for(int i = 1; i<=j; i++)
	if (less_than(A[i],A[i-1]))
	{ T tmp = A[i-1];
	  A[i-1] = A[i];
	  A[i] = tmp;
	};
  list<T>* res = new list<T>;
  for(int i = len-1; i>=0; i--)
     res = res->cons(A[i]);
  return res;
};

template<class T>
ostream& operator<<( ostream& s, list<T> *lst ) {
  if (lst->nullp()) return s << "()";
  s << "(" << lst->hd;
  for( list<T>* r = lst->tl; r->consp(); r = r->tl)
     s << "," << r->hd;
  return s << ")";
};

template<class T>
binding<T>::binding ( String s, T c ) {
  env = (new list<pair<String,T>*>)->cons(new pair<String,T>(s,c));
};

template<class T>
binding<T>* binding<T>::extend ( pair<String,T>* x ) {
  binding<T>* res = new binding<T>(this);
  res->env = res->env->cons(x);
  return res;
};

template<class T>
binding<T>* binding<T>::extend ( binding<T>* r ) {
  binding<T>* res = new binding<T>(this);
  res->env = res->env->append(r->env);
  return res;
};

template<class T>
T binding<T>::find ( String n ) {
  for(list<pair<String,T>*>* r = env; r->consp(); r=r->tl)
     if (r->hd->first->eq(n)) return r->hd->second;
};

template<class T>
T binding<T>::find ( String n, T def ) {
  for(list<pair<String,T>*>* r = env; r->consp(); r=r->tl)
     if (r->hd->first->eq(n)) return r->hd->second;
  return def;
};

template<class T>
Names binding<T>::names () {
  list<String>* s = new list<String>;
  for(list<pair<String,T>*>* r = env; r->consp(); r=r->tl)
     s = s->cons(r->hd->first);
  return s->reverse();
};

template<class T>
bool binding<T>::in ( String n ) {
  for(list<pair<String,T>*>* r = env; r->consp(); r=r->tl)
     if (r->hd->first->eq(n)) return true;
  return false;
};

template<class T>
ostream& operator<<( ostream& s, binding<T> *lst ) {
  if (lst->env->nullp()) return s << "[]";
  s << "[" << lst->env->hd;
  for( list<pair<String,T>*>* r = lst->env->tl; r->consp(); r = r->tl)
     s << "," << r->hd;
  return s << "]";
};

template<class T,class S>
bool node<T,S>::member ( list<node<T,S>*>* n ) {
  for(list<node*>* r = n; r->consp(); r=r->tl)
     if (r->hd == this) return true;
  return false;
};

template<class T,class S>
ostream& operator<< ( ostream& s, graph<T,S>* n ) {
  for(list<node<T,S>*>* r = n->nodes; r->consp(); r=r->tl)
  {  s << "{" << r->hd->info << ",";
     for(list<pair<node<T,S>*,S>*>* t = r->hd->edges; t->consp(); t=t->tl)
        s << "(" << t->hd->first->info << "," << t->hd->second << ")";
     s << "}";
  };
  return s;
};