John500
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;
}
/* -------------------------I nsertJob -------------------------- ------
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.insertTi me);
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;
}
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;
}
/* --------------------------
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;
}
/* -------------------------I
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.insertTi
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;
}
>> 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...)
Good.
I'm gone from Mar 6th to the 13th. You're on your own then. (Well there are other experts...)
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
ASKER
Todd,
You didn't give me the option to grade...
John
You didn't give me the option to grade...
John
ASKER