Lab 14, CSC 102, Spring 2012
YOU MAY SHOW ME THIS LAB ON FRIDAY
In a Lab14 class, Develop the static void assertIterEquals method, that accepts two Iterator<T> objects and tests whether they contain the same elements. This method should use assertEquals on each pair of elements. Iterators containing different numbers of elements shoudl be considered different. The recursive solution will be shorter. Test this method carefully, because it will be the basis for the remainder of the tests in the lab.
Hint: you’ll need four cases: one when both iterators are empty, one when just the first one is empty, one when just the second one is empty, and one when neither one is empty.
- Develop the static assertSeqEquals method... actually, I’ll just give it to you:
static <T> void assertSeqEquals(Iterable<T> expected, Iterable<T> actual){
assertIterEquals(expected.iterator(),actual.iterator())))
}
Copy or implement the Listt<T> class (using null) from earlier labs. It should have no methods aside from the automatically-inserted ones (equals, hashCode, toString).
In a ListUtils class, develop the static length method, that accepts a Listt and returns its length.
In a ListUtils class, develop the take method, that accepts a Listt and a number ’n’ and returns a new list formed from the first ’n’ elements of the list.
In a ListUtils class, develop the static drop method, that accepts a Listt and a number ’n’ and returns a new list formed by dropping the first ’n’ elements of the list.
In the ListUtils class, develop the static firstHalf method, that returns the list containing the "first half" of the given list, where the number of elements is rounded up, so that the first half of a list of length five would contain three elements.
In the ListUtils class, develop the static secondHalf method, that returns the list containing the "second half" of the given list, where the number of elements is rounded down, so that the second half of a list of length five would contain two elements.
In the ListUtils class, develop the static merge method, that accepts two sorted Listt’s of Comparables and returns a list containing a "merged" list with all of the elements in the two lists in increasing order. As you did for assertIterEquals, you will need four cases. Note that you’ll need the amusing goop that you used to implement the static "insert" method, to ensure that the Listt’s contain Comparable objects.
Using the code from lecture, implement the static mergeSort method, that uses the methods you’ve just implemented to obtain a mergeSort for Listt’s of Comparable objects.
Okay, now we do it again with Vectors! Remember that Vectors are essentially the same as ArrayLists. Check the Java 1.6 API if you have any questions about what methods they have.
Develop the SubVector class, that contains a Vector and two integers, representing the start and end of the "sub-vector" that we’re interested in. Use a constraint to guarantee that SubVectors contain only elements that are comparable to each other.
Develop the Object-oriented firstHalf method on the SubVector class that returns a SubVector containing the first half of this SubVector, using the same rules specified above. Note that no actual creation of Vectors is required.
Develop the Object-oriented secondHalf method on the SubVector class that returns a SubVector containing the second half of this SubVector, using the same rules specified above. Again, no actual creation of Vectors is required.
Develop the Object-oriented merge method on the SubVector class that accepts another SubVector, and returns a new SubVector containing the merged sequences. This method should create a new Vector as part of its operation.
Finally, implement the Object-oriented mergeSort method, that uses the methods you’ve just implemented to obtain a mergeSort for SubVectors .