Как создать оболочку итератора для структуры DAG в Java? - PullRequest
Новая
       29

Как создать оболочку итератора для структуры DAG в Java?

2 голосов
/ 15 ноября 2010

Я хочу иметь итератор для структуры данных. Пока я не знаю, что такое структура данных, возможно, это DAG (направленный ациклический граф), но, возможно, это может быть также связанный список. Поэтому я хочу обернуть его в итератор и не думать сейчас о конкретной структуре данных.

Я знаю, как посетить DAG с рекурсивным посетителем, но я не могу понять простую и понятную структуру для реализации методов итераторов next() и hasNext().

Внутри итератора я создал текущий экземпляр узла и перебрал цикл for для всех потомков, а затем вернулся к родителю. Требуется уже посещенный флаг. Так что у моего DagElement есть следующие атрибуты: 

DagElement parent
boolean alreadyVisited

Я не думаю, что это чистое решение.

Любой совет?

1 Ответ

1 голос
/ 15 ноября 2010

Быстрый и грязный метод преобразования рекурсивной эвристики в итеративную состоит в том, чтобы использовать стек (LIFO) или очередь (LILO) для хранения «дорог, которые не приняты» - пути найдены, но еще не приняты. В этом случае итератор будет иметь переменную экземпляра стека или очереди. Что-то вроде: 

    class DagIterator<T>
    extends Iterator<T> {

        private Stack<DagNode<T>> nodes;

        private DagIterator(Dag<T> dag) {
            nodes.push(dag.getRootNode());
        }

        public boolean hasNext() {
            return ! nodes.isEmpty();      
        }

        public T next() {
            final DagNode node = nodes.pop();
            for (final DagNode child : node.getChildren()) {
                nodes.push(child);
            }
            return node.getValue();
        }

    }

Вы настраиваете порядок посещения на основе структуры данных (LIFO или LILO), порядка, в котором дети помещаются в очередь, и когда они ставятся в очередь. Меня не удивит, что некоторые заказы на посещение могут потребовать постановки в очередь всего набора узлов в правильном порядке сразу же (в конструкторе).

...