Объединение итераторов с помощью итератора итераторов

Question

Мне дали задание:

Реализовать интерфейс с методом Iterator<Integer> convert(Iterator<Iterator<Integer>> it).

Что из себя представляет запись Iterator<Iterator<Integer>?.

Каждый итератор - это последовательность.

Итератор 1 – 4 2 0 4 6 4 9

Итератор 2 – 0 9 8 7 5

Итератор 3 – 1 3 5 6 7 0 9 8 4

Если мы говорим о записи Итератор Итераторов. Значит, итератор содержит не конечные значения, а сложенные итераторы.

Итератор - Итератор 1, Итератор 2, Итератор 3.

Метод convert должен принимать объект итератор итератор и возвращать Итератор чисел.

Iterator<Iterator<Integer> - ((4 2 0 4 6 4 9), (0 9 8 7 5), (1 3 5 6 7 0 9 8 4))

Метод должен возвращать Iterator<Integer> - (4 2 0 4 6 4 9 0 9 8 7 5 1 3 5 6 7 0 9 8 4)

Метод не должен копировать данные. Нужно реализовать итератор, который будет пробегать по вложенными итераторам без копирования данных.

Я никак не пойму, что от меня нужно в этом задании.

Каждый итератор это последовательность. Итератор 1 – 4 2 0 4 6 4 9

Что это за цифры - имеются в виду номера ячеек коллекций или что-то еще?

Итератор итераторов. Это в смысле коллекция, но итератор - это просто способ перебора коллекции. Как может быть итератор итераторов?

В чем вообще смысл задания? Это только мне оно кажется странным или нет? Что от меня хотят?

Да это обучение работы с итераторами. Я не понимаю что значат эти цифры в итераторе. Это номера ячеек по которым должен вести итератор, или это просто данные которые итератор должен возвращать по ходу своей работы инкрементируя как обычно по одному? — Pavel, Jan 09 '17 at 10:02
@Павел просто данные. А вообще, конечно, уточнять нужно у того, кто дал задание. Мало ли что и где подразумевалось. — Regent, Jan 09 '17 at 10:19

score 4 · Answer 1 · answered Jan 09 '17 at 12:51

Iterator это метод, который позволяет пробежаться по элементам коллекции
Iterator<Integer> - это метод который пробегается по элементам коллекции содержащей Integer
Iterator<Iterator<Integer>> - это метод который пробегает по итераторам Iterator<Integer>

Для понимания, например, Iterator<Integer> это способ обхода целочисленного одномерного массива данных, а Iterator<Iterator<Integer>> - это (например) способ обхода двумерного массива целочисленных данных.

Каждый итератор - это последовательность.

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

Ок. Итератор это правило(заданное по сути в методах hasNext() и next() ), я не сомневался в этом пока не увидел в задании "Итератор 1 – 4 2 0 4 6 4 9" что значат тогда эти цифры они меня путают и вносят неуверенность... Вряд ли это номера ячеек по которым итератор должен ходить... Но если нет тогда что это может быть? — Pavel, Jan 09 '17 at 13:17

user184868 · Accepted Answer · 2018-01-29T03:29:29.150

Вот вариант покороче:

import java.util.Arrays;
import java.util.Iterator;

public class IterIterator<N> implements Iterator<N> {

private Iterator<Iterator<N>> iters;
private Iterator<N> ptr;

public IterIterator(Iterator<N>... iters) {
    reset(iters);

}

public void reset(Iterator<N>... iters) {
    this.iters = Arrays.asList(iters).iterator();
    ptr = this.iters.hasNext() ? this.iters.next() : null;
}

@Override
public boolean hasNext() {
    return ptr != null;
}

@Override
public N next() {
    N n = ptr.next();

    while (ptr != null && !ptr.hasNext()) {
        ptr = this.iters.hasNext() ? this.iters.next() : null;
    }

    return n;
}

} Дополнено: в Java8 ещё проще через stream:

Collection<Integer> i1 = Arrays.asList(1, 2, 3, 4, 5, 6, 7);
          Collection<Integer> i2 = Arrays.asList(10, 20, 30, 40, 50);
            Collection<Integer> i3 = new ArrayList<Integer>();
            Collection<Integer> i4 = Arrays.asList(100, 200, 300, 400);

            Collection<Collection<Integer>> iter = Arrays.asList(i1,i2,i3,i4);

            iter.stream().forEach(col -> col.stream().forEach(i -> System.out.println(i)));

Владислав · Answer 3 · 2019-01-23T20:27:12.317

3

public class Converter {

