TA Lab Program (Stacks & Queues)

//////////////////////////////////////////////////////////////////////////////
///  
///  \file TALab.c
///  \brief Simulates students visiting TAs for help. Demonstrates stacks and
///         queues.
///
///  <br>Author(s): Nicholas Guthrie
///  <br>Created: 2011-03-21
///  <br>Email: nickguthrie@knights.ucf.edu
///  <br>Web: http://nickguthrie.com
///  <br>Title: TA Lab (Stacks & Queues)
///  <br>Course: COP3502C Compute Science I
///  <br> Class #: 16173
///  <br>Section #: 0001
///  <br>Version #: 276
///  
///  THIS SOFTWARE IS PROVIDED BY THE NICHOLAS GUTHRIE''AS IS'' AND ANY EXPRESS
///  OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
///  OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN
///  NO EVENT SHALL UCF BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
///  EXEMPLARY,OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
///  PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
///  OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
///  WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
///  OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
///  ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
///  
////////////////////////////////////////////////////////////////////////////////

///////////////////////////
//   Library Includes    //
///////////////////////////
#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <stdlib.h> //necessary for malloc
#include <string.h>


///////////////////////////
// #defines & Constants  //
///////////////////////////
#define SIZE 300
#define EMPTY -1


///////////////////////////
//  Struct Declarations  //
///////////////////////////
typedef struct COP3502student
{
  char firstName[20];
  char lastName[20];
  int enterTime;
  int numQuestions;
  int numAnswered;
  int laptopSerialNum;
  int number;		///< reference # so queues can be used
} student;

typedef struct teachingAssistant
{
  char name&#91;21&#93;;		///< only use first names for TAs >//
  int startTimes[3];		///< start times for each day of simulatoin >//
  int endTimes[3];		///< end times for each day of simulation >//
  student *studentWithTA;	///< pointer to type struct COP3502student >//
  int minute;		///< # of minutes TA has spent with a student >//
  int number;		///< reference # so queues can be used
  int active;
} TA;


////////////////
//    Stacl   //
////////////////
struct stack
{
  int items&#91;SIZE&#93;;
  int sTop;   
};

////////////////
//    Queue   //
////////////////
// Stores one node of the linked list.
struct node {
  int data;
  struct node* next;
};

// Stores our queue.
struct queue {
  struct node* front;
  struct node* back;
};





///////////////////////////
// Function Declarations //
///////////////////////////

///////////
// Stack //
///////////
void sInitialize(struct stack* stackPtr);
int sFull(struct stack* stackPtr);
int sPush(struct stack* stackPtr, int value);
int sEmpty(struct stack* stackPtr);
int sPop(struct stack* stackPtr);
int sTop(struct stack* stackPtr);

///////////
// Queue //
///////////
void qInit(struct queue* qPtr);
int qEnqueue(struct queue* qPtr, int val);
int qDequeue(struct queue* qPtr);
int qEmpty(struct queue* qPtr);
int qFront(struct queue* qPtr);

////////////////////////
// Input & Processing //
////////////////////////
void getTime(int time, FILE *output);
void printSummary(FILE *output, int time, int numStudentsEntered,
		  int numHappyStudents);





