CMUQ 15-121 Iterator

• 1. Introduction
• 2. The Iterator
  • 2.1. What is an Iterator?
  • 2.2. Iterator is an Interface
  • 2.3. The Iterable Interface
• 3. Example
  • 3.1. Basic Roster Class
  • 3.2. Adding an Iterator
  • 3.3. Making Roster Iterable
  • 3.4. Bringing it All Together
• 4. Why is This Useful?

1. Introduction

As you may remember, there are two types of for loops in Java, and either one can be used to go through a variety of lists. Consider the following two implementations of the same method: A simple method to print out the contents of an ArrayList.

Traditional For Loop

public static void printItemsTraditional(ArrayList<String> myList) {
    for(int i = 0; i < myList.size(); i++) {
        String item = myList.get(i);
        System.out.println(item);
    }
}

For-Each Loop

public static void printItemsForEach(ArrayList<String> myList) {
    for(String item: myList) {
        System.out.println(item);
    }
}

In this set of notes we’ll talk about how you can modify your own data structures so that the for-each loop can be used on them. We’ll also discuss why this loop can be more efficient in some cases.

2. The Iterator

https://docs.oracle.com/javase/8/docs/api/java/util/Iterator.html

The for-each loop is actually a Java shortcut for using something called an Iterator. When you use a for-each loop, what Java is actually doing is this:

Actual Code Executed from a For-Each Loop

public static void printItemsActualForEach(ArrayList<String> myList) {
    Iterator<String> it = myList.iterator();
    while(it.hasNext()) {
        String item = it.next();
        System.out.println(item);
    }
}

2.1. What is an Iterator?

An Iterator is an object returned from a collection (such as an ArrayList) that you can use to go through the list sequentially. You use the hasNext method to determine if there are any other items in the collection and you call the next method in order to get the next item. In usage, it is very similar to how we use a Scanner to get the lines of a file.

Let’s go through the last code example. In order to iterate over an ArrayList we get an Iterator for the list by calling myList.iterator(). We then loop over that Iterator, using hasNext to determine if there are more items and calling next to get the next item.

2.2. Iterator is an Interface

Iterator is actually an interface that requires you to implement three methods:

// Returns true if the iteration has more elements. 
// (In other words, returns true if next() would return an element rather than throwing an exception.)
public boolean hasNext();

// Returns the next element in the iteration.
// Throws the NoSuchElementException if the iteration has no more elements
public Object next();

// Removes from the underlying collection the last element returned by this iterator (optional operation). 
// This method can be called only once per call to next(). 
// The behavior of an iterator is unspecified if the underlying collection is modified while the iteration
//  is in progress in any way other than by calling this method.
// Note: If you don't want to support remove, then throw the UnsupportedOperationException instead of
//  actually removing anything.
public void remove();

So, the call myList.iterator() returns an object that implements the iterator interface.

2.3. The Iterable Interface

https://docs.oracle.com/javase/8/docs/api/java/lang/Iterable.html

One more note before we get to a code example: If you want your data structure to be able to be used as a for-each loop, then it needs to implement the Iterable interface. (Notice this is different from the Iterator interface.) The Iterable interface requires only one method:

// Returns an iterator over elements of type T.
public Iterator<T> iterator();

This method simple returns an Iterator for the data structure.

3. Example

Let’s do an example to make things more clear.

3.1. Basic Roster Class

Consider the following Roster class that uses a basic array to store people. It should be fairly straight-forward:

public class Roster {
    private static final int MAX_STUDENTS = 5;

    private Person[] studentList;
    private int end;

    public Roster() {
        studentList = new Person[MAX_STUDENTS];
        end = 0;
    }

    /**
     * Get the number of people in the roster
     * 
     * @return The size of the roster
     */
    public int getSize() {
        return this.end;
    }

    /**
     * Add a person to the roster
     * 
     * @param p The person to add to the roster
     */
    public void addStudent(Person p) {
        if (end < MAX_STUDENTS) {
            studentList[end++] = p;
        }
    }

    /**
     * Get a person from the roster based on index
     * 
     * @param i The index of the person to get
     * @return The person at that index or null if the index is not valid
     */
    public Person getStudent(int i) {
        if (i < end) {
            return studentList[i];
        } else {
            return null;
        }
    }
}

