I am in a C programming class and our current assignment is to write a program that will simulate the number of customers entering the bank and how long each takes to be served based on a Poisson distribution, while keeping track of certain information. I have a good idea of how I plan to implement this, but I seem to be really hung on the queue.h and queue.c we are supposed to use to implement queues in the program. If someone could tell me what I am doing wrong it would be appreciated.
I made the following structure that will hold some information for the customers.
Code:
typedef struct customer {
int id;
double arrival_time;
double service_time;
double finish_time;
} Customer;
so that should be fine, but then when I try to implement the Queue I am at a loss. Below is the header file and .c file for the Minimum Priority Queue.
Queue.h
Code:
#ifndef MINPRIORITYQUEUE_DEFINED
#define MINPRIORITYQUEUE_DEFINED
/* File MinPriorityQueue.h. Header file for a MinPriorityQueue
containing elements of type PQEntry. PQEntry must be defined
on the command line when any source file including MinPriorityQueue.h
is compiled, e.g.,
gcc -Wall -DPQEntry=Event MinPriorityQueue.c
where Event is a structure type.
In a MinPriorityQueue, a remove operations always removes the
"smallest element". Since the elements may be of structure or
pointer type, we cannot decide which element is smallest by
comparing elements using <. The program using a MinPriorityQueue
must supply a function
Boolean f( PQEntry a, PQEntry b);
that returns true if a should be treated as less than b. A
pointer to this function is then passed to the function
CreateMinPriorityQueue that creates the MinPriorityQueue.
*/
#ifndef PQEntry
#error Error: PQEntry not defined in the compile command.
#endif
#include "mcs360.h"
typedef struct MinPriorityQueue MinPriorityQueue;
/* createMinPriorityQueue(less) creates a new MinPriorityQueue,
initializes it to empty, and returns a pointer to it. The argument
less is a pointer to a function that tells us when one element of
type PQEntry is treated as less than another; a is treated as less
that b is less(a,b) is true. */
MinPriorityQueue *CreateMinPriorityQueue( Boolean (*less)(PQEntry,PQEntry));
/* DestroyMinPriorityQueue(pq) frees the dynamic memory used by
MinPriorityQueue pq. */
void DestroyMinPriorityQueue( MinPriorityQueue *pq);
/* add(item,pq) adds item to MinPriorityQueue pq. */
void add( PQEntry item, MinPriorityQueue *pq);
/* removeMin(pq) removes a "smallest" element on MinPriorityQueue pq,
and returns it. Here a "smallest" element on pq is an element x such
that less(y,x) is false for all y on pq. */
PQEntry removeMin( MinPriorityQueue *pq);
/* min(pq) returns a "smallest" element (as defined above) on
MinPriorityQueue pq, without removing it from pq. */
PQEntry min( const MinPriorityQueue *pq);
/* empty(pq) returns true if MinPriorityQueue pq is empty.*/
Boolean empty( const MinPriorityQueue *pq);
/* size(pq) returns the number of elements in the MinPriorityQueue pq. */
int size( const MinPriorityQueue *pq);
#endif
Queue.c
Code:
/* File MinPriorityQueue.c. */
#include "mcs360.h"
#include "MinPriorityQueue.h"
struct MinPriorityQueue {
int size; /* Current size of MinPriorityQueue. */
int capacity; /* Allocated size of dynamic array. */
PQEntry *entry; /* Dynamic array for MinPriorityQueue entries. */
Boolean (*less)(PQEntry a, /* Pointer to function returning true if first */
PQEntry b); /* argument is treated as less than the second. */
};
#define INITIAL_CAPACITY 16
MinPriorityQueue *CreateMinPriorityQueue( Boolean (*less)(PQEntry,PQEntry))
{
MinPriorityQueue *newPQ = (MinPriorityQueue *)checked_malloc(sizeof(MinPriorityQueue));
newPQ->size = 0;
newPQ->capacity = INITIAL_CAPACITY;
newPQ->entry = (PQEntry *)checked_malloc( newPQ->capacity * sizeof(PQEntry));
newPQ->less = less;
return newPQ;
}
void DestroyMinPriorityQueue( MinPriorityQueue *pq)
{
free( pq->entry);
free(pq);
}
void add( PQEntry item, MinPriorityQueue *pq)
{
int n;
if (pq->size == pq->capacity ) {
pq->entry = (PQEntry *)checked_realloc( pq->entry, 2*pq->capacity);
pq->capacity *= 2;
}
++pq->size;
n = pq->size - 1;
pq->entry[n] = item;
while ( n > 0 && pq->less( pq->entry[n], pq->entry[(n-1)/2]) ) {
PQEntry temp = pq->entry[n];
pq->entry[n] = pq->entry[(n-1)/2];
pq->entry[(n-1)/2] = temp;
n = (n-1) / 2;
}
}
PQEntry removeMin( MinPriorityQueue *pq)
{
int i, smallest;
PQEntry minEntry = pq->entry[0];
pq->entry[0] = pq->entry[--pq->size];
i = 0;
while ( 2*i+1 <= pq->size - 1 ) {
smallest = i;
if ( pq->less( pq->entry[2*i+1], pq->entry[i]) )
smallest = 2*i+1;
if ( 2*i+2 <= pq->size-1 && less( pq->entry[2*i+2], pq->entry[smallest]) )
smallest = 2*i+2;
if ( smallest != i ) {
PQEntry temp = pq->entry[i];
pq->entry[i] = pq->entry[smallest];
pq->entry[smallest] = temp;
i = smallest;
}
else
i = pq->size;
}
return minEntry;
}
PQEntry min( const MinPriorityQueue *pq)
{
return pq->entry[0];
}
Boolean empty( const MinPriorityQueue *pq)
{
return pq->size == 0;
}
int size( const MinPriorityQueue *pq)
{
return pq->size;
}
the part I do not understand is in the structure for a queue. I compile using gcc so I was trying to use
assuming this means for each entry in the Queue there will be a nested structure for that customer containing all the information I need for that customer... But I can't get this to work. Am I thinking about it all wrong, is this not what PQEntry should be used for?
Also I am having a difficult time understanding
Code:
Boolean f( PQEntry a, PQEntry b);
The way I am seeing it, PQEntry will be set to the customer data struct, so I thought that if I wrote the following for the less function it would be able to check and verify that a arrived before b which returns true that a.
Code:
Boolean less(PQEntry a, PQEntry b) {
return PQEntry[a]->arrival_time < PQEntry[b]->arrival_time;
}
CreateMinPriorityQueue(less(customer1, customer2)); //but why would I have two customers when I am just initializing a queue?
But alas, it does not. I get all sorts of errors when I try to write this and I spent all weekend trying to figure this out. Plus, I do not understand how
Code:
MinPriorityQueue *CreateMinPriorityQueue( Boolean (*less)(PQEntry,PQEntry))
is supposed to work if I am just trying to initialize a single queue with the first customer that enters the bank, there will only be one entry in the queue to start with so what in the world would I be using as PQEntry a, PQEntry b?
I assume I am doing this all wrong since it is making no sense to me, so if someone could point me in the right direction it would be much appreciated.
This is a University project, but it is a very small part of the program (considering) and I just need to get it to work before I can actually write the real code. Or I at least need to understand it. The book we use has no mention of priority queues so it is of no assistance.
Thank you for any help!