Interview: Conception d'un itérateur sur une collection de collections

Conception d'un itérateur sur une collection de collections en java. L'itérateur doit masquer l'imbrication, vous permettant d'itérer l'ensemble des éléments appartenant à l'ensemble des collections, comme si vous travailliez avec une seule collection

Ce qu'il y a à ? Le prototype? La mise en œuvre?
à la fois, ce qui est de l'interface, et comment voulez-vous mettre en œuvre?
Si c'est votre entrevue d'emploi, pourquoi êtes-vous de les poster ici au lieu de simplement les faire?
Je ne voudrais pas concevoir quelque chose de moi-même -- je venais d'utiliser Google Collections: guava-libraries.googlecode.com/svn/trunk/javadoc/com/google/... . Cela dit, la mise en œuvre est assez simple si vous avez vraiment envie de le faire vous-même.
est votre besoin est quelque chose de ce genre-de la Collection parent = new ArrayList(); Collection slave1 = new ArrayList(); slave1.ajouter(10); slave1.ajouter(20); slave2 = new HashSet(); slave2.ajouter(30); slave2.ajouter(40); parent.ajouter(slave1); parent.ajouter(slave2);

OriginalL'auteur | 2010-07-24

Voici une implémentation possible. Note que j'ai laissé remove() n'est pas implémentée:

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
    }

}

Votre solution ne tient pas compte de la valeur null dans la collection de collections. Correctif: dans prepareNext(), la boucle intérieure devrait continuer jusqu'à ce qu'il.next() est non nulle, avant de le faire.next().iterator(), et il devrait renflouer si il n'y a pas de non-null objet de collection qu'il nous reste à utiliser.

OriginalL'auteur Eyal Schneider

C'est une vieille question, mais de nos jours (2019), nous avons JDK8+ goodies. En particulier, nous avons flux de, rendre cette tâche simple:

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

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

Je suis filtrage null intérieure collections, juste au cas où...

EDIT: Si vous aussi vous souhaitez filtrer null éléments de l'intérieur de collections, il suffit d'ajouter un supplément non-null filtre aflter flatMap:

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

OriginalL'auteur Federico Peralta Schaffner

Dans ce post vous pouvez voir deux implémentations, la seule (petite) différence est qu'il prend un itérateur de itérateurs au lieu d'une collection de collections.

Cette différence combinée avec l'obligation de parcourir les éléments dans un round robin (une exigence qui n'a pas été demandé par les OP dans ce question) ajoute la surcharge de copie des itérateurs dans une liste.

La première approche est paresseux: il réitérera un élément uniquement lorsque cet élément est demandée, le "prix" nous avons à payer est que le code est plus complexe, car il doit gérer plus de bord de cas:

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,
}
}
}

et la seconde ("avides" de la copie de tous les éléments de tous les itérateurs dans la demande d'ordre dans une liste et retourne un itérateur à cette liste ):

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,
}
}
}

J'ai inclus un simple "test" code afin de montrer la façon d'utiliser le MultiIterator, ce n'est pas toujours trivial (en raison de l'utilisation de médicaments Génériques) comme vous pouvez le voir sur la ligne:

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

OriginalL'auteur alfasin

Voici une autre mise en œuvre:

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();
}
}

OriginalL'auteur Geoffroy Warin

0

Tout d'abord, jetez un oeil à la mise en œuvre de l'itérateur en java.util.LinkedList

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

À partir de là, votre tâche est facile il suffit de mettre en œuvre une seule itérateur qui prend en compte le fait que c'est une itération sur les collections.

Ce qui concerne.

Pourquoi était-ce downvoted?
Il a valeur négative: Il prétend que l'analyse de LinkedList en quelque sorte vous donne une réponse, ce qui n'est pas (le vrai défi est de les deux niveaux de mise en œuvre, de ne pas obtenir un Itérateur à partir d'une Collection).

OriginalL'auteur Jose Diaz
0

si tout ce que vous avez à travailler avec des est java Itérateur: qui juste ont hasNext(), next() et remove(), j'ai pensé que vous devez aller autour d'elle.

La traiter comme vous pourrez le processus d'un tableau 2D, qui est, avec un extérieur et l'intérieur de la boucle, car ils ont le même "arrangement" mais le type de données différent. Comme vous le processus, de les transférer à une nouvelle collection.

alors peut-être une méthode privée:
```
    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"
}
```
fin

J'espère que cette aide. Il devrait y avoir d'autres façons de le résoudre, je suppose.

OriginalL'auteur Uche Dim

Vous devez vous connecter pour publier un commentaire.