Lab 8

Goals: The goals of this lab is to learn how to work with mutable direct access data types defined in the Java Collections Framework library.

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 have 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.

Understanding the ArrayList data structure

For this part of the lab download the file ExamplesArrayList.java, which contains two classes: the ExamplesArrayList class and the Person class. Start a new project, Lab8-ArayLists and import this file into it. Your goal in this part of the lab is to design a test suite for the methods defined for the Arraylist.

• 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.

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

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

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

• Read 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.

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.

  Think of what this means, then augment all tests so you would also test what is happening to the arlistSame object.

• 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.

• 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 ArrayList... it should be parametrized as we did in the lecture.

Generating Javadocs

Spend a few minutes learning 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.

Binary Search

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

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

• In the class ExamplesAlgorithms make examples of sorted ArrayLists of Strings 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.

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

• 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 -1 if the object is not found.

Visitors

We often do not know what kinds of methods the programmers need to define for their lists of objects. Furthermore, they may have to define one specific method for their list that is not applicable to any other list of objects.

For example, we may want to use these classes for our circularly defined data. So we may want to add the method addBook to the classes that represent the list of authors (or addRole to the classes that represent the list of movie actors).

To make the library extensible, the designers need to provide ways for adding new methods at the time the programmer wants to use it.

One way to make the self-referential union of classes extensible is by defining a visitor interface and adding to the union a method that invokes the methods of the visitor interface supplying its own internal data as arguments. This sounds very complicated. We will illustrate this on an example.

Start with a new project HW08Problem2 and add to it all files in from Lab8-Visitors.zip. You should have the following files:

Book.java

Song.java

Image.java

ILo.java

ISelect.java

ExamplesLists.java

NoSuchElementException.java

ILoVisitor.java

Here is an example of a visitor interface for the classes that define a list of objects:

// A visitor for the ILo<T> classes that

// consumes no arguments

// and produces the result of the type R

interface ILoVisitor<R, T>{

// method for the empty list

public R forMt();

// method for the nonempty list

public R forCons(T first, ILo rest);

}

The visitor for a union of data types contains one method for every class in the union, and has the name that indicates the class it targets. The arguments for each method are the fields in the target class that are needed to perform any operations on an object in this field. So, here, the method forMt takes no arguments, as there are no relevant fields in the class MtLo<T>. On the other hand, the method forCons consumes two arguments: first and rest, where the first is of the type T and the rest is of the type ConsLo<T>.

We now add to the classes MtLo<T> and ConsLo<T> the hooks, the methods that accept the instance of the visitor class and invoke the appropriate methods defined there:

// in the interface ILo<T>:

// accept the visitor that produces a result of the type R

public <R> R accept(ILoVisitor<R, T> ilov);

// in the class MtLo< T>:

// accept the visitor that produces a result of the type R

public <R> R accept(ILoVisitor<R, T> ilov){

return ilov.forMtLo();

}

// in the class MtLo< T>:

// accept the visitor that produces a result of the type R

public <R> R accept(ILoVisitor<R, T> ilov){

return ilov.forConsLo(this.first, this.rest);

}

The example included in the Lab8.zip files defines a visitor that represents a method that computes the total download time for all files in the list of image files.

The visitor class (that implements the ILoVisitor<T> interface is defined as follows:

// A visitor that computes the total download time for all files

// in the list of image files

class ILoImageDownloadTimeVisitor

implements ILoVisitor<Integer, Image>{

int speed;

ILoImageDownloadTimeVisitor(int speed){

this.speed = speed;

}

// method for the empty list

public Integer forMt(){

return 0;

}

// method for the nonempty list

public Integer forCons(Image first, ILo rest){

return

first.fileSize / speed + rest.accept(this);

}

}

The following examples show how we can use this method with our lists of data:

ILoVisitor imageDownloads =

new ILoImageDownloadTimeVisitor(200);

// test the use of the ILoMakeStringVisitor

void testILoMakeStringVisitor(Tester t){

t.checkExpect(this.mtloi.accept(this.imageDownloads), 0);

t.checkExpect(this.ilist2.accept(this.imageDownloads), 287);

}

We see that the methods defined in the class that implements the visitor have the same structure as those originally defined inside of the MtLo... and ConsLo... classes. The instance of the list then invokes the new method by applying the accept method with the appropriate visitor as its argument.

• Make another example of the use of the ILoImageDownloadTimeVisitor that computes the download time with the download speed 100 for the list ilist3.

• Design a visitor that implements the method that produces a list of titles of all songs in a list of songs. Of course, you need to make sure that your solution works.

• Design a visitor class that implements the method that produces one long String that contains the titles of all books, separating the titles with the new line String that is encoded as "\n". Of course, you need to make sure that your solution works.

We could now rewrite the solution to the circularly referential problem af books and authors (or actors with movie roles) using the generic list of objects and adding the appropriate visitor to the list of authors (or actors). Work this out on your own as a practice problem - it is not a required part.

You will finish this problem as a part of your next homework.