Use the template for both. Modify the templates with your name and the separation between tab stops, if you use tabs.

Add a comment to pqueue.cpp telling its purpose.

Your module is intended to support an application, not to be an application. But it is not clear right now what types of items or priorities the application will need. For example, should the priorities be integers or real numbers or something else? Should the items be strings or numbers or widgets or something else?

To handle that, define two types, ItemType and PriorityType, in pqueue.h. For this assignment, use definitions

  typedef const char* ItemType;
  typedef double      PriorityType;

Later, when you want to change the definitions of ItemType and PriorityType, you should only need to change those two lines. Not a single other line should need to be touched. (You might need to add one or more #include lines to pqueue.h to make some types available.)

That means you need to write the entire implementation of priority queues using ItemType for the type of an item and PriorityType for the type of a priority. Do not assume that ItemType will be const char* or that PriorityType will be double.

You are required to store the information in a priority queue using a linked list, kept in nondecreasing order by priority. That means items with smaller priorities are closer to the beginning of the linked list. You will need the following types. Provide documentation for each type.

1. In pqueue.cpp, 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. Document type PQCell.

   In pqueue.h, write a forward declaration of PQCell, as follows.

     struct PQCell;
   

   That allows your definition of PriorityQueue to use type PQCell*.

2. In pqueue.h, define a structure type, PriorityQueue, that holds only 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, after the forward declaration of PQCell, so that type PriorityQueue can be used in other modules. Document type PriorityQueue in pqueue.h.

In pqueue.cpp, document and define function isEmpty(q) with the following prototype.

  bool isEmpty(const PriorityQueue& q);

Put a prototype for isEmpty into pqueue.h and a definition of isEmpty in pqueue.cpp.

In pqueue.cpp, document and define function insert(q, item, pri) with the following prototype.

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

Put a prototype for this function into pqueue.h.

You will find it convenient to write a helper function

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

Do not put a prototype for insertCell in pqueue.h since insertCell is not being exported; it is only to be used in pqueue.cpp.

In pqueue.cpp, write a function for debugging that prints the content of the priority queue in a readable format.

There is an important issue here. Remember that the definitions of types ItemType and PriorityType can be changed. You cannot assume that ItemType is const char* or that PriorityType is double. But then how do you know how to print the items and priorities?

A solution is to require the module that uses priority queues to say how to print items and priorities by providing two functions, one for printing an item and another for printing a priority. C++ allows you to pass a function as a parameter of a function. (Think of lending a tool to a friend. You don't use the tool, your friend does.)

Add the following type definitions to pqueue.h.

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

In pqueue.cpp, document and define a function printPriorityQueue with the following prototype.

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

  pi(x);

  pp(y);

PrintPriorityQueue should assume that pi and pp do not write any spaces or newlines. PrintPriorityQueue should print those. It is not acceptable to write out the entire priority queue on one line.

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

Create file testpq.cpp for testing. In testpq.cpp, include pqueue.h, with directive

  #include "pqueue.h"

Add a main function to testpq.cpp. Make it create a PriorityQueue and perform several insertions. After each insertion, show what is in the priority queue using printPriorityQueue.

Assuming ItemType and PriorityType have the default definitions, add the following definitions to testpq.cpp.

  typedef const char* CSTRING;

  void printString(CSTRING s)
  {
    printf("%s", s);
  }

  void printDouble(double x)
  {
    printf("%lf", x);
  }

  printPriorityQueue(q, printString, printDouble);

In pqueue.cpp, document and define function remove(q, x, p) with the following prototype.

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

Be sure that remove deletes the list cell that is removed so that you do not have a memory leak.

Put a prototype for remove into pqueue.h.

Add tests of remove to main in testpq.cpp. Show the contents of the priority queue after each remove. Also show the values sent back from remove to main through the out-parameters. Check that the results are correct.

Check contracts for correctness, spelling and grammar. Are standards followed?

A module that uses priority queues can do the following, and nothing more. Be sure that testpq.cpp adheres to this.

• 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(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 pi, PriorityPrinter pp);