Рекурсивный итератор для составного шаблона

У меня есть классы дерева AbstractComponent, Leaf и 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;
    }
}

Мой вопрос: как я могу написать рекурсивный итератор на Java для модели, основанной на составном шаблоне? Я прочитал этот вопрос (Создание рекурсивного итератора). Можно принять принятый ответ на мою проблему? Я также нашел класс TreeTraverser из Guava, но он, похоже, ограничен одним классом, представляющим узел.


java iterator composite
person Marcello90    schedule 11.06.2015    source источник

Ответы (2)


arrow_upward
4
arrow_downward

Сначала немного помощи по терминологии.

  • Итераторы не являются рекурсивными. Вам нужна стратегия обхода дерева.

  • Хотя реализации обхода дерева часто являются рекурсивными, для итератора они обычно не подходят.

  • Структура ваших объектов Component называется универсальным деревом.

Во-первых, вам нужно выбрать, как вы хотите перемещаться по составной структуре (также известной как универсальное дерево).

Решение user1121883 — отличный вариант, если у вас нет конкретных требований к порядку обхода, поскольку его просто реализовать.

Если вам нужно реализовать другую стратегию (например, сначала вглубь), попробуйте следующее.

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);
        }
    }
}
person cyroxis    schedule 11.06.2015
comment
Немного (память) расточительно нет? - person shinzou; 28.02.2018

arrow_upward
3
arrow_downward

Итератор не является рекурсивным. Не уверен, что понял ваш вопрос, но базовая структура итератора для вас должна выглядеть так (порядок уровней отсюда: 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;
    }
}
person user1121883    schedule 11.06.2015
comment
Отличное решение, мне очень нравится простота. - person cyroxis; 11.06.2015
comment
Когда стек пуст, stack.pop() выбрасывает NoSuchElementException`. Он не возвращает ноль. - person saka1029; 11.06.2015
comment
@ saka1029 Предполагается, что java.util.Iterator.next выдает исключение NoSuchElementException, если в итерации больше нет элементов; правда могу сделать понятнее и скинуть сам. нулевая проверка есть в случае, если Composite.children имеет ноль - person user1121883; 11.06.2015