Explanation

Discussion in 'C Programming' started by Alessandro Zucchini, Jul 22, 2004.

  1. 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;
    }
     
    Alessandro Zucchini, Jul 22, 2004
    #1
    1. Advertising

  2. Alessandro Zucchini

    Richard Bos Guest

    "Alessandro Zucchini" <> 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
     
    Richard Bos, Jul 22, 2004
    #2
    1. Advertising

  3. Alessandro Zucchini

    Karthik Guest

    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
     
    Karthik, Jul 23, 2004
    #3
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Mariusz

    explanation

    Mariusz, Jan 12, 2004, in forum: VHDL
    Replies:
    1
    Views:
    598
    tbx135
    Jan 13, 2004
  2. Kaladhaur Palaniappa

    Need Explanation

    Kaladhaur Palaniappa, Aug 7, 2003, in forum: Perl
    Replies:
    0
    Views:
    1,010
    Kaladhaur Palaniappa
    Aug 7, 2003
  3. Benjie Fallar

    tracing output explanation

    Benjie Fallar, Jul 15, 2003, in forum: ASP .Net
    Replies:
    0
    Views:
    361
    Benjie Fallar
    Jul 15, 2003
  4. George Ter-Saakov

    Do you have an explanation for this?

    George Ter-Saakov, Apr 29, 2004, in forum: ASP .Net
    Replies:
    1
    Views:
    592
    Pravin A. Sable
    Apr 30, 2004
  5. Dave
    Replies:
    4
    Views:
    398
Loading...

Share This Page