Project 3: Zoom Tables

Due Dates

Design Document: Sunday, April 1, 2007, 11:59pm + 59 seconds

Final Project^*: Monday, April 9, 2007, 11:59pm + 59 seconds

^*Because of the religious holidays around the due date, Monday was chosen to be the official due date. If this creates an unusual hardship, contact Prof. Chang.

Contents

• Objective
• Warning to Procrastinators
• Background
• Assignment
• Grading
• Implementation Notes
• Design Document
• Testing
• Submitting in your program

1. If most of the race course is empty space, then we use a lot of memory to store nothing.
2. When we zoom a car in a particular direction, we may have to loop through a large expanse of empty space to find the new position of the car.

Here, each node represents an object in the race course. Each node has 4 pointers to point to the object above, below, to the left and to the right of the node. (The node might also hold information about the object itself. This is not shown in the diagram.) Using such a ZoomTable, our storage requirement is proportional to the number of objects in the race course and we can determine the new position of a car in one step.

^Return to top

Your assignment is to design and implement the ZoomTable data structure. As in Project 2, your code must conform to the requirements specified below and work with the main programs supplied. You must implement two classes: Node and ZoomTable. Since the primary objective of this project is to have you write code that manages memory dynamically, you are not allowed to use vectors or any other data type that does the dynamic memory allocation and deallocation for you.

Requirements for the Node class

The Node class must also have the following member functions with the prescribed function prototypes:

• Store data into the "payload": void set(int data) ;
• Retrieve the int value from the "payload": int get() const ;
• Return the row number of the node: int row() const ;
• Return the column number of the node: int col() const ;

Requirements for the ZoomTable class

• A destructor that properly deallocates all of the dynamic memory associated with this ZoomTable.
• A copy constructor that makes a deep copy.
• An overloaded assignment operator that makes a deep copy.

• A constructor that creates a ZoomTable that can have the specified number of rows and columns. Note that no Nodes should be added here. ZoomTable(int rows, int cols) ;
• Insert a Node with payload data in the specified row and column. A pointer to the inserted Node must be returned. If there is already a node at that location, its data is overwritten. A NULL value should be returned to indicate an error condition. Node *insert(int row, int col, int data) ;

• Return a pointer to the Node at the specified row and column. If no such node exists, return NULL. Node *find(int row, int col) const ;

• Remove the specified Node from the ZoomTable. Memory for the removed node should be deallocated. void remove(Node *ptr) ;

• Remove the specified Node from the ZoomTable if it exists. If removal is successful return true. If the Node does not exist, return false. Memory for the removed node should be deallocated. bool remove(int row, int col);

• Return the value of the "payload" of the Node located at the specified row and column. If no such node exists, return the default value of 0. int at(int row, int col) const ;

• Return a pointer to the first Node in the specified row or column. Return NULL if row or column is empty. Node *FirstInRow(int row) const ; Node *FirstInCol(int col) const ;

• Return a pointer to the Node immediately to the left, to the right, above or below the Node indicated by ptr. Return NULL if no such Node exists. Node *ZoomLeft(Node *ptr) const ; Node *ZoomRight(Node *ptr) const ; Node *ZoomUp(Node *ptr) const ; Node *ZoomDown(Node *ptr) const ;

• Print out all the Nodes in a ZoomTable in a human-readable format. void dump() const;

• Return the dimensions of the ZoomTable. int rows() const; int cols() const;

• A design document is due on Sunday, April 1, about one week before the final project. (See the Design Document section.) The design document is 15% of the project grade.

• Projects will be graded on five criteria: correctness, design, style, documentation and efficiency. So, turning in a project that merely "works" is not sufficient to receive full credit.

• Part of your grade will also depend on having demonstrated that you have diligently tested your own program, by creating and submitting your own test main program. (See the Testing section.)

• The Academic Conduct Policy for this course states that programming projects must completed by you own individual effort.

• Remember that the late policy is a 25% penalty for submissions up to 24 hours late. Projects more than 1 day late will receive zero.

1. Since Node and ZoomTable are closely related classes (you would not use one without the other), both class declarations should go into a single file ZoomTable.h and both implementations should go into another single file ZoomTable.cpp. Please capitalize ZoomTable exactly.

2. Since a ZoomTable is designed to replace two-dimensional arrays, row and column numbers should begin at 0.

3. When a Node is inserted, you must link the Node into its row and into its column.

4. The ZoomTable member function insert() will allow a programmer to insert 0's into the table, even though one of the main reasons for having a ZoomTable is to not store zeroes. We'll assume the programmer has a good reason for doing so.

5. The ZoomTable member functions insert(), remove() and find() share some common tasks. It will make your code cleaner (and easier to debug) if the common tasks are consolidated into one function. Such functions are usually declared as private member functions.

6. Remember that you are not allowed to use vector.

7. Yes, the copy constructor has to chase down every Node in the ZoomTable and copy it. Ditto for the overloaded assignment operator.

8. The insert() function can be pretty useful when you write the copy constructor and the overloaded assignment operator.

9. Know the difference between delete and delete [].

10. Yes, the destructor has to chase down every Node in the ZoomTable and delete it.

11. Consider using assertions (see p. 169 of your textbook). It is very useful to have assertions like: assert(ptr != NULL) ; in parts of your code where you think you know that ptr can't be or shouldn't be NULL. If you're wrong then the assertion will fail and you will get an error message giving the line number of the assertion that failed. This is much better than having your program crash later when you try to dereference a NULL pointer.

    There is no harm in having too many assertions, since they can be "turned off" easily with a #define NDEBUG.

12. When you get a core dump, remember that you've had practice using the gdb debugger.

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

Answer the following questions using complete English sentences. As usual, grammar and spelling counts. If you remember CUPS = "Capitalization, Usage, Punctuation and Spelling" from elementary school, they certainly apply here.

1. In Lab 6, the List class used dummy headers at the beginning of the linked list. Will you use dummy headers for each row or column of a ZoomTable? If so, how many (1 or 2) and how can you tell when a Node pointer is pointing to a dummy? If no dummy headers will be used, why not?

2. How will your ZoomTable constructor initialize the linked lists for each row and or column? What, if any, items need to be dynamically allocated?

3. Suppose that you locate the insertion point for a Node in a ZoomTable starting at smaller index values to larger ones. When you copy an entire ZoomTable in the copy constructor, should you copy nodes with larger indices first? or smaller indices first? Why would this make a difference?

What/how to submit for your design document:

• Download the plain text file: design.txt. The file has the 3 questions listed above.
• Insert your answers in the plain text file using a text editor.
• Submit the text file to the project 'proj3design' using the Unix command: submit cs202 proj3design design.txt
• You do not need submit any header files. Please do not submit any MS Word files, PDF files, ... Just plain text, please.

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.

You must also create and submit your own test program. Part of your grade depends on this. You should show that you have fully exercised your implementation of the Node and ZoomTable classes.

• p3main1.cpp    Sample output from p3main1.cpp: output1.txt.
• p3main2.cpp    Sample output from p3main2.cpp: output2.txt.

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

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

• ZoomTable.h: contains class declaration for Node and for ZoomTable.

• ZoomTable.cpp: contains the implementation for Node and for ZoomTable member functions.

• myp3main.cpp: Your main program for testing.