ulven.org

Using different types of general collections of objects such as lists (List), stacks (Stack) and set (Set) often requires that we iterate (going through) through all elements in the collection.

The most common way of iterating is with the help of a for and loop variable of int type. That is, we would normally iterate like this:

List<Person> people = new ArrayList<Person>();

// we're looking for people called "Homer Simpson"

for (int i=0; i <people.size(); i++) {
     Person p = people.get(i);
     if ("Homer Simpson".equals(p.getName())) {
	// send email to Marge Simpson
	...
     }
}

standard loop structure

The loop handles the loop variable (for-loops clearly distinguish between these three elements, and while-loops have them more implicit):

• declare a loop variable and give it an initial value: int i=0
• checks if the loop should continue: i<people.length
• calculates the next value for the loop variable (i++ / i+=1 / i=i+1 / ++i)

And the loop handles the object for each round of the loop:

• identifies the object to be treated: Person p = people.get(i)
• uses or manipulates the object: if ("Homer Simpson".equals(p.getName())) {... }

The first four points (initialization, test, step, object) depend on what we iterate over. Only the last point (loop body) depends on what we want to do.

Iterating with the help of Iterator

What do we do in a more general case?

An iterator encapsulates the first four points mentioned above, so that the loop is independent of what we iterate over. The complexity of the loop is pushed into the iterator object and thus “inside” the iterator encoder. All data structures should have an associated iterator class and an iterator() method.

The iterator/interface technique gives an uniform way to iterate over elements. A so-called iterator is an object that “generates” objects

• Iterator.hasNext() tells us if there are several other objects to generate.
• Iterator.next() generates the next item (which is “used up”).

List<Person> people = new ArrayList<Person>();

// we're looking for people called "Homer Simpson"

Iterator<Person> itr = people.iterator();
while (itr.hasNext()) {
	Person p = itr.next();
	if ("Homer Simpson".equals(p.getName())) {
		// send email to Marge
		...
	}
}

The iterator “remembers” how far the in list we’ve reached.

• hasNext() returns true as long as we have not come through the entire list.
• next() will return the next item each time, and move a step further in the list.

The iterator() method is defined for all types of collections (Collection). All List and Set implementations have it.

An iterator object remembers how far we have come, and uses the underlying list to check whether we’ve gone through the whole list already and are finished, or retrieve the next item if we haven’t. The iterator technique is a uniform way of iterating through a collection of items. Whether it is a position based list implementation or another type of collection, and independent of the method used to extract objects (table[i] or list.get(i)).

This technique offers less dependency between code accessing a collection and code implementing a collection. It can for instance, create code for adding numbers, without knowing where the numbers come from.

Iterable

Iterable is an interface that only provides one method: iterator(). Simply said, this interface is implemented by classes that have something to iterate over.

public class Person implements Iterable<Person> {
	private List<Person> children;
	public Iterator<Person> iterator() {
		return children.iterator();
	}
}

Thus we can…

Person father = ...
for (Person child: father) {
     // code that uses child
     ...
}

Implementing this interface allows us to use a special variant of the iteration:

List<Person> people = ...
for (Person person: people) {
     ...
}

Which is exactly the same as:

List<Person> people = ...
Iterator<Person> itr = people.iterator();
while (itr.hasNext()) {
     Person person = itr.next();
     ...
}

Or this:

List<Person> people = ...

for (Iterator<Person> itr = people.iterator(); itr.hasNext();) {
	Person p = itr.next();
	...
}

The general form for all:

Iterable<X> x's = ...
for (X x: x's) {
	...
}	

// the same as...

Iterable<X> x's = ...
Iterator<X> itr = x's.iterator();
while (itr.hasNext()) {
	X x = itr.next();
	...
}

// the same as...

List<X> x's = ...

for (Iterator<X> itr = x's.iterator(); itr.hasNext();) {
	X x = itr.next();
	...
}

final example

import java.util.ArrayList;
import java.util.Iterator;

public class Person implements Iterable<Person> {

	private ArrayList<Person> children = new ArrayList<Person>();
	private String name;

	// constructor
	public Person (String name) {
		this.name = name;
	}

	public void addChild (Person person) {
		children.add(person);
	}

	private String getName() {
		return name;
	}

	public Iterator<Person> iterator() {
		return children.iterator();
	}

	public static void main (String[] args) {

		Person homer = new Person("Homer");
		homer.addChild(new Person("Bart"));
		homer.addChild(new Person("Lisa"));
		homer.addChild(new Person("Maggie"));

		for (Person child: homer) {
			System.out.println(child.getName());
		}

	}

}