Drawing Program Part 2

Due: Wednesday, February 24, 1999

Introduction

Congratulations on your working program! Now that you have a reasonably working vector drawing program, your bosses have decided that you should look into seeing ways to improve the performance of the program. Towards this end, they wish for you to experiment with alternative data structures that may (or may not) speed up the program significantly.

Some people within the company have been walking through your code, and have recommended that you change the dynamic array structure you used to implement the PointArray into a linked list data structure. However, others say that its fine the way it is.

You (and, for that matter, the company CEO) are not sure about whether or not this is a good idea. So, you have also been asked to compare/contrast the execution times of both types of programs. In order to make the comparison as device independent as possible, big-O notation, where N is the number of elements in the array/list, should be used to analyze the run-time performance of each of the methods in the PointArray class.

We recommend that as a starting point you utilize the solution code we give for Homework 3. If you choose not to use our solution code, but instead use your own solution as a base, then you will want to download the following files:

• drawer.rc
• drawerView.h
• drawerView.cpp

They provide a new piece of functionality, namely, removing inidividual points from a polyline. This can be done while in point selection mode. Simply move your mouse to a point, click the right mouse button, and a menu will pop up, allowing you to delete the point.

Deliverables

The following two items are expected by the CEO for evaluation purposes:

1. A new version of the PointArray class that utilizes a singly linked list as a core part of its implementation. The specification for the PointArray is the same as before, but with one exception: we have slightly refined the meaning of the set method so that only positions of [0 .. numPoints] (where numPoints is the number of points in the array) are valid. In other words, set may only be used to extend the list by adding one point to the end of the list, or it may be used to change an existing point in the list. An assertion should be triggered if a position not in that range is passed to the method. Note that we have changed neither the commenting nor the code to reflect this new behavior; that is up to you.
2. A document that describes the run-time analysis of both the dynamic array version of PointArray and the linked list version of PointArray. Build a chart giving the running time (in terms of the number of points in the PointArray, n) of each of the methods in these classes. Which of the two implementations is preferable, and why?

Notes on Debugging

Because this is a full fledged windows program, cin/cout/cerr will not work properly. You will have to rely on the debugger and assert statements to determine how your program behaves, if you need to do testing. You could also use fstreams to write debugging output to a temporary file, if you feel the need to do so. Alternatively, since the code you will be running will not involve writing windows code, you could test your code with testing programs in a console environment (like you've done in the past assignments) before trying to integrate the code back into the main system.

Also, remember that just because it happens to work within the framework provided by the interface doesn't mean that your code is correct. It is imperative on your part to test your code under a wide variety of conditions.