/ciol/media/agency_attachments/c0E28gS06GM3VmrXNw5G.png)
Follow UsAvijeet Dash,
Satyabrata
Dash and Nagesh
Hassan Sathyanarayana
Intent
Provides a way to access the elements of an aggregate object sequentially
without exposing its underlying representation.
In 30 Seconds
The catch here is ‘taking out the access and traversal responsibility of an
aggregate object from itself to another object called iterator’. For any kind
of aggregate object say List, Vector, Hashtable, Map etc. the most important
client requirement is to traverse through them for elements. The traversal needs
may vary from a sequential traversal to some kind of criteria matching
traversal. Complex aggregates like Composites have traversal needs like
preorder, inorder and postorder. By moving this access and traversal
functionality out of the aggregate object to another coupled object ‘Iterator’
gives a 2-fold solution. Firstly it simplifies the aggregate objects interface
and secondly it lets client to do traversals in various ways without flooding
the aggregate objects like List with many operations for various traversals.
Motivation
The Iterator class defines an interface for accessing the aggregate object’s
(List) elements. It’s also responsible for keeping track of the current
element. ListIterator is a concrete Iterator for List with methods like First(),
Next(), IsDone() and CurrentItem() implemented in it. The List and ListIterator
are coupled. We can have specific kind of aggregates like List and SkipList and
concrete iterators for each of them. For List its ListIterator and for SkipList
it’s SkipListIterator. All these Iterators can extend from a generic Iterator
interface. The responsibility of creating the specific iterator should lie with
the respective aggregate classes by use of Factor method pattern.
Sample Code
AbstractList.java in java.util implements the Iterator as an inner class. See
the implementation below:
private class Itr implements Iterator {
/**
* Index of element to be returned by subsequent call to next.
*/
int cursor = 0;
/**
* Index of element returned by most recent call to next or
* previous. Reset to -1 if this element is deleted by a call
* to remove.
*/
int lastRet = -1;
/**
* The modCount value that the iterator believes that the backing
* List should have. If this expectation is violated, the iterator
* has detected concurrent modification.
*/
int expectedModCount = modCount;
public boolean hasNext() {
return cursor != size();
}
public Object next() {
try {
Object next = get(cursor);
checkForComodification();
lastRet = cursor++;
return next;
} catch(IndexOutOfBoundsException e) {
checkForComodification();
throw new NoSuchElementException();
}
}
public void remove() {
if (lastRet == -1)
throw new IllegalStateException();
checkForComodification();
try {
AbstractList.this.remove(lastRet);
if (lastRet < cursor)
cursor--;
lastRet = -1;
expectedModCount = modCount;
} catch(IndexOutOfBoundsException e) {
throw new ConcurrentModificationException();
}
}
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
public Iterator iterator() {
return new Itr();
}
Complexities simplified
External Iterator and Internal Iterator
The actual iteration can be controlled either in the client or the iterator
itself. If it’s done in client it’s an External Iterator else it’s an
internal iterator. External iterators are more flexible and more widely used.
Internal iterators can be easier to use and mostly used with Composites where it
can record the current position simply by calling itself recursively.
Cursor and Iterator
The traversal algorithm can either be stored in the aggregate or the iterator.
If it’s stored in the aggregate, the iterator simply stores the state of the
iteration. These kinds of iterators are ‘Cursors’. The client can invoke the
next operation on the aggregate with the cursor as an argument. And the Next
operation will change the state of the cursor.
The traversal algorithm when kept in iterators, its easy to reuse them, on
the other hand the algorithms may need to access some private variables of the
aggregate which violates the encapsulation of the aggregate.
Robust Iterator
A robust iterator ensures that insertions and removals won’t interfere with
the traversal and it does it without copying the aggregate. In Java Collection
API Iterators are robust as opposed to enumeration, which are not robust.
Also known as and Related Patterns
It’s also known as ‘Cursor’ and often used in conjunction with
Composites, Factory Method and Memento. An iterator can use a memento to capture
the state of an iteration.
Discussion
An Iterator is recommended when your design has two or more kinds of
collection of objects (Vectors, Hashtables, Lists, Stacks etc...) that you would
like to move through
using similar methods, even though their implementation are different from one
another.
Also the importance of an iterator grows when it provides an uniform interface
to navigate different data structures by the support of polymorphic
iteration.
The Java collection framework uses iterator design pattern in giving
programmatic access to its elements . The Iterator interface in collection
package is a simple interface which provides an iterator over a Collection.
There are some differences between this interface and the Iterator in the
iterator design pattern, most notably the addition of a remove method, and the
exclusion of the CurrentItem(), and First() methods. The First() method however,
can be thought of as being the first call to Next() on a new iteration,. The
CurrentItem() method of the Iterator design pattern, although not directly
implemented in the Iterator interface, can be added by defining a sub-interface
to Iterator.
External Reference
Gamma, E., Helm, R., Johnson,R. & Vlissides, J. (1995).
Design Patterns: Elements of Reusable Object-Oriented Software. Reading
Mass., Addison Wesley.