Computer Science 2530
Spring 2017
Programming Assignment 5

1. Items and Priorities: Types PQItemType and PQPriorityType

It is not clear right now what types of items or priorities an application will need. For example, should the priorities by integers or real numbers or something else? Should the items be strings or widgets or something else?

To handle that, you will define two types, PQItemType and PQPriorityType. Start with default definitions of them. But it must be possible to change what those types are by changing only one line for each type.

Here are default definitions that you are required to use for this assignment. Put

  typedef const char* PQItemType;
  typedef double      PQPriorityType;

Write the entire implementation of priority queues using PQItemType for the type of an item and PQPriorityType for the type of a priority. Do not assume that PQItemType will be const char* or that PQPriorityType will be double.

2. Representing Priority Queues: Types PriorityQueue and PQCell

You are required to store the information in a priority queue using a linked list, kept in nondecreasing order by priority. You will need the following types. Provide documentation for each type.

1. Define a structure type, PQCell, that is used as a cell in a linked list. It holds an item, a priority, and a pointer to the next cell in the list. Write the definition of PQCell in pqueue.cpp. Document type PQCell.

   In pqueue.h, just write

     struct PQCell;
   

   to allow your definition of PriorityQueue to use type PQCell*.

2. Define a structure type, PriorityQueue, that holds a pointer to a linked list made of PQCells. This pointer must be initially set to NULL by a parameterless constructor in the definition of PriorityQueue.

   Write the definition of type PriorityQueue in pqueue.h so that it can be used in other modules. Document type PriorityQueue.

3. Testing Whether a Priority Queue Is Empty

Document and define function isEmpty with the following heading.

  bool isEmpty(const PriorityQueue& q);

Put a prototype for isEmpty into pqueue.h. (A prototype is just the function heading followed by a semicolon.)

4. Insertion into a Priority Queue

Document and define function insert(q, item, pri) with the following heading.

  void insert(PriorityQueue& q, PQItemType item, PQPriorityType pri);

Put a prototype for this function into pqueue.h. The prototype is just the function's heading followed by a semicolon. By putting this prototype in pqueue.h, you are saying that other modules should be allowed to use it.

Put the definition of insert into pqueue.cpp. You will find it convenient to write a helper function

  void insertCell( PQCell*& p, const PQItemType& item, PQPriorityType pri)

Do not put a prototype for insertCell in pqueue.h since insertCell is not being exported; it is only to be used in pqueue.cpp.

5. Removing an Item

Document and define function remove with the following heading.

  void remove(PriorityQueue& q, PQItemType& item, PQPriorityType& pri);

Put a prototype for remove into pqueue.h.

Be sure to delete the list cell that is removed.

6. Debugging: Printing the Priority Queue

For this part, write a function for debugging that prints the content of the priority queue.

But there is an issue here. Remember that types PQItemType and PQPriorityType can be changed. You cannot assume that PQItemType is const char* or that PQPriorityType is double. But then how do you know how to print the items and priorities?

A solution is to require the module that uses priority queues to say how to print items and priorities by providing two functions, one for printing an item and another for printing a priority. C++ allows you to pass a function as a parameter of a function.

Add the following type definitions to pqueue.h.

  typedef void (ItemPrinter)(PQItemType);
  typedef void (PriorityPrinter)(PQPriorityType);

Document and define a function printPriorityQueue with the following heading.

  void printPriorityQueue(const PriorityQueue& q, ItemPrinter pi, PriorityPrinter pp);

  pi(x);

  pp(y);

PrintPriorityQueue should assume that pi and pp do not write any spaces or newlines. PrintPriorityQueue should print those. It is not acceptable to write out the entire priority queue on one line.

Function printPriorityQueue is only intended to be used for debugging. Put a prototype for printPriorityQueue into pqueue.h so that another module can use PrintPriorityQueue for debugging.

Another module can print a priority queue by defining functions for printing items and priorities. For example, If PQItemType and PQPriorityType have the default definitions, then the following would be suitable.

  typedef const char* CSTRING;

  void printString(const char* s)
  {
    printf("%s", s);
  }

  void printDouble(double x)
  {
    printf("%lf", x);
  }

  printPriorityQueue(q, printString, printDouble);

7. Summary of the priority queue interface

A module that uses priority queues can do the following, and nothing more.

• It can create a variable of type PriorityQueue, as follows.

    PriorityQueue q;
  

  (Of course, you can call the priority queue whatever you like.) The priority queue is initially empty.

• It can use the following functions.

    bool isEmpty(const PriorityQueue& q);
    void inser(PriorityQueue& q, PQItemType item, PQPriorityType pri);
    void remove(PriorityQueue& q, PQItemType& item, PQPriorityType& pri);
  

• Strictly for debugging, it can use

    void printPriorityQueue(const PriorityQueue& q, ItemPrinter pi, PriorityPrinter pp);