Software Engineering

Compound-Iterator

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 NestedArrayLists

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

Only class NestedArrayLists, 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.

The behavior NestedArrayLists 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 NestedArrayLists<Type>
extends CompoundIteratorBehavior<ArrayList<Type>, Type, Type>
{
    private ArrayList<ArrayList<Type>> a0;

    public NestedArrayLists(ArrayList<ArrayList<Type>> a0_)
    {
        a0=a0_;
    }

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

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

    /** specifies the object composed of the two
     *  cursor objects x0 and x1
     *  (here only x1 is used)
     */
    @Override
    public Type composeItems(ArrayList<Type> x0, Type x1)
    {
        return x1;
    }

}

The following main function in class TestNestedArrayLists tests the compound iterator for NestedArrayLists.

public class TestNestedArrayLists
{
    public static void main(String[] args)
    {
        ArrayList<ArrayList<String>> a0;
        ArrayList<String> a1;

        a0=new ArrayList<ArrayList<String>>();

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

        a1=new ArrayList<String>();
        a1.add("10");
        a0.add(a1);

        a1=new ArrayList<String>();
        a1.add("20");
        a1.add("21");
        a0.add(a1);

        // with compound iterator
        Iterator<String> ci=new NestedArrayLists<String>(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.

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

Method:

let p be the end field of the domino chain

for all free neighbour fields q of p

for all free neighbour fields r of q

for all matching domino pieces s available

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

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<Position, Position, Location>
{
    private Board board;
    private Position p;

    public FreeNeighbourLocations(Board board, Position p)
    {
        this.board=board;
        this.p=p;
    }

    // the base iterator
    @Override
    public Iterator<Position> baseIterator()
    {
        return new FreeNeighbourIterator(board, p);
    }

    // the subiterator,
    // p0 is the cursor object of the base iterator
    @Override
    public Iterator<Position> subIterator(Position p0)
    {
        return new FreeNeighbourIterator(board, p0);
    }

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

}

With new FreeNeighbourLocations(board, p).iterator() we get an iterator that iterates over all possible locations of board board 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]

H.W. Lang mail@hwlang.de Impressum Datenschutz
Created: 05.03.2008 Updated: 18.02.2023

Software Engineering

Compound-Iterator

Problem

Behavior NestedArrayLists

Usage

Example