Programming Assignment 6 PDF

Preview

Summary

Wednesday, 10/25, 2017. ...

Description

Programming Assignment 6 Assigned: Wednesday, October 25 Due: Wednesday, November 1, 11:59pm

Table of Contents 1. 2. 3. 4. 5. 6. 7. 8. 9.

Purpose of this assignment Background The assignment A refinement plan and additional requirements Compiling and testing on xlogin Issues to be aware of Submitting your work Late submissions 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. Just keep it simple.

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 with a given priority. 3. You can remove the item that has the smallest priority.

For example, suppose that you start with an empty priority queue and imagine performing the following steps. 1. 2. 3. 4. 5.

Insert item "one" with priority 10. Insert item "two" with priority 5. Insert item "three" with priority 15. Remove the item with the smallest priority and call it x. 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 in other applications, 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 2.

PriorityQueue q;

makes q be an initially empty priority queue. 3. 4.

5. 6.

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);

7.

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

8.

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.

A Refinement Plan and Additional Requirements

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

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.

1. 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, write a forward declaration of PQCell, as follows. struct PQCell;

That allows your definition of PriorityQueue to use type PQCell*. 2. 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.

4. Testing Whether a Priority Queue Is Empty 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 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 function into pqueue.h and the definition of insert in pqueue.cpp. 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. 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 has a one-line body. 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.

6. Debugging: Printing the Priority Queue 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. 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. 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. 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

Create file testpq.cpp for testing. Include pqueue.h, with #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); }

Now printPriorityQueue(q, printString, printDouble);

prints priority queue q. 8. Removing an Item Document and define function remove(q, x, p) with the following prototype. void remove(PriorityQueue& q, ItemType& x, PriorityType& p);

It must remove the item from q that has the smallest priority. (If two or more items have the same priority, remove one of them.) It must also 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. Put a prototype for remove into pqueue.h.

9. Test remove 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 outparameters. Check that the results are correct.

10. Proofread pqueue.cpp and pqueue.h. Check contracts for correctness, spelling and grammar. Are standards followed?

11. Submit your work. 12. 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.



Strictly for debugging, it can use

   

bool isEmpty(const PriorityQueue& q); void insert(PriorityQueue& q, ItemType item, PriorityType pri); void remove(PriorityQueue& q, ItemType& item, PriorityType& pri); void printPriorityQueue(const PriorityQueue& q, ItemPrinter pi, PriorityPrinter pp);

Compiling and Testing on Xlogin

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. make testpq Just compile pqueue.cpp and testpq.cpp, if necessary, and link them to create executable file testpq. make pqueue.o Just compile pqueue.cpp, if necessary. make test Do make testpq then run the tester.

make debug Do make testpq then run the tester via the gdb debugger. make clean Remove all machine-generated files. 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.

Issues to Be Aware of

Keep function definitions short and simple. 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 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 name. 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, 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 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 6

will show you what you have submitted for assignment 6. You can do repeated submissions. New submissions will replace old ones....