External Iterator for Composite

We have seen how the composite pattern could be used to implement a sort of extended iterator to navigate in a structure of menus and submenus. Now we want to go a bit further, and use an external iterator, a quite more complex pattern.

To see it in action, we'll extend the already seen example, so that we'll be able to print menus on the fly, browsing through the elements available and selecting the items matching his own current request.

Using an external iterator we would be able to keep the current position of iteration and keep the current position over the recursive structure of a composite collection.

Here is our new iterator:

import java.util.Iterator;
import java.util.Stack;

class IteratorComposite implements Iterator {
    Stack<Iterator<MenuComponent>> stack = new Stack<Iterator<MenuComponent>>();

    public IteratorComposite(Iterator<MenuComponent> iterator) { // 1
        stack.push(iterator);
    }

    public boolean hasNext() { // 2
        // check if there are element left on the stack
        if(stack.empty())
            return false;

        // check if the current menu has a next element
        Iterator<MenuComponent> it = stack.peek();
        if(it.hasNext())
            return true;

        // no next element in the current element, check the next one
        stack.pop();
        return hasNext();
    }

    public MenuComponent next() { // 3
        if(hasNext() == false)
            return null;

        Iterator<MenuComponent> it = stack.peek();
        MenuComponent mc = it.next();
        if(mc instanceof Menu)
            stack.push(mc.iterator());
        return mc;
    }

    public void remove() {
        throw new UnsupportedOperationException("Not supported yet.");
    }
}

Not the simplest piece of code in the world, actually.
1. The client starts a request, passing an iterator to the item where we want to begin the job. Since we have to manage a tree structure, we use a stack to keep memory of the various levels we could find.
2. To check if there is a next element, we check (a) if the stack is empty - if so, naturally there we'll be no next, and (b) if the current element in the stack has a next - if so we can just return true. Moreover, if (c) the current element has no next, we can just pop it from the stack - there is no more use for it - and enter in a recursion.
3. Before returning the next element, we check if it actually exists. The client should always do this check on its own, so this check is a bit redundant. Looks like we lack of trust in the client. In any case, we peek in the stack for the current iterator, and we get its next element. If it is a Menu, we push on the stack its iterator, since we'll have to get the future next from it. Finally we return what we found.

To keep the code not even more complex we use a Null Iterator, a paradigm similar to the Null Object we have already seen before. MenuItem has nothing to iterate, so we usually return a null when the client ask it for a iterator, and let it to manage this asymmetry. If we return an iterator that never has a next, and if we still call for next, it returns us a null, the code gets less complicated:

import java.util.Iterator;
class IteratorNull implements Iterator {
    public boolean hasNext() {
        return false;
    }

    public MenuComponent next() {
        return null;
    }

    public void remove() {
        throw new UnsupportedOperationException("Not supported yet.");
    }
}

Let's refactor the MenuComponent class adding a method for retrieving its iterator that, by default, return the Null Iterator and change accordingly the derived classes that do return a real iterator - in our case, just the Menu class:

public abstract class MenuComponent {
    // ...
    // common method
    public void print() {
        throw new UnsupportedOperationException();
    }

    public Iterator<MenuComponent> iterator() {
        return new IteratorNull();
    }
}

public class Menu extends MenuComponent {
    // ...
    @Override
    public Iterator iterator() {
        return new IteratorComposite(components.iterator());
    }
}

We still have to change the Waitress class, to add a method using the iterator. Here we have a method for printing just and all the vegetarian dishes available:

public void printVeggieMenu() {
    System.out.println("\nVeggie Menu\n");
    int i = 0;

    Iterator<MenuComponent> it = menus.iterator();
    while(it.hasNext()) {
        MenuComponent mc = it.next();

        if(mc instanceof MenuItem) {
            if(mc.isVeg())
                mc.print();
        }
    }
}

We see in the code a check on the type for the object returned by the iterator, to resolve the transparency added by the composite, since here we actually want to do an operation that makes sense only for MenuItem. The alternatives are try/catching on the call to isVeg() - for a Menu we'll have an exception, or implementing isVeg() also for menu, making it returning always false.

I'm not especially happy with this code. I think I would have taken a different way, something like providing an iterator that would return just MenuItem. I see this is not a clean solution either, since it violates the transparency principle for a composite. But a violation somewhere there has to be, given the problem we are facing, and I will be more comfortable explicitly putting the violation in the class interface, instead of letting Waitress class the burden of messing with it.

In any case, I suggest you to read chapter nine of Head First Design Patterns to have more info on this pattern, and make yourself your idea.