| | |
Often we will want to be able to iterate over an abstract data type -- like a stack -- but we will want to do so in a way the doesn't betray anything about the particular implementation of that abstract data type.
A convenient way to do this is through the use of a "for-each" loop. Suppose we want to be able to iterate over the items of a stack of strings, printing each string as it is visited. Some code that can accomplish this -- provided the Stack class supports it -- can be seen below.
Stack<String> collection = new Stack<String>(); ... for (String s : collection) System.out.println(s); }
We often read this code in the following way: "for each string s in the collection, print s". Being able to type a for loop in this way is actually a bit of "syntactic sugar" provided to us by the compiler. In truth, the following code is what is really being executed in it's place:
Iterator<String> iterator = collection.iterator();
while (iterator.hasNext()) {
String s = iterator.next();
System.out.println(s);
}
More generally, suppose Adt is any abstract data type that represents a collection of items of generic type, and we have defined a variable named collection to be a reference to an Adt object using the type Item:
Adt<Item> collection = new Adt<Item>();Then, the code on the left below is equivalent to the code on the right:
for (Item item : collection) {
// do something with item
}
|
Iterator<Item> iterator = collection.iterator();
while (iterator.hasNext()) {
Item item = iterator.next();
// do something with item
}
|
Returning to the idea that the stack or abstract data type in question must support this type of for-each loop -- one might notice in the above code that our abstract data type class must have a method named iterator(). To this end, we require the abstract data type class implements the Iterable interface, seen below:
public interface Iterable<Item> {
Iterator<Item> iterator();
}
Further, since the iterator() method must return something of type Iterator, we must also have connected in some way to the abstract data type class, a class that implements the Iterator interface, which for reference is given below:
public interface Iterator<Item> {
forEachRemaining(Consumer<? super E> action);
boolean hasNext();
Item next();
void remove(); // <-- you might want to avoid using this method
// and the forEachRemaining(Consumer<? super E> action)
// (i.e., don't even define them). Fortunately, this is legal,
// as they both have default implementations.
}
Note, by creating the class that implements the Iterator interface as an inner class, we can easily provide access to the instance fields and methods of the outer abstract data type class.
Now suppose we go to all the trouble of creating a nice iterable data type so that the client can take advantage of iterating through the elements of the collection in question. As a specific example, let's say we have created an iterable stack. What happens if the client modifies the stack in the middle of iterating through it?
For example, consider the following code:
for (String s : stack) stack.push(s)
Clearly, that's going to be a problem! Modifying the structure of a stack or other similar data type while iterating over its elements is an example of a concurrent modification. One way to try to keep this from happening is to throw a java.util.ConcurrentModificationException.
Of course, how does the stack or other data type detect this has happened, so that they can throw this exception?
To know whether a collection has been structurally modified or not, one can keep an internal count of the number of modifications that have been made to the collection. In the case of a stack, you would want to keep track of the total number of push and pop operations that have happened. Then, upon creation of the iterator object, make a copy of this count (often called the modCount). Thereafter, if upon calling next() or hasNext() one notices the iterator's count and the collection's count disagree, one should throw the exception.