Computer Science 2530
Spring 2020
Programming Assignment 6

Table of Contents

1. Purpose of this assignment
2. What you will submit
3. Background
4. The assignment
5. Getting started
6. A refinement plan
7. Compiling and testing on xlogin
8. Issues to be aware of
9. Submitting your work
10. Late submissions
11. Asking questions

Purpose of This Assignment

---

This assignment has you write a module, not an application, as you did for assignment 4. It gives you experience implementing an abstract data type using linked lists.

Initially, this might look like a difficult assignment. It isn't. Keep it simple. Read the entire assignment before you start to work on it.

Follow the design. Do not rename the functions or reorder the parameters.

You will need to define two structure types and five functions.

What You Will Submit

---

You will need to submit two files, pqueue.cpp and pqueue.h.

Background

---

A priority queue is a collection of items each having a priority. A priority queue supports three fundamental operations.

1. You can ask a priority queue whether it is empty.

2. You can insert an item into the priority queue with a given priority.

3. You can remove the item from the priority queue that has the smallest priority.

For example, suppose that you start with an empty priority queue and imagine performing the following steps.

1. Insert item "one" with priority 10.
2. Insert item "two" with priority 5.
3. Insert item "three" with priority 15.
4. Remove the item with the smallest priority and call it x.
5. Remove the item with the smallest priority and call it y.

You should find that x is "two" and y is "one".

The Assignment

---

For this assignment, you will not write an application, but a module that can be used as part of a larger application, as you did for assignment 4. File pqueue.cpp must contain function implementations and file pqueue.h must describe what pqueue.cpp exports.

Types ItemT and PriorityT

Initially, you will assume that items in the priority queue have type const char* and priorities have type double. But it must be possible to change the item type without changing more than one line, and similarly to change the priority type without changing more than one line.

  typedef const char* ItemT;
  typedef double PriorityT;

The remainder of pqueue.h and pqueue.cpp must not presume that ItemT is const char* or that PriorityT is double. It must use types ItemT and PriorityT.

The interface

The module interface includes the following.

PriorityQueue

Declaration

  PriorityQueue q;

must create a new priority queue q that is initially empty.

bool isEmpty(const PriorityQueue& q)

isEmpty(q) returns true if q is empty and returns false if q is not empty.

void insert(PriorityQueue& q, ItemT i, PriorityT p)

insert(q, i, p) inserts item i, with priority p, into q.

void remove(PriorityQueue& q, ItemT& i, PriorityT& p)

If q is not empty, then remove(q, i, p) removes the item from q that has the smallest priority. Parameters i and p are out-parameters. Remove stores the removed item into variable i and stores the removed item's priority into variable p.

If q is empty, then remove(q, i, p) must print "Attempt to remove from an empty priority queue" on the standard output and abort the program.

Showing the contents of a priority queue

For debugging, you will write a function ShowPriorityQueue that shows the contents of a priority queue.

But when you try to define ShowPriorityQueue, you encounter a problem. Since pqueue.cpp does not know what the definitions of ItemT or PriorityT are, it does not know how to print an item or a priority. If ShowPriorityQueue tries to show a priority under the assumption that PriorityT is double, then it will not work when PriorityT is changed to be int.

When a function does not possess information that it needs, the usual fix is to add a parameter that tells the function the needed information.

That is what we will do here. ShowPriorityQueue asks its caller to tell it how to print an item and how to print a priority. The caller will pass two functions to ShowPriorityQueue, one to print an item and one to print a priority.

Every parameter must have a type, including parameters that are functions. Here are type definitions of types ItemPrinterT and PriorityPrinterT, where a value of type ItemPrinterT is a function that prints an item and a value of type PriorityPrinterT is a function that prints a priority.

  typedef void (*ItemPrinterT)(ItemT item);
  typedef void (*PriorityPrinterT)(PriorityT priority);

void ShowPriorityQueue(const PriorityQueue& q, ItemPrinterT printItem, PriorityPrinterT printPriority)

Print the current contents of q. Use printItem(i) to print item i and use printPriority(p) to print priority p.

