Computer Science 3300
Spring 2015
Section 001
Programming Assignment 4

Table of contents

1. Priority queues
2. Testing your implementation
3. Submitting your work
4. Late submissions

Priority Queues

Priority queues

A priority queue is an abstract data type. An instance of a priority queue holds a collection items, with a priority associated with each item. You can insert an item, with a given priority into the collection and you can remove the item with the smallest priority from the collection.

The assignment

For this assignment, you will not write an application, but just a module that can be used in other applications. Create a module called pqueue.cpp that implements priority queues, with a header file called pqueue.h that describes what pqueue.cpp exports.

Generalizing priority queues

The items in a priority queue could be of any type, and the priorities could have any numeric type. For example, an item could be a Widget (whatever that is) and the priority could be an integer.

We do not want to commit to particular types for the items and priorities in more than one place. Put type definitions

  typedef const char* PQItemType;
  typedef double      PQPriorityType;
  typedef void (ItemPrinter)(const PQItemType&);
  typedef void (PriorityPrinter)(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. You will want to be able to change the above type definitions later.

What to define

Provide a type PriorityQueue and the following functions.

1. bool isEmpty(const PriorityQueue& q): return true if q is empty.

2. void insert(const PQItemType& x, PQPriorityType, PriorityQueue& q): Insert item x with priority p into q.

3. void remove(PQItemType& x, PQPriorityType& p, PriorityQueue& q): Remove the item from q that has the smallest priority. Store the removed item into variable x and store its priority into variable p.

4. void printPriorityQueue(const PriorityQueue& q, ItemPrinter pi, PriorityPrinter pp): Print the contents of q, in order from lowest priority to highest priority, to the standard output. Use pi(x) to show item x and pp(y) to show priority y. Write the priority first, then a tab, then the item, then a newline character.

Representing priority queues

Store the information in a priority queue using a linked list, kept in increasing order by priority. You will need the following types.

1. 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.

2. 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.

Define type PriorityQueue in pqueue.h so that it can be used by any other module that includes pqueue.h. Other modules do not need to know about type PQCell, and must not use it. But the definition of type PriorityQueue needs to use PQCell, so you need to tell the compiler that PQCell exists. In pqueue.h, just write

  struct PQCell;

Put implementations of the priority queue functions in pqueue.cpp. You will find it easiest to implement insert if you provide a helper function

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

Provide a prototype in pqueue.h for each of the functions for priority queues that other modules are expected to use. Do not put a definition of insertCell, since other modules are not supposed to use it directly.

Nonfunctional requirements

Keep functions short and simple.

As always, you must follow the coding standards for this course, which include the following.

• The program must use the correct file format and file name. Use template template as a starting point.
• Every function is required to have a clear, concise and precise contract telling what the function accomplishes and returns and how each of its parameters influences what it accomplishes and what it returns. The contract must not be concerned with how the function works.
• A function body must not change the value of a call-by-value parameter.
• Do not use global or static variables.
• Every body of an if-statement, loop, etc. must be a compound statement.

Testing Your Implementation

You will need to write a test module that uses priority queues and demonstrates that your implementation is working, at least for the test cases. Call your tester testpq.cpp.

Ensure that your tester tests every function. Try creating more than one priority queue. (You will need to use the same types of items and priorities for both.)

Testing is critical. Do not turn in an untested module.

Submitting Your Work

To turn in this program, log into one of the Linux computers in the lab. (You can log in remotely.) Ensure that your files are there. Change to the directory that contains those files. Then issue one of the following commands.

First version

~abrahamsonk/3300/bin/submit 4a pqueue.cpp pqueue.h testpq.cpp

Second version

~abrahamsonk/3300/bin/submit 4b pqueue.cpp pqueue.h testpq.cpp

Late submissions

Late submissions on version (a) will be accepted for one day after the due date. Late submissions for version (b) will be accepted for three days after the due date. If you miss a late submission deadline by a microsecond, your work will not be accepted.