/* ***************************************************************
   File    : fsm_lower.c
   Author  : Himanshu A. Sanghavi
   Advisor : Dr. Vijay K. Garg
   Date    : August 1, 1991

   This file contains the lower level function of the finite state
   machine library.  Most of these functions are for manipulating
   individual states and transitions of a state machine.

   *************************************************************** */


#include "fsm.h"



/* *************************************************************
   Function : get_NTrans

   This function counts the number of transitions going
   out of a given state of a state machine

   Arguments : st_ptr - pointer to the state

   Return Type : int - the number of transitions

   ************************************************************* */

int get_NTrans(st_ptr)
ST_LIST *st_ptr;
{
   int no_of_trans = 0;
   TR_LIST *this;

   if (!st_ptr)
	prog_abort("get_NTrans : NULL pointer passed as argument for (ST_LIST *)");
 
   this = st_ptr->trans;  /* start with the first transition */
   while(this) {  /* count till you reach the last transition */
      ++(no_of_trans);
      this = this->next;
   }

   return(no_of_trans);
}


/* *************************************************************
   Function : find_trans

   This function finds out if a particular transition exists in
   a given state of a state machine

   Arguments : st_ptr - pointer to the state whose transition
                        list is to be checked
               ip - name of the transition being searched for
               nxt_st - name of the state that the transition
                        leads to

   Return Type : (TR_LIST *) returns a pointer to the transition
                 if it exists - a NULL pointer otherwise

   *************************************************************** */

TR_LIST* find_trans(st_ptr, ip, nxt_st)
ST_LIST *st_ptr;
char *ip, *nxt_st;
{
   TR_LIST *this;

   if (!st_ptr)
	prog_abort("find_trans : NULL pointer passed as argument for (ST_LIST *)");

   /* Start with the first transition and check all the transitions
      of the given state */
   this = st_ptr->trans;
   while (this) {

      /* If the input symbol of this transition is the one being
         searched for and the transition leads to the desired next
         state then the required transition has been found */
      if (strcmp(this->input, ip) == 0  &&
		strcmp(this->next_state->name, nxt_st) == 0) break;

      this = this->next;
   }

   /* If the transition exists, "this" points to it otherwise it
      is a NULL pointer */
   return(this);
}


/* **************************************************************
   Function : insert_trans

   This function inserts a transition in a given state of a 
   finite state machine.

   Arguments : fsm_ptr - pointer to the finite state machine
	       st_ptr  - pointer to the state in which the
			 transition is to be inserted
	       ip      - input triggering the transition
	       nxt_st  - new state after the transition

   Return Type : (TR_LIST *) - pointer to the inserted state 

   ************************************************************** */

TR_LIST* insert_trans(fsm_ptr, st_ptr, ip, nxt_st)
FSM *fsm_ptr;
ST_LIST *st_ptr;
char *ip;
char *nxt_st;
{
   ST_LIST *new_state;
   TR_LIST *tmp;

   
   if (!fsm_ptr)
	prog_abort("insert_trans : NULL pointer given as argument for (FSM *)");
   if (!st_ptr)
    	prog_abort("insert_trans : NULL pointer given as argument for (ST_LIST *)");

   /* first check if the transition already exists */
   tmp = find_trans(st_ptr, ip, nxt_st);
   
   /* if it does not exist, insert it */
   if (!tmp) {

      /* allocate storage space */
      tmp = alloc_trans;
     /* tmp->input = (char *) malloc(strlen(ip) + 4);/*static now*/

      strcpy(tmp->input, ip); /* name of the transition */

      /* resultant state after the transition occurs */
      tmp->next_state = insert_state(fsm_ptr, nxt_st);

      /* Insert the transition as the first element of the
         linked list of transitions */
      tmp->next = st_ptr->trans;
      st_ptr->trans = tmp;
   }

   return(tmp);
}


/* *************************************************************
   Function : delete_trans

   This function removes a transition from a state of a finite
   state machine

   Arguments : st_ptr - pointer to the state from which the
                        transition is to be removed
               tr_ptr - pointer to the transition which is to
   			be removed

   Return Type : void

   ************************************************************* */

