1	The Iterator Design Pattern Keith Alcock TCS DevSIG 2 Sept. 2003
2	Outline Introduction Iteration Iterator Examples C# Java C++ Smalltalk Conclusion Exercise
3	Introduction
4	Iteration Exemplified by C-style for loop: #define SIZE 100 int array[SIZE]; int sum=0; for (i=0;i<SIZE;i++) sum+=array[i]; Included in object-oriented languages: // Java stolen from William Mitchell double sum=0.0; for (int i=0;i<sensors.length;i++) sum+=sensors[i].getTemperature();
5	Iterator “. . . a way to access the elements of an aggregate object sequentially without exposing its underlying representation.” (DP) “any aggregate object” “in any desired sequence”
6	Iteration Problems Concrete traversal method [], ++ (array) next (linked list) for (i=list.first;i!=NULL;i=i.next) // C code sum+=i.value; parent, children, sibling (tree) pop (queue) for (i=queue.top;i!=NULL;i=pop(queue)) // C code sum+=i.value;
7	Iterator Solutions Abstract traversal interface arrayIterator.next() ArrayIterator iterator(array); // C++ for (iterator.first();!iterator.atEnd();iterator.next()) sum+=iterator.current(); linkedListIterator.next() LinkedListIterator iterator(linkedList); // C++ for (iterator.first();!iterator.atEnd();iterator.next()) sum+=iterator.current(); treeIterator.next() queueIterator.next() or just iterator.next()
8	Iteration Problems Code duplication // C code for (i=0;i<SIZE;i++) sum+=array[i]; for (i=0;i<SIZE;i++) product*=array[i]; for (i=0;i<SIZE;i++) printf(“%d\n”,array[i]); for (i=0;i<SIZE;i++) fprintf(fp,”%d\n”,array[i]); for (i=0;i<SIZE;i++) max=max<array[i] ? array[i] : max; for (i=0;i<SIZE;i++) min=array[i]<min ? array[i] : min;
9	Iterator Solutions Code unification “This is Smalltalk.” array do: [ :value \| sum := sum + value ]. array do: [ :value \| product := product * value ]. array do: [ :value \| Transcript nextPutAll: value printString ]. array do: [ :value \| stream nextPutAll: value printString ]. // This is C# foreach (int value in array) max=max<value ? value : max; foreach (int value in array) min=value<min ? value : min;
10	Iteration Problems Mixing of traversal and processing code // Java based on example from Nicholas Lesiecki double tax=0.0; for (int i=1;i<taxBrackets.length;i++) tax+=between(taxBrackets[i-1].cutoff,taxBrackets[i].cutoff, income)*taxBrackets[i].rate;
11	Iterator Solutions Separated traversal and processing code // C# code double tax=0.0; foreach (TaxBracketPair taxBracketPair in taxBrackets) tax+=between(taxBracketPair.left.cutoff, taxBracketPair.right.cutoff, income)*taxBracketPair.right.rate;
12	Iteration Problems No encapsulation of state // BASIC, solves hocus + pocus = presto for h = 0 to 9 for o = 0 to 9 for c = 0 to 9 . . . hocus = h * 10000 + o * 1000 + c * 100 + u * 10 + s . . . next next next
13	Iterator Solutions State encapsulated in “cursor” “This is Smalltalk again.” \| hocusPocusPrestoOdometer \| hocusPocusPrestoOdometer := Odometer on: ‘hocuspocuspresto’. [ hocusPocusPrestoOdometer atEnd ] whileFalse: [ \| hocus pocus presto \| hocus := hocusPocusPrestoOdometer valueFor: ‘hocus’. . . . hocusPocusPrestoOdometer next. ].
14	Iterator Design Goals Provide access without exposing underlying representation Standardize traversal interface Separate traversal of collection from processing of elements Allow traversal in different ways Allow multiple, simultaneous traversals Prevent bloating of collection interface
15	External Iterator Client controls iteration // This is C++ List list; for (ListIterator iterator(list);!iterator.IsDone();iterator.Next()) { Element &element=iterator.CurrentItem(); element.Process(); }
16	Internal Iterator Server controls iteration // This is C# List list=new List(); foreach (Element element in list) element.Process();
17	Iterator Issues Who controls iteration? Does collection know about iterator? How robust is the iterator? (DP) Who cleans up heap-based iterators? How are recursive collections handled? What about boundaries? (NullIterator)
18	Examples
19	C# Examples Syntax allows a single external iterator to act as an internal iterator. (foreach) One cannot add iterators to sealed classes by extention or inheritance. Use proxy or reimplementation. External iterators may require casting and are subject to runtime errors.
20	Java Examples Java provides no syntax support. Some library classes are final and aren’t easily reused. Types may not be aware of their iterators. Casting can be required, especially for mixed containers.
21	C++ Examples Syntax is supported by templates. STL includes multiple iterators for each collection and a framework for making more. Standardized access to iterators is provided. (::iterator, ::reverse_iterator) Casting is often not required.
22	Smalltalk Examples Control structures are implemented in library code rather than with syntax. Base classes are extendible. Dynamic typing requires no casting, but can result in runtime exceptions. Multiple internal iterators are supported. External iterators are not often used.
23	Conclusion Iterators are relatively easy to use and are supported by object-oriented languages. Begin by using built-in iterators, Then make your own, as you Replace iteration with iterators.
24	Exercise // Java Examples in a Nutshell, p. 12 // Rewrite this program using iterators with no “for” or “%” public class FizzBuzz { public static void main(String[] args) { for (int i=1;i<=100;i++) { if ((i%5)==0 && (i%7)==0) System.out.print(“fizzbuzz”); else if ((i%5)==0) System.out.print(“fizz”); else if ((i%7)==0) System.out.print(“buzz”); else System.out.print(i); System.out.print(“ “); } System.out.println(); } }