symbol.cc

this is a lp0 compilator new

//
// ******************************************************************
// * 
// *   Author		: Gerald Carter
// *   Filename		: symbol.h
// *   File created	: 940107
// *
// * This file contains the class definition for a binary
// * search tree.  The tree may only be searched, inserted in to and
// * printed useing the "put to" (ie. '<<') operator.  It constructs
// * the tree using nodes of type symbolNode that hold the data and the
// * left/right child pointers.
// *
// * This file contains all the class member functions' declarations.  All are
// * fully implemented and are also fully documented.
// *
// * ---------------------
// * Modifications
// * ---------------------
// * 961206   [e-mail]
// *		added field to symbolNode to hold the maple function 
// *		name as well a pointer to the function maple expression 
// *		tree.
// *
// ********************************************************************
//


#include <iostream.h>      // cout
#include <string.h>	   // for strdup used in symbolNode constructor
#include "logic.h"         // boolean type and operators
#include "symbol.h"        // symbolNode and symbolTable declaration

// #####################################################################
// ## class symbolNode
// ## 
/*
   Constructors---The first takes two arguements, and character pointer
   and an integer.  The second takes only a symbolNode as the arguement.
*/
symbolNode::symbolNode (char* symName)
{
   name = strdup (symName);	    // allocate space and copy name
   its_a = ITS_A_UNDEFINED;
   maple_name = 0;
   maple_expr = 0; 

}

symbolNode::symbolNode (const symbolNode& item)
{
   name = strdup (item.name);	   // allocate space and copy name
   its_a = item.its_a;
   maple_name = strdup ( item.maple_name );

   // This could be a bad move.  Will be hard to debug and could
   // cause seg fault if points to La-La land.  See the operator= 
   // as well.
   maple_expr = item.maple_expr;
}

/*
   These are the definitions of the = < > operators for symbolNode.  Each
   function simply take a constant reference to another symbolNode as
   the arguement.
*/
symbolNode& symbolNode::operator= (const symbolNode& item)
{
   name = strdup (item.name);	   // allocate space and copy name
   its_a = item.its_a;

   if ( item.maple_name != 0 )
      maple_name = strdup ( item.maple_name );

   // This could be a bad move.  Will be hard to debug and could
   // cause seg fault if points to La-La land.  Se the copy constructor
   // as well.
   maple_expr = item.maple_expr;

   return *this;
}

int symbolNode::operator< (const symbolNode& item)
{
   if ((strcmp (name, item.name)) < 0)
      return TRUE;
   else
      return FALSE;
}

int symbolNode::operator> (const symbolNode& item)
{
   if ((strcmp (name, item.name)) > 0)
      return TRUE;
   else
      return FALSE;
}

int symbolNode::operator== (const symbolNode& item)
{
   if ((strcmp (name, item.name)) == 0)
      return TRUE;
   else
      return FALSE;
}

int symbolNode::operator!= (const symbolNode& item)
{
   if ((strcmp (name, item.name)) != 0)
      return TRUE;
   else
      return FALSE;
}

/*
   This is the overloaded meaning of the "put to" operator for the
   symbolNode class.
*/
ostream& operator<< (ostream& S, const symbolNode& item)
{
   S << item.name;			   // print symbol name
   switch (item.its_a)
   {
      case ITS_A_FUNCTION :
         S << "(function)" << "\t[Maple Function Name = "
           << item.maple_name << "]";
         break;
      case ITS_A_PROCEDURE :
         S << "(procedure)" << "\t[Maple Function Name = " 
	   << item.maple_name << "]";
         break;
      case ITS_A_VARIABLE :
         S << "(variable)";
         break;
      case ITS_A_PROGRAM :
         S << "(program)";
         break;
      case ITS_A_CONSTANT :
         S << "(constant)";
         break;
      default :
         S << "(undefined)";
         break;
   }

   // Return the output stream for next data type
   return S;
}

// This function sets the existence variable of the symbolNode.  If
// the variable is a procedure or function, the method will call
// "nextMapleFunction" to generate a maple function name and 
// return the pointer to the character string containing the
// newly generated name.
int symbolNode::SetExistence (const int exist )
{
   // local variables
   char		func_name[256] = "";

   if ( ( exist >= 0 ) AND ( exist <= 15 ) ) {
      its_a = exist;
      if ( ( its_a == ITS_A_PROCEDURE ) OR (its_a == ITS_A_FUNCTION ) ) {
         nextMapleFunction ( func_name );
         maple_name = strdup ( func_name );
      }
   }
   else
      cerr << "Invalid symbol type passed to class <symbolNode>.\n";

   // successful completion
   return ( its_a );
}	// end of symbolNode::SetExistence ()