void delete_trans(st_ptr, tr_ptr)
ST_LIST *st_ptr;
TR_LIST *tr_ptr;
{
   TR_LIST *this, **anchor;

   if (!st_ptr)
	prog_abort("delete_trans : NULL pointer passed as argument for (ST_LIST *)");

   if (!tr_ptr)
	prog_abort("delete_trans : NULL pointer passed as argument for (TR_LIST *)");

   /* Start with the first transition of the given state and check
      each transition.  "anchor" is used to complete the pointer 
      linkage when the transition to be deleted is found and removed 
      from the linked list */
   anchor = &st_ptr->trans;
   this = st_ptr->trans;
   while (this) {

      if (this == tr_ptr) {
         /* transition to be deleted is found so remove it from 
            the list */
	 *anchor = this->next;
	 /*free(this->input);/*static now*/
         free(this);
	 break;
      }

      anchor = &this->next;
      this = this->next;
   } 
}


/* *************************************************************
   Function : get_NStates

   This function finds out the number of states in a given 
   finite state machine

   Arguments : fsm_ptr - pointer to the state machine

   Return Type : int - the number of states
   
   ************************************************************* */

int get_NStates(fsm_ptr)
FSM *fsm_ptr;
{
    int no_of_states = 0;
    ST_LIST *current;

    if (!fsm_ptr) 
	prog_abort("get_NStates : NULL pointer passed as argument for (FSM *)");

    current = fsm_ptr->states;  /* start with the first state */
    while (current) { /* count till you reach the last state */
       ++(no_of_states);
       current = current->next;
    }

    return(no_of_states);
}

/* *************************************************************
   Function : get_NBadStates GREG ADDED

   This function finds out the number of bad states in a given 
   finite state machine

   Arguments : fsm_ptr - pointer to the state machine

   Return Type : int - the number of states
   
   ************************************************************* */

int get_NBadStates(fsm_ptr)
FSM *fsm_ptr;
{
    int no_of_states = 0;
    ST_LIST *current;

    if (!fsm_ptr) 
	prog_abort("get_NStates : NULL pointer passed as argument for (FSM *)");

    current = fsm_ptr->states;  /* start with the first state */
    while (current) { /* count till you reach the last state */
       
		if(strstr(current->name, "@$")!=NULL) /*bad state?*/
			++(no_of_states);
       
		current = current->next;
    }

    return(no_of_states);
}


/* *************************************************************
   Function : find_state(fsm_ptr, name)
   
   This function finds a state (if it exists) in a given
   finite state machine.

   Arguments : fsm_ptr - pointer to the state machine
	       name    - name of the state being searched for 

   Return Type : (ST_LIST *) - Returns a pointer to the state
		 if it exists - a NULL pointer otherwise

   ************************************************************* */

ST_LIST* find_state(fsm_ptr, name)
FSM *fsm_ptr;
char *name;
{
   ST_LIST *current;

   if (!fsm_ptr)
	prog_abort("find_state : NULL state machine pointer given as argument");

   current = fsm_ptr->states; /* start with the first state */

   while(current) {  /* step through the states */
      /* stop if the required state is found */
      if (strcmp(current->name, name) == 0) break;  
      current = current->next;
   }

   /* Return a pointer to the required state if it exists or
      return a NULL pointer if it does not exist */
   return(current);
}


/* **************************************************************
   Function : insert_state

   This function inserts a state into a given finite state machine.
   A new state is inserted only if it does not already exist
   This routine does not read in any transition or other 
   information corresponding to the state.  It only creates
   an entry in the linked list storing the states.  If the 
   state machine does not contain any states, the inserted 
   state is assumed to be the initial state.  This routine
   sets the marked status to "unmarked".

   Arguments : fsm_ptr - pointer to the given state machine
               name    - name of the state to be inserted

   Return Type : (ST_LIST *) - returns a pointer to the 
                 inserted state

   ************************************************************* */

ST_LIST* insert_state(fsm_ptr, name)
FSM *fsm_ptr;
char *name;
{
   ST_LIST *new_state, *current, **anchor;
   
   if (!fsm_ptr) 
	prog_abort("insert_state : NULL pointer given as argument for (FSM *)");

   /* first check if the state already exists */
   new_state = find_state(fsm_ptr, name);

   if (!new_state) {  /* if it does not exist */

      /* allocate storage space */
      new_state = alloc_state;
/*      new_state->name = (char *) malloc(strlen(name) + 8); /*static now*/
	/* + 4 to accomodate marking states with @$ (bad) ..Sudhir */
  
      /* assign appropriate values to all the fields */
      strcpy(new_state->name, name);
      new_state->trans = NULL;

      /* make the state unmarked */
      new_state->marked = UNMKD;

      /* insert the new state in the linked list of states */
      if (fsm_ptr->states) {
         /* insert the new state as the second element of the
            linked list of states since the initial state exists */
         new_state->next = fsm_ptr->states->next;
         fsm_ptr->states->next = new_state;
      }
      else {
         /* Insert the new state as the first element of the
            linked list of states since this is the initial state */
         fsm_ptr->states = new_state;
         new_state->next = NULL;
      }
   }
    return(new_state);
}


