/******************************************************************************** * * The basic library for strings, lists, exprs etc * * Copyright (c) 1999-2003 by Leonidas Fegaras, the University of Texas at * Arlington. All rights reserved. * Programmer: Leonidas Fegaras, UTA * Date: 4/12/97 * ********************************************************************************/ #ifndef __basic_h__ #define __basic_h__ #include #include #include #include #include "error.h" static int name_counter = 0; /*-------------------------------------------------------------------------------- - Strings ---------------------------------------------------------------------------------*/ class string: public gc { private: char* sp; /* the string content */ public: /* string constructors */ string (); string ( const char* ); string ( const int n ); string ( const long n ); string ( const double x ); /* return the string content; use it with caution */ inline const char* content () const { return sp; } /* string comparisons */ bool operator == ( const string ) const; bool operator != ( const string ) const; bool operator <= ( const string ) const; bool operator >= ( const string ) const; bool operator < ( const string ) const; bool operator > ( const string ) const; inline bool eq ( const string* s ) const { return *this == *s; }; inline bool eq ( const char* s ) const { return strcmp(sp,s) == 0; }; /* string concatenation */ friend const string operator + ( const string, const string ); friend const string operator + ( const string, const char* ); friend const string operator + ( const char*, const string ); /* string length */ int length () const; /* the nth character of string */ char nth ( int ) const; /* create a new string by copying the k characters of the string starting from n */ const string substring ( int n, int k ) const; /* position of a string inside a string */ int position ( const string ) const; /* map a string into an integer; it is used in hashing */ unsigned long hash () const; /* new_name() returns a name that hasn't been used before */ friend string* new_name (); /* I/O functions */ void write ( ostream& to ) const; friend string* reads ( istream& from ); /* print & read a string */ friend ostream& operator << ( ostream&, const string ); friend ostream& operator << ( ostream& s, string* x ) { return s << *x; }; }; typedef string* String; /*-------------------------------------------------------------------------------- - pair is a pair with two elements: one of type T and one of type S ----------------------------------------------------------------------------------*/ template class pair: public gc { public: T first; S second; pair ( const T x, const S y ) { first = x; second = y; }; }; template pair* Pair ( const T x, const S y ) { return new pair(x,y); }; template ostream& operator<< ( ostream& s, pair* p ); /*-------------------------------------------------------------------------------- - list is a list of elements of type T ----------------------------------------------------------------------------------*/ template class list: public gc { private: enum { Nil, Cons } tag; public: T hd; /* list head */ list* tl; /* list tail */ /* list constructor */ list () { tag = Nil; }; /* test whether the list is null or not */ inline bool nullp () const { return (tag==Nil); }; inline bool consp () const { return (tag==Cons); }; /* construct a new list cell */ list* cons ( const T ); /* list size */ int length () const; /* append the argument to the end of the list forming a new list */ list* append ( list* ) const; friend inline list* Append ( list* x, list* y ) { return x->append(y); }; /* list reverse */ list* reverse () const; /* the nth element of a list */ const T nth ( int n ) const; /* check for membership in a list */ bool member ( const T, bool (eq)(const T,const T) ) const; /* checking if argument is subset of the list */ bool subset ( list*, bool (eq)(const T,const T) ) const; /* sort the list using bubble sort */ list* sort ( bool (less_than)(const T,const T) ) const; }; /* display a list */ template ostream& operator<< ( ostream&, list* ); template list* Cons ( const T x, list* r ) { return r->cons(x); }; typedef list* Names; /*-------------------------------------------------------------------------------- - binding lists associate names with values of type T --------------------------------------------------------------------------------*/ template class binding: public gc { public: list*>* env; /* binding constructors */ binding () { env = new list*>; }; binding ( const binding* e ) { env = e->env; }; binding ( list*>* e ) { env = e; }; binding ( pair* x ); binding ( String, T ); /* extend the binding list with a new binding */ binding* extend ( pair* x ) const; inline binding* extend ( String s, const T c ) const { return extend(new pair(s,c)); }; /* append two binding lists */ binding* extend ( binding* r ) const; /* find a value T given its name */ const T find ( String ) const; /* find a value T given its name; if you don't find return a default value */ const T find ( String, const T ) const; /* is name bound in the binding list? */ bool in ( String ) const; /* return the list of all the names bound in the binding list */ Names names () const; inline int length () const { return env->length(); }; }; /* display a binding list */ template ostream& operator<< ( ostream&, binding* ); /*-------------------------------------------------------------------------------- - This is the data structure to represent algebraic forms, plans, etc --------------------------------------------------------------------------------*/ class expr; typedef expr* Expr; typedef list* Params; const int screen_size = 100; /* used in pretty printing */ class expr: public gc { public: typedef enum { VAR, INT, REALN, STRING, FNC, ERROR } tagtype; private: tagtype tag; /* the type of expression */ Expr etype; /* type information */ unsigned long hash_value; /* the hash key of the Expr */ int size () const; public: union { String Variable; long Integer; double Real; String Estring; struct { Expr Name; Params Parameters; } Function; } info; /* expr constructors */ expr () { tag = ERROR; hash_value = 0; etype = NULL; }; friend Expr variable ( String ); friend inline Expr variable ( const char* s ) { return variable(new string(s)); }; friend Expr integer ( long ); friend Expr real ( double ); friend Expr estring ( String ); friend inline Expr estring ( const char* s ) { return estring(new string(s)); }; friend Expr function ( Expr name, list* params ); /* accessors */ inline Expr type () const { return etype; }; inline String name () const { return info.Variable; }; inline list* arguments () const { return info.Function.Parameters; }; /* checking the type of expr */ inline bool variablep () const { return (tag==VAR); }; inline bool integerp () const { return (tag==INT); }; inline bool realp () const { return (tag==REALN); }; inline bool stringp () const { return (tag==STRING); }; inline bool functionp () const { return (tag==FNC); }; /* destructively, update the type information */ void set_type ( Expr tp ) { etype = tp; }; /* deep equality */ bool eq ( Expr ) const; /* deep copy */ Expr copy () const; /* check if an expr is a member of a list of exprs or a list of strings */ friend bool member ( Expr, list* ); friend bool member ( Expr, list* ); /* substitute all occurrences of term in e or es with value */ friend Expr subst_expr ( Expr term, Expr value, Expr e ); friend list* subst_list ( Expr term, Expr value, list* es ); friend inline Expr substitute ( Expr e, Expr value ) { return subst_expr(e->arguments()->hd,value,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; used for hashing in memoization */ unsigned long hash (); /* print with indentations to look nice */ void pretty_print ( int n, ostream& s ) const; /* I/O functions */ friend Expr read ( istream& ); void write ( ostream& ) const; /* print an expr into a string */ String into_string () const; /* translation from/to a binary string */ friend Expr string_to_expr ( String s ); friend Expr read_expr ( const char* s ); }; ostream& operator<< ( ostream&, Expr ); #define Nil (new list) const char* fform ( const char* fmt, ... ); /*-------------------------------------------------------------------------------- - The template methods' code must be included here, since templates are macros --------------------------------------------------------------------------------*/ #include "basic_templates.h" #endif