This lab was written by Prof. John Bowers.
Introduction
As you saw in CS 159, in addition to the the standard for and while looping structures, Java
supports the “for-each” loop structure for iterating over all elements in a collection. The following method, for example, prints out all integers passed into it through its list parameter:
public void printAll(ArrayList<Integer> list) {
for (int i : list) {
System.out.println(i);
}
}
This syntactic sugar is a lot more convenient than the typical for loop:
public void printAll(ArrayList<Integer> list) {
for (int i = 0; i < list.size(); i++) {
System.out.println(list.get(i));
}
}
All of the standard Java Collections Framework classes (ArrayList, LinkedList, HashMap, etc.) work with for-each loops. In this lab, you will learn how to make your own iterators and use them to loop over a custom collection.
What is an iterator?
Recall from CS 159 that the iterator design pattern abstracts the idea of “looping” over an aggregate object like an ArrayList or HashSet. The iterator pattern provides methods for retrieving the next item (next()) as well as checking whether there is a next item (hasNext()). A typical loop using an iterator looks like:
// Assuming we have a List<Integer> type object list:
Iterator<Integer> iterator = list.iterator();
while (iterator.hasNext()) {
Integer nextInt = iterator.next();
// ...
}
The code above gets an Iterator object from the list using the .iterator() method. It then uses the iterator’s hasNext() and next() methods to loop over all of the integers stored in list.
The purpose of the iterator pattern is to hide the underlying implementation specific details about how to loop over a particular data structure and allow the programmer to think just about the high level loop structure–we don’t think “to iterate over this list, I need to use an integer index and add one to it each time.” No. Instead we think “to iterate over this list I’ll keep getting the next item until there aren’t any more.” This greatly simplifies the job of the programmer using our code.
Creating an iterator
In order to create an iterator in Java, you subclass java.util.Iterator and implement the next() and hasNext() methods. Here is a simple example of a class that provides an iterator for looping over a fixed-sized array of message strings:
import java.util.Iterator;
import java.util.NoSuchElementException;
public class Messages {
String[] messages = new String[10];
public Messages() {
for (int i = 0; i < 10; i++) {
messages[i] = "Message #" + i;
}
}
private class MessageIterator implements Iterator<String> {
int index;
public MessageIterator() {
index = 0;
}
@Override
public boolean hasNext() {
return index < 10;
}
@Override
public String next() {
if (hasNext()) {
return messages[index++];
} else {
throw new NoSuchElementException();
}
}
@Override
public void remove() {
throw new UnsupportedOperationException();
}
}
public Iterator<String> iterator() {
return new MessageIterator();
}
public static void main(String[] args) {
Messages theMessages = new Messages();
Iterator<String> iterator = theMessages.iterator();
while (iterator.hasNext()) {
System.out.println(iterator.next());
}
}
}
Our iterator is implemented in the private inner class MessageIterator. The MessageIterator keeps track of what index in the list it is currently on. A call to hasNext() checks whether index is valid (i.e. is less than 10). A call to next() returns the value stored at messages[index], if index is valid, or otherwise throws a NoSuchElementException. The remove() method is essentially optional (in Java 8, it actually is optional, but we are using Java 7 in this class), but we have to implement it in order to implement the Iterator interface. This is done by having it throw the UnsupportedOperationException, which keeps it from being used.
Notice that the only purpose of having the inner class MessageIterator is to support the iterator() method. We really don’t even need to give this class a name. We make the code a bit cleaner by defining the inner class as an anonymous inner class within the iterator() method, like so:
import java.util.Iterator;
import java.util.NoSuchElementException;
public class Messages {
String[] messages = new String[10];
public Messages() {
for (int i = 0; i < 10; i++) {
messages[i] = "String #" + i;
}
}
public Iterator<String> iterator() {
return new Iterator<String>() {
int index = 0;
@Override
public boolean hasNext() {
return index < 10;
}
@Override
public String next() {
if (hasNext()) {
return messages[index++];
} else {
throw new NoSuchElementException();
}
}
@Override
public void remove() {
throw new UnsupportedOperationException();
}
};
}
public static void main(String[] args) {
Messages theMessages = new Messages();
Iterator<String> iterator = theMessages.iterator();
while (iterator.hasNext()) {
System.out.println(iterator.next());
}
}
}
Now, consider the loop structure in main that loops over all of the messages using the iterator and prints them out. Our Messages class is really an aggregate of ten messages. It would be convenient if we could use a for-each to loop over the messages:
Messages theMessages = new Messages();
for (String message : theMessages) {
System.out.println(message);
}
To support the for-each loop, we need to make our class implement the Iterable interface, which provides an iterator() method. The for-each loop uses the iterator() method in order to build a normal while-loop structure as in our original code. Here is the listing of our code now modified to implement iterable() and then use a for-each loop:
import java.util.Iterator;
import java.util.NoSuchElementException;
public class Messages implements Iterable<String> {
String[] messages = new String[10];
public Messages() {
for (int i = 0; i < 10; i++) {
messages[i] = "String #" + i;
}
}
@Override
public Iterator<String> iterator() {
return new Iterator<String>() {
int index = 0;
@Override
public boolean hasNext() {
return index < 10;
}
@Override
public String next() {
if (hasNext()) {
return messages[index++];
} else {
throw new NoSuchElementException();
}
}
@Override
public void remove() {
throw new UnsupportedOperationException();
}
};
}
public static void main(String[] args) {
Messages theMessages = new Messages();
for (String message : theMessages) {
System.out.println(message);
}
}
}
That’s it! Almost nothing changed since we had already named our iterator method iterator(), we only had to add implements Iterable to our class signature and add an @Override annotation to iterator() to tell the compiler that it implements the iterator() method from Iterable.
Now it gets awkward
As we saw above, having a class implement Iterable and return an anonymously defined Iterator object is very straightforward. An Iterator is an object that allows us to iterate over some aggregate (or collection). An Iterable is an aggregate that provides an Iterator of some sort. Easy, no?
Well, not quite. The problem comes when we want to support more than one type of iterator for the same aggregate type. Why is this a problem? Well, consider trying to add a second type of iterator to Messages. One that only iterates over the last five messages. In order to use a for-each loop with Messages we made it implement the Iterable interface and provided an implementation of iterator(). But that’s all we get. We can’t provide a second implementation of iterator() in the same class that returns some other sort of iterator. Instead, and here’s where it gets awkward, we have to create a method which returns an Iterable object wrapped around an Iterator. Study the following example to see what this means:
import java.util.Iterator;
import java.util.NoSuchElementException;
public class Messages implements Iterable<String> {
String[] messages = new String[10];
public Messages() {
for (int i = 0; i < 10; i++) {
messages[i] = "String #" + i;
}
}
public Iterator<String> iterator() {
return new Iterator<String>() {
int index = 0;
@Override
public boolean hasNext() {
return index < 10;
}
@Override
public String next() {
if (hasNext()) {
return messages[index++];
} else {
throw new NoSuchElementException();
}
}
@Override
public void remove() {
throw new UnsupportedOperationException();
}
};
}
/**
* An Iterable object for constructing an iterator that loops over the
* last five messages.
*/
public class LastFiveIterable implements Iterable<String> {
@Override
public Iterator<String> iterator() {
return new LastFiveIterator();
}
}
/**
* An iterator for iterating over the last five messages.
*/
public class LastFiveIterator implements Iterator<String> {
int index;
public LastFiveIterator() {
index = 5;
}
@Override
public boolean hasNext() {
return index < 10;
}
@Override
public String next() {
if (hasNext()) {
return messages[index++];
} else {
throw new NoSuchElementException();
}
}
@Override
public void remove() {
throw new UnsupportedOperationException();
}
}
/**
* @return An iterable object for iterating over the last five messages.
*/
public Iterable<String> lastFive() {
return new LastFiveIterable();
}
public static void main(String[] args) {
Messages theMessages = new Messages();
System.out.println("Printing all the messages:");
for (String message : theMessages) {
System.out.println(message);
}
System.out.println("\nPrinting the last five messages: ");
for (String message : theMessages.lastFive()) {
System.out.println(message);
}
}
}
Notice the difference between iterator() and lastFive(). The iterator() method simply returns an Iterator object, whereas the lastFive() method returns a LastFiveIterable object that itself implements a second iterator() method that returns a LastFiveIterator object. If you need to support more than one iterator, this is (awkwardly), the Java way of doing it: all of your extra iterators need two components–an iterator type and an iterable type, which acts as a factory for iterators.
Iterators Lab
You are now going to implement a class for storing a variable list of messages. Internally, the messages will be stored inside an ArrayList object. Your task is to implement iterators for several different methods of iterating over a list. The model for the code you will write is the lastFive() method above. Write each of the following methods and test them:
everyOther(): returns anIterableobject that constructs anIteratorfor looping over every other item in the list (the items at even numbered indices). You may either create inner classesEveryOtherIteratorandEveryOtherIterableto support this method or (BONUS) implement it using anonymous classes.reversed(): returns anIterableobject that constructs anIteratorfor looping over the list in reverse order. You may either create inner classesReversedIteratorandReversedIterableto support this method or (BONUS) implement it using anonymous classes.startsWith(String s): returns anIterableobject that constructs anIteratorfor looping over all the messages that start with the String stored in parameters. You may create inner classesStartsWithIteratorandStartsWithIterable. (Using anonymous classes in this one is considerably harder in Java 7, so let’s avoid it.)twice(): returns anIterableobject that constructs anIteratorfor looping over all the messages twice. You may either create inner classesTwiceIteratorandTwiceIterableto support this method or (BONUS) implement it using anonymous classes.
Listing: Messages.java
import java.util.ArrayList;
import java.util.Iterator;
import java.util.NoSuchElementException;
public class Messages implements Iterable<String> {
ArrayList<String> messages = new ArrayList<String>();
public void addMessage(String message) {
messages.add(message);
}
/**
* @return An iterator for looping over all messages once.
*/
public Iterator<String> iterator() {
return messages.iterator();
}
/**
* @return An iterable object for iterating over every other message.
*/
public Iterable<String> everyOther() {
throw new UnsupportedOperationException();
}
/**
* @return An iterable object for iterating over the messages backwards.
*/
public Iterable<String> reversed() {
throw new UnsupportedOperationException();
}
/**
* @param s The desired prefix string.
* @return An iterable object over all strings that start with a prefix string s.
*/
public Iterable<String> startsWith(String s) {
throw new UnsupportedOperationException();
}
/**
* @return An iterable for iterating over all messages twice.
*/
public Iterable<String> twice() {
throw new UnsupportedOperationException();
}
public static void main(String[] args) {
Messages theMessages = new Messages();
theMessages.addMessage("Curse your sudden but inevitable betrayal!");
theMessages.addMessage("Everything's shiny captain.");
theMessages.addMessage("Ten percent of nothin' is ... let me do the math here ... nothin'"
+ " into nothin' ... carry the nothin' ...");
theMessages.addMessage("Without your space helmet, Dave? You're going to find that rather "
+ "difficult.");
theMessages.addMessage("Not all those who wander are lost.");
theMessages.addMessage("It's the job that's never started as takes longest to finish.");
theMessages.addMessage("Where there's life there's hope, and need of vittles.");
System.out.println("Printing every other:");
for (String message : theMessages.everyOther()) {
System.out.println(message);
}
System.out.println("\nPrinting reversed:");
for (String message : theMessages.reversed()) {
System.out.println(message);
}
System.out.println("\nPrinting starts with \"W\":");
for (String message : theMessages.startsWith("W")) {
System.out.println(message);
}
System.out.println("\nPrinting twice:");
for (String message : theMessages.twice()) {
System.out.println(message);
}
}
}
Turn in:
When you have completed all the iterators turn in your Messages.java file using Web-Cat.