    Iterator<Integer> convert(Iterator<Iterator<Integer>> it) {
        return new Iterator<Integer>() {
            private Iterator<Integer> iterator = (new ArrayList<Integer>()).iterator();
            @Override
            public boolean hasNext() {

                while (it.hasNext() && !iterator.hasNext()) {
                    iterator = it.next();
                }
                return iterator.hasNext();
            }

            @Override
            public Integer next() {
                if (!this.hasNext()) {
                    throw new NoSuchElementException();
                }
                return iterator.next();
            }
        };
    }
}

edited Jan 23 '19 at 20:27

answered Jan 23 '19 at 20:09

Владислав

31

Добро пожаловать на StackOverflow! Рекомендую давать пояснения к коду, чтобы было понятнее. – A K Jan 23 '19 at 20:12
точно соответствует заданию – Владислав Jan 23 '19 at 20:17

Artem · Answer 4 · 2017-01-09T10:32:35.413

2

Примерно так, должно быть:

public static void main(String[] args) throws Throwable {
    Iterator<Integer> i1 = Arrays.asList(4, 2, 0, 4, 6, 4, 9).iterator();
    Iterator<Integer> i2 = Arrays.asList(0, 9, 8, 7, 5).iterator();
    Iterator<Integer> i3 = Arrays.asList(1, 3, 5, 6, 7, 0, 9, 8, 4).iterator();

    Iterator<Integer> iterator = iterator(i1, i2, i3);
}

@SafeVarargs
private static <T> Iterator<T> iterator(Iterator<T>... iterators) {
    return new Iterator<T>() {
        private final Iterator<Iterator<T>> iterator;
        private Iterator<T> currentIterator;

        {
            List<Iterator<T>> iteratorList = new ArrayList<>(iterators.length);
            Collections.addAll(iteratorList, iterators);
            iterator = iteratorList.iterator();
        }

        private void check(){
            if (currentIterator == null && iterator.hasNext())
                currentIterator = iterator.next();
        }

        @Override
        public boolean hasNext() {
            check();
            if(currentIterator == null)
                return false;
            if(currentIterator.hasNext())
                return true;

            if(iterator.hasNext())
                currentIterator = iterator.next();

            return currentIterator.hasNext();
        }

        @Override
        public T next() {
            check();
            if(currentIterator == null)
                throw new NoSuchElementException();

            if(!currentIterator.hasNext() && iterator.hasNext())
                currentIterator = iterator.next();

            return currentIterator.next();
        }
    };
}

edited Jan 09 '17 at 10:32

answered Jan 09 '17 at 10:25

Artem

14,967

А что происходит в строчке Collections.addAll(iteratorList, iterators);??? Подскажите пожалуйста. – Pavel Jan 09 '17 at 13:48
@Павел добавление в коллекцию iteratorList всех элементов массива iterators. – Regent Jan 09 '17 at 13:52
Ага понял спасибо. А не подскажите еще про вот эту запись Arrays.asList(0, 9, 8, 7, 5).iterator(); что здесь происходит? В частности в Arrays.asList - что оно делает, и где берется этот метод .iterator()? – Pavel Jan 09 '17 at 14:09
@Павел Arrays.asList, как и описано в документации, возвращает список, созданный на основе переданного ему массива значений. Метод iterator есть у списка (List), так как тот расширяет Collection, который в свою очередь реализует интерфейс Iterable. – Regent Jan 09 '17 at 14:13
@Regent Да но на сколько я понял в разных коллекциях итератор реализован по разному. В принципе понятно что Arrays.asList делает коллекцию даже по названию но какой именно List и какой там будет итератор , ? Или я что-то не то уже спрашиваю..? – Pavel Jan 09 '17 at 14:17
@Павел так ведь неважно как итератор внутри реализован. Главное - как им пользоваться. На практике (включая этот вопрос-задачу) требуется, чтобы итератор умел корректно отвечать на вопрос, есть ли ещё итерации (hasNext), и возвращать элементы при вызове след. итерации (next). – Regent Jan 09 '17 at 14:21
Все равно не понимаю как работает этот блок инициализации и эта строчка Arrays.asList(1, 2, 3).iterator() – Pavel Jan 09 '17 at 18:25
В анонимных классах нельзя определить конструктор, поэтому использую блок инициализации. Он выполняется после создания объекта. Arrays.asList() - создает список из элементов которые были переданы в качестве параметров, далее для этого списка создается итератор. – Artem Jan 09 '17 at 18:55

Regent · Answer 5 · 2017-01-09T14:46:58.313

