Computer Science 3300
Spring 2016
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 only by changing 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 increasing 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.

   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.

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.

4. Insertion into a Priority Queue

Document and define function insert(item, pri, q) that inserts item item with priority pri into PriorityQueue object q.

Put a prototype for this function into pqueue.h. The prototype is just the function's heading followed by a semicolon. For example,

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

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

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

Do not put a prototype for insertCell in pqueue.h. It is only to be used in pqueue.cpp.

5. Removing an Item

Document and define function remove with the following heading.

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

Put a prototype for remove into pqueue.h.

Be sure to delete the list cell that is removed.

6. Debugging: Printing the Priority Queue

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);

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

Recall that you do not know what types PQItemType and PQPriorityType will be. For now, they have defaults, but those can change. You want to define pqueue.cpp so that it will continue to work, without any modification, when the definitions of PQItemType and PQPriorityType are changed.

To handle that, printPriorityQueue needs to be told how to print an item and how to print a priority. It uses pi to print an item and pp to print a priority. In the body of printPriorityQueue, write statement

  pi(x);

  pp(y);

PrintPriorityQueue should assume that pi and pp do not write any spaces or newlines. PrintPriorityQueue should print those.

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.

  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 insert(PQItemType item, PQPriorityType pri, PriorityQueue& q);
    void remove(PQItemType& item, PQPriorityType& pri, PriorityQueue& q);
  

• Strictly for debugging, it can use

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