/* *************************************************************
   Function : delete_state

   This function removes a state from a finite state machine.
   All transitions (controllable or uncontrollable) which 
   lead to this state are also removed from their respective
   states


   Arguments : fsm_ptr - pointer to the state machine
               st_ptr - pointer to the state to be removed

   Return Type : void

   ************************************************************** */

void delete_state(fsm_ptr, st_ptr)
FSM *fsm_ptr;
ST_LIST *st_ptr;
{
   ST_LIST *current, **st_anchor;
   TR_LIST *this, *next_trans, **tr_anchor;

   if (!fsm_ptr)
	prog_abort("delete_state : NULL pointer passed as argument for (FSM *)");

   if (!st_ptr)
	prog_abort("delete_state : NULL pointer passed as argument for (ST_LIST *)");

   /* First locate the state to be deleted by stepping through the
      list.  While doing so remember the address of the pointer
      pointing to the state to be deleted so that the pointer 
      linkage can be complete after the state is deleted */
   current = fsm_ptr->states;
   st_anchor = &fsm_ptr->states;
   while (current) {
      if (current == st_ptr) break;
      st_anchor = &current->next;
      current = current->next; 
   }

   /* if the state does not exist, do nothing */
   if (!current) return;

   /* remove the state from the pointer linkage */
   *st_anchor = current->next;

   /* Now examine each transition of the state machine and if the
      transition leads to the deleted state, remove it */
   current = fsm_ptr->states;
   while (current) {
      this = current->trans;
      while (this) {
         /* Remember the pointer to the next transition in case
            the current transition is to be deleted */
         next_trans = this->next; 
         /* If this transition leads to the deleted state, 
            delete the transition */
         if (this->next_state == st_ptr) 
	    delete_trans(current, this);
         this = next_trans;
      }
      current = current->next;
   }
   
   /* Now free the storage space utilized by the transitions of
      the deleted state */
   this = st_ptr->trans;
   while (this) {
      next_trans = this->next;
      /*free(this->input);/*static now*/
      free(this);
      this = next_trans;
   }

   /* free the storage utilized by the deleted state itself */
   /*free(st_ptr->name);/*static now*/
   free(st_ptr);
} 


/* ************************************************************
   Function : find_name

   This function checks if a character string (representing some
   name) exists in the given name list.

   Argument : name_list - the list which is to be searched
              name - name of the state to be searched for

   Return Type : int - returns 1 if the name exists in the list
                       returns 0 if it does not

   ************************************************************ */

int find_name(name_list, name)
NAME_LIST *name_list;
char *name;
{
   /* step through the list and search for the name */
   while(name_list) {
      /* if found, return 1 */
      if (strcmp(name_list->name, name) == 0) return(1);
      name_list = name_list->next;
   }

   /* if the name is not found, return 0 */
   return(0);
}


/* ***************************************************************
   Function : delete_name

   This functions deletes the linked list of names given to it as
   argument.  It is used to free the memeory used to store the 
   list of names of states created by the reachability function.

   Arguments : list - pointer to pointer to name list

   Return Type : void

   *************************************************************** */

void delete_name(list_ptr)
NAME_LIST **list_ptr;
{
   NAME_LIST *name_list, *name_ptr;

   name_list = *list_ptr;
   while (name_list) {
      name_ptr = name_list->next;
      free(name_list);
      name_list = name_ptr;
   }

   *list_ptr = NULL;
}


/* *************************************************************
   Function : prog_abort

   This function is called whenever the program has to be aborted
   due to an error.  It prints an error message and aborts the 
   program.

   Arguments : message - the error message to be printed

   Return Type - void

   ************************************************************** */

void prog_abort(message)
char *message;
{
   fprintf(stderr, "%s \n\n", message);
   exit(1);
}