Лирическое отступление:
В вопросе идёт речь о реализации интерфейса с методом Iterator<Integer> convert(Iterator<Iterator<Integer>> it). Описание интерфейса - это уже один файл. Его реализация - второй. Можно, конечно, реализовывать его с помощью анонимного класса "прямо на месте", но это уже "на любителя". Ещё нужна реализация самого итератора итераторов - это третий и главный файл. Пытаться объединять его с реализацией интерфейса, на мой взгляд, не звучит как хорошая идея от слова "полностью". Тест находится в четвёртом, запускаемом классе (и файле). Можно его затолкать во второй или третий класс, но лучше от этого не станет.
О каком оверинжиниринге в таком случае речь - непонятно.

С учетом реализации указанного интерфейса (назвал его IteratorExtension), обработки пустых коллекций и вынесения итератора в отдельный класс:

Интерфейс:

import java.util.Iterator;

public interface IteratorExtension
{
    Iterator<Integer> convert(Iterator<Iterator<Integer>> it);
}

Его реализация:

import java.util.Iterator;

public class IteratorExtensionImpl implements IteratorExtension
{
    @Override
    public Iterator<Integer> convert(Iterator<Iterator<Integer>> it)
    {
        return new GroupIterator<>(it);
    }
}

Реализация итератора итераторов:

import java.util.*;

public class GroupIterator<T> implements Iterator
{
    private final Iterator<Iterator<T>> iterator;
    private Iterator<T> currentIterator = null;

    public GroupIterator(Iterator<Iterator<T>> iterator)
    {
        this.iterator = iterator;
    }

    @Override
    public boolean hasNext()
    {
        selectCurrentIterator();
        return (currentIterator != null && currentIterator.hasNext());
    }

    @Override
    public T next()
    {
        selectCurrentIterator();
        if (currentIterator == null)
        {
            throw new NoSuchElementException();
        }
        return currentIterator.next();
    }

    private void selectCurrentIterator()
    {
        if (currentIterator != null && currentIterator.hasNext())
        {
            return;
        }
        currentIterator = null;
        while (iterator.hasNext())
        {
            Iterator<T> nextIterator = iterator.next();
            if (nextIterator.hasNext())
            {
                currentIterator = nextIterator;
                break;
            }
        }
    }
}

Тест:

public static void main(String[] args)
{
    Iterator<Integer> i1 = Arrays.asList(4, 2, 0, 4, 6, 4, 9).iterator();
    Iterator<Integer> i2 = Arrays.asList(0, 9, 8, 7, 5).iterator();
    Iterator<Integer> i4 = new ArrayList<Integer>().iterator();
    Iterator<Integer> i3 = Arrays.asList(1, 3, 5, 6, 7, 0, 9, 8, 4).iterator();
    Iterator<Iterator<Integer>> iterator = Arrays.asList(i1, i2, i4, i3).iterator();
    IteratorExtension iteratorExtension = new IteratorExtensionImpl();
    Iterator<Integer> convertedIterator = iteratorExtension.convert(iterator);
    while (convertedIterator.hasNext())
    {
        System.out.print(convertedIterator.next() + " ");
    }
}

без обид, но это какой то оверинженеринг :) — Artem, Jan 09 '17 at 13:43
В методе selectCurrentIterator() в первом ифе наверно описались там return; а метод void. не как не могу прочесть что там делается. — Pavel, Jan 09 '17 at 13:46
@ArtemKonovalov я собирался сделать только GroupIterator, который, по сути, отличается от вашего только вынесением итератора в отдельный класс и обработкой пустых коллекций. Но в тексте вопроса неожиданно (при правке) всплыл интерфейс с методом Iterator<Integer> convert(Iterator<Iterator<Integer>> it), который нужно реализовать. Так что пришлось переделывать. — Regent, Jan 09 '17 at 13:51
@Павел опечаток нет. В случае возвращения методом void как раз и используется return; без конкретного значения. По сути, это просто выход из метода в этой точке. Метод делает следующее: если в текущем итераторе есть ещё итерации (hasNext возвращает true), то не трогаем его. Если нет - идём по следующим итераторам до тех пор, пока либо они не кончатся, либо не будет найден итератор, у кого есть итерации. — Regent, Jan 09 '17 at 13:54
Ого! В void методах можно использовать пустой return по типу break чтобы выйти из метода. Надо-же никогда не пробовал. Спасибо буду знать... — Pavel, Jan 09 '17 at 14:11

Объединение итераторов с помощью итератора итераторов

5 Answers5