The Iterator Pattern

24. The Iterator Pattern The Iterator is one of the simplest and most frequently used of the design patterns. The Iterator pattern allows you to move through a list or collection of data using a standard interface without having to know the details of the internal representations of that data. In addition, you can also define special iterators that perform some special processing and return only specified elements of the data collection. Motivation The Iterator is useful because it provides a defined way to move through a set of data elements without exposing what is taking place inside the class. Since the Iterator is an interface, you can implement it in any way that is convenient for the data you are returning. Design Patterns suggests that a suitable interface for an Iterator might be the following. public interface Iterator { object First(); object Next(); bool isDone(); object currentItem(); } Here you can move to the top of the list, move through the list, find out if there are more elements, and find the current list item. This interface is easy to implement and it has certain advantages, but a number of other similar interfaces are possible. For example, when we discussed the Composite pattern, we introduced the getSubordinates method IEnumerator getSubordinates(); //get subordinates to provide a way to loop through all of the subordinates any employee may have. The IEnumerator interface can be represented in C# as bool MoveNext(); void Reset(); object Current {get;} This also allows us to loop through a list of zero or more elements in some internal list structure without our having to know how that list is organized inside the class. One disadvantage of this Enumeration over similar constructs in C++ and Smalltalk is the strong typing of the C# language. This prevents the Current() property from returning an object of the actual type of the data in the collection. Instead, you must convert the returned object type to the actual type of the data in the collection. Thus, while this IEnumerator interface is intended to be polymorphic, this is not directly possible in C#. Sample Iterator Code Let’s reuse the list of swimmers, clubs, and times we described earlier, and add some enumeration capabilities to the KidData class. This class is essentially a collection of Kids, each with a name, club, and time, and these Kid objects are stored in an ArrayList. public class KidData :IEnumerator { private ArrayList kids; private int index; public KidData(string filename) { kids = new ArrayList (); csFile fl = new csFile (filename); fl.OpenForRead (); string line = fl.readLine (); while(line != null) { Kid kd = new Kid (line); kids.Add (kd); line = fl.readLine (); } fl.close (); index = 0; } To obtain an enumeration of all the Kids in the collection, we simply use the methods of the IEnumerator interface we just defined. public bool MoveNext() { index++; return index < kids.Count ; } //-----public object Current { get { return kids[index]; } } //-----public void Reset() { index = 0; } Reading in the data and displaying a list of names is quite easy. We initialize the Kids class with the filename and have it build the collection of kid objects. Then we treat the Kids class as an instance of IEnumerator and move through it to get out the kids and display their names. private void init() { kids = new KidData("50free.txt"); while (kids.MoveNext () ) { Kid kd = (Kid)kids.Current ; lsKids.Items.Add (kd.getFrname()+ " "+ kd.getLname ()); } } Fetching an Iterator Another slightly more flexible way to handle iterators in a class is to provide the class with a getIterator method that returns instances of an iterator for that class’s data. This is somewhat more flexible because you can have any number of iterators active simultaneously on the same data. Our KidIterator class can then be the one that implements our Iterator interface. public class KidIterator : IEnumerator { private ArrayList kids; private int index; public KidIterator(ArrayList kidz) kids = kidz; index = 0; } //-----public bool MoveNext() { { index++; return index < kids.Count ; } //-----public object Current { get { return kids[index]; } } //-----public void Reset() { index = 0; } } We can fetch iterators from the main KidList class by creating them as needed. public KidIterator getIterator() { return new KidIterator (kids); } Filtered Iterators While having a clearly defined method of moving through a collection is helpful, you can also define filtered Iterators that perform some computation on the data before returning it. For example, you could return the data ordered in some particular way or only those objects that match a particular criterion. Then, rather than have a lot of very similar interfaces for these filtered iterators, you simply provide a method that returns each type of enumeration with each one of these enumerations having the same methods. The Filtered Iterator Suppose, however, that we wanted to enumerate only those kids who belonged to a certain club. This necessitates a special Iterator class that has access to the data in the KidData class. This is very simple because the methods we just defined give us that access. Then we only need to write an Iterator that only returns kids belonging to a specified club. public class FilteredIterator : IEnumerator { private ArrayList kids; private int index; private string club; public FilteredIterator(ArrayList kidz, string club) { kids = kidz; index = 0; this.club } //-----public bool MoveNext() { bool more = index < kids.Count-1 ; if(more) { Kid kd = (Kid)kids[++index]; more = index < kids.Count; while(more && ! kd.getClub().Equals (club)) { kd = (Kid)kids[index++]; more = index < kids.Count ; } } return more; } //-----public object Current { get { return kids[index]; } } //-----public void Reset() { index = 0; } } All of the work is done in the MoveNext() method, which scans through the collection for another kid belonging to the club specified in the constructor. Then it returns either true or false. Finally, we need to add a method to KidData to return this new filtered Enumeration. public FilteredIterator getFilteredIterator(string club) { return new FilteredIterator (kids, club); } This simple method passes the collection to the new Iterator class FilteredIterator along with the club initials. A simple program is shown in Figure 24-1 that displays all of the kids on the left side. It fills a combo box with a list of the clubs and then allows the user to select a club and fills the right-hand list box with those belonging to a single club. The class diagram is shown in Figure 24-2. Note that the elements method in KidData supplies an Enumeration and the kidClub class is in fact itself an Enumeration class. Figure 24-1 – A simple program-illustrated filtered enumeration Figure 24-2– The classes used in the Filtered enumeration Keeping Track of the Clubs We need to obtain a unique list of the clubs to load the combo box in Figure 25-1 with. As we read in each kid, we can do this by putting the clubs in a Hashtable: while(line != null) { Kid kd = new Kid (line); string club = kd.getClub (); if(! clubs.Contains (club ) ) { clubs.Add (club, club); } kids.Add (kd); line = fl.readLine (); } Then when we want to get the list of clubs, we can ask the Hashtable for an iterator of its contents. The Hashtable class has a method getEnumerator which should return this information. However, this method returns an IdictionaryEnumerator, which is slightly different. While it is derived from IEnumerator, it uses a Value method to return the contents of the hash table. This, we load the combo box with the following code: IDictionaryEnumerator clubiter = kdata.getClubs (); while(clubiter.MoveNext ()) { cbClubs.Items.Add ((string)clubiter.Value ); } When we click on the combo box, it gets the selected club to generate a filtered iterator and load the kidclub list box: private void cbClubs_SelectedIndexChanged(object sender, EventArgs e) { string club = (String)cbClubs.SelectedItem ; FilteredIterator iter = kdata.getFilteredIterator ( club); lsClubKids.Items.Clear (); while(iter.MoveNext() ) { Kid kd = (Kid) iter.Current; lsClubKids.Items.Add (kd.getFrname() +" "+ kd.getLname ()); } } Consequences of the Iterator Pattern 1. Data modification. The most significant question iterators may raise is the question of iterating through data while it is being changed. If your code is wide ranging and only occasionally moves to the next element, it is possible that an element might be added or deleted from the underlying collection while you are moving through it. It is also possible that another thread could change the collection. There are no simple answers to this problem. If you want to move through a loop using an Enumeration and delete certain items, you must be careful of the consequences. Deleting or adding an element might mean that a particular element is skipped or accessed twice, depending on the storage mechanism you are using. 2. Privileged access. Enumeration classes may need to have some sort of privileged access to the underlying data structures of the original container class so they can move through the data. If the data is stored in an Arraylist or Hashtable, this is pretty easy to accomplish, but if it is in some other collection structure contained in a class, you probably have to make that structure available through a get operation. Alternatively, you could make the Iterator a derived class of the containment class and access the data directly. 3. External versus Internal Iterators. The Design Patterns text describes two types of iterators: external and internal. Thus far, we have only described external iterators. Internal iterators are methods that move through the entire collection, performing some operation on each element directly without any specific requests from the user. These are less common in C#, but you could imagine methods that normalized a collection of data values to lie between 0 and 1 or converted all of the strings to a particular case. In general, external iterators give you more control because the calling program accesses each element directly and can decide whether to perform an operation on it. Programs on the CD-ROM \Iterator\SimpleIterator kid list using Iterator \Iterator\FilteredIterator filtered iterator by team name