///////////////////////////
//        Main           //
///////////////////////////
int main()
{
  ///////////////
  // Variables //
  ///////////////
  FILE *input, *output;  
  struct COP3502student *Student&#91;3&#93;&#91;300&#93;;
  struct teachingAssistant* Mentor&#91;300&#93;; //DEBUG what is max TA? <= students?
  struct stack *sLaptop;

  struct queue* qLDM;	///< qLDM is a line for students getting laptops
  struct queue* qLine;	///< qLine is a line for students w/laptops
  struct queue* qTA;		///< qTA is a line of TAs ready to serve
  struct queue* qQuestions; ///< gMoreQuestions for students with lots of questions

  int numLaptops;		///< numLaptops #(+)laptops to be put in machine
  int numStudentsPerDay;	///< numStudentsPerDay #(+)students for  M,T,W
  int numPrograms;		///< numPrograms #(+)of programs for the semester
  int numTAs;		///< numTAs #(+) of TAs on duty
  int tserial;		///< tserial temp placeholder for laptop serial #

  int time;	///< time stores as minutes past midnight
  int day;
  int LDMTime;	///< keeps track if LDM has been w/student
  int numStudentsEntered; ///< keeps track of students in lab
  int LabOpen;
  int activeTAs;
  int LDMTimer;
  int numHappyStudents;

  int i, j, k;		///< i,j, k navigation variables
   

     
  ///////////////
  //   Input   //
  ///////////////

  /////////////////////
  // Initializations //
  /////////////////////
  sLaptop = (struct stack*)malloc(sizeof(struct stack));
  qQuestions = (struct queue*)malloc(sizeof(struct queue));
  qLDM = (struct queue*)malloc(sizeof(struct queue));
  qLine = (struct queue*)malloc(sizeof(struct queue));
  qTA = (struct queue*)malloc(sizeof(struct queue));

  sInitialize(sLaptop);
  qInit(qLDM);
  qInit(qLine);
  qInit(qTA);
  qInit(qQuestions);
  output = fopen("out.txt", "w");

     
  for(i = 0; i<3; i++){
    for(j = 0; j<300; j++){
      Student&#91;i&#93;&#91;j&#93; =
	(struct COP3502student*)malloc(sizeof(struct COP3502student));
    }
  }
     
  ////////////////
  //  Open File //
  ////////////////
  input = fopen ("input.txt", "r");
  //file open error checking
  if(input == NULL)
    {
      printf("File not Found, Press ENTER to exit\n");
      getchar();
      //return 0;
    }
 
  ///////////////////
  // Collect Input //
  ///////////////////
  // collect laptop serial numbers & store in Stack
  fscanf(input, "%d", &numLaptops);
  for(i = 0; i < numLaptops; i++){
    fscanf(input, "%d", &tserial);
    sPush(sLaptop, tserial);
  }

  // collect TA info
  fscanf(input, "%d", &numTAs); //# of TAs


  // store data on TAs
  for(i = 0; i < numTAs; i++){
    Mentor&#91;i&#93; = 
      (struct teachingAssistant*)malloc(sizeof(struct teachingAssistant));

    Mentor&#91;i&#93;->number = i;  //store reference # of TA
    Mentor[i]->active = 0;
    Mentor[i]->studentWithTA = NULL;
    Mentor[i]->minute = 0;
    
    fscanf(input, "%s", Mentor[i]->name); // store first name
    for(j = 0; j < 3; j++){
      fscanf(input, "%d", &Mentor&#91;i&#93;->startTimes[j]); //start times
      fscanf(input, "%d", &Mentor[i]->endTimes[j]); //end times
    }
  }


  fscanf(input, "%d", &numPrograms); // # of programs



  /////////////////////
  //      OUTPUT     //
  /////////////////////
  
  // PROGRAMS
  for(i = 0; i<numPrograms; i++){
    fprintf(output, "**********\nProgram %d:\n**********\n\n", i+1);

    // DAYS
    // process all students for given day
    for(day = 0; day<4; day++){
      switch(day){
      case 1:
	fprintf(output, "\n\nMonday's Lab Summary:\n");
	printSummary(output, time, numStudentsEntered, numHappyStudents);
	break;
      case 2:
	fprintf(output, "\n\nTuesday's Lab Summary:\n");
	printSummary(output, time, numStudentsEntered, numHappyStudents);
	break;
      case 3:
	fprintf(output, "\n\nWednesday's Lab Summary:\n");
	printSummary(output, time, numStudentsEntered, numHappyStudents);
	fclose(input);
	fclose(output);
	return 0; //exit the program here
      }

      ///////////////
      // Variables //
      ///////////////
      time = 0;	///< time stores as minutes past midnight
      LDMTime = 0;	///< keeps track if LDM has been w/student
      numStudentsEntered = 0; ///< keeps track of students in lab
      LabOpen = 0;
      activeTAs = 0;
      LDMTimer = 0;
      numHappyStudents = 0;
      time = -1;
      
      

      fscanf(input, "%d", &numStudentsPerDay);
      for(k = 0; k<numStudentsPerDay; k++){
	Student&#91;day&#93;&#91;k&#93;->number = k;
	Student[day][k]->laptopSerialNum = 0;
	Student[day][k]->numAnswered = 0;
	// store student entry time
	fscanf(input, "%d", &Student[day][k]->enterTime);
		    
	// store student names
	fscanf(input, "%s", Student[day][k]->firstName);
	fscanf(input, "%s", Student[day][k]->lastName);

	// store student questions
	fscanf(input, "%d", &Student[day][k]->numQuestions);
      }

      // print the day
      switch(day){
      case 0:
	fprintf(output, "Monday:\n\n");
	break;
      case 1:
	fprintf(output, "\n\nTuesday:\n\n");
	break;
      case 2:
	fprintf(output, "\n\nWednesday:\n\n");
	break;
      }

    

      while(activeTAs != -1 || !qEmpty(qLDM))
	{
	  time++;
	
	  	  
	  //Check Newly Available TAs
	  for(k = 0; k<numTAs; k++){
	    if(Mentor&#91;k&#93;->startTimes[day] == time && 
	       Mentor[k]->endTimes[day] != time){
	      getTime(time, output);
	      fprintf(output, "%s has begun lab hours.\n", Mentor[k]->name);
	      Mentor[k]->active = 1;
	      qEnqueue(qTA, k);
	      LabOpen = 1;
	      activeTAs++;
	    }}//End Newly Available TAs

  
	  //Process LDM
	  if(!qEmpty(qLDM)){
	    //time to offset the odd behavior of LDM by 1 minute
	    if(LDMTimer == 0){
	      LDMTimer++;
	    }
	    else{
	      LDMTimer = 0;
	      //student has no laptop (therefore getting one)
	      if(Student[day][qFront(qLDM)]->laptopSerialNum == 0){
		//lab is open so getting a laptop
		if(LabOpen == 1){
		  getTime(time, output);
		  fprintf(output, "%s %s has borrowed laptop %d and moved to the TA line.\n",
			  Student[day][qFront(qLDM)]->firstName,
			  Student[day][qFront(qLDM)]->lastName, sTop(sLaptop));
		  Student[day][qFront(qLDM)]->laptopSerialNum = sTop(sLaptop);
		  sPop(sLaptop);
		  qEnqueue(qLine, qFront(qLDM));
		}
		//lab is closed so never got a laptop & leaving
		else{
		  getTime(time, output);
		  fprintf(output, "%s %s never even got a laptop and went home"
			  " FRUSTRATED.\n",
			  Student[day][qFront(qLDM)]->firstName,
			  Student[day][qFront(qLDM)]->lastName);
		}
	      }
	      //has a serial so returning a laptop
	      else{
		// forced to return the laptop w/questions left
		if((double)Student[day][qFront(qLDM)]->numAnswered /
		   (double)Student[day][qFront(qLDM)]->numQuestions <= 0.75){
		  getTime(time, output);
		  fprintf(output, "%s %s has returned laptop %d and went"
			  " home FRUSTRATED.\n",
			  Student&#91;day&#93;&#91;qFront(qLDM)&#93;->firstName,
			  Student[day][qFront(qLDM)]->lastName,
			  Student[day][qFront(qLDM)]->laptopSerialNum);
		}    
		// no questions left, HAPPY
		else{
		  getTime(time, output);
		  fprintf(output, "%s %s has returned laptop %d and went"
			  " home HAPPY.\n", 
			  Student[day][qFront(qLDM)]->firstName,
			  Student[day][qFront(qLDM)]->lastName,
			  Student[day][qFront(qLDM)]->laptopSerialNum);
		  numHappyStudents++;
		}
		sPush(sLaptop, Student[day][qFront(qLDM)]->laptopSerialNum);
	      }
	      qDequeue(qLDM); //DEBUG - this doesn't seem to work
	    }}//LDM Processed



	  //Answer Questions
	  for(k = 0; k<numTAs; k++){
	    if(Mentor&#91;k&#93;->studentWithTA != NULL){
	      Mentor[k]->minute++;
             
	      //if time is 5 remove student (to LDM or Line)
	      if(Mentor[k]->minute == 5){
		Mentor[k]->studentWithTA->numAnswered++;
		if(Mentor[k]->studentWithTA->numQuestions - 
		   Mentor[k]->studentWithTA->numAnswered > 0){
		  qEnqueue(qQuestions, Mentor[k]->studentWithTA->number);          
		}
		else{
		  getTime(time, output);
		  fprintf(output, "%s %s has no more questions and will now "
			  "return the laptop.\n",
			  Mentor[k]->studentWithTA->firstName, 
			  Mentor[k]->studentWithTA->lastName);
		  qEnqueue(qLDM, Mentor[k]->studentWithTA->number);          
		}
		Mentor[k]->minute = 0;
		Mentor[k]->studentWithTA = NULL;
	      }}}//Questions Answered


	  
	  //move the people with more questions to Line (get less priority than
	  //those who haven't asked)
	  while(!qEmpty(qQuestions)){
	    getTime(time, output);
	    fprintf(output, "%s %s has had one question answered and gotten back"
		    " in line.\n",
		    Student[day][qFront(qQuestions)]->firstName, 
		    Student[day][qFront(qQuestions)]->lastName); 
	    qEnqueue(qLine, qFront(qQuestions));
	    qDequeue(qQuestions);
          }//end qQuestions to qLine



	  //have TAs start working with students
	  for(k = 0; k<numTAs; k++){
	    if(Mentor&#91;k&#93;->active == 1 && Mentor[k]->studentWithTA == NULL
	       && !qEmpty(qLine)){
	      getTime(time, output);
	      fprintf(output, "%s %s is getting help from %s.\n",
		      Student[day][qFront(qLine)]->firstName,
		      Student[day][qFront(qLine)]->lastName, Mentor[k]->name);
	      Mentor[k]->studentWithTA = Student[day][qFront(qLine)];
	      qDequeue(qLine);
	    }}//END TA's working with Students



	  //have students enter from outside
	  while(Student[day][numStudentsEntered]->enterTime == time &&
		LabOpen == 1){
	    getTime(time, output);
	    fprintf(output, "%s %s has arrived in the Cave.\n",
		    Student[day][numStudentsEntered]->firstName, 
		    Student[day][numStudentsEntered]->lastName);
	    qEnqueue(qLDM, numStudentsEntered);
	    numStudentsEntered++;
          }//End Students Entering


	
	  //Check for TA's that have to leave
	  for(k = 0; k<numTAs; k++){
	    //DEBUG - having trouble setting special case for TAs + student
	    if(Mentor&#91;k&#93;->endTimes[day] == time && Mentor[k]->active == 1){
	      getTime(time, output);
	      fprintf(output, "%s has finished lab hours.\n",
		      Mentor[k]->name);
	      Mentor[k]->active = 0;
	      activeTAs--;
	      if(activeTAs == 0){
		activeTAs = -1;
		LabOpen = 0;
		while(!qEmpty(qLine)){
		  qEnqueue(qLDM, qFront(qLine));
		  qDequeue(qLine);
                }
		while(!qEmpty(qQuestions)){
		  qEnqueue(qLDM, qFront(qQuestions));
		  qDequeue(qQuestions);
		}
	      }}}//leaving TAs


	}//end time
    }//end day
  }//end program
}



//////////////////////////////
// Function Implamentations //
//////////////////////////////

////////////////////////////////////////////////////////////////////////////////
///
///  \brief Prints time in a structured format to output file.
///  \param time The time to print
///  \param *output The file to output to.
///  \return void
///
////////////////////////////////////////////////////////////////////////////////
void getTime(int time, FILE *output){
  if(time/60 == 0)
    fprintf(output, "12:%.2d PM:  ", time%60);
  else
    fprintf(output, "%d:%.2d PM:  ", time/60, time%60);
}


////////////////////////////////////////////////////////////////////////////////
///
///  \brief Prints the summary of events during a day at the lab.
///  \param *output The file to output to.
///  \param time The time the lab was open.
///  \param numStudentsEntered The number of students that entered the lab.
///  \param numHappyStudents The number of students that left the lab happy.
///
////////////////////////////////////////////////////////////////////////////////
void printSummary(FILE *output, int time, int numStudentsEntered,
		  int numHappyStudents){
  fprintf(output, "The TA Lab was open for %d hours and %d minutes.\n%d students"
	  "visited the lab. Out of those students, only %d left happy.\n"
	  "The remaing left frustrated.\n\nLesson Learned:  "
	  "Do not procrastinate! Start programs early!\n",
	  time/60, time%60, numStudentsEntered, numHappyStudents);

}



///////////////////////////
//    Stack Functions    //
///////////////////////////

////////////////////////////////////////////////////////////////////////////////
///
/// \brief Initializes a stack by properly setting the value of sTop.
/// \return void
/// 
////////////////////////////////////////////////////////////////////////////////
void sInitialize(struct stack* stackPtr) {
  stackPtr->sTop = -1;
}


////////////////////////////////////////////////////////////////////////////////
///
/// \brief Adds a value onto a stack (pushes).
/// \param stackPtr a valid struct stackPtr
/// \param value value to push
/// \return 1 if the push is successfull
///         0 if the stack is Full and the pusth can't be done
///
////////////////////////////////////////////////////////////////////////////////
int sPush(struct stack* stackPtr, int value) {
    
  // Check if the stack is full.
  if (sFull(stackPtr))
    return 0;
    
  // Add value to the top of the stack and adjust the value of the top.
  stackPtr->items[stackPtr->sTop+1] = value; //DEBUG - cause segfault
  (stackPtr->sTop)++;
  return 1;
}


////////////////////////////////////////////////////////////////////////////////
///
/// \brief Checks to see if stackPtr is full.
/// \param stackPtr struct stackPtr to check
/// \return  true if the stack pointed to by stackPtr is full.
///
////////////////////////////////////////////////////////////////////////////////
int sFull(struct stack* stackPtr) {
  return (stackPtr->sTop == SIZE - 1);
}


////////////////////////////////////////////////////////////////////////////////
///
/// \brief Checks to see if stackPtr is empty.
/// \param stackPtr struct stackPtr to check
/// \return true if the stack pointed to by stackPtr is empty.
///
////////////////////////////////////////////////////////////////////////////////
int sEmpty(struct stack* stackPtr) {
  return (stackPtr->sTop == -1);
}

////////////////////////////////////////////////////////////////////////////////
/// 
/// \brief Checks to see if stackPtr is full.
/// /pre The stack pointed to by stackPtr is NOT empty.
/// \param stackPtr struct stackPtr to check
/// \return The value on the top of the stack is popped and returned IF NOT empty
///         -1 IF the stack pointed to by stackPtr is empty.
/// 
////////////////////////////////////////////////////////////////////////////////
int sPop(struct stack* stackPtr) {
    
  int retval;
    
  // Check the case that the stack is empty.
  if (sEmpty(stackPtr))
    return EMPTY;
    
  // Retrieve the item from the top of the stack, adjust the top and return
  // the item.
  retval = stackPtr->items[stackPtr->sTop];
  (stackPtr->sTop)--;
  return retval;
}


////////////////////////////////////////////////////////////////////////////////
///
/// \brief Returns the top of stackPtr.
/// \param stackPtr is a NOT empty stack
/// \return The value on the top of the stack if the stack is NOT empty
///         -1 IF the stack pointed to by stackPtr is empty
///
////////////////////////////////////////////////////////////////////////////////
int sTop(struct stack* stackPtr) {
    
  // Take care of the empty case.
  if (sEmpty(stackPtr))
    return EMPTY;
    
  // Return the desired item.
  return stackPtr->items[stackPtr->sTop];
}




///////////////////////////
//    Queue Functions    //
///////////////////////////

////////////////////////////////////////////////////////////////////////////////
///
/// \brief Initializes a que by properly setting members front & back.
/// \param qPtr valid struct queue
/// \post the struct qPtr points to will be set up to represent an empty queue
/// \return void
///
////////////////////////////////////////////////////////////////////////////////
void qInit(struct queue* qPtr) {
  // Just set both pointers to NULL!
  qPtr->front = NULL;
  qPtr->back = NULL;
}


////////////////////////////////////////////////////////////////////////////////
/// 
/// \brief Adds val to the front of the queue.
/// \param qPtr points to a valid struct que
/// \param val is the value to enqueue into the queue pointed to by qPtr
/// \return 1 IF the operation is successful
///         0 IF not successfull, & no change will be made to the queue
///
////////////////////////////////////////////////////////////////////////////////
int qEnqueue(struct queue* qPtr, int val) {

  struct node* temp;
    
  // Allocate space for a new node to add into the queue.
  temp = (struct node*)malloc(sizeof(struct node));
    
  // This case checks to make sure our space got allocated.
  if (temp != NULL) {
             
    // Set up our node to enqueue into the back of the queue.
    temp->data = val;
    temp->next = NULL;
        
    // If the queue is NOT empty, we must set the old "last" node to point
    // to this newly created node.
    if (qPtr->back != NULL)
      qPtr->back->next = temp;
        
    // Now, we must reset the back of the queue to our newly created node.
    qPtr->back = temp;
        
    // If the queue was previously empty we must ALSO set the front of the
    // queue.
    if (qPtr->front == NULL)
      qPtr->front = temp;
        
    // Signifies a successful operation.
    return 1;
  }
    
  // No change to the queue was made because we couldn't find space for our
  // new enqueue.
  else
    return 0;   
}


////////////////////////////////////////////////////////////////////////////////
///
/// \brief Dequeues one element from the front of the queue.
/// \param qPtr points to a valid struct queue.
/// \post  IF the queue pointed to by qPtr is non-empty, then the value at the
///            front of the queue is deleted from the queue and returned.
///         Otherwise, -1 is returned to signify that the queue was already empty
///            when the dequeue was attempted.
///  \return value at the front of the que IF the queue is non-empty
///          -1 if the queue was already empty
///
////////////////////////////////////////////////////////////////////////////////
int qDequeue(struct queue* qPtr) {
    
  struct node* tmp;
  int retval;
    
  // Check the empty case.
  if (qPtr->front == NULL)
    return EMPTY;
    
  // Store the front value to return.
  retval = qPtr->front->data;
        
  // Set up a temporary pointer to use to free the memory for this node.
  tmp = qPtr->front;
    
  // Make front point to the next node in the queue.
  qPtr->front = qPtr->front->next;
    
  // If deleting this node makes the queue empty, we have to change the back
  // pointer also!
  if (qPtr->front == NULL)
    qPtr->back = NULL;
        
  // Free our memory.
  free(tmp);
    
  // Return the value that just got dequeued.
  return retval;
}


////////////////////////////////////////////////////////////////////////////////
///
/// \brief Returns the data of qFront from a struct qPtr.
/// \param qPtr points to a valid struct queue.
/// \return value at front  if the queue pointed by qPtr is non-empty
///         -1              if the queue is empty
///
////////////////////////////////////////////////////////////////////////////////
int qFront(struct queue* qPtr) {
  if (qPtr->front != NULL)
    return qPtr->front->data;
  else
    return EMPTY;
}



////////////////////////////////////////////////////////////////////////////////
///
/// \brief Checks to see if the queue is empty.
/// \param qPtr points to a valid struct queue.
/// \return true if the queue pointed by qPtr is empty
///
////////////////////////////////////////////////////////////////////////////////
int qEmpty(struct queue* qPtr) {
  return qPtr->front == NULL;
}

Leave a Reply

You must be logged in to post a comment.