Computer Science 3300
Fall 2015
Section 001
Programming Assignment 5

Table of contents

1. Priority queues
2. The assignment
3. Testing your implementation
4. Submitting your work

Priority Queues

---

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.

A priority queue is an abstract data type. An instance of a priority queue holds a collection items, each with a priority. 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.

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.

The assignment

---

Create a directory for assignment 5 and files pqueue.cpp and pqueue.h. Start each using the standard template.

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. Use the headings shown for them.

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

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

3. void remove(PriorityQueue& q,  PQItemType& x,  PQPriorityType& p): 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.

   Note that parameters pi and pp refer to functions. The functions that are passed to printPriorityQueue are not called pi and pp. Those names are just formal parameters, the name by which printPriorityQueue refers to the functions that are passed to it. Do not define functions called pi and pp in pqueue.cpp.

Nonfunctional requirements

Keep functions short and simple.

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

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

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

A Makefile is provided for you. If your tester is called testpq.cpp, you can use the following commands with it.

make testpq

Just compile pqueue.cpp and testpq.cpp, if necessary, and link them to create executable file testpq.

make pqueue.o

Just compile pqueue.cpp, if necessary.

make test

Do make testpq then run the tester.

make debug

Do make testpq then run the tester via the gdb debugger.

make clean

Remove all machine-generated files.

Submitting your work

---

To turn in your work, log into the Linux system, change your directory for the one for assignment 5, use the following command.

  ~abrahamsonk/3300/bin/submit 5 pqueue.cpp pqueue.h testpq.cpp

Command

  ~abrahamsonk/3300/bin/submit 5

You can do repeated submissions. New submissions will replace old ones.

Late submissions

Late submissions will be accepted for one day after the due date. If you miss a late submission deadline by a microsecond, your work will not be accepted.