Link to home
Start Free TrialLog in
Avatar of John500
John500Flag for United States of America

asked on

(Question For Todd Niec) Queue Functions

Todd,

Thanks again for the help!!  I made it in time.

      /*
      This program will demonstrate the behaviour of a queue by simulating
      the process of jobs being submitted to a print queue.  Each job inserted
      or removed from the queue will be output to the screen stating the time of
      occurrence in milliseconds.  Jobs removed from the queue will also display
      the elapsed wait time.  The program ends showing the average wait time for
      all jobs.  The queue has been      implemented using a static array and the
      mechanism for tracking its length is a modulas operation on the head or
      tail.  The queue is also Circular.  If the input file contains any excess
      carriage returns at the end of the the data, the last item processed will
      be processed again creating false output.
      */

      #include <stdio.h>
      #include <stdlib.h>
      #include <string.h>
      #define MAX_Q_SIZE 30                                    /* max length of static queue */
      #define ID_LENGTH 10                                          /* size of print job ID # */

      typedef enum {FALSE, TRUE} Boolean;            /* boolean data type */

      typedef struct {                                                /* define the base data type */
            char jobID[ID_LENGTH];                              /* for the queue: a string */
            unsigned int insertTime;                        /* and an unsigned int for time */
      } dataType;                                                            /* ---- DATA TYPE ---- */

      typedef struct {                                                        /* define the structure of */
            dataType elements[MAX_Q_SIZE];                                      /* the static queue: a list */
            int head;                                                              /* of elements, a head ptr, */
            int tail;                                                              /* and a tail pointer */
      } queueADT;                                                                    /* ---- QUEUE ADT ---- */

      void readFile(queueADT *);

                                                                                                      /*  Queue Maintainence  */
      Boolean insert(queueADT *, dataType);                    /* insert an element */
      Boolean insertJob(queueADT *, dataType);              /* non ADT function */
      Boolean delet(queueADT *, dataType *);                        /* delete an element */
      Boolean removeJob(queueADT *,
                                          dataType *, unsigned int*);      /* non ADT function */
      Boolean full(queueADT);                                                      /* test for full queue */
      Boolean empty(queueADT);                                                /* test for empty queue */
      void initializeQueue(queueADT *);                              /* set up a new queue */



      /* ------------------------  main  ---------------------------------*/

      int main(void)
      {
            /* Display the menu and get the entry: r, or q   */

            char response='b';   /* initialize to start while loop */

            dataType Dummy;    /* used to destroy the queue upon exit of the proram */
            queueADT queue;
            initializeQueue(&queue);


            while ((response != 'q') && (response != 'Q'))
            {
                  fflush(stdin);
                  printf("\n\n");
                  printf("r)ead,   q)uit,\n\n");
                  printf("Selection:\n\n");
                  response = getchar();
                  fflush(stdin); /* flush I/O buffers - in case more than one char was entered */
                  printf("\n");

                  if ((response != 'q') && (response != 'Q'))
                  {
                        switch (response)
                        {
                              case 'r':
                              case 'R': /* Access Input File */
                                    readFile(&queue);
                                    break;
                              default:
                                    break;
                        }                                                                /* end switch  */
                  }                                       /* end if   */
            }                                              /* end while  */


            while(!empty(queue)){
                  delet(&queue, &Dummy);
            }
            printf("Queue destroyed!\n");

            return 0;
      }                                             /* end main  */


      /* ------------------------  Read File  ------------------------------
      Input: The initialized queue passed from main
      Output: Prints the average wait time for all print jobs upon termination
      Returns: -
      Assumptions: A .txt data file is input from the user containing a maximum
                               of one time-stamp and print-jobID per line.
      Description: Examines incoming file to determine if each line should be
                               processed as a queue insert or remove.  It also calculates
                               the average elapsed/wait time for all jobs in the queue by
                               receiving each elapsed time from the removeJob function as
                               a pointer to an unsigned int.
      */

      void readFile(queueADT *q)
      {

            FILE *inputFile;              /* input file pointer  */
            char fname[40];
            char buff[20];
            char *token;
            unsigned int totalElapsedTime = 0;      /* keeps the running total */
            unsigned int avgWaitTime;        /* elapsed time divided total jobs (count)*/
            unsigned int count = 0;      /* counter for all jobs removed from queue */
            unsigned int curElapsed;     /* value received from removeJob */
            unsigned int *elapsed = &curElapsed;
            dataType stamp_job;          /* struct to hold a time-stamp and jobID */
            dataType *stampJob = &stamp_job;

            printf("Enter a file to read:\n\n");
            scanf(" %s", fname);
            inputFile = fopen(fname, "r");

                        if( inputFile == NULL ) {
                              printf("Unable to open datafile %s\n\n", fname );
                              return;
                        }

                        while(!feof(inputFile)){

                              fgets(buff, 20, inputFile);

                              if (strlen(buff) < 3)    /* If there is no stamp or data */
                                    continue;

                                    /* strtok() used to obtain time and jobID from buffer */
                                    token = strtok(buff, " \n");
                                    stamp_job.insertTime = atoi(token);

                                    /*continue until space or end of line */
                                    token = strtok(0, " \n");

                                    if(token == NULL){
                                          removeJob(q, stampJob, elapsed);

                         /* keep running total of elapsed time for jobs waiting in queue */

                                          totalElapsedTime = (totalElapsedTime + curElapsed);
                                          count++;
                                          avgWaitTime = totalElapsedTime/count;
                                          continue;
                                    }
                                    else{
                                          strcpy(stamp_job.jobID, token);
                                          insertJob(q, stamp_job);
                                    }

                        } /* end of while  */
                        printf("Average wait time for print jobs:\n");
                        printf(" %i milliseconds!\n", avgWaitTime);
      }  /*end readFile  */

      /* ------------------ Initialize Queue -------------------------------
      Input: The queue pointer passed from main
      Output: -
      Returns: -
      Assumptions: The QueueADT struct has been declared within main prior
                               to passing the queue pointer to initializeQueue()
      Description: assigns the head and tail ints to the same position.
      */

      void initializeQueue(queueADT *q)
      {
            q->head = q->tail = MAX_Q_SIZE -1;
      }


      /* ------------------------- Empty -----------------------------------
      Input: The queue passed from delete()
      Output: -
      Returns: - Boolean, true if the head int is equal to the tail int
      Assumptions: -
      Description: If the head is equal to the tail, the queue has no items
                               in it because the tail is incremented with each insert.
      */

      Boolean empty(queueADT q)
      {
            if(q.head == q.tail)
                  return TRUE;
            else
                  return FALSE;
      }


      /* -------------------------- Full -----------------------------------
      Input: The queue passed from insert()
      Output: -
      Returns: - Boolean, true if the tail + 1 is equal to the head
      Assumptions: -
      Description: If the head int is equal to the tail int, the queue has
                               no items in it because the tail is incremented with each
                               insert.
      */
      Boolean full(queueADT q)
      {
            int temp;

            temp = (q.tail + 1) % MAX_Q_SIZE;

            if(temp == q.head)
                  return TRUE;
            else
                  return FALSE;
      }

      /* ------------------------- Insert ----------------------------------
      Input: The queue pointer and dataType struct passed from insertJob()
      Output: -
      Returns: - Boolean, true if a job was inserted onto the queue
      Assumptions: -
      Description: After ensuring that the queue is not full, the tail is
                               first incremented, then the new dataType is inserted in
                               the tail position.
      */

      Boolean insert(queueADT *q, dataType value)
      {

            if(!full(*q)){
                  q->tail = (q->tail + 1)% MAX_Q_SIZE;
                  q->elements[q->tail] = value;
                  return TRUE;
            }
            else
                  return FALSE;

      }

      /* -------------------------InsertJob --------------------------------
      Input: The queue pointer and dataType struct passed from readFile()
      Output: Generates a message whether the print-job was inserted or not
      Returns: - Boolean, true if a job was inserted onto the queue
      Assumptions: -
      Description: Solely responsible for printing in order to maintain the
                               ADT functionality of insert()
      */

      Boolean insertJob(queueADT *q, dataType value)
      {
            int result;
            result = insert(q, value);

                  if(result == 1){
                        printf("Job '%s' sent to queue at %i!\n", value.jobID,value.insertTime);
                        return TRUE;
                  }
                  else{
                        printf("Queue is full, job %s denied!\n", value.jobID);
                        return FALSE;
                  }
      }


      /* ------------------------- Delete ----------------------------------
      Input: The queue pointer and dataType struct passed from removeJob()
      Output: -
      Returns: - Boolean, true if a job was deleted/removed from the queue
      Assumptions: -
      Description: After ensuring that the queue is not empty, the head is
                               first incremented, then the dataType needed is accessed
                               from the real head position.  It isn't until the following
                               call to delete() that the current job is lost/deleted.
      */

      Boolean delet(queueADT *q, dataType *job)
      {
            if(!empty(*q)){
                  q->head = (q->head + 1) % MAX_Q_SIZE;         /* update queue head  */

                  /* changes dataType located in readFile()*/
                  *job = q->elements[q->head];
                  return TRUE;
            }
            else
                  return FALSE;
      }

      /* ----------------------- removeJob ---------------------------------
      Input: The queue pointer, a dataType pointer and unsigned int pointer
      Output: Generates a message whether the print-job was processed or not
      Returns: - Boolean, true if a job was deleted/removed from the queue
      Assumptions: -
      Description: Responsible for printing to maintain the ADT functionality
             of delete() and to calculate elapsed time of jobs waiting in the
             queue.  The elapsed time is calculated by first accessing the incoming
             dataType time (curTime) read in from the readFile() function.  Second,
             the outgoing or changed dataType from the delete() function is
             accessed using the same dataType pointer as the first, to obtain the
             queue insertTime again.  The second insertTime is then subtracted from
             the first (curTime) to arrive at the elapsed time.
      */


      Boolean removeJob(queueADT *q, dataType *datatype, unsigned int *elapsed)
      {
            Boolean result;
            unsigned int curTime = datatype->insertTime;
            unsigned int elapsedTime;

            result = delet(q, datatype);

                  if(result == TRUE){
                                                                   /*the updated insertTime from delete()*/
                        elapsedTime = curTime - datatype->insertTime;
                        *elapsed = elapsedTime;
                        printf("\nJob '%s' processed at %i!\n", datatype->jobID,curTime);
                        printf("Elapsed time in queue = %i\n\n", elapsedTime);
                        return TRUE;
                  }
                  else
                        printf("Unable to process job '%s' - queue empty!\n", datatype->jobID);
                        return FALSE;
      }



Avatar of John500
John500
Flag of United States of America image

ASKER

Edited text of question.
Avatar of nietod
nietod

>>  I made it in time.
Good.

I'm gone from Mar 6th to the 13th.  You're on your own then.  (Well there are other experts...)
ASKER CERTIFIED SOLUTION
Avatar of nietod
nietod

Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
Avatar of John500

ASKER

Todd,

You didn't give me the option to grade...

John