Iterator Pattern

What is Iterator Pattern?

Provide a way to access the elements of the aggregate object sequentially without exposing its underlying representation.
Aggregate object is an object that contains other objects for the purpose of grouping those objects as a unit.It is also called a container or a collection.Examples are linkedList,Hashtable,ArrayList etc.

also read:

Motivation

  • Aggregate object such as a list should allow a way to traverse its elements without exposing its internal structure.
  • It should allow different traversal methods.
  • It should allow multiple traversals to be in progress concurrently.
  • But we really donot want to add all these methods to the interface for the aggregate.

Use of Iterator Pattern

  • To Support traversals of aggregate objects without exposing their internal representation.
  • To support multiple,concurrent traversals of aggregate objects.
  • To provide a uniform interface for traversing different aggregate structures
    (that is, to support polymorphic iteration)

Related Patterns

  • Composite – Iterators are often used to recursively traverse composite structures.
  • Factory Method – Polymorphic iterators use factory methods to instantiate the appropriate iterator subclass.

Iterator Pattern is one which allows us to navigate through a collection of data using a common interface without knowing its underlying implementation.Iterator Pattern should be implemented as interface.This allows every user to implement it in the manner which most likely suits the requirement.

One Real time example of Iterator Pattern is the usage of Remote Controls in Home.Any Remote Control we use to start pressing up and down and back keys to iterate through the channels.

What sort of interface can Iterator be in case of Remote Controls?

One Example Implementation might be:

public interface Iterator {
 public Channel nextChannel(int currentChannel);
 public Channel previousChannel(int currentChannel);
}

The Channel iterator is common for all the remote controls.It’s like a specification implemented by all the remote control manufacturing companies.

public ChannelSurfer implements Iterator {

public Channel nextChannel(int currentChannel) {
 Channel channel=new Channel(currentChannel+1);
 return channel;
 }

public Channel previousChannel(int currentChannel) {
 Channel channel=new Channel(currentChannel-1);
 return channel;
 }
}

public class RemoteControl {

 private ChannelSurfer surfer;

 public RemoteControl() {
  surfer=new ChannelSurfer();
 }

 public Program getProgram(ChannelSurfer surfer) {
  return new Program(surfer.nextChannel());
 }
}

public Program {

// ... Some specific implementation of Program class.
}

We all know that every channel is associated with program and it’s basically the program and not the channel number which a user wants to see.This applies that we can apply some logic before returning the elements through iterator.Iterator here can also be programmed to return ‘the programs’ straight away rather than returning the channels.

Common Java Iterator is Iterator itself.Interface Signature has been copied from the javadoc.

An iterator over a collection. Iterator takes the place of Enumeration in the Java collections framework. Iterators differ from enumerations in two ways:
Iterators allow the caller to remove elements from the underlying collection during the iteration with well-defined semantics.
Method names have been improved.

public interface Iterator<E> {
 boolean hasNext();
 E next();
 void remove();
}

java.util.Collection interface a root interface in Collections hierarchy contains a method iterator() which returns the Iterator interface.Hence any class implementing Collection interface should provide definition for iterator() method.But please note that there are no Guarantees concerning the order(unless this collection is an instance of some class that provides a guarantee) as List by definition guarantees ordered Collection.

When we try to view List interface which extends Collection interface it has a method iterator() which returns an Iterator over the elements in this list in proper sequence.

Now coming to ArrayList a subclass class implementing List interface – which also extends AbstractList class provides definition for iterator() method.Infact all the underlying logic sits in AbstractList class.

When we try to view code it tries to return a Itr innerClass object.

  public Iterator<E> iterator() {
 return new Itr();
    }

   public E remove(int index) {
 throw new UnsupportedOperationException();
    }

Now finally when we try to go through code of Itr we can see that this class implements Iterator interface naturally and provides definition for all methods.

Let us try to view few important parts of the code:

private class Itr implements Iterator<E> {

 /**
  * 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;

 // Note that size() returns the no of elements count in the list.
 public boolean hasNext() {
 return cursor!=size();
 }

 public E next() {
            checkForComodification();
  try {
    E next=get(cursor);
    // Please note that the implementation for get() method is defined in indivudual subclasses like ArrayList class rather than AbstractList itself.
    lastRet=cursor++;
    return next;
  }catch(IndexOutOfBoundsException ie) {
             checkForComodification();
    throw new NoSuchElementModification();
    }
 }

 public void remove() {
  if(lastRet==-1)
  throw new IllegalStateException();
             checkForComodification();
     try {
  AbstractList.this.remove(lastRet); // Please note that remove method will be called depending on the object called.Also an exception is thrown in the remove() method implementation of AbstractList class.

  if (lastRet < cursor)
      cursor--;
  lastRet = -1;
  expectedModCount = modCount;
     } catch(IndexOutOfBoundsException e) {
  throw new ConcurrentModificationException();
     }

 }

 final void checkForComodification() {
  if(modCount!=expectedModCount)
   throw new ConcurrentModificationException();
 }

}

When we try to peep code of ArrayList class to check the implementation of get() method we find:

public E get(int index) {
 RangeCheck(index);
 return elementData[index]; // elementData is an array of type E.
}

    /**
     * Check if the given index is in range.  If not, throw an appropriate
     * runtime exception.  This method does *not* check if the index is
     * negative: It is always used immediately prior to an array access,
     * which throws an ArrayIndexOutOfBoundsException if index is negative.
     */
    private void RangeCheck(int index) {
 if (index >= size)
     throw new IndexOutOfBoundsException(
  "Index: "+index+", Size: "+size);
    }

 When we try to view remove() method logic in ArrayList.

    public E remove(int index) {
 RangeCheck(index);

 modCount++;
 E oldValue = elementData[index];

 int numMoved = size - index - 1;
 if (numMoved > 0)
     System.arraycopy(elementData, index+1, elementData, index,
        numMoved);
 elementData[--size] = null;

 return oldValue;
    }

It clearly tries to remove the specified element by shifting other if remaining elements to left and nullifies last element to null just to make sure if the user is trying to remove last element and finally returns back the value of the element to be removed.

Comments

comments

About Krishna Srinivasan

He is Founder and Chief Editor of JavaBeat. He has more than 8+ years of experience on developing Web applications. He writes about Spring, DOJO, JSF, Hibernate and many other emerging technologies in this blog.

Speak Your Mind

*