Implement the following into minprio.c : #ifndef minprio_H #define minprio_H /*
ID: 3818926 • Letter: I
Question
Implement the following into minprio.c :
#ifndef minprio_H
#define minprio_H
/* min-priority queues
* Items in a given queue are struct pointers that should be
* comparable by the comparator provided to makeQueue.
*
* This API provides "addressable" queue, meaning that the client
* is given a handle for each enqueued item. This enables an
* efficient interface for the decrease-key operation. (The handle
* enables the decreaseKey to find, in constant time, an item's
* index in the array.)
*
*/
/* the queue type */
struct minprio; /* to be defined by the implementation */
typedef struct minprio* MinPrio;
/* handles for efficient access to enqueued items
* ALERT: Clients must not read or write the pos field; it's for use only
* by code in minprio.c.
*/
struct handle {
int pos; /* not for client use (current position in queue array) */
void* content; /* the client's data */
};
typedef struct handle* Handle;
/* type and contract for comparison function
* Assumes lhs and rhs non-null.
* Returns <0, =0, >0 according to whether lhs<rhs, lhs==rhs, lhs>rhs */
typedef int (*Comparator)(void* lhs, void* rhs);
/* make an empty queue
* Items will be compared using comp.
*
* It' the client's responsibility to ensure that
* there are never more than maxsize elements in queue.
*/
MinPrio makeQueue(Comparator comp, int maxsize);
/* dispose of memory owned by the queue
* Namely: the queue object, the array, and the Handles.
* The Handle contents are the responsibility of the client.
*/
void disposeQueue(MinPrio qp);
/* enqueue
* Assumes queue currently contains less than maxsize elements.
* Assumes qp and item non-null.
* Returns a Handle containing the item, for use with decreaseKey.
*/
Handle enqueue(MinPrio qp, void* item);
/* 1 if queue has elements, else 0 (assuming qp non-null) */
int nonempty(MinPrio qp);
/* dequeue and return a minimum element according to the comparator.
* Assumes qp non-null and queue nonempty.
* Frees the handle, so client should no longer use handle.
*/
void* dequeueMin(MinPrio qp);
/* decrease the item's key
* Must be called whenever comparison value may have changed.
* Must only decrease comparison value (i.e. raise priority).
*
* Assumes qp non-null and hand is in the queue.
*/
void decreasedKey(MinPrio qp, Handle hand);
#endif
Explanation / Answer
struct QNode
{
int key;
void* content;
struct QNode *next;
};
struct MinPrio
{
struct QNode *front, *rear;
};
MinPrio makeQueue(Comparator comp, int maxsize)
{
MinPrio q = (MinPrio)malloc(maxSize);
q->front = q->rear = NULL;
return q;
}
struct QNode* newNode(void* k)
{
struct QNode *temp = (struct QNode*)malloc(sizeof(struct QNode));
temp->key = k;
temp->next = NULL;
return temp;
}
Handle enqueue(MinPrio qp, void* item)
{
struct QNode *temp = newNode(item);
if (q->rear == NULL)
{
q->front = q->rear = temp;
return;
}
else{
//Check Priority Using Comparator, and enqueue node accordingly.
while(qp->next!=null)
{
void *temp_content=qp->content;
int x=check(temp_content,item);
if(x==1)
{
q->rear->next = temp;
q->rear = temp;
}
if(x==-1)
{
//move to next. Not to be added here
qp->next=qp->next->next;
}
if(x==0)
{
//print Same Content
}
}
}
}
void disposeQueue(MinPrio queue)
{
void *next;
for(QNode *ite = queue->front; ite != NULL; ite = next){
next = ite->next;
free(ite);
free(queue);
}
struct QNode *deQueue(MinPrio q)
{
if (q->front == NULL)
return NULL;
struct QNode *temp = q->front;
q->front = q->front->next;
if (q->front == NULL)
q->rear = NULL;
return temp;
}
int nonempty(MinPrio qp)
{
if(deQueue(qp)!=NULL)
return 1;
else return 0;
}
typedef int check (*Comparator)(void* lhs, void* rhs)
{
//implementing Comparator based on priorities defined
if(lhs>rhs)
return 1;
else if(lhs<rhs)
return -1;
else return 0;
}