Интервью: Разработка итератора для коллекции коллекций

Question

Разработка итератора для коллекции коллекций в Java. Итератор должен скрывать вложенность, позволяя вам перебирать все элементы, принадлежащие всем коллекциям, как если бы вы работали с одной коллекцией

Answer 1

Это старый вопрос, но в настоящее время (2019) у нас есть вкусности JDK8 +. В частности, у нас есть потоки, которые упрощают эту задачу:

public static <T> Iterator<T> flatIterator(Collection<Collection<T>> collections) {

    return collections.stream()
            .filter(Objects::nonNull)
            .flatMap(Collection::stream)
            .iterator();
}

Я фильтрую null внутренние коллекции, на всякий случай ...

---

РЕДАКТИРОВАНИЕ: Если вы также хотите отфильтровать null элементов из внутренних коллекций, просто добавьте дополнительный ненулевой фильтр после flatMap:

return collections.stream()
        .filter(Objects::nonNull)
        .flatMap(Collection::stream)
        .filter(Objects::nonNull)
        .iterator();

Answer 2

Вот возможная реализация. Обратите внимание, что я оставил remove () не реализованным:

public class MultiIterator <T> implements Iterator<T>{

    private Iterator<? extends Collection<T>> it;
    private Iterator<T> innerIt;
    private T next;
    private boolean hasNext = true;

    public MultiIterator(Collection<? extends Collection<T>> collections) {
        it = collections.iterator();    
        prepareNext();
    }

    private void prepareNext() {
        do {
            if (innerIt == null || !innerIt.hasNext()) {
                if (!it.hasNext()) {
                    hasNext = false;
                    return;
                } else
                    innerIt = it.next().iterator();
            }
        } while (!innerIt.hasNext());

        next = innerIt.next();
    }

    @Override
    public boolean hasNext() {
        return hasNext;
    }

    @Override
    public T next() {
        if (!hasNext)
            throw new NoSuchElementException();
        T res = next;
        prepareNext();
        return res;
    }

    @Override
    public void remove() {
        //TODO
    }

}

Answer 3

Вот еще одна реализация:

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

import static java.util.Collections.emptyIterator;

public class Multiterator<E> implements Iterator<E> {
    private Iterator<Iterator<E>> root;
    private Iterator<E> current;

    public Multiterator(Iterator<Iterator<E>> root) {
        this.root = root;
        current = null;
    }

    @Override
    public boolean hasNext() {
        if (current == null || !current.hasNext()) {
            current = getNextNonNullOrEmpty(root);
        }
        return current.hasNext();
    }

    private Iterator<E> getNextNonNullOrEmpty(Iterator<Iterator<E>> root) {
        while (root.hasNext()) {
            Iterator<E> next = root.next();
            if (next != null && next.hasNext()) {
                return next;
            }
        }
        return emptyIterator();
    }

    @Override
    public E next() {
        if (current == null) {
            throw new NoSuchElementException();
        }
        return current.next();
    }
}

Answer 4

В этом посте вы можете увидеть две реализации, единственное (незначительное) отличие состоит в том, что он принимает итератор итераторов вместо коллекции коллекций.

Это различие в сочетании с требованием циклически повторять элементы (требование, которое не было запрошено OP в этом вопросе) добавляет накладные расходы на копирование итераторовв список.

Первый подход ленив: он будет повторять элемент только при запросе этого элемента, «цена», которую мы должны заплатить, состоит в том, что код более сложный, потому что ему нужно обрабатывать больше границ-cases:

import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.NoSuchElementException;    

public class MultiIterator<E> implements Iterator {

    List<Iterator<E>> iterators = new LinkedList<>();
    Iterator<E> current = null;

    public MultiIterator(Iterator<Iterator<E>> iterator) {
        // copy the iterators into a list
        while (iterator.hasNext()) {
            iterators.add(iterator.next());
        }
    }

    @Override
    public boolean hasNext() {
        boolean result = false;
        if (iterators.isEmpty() && (current == null || !current.hasNext())) {
            return false;
        }

        if (current == null) {
            current = iterators.remove(0);
        }

        while (!current.hasNext() && !iterators.isEmpty()) {
            current = iterators.remove(0);
        }

        if (current.hasNext()) {
            result = true;
        }
        return result;
    }

    @Override
    public E next() {
        if (current == null) {
            try {
                current = iterators.remove(0);
            } catch (IndexOutOfBoundsException e) {
                throw new NoSuchElementException();
            }
        }
        E result = current.next(); // if this method was called without checking 'hasNext' this line might raise NoSuchElementException which is fine
        iterators.add(current);
        current = iterators.remove(0);
        return result;
    }