Neither printItem nor printPriority should write any extra space or line ends. ShowPriorityQueue takes care of formatting the output.

Additional type and function

Pqueue.cpp will define one additional type and one additional function.

PQCell

This module represents the contents of a priority queue as a linked list, in nondescending order by priority. Type PQCell is the list cell type.

An object of type PQCell contains an item, a priority and a pointer to the next cell in the linked list.

void insertCell(PQCell*& L, ItemT item, PriorityT priority)

InsertCell(L, i, p) inserts a cell with item i and priority p into linked list L. It assumes that L is in nondescending order by priority, and it inserts the new cell in a place so that L is still in nondescending order by priority.

Getting Started

---

Start by creating a directory to hold assignment 6. Download files

• Makefile
• dotest
• testpqueue.cpp

Create a files pqueue.h and pqueue.cpp. Copy and paste the module-template into pqueue.cpp. Edit pqueue.cpp. Add your name and the assignment number. If you will use tabs, say how far apart the tab stops are. Add line

  #include "pqueue.h"

A Refinement Plan

---

1. In pqueue.h, add a forward declaration of type PQCell.

   After that, define type PriorityQueue. It must be a structure type with just one field, a pointer to a PQCell, and it must have a constructure that initializes that pointer to NULL.

   Document type PriorityQueue. Do not say that a priority queue is a linked list, because it isn't. A priority queue is represented by a linked list that is in nondescending order by priority.

2. Add prototypes for the functions that are part of the interface to pqueue.h. Include ShowPriorityQueue so that it can be used for debugging. But do not add anything else that is not part of the interface.

3. Write a contract and definition of isEmpty in pqueue.cpp.

4. Write a contract and definition of insertCell in pqueue.cpp.

5. Write a contract and definition of insert in pqueue.cpp. Its body should be one line long, and you will lose points if the body of insert is more than one line long.

6. Write a contract and definition of remove in pqueue.cpp.

   Statement

     exit(1);
   

   stops the program immediately and returns exit status 1 to the operating system. You will need to include <cstdlib> to use exit.

   Be sure that the contract explains all of the parameters clearly.

7. Write a contract and definition of ShowPriorityQueue in pqueue.cpp.

8. Test your module by running the automated tester.

9. Proofread your comments. Check spelling, grammar and correctness. Make sure that comments are written in complete sentences except in numbered lists. Make sure that each contract explains how all of the parameters affect what the function does.

10. When you are satisified that your program works and is well written, submit your work.

Compiling and Testing on Xlogin

---

Use the following commands to compile and test your module.

make testpqueue

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

make pqueue.o

Just compile pqueue.cpp, if necessary.

make test

Do make testpqueue then run it as an automated test.

make debug

Do make testpqueue then run it via the gdb debugger.

make clean

Remove all machine-generated files.

Issues to Be Aware of

---

Keep function definitions short and simple, with no more than 16 noncomment lines each.

As always, you must follow the coding standards for this course. Pay attention to the following.

• Do not ignore compiler warnings. If you do not understand what a warning means, ask about it.

• Every function is required to have a clear, concise and precise contract.

• Each structure type must have documentation that describes what a structure of that type represents and what information each field holds.

• A function body must not change the value of a call-by-value parameter.

• Make each function do its whole job. For example, insertCell should be able to insert a new cell into any linked list that is in nondescending order by priority. Do not limit it to nonempty lists. Pay attention to this! It has been a source of lost points for students in the past.

• If you need a local variable of type PQCell*, create a local variable of type PQCell*, not one of type PriorityQueue. That should be common sense, but many students have violated it in the past.

Submitting Your Work

---

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

  ~abrahamsonk/2530/bin/submit 6 pqueue.cpp pqueue.h

Command

  ~abrahamsonk/2530/bin/submit 6

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

Late Submissions

---

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

Asking Questions

---

To ask a question about your program, first submit it, but use assignment name q6. For example, use command

  ~abrahamsonk/2530/bin/submit q6 pqueue.cpp pqueue.h