Assigned: | Wednesday, March 1 |
Due: | Wednesday, March 15, 11:59pm |
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.
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.
Details are in the following development plan.
Development plan |
---|
1. Items and Priorities: Types PQItemType and PQPriorityTypeIt 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 PQCellYou 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.
|
3. Testing Whether a Priority Queue Is EmptyDocument 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 QueueDocument 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 ItemDocument 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 QueueFor 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 interfaceA module that uses priority queues can do the following, and nothing more.
|
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.
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.
Note: I might look at your tester to see whether you did a thorough test, but I will not use it for grading. I will use my own tester. So don't assume that you can hide mistakes by avoiding them in the tester. My tester will find them.
To turn in your work, log into the Linux system, change your
directory for the one for assignment 5,
use the following command.
~abrahamsonk/2530/bin/submit 5 pqueue.cpp pqueue.h testpq.cpp
After submitting, you should receive confirmation that the
submission was successful. If you do not receive confirmation,
assume that the submission did not work.
Command
~abrahamsonk/2530/bin/submit 5
will show you what you have submitted for
assignment 5.
You can do repeated submissions. New submissions will replace old ones.
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.
To ask a question about your program, first submit it,
but use assignment name q5. For example, use command
~abrahamsonk/2530/bin/submit q5 pqueue.cpp pqueue.h
Add testpq.cpp if you have written it.
Then send me an email with your question. Do not expect
me to read your mind. Tell me what your questions are.
I will look at the files that you have submitted as q5.
If you have another question later, resubmit your new file
as assignment q5.