Thread: MinPriority Queue and structures, assistance needed :)

  1. #1
    Registered User
    Join Date
    Sep 2007
    Posts
    15

    MinPriority Queue and structures, assistance needed :)

    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
    Code:
     -DPQEntry=Customer
    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!
    Last edited by trancekid; 10-29-2007 at 09:21 AM.

  2. #2
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    When you use "-DPQEntry=Customer", then, ALL places where the original source code says "PQEntry" will become "Customer".

    If Customer is a struct, then:
    Code:
    Boolean less(PQEntry a, PQEntry b) {
        return PQEntry[a]->arrival_time < PQEntry[b]->arrival_time;
    }
    is definitely incorrect.

    You probably want something like:
    Code:
    Boolean less(PQEntry a, PQEntry b) {
        return a.arrival_time < b.arrival_time;
    }
    [What is "mcs360.h" - sounds like a Motorola Quicc "360" microcontroler, but I fail to understsand what this would have to do with a queue implementation].

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  3. #3
    Registered User
    Join Date
    Sep 2007
    Posts
    15
    haha mcs360 is the course. MCS = Math and Computer Science, the course is just an introduction to data structures. The prof gave us MCS360.c/.h which includes a version of checked_malloc/realloc etc so we do not have to check if anything is NULL or if there is no more memory available.

    Thank you for the explanation, that is an obvious mistake on my behalf, this program is driving me nuts since I have spent so much time and have near nothing done =P.

    Any idea how I would initialize the queue though? Rather, why do I need two customers in the bank to setup the queue... it just doesn't make sense. The queue examples in our book are quite simple,

    Code:
    CreateQueue(*queuePointer);
    From the code I don't see how a queue can be created unless two customers enter the bank instantly, but that doesn't work for most of the strategies we have to code, example in one case we have N number of tellers and each teller has their own queue so unless >N customers enter the moment the bank "opens" where would a second PQEntry come from?
    Last edited by trancekid; 10-29-2007 at 09:37 AM.

  4. #4
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Not sure what you mean: Are you referring to this:
    Code:
    MinPriorityQueue *CreateMinPriorityQueue( Boolean (*less)(PQEntry,PQEntry))
    ??

    If so, that doesn't take two customers as a parameter. It takes a function "less" that takes two custoemrs as parameters.

    If you have no or one customer in the queue, obviously, there is no need to compare for "less" in the queu - there is no "choices" to be made from this.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  5. #5
    Registered User
    Join Date
    Sep 2007
    Posts
    15
    anyone know what the gcc command is to declare the typedef of PQEntry on the command line? I am currently typing:

    gcc -DPQEntry=customer bank.c MinPriorityQueue.c mcs360.c -Wall -o bank

    but it is giving me a massive amount of errors. Is there something special you must type to declare PQEntry = struct customer?

  6. #6
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    As well as doing -DPQEntry=customer, you also need to figure a way of getting the actual typedef of that structure into scope as well.

    Otherwise the compiler will simply complain when it expands say
    Boolean less(PQEntry a, PQEntry b)
    to
    Boolean less(customer a, customer b)

    If this really is meant to be a generic minpriority queue module, then the only thing you're allowed to use would be instances of PQEntry *
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  7. #7
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by trancekid View Post
    anyone know what the gcc command is to declare the typedef of PQEntry on the command line? I am currently typing:

    gcc -DPQEntry=customer bank.c MinPriorityQueue.c mcs360.c -Wall -o bank

    but it is giving me a massive amount of errors. Is there something special you must type to declare PQEntry = struct customer?
    If that's what you want to do, the -DPQEntry="struct customer" should do it. [I'm 95% sure that's right - it may not work due to the quotes being included in the actual define, but I'm fairly sure they are stripped]

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Game programming task
    By VirtualAce in forum Game Programming
    Replies: 8
    Last Post: 01-06-2006, 12:10 AM
  2. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM
  3. Data Structures part2
    By sonicsite in forum C Programming
    Replies: 7
    Last Post: 03-01-2002, 03:34 PM
  4. Data Structures
    By sonicsite in forum C Programming
    Replies: 3
    Last Post: 02-28-2002, 09:56 PM