Software Engineering

Compound-Iterator

 German version  up

Problem

Let a be an ArrayList whose entries are again ArrayLists of certain items. In order to iterate over all these items, e.g. for output, two nested loops are necessary:
    public void output(ArrayList a0)
    {
        Iterator i0, i1;
        ArrayList a1;
        i0=a0.iterator();    // standard iterator of ArrayList
        while (i0.hasNext())
        {
            a1=(ArrayList)i0.next();
            i1=a1.iterator();
            while (i1.hasNext())
                System.out.print(i1.next()+" ");
        }
    }

 

The problem is to design one single iterator that iterates over all items in the nested ArrayLists.

Such an iterator is the compound iterator. A compound iterator uses a base iterator (in the example the iterator for ArrayList a0) and a subiterator (in the example the iterator for ArrayList a1), furthermore a function composeItems for forming one new object from the two cursor objects that is returned by the next function of the compound iterator.

The compound iterator follows the bridge design pattern. It uses a behavior that contains the base iterator, the subiterator, and the function composeItems (Figure 1). Furthermore, the behavior contains a factory method for creating the so-specified compound iterator.

Figure 1: Class diagram of a compound iterator with behavior NestedArrayList
Figure 1: Class diagram of a compound iterator with behavior NestedArrayList

Only class NestedArrayList, depicted in blue, is to be written by the user (see next section).

The following program examples do not use type parameters. The import statements required for Iterator and ArrayList have been omitted for shortness.

Behavior NestedArrayList

The behavior NestedArrayList creates a compound iterator that iterates over an ArrayList of ArrayLists. The main ArrayList is passed as a parameter to the constructor. Then, three methods are needed to specify the functionality of the compound iterator.

Any behavior of a compound iterator extends the abstract class CompoundIteratorBehavior that requires methods baseIterator, subIterator and composeItems.

In the method baseIterator the base iterator is specified, and in the method subIterator the corresponding subiterator, depending on the currsor object of the main ArrayList. In this example, the method composeItems uses only the cursor object of the sub-ArrayList. The factory method that returns the compound iterator is provided by the base class CompoundIteratorBehavior.

public class NestedArrayList extends CompoundIteratorBehavior 
{
    private ArrayList a0;

    public NestedArrayList(ArrayList a0_)
    {
        a0=a0_;
    }

    /** the base iterator
     */
    @Override
    public Iterator baseIterator()
    {
        return a0.iterator();
    }

    /** the subiterator,
     *  o0 is the cursor object of the base iterator
     */ 
    @Override
    public Iterator subIterator(Object o0)
    {
        return ((ArrayList)o0).iterator();
    }

    /** specifies the object composed of the two
     *  cursor objects o0 and o1
     *  (here only o1 is used)
     */ 
    @Override
    public Object composeItems(Object o0, Object o1)
    {
        return o1;
    }

}

Usage

The following main function in class TestNestedArrayList tests the compound iterator for NestedArrayList.

public class TestNestedArrayList
{
    public static void main(String[] args)
    {
        ArrayList a0, a1;

        // set up nested ArrayLists
        a0=new ArrayList();

        a1=new ArrayList();   
        a1.add("00");
        a1.add("01");
        a1.add("02");
        a0.add(a1);

        a1=new ArrayList();   
        a1.add("10");
        a0.add(a1);
   
        a1=new ArrayList();   
        a1.add("20");
        a1.add("21");
        a0.add(a1);

        // iterate with compound iterator
        Iterator ci=new NestedArrayList(a0).iterator();
        while (ci.hasNext())
            System.out.print(ci.next()+" ");

        System.out.println();   
    }

}

 

Of course, in this simple example the overhead for using a compound iterator may be too high. However, since the compound iterator implements the iterator interface itself it can be used everywhere where an iterator is appropriate, e.g. as a base iterator in a filter iterator or as a subiterator in another compound iterator.

The program example is based on tested implementations of the classes Compound-Iterator and Compound-IteratorBehavior. These classes are also included in the Java archive de.fh-flensburg.inf.lang.iterators-untyped.jar.

Example

A way to find possible moves m in the domino game is the following:

 

Method:
  1. let p be the end field of the domino chain

    for all free neighbour fields q of p

    1. for all free neighbour fields r of q
      1. for all matching domino pieces s available
        1. set m=new Move(s, q, r)

 

As an example, figure 2 shows some the fields occupied by domino pieces. One of the free neighbour fields of the end of the domino chain p is denoted by q, and one of the free neighbour fields of q is denoted by r. Thus (q, r) is a possible location for the next domino piece.

Figure 2: Possible location (q, r) of next domino piece
Figure 2: Possible location (q, r) of next domino piece

Assume we have an iterator FreeNeighbourIterator that iterates over all free neighbour fields of a certain field p. We combine this iterator with another FreeNeighbourIterator to a compound iterator to iterate over all possible locations for the next domino piece. The compound iterator is generated using the behavior FreeNeighbourLocations.

import java.util.Iterator;

public class FreeNeighbourLocations implements CompoundIteratorBehavior 
{
    private Board b;
    private Position p;
    
    public FreeNeighbourLocations(Board b_, Position p_)
    {
        b=b_;
        p=p_;
    }

    // the base iterator
    @Override
    public Iterator baseIterator()
    {
        return new FreeNeighbourIterator(b, p);
    }

    // the subiterator,
    // o0 is the cursor object of the base iterator
    @Override
    public Iterator subIterator(Object o0)
    {
        return new FreeNeighbourIterator(b, (Position)o0);
    }

     // specifies the object composed of the two
     // cursor objects o0 and o1
    @Override
    public Object composeItems(Object o0, Object o1)
    {
        return new Location((Position)o0, (Position)o1);
    }

}

With new FreeNeighbourLocations(b, p).iterator() we get an iterator that iterates over all possible locations of board b that are adjacent to field p (such as (q, r) in figure 2).

Combining this iterator again with an iterator over all matching domino pieces s will result in an iterator for the possible moves.

 

Next:   up

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   ©   Created: 05.03.2008   Updated: 03.03.2017
Valid HTML 4.01 Transitional