Right now if I want to loop through a roster I would do something like the following:

Roster r = new Roster();
r.addStudent(new Person("Bob"));
r.addStudent(new Person("Fred"));
r.addStudent(new Person("John"));

for (int i = 0; i < r.getSize(); i++) {
    System.out.println(r.getStudent(i));
}

3.2. Adding an Iterator

If I want to be able to use an Iterator to properly go over the Roster, then I need to add a method that returns an Iterator. I’ll add the following new method to my Roster class:

public Iterator<Person> iterator() {
    // What do I do now?
}

Remember, this method needs to return an Iterator that operates over my Roster. Given that Iterator is an interface, that means I need to declare a new class that implements that interface and then return an object of one. So, let’s create a new, inner class that implements the Iterator interface:

public class RosterIterator implements Iterator<Person> {
    // Pointer to the current element the iterator is pointing to
    private int cur = 0;

    // Return true if there is another element, and false otherwise.
    public boolean hasNext() {
        return (cur < end);
    }

    // Return the next item in the Roster and then increment cur
    // If there is no next item, then throw an exception.
    public Person next() {
        if (hasNext()) {
            return studentList[cur++];
        } else {
            throw new NoSuchElementException();
        }
    }

    // I decided not to implement this, so we throw an appropriate exception.
    public void remove() {
        throw new UnsupportedOperationException();
    }
}

We also fill in our iterator method from above to return one of these:

public Iterator<Person> iterator() {
    return new RosterIterator();
}

3.3. Making Roster Iterable

Now that we have implemented all of the required methods, our last step is to make the Roster class Iterable:

public class Roster implements Iterable<Person> {
    ...

Since we have already implemented the interator() method required by this interface, there is nothing else for us to do.

3.4. Bringing it All Together

Here is the final code for our Roster class:

public class Roster implements Iterable<Person> {
    private static final int MAX_STUDENTS = 5;

    private Person[] studentList;
    private int end;

    public Roster() {
        studentList = new Person[MAX_STUDENTS];
        end = 0;
    }

    /**
     * Get the number of people in the roster
     * 
     * @return The size of the roster
     */
    public int getSize() {
        return this.end;
    }

    /**
     * Add a person to the roster
     * 
     * @param p The person to add to the roster
     */
    public void addStudent(Person p) {
        if (end < MAX_STUDENTS) {
            studentList[end++] = p;
        }
    }

    /**
     * Get a person from the roster based on index
     * 
     * @param i The index of the person to get
     * @return The person at that index or null if the index is not valid
     */
    public Person getStudent(int i) {
        if (i < end) {
            return studentList[i];
        } else {
            return null;
        }
    }

    /**
     * Get an iterator for the Roster
     * 
     * @return The iterator
     */
    public Iterator<Person> iterator() {
        return new RosterIterator();
    }

    public class RosterIterator implements Iterator<Person> {
        // Pointer to the current element the iterator is pointing to
        private int cur = 0;

        // Return true if there is another element, and false otherwise.
        public boolean hasNext() {
            return (cur < end);
        }

        // Return the next item in the Roster and then increment cur
        // If there is no next item, then throw an exception.
        public Person next() {
            if (hasNext()) {
                return studentList[cur++];
            } else {
                throw new NoSuchElementException();
            }
        }

        // I decided not to implement this, so we throw an appropriate exception.
        public void remove() {
            throw new UnsupportedOperationException();
        }
    }
}

Using this Roster, we can finally do the for-each loop:

Roster r = new Roster();
r.addStudent(new Person("Bob"));
r.addStudent(new Person("Fred"));
r.addStudent(new Person("John"));

for (Person p : r) {
    System.out.println(p);
}

4. Why is This Useful?

So, why is this useful? Here’s a few reasons:

1. There is a uniform way to go through (iterate over) all of the elements of a variety of data structures.
2. For-each is frequently more readable and faster to write.
3. For some data structures, having this sort of control over iteration can make things more efficient. Consider a linked list: A traditional for loop going through a linked list and using get(i) is \(O(N^2)\) because get(i) is \(O(N)\) and is being called from a loop over \(N\) items. With a properly written iterator, however, a for-each loop through a linked list can be \(O(n)\).