Assigned: | Tuesday, October 30 |
Due: | Monday, November 5, 11:59pm |
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.
A priority queue is a collection of items each having a priority. A priority queue supports three fundamental operations.
You can ask a priority queue whether it is empty.
You can insert an item into the priority queue with a given priority.
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.
You should find that x is "two" and y is "one".
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.
A type, PriorityQueue. Creating a PriorityQueue object with line
PriorityQueue q;makes q be an initially empty priority queue.
Function isEmpty(q) returns true if q is an empty priority queue. Its prototype is
bool isEmpty(const PriorityQueue& q);
Function insert(q, x, p) inserts item x with priority p into q. Its prototype is
void insert(PriorityQueue& q, ItemType x, PriorityType p);
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.
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.
Development plan |
---|
1. Create a directory for assignment 6 and create
files pqueue.h and pqueue.cpp.
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. |
2. Items and Priorities: Types ItemType and PriorityType
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 is const char* or that PriorityType is double. They might be changed. |
3. 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. 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.
|
4. Testing Whether a Priority Queue Is Empty
In pqueue.cpp, document and define function isEmpty(q) with the following prototype. 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 and a definition of isEmpty in pqueue.cpp. |
5. Insertion into a Priority Queue
In pqueue.cpp, document and define function insert(q, item, pri) with the following prototype. void insert(PriorityQueue& q, ItemType x, PriorityType p);'Insert' inserts item x with priority p into PriorityQueue object q. Put a prototype for this 'insert' into pqueue.h. You will find it convenient to write a helper function void insertCell(PQCell*& L, ItemType x, PriorityType p)that inserts item x with priority p into linked list L. It assumes that L is in nondescending order by priority, and it inserts the new item into the correct spot so that the list is still in nondescending order. The reason is that 'insertCell' can be recursive, and that makes it easier to write. The body of 'insert' should just make a call to 'insertCell'. That is, 'insert' should have a one-line body. Do not put a prototype for 'insertCell' into pqueue.h since 'insertCell; is not being exported; it is only to be used in pqueue.cpp. |
6. Debugging: Printing the Priority Queue
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 might 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);They define types ItemPrinter and PriorityPrinter. The function to print an item has type ItemPrinter; it takes a parameter of type ItemType and has a void return type. The function to print a priority has type PriorityPrinter. It takes a parameter of type PriorityType and has a void return type. In pqueue.cpp, document and define a function printPriorityQueue with the following prototype. void printPriorityQueue(const PriorityQueue& q, ItemPrinter pi, PriorityPrinter pp);It must show a clear and readable representation of what is in priority queue q, including each value and its priority. 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. |
7. Testing insert
Add a void remove(PriorityQueue& q, ItemType& x, PriorityType& p) { x = "nothing"; p = 0.0; } Put a prototype for remove into pqueue.h. (It is just the heading followed by a semicolon.) Now use the automated tester to test insert. Don't be surprised that errors are reported about 'remove' not working. But don't move on to the next step until 'insert' is working. |
8. Removing an Item
In pqueue.cpp, replace the stub for 'remove' by a correct definition. 'Remove' must remove the item from q that has the smallest priority. (If two or more items have the same priority, remove one of them.) Parameters x and p are out-parameters. 'Remove' must store the item that is removed into variable x and store its priority into p. Be sure that remove deletes the list cell that is removed so that you do not have a memory leak. |
9. Test remove
Rerun the automated tester. This time, everything should look right. If not, fix any errors. |
10. Proofread pqueue.cpp and pqueue.h.
Check contracts for correctness, spelling and grammar. Are standards followed? Are all parameters described and referred to by name? Are contracts written in complete sentences? |
11. Submit your work.
|
A module that uses priority queues can do the following, and nothing more. Be sure that testpq.cpp adheres to this.
|
Get files Makefile, dotest and testpqueue.cpp and put them in the directory that holds assignment 6. Then you can use the following commands.
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 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. 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.
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
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 6
will show you what you have submitted for
assignment 6.
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 q6. For example, use command
~abrahamsonk/2530/bin/submit q6 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 q6.
If you have another question later, resubmit your new file
as assignment q6.