Explanation

[Alessandro Zucchini]

does someone can understand this function?can you explain me what do they do
one by one?thankyou

PQUEUE *pqueue_new(void)
{
PQUEUE *pq;

if ((pq = (PQUEUE *) my_malloc(sizeof(PQUEUE))) == NULL)
return (NULL);
pq->count = 0;
pq->priorities = NULL;
return pq;
}

int pqueue_insert(PQUEUE * pq, COORD coord, int wt)
{
ELIST *e;
PLIST *p, *pp;

if (pq == NULL)
return -1;

if ((e = (ELIST *) my_malloc(sizeof(ELIST))) == NULL)
return -1;
e->coord = coord;
e->next = NULL;
if (pq->priorities == NULL || pq->priorities->wt > wt) {

if ((p = (PLIST *) my_malloc(sizeof(PLIST))) == NULL)
return -1;

p->wt = wt;
p->elements = e;
p->next = pq->priorities;
pq->priorities = p;
pq->count++;

return 0;
}
pq->count++;

for (p = pq->priorities; p->next && p->next->wt <= wt; p = p->next);

if (p->wt == wt) {
e->next = p->elements;
p->elements = e;
return 0;
}
if ((pp = (PLIST *) my_malloc(sizeof(PLIST))) == NULL)
return -1;

pp->wt = wt;
pp->elements = e;
pp->next = p->next;
p->next = pp;
pq->count++;

return 0;
}

int pqueue_peekmin(PQUEUE * pq, PCOORD coord)
{
if (pq == NULL || pq->priorities == NULL || pq->priorities->elements ==
NULL)
return -1;

*coord = pq->priorities->elements->coord;

return 0;
}

int pqueue_popmin(PQUEUE * pq, PCOORD coord)
{
ELIST *tmpe;
PLIST *tmpp;

if (pqueue_peekmin(pq, coord) < 0)
return -1;

pq->count--;

tmpe = pq->priorities->elements;
pq->priorities->elements = pq->priorities->elements->next;
my_free(tmpe, sizeof(ELIST));

if (pq->priorities->elements == NULL) {
tmpp = pq->priorities;
pq->priorities = pq->priorities->next;
my_free(tmpp, sizeof(PLIST));
}
return 0;
}

[Richard Bos]

"Alessandro Zucchini" <a.********@treamail.biz> wrote:

does someone can understand this function?can you explain me what do they do
one by one?thankyou

Well, a couple of type definitions wouldn't have gone amiss, but it
looks like code for handling a priority queue. You can call pqueue_new()
to create a new, empty queue; pqueue_insert() to insert a new item with
priority wt and payload coord into a queue; and pqueue_peekmin() and
pqueue_popmin() to look at, resp. pop, the first element with maximum
priority off the queue.
Note that:
- if the queue can get large, a tree may be a better implementation than
a list;
- this higher-level interface makes it possible to switch to a tree
implementation without many changes, if any at all, to the user code,
should it become necessary, and is thus a Good Thing;
- pqueue_peekmin() and pqueue_popmin() seem misnamed to me, since they
refer to the element with the _maximum_, not minimum, priority;
- should I comment on the wisdom of casting malloc(), or writing a
malloc() wrapper which does not return a void *? Thought not.

Richard

[Karthik]

Alessandro Zucchini wrote:

does someone can understand this function?can you explain me what do they do
one by one?thankyou

PQUEUE *pqueue_new(void)
{
PQUEUE *pq;

if ((pq = (PQUEUE *) my_malloc(sizeof(PQUEUE))) == NULL)
return (NULL);
pq->count = 0;
pq->priorities = NULL;
return pq;
}

int pqueue_insert(PQUEUE * pq, COORD coord, int wt)
{
ELIST *e;
PLIST *p, *pp;

if (pq == NULL)
return -1;

if ((e = (ELIST *) my_malloc(sizeof(ELIST))) == NULL)
return -1;
e->coord = coord;
e->next = NULL;
if (pq->priorities == NULL || pq->priorities->wt > wt) {

if ((p = (PLIST *) my_malloc(sizeof(PLIST))) == NULL)
return -1;

p->wt = wt;
p->elements = e;
p->next = pq->priorities;
pq->priorities = p;
pq->count++;

return 0;
}
pq->count++;

for (p = pq->priorities; p->next && p->next->wt <= wt; p = p->next);

if (p->wt == wt) {
e->next = p->elements;
p->elements = e;
return 0;
}
if ((pp = (PLIST *) my_malloc(sizeof(PLIST))) == NULL)
return -1;

pp->wt = wt;
pp->elements = e;
pp->next = p->next;
p->next = pp;
pq->count++;

return 0;
}

int pqueue_peekmin(PQUEUE * pq, PCOORD coord)
{
if (pq == NULL || pq->priorities == NULL || pq->priorities->elements ==
NULL)
return -1;

*coord = pq->priorities->elements->coord;

return 0;
}

int pqueue_popmin(PQUEUE * pq, PCOORD coord)
{
ELIST *tmpe;
PLIST *tmpp;

if (pqueue_peekmin(pq, coord) < 0)
return -1;

pq->count--;

tmpe = pq->priorities->elements;
pq->priorities->elements = pq->priorities->elements->next;
my_free(tmpe, sizeof(ELIST));

if (pq->priorities->elements == NULL) {
tmpp = pq->priorities;
pq->priorities = pq->priorities->next;
my_free(tmpp, sizeof(PLIST));
}
return 0;
}

I would suggest to get a good book on data structures and look out
for priority queues and what they mean. And then of course, about lists
( singly linked lists). Then come back to this code. It would be much
simple to understand this then.
--
Karthik