70Lecture 7: Iteration Abstraction and Iterators 7.1 Introduction In this lecture, we describe iteration abstraction and iterators. Iterators are a generalization of the iteration mechanism available in most programming languages. They permit users to iterate over arbitrary types of data in a convenient and efficient way. For example, an obvious use of a set is to perform some action for each of its elements: for all elements of the set do action In this lecture we discuss how we can specify and implement iteration abstraction. We also describe representation exposure as related to iterators. 7.2 Reading Read Chapter 6 of Liskov and Guttag before moving on. The first half of the material of this lecture is based on Chapter 6 of the book, and will not be duplicated here. 7.3 Representation Exposure in Iterators Consider the implementation of an iterator for IntSet. The general structure of the class IntSet would look like this: public class IntSet { private Vector els; // the rep private int size; // the rep // constructors, etc go here, see p. 88 of Liskov … public Iterator elems() { return new IntGen(this); } // static inner class private static class IntGen implements Iterator { public boolean hasNext() { … } public Object next() throws NoSuchElementException { … } public void remove(Object o) { … } } // end of IntGen }71 Notice the additional method remove() in the IntGen class. This method is not required to be implemented, it is optional. The method allows one to remove an element from IntSet while iterating over the elements of the set. It has to be implemented very carefully! Note that in Liskov, modifications to the object being iterated over (i.e., IntSet in our example) are not allowed. However, the Java iterator interface includes the optional remove() method. Now we wish to implement IntGen. We notice that IntSet is represented by the Vector els, and the Vector class has a method that returns an iterator, so we could conceivably implement our method elems() like this: public class IntSet { … public Iterator elems() { return els.iterator(); } } The returned generator els.iterator() provides the next(), hasNext() and remove() methods. This saves us a lot of work, but unfortunately causes a subtle form of rep exposure! We have already discussed a simple form of rep exposure relating to the remove() methods in IntSet and Vector. IntSet implements a remove() method which may affect the size() method. The Vector remove() method does not know about the size of IntSet. So if a client calls the Vector remove() directly, then bad things can happen, e.g., size will be computed incorrectly. Similarly, in the iterator class, if the client directly uses g.remove(), where g = els.iterator(), since there is shared state between the els.iterator() and the Vector els, bad things can happen. We summarize this pictorially below.72 What should we do? We could obviously turn off IntGen remove() or not ever call it, but that is a cop-out. We need IntGen to implement the remove() method so it does the things that IntSet remove() does, and this is the only method that the client can call. IntGen remove() can call g.remove(), where g = els.iterator(), which manipulates the underlying representation while the iterator is being used. This is summarized pictorially below. els Class IntSet size() remove() elems() Vector remove() Client BAD dependence elems() els.iterator() remove() next() hasNext() shared state xxxxxxxx els Class IntSet size() remove() … Vector remove() Iterator Inner Class IntGen remove() els.iterator() remove() next() hasNext() shared state els73Note that implementing IntGen remove() by calling Vector els.remove() is also not a good idea, it might break the iterator with respect to the next() or hasNext()