11 3/18: Iterators
Java & Collections
Out of the box, Java comes with an extensive library of data structures. Java’s standard library takes advantage of its object-oriented nature and thus uses interfaces extensively. For example, most of the important data structures you will use in Java implement the Collection interface.
As you can see, there are quite a few methods that you have to implement to have a real, working Collection. That’s a lot of work for the library designer, but it’s great that you can use any of these methods with most of the data structures in Java.
In this lab, we don’t actually want to make you implement all of these methods by hand. Instead, we will take the easy way out by using classes that Java provides to make our life easier. Before that, we will review iterators.
Iterators
In this lab, we’ll examine one of the core features for working with collection: iterators. First of all, let’s just note that all Collections implement the Iterable interface that is defined like this:
// An Iterable<T> implements
//
// iterator : -> Iterator<T>
// Produces an iterator
This interface lets us extract an iterator in order to iterate over any collection. The iterator itself implements an interface:
// An Iterator<T> implements
//
// hasNext : -> Boolean
// Check if there are more elements
//
// next : -> T
// Produces the next element
// Effect: modifies the iterator's position
//
// remove : -> Void
// Removes the last element produced (optional)
// Effect: modifies the collection
Looks simple enough right? Okay, try implementing it on your own.
Exercise 1. You have implemented the Dict<V> interface many times before. Now improve any of your dictionary classes to implement the Iterable<V> interface.
You will need to define an Iterator class to do this. Note that the V parameter implies that this iterator only iterates over the values stored in the dictionary, not the keys.
Exercise 2. In an Examples class, write a map method that iterates over your dictionary and produces an Iterable<Y> of the new values.
Your map method will need to take as input something implementing the Function<X ,Y> interface.
Exercise 3. Now write a reverse method that returns an Iterable<T> that will iterate in reverse order.
Test both map and reverse with a dictionary.
Your iterator for dictionaries iterates only over the values. What if we want to have both the keys and values? You can represent key-value pairs using an interface like this:
// A Pair<X, Y> implements
//
// getFirst : -> X
// Produce the first item in the pair
//
// getSecond : -> Y
// Produce the second item in the pair
Exercise 4. Now write iterators for your dictionary producing iterators that implement the Iterator<Pair<Key ,V>> interface. Recall that we defined Key to be String in Lab 8.
It turns out there are more specific iterators that let you do more interesting things. For example, there are iterators that specifically work over lists:
// A ListIterator<T> extends Iterator<T> and implements
//
// add : T -> Void
// Add a new element (optional)
// Effect: updates the collection
//
// hasPrevious : -> Boolean
// Check if we can produce the last element
//
// nextIndex : -> Integer
// Produces the index of the next item
//
// previous : -> T
// Produces the last element
// Effect: updates the iterator
//
// previousIndex : -> Integer
// Produces the index of the last item
//
// set : T -> Void
// Set the last element produced to the new element (optional)
// Effect: updates the collection
Note that since ListIterator implements Iterator, it has all of the methods that Iterator implements (e.g., next) even though they are not listed here.
Let’s think of a class that we can use with list iterators. Think back to Lab 5 where you used sorted lists to represent dictionaries. Now let’s just implement a general sorted list class that follows this interface:
// A SortedList<V> implements Iterable<V>
//
// where V implements Comparable<V>
//
// and SortedList<V> also implements:
//
// add : V -> Void
// Add the element to the list
// Effect: modifies the list
//
// remove : V -> Void
// Remove the given element from the list
// Effect: modifies the list
//
// size : -> Integer
// Produces the size of the list
Exercise 5. Implement a SortedList<V> and its iterator. Make sure that the iterator implements Iterator<V>.
Exercise 6. Modify your list so that it produces a ListIterator<V> instead.
Making collections out of iterators
Now you have some experience building iterators and iterable things. Java provides a convenient way to turn anything with an iterator into a full-blown collection using its built-in abstract classes.
The way to do it is to extend the AbstractCollection class and define the following two methods: size and iterator.
Exercise 7. Add a size method to your sorted list class.
Exercise 8. Modify your sorted list to extend AbstractCollection. Try to test all of the methods provided by the Collection interface for your list (you can ignore toArray).
Does this work? If you read carefully, you might notice that some of the optional operations don’t work. Change your tests (using checkException) to accommodate the operations that aren’t implemented and make sure they pass.
Exercise 9. Follow the instructions in the AbstractCollection documentation to implement the optional operations as well. Now test these operations too.
Exercise 10. Now try to make your dictionary class from earlier into a Collection using the same technique.