Computer Science 2530
Spring 2019
Programming Assignment 6

Table of Contents

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

Purpose of This Assignment

---

This assignment gives you experience implementing an abstract data type using linked lists.

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

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.

You will need to define 2 structure types and 5 functions.

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 just a module that can be used as part of a larger application, as you did for assignment 4.

Create a module called pqueue.cpp that implements priority queues, with a header file called pqueue.h that describes what pqueue.cpp exports. The interface includes the following, and nothing else. Types ItemType and PriorityType are discussed below under the refinement plan.

1. A type, PriorityQueue. Creating a PriorityQueue object with line

     PriorityQueue q;
   

   makes q be an initially empty priority queue.

2. Function isEmpty(q) returns true if q is an empty priority queue. Its prototype is

     bool isEmpty(const PriorityQueue& q);
   

3. Function insert(q, x, p) inserts item x with priority p into q. Its prototype is

     void insert(PriorityQueue& q, ItemType x, PriorityType p);
   

4. Function remove(q, x, p) removes the item that has the smallest priority from q. Its prototype is

     void remove(PriorityQueue& q, ItemType& x, PriorityType& p);
   

   Parameters x and p are out-parameters. 'Remove' sets x to the item that was removed and sets p to the priority associated with that item.

   If q is empty, then remove(q, x, p) writes a message on the standard output explaining the problem and stops the program. Statement

     exit(1);
   

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

5. Function printPriorityQueue(q, printItem, printPriority) prints the contents of priority queue q in a readable format for debugging. Parameters printItem and printPriority are functions. PrintPriorityQueue uses printItem(x) to print item x and uses printPriority(p) to print priority p.

Summary of the interface

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

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

    PriorityQueue q;
  

  The priority queue is initially empty.

• It can use the following functions.

    bool isEmpty(const PriorityQueue& q);
    void insert(PriorityQueue& q, ItemType item, PriorityType pri);
    void remove(PriorityQueue& q, ItemType& item, PriorityType& pri);
  

• Strictly for debugging, it can use

    void printPriorityQueue(const PriorityQueue& q,
                            ItemPrinter printItem,
                            PriorityPrinter printPriority);
  

Additional Requirements

---

Your program must follow the design in the section "A refinement plan." It can have additional functions, but it must have at least the functions indicated in the design. Do not add extra responsibilities to the required functions.

A Refinement Plan

---

  typedef const char* ItemType;
  typedef double      PriorityType;

  bool isEmpty(const PriorityQueue& q);

  void insert(PriorityQueue& q, ItemType x, PriorityType p);

  void insertCell(PQCell*& L, ItemType x, PriorityType p)

  typedef void (*ItemPrinter)(ItemType);
  typedef void (*PriorityPrinter)(PriorityType);

  void printPriorityQueue(const PriorityQueue& q,
                          ItemPrinter printItem,
                          PriorityPrinter printPriority);

  printItem(x);

  printPriority(y);

  void remove(PriorityQueue& q, ItemType& x, PriorityType& p)
  {
     x = "nothing";
     p = 0.0;
  }

Compiling and Testing on Xlogin

---

If you haven't already, get files Makefile, dotest and testpqueue.cpp and put them in the directory that holds assignment 6. Then you can use the following commands.

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