I need help with the following assignment only using C++.

This assignment gives you experience using linked lists and again gives you experience in implementing a module of a larger program. The module implements an abstract data type.

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

The Assignment: Priority Queues

For this assignment, you will not write an application, but just a module that can be used in other applications, as you did for assignment 3.

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. There are just three operations.

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

You can remove the item with the smallest priority from the collection (and be told what the removed item and priority are).

You can ask whether the collection is empty.

Details are in the following development plan.

Development plan

1. Items and Priorities: Types PQItemType and PQPriorityType

It is not clear right now what types of items or priorities an application will need. For example, should the priorities by integers or real numbers or something else? Should the items be strings or widgets or something else?

To handle that, you will define two types, PQItemType and PQPriorityType. Start with default definitions of them. But it must be possible to change what those types are by changing only one line for each type.

Here are default definitions that you are required to use for this assignment. Put

 typedef const char* PQItemType; typedef double PQPriorityType; 

in pqueue.h to define type PQItemType to be const char* and PQPriorityType to be double.

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.

2. Representing Priority Queues: Types PriorityQueue and PQCell

You are required to store the information in a priority queue using a linked list, kept in nondecreasing order by priority. You will need the following types. Provide documentation for each type.

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. Write the definition of PQCell in pqueue.cpp. Document type PQCell.

In pqueue.h, just write

 struct PQCell; 

to allow your definition of PriorityQueue to use type PQCell*.

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

Write the definition of type PriorityQueue in pqueue.h so that it can be used in other modules. Document type PriorityQueue.

3. Testing Whether a Priority Queue Is Empty

Document and define function isEmpty with the following heading.

 bool isEmpty(const PriorityQueue& q); 

isEmpty(q) must return true if q is empty, false if q is not empty.

Put a prototype for isEmpty into pqueue.h. (A prototype is just the function heading followed by a semicolon.)

4. Insertion into a Priority Queue

Document and define function insert(q, item, pri) with the following heading.

 void insert(PriorityQueue& q, PQItemType item, PQPriorityType pri); 

Insert inserts item item with priority pri into PriorityQueue object q.

Put a prototype for this function into pqueue.h. The prototype is just the function's heading followed by a semicolon. By putting this prototype in pqueue.h, you are saying that other modules should be allowed to use it.

Put the definition of insert into pqueue.cpp. You will find it convenient to write a helper function

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

that inserts a given item into a linked list. The reason is that this function can be recursive. The body of insert should just make a call to insertCell.

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.

5. Removing an Item

Document and define function remove with the following heading.

 void remove(PriorityQueue& q, PQItemType& item, PQPriorityType& pri); 

It must remove the item from q that has the smallest priority. (If two items have the same priority, remove one of them.) It must also store the item that is removed into variable item and stores its priority into pri.

Put a prototype for remove into pqueue.h.

Be sure to delete the list cell that is removed.

6. Debugging: Printing the Priority Queue

For this part, write a function for debugging that prints the content of the priority queue.

But there is an issue here. Remember that types PQItemType and PQPriorityType can be changed. You cannot assume that PQItemType is const char* or that PQPriorityType 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.

Add the following type definitions to pqueue.h.

 typedef void (ItemPrinter)(PQItemType); typedef void (PriorityPrinter)(PQPriorityType); 

They define types ItemPrinter and PriorityPrinter. The function to print an item has type ItemPrinter; it takes a parameter of type PQItemType and has a void return type. The function to print a priority has type PriorityPrinter. It takes a parameter of type PQPriorityType and has a void return type.

Document and define a function printPriorityQueue with the following heading.

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

It must show a clear and readable representation of priority queue q. In the body of printPriorityQueue, use statement

 pi(x); 

to print item x and

 pp(y); 

to print priority 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.

Another module can print a priority queue by defining functions for printing items and priorities. For example, If PQItemType and PQPriorityType have the default definitions, then the following would be suitable.

 typedef const char* CSTRING; void printString(const char* s) { printf("%s", s); } void printDouble(double x) { printf("%lf", x); } 

Now

 printPriorityQueue(q, printString, printDouble); 

prints priority queue q. Notice that printString and printDouble are not written in pqueue.cpp. Put them in your tester, testpq.cpp.

7. Summary of the priority queue interface

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

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 inser(PriorityQueue& q, PQItemType item, PQPriorityType pri); void remove(PriorityQueue& q, PQItemType& item, PQPriorityType& pri); 

Strictly for debugging, it can use

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

Nonfunctional Requirements

Keep function definitions 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. Refer to parameters by nam. The contract must not be concerned with how the function works.

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

Each function body must have no more than 15 noncomment lines.

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

Make a 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.

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.