Итератор шаблон/итератор


Я реализовал простой итератор. Просто хочу проверить, если я что-то упустил.

interface iterator<E>
    {
        boolean hasNext();

        E next();
    }

    class Iterator<E> implements iterator
    {
        E[] arr;

        int curPos = 0;

        @Override
        public boolean hasNext()
        {
            if (curPos >= arr.length || arr[curPos] == null) 
            {
                return false;
            }
            else
            {
                return true;
            }
        }

        @Override
        public E next()
        {
            if(hasNext())
            {
                E res = arr[curPos];
                curPos++;
                return arr[curPos+1];
            }
            else
            {
                throw new runtimeException("No next element available !");
            }
        }

    }

Вопросы:

  1. Почему я должен не использовать объект вместо э/шаблон везде ?
  2. Как сделать итератор для двоичного дерева.

Я предполагаю, помимо вышеизложенного, я бы реализовать алгоритм обхода и попытаться найти, если существуют очередного "обхода" преемник?



4224
3
задан 4 июня 2011 в 08:06 Источник Поделиться
Комментарии
4 ответа

Я бы написал итератора для массивов таким образом:

import java.util.Iterator;
import java.util.NoSuchElementException;

public class ArrayIterator<E> implements Iterator<E> {

private final E[] arr;
private int currentIndex = 0;

public ArrayIterator(E... arr) {
if(arr == null) {
throw new IllegalArgumentException("Array is null");
}
this.arr = arr;
}

public boolean hasNext() {
return currentIndex < arr.length;
}

public E next() {
if (! hasNext()) {
throw new NoSuchElementException();
}
return arr[currentIndex++];
}

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

}

На ваш второй вопрос: я предполагаю, что вы хотите, чтобы пересечь дерево в порядок, и что узлы имеют ссылку на родителя, только для детей. Тогда вам нужен список узлов от корневого узла к текущему узлу, который может хранить, если узел уже побывали или нет, тоже.

Затем вы идете влево как можно глубже, сохраняя путь в списке узлов. Это ваш первый текущий узел. Когда вам нужно следующее, взять его родитель (из списка узлов). Далее будет право детей этого узла (если есть) или своих собственных родителей. Лучший способ понять это, чтобы взять лист бумаги, рисовать различные деревья, и смотреть, как обход должен работать.

3
ответ дан 5 июня 2011 в 05:06 Источник Поделиться

Потому что тогда потребитель, что код мог бы написать что-то вроде:

Iterator<Foo> iterator = new Iterator<Foo>();

//...

Foo theFoo = iterator.next();

вместо того, чтобы привести объект типа object к типу Foo нравится

Foo theFoo = (Foo)iterator.next();

Она позволяет избежать потенциальной путаницы, будучи строгим о том, что тип объекта ожидать.

1
ответ дан 4 июня 2011 в 09:06 Источник Поделиться

Следующий метод должен выбрасывать исключение в случае итератора до конца. Это не является ни безопасным, ни удобным, чтобы получить НПЭ после того, как iterator был использован неправильно.

1
ответ дан 5 июня 2011 в 12:06 Источник Поделиться

Если вы не определите свой собственный итератор, но использовать Java.утиль.Итератор, вы получите ошибку компилятора:

Iterator.java:9: Iterator is not abstract and does not override abstract method remove() in java.util.Iterator

Чтобы использовать его, где ожидается итератор, вы должны использовать Java.утиль.Итератор, который не будет слишком легко - удалением из массива - но вы могли бы посмотреть, как это сделано в исходном коде Java.

Но тогда компилятор-ваш друг, и говорит вам, что это неправильно.

Для дерева, можно написать несколько итераторов на глубину обхода, или сверху вниз.

1
ответ дан 5 июня 2011 в 05:06 Источник Поделиться