    // test
    public static void main(String[] args) {
        List<Integer> a = new LinkedList<>();
        a.add(1);
        a.add(7);
        a.add(13);
        a.add(17);
        List<Integer> b = new LinkedList<>();
        b.add(2);
        b.add(8);
        b.add(14);
        b.add(18);
        List<Integer> c = new LinkedList<>();
        c.add(3);
        c.add(9);
        List<Integer> d = new LinkedList<>();
        d.add(4);
        d.add(10);
        d.add(15);
        List<Integer> e = new LinkedList<>();
        e.add(5);
        e.add(11);
        List<Integer> f = new LinkedList<>();
        f.add(6);
        f.add(12);
        f.add(16);
        f.add(19);
        List<Iterator<Integer>> iterators = new LinkedList<>();
        iterators.add(a.iterator());
        iterators.add(b.iterator());
        iterators.add(c.iterator());
        iterators.add(d.iterator());
        iterators.add(e.iterator());
        iterators.add(f.iterator());
        MultiIterator<Integer> it = new MultiIterator<>(iterators.iterator());
        while (it.hasNext()) {
            System.out.print(it.next() + ","); // prints: 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,
        }
    }
}

и второй («жадное» копирование всех элементов со всех итераторов в требуемом порядке в список и возврат итератора в этот список):

import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;

public class MultiIterator<E> {

    Iterator<Iterator<E>> iterator = null;
    List<E> elements = new LinkedList<>();

    private MultiIterator(Iterator<Iterator<E>> iterator) {
        this.iterator = iterator;
    }

    private void copyElementsInOrder() {
        List<Iterator<E>> iterators = new LinkedList<>();
        // copy the iterators into a list
        while (iterator.hasNext()) {
            iterators.add(iterator.next());
        }
        // go over the list, round-robin, and grab one
        // element from each sub-iterator and add it to *elements*
        // empty sub-iterators will get dropped off the list
        while (!iterators.isEmpty()) {
            Iterator<E> subIterator = iterators.remove(0);
            if (subIterator.hasNext()) {
                elements.add(subIterator.next());
                iterators.add(subIterator);
            }
        }
    }

    public static <E> Iterator<E> iterator(Iterator<Iterator<E>> iterator) {
        MultiIterator<E> instance = new MultiIterator<>(iterator);
        instance.copyElementsInOrder();
        return instance.elements.iterator();
    }

    // test
    public static void main(String[] args) {
        List<Integer> a = new LinkedList<>();
        a.add(1);
        a.add(7);
        a.add(13);
        a.add(17);
        List<Integer> b = new LinkedList<>();
        b.add(2);
        b.add(8);
        b.add(14);
        b.add(18);
        List<Integer> c = new LinkedList<>();
        c.add(3);
        c.add(9);
        List<Integer> d = new LinkedList<>();
        d.add(4);
        d.add(10);
        d.add(15);
        List<Integer> e = new LinkedList<>();
        e.add(5);
        e.add(11);
        List<Integer> f = new LinkedList<>();
        f.add(6);
        f.add(12);
        f.add(16);
        f.add(19);
        List<Iterator<Integer>> iterators = new LinkedList<>();
        iterators.add(a.iterator());
        iterators.add(b.iterator());
        iterators.add(c.iterator());
        iterators.add(d.iterator());
        iterators.add(e.iterator());
        iterators.add(f.iterator());
        Iterator<Integer> it = MultiIterator.<Integer>iterator(iterators.iterator());
        while (it.hasNext()) {
            System.out.print(it.next() + ","); // prints: 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,
        }
    }
}

Я включил простой «тестовый» код, чтобы показать способ использования MultiIterator, это не всегда тривиально (из-за использования Общих), как вы можете видеть в строке:

Iterator<Integer> it = MultiIterator.<Integer>iterator(iterators.iterator());

Answer 5

Если все, с чем вам нужно работать, это java Iterator: у которого просто есть hasNext (), next () и remove (), я подумал, что вам нужно обойти это.

Обработайте его так же, как обработайте двумерный массив, то есть с внешним и внутренним циклом, поскольку они имеют одинаковое «расположение», но разные типы данных.По мере обработки вы переносите их в новую коллекцию.

, поэтому, возможно, это частный метод:

    private void convertToSingleCollection()
    {


         while("column")
         {
            //convert the "column" to an arra


           for( "Row")
           {
            //add to newCollection here
           }

          //remove the processed column from CollectionOFcollection
         } 
    }
    //call the above method in your constructor


    public iterator<T> Iterator()
    {
       newCollection.iterator();
    }

    public boolean hasNext()
    {
       return Iterator().hasNext()
    }

    public T next()
    {
       if(!hasNext())
       {
        //exception message or message
       }
       else
           //return "next"
    }

end

Надеюсь, это поможет.Я думаю, должны быть и другие способы ее решения.

Answer 6

Во-первых, взгляните на реализацию итератора в java.util.LinkedList

http://www.docjar.com/html/api/java/util/LinkedList.java.html

Оттуда ваша задача проста - просто реализовать один итератор, который учитываеттот факт, что он перебирает коллекции.

С уважением.