Lab 8: Working with ArrayLists and Iterators
Goals: The goals of this lab is to get practice with designing methods on array lists and iterators.
8.1 Filtering on ArrayLists
<T> ArrayList<T> filter(ArrayList<T> arr, Predicate<T> pred)
8.1.1 Abstraction and Naming
Next, define filterNot, which has the same signature as filter, but keeps all of the elements filter does not.
As you can see, there is a lot of overlap between filter and filterNot. Abstract these two methods by defining a new method with the header:
<T> ArrayList<T> customFilter(ArrayList<T> arr, Predicate<T> pred, boolean keepPassing)
filter and filterNot are now essentially convenience methods that call customFilter. To anyone using the util class, their intent is clear just based on the names of filter and filterNot. As the designer of the util class, you only have to write one complex method. Whenever you want to create a method whose behavior can be configured by one or two simple boolean flags, it is a good idea to name each of these options and have one abstracted method do the heavy lifting.
8.1.2 Mutation
<T> void removeFailing(ArrayList<T> arr, Predicate<T> pred)
A boilerplate for-loop here will fail. Why?
Be sure to test this carefully.
Next, define removePassing and customRemove, analgous to filterNot and customFilter above.
8.2 Combining ArrayLists
The rest of the lab asks you to define methods that produce iterators. For the remove method, you are welcome to throw an UnsupportedOperationException. Be sure to throw a NoSuchElementException if next is called when hasNext is false.
8.2.1 Interweaving
<T> ArrayList interweave(ArrayList<T> arr1, ArrayList<T> arr2)
The method should interweave the two lists in order, so the first element of the output list comes from arr1, the second from arr2, the third from arr1, etc. If one list runs out before the other, the output list should finish with just elements from the longer list.
<T> ArrayList interweave(ArrayList<T> arr1, ArrayList<T> arr2, int getFrom1, int getFrom2)
This should work similarly to interweave, but instead of getting an element from arr1, then arr2, then arr1, etc., this should get (up to) getFrom1 elements from arr1, then (up to) getFrom2 elements from arr2, then (up to) getFrom1 elements from arr1, etc. For instance, given two lists ["A", "B", "C", "D", "E", "F"] and ["w", "x", "y", "z"], if we took three elements at a time from the first list, and two elements at a time from the second, we should produce ["A", "B", "C", "w", "x", "D", "E", "F", "y", "z"]. Similarly to the basic interweave, if one list runs out before the other, the list should finish with just elements from the longer list.
Then, redefine the first version of interweave as a call to this more general (and more complex) one.
8.2.2 Zipping
Given the pair class:
class Pair<L, R> { L left; R right; Pair(L left, R right) { this.left = left; this.right = right; } }
<X, Y> Iterator<Pair<X,Y>> zipLists(ArrayList<X> arr1, ArrayList<Y> arr2)
The method should return an iterator of pairs of corresponding elements. If the lists are of different sizes, only return pairs up to the size of the shorter one.
8.3 Combining Iterators
<T> Iterator<T> concat(Iterator<T> iter1, Iterator<T> iter2)
The method should produce a new iterator that concatenates the two iterators (similar to append on lists). Note that this method should terminate even if iter1 or iter2 is an infinitely large iterator.