Recursive iterator for composite pattern

Question

I have the tree classes AbstractComponent, Leaf and Composite:

public abstract class AbstractComponent {
    privavte String name;

    [...]
}

public class Leaf extends AbstractComponent {
    [...]
}

public Composite extends AbstractComponent {
    private List<AbstractComponent> children;

    public void addChild(AbstractComponent a) {
        [...] 
    }

    public List<AbstractComponent> getChildren() {
        return children;
    }
}

My question: How can I write a recursive iterator in Java for a model that is based on the composite pattern? I read this question (Creating a recursive iterator). It is possible to adopt the accepted answer to my problem? I also found the TreeTraverser class from Guava but it seems to be limited to one class that represents a node.

Answer 1

First some help on terminology.

• Iterators are not recursive. What you are looking for is a strategy of Tree Traversal.

• While tree traversal implementations are often recursive they typically will not be for an iterator.

• The structure of your Component objects is called a generic tree.

1st you need to pick how you want to traverse your composite structure (a.k.a Generic Tree)

user1121883's Solution is a great option if you don't have specific traversal order requirements because it is Simple to implement.

If you need to implement a different strategy (e.g. depth first) try the following

class AbstractComponent {

    public Iterator<AbstractComponent> iterator() {
        List<AbstractComponent> list = new LinkedList<AbstractComponent>();
        addAllChildren(list);
        list.add(this);
        return list.iterator();
    }

    protected abstract void addAllChildren(List<AbstractComponent> list);
}

public class Leaf extends AbstractComponent {

    //...

    protected void addAllChildren(List<AbstractComponent> list) {
        //DO NOTHING
    }
}

public class Composite extends AbstractComponent {

    //...

    protected void addAllChildren(List<AbstractComponent> list) {
        for (AbstractComponent component : children) {
            // This is where you implement your traversal strategy
            component.addAllChildren(list);
            list.add(component);
        }
    }
}

Answer 2

An iterator is not recursive. Not sure if I understood your question but a basic iterator for you structure should look like ( level order from here: http://en.wikipedia.org/wiki/Tree_traversal ) :

 public class AbstractComponentIterator implements Iterator<AbstractComponent> {

    Deque<AbstractComponent> stack = new LinkedList<>();


    public AbstractComponentIterator(AbstractComponent root) {
        stack.add(root);
    }

    @Override
    public boolean hasNext() {
        return !stack.isEmpty();
    }

      @Override
    public AbstractComponent next() {
        if(stack.isEmpty()){
            throw new NoSuchElementException();
        }
        AbstractComponent node = stack.pop();
        if (node != null) { //only if Composite.children has null 
            if (node instanceof Composite) {
                Composite ac = (Composite) node;
                for (AbstractComponent acc : ac.children) { 
                    stack.add(acc);
                }
            }
        }
        return node;
    }
}