UMBC, CMSC202 Computer Science II, Spring 2007

Project 5: Zoom Tables Revisited

Due Dates

Design Document: Sunday, May 6, 2007, 11:59pm + 59 seconds

Final Project: Sunday, May 13, 2007, 11:59pm + 59 seconds

Contents

Objective

 The objective of this project is to practice writing C++ templates.

^Return to top

Background

 For this programming project, you will make the ZoomTable class you designed in Project 3 more useful by:

  1. making the ZoomTable templated, so your client can define ZoomTables of any underlying object,

  2. making ZoomTable member functions throw an exception when an index out of bounds error is encountered, and

  3. adding row and column iterators to make efficient traversal the rows and cols of the ZoomTable easier.
The first two improvements are straightforward. The third one needs some explanation. You can look in Lab 13 for a basic explanation of iterators, but the root of the problem is this. Suppose your client wants to do something with a row in the ZoomTable. The code might look something like: ZoomTable Z ; ... for (int i = 0 ; i < Z.cols() ; i++) { ... Z.at(row,i) ; } This is terribly inefficient because every time your client makes a call to Z.at(row,i), your at() function must find the Node with coordinates (row,i) all over again. A loop that should take linear time will instead take quadratic time. Although it is possible to be efficient using the Zoom functions, it is cumbersome when all your client wants to do is to step through a row of the ZoomTable.

This problem can be resolved using an iterator. The container classes in the C++ Standard Template Library (STL) use many types of iterators, you will implement a simple version here. The code for stepping through a row of the ZoomTable looks like:

ZoomTable<int> Z ; ZTRowIterator<int> it ; int row = ... ; for (it = Z.RowBegin(row) ; it != Z.RowEnd(row) ; it++) { ... *it ; } The iterator "it" remembers a position in a row of the ZoomTable --- stepping to the next position takes constant time and does not require any looping. The ZTRowIterator class must have the ++ and * (dereference) operators defined. The * (dereference) operator returns a value of the underlying type, in this example an int. The whole loop takes linear time and allows your client to write code using a familiar-looking for loop.

^Return to top

Assignment

 There are 3 parts to this project: make ZoomTables templated, add exceptions, and add iterators.

Templated ZoomTable

This part of the project is straight forward, although you may be spending some time with the compiler figuring out where you need a <T> and where you don't.

The header file for ZoomTable should go in a file called ZoomTable.H. The ZoomTable.cpp file holds the templated implementation. ZoomTable.H should include ZoomTable.cpp at the bottom. (Other schemes are prevalent and possibly better, but we need to stick to one format.)

All of the templated class definitions, including Node, ZTRowIterator and ZTColIterator should go in ZoomTable.H.

There is one change in the ZoomTable requirement from Project 3. Since we don't know the underlying type of a ZoomTable when we write the template, we must require the client to supply us with the default value of the table where we don't store a node. Thus, the alternate constructor for ZoomTable is expanded to:

template <class T> ZoomTable::ZoomTable(int rows, int cols, T d_value) ;

To test that your templated class actually works on a different data type, create a class called Cup (defined and implemented in Cup.h and Cup.cpp). You will use the ZoomTable to simulate the ball-tossing game seen in many a county fair. Different colored cups are laid out on a grid. You toss a plastic ball at the cups. If the ball lands in a white cup, you get nothing. If it lands in a red cup, you get a small prize. If it lands in a silver cup, you get the grand prize.

Your Cup class must have at least two string data members for the color of the cup and the prize associated with that cup. White is the default value (and has no associated prize). Write a small main program, cuptest.cpp, to exercise the ZoomTable functions. {\it Note:} you need to implement an overloaded output operator (<<) for your Cup class in order to have the dump() method work properly.

ZoomTable Exceptions

Revise your code so your ZoomTable member functions throw an exception when an index out of bounds error is encountered. The type of the exception is ZTerror and is given in ZTerror.h. Note that ZTerror is a data-only class and does not have any member functions defined.

