CS 2510 Spring 2012: Lab 9 - Direct Access Data Structures

copyright 2012 Felleisen, Proulx, et. al.

Goals

The goal of this lab is to explore the use of direct access data structures, especially the ArrayList.

Partner change

1  The Java Collections Framework.

Start the lab by looking at the web pages for the Java Libraries APIs. Scroll through the All Classes in the lower left frame to find the Comparable and Comparator interfaces. You can see from the descriptions that there is a lot of detail, much more than we would expect from such a simple function-object. We will address some of these issues in the lectures.

Scroll through the All Classes frame on the left again and find the ArrayList class. In lecture we discussed a number of methods we can use to modify/manipulate and instance of ArrayList. Use the online documentation as you work on this part of the lab.

2  Understanding ArrayList.

1. Run the project as is and read the code to see what it does. As you can see, it tests the method size for the class ArrayList

2. Read in the documentation for the method add. Add the tests that verify the correctness of both variants of the method add

3. Read in the documentation for the methods isEmpty and remove. Add the tests that verify the correctness of these method

4. Read in the documentation for the method remove. Add the tests that verify the correctness of both variants of the method remove. Notica, that the variant that removes the desired object uses the identity version of equality for finding the desired object

5. Read in the documentation for the method set. Add the tests that verify the correctness of this method. Make sure you test both the effect and the value that the method produces.

3  Mutating ArrayList.

Continue with the current project and test suite. Define a new instance of ArrayList as follows:

ArrayList arlistSame = this.arlist; 

right after this.arlist has been declared.

1. Define a new instance of ArrayList as follows:

   ArrayList arlistSame = this.arlist; 
   

   right after this.arlist has been declared. Think of what this means, then augment all tests so you would also test what is happening to the arlistSame

2. Now add the following field definition right after the previous one:

   ArrayList arlistOther; 
   

   and as the last line of the method initList add the following line:

   this.arlistOther = new ArrayList(this.arlist); 
   

   Think of what this means, then augment all tests so you would also test what is happening to the arlistOther. Draw a picture that shows the difference between the three lists.

3. Finally, design the method swapAtIndices that swaps the elements of the given ArrayList at the two given positions (indices). Make sure that this method works for any \code{ArrayList}... it should be parametrized as we did in Lecture.

4  Generating Javadocs

Spend a few minutes to learn how to generate web pages of your documentation for this project. Notice that we have already started to write all purpose statements and comments using the JavaDoc format. Under the Project menu select Generate Javadoc and then select the files that should be used to generate the documentation (likely your entire project). By convention we typically generate JavaDoc files into a directory named docs at the same level as the src directory. Be sure to fix any warnings and problems with the generation.

5  Binary Search

This problem will be a part fo the homework assignment, but you can start working on it now.

Start with a new project HW09Problem1 and create two files: Algorithms.java and ExamplesAlgorithms.java.

1. In the class ExamplesAlgorithmms make examples of sorted ArrayLists ofStrings and Integers. Of course, there is no constructor that creates an ArrayList filled with values. You need to define a method initData that adds the values to the initially empty ArrayLists one at a time.

2. Next, design two classes that implement the Comparator interface in Java Collections --- one that compares Strings by lexicographical ordering, one that compares Integers by their magnitude.

3. Now, design the method binarySearch in the class Algorithms that consumes the lower index (inclusive), the upper index (exclusive), an ArrayList of data of the type T, a Comparator of the type T, and an object of the type T and produces the index for this object in the given ArrayList or throws a RuntimeException if the object is not found.