Dec 30, 2012

Exploring Iterator Design Pattern

Intent
Provide a way to access the elements of an aggregate object sequentially without exposing its underlying representation
Applicability
1. To access an aggregate object's contents without exposing its internal representation.
2. To support multiple traversals of aggregate objects.
3. To provide a uniform interface for traversing different aggregate structures (support polymorphic iteration).
In this post, we will be dealing only with the External Iterators. A typical ExternalIterator interface is as such
package com.devfaqs.designpatterns;

public interface ExternalIterator<E>
{
    public boolean hasNext();
    public E next();
}

The ExternalIterable interface indicates that the implementing aggregate class supports ExternalIterator
package com.devfaqs.designpatterns;

public interface ExternalIterable<E>
{
    public ExternalIterator<E> getIterator();
}
The sample LinkedList aggregate class below implements the ExternalIterable interface and returns ListIterator which is an implementation of ExternalIterator interface

package com.devfaqs.designpatterns;

class Node<E>
{
    Node<E> next = null;
    E data;
}

class LinkedList<E>
    implements ExternalIterable<E>
{
    private Node<E> m_head;

    public LinkedList()
    {
        m_head = null;
    }

    /* Adds element at the end of the list */
    public void add(E n)
    {
        Node<E> tmp = getNewNode();
        tmp.data = n;

        if (isEmpty())
        {
            m_head = tmp;
        }
        else
        {
            Node<E> lastNode = getLastNode();
            lastNode.next = tmp;
        }
    }

    private Node<E> getLastNode()
    {
        Node<E> lastNode = m_head;
        while (lastNode.next != null)
        {
            lastNode = lastNode.next;
        }
        return lastNode;
    }

    private Node<E> getNewNode()
    {
        return new Node<E>();
    }

    private boolean isEmpty()
    {
        return m_head == null;
    }

    @Override
    public ExternalIterator<E> getIterator()
    {
        return new ListIterator<E>(m_head);
    }
}
The ListIterator implementation class
package com.devfaqs.designpatterns;

class ListIterator<E>
    implements ExternalIterator<E>
{
    private Node<E> node = null;

    public ListIterator(Node<E> node)
    {
        this.node = node;
    }

    @Override
    public boolean hasNext()
    {
        return node != null;
    }

    @Override
    public E next()
    {
        Node<E> curent = node;
        node = node.next;
        return curent.data;
    }
}
The client program making use of the External Iterator to print out all the elements in the list
package com.devfaqs.designpatterns;

public class ListExample
{
    static Integer[] elems = new Integer[] { 10, 20, 30, 60, 50, 40, 70, 80, 90, 100 };
    static String[] names = new String[] { "SUPERMAN", "BATMAN", "GREEN ARROW", "BLACK WIDOW", "SPIDERMAN", "HULK", "MIGHTY THOR" };

    public static void main(String[] args)
    {
        LinkedList<Integer> listOfIntegers = new LinkedList<Integer>();
        for (int elem : elems)
        {
            listOfIntegers.add(elem);
        }
        printElements(listOfIntegers);

        LinkedList<String> listOfStrings = new LinkedList<String>();
        for (String name : names)
        {
            listOfStrings.add(name);
        }
        printElements(listOfStrings);
    }

    private static <E> void printElements(LinkedList<E> list)
    {
        ExternalIterator<E> itr = list.getIterator();
        while (itr.hasNext())
        {
            System.out.print("[" + itr.next() + "] ");
        }
        System.out.println();
    }
}
Sample Run
All the code and executable jar can be downloaded from here
External vs Internal Iterators
1. When the client controls the iteration, the iterator is called an external iterator, and when the iterator controls it, the iterator is an internal iterator
2. Internal iterators are easier to use as they define the iteration logic for us whereas in external iterators client is responsible for advancing the iterator and requesting the next element from the iterator
3. External iterators are flexible, You can compare two collections for equality easily with external iterator whereas the same is not possible with the internal iterators

More details on Internal Iterators can be found here

No comments :

Post a Comment