Requirements for the iterator classes

Two components are required for the iterators to work. You need begin and end functions in ZoomTable and overloaded operators in the iterator classes.

Add 4 member functions to your templated ZoomTable class:

ZTRowIterator<T> RowBegin(int row) ; ZTRowIterator<T> RowEnd(int row) ; ZTColIterator<T> ColBegin(int col) ; ZTColIterator<T> ColEnd(int col) ; The RowBegin() function should return a ZTRowIterator that represents the coordinate (row,0) in the ZoomTable. Note that this is not the FirstInRow() function, because we actually want column 0, even if no Node is stored there. The RowEnd() function returns a ZTRowIterator that represents a coordinate that is past the last column of the ZoomTable. A typical for loop using iterators ends when the condition it != Z.RowEnd(row) fails. This happens when "it" is incremented beyond the last column and equals the iterator returned by RowEnd().

The specifications for ColBegin() and ColEnd() are analogous.

The actual data you have stored in ZTRowIterator and ZTColIterator depends on your design for ZoomTable. Think about how you will represent coordinates where an actual Node is stored and coordinates between two actual nodes.

The ZTRowIterator class must be templated and must support the following methods:

You may need to add other methods depending on your design. The requirements do not specify the data members in ZTRowIterator. The methods listed above should be public. It makes sense to have ZTRowIterator be a friend of Node and/or ZoomTable. To do so, you will need to have forward class declarations like: template <class T> class ZTRowIterator ;

The requirements for ZTColIterator class are analogous.

Most designs will not have dynamically allocated data members in ZTRowIterator or ZTColIterator. If your design for some reason requires dynamically allocated data members, you will have to implement a destructor, a copy constructor and an assignment operator.

^Return to top

Grading

^Return to top

Implementation Notes

  1. If your Project 3 is does not work, you will be allowed to build on Prof. Chang's implementation of Project 3. Details will be posted on the News section of the course website.

    [Now available: ZoomTable.h, ZoomTable.cpp.]

  2. ZTRowIterator needs to know several things that are stored in ZoomTable, including the default value of type T, and the number of rows and cols. A simple way to make these accessible is to store a pointer to the ZoomTable in the ZTRowIterator (similar to what we did with RaceCourses and Cars in Projects 2 and 4).


^Return to top

Design Document

You must submit written responses to these questions by Sunday, May 6, 11:59:59pm. Late submissions are not accepted for design documents.

Include the templated class definition for your ZTRowIterator. You are not beholden to the exact definition for your final project, but it will help in your answer to these questions:

  1. How will your ZTRowIterator represent the coordinates in a ZoomTable that are in between two actual Nodes in a row? What happens when you increment?

  2. After you increment a ZTRowIterator, how can you check if you have gone past the last column?

  3. How will your ZTRowIterator * (dereference) operator know when it should return the default value?

What/how to submit for your design document:

Please submit only 1 file.

^Return to top

Testing

 You are provided with 2 main programs listed below. Your design and implementation of ZoomTable classes must compile and run with these 2 programs without any modification.

A separate main program will be posted shortly which tests the exception handling part of your program. [Now available as p5main3.cpp. See below.]

Warning: When your project is graded, it will also be tested with additional main programs. So, having a project that works with these programs is not a 100% guarantee. Your project must also satisfy the requirements specified above.

Note: You were required to implement a Cup class and write a program to test that the ZoomTable template actually worked on a different data type. See the Assignment section.



^Return to top

Submitting in your program

 Remember to submit the design document the first week!

Use the UNIX submit command to turn in your project. The project name for Project 5 is 'proj5'. So, the Unix command will look like:

submit cs202 proj5 ... where ... is a list of files you wish to submit.

You should submit the following files. Please follow the capitalization and spelling of these files.


Note: We will assume that your template will compile properly when the main program, main.cpp, includes ZoomTable.H and is compiled using: g++ -ansi -Wall main.cpp and nothing else.


^Return to top