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

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

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

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

DagElement parent
boolean alreadyVisited

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

Любой совет?


java directed-acyclic-graphs iterator tree visitor
person nkint    schedule 15.11.2010    source источник
comment
Реализация итератора, естественно, полностью зависит от структуры данных, а также от того, в каком порядке вы хотите выполнить итерацию. Определите эти два пункта и обновите вопрос. В любом случае, alreadyVisited не должен быть членом структуры данных, вместо этого сохраняйте Set ссылок на посещенные узлы в итераторе.   -  person Christoffer Hammarström    schedule 15.11.2010
comment
привет, спасибо за комментарий, уже Посетил в наборе действительно хорошо\n. до сих пор я знаю: моя структура данных представляет собой дерево, и я посещаю в предварительном порядке (посещение корня, посещение дочернего элемента). Но все может измениться, и я хочу оставить четкий способ изменить это. так что, возможно, в будущем кто-то захочет взять мой код, использовать другую структуру данных (скажем, связанный список) и другой порядок (скажем, обратный от хвоста к голове) и написать код для его ListElement реализует Element, а его ListIterator реализует итератор, и используйте мой код, который зависит только от интерфейса Element и Iterator. я в неправильном направлении?   -  person nkint    schedule 15.11.2010
comment
Как я уже сказал, реализация итератора ПОЛНОСТЬЮ зависит от реализации структуры данных. Если бы вы могли создать общий итератор, который мог бы перебирать любую структуру данных, кто-нибудь уже сделал бы это.   -  person Christoffer Hammarström    schedule 15.11.2010

Ответы (1)


arrow_upward
1
arrow_downward

Быстрый и грязный метод преобразования рекурсивной эвристики в итеративную заключается в использовании стека (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), порядка, в котором дети ставятся в очередь, и когда они ставятся в очередь. Меня не удивит, что некоторые заказы на посещение могут потребовать поставить в очередь весь набор узлов в правильном порядке сразу (в конструкторе).

person Bert F    schedule 15.11.2010