Velocity Reviews > Explanation

# Explanation

Alessandro Zucchini
Guest
Posts: n/a

 07-22-2004
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
Guest
Posts: n/a

 07-22-2004
"Alessandro Zucchini" <(E-Mail Removed)> 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
Guest
Posts: n/a

 07-23-2004
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