Overview

This week you will modify your solution to the previous assignment. The key modifications will allow you to compare the efficiency of using iterators versus indicies when accessing elements in ArrayLists and LinkedLists.

Details

General Program Guidelines

In addition to providing all of the functionality required in lab 2, you must add the following:

• Give the user the option to draw the desired number of dots and the lines in between the dots on a WinPlotter surface (no longer optional).
• Give the user the option to benchmark the amount of time required to calculate the correct dots to draw.
• Never crash - it should gracefully handle all missing or invalid (don't follow the correct format) input files and any other wacky input from the user.

Your program should look something like this:

If your program is not able to produce a result similar to the image shown above (use the balloon.pnt file), it is not ready to be submitted. You may wish to ask your instructor for help if you get stuck.

Refactoring Lab 2 File Input

Strengthen your exception handling for the file input, if necessary. Your program should react gracefully to invalid input files. If an input file is selected that contains anything other than valid points, the program should display a notice to the user and ignore the file.

Refactoring Lab 2 getDesiredDots Method

In addition to making corrections to critical errors in your previous submission, you must refactor your code so that your getDesiredDots() method conforms to the following:

/**
 * Accepts a list of dots, original, and copies the dots into a list,
 * result, that starts out empty.  The method then uses the technique described
 * in the lab assignment to remove all but the numDesired number of dots.
 * <br />
 * If fewer than numDesired dots are found in original, then a copy of all
 * the dots in original is returned.
 * @param original The list of dots read in from the data file
 * @param result An empty list that will contain the numDesired most critical
 *        dots from the original list
 * @param numDesired The number of dots desired in the resulting list, must be
 *        at least 3
 * @return The number of nanoseconds required to execute
 */
public static long getDesiredDots(List<Dot> original, List<Dot> result, int numDesired);

Furthermore, the method must throw an IllegalArgumentException if any of the following occurs:

• original is null or contains fewer than three points
• numDesired is less than three
• result is null

Using Iterator Access for Dot Picking Algorithm

In addition, you must create an other version of the above method that makes use of one or more iterators to traverse the collection.

/**
 * Accepts a list of dots, original, and copies the dots into a list,
 * result, that starts out empty.  The method then uses the technique described
 * in the lab assignment to remove all but the numDesired number of dots.
 * <br />
 * If fewer than numDesired dots are found in original, then a copy of all
 * the dots in original is returned.
 * @param original The list of dots read in from the data file
 * @param result An empty list that will contain the numDesired most critical
 *        dots from the original list
 * @param numDesired The number of dots desired in the resulting list, must be
 *        at least 3
 * @return The number of nanoseconds required to execute
 */
public static long getDesiredDots2(List<Dot> original, Collection<Dot> result, int numDesired);

Benchmarking

When the user selects the benchmarking option, your program must display the time it took for your program to determine the correct dots to draw using each of four different methods:

1. Using get() to access elements in an ArrayList
2. Using get() to access elements in a LinkedList
3. Using iterators to access elements in an ArrayList
4. Using iterators to access elements in a LinkedList

You should be able to get benchmarks for 1) by timing how long it takes to execute getDesiredDots() when passing in an empty ArrayList for result. Similarly, you should be able to get benchmarks for 2) by timing the call to getDesiredDots() when passing in an empty LinkedList for result. Benchmarks for 3) and 4) can be obtained by calling getDesiredDots2() instead of getDesiredDots().

The benchmarking results may be displayed in the program UI, written to a file, displayed to the console, or displayed in a pop-up window. The times should be displayed in hh:mm:ss.ssss format.

For example, your results of running your benchmarks on the magician.pnt file with fifty desired points might look something like this:

Indexed ArrayList:   00:00:13.1294
Indexed LinkedList:  00:09:51.5123
Iterated ArrayList:  00:00:13.0538
Iterated LinkedList: 00:00:17.1472

Acknowledgements

This assignment was written by Dr. Chris Taylor.

Lab Deliverables

Your submission must include:

• A description of any changes made to your code from lab 2.
• Benchmarking results for:
  • balloon.pnt with 100 desired points
  • balloon.pnt with 1000 desired points
  • skull.pnt with 9000 desired points
• Asymptotic time analysis for four of the following eight situations (do the first four if your last name begins with a letter in the first half of the alphabet, otherwise do the last four), assuming n is the number of points in the original list.
  • If your last name begins with a letter in the first half of the alphabet do these:
    • getDesiredDots() where numDesired = n - 1 and result is an ArrayList.
    • getDesiredDots() where numDesired = 3 and result is an ArrayList.
    • getDesiredDots() where numDesired = n - 1 and result is a LinkedList.
    • getDesiredDots() where numDesired = 3 and result is a LinkedList.
  • If your last name begins with a letter in the last half of the alphabet do these:
    • getDesiredDots2() where numDesired = n - 1 and result is an ArrayList.
    • getDesiredDots2() where numDesired = 3 and result is an ArrayList.
    • getDesiredDots2() where numDesired = n - 1 and result is a LinkedList.
    • getDesiredDots2() where numDesired = 3 and result is a LinkedList.
  Your analysis must include a discussion justifying the O( ? ) answer for each scenerio.
• Your fully documented source files