Chain of Responsibility
Iterator Design Pattern
In software engineering the Iterator Pattern is one of the most simple and frequently used design patterns. This pattern lets you sequentially move through a collection of objects using a standard interface, and without having to know the internal representation of that collection
But what is more important is that a collection should provide a way to access its elements without exposing its internal structure. We should have a mechanism to traverse in the same way a list or an array. It doesn't matter how they are internally represented.
The idea of the iterator pattern is to take the responsibility of accessing and passing trough the objects of the collection and put it in the iterator object. The iterator object will maintain the state of the iteration, keeping track of the current item and having a way of identifying what elements are next to be iterated.
IntentionIt Provides a way to access the elements of an aggregate object sequentially without exposing its underlying representation.
The abstraction provided by the iterator pattern allows you to modify the collection implementation without making any changes outside of collection. It enables you to create a general purpose GUI component that will be able to iterate through any collection of the application.
Applicability & ExamplesThe iterator pattern allow us to:
Example 1:This exmple is using a collection of books and it uses an iterator to iterate through the collection. The main actors are:
And here is the code for concrete classes for iterator and collection. Please note that the concrete iterator is an nested class. This way it can access all the members of the collection and it is encapsulated so other classes can not access the BookIterator. All the classes are not aware of BookIterator they uses the IIterator:
Example 2:Java collection framework
Example 3:.NET collection framework
Specific problems and implementation
Iterator and multithreadingSeveral problems may appear when collections are added from different threads. First of all let's see which the basic steps when using an iterator are:
Let's analyze each case:
The main task when creating a multithreading iterator is to create a robust iterator (that allows insertions and deletions without affection transversal). Then the blocks which are changing or accessing resources changed by another thread have to be synchronized.
External vs. internal iterators.External Iterators - when the iteration is controlled by the collection object we say that we have an external Iterator.
In languages like .net on java it's very easy to create external iterators. In our classical implementation an external iterator is implemented. In the following example an external iterator is used:
Internal Iterators - When the iterator controls it we have an internal iterator On the other side implementing and using internal iterators is really difficult. When an internal iterator is used it means that the code is be run is delegated to the aggregate object. For example in languages that offer support for this is easy to call internal iterators:
The main idea is to pass the code to be executed to the collection. Then the collection will call internally the doSomething method on each of the components. In C++ it's possible to send the doMethod method as a pointer. In C# .NET or VB.NET it is possible to send the method as a delegate. In java the Functor design pattern has to be used. The main idea is to create a base Interface with only one method (doSomething). Then the method will be implemented in a class which implements the interface and the class will be passed to the collection to iterate. For more details see the Functor design pattern.
Who defines the traversal algorithm?The algorithm for traversing the aggregate can be implemented in the iterator or in the aggregate itself. When the traversal algorithm is defined in the aggregate, the iterator is used only to store the state of the iterator. This kind of iterator is called a cursor because it points to the current position in the aggregate.
The other option is to implement the traversal algorithm in the iterator. This option offers certain advantages and some disadvantages. For example it is easier to implement different algorithms to reuse the same iterators on different aggregates and to subclass the iterator in order to change its behavior. The main disadvantage is that the iterator will have to access internal members of the aggregate. In Java and .NET this can be done, without violating the encapsulation principle, by making the iterator an inner class of the aggregate class.
Robust Iterators- Can the aggregate be modified while a traversal is ongoing? An iterator that allows insertion and deletions without affecting the traversal and without making a copy of the aggregate is called a robust iterator. A robust iterator will make sure that when elements are added or removed from an aggregate during iteration; elements are not accessed twice or ignored.
Lets' say we don't need a robust iterator. If the aggregate can not be modified (because the iteration is started), it should be made explicitly, meaning that the client should be aware of it. We can just return a false value what an element is added to the collection stating that the operation has failed, or we can throw an exception.
An alternative solution is to add functions to change the aggregate in the iterator itself. For example we can add the following methods to our iterator:
In the case when this solution is chosen the iterator handles the changes of the aggregator. In this case the operation to change the iteration should be added to the iterator interface or base class not to the implementation only, in order to have a general mechanism for the entire application.
Mechanism provided by the programming languageThe iterator pattern can be implemented from scrach in Java or .NET, but there is already built-in support for Iterator Pattern (IEnumerator/IEnumerable in .NET and Iterator/Collection in JAVA).