// Function to generate the next available maple name.  Currently will
// only generate up to 25 function names.  If asked to do more, the 
// function will complain and use the last generate function name
char* symbolNode::nextMapleFunction ( char return_string[] )
{
   // local variables
   static char		func_array[] = { 'a', 'b', 'c', 'd', 'e', 'g', 'h',
                                         'i', 'j', 'k', 'l', 'm', 'n', 'o',
        				 'p', 'q', 'r', 's', 't', 'u', 'v',
					 'w', 'x', 'y', 'z' };
   static int		next = 0;
   static char		func_name[5] = "a(n)";

   if ( next < 25 )
      func_name[0] = func_array[next++];
   else
      cerr << "The method can only generate up to 25 function names.\n";
   
   // return the generated function name
   strcpy ( return_string, func_name );
   return ( return_string );

}	// end of symbolNode::nextMapleFunction ()

// #####################################################################
// ## class symbolTable
// ## 
/*
   This function searches the binary search tree to determine if the
   item passed as a parameter is in the tree.  The parameters are :
       item => the item to find
*/
symbolNode *symbolTable::Search (const symbolNode& item)
{
   //local variables
   struct node* temp = root;

   while (temp)                            // valid node pointed to
   {
      if ( temp -> data == item )              // node found
	 return ( &temp -> data );
      else if ( temp -> data < item )          // go right
	 temp = temp -> right_child;
      else
	 temp = temp -> left_child;          // go left
   }

   return ( 0 );
}   // end of Search


/*
   This function inserts the given into the binary search tree.  It
   returns a boolean value (from logic.h) that is TRUE if the value was
   inserted and FALSE if it was already there.  The parameters passed
   are :
      item => the data to be inserted
*/
symbolNode *symbolTable::Insert (const symbolNode& item)
{
   // Declare local variables
   struct node* temp = root;            // pointer to parent node to insert
   struct node* next = root;            // look ahead pointer
   symbolNode* result = NULL;
   boolean found = FALSE;               // is item already there?

   if (this->root == 0)                 // if no nodes in tree
   {
      root = new node;                  // insert new node
      root->data = item;                // copy item
      root->left_child = root->right_child = 0;   // child pointers = NULL
      result = &(root->data);
      found = TRUE;
   }

   while ((NOT found) AND (next))      // look ahead to see if there is a
   {                                   //   node already there
      temp = next;                     // increment temp
      if (temp->data == item)          // node found
      {
         result = &(temp->data);
	 found = TRUE;
      }
      else if (temp->data > item)      // go left
	 next = temp->left_child;
      else                             // else go right
	 next = temp->right_child;
   }

   if (NOT found)                      // if node not in tree, then insert
   {                                   //   new one
      if (temp->data > item)           // temp points the parent node of the
      {                                //   child to be inserted
	 temp->left_child = new node;     // insert new node
	 temp = temp->left_child;
	 temp->data = item;
	 temp->left_child = temp->right_child = 0;
	 found = TRUE;
      }
      else
      {
	 temp->right_child = new node;   // insert new node
	 temp = temp->right_child;
	 temp->data = item;
	 temp->left_child = temp->right_child = 0;
	 found = TRUE;
      }
      result = &(temp->data);
   }

   return (result);
}       // end of Insert

/*
   This is the resursive solution the the operator<< ().  The data is printed
   in an infix order with one tree node per line.
*/
int symbolTable::RecursivePrint
   (ostream& S, struct node *current_node) const
{
   if (NOT current_node == 0)
   {
      RecursivePrint (S, current_node->left_child);
      S << current_node->data << "\n";
      RecursivePrint (S, current_node->right_child);
   }
}  // end of RecursivePrint;

void symbolTable::ProcExpression ( ostream& S, node *ptr)
{
   // local variables
   int 		exist;

   if ( ptr != 0 ) {
      ProcExpression ( S, ptr->left_child );
      exist = ptr->data.GetExistence ();
      if ( ( exist == ITS_A_PROCEDURE ) OR ( exist == ITS_A_FUNCTION ) ) {
         mapleNode*	maple_expr;
         S << "assign ( rsolve ( " << ptr->data.GetMapleName () << "=";
         maple_expr = ptr->data.GetMapleExpression ();
         maple_expr -> PrintTree ( S );
         // maple_expr -> PrintGML ( cout );
         S << ", " << ptr->data.GetMapleName () << " ) );\n";
      }
      ProcExpression ( S, ptr->right_child );
   }
}	// end of symbolTable::ProcExpression ()

/*
   This is the recursive soltuion to the problem of a destructor for a binary
   search tree.  The tree is deleted in an postfix order with the tree being
   traversed to left extreme and then the right extreme before tha leaf
   node is deleted.
*/
int symbolTable::DeleteTree (struct node *current_node)
{
   if (current_node)
   {
      DeleteTree (current_node->left_child);
      DeleteTree (current_node->right_child);
      delete current_node;
   }
}   // end of DeleteTree

//********** end of symbol.h ******************************************
//